数据结构练习题 第二章 线性表 习题及答案(4)

(4)删除DELDTE(L,i) 在带头结点的单链表上实现的算法为： void delete_lklist(lklist head,int i) /*删除表head的第i个结点*/ {p=find_lklist(head,i-1) /*先找待删结点的直接前驱*/ if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/ (q=p->next; /*q指向待删结点*/ p->next=q->next/*摘除待结点*/; free(q);/*释放已摘除结点q*/ } else error(“不存在第i个结点”)/*否则给出相关信息*/ } 在无头结点的单链表上实现的算法为： void Wdelete(lklist head,int i) /* 删除表head的第i个结点，若该链表仅有一个结点时，赋该结点指针NULL*/ {if(i<=0) error(“I＜＝0” else{if(i= =0){q=head;head=head->next;free(q);} else{p=wfind_lklist(head,i-1);/*找链表head中第i-1结点指针*/ if(p!=NULL)&&(p->next!=NULL) ｛q=p->next; p->next=q->next; free(q);｝ else error(“不存在第I个结点”)； ｝ ｝ ｝ 3、 分析：从第一个结点开始访问，只要是非空计数一次。 Int wlength_lklist(lklist head) /*求表head的长度*/ {p=head;j=0; while(p!=NULL){p=p->next;j++;} return(j); /*回传表长*/ ｝ 4、 设A,B,C均为无头结点单链表 分析：（1）当有序表A，B均非空时，找出两表中元素最小的一个元素，然后将此结点插入到C表中，重复上述步骤。 （2）当A，B两表有一个为空表时，将另一表中元素顺序地插入到C表中。 （3）由于C按递减排序，因此在C表中插入元素时，应始终插入到C表表头。 Lklist Wlink_lklist(lklist A,lklist B) { while((A!=NULL)&&(B!=NULL)) if(A->datadata){p=A;A=A->next;} else 16

p->next=C;C=p; } if(A= =NULL) A=B; while(A!=NULL) {p=A;A=A->next; p->next=C;C=p;} return(C); } 5、 分析：（1）当有序表A、B均非空时，依次分别从A、B表头部取下结点，插入C表中。 （2）当A、B两表有一个为空表时，将非空表插入到C表尾部。 设A，B，C均为带头结点的单链表 lklist HB_lklist(lklist A,lklist B) { C=A; A=A->next;B=B->next; //去除头结点 While((A!=NULL)&&(B!=NULL)) {p->next=A;p=p->next;A=A->next; p->next=B;p=p->next;B=B->next; } if((B= =NULL)&&(A!=NULL)) p->next=A; else if((A= =NULL)&&(B!=NULL)) p->next=B; Return(c); } 6、 分析：从有序表的尾部开始依次取元素与插入元素比较，若大于插入元素，此元素后移一位，再取它前面一个元素重复上述步骤；则将待插入元素插入。 Void CR(datatype A[],datatype X,int elenum) { i=elenum-1; while((i>=0)&&Xnext; while((p!=NULL)&&(p->datanext;}/*查X插入位置q*/ 17

s=malloc(size);s->data=s; } 8、 (1)顺序表 分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换。 Void NZ_sqlist(sqlist A) {for{i=0;i<((A.last-1)/2);i++} {x=A.data[i]; A.data[i]=A.data[A.last-i-1]; A.data[A.last-i-1]=x; } } (2)单链表 分析：将原单链表的元素依次取出，再插入另一个单链表的头部。 设该单链表为无头结点，s为指向表的第一个结点的指针。 Void NZ_lklist(lklist s) {p=NULL; /*p指向当前结点的前趋结点*/ /*将原单链表的元素依次取出到q*/ /*再插入另一个单链表p的头部*/ while(s!=NULL) { q=s;s=s->next; q->next=p;p=q; } s=p; /*s指向新单链表的第一个结点*/ } 9、 分析：A与B的交是指A与B的相同部分元素，即那些在A中出现又在B中出现的元素。由于A、B是有序表，故从表头开始依次比较当前指针所指元素的值是否相同，若相同，在C表中插入该元素，然后将两个表的指针后移，否则指向较小元素的指针后移。重复上述步骤，直到A，B表中有一个表到表尾。 (1)顺序表 sqlist HDZ_sqlist(sqlist A,sqlist B) { t=0;j=0;k=0; while((t<=A.last-1)&&(j<=B.last-1)) switch{ case A.data[i]B.data[j];j++;break; case A.data[i]= =B.data[j];C.data[k]=A.data[i];k++;i++;j++;break; } C.last=k; Return(c ); } (2)单链表（设带头结点） 18

lklist HDZ_lklist(lklist A,lklist B) { C=initiate_lklist(); r=C;p=A->next;q=B->next:; While ((p!=null)&&(q!=null)) Switch { case p->data data: p=p->next;break; case p->data data: q=q->next;break; case p->data==q->data; s=malloc(size);s->data=p->data; s->next=r->next; r->next=s; r=s; p=p->next;q=q->next; } return(c); } 10.分析：①在有序表B、C中找出相同元素X； ②若X在表A中出现则删除，否则转①； ③重复①②直到B、C表有一个表查找完毕。 （1） 顺序表 void ASBC_sqlist(sqlist A, sqlist B, sqlist C) {I=0;j=0;k=0; while ((jnext;q= A; 19

pb= B ->next;pc= C ->next; while ((pb!=null)&&(pc!=null)) switch { case pb->datadata: pb=pb->next;break; case pb->datadata: pc=pc->next;break; case pb->data= =pc->data:/* B、C中找到相同元素*/ if(pa= =null)return; if (pa->data= =pb->data)/*在 A中存在 B、C 表共有元素，删除*/ {q->next=pa->next; free(pa);pa=q->next;} pb=pb->next;pc=pc->next; } } } 11．分析设置两个指针，分别指向*S及其后继，然后按循环链表特性，顺序往下查找*s的 直接前趋，找到后删除； void DELETE_Xlklist(lklist S) {p=s; q=p->next; while (q->nest!=s) { p=q; q=q->next;} p->next=s; free(q); } 12．分析：在链表L中依次取元素，若取出的元素是字母，把它插入到字母B中，然后在L中删除该元素；若取出的元素是数字，把它插入到数字链D中，然后在L中删除该元素。继续取下一个元素，直到链表的尾部。最后B、D、L中分别存放的是字母字符、数字字符和其它字符。 设原表有头结点、头指针L，新建数字字符链D，字母字符链B，其它字符链R。 void DISM_lklist(lklist L,lklist D,lklist B,lklist R) { D =malloc(size of(int)); D ->next= D; /*建D循环链表头结点*/ B =malloc(sizeof(char)); B ->next= B; /*建B循环链表头结点*/ p= L;q=p->next; while(q!=null) {if((q->data<=’9’)&&(q->data>=’0’)) {p->next=q->next; /*在表L 中摘除q结点*/ q->next= D ->next; D ->next=q; /*将q结点插入D中*/ q=p->next; /*移动q指针*/ } else if (q->data<=’z’)&&(q->data>=’a’)||(q->data<=’z’)&&(q->data>=’a’)) 20