第二章 线性表(9)

NODE *append (NODE *last,int e)

27

{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 (1)___ if (A->elementelement) { last=append(last,A->element); A=A->link; }

else if (2) ___ { A=A->link; B=B->link; } ELSE (3) ___ ; while (4) __ { last=append(last,A->element); A=A->link; } (5) ___; last=C; C=C->link; free (last); return (C); }

/*call form:C=difference(A,B);*/ 【上海大学 2000 一.4 （10分）】

(1)(A!=null && B!=null) ∥两均未空时循环

(2)A->element==B->element ∥两表中相等元素不作结果元素 (3)B=B->link ∥向后移动B表指针

(4)(A!=null) ∥或(A) 将A 表剩余部分放入结果表中 (5)last->link=null ∥置链表尾

27. 判断带头结点的双向循环链表L是否对称相等的算法如下所示，请在划线处填上正确的语句。 【华南师范大学 2000年 五.1 ( 9分)】 FUNCTION equal(l:pointer) :boolean; VAR p,q:pointer; result: Boolean;

BEGIN result:=true ; p:= l^.link; q:=l^.pre ; WHILE (p<>q) AND ((1)_______)DO

IF p^.data=q^.data THEN BEGIN (2)___; (3)____; END； ELSE result:=false ; return(result); END;

(1)result; (2)p:=p^.link; (3) q:=q^.pre （（２）（３）顺序可变）

2. 28. LinkList exam2(LikeList l) { //L是无头结点的的单链表 ListNode *P,*Q; if (L && L->next)

{ Q=L; L=L->next; P=L; while ( P->next ) P=P->next;

28

P->next=Q; Q->next=NULL; }//if return L; }//exam2

程序段2 的功能是将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针；（根据答题情况酌情给分）

七、算法设计题

1．统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x) nt CountX(LNode* HL,ElemType x)

{ int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)

{ if (P->data==x) i++; p=p->next;

}//while, 出循环时i中的值即为x结点个数 return i;

}//CountX

2. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。

typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) {

lklist *p,*q,*t;

for(p=ha,hc=0;p!=0;p=p->next)

{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;

if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } }

3．设计在单链表中删除值相同的多余结点的算法。

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) {

lklist *p,*q,*s;

for(p=head;p!=0;p=p->next) {

for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}

29

else {s=q,q=q->next;}

}

}

4．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

typedef char datatype;

typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) {

lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) {

head=p->next; p->next=0;

if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}

else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;}

}

}

5．设计两个有序单链表的合并排序算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc) {

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}

else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; }

6．设计将所有奇数移到所有偶数之前的算法。

void quickpass(int r[], int s, int t) {

int i=s,j=t,x=r[s]; while(i

while (i

7．设计判断单链表中元素是否是递增的算法。

int isriselk(lklist *head) {

if(head==0||head->next==0) return(1);else

30