05到09年福建专升本数据结构真题详解

为非递减(从小到大)有序(如下图)。用指针current从head开始搜索数据域等于key的元素在线性表中位置，如果搜索成功则current指向搜索到的结点，函数返回该指针：如果搜索不成功，函数返回空指针NULL。请在函数

SortedlistLocate(head，key)

内填空，完成下列算法以实现这种搜索，并使得搜索不成功的平均比较次数小于链表长度。（发现current指向结点的数据域比key大，则停止搜索，后面肯定没有key，搜索失败。这样就没有必要走到链表的尾部，不成功的平均比较次数=(0+1+2+..+n)/(n+1)=n/2）

注意：有头结点，是单循环链表。空表如下

typedef struct node{

elemtype data；/*数据域*/ struct node next；/*指针域*/ }lnode，*linklist；

注意typedef，lnode和linklist是类型名 linklist SortedlistLocate ( linklist head，

elemtype key){

linklist current；

if(_head==NULL_)return ERROR；

/*错误提示*/

current ___=head->next____;

/*循链搜索其值等于key的结点*/

while(_current!=head_&&_current->data

current=current-->next；

/*排除空表*/

if ( _ current !=head && current->data==key _) return current； /*找到，返回结点地址*/ else

return NULL； /*末找到，返回空指针*/ }

25．r[]为一维数组，其中r[0]到r[n-1]为待排序的n个元素，排序好的元素仍放在r[0]到r[n-1]中。请写出对该数组进行非递减排序的直接插入排序算法， 取名为InsertSort(elemtype r[]，int n)。