数据结构考研分类复习真题 第二章 线性表[22]

．对单链表中元素按插入方法排序的C语言描述算法如下其中L为链表头结点指针请填充算法中标出的空白处完成其功能

typedef struct node

{int data; struct node *next;

}linknode*link;

void Insertsort(link L)

{ link pqru;

p=L>next; () ;

while( () )

{ r=L; q=L>next;

while( () && q>data<=p>data) {r=q; q=q>next;}

u=p>next; () ; () ; p=u;

}

}【北京科技大学 二 （分）】

．下面是一个求两个集合A和B之差C=AB的程序即当且仅当e是A的一个元素但不是B中的一个元素时e才是C中的一个元素集合用有序链表实现初始时AB集合中的元素按递增排列C为空操作完成后AB保持不变C中元素按递增排列下面的函数append(laste)是把值为e的新结点链接在由指针last指向的结点的后面并返回新结点的地址函数difference(AB)实现集合运算AB并返回表示结果集合C的链表的首结点的地址在执行AB运算之前用于表示结果集合的链表首先增加一个附加的表头结点以便新结点的添加当AB运算执行完毕再删除并释放表示结果集合的链表的表头结点

程序(a)（编者略去这个PASCAL程序）

程序（b）

typedef struct node{ int element; struct node *link;

}NODE;

NODE *A*B*C;

NODE *append (NODE *lastint e)

{ last>link=(NODE*) malloc (sizeof(NODE));

last>link>element=e;

return(last>link);

}

NODE *difference(NODE *ANODE *B)

{NODE *C*last;

C=last=(NODE*) malloc (sizeof(NODE));

while ()

if (A>element<B>element) { last=append(lastA>element); A=A>link; }

else if () { A=A>link; B=B>link; } ELSE () ;

while ()

{ last=append(lastA>element); A=A>link; }

() ; last=C; C=C>link; free (last); return (C);

}

/*call form:C=difference(AB);*/【上海大学 一 （分）】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []