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

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

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

　　typedef struct node　　{int data;  struct node *next;　　}linknode *link;　　void Insertsort(link L)　　{ link p q r u;　　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=A B的程序 即当且仅当e是A的一个元素 但不是B中的一个元素时 e才是C中的一个元素 集合用有序链表实现 初始时 A B集合中的元素按递增排列 C为空 操作完成后A B保持不变 C中元素按递增排列 下面的函数append(last e)是把值为e的新结点链接在由指针last指向的结点的后面 并返回新结点的地址 函数difference(A B)实现集合运算A B 并返回表示结果集合C的链表的首结点的地址 在执行A B运算之前 用于表示结果集合的链表首先增加一个附加的表头结点 以便新结点的添加 当A B运算执行完毕 再删除并释放表示结果集合的链表的表头结点

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

　　程序（b）

　　typedef struct node{ int element;  struct node *link;　　}NODE;　　NODE  *A *B *C;　　NODE  *append (NODE *last int e)　　{  last >link=(NODE*) malloc (sizeof(NODE));　　last >link >element=e;　　return(last >link);　　}　　NODE *difference(NODE *A NODE *B)　　{NODE *C *last;　　C=last=(NODE*) malloc (sizeof(NODE));　　while   ( )　　if (A >element<B >element) { last=append(last A >element);  A=A >link;  }　　else  if   ( )    { A=A >link;  B=B >link;  } ELSE    ( )    ;　　while   ( )　　{ last=append(last A >element); A=A >link;  }　　( )   ;  last=C;    C=C >link;  free (last);   return (C);　　}　　【上海大学 一 （ 分）】