第二章参考答案 、名词解释(略) 、填空题 1、结点起始终端序号位置前趋后趋 3、前趋前趋后趋后趋 4、线性 5、线性长度表长 6、空表 7、初始化 INITLATE(L)求表长 LENGTH(L)读表长GET(L,i)定位 LOCATE (L,X)插入 INSERT(L,X,i)删除 DELETE(L,i) 8、逻辑结构中相邻的结点在存储结构中仍相邻 9、b+(i-1)xk 10, L. datal]=L. data[j-1 ll、nO(n)n/2O(n) 12, Ldata[j-2=l data[j-1 14、i=1 ≡L.last 15、O(n)O 16、 L last L data[i-1 17、单链表循环链表双链表 18、指针19,单链表 20、头结点表结点 21、首结点尾结点任何信息、特殊标志表长 22、头结点头结点 23, t=malloc(size) t->next=NULL 24、p- haed p=p->next 25,(p->next!=NULL)&&lnext!=NULL)&&(p->data!=x) 27,(p!=NULL)&&(p->next!=NULL)p->next 28, maillot(size)p->next 29, insert lklist(head, x, 1)I++ n(n-1)/2 O(n) 30, p=q p->next=NULL O(n) 31、单向循环链表(简称循环链表)双向循环链表(简称双链表) 32、NULL头结点 33、双链表 34、字符数组赋值 35、空中非空字符 36、长度相同子主 37、非紧缩紧缩 38、结点大小不属于字符集的特殊符号 三、单项选择题 1、②2、①3、①4、②5、①6、②7、③8、③9、④ 10、②11、④12、③13、⑤14、④15、③16、①17、②18、③ 19、④20、④21、④22、223、②24、③25、④26、②27、③ 28、④29、①30、④31、②32、②33、④34、④35、③36、③ 37、②38、③39、②40、①41、④
1 第二章 参考答案 一、名词解释 (略) 二、填空题 1、结点 起始 终端 序号 位置 前趋 后趋 2、() ф 3、前趋 前趋 后趋 后趋 4、线性 5、线性 长度 表长 6、空表 7、初始化 INITLATE(L) 求表长 LENGTH(L) 读表长 GET(L,i) 定位 LOCATE (L,X) 插入 INSERT(L,X,i) 删除 DELETE(L,i) 8、逻辑结构中相邻的结点在存储结构中仍相邻 9、b+(i-1)x k 10、L.data[j]=L.data[j-1] 11、n O(n) n/2 O(n) 12、L.data[j-2]=l.data[j-1] 13、n-1 o(n) (n-1)/2 O(n) 14、i=1 i≦L.last 15、O(n) O(1) 16、L.last L.data[i-1] 17、单链表 循环链表 双链表 18、指针 19,单链表 20、头结点 表结点 21、首结点 尾结点 任何信息、特殊标志 表长 22、头结点 头结点 23、t=malloc(size) t->next=NULL 24、p=haed p=p->next 25、(p->next!=NULL)&&(jnext!=NULL)&&(p->data!=x) 27、(p!=NULL)&&(p->next!=NULL) p->next 28、mailloc(size) p->next 29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n2 ) 30、p=q p->next=NULL O(n) 31、单向循环链表(简称循环链表) 双向循环链表(简称双链表) 32、NULL 头结点 33、双链表 34、字符数组 赋值 35、空 ф 非空 字符 36、长度 相同 子 主 37、非紧缩 紧缩 38、结点大小 不属于字符集的特殊符号 三、单项选择题 1、②2、①3、①4、②5、①6、②7、③8、③9、④ 10、②11、④12、③13、⑤14、④15、③16、①17、②18、③ 19、④20、④21、④22、223、②24、③25、④26、②27、③ 28、④29、①30、④31、②32、②33、④34、④35、③36、③ 37、②38、③39、②40、①41、④
四、简答及应用 1、线性表的数据元素的类型为 datatype,则在语言上可用下述类型定义来描述顺序表: const maxsize=顺序表的容量 typedef struct i datatype data [maxsize I sqlist qlist L 数据域data是一个一维数组,线性表的第1,2…,n个元素分别存放在此数组的 第0,1 ,1ast-1个分量中,数据域last表示线性表当前的长度,而last-1是线性 表的终端结点在顺序表中的位置。常数 maxsize称为顺序表的容量,从last到 maxsize-1 为顺序表当前的空闲区(或称备用区)。 Sqlist类型完整地描述了顺序表的组织。L被说明为 sqlist类型的变量,即为一顺 序表,其表长应写为L.1ast,而它的终端结点则必须写为 L data[L.1ast-1]。 2、假设数据元素的类型为 datatype。单链表的类型定义如下: typedef struct node *pointer struct node Datatype data pointer next typedef pointer lklist 其中,① poster是指向 struct node类型变量的指针类型;② struct node是结构体 类型规定一个结点是由两个域data和next组成的记录,其中data的结点的数据域,next 是结点的链域:③ krist与 pointer相同类型,用来说明头指针变量的类型,因而 krist 也就被用来作为单链表的类型 3 typedef struct dnode *pointer struct dnode pointer prior, next typedaf pinter dlklist 链域 prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所 在的结点。所有结点通过前趋和后继指针链接在一起,再加上起标识作用的头指针,就得到 双向循环链表。 4、顺序串的类型定义与顺序表类似,可描述如下: const maxlen=串的最大长度 typedef struct Ichar ch[maxlen string 5、链串的类型定义为 const nodesize=用户定义的结点大小 typedef struct node * pointer 2
2 四、简答及应用 1、线性表的数据元素的类型为 datatype,则在语言上可用下述类型定义来描述顺序表: const maxsize=顺序表的容量; typedef struct { datatype data[maxsize] int last; }sqlist; sqlist L; 数据域 data 是一个一维数组,线性表的第 1,2……,n 个元素分别存放在此数组的 第 0,1,……,last-1 个分量中,数据域 last 表示线性表当前的长度,而 last-1 是线性 表的终端结点在顺序表中的位置。常数 maxsize 称为顺序表的容量,从 last 到 maxsize-1 为顺序表当前的空闲区(或称备用区)。 Sqlist 类型完整地描述了顺序表的组织。L 被说明为 sqlist 类型的变量,即为一顺 序表,其表长应写为 L.last,而它的终端结点则必须写为 L.data[L.last-1]。 2、假设数据元素的类型为 datatype。单链表的类型定义如下: typedef struct node *pointer struct node {datatype data; pointer next; }; typedef pointer lklist; 其中,①ponter 是指向 struct node 类型变量的指针类型;②struct node 是结构体 类型规定一个结点是由两个域 data 和 next 组成的记录,其中 data 的结点的数据域,next 是结点的链域;③lklist 与 pointer 相同类型,用来说明头指针变量的类型,因而 lklist 也就被用来作为单链表的类型。 3、typedef struct dnode *dpointer; struct dnode {datatype data; dpointer prior,next; } typedaf dpinter dlklist; 链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所 在的结点。所有结点通过前趋和后继指针链接在一起,再加上起标识作用的头指针,就得到 双向循环链表。 4、顺序串的类型定义与顺序表类似,可描述如下: const maxlen=串的最大长度 typedef struct {char ch[maxlen] int curlen; }string 5、链串的类型定义为: const nodesize=用户定义的结点大小; typedef struct node *pointer;
struct node Ichar ch[ oqeslze polnernext typedef pointer strlist 当结点大小为1时,可将ch域简单地定义为: char ch 6、head称为头指针变量,该变量的值是指向链表的第一个结点的指针,称为头指针。头指 针变量是用于存放头指针的变量 为了便于实现各种运算,通常在单链表的第一个结点之前增设一个类型相同的结点,称 为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。 头指针变量的作用:对单链表中任一结点的访问,必须首先根据头指针变量中存放的头 指针找到第一个结点,再依次按各结点链域存放的指针顺序往下找,直到找到或找不到。头 指针变量具有标识单链表的作用,故常用头指针变量为命名单链表 头结点的作用:头结点的数据域可以不存储任何信息,也可以存放一个特殊标志或表长 其作用是为了对链表进行操作时,将对第一个结点煌处理和对其它结点的处理统一起来 7、循环单链表、循环双链表 8、空串和空格串:含0个字符的串称为空串,其长度为0。空格串是含有一个或多处空格 字符组成的串,其长度不为0。 串变量和串常量:串常量在程序的执行过程中只能引用不能改变而串变量的值在程序执 行过程中是可以改变和重新赋值的 主串和子串:一个串中任意个连续字符组成的子序列称为该串的子串,该串称为它的所 以子串的主串。 串变量的名字与串变量的值:串变量的名字表示串的标识符:串变量的值表示串变量的 字符序列 9、(a)A+B mule” (b)b+A “mule (c)D+C+B “ myoldmt (dSUBSTR(B, 3, 2) “le (g)LENGTH(D) (h)INDEX(B, D) 0 (i) DINDEX(C,”"d”) 3 OINSERT(D, 2, C) “ mold (k)INSERT(B, 1, A) mule” (DELETE(B, 2, 2) (m)DELETE(B, 2,0) 10、 REPLACE(S, SUBSTR(T,7,1) SUBSTR(T,3,1), CONCAT(S,”y”) 五、算法设计 1、分析:(1)当A、B表都不为空时,比较A,B表中各元素对应位置的内容的大小, 进而判断A,B的大小 (2)当A,B表都不为空时,且A,B表中各各元素对应位置的内容相同时, 比较A,B的长度,进而判断A,B的大小或是否相等
3 struct node {char ch[nodesize] poinernext; } typedef pointer strlist; 当结点大小为 1 时,可将 ch 域简单地定义为:char ch 6、head 称为头指针变量,该变量的值是指向链表的第一个结点的指针,称为头指针。头指 针变量是用于存放头指针的变量。 为了便于实现各种运算,通常在单链表的第一个结点之前增设一个类型相同的结点,称 为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。 头指针变量的作用:对单链表中任一结点的访问,必须首先根据头指针变量中存放的头 指针找到第一个结点,再依次按各结点链域存放的指针顺序往下找,直到找到或找不到。头 指针变量具有标识单链表的作用,故常用头指针变量为命名单链表。 头结点的作用:头结点的数据域可以不存储任何信息,也可以存放一个特殊标志或表长。 其作用是为了对链表进行操作时,将对第一个结点煌处理和对其它结点的处理统一起来。 7、循环单链表、循环双链表。 8、空串和空格串:含 0 个字符的串称为空串,其长度为 0。空格串是含有一个或多处空格 字符组成的串,其长度不为 0。 串变量和串常量:串常量在程序的执行过程中只能引用不能改变而串变量的值在程序执 行过程中是可以改变和重新赋值的。 主串和子串:一个串中任意个连续字符组成的子序列称为该串的子串,该串称为它的所 以子串的主串。 串变量的名字与串变量的值:串变量的名字表示串的标识符;串变量的值表示串变量的 字符序列。 9、(a)A+B “ mule” (b)B+A “mule ” (c)D+C+B “myoldmule” (d)SUBSTR(B,3,2) “le” (e)SUBSTR(C,1,0) “ ” (f)LENGTH(A) 2 (g)LENGTH(D) 2 (h)INDEX(B,D) 0 (i)INDEX(C,”d”) 3 (j)INSERT(D,2,C) “myold” (k)INSERT(B,1,A) “m ule” (l)DELETE(B,2,2) “me” (m)DELETE(B,2,0) “mule” 10、REPLACE(S,SUBSTR(T,7,1),SUBSTR(T,3,1));CONCAT(S,”y”); 五、算法设计 1、 分析:(1)当 A、B 表都不为空时,比较 A,B 表中各元素对应位置的内容的大小, 进而判断 A,B 的大小。 (2)当 A,B 表都不为空时,且 A,B 表中各各元素对应位置的内容相同时, 比较 A,B 的长度,进而判断 A,B 的大小或是否相等
const maxsize=顺序表的容量; fint data maxsize i sqlist; int CMP sqlist(sqlist A sqlist B) i for (i=0; (iB data[i]return(1); (A last==B last)return(O) else if(A last>. last)return(1); 2、(1)定位 LOCATE(L,X 在带头结点类单链表上实现的算法为 int locate lklist(lklist head, datatype x) *求表head中第一个值等于x的的序号,不存在这种结点时结果为0*/ /*置初值 while((p!=NULL)&&(p->datal=x)) {p=p-> next:J++}/*未达表结点又未找到值等于Ⅹ的结点时经,继续扫描 if(p->data==x) return(; eturn(0) 在无头结点的单链表上实现的算法为: int Locate(lklist head, datatype X) 求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ ip=head; j=l /*置初值* while((p!=NULL)&&(p->datal=x)) {p=p->next计++}/未达表结点又未找到值等于X的结点时经,继续扫描* if( p->data==X) return( return(O) (2)按序号查找find(L,i) 在带头结点的单链表上实现的算法为: pointer find Iklist(Iklist head, int i) (=l; p=head->next; while((next; j++) if(i==j return(p) else return(NULL) 在无头结点的单链表上实现的算法为: pointer find lklist(lklist head, int i)
4 const maxsize=顺序表的容量; typedef struct {int data[maxsize] int last; }sqlist; int CMP_sqlist(sqlist A ,sqlist B) { for (i=0;(iB.data[i])return(1); } if(A.last= =B.last) return(0); else if(A.last>B.last) return(1); else return(-1); } 2、(1)定位 LOCATE(L,X) 在带头结点类单链表上实现的算法为: int locate_lklist(lklist head,datatype x) /*求表 head 中第一个值等于 x 的的序号,不存在这种结点时结果为 0*/ {p=head->next;j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于 X 的结点时经,继续扫描*/ if (p->data = =x) return(j); else return(0); } 在无头结点的单链表上实现的算法为: int Wlocate(lklist head,datatype X) /*求表 head 中第一个值等于 x 的结点的序号。不存在这种结点时结果为 0*/ {p=head; j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于 X 的结点时经,继续扫描*/ if( p->data = =X) return(j); else return(0); } (2)按序号查找 find(L,i) 在带头结点的单链表上实现的算法为: pointer find_lklist(lklist head , int i); { j=1; p=head->next; while((jnext; j++} if(i= = j) return(p); else return(NULL); } 在无头结点的单链表上实现的算法为: pointer find_lklist(lklist head , int i);
while((next; j ++ else return(NULL) (3)、插入 INSERT(L,X,i) 在带头结点单链表上实现的算法为: void insert Iklist(Iklist head, datatype x, int I) /*在表haed的第i个位置上插入一人以x为值的新结点* {p= find lklist(head,i-1),/*先找第i-1个结点* ifp== NULLreeor((“不存在第i个位置”)*若第i-1个结点不存在,退出* =x/否则生成新结点* s>next=p->next/*结点*p在链域值传给结点*s的链域* t=s;/*修改*p的链域* 在无头结点的单链表上实现的算法为: void Insert( Iklist head, dataytpe X, int 1) /*在表haed的第i个位置上插入一人以x为值的新结点* if(ix=0)eror(idata=X,/*否则生成新结点 if(i==1)(s->next=head; head=s; i else! p=wfind Iklist(lklist head, i-1) if(p==NULL) error("i>n+1) (4)删除 DELDTE(Li) 在带头结点的单链表上实现的算法为: void delete lklist(( krist head. int i)/删除表head的第i个结点* {p= find lklist(head,i-1)/*先找待删结点的直接前驱* if(p!=NULL)&&(p->next!=NUL)/*若直接前趋存在且待结点存在* (qFp->next/*q指向待删结点* p>next=q>next摘除待结点* fre(q)/*释放已摘除结点q* else erro(“不存在第i个结点”)/否则给出相关信息* 在无头结点的单链表上实现的算法为: oid delete(lklist head, int 1) /*删除表head的第i个结点,若该链表仅有一个结点时,赋该结点指针NUL* fif(inext; free(@) else{p= wind Iklist(head,i-l)/*找链表head中第i-1结点指针*/
5 { j=1; p=head; while((jnext; j++} if(i= = j) return(p); else return(NULL); } (3)、插入 INSERT(L,X,i) 在带头结点单链表上实现的算法为: void insert_lklist(lklist head,datatype x,int I) /*在表 haed 的第 i 个位置上插入一人以 x 为值的新结点*/ {p=find_lklist(head,i-1); /*先找第 i-1 个结点*/ if(p= =NULL)reeor(“不存在第 i 个位置”)/*若第 i-1 个结点不存在,退出*/ else{s=malloc(size);s->data=x /*否则生成新结点*/ s->next=p->next /*结点*p 在链域值传给结点*s 的链域*/ p->next=s; /*修改*p 的链域*/ } } 在无头结点的单链表上实现的算法为: void Winsert(lklist head,dataytpe X,int i) /*在表 haed 的第 i 个位置上插入一人以 x 为值的新结点*/ {if(idata=X; /*否则生成新结点*/ if(i= =1){s->next=head;head=s;} else{ p=wfind_lklist(lklist head,i-1); if(p= =NULL) error(“i>n+1”); else{s->next=p->next;p->next=s;} } } (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(inext;free(q);} else{p=wfind_lklist(head,i-1);/*找链表 head 中第 i-1 结点指针*/
if(p!=NULL)&&(p->next =NULL) Lq=p->next; p->next=q->next; free(q); y else error(“不存在第I个结点”) e} 3、分析:从第一个结点开始访问,只要是非空计数一次。 Int length Iklist(lklist head) 求表head的长度* ip=head; j =0 hile(p!=NULL)(p=p->next j ++ i return;,/回传表长 4、设ABC均为无头结点单链表 分析:(1)当有序表A,B均非空时,找出两表中元素最小的一个元素,然后将此结点插入 到C表中,重复上述步骤 (2)当A,B两表有一个为空表时,将另一表中元素顺序地插入到C表中 (3)由于C按递减排序,因此在C表中插入元素时,应始终插入到C表表头 Lklist Wlink Iklist(Iklist A, lklist B) i while((A!=NULL)&&(B!=NULL)) if(A->datadata)Ip=A; A=A->next p->next=C; C=p if(A==NULL)A=B while(A!=NULL) p->next=C; C=p 5、分析:(1)当有序表A、B均非空时,依次分别从A、B表头部取下结点,插入C表中。 2)当A、B两表有一个为空表时,将非空表插入到C表尾部 设A,B,C均为带头结点的单链表 Iklist HB lklist(lklist A, Iklist B) A=A-> next: B=B->next,∥/去除头结点 While((a!=NULL)&&(B!=NULL)) (p- 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;
6 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 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) plenum while((i>=0)&&Xnext;}/查X插入位置q* s-malloc(size); S->data=s 8、(1)顺序表 分析:将顺序表的第一个元素与最后一个元素互换,第二个元素与倒数第二个元素互换。 Void nz sqlist( sqlist A) {for{i=0;inext=p p-q /*再插入另一个单链表p的头部* p,/*s指向新单链表的第一个结点 9、分析:A与B的交是指A与B的相同部分元素,即那些在A中出现又在B中出现的元 素。由于A、B是有序表,故从表头开始依次比较当前指针所指元素的值是否相同,若 相同,在C表中插入该元素,然后将两个表的指针后移,否则指向较小元素的指针后移 重复上述步骤,直到A,B表中有一个表到表尾 (1)顺序表 list HDz sqlist(sqlist A, sqlist B)
7 6、 分析:从有序表的尾部开始依次取元素与插入元素比较,若大于插入元素,此元素后移 一位,再取它前面一个元素重复上述步骤;则将待插入元素插入。 Void CR(datatype A[],datatype X,int elenum) { i=elenum-1; while((i>=0)&&Xnext; while((p!=NULL)&&(p->datanext;}/*查 X 插入位置 q*/ s=malloc(size);s->data=s; } 8、 (1)顺序表 分析:将顺序表的第一个元素与最后一个元素互换,第二个元素与倒数第二个元素互换。 Void NZ_sqlist(sqlist A) {for{i=0;inext; /*将原单链表的元素依次取出到 q*/ q->next=p;p=q; /*再插入另一个单链表 p 的头部*/ } 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((tB data[: j++; break; A data[i]==B data[]: C data[ k]=A data[0]; k++; i++j++; brea C last=k. Return(c (2)单链表(设带头结点) Iklist HDZ Iklist(lklist A, Iklist B) i C=initiate Ilklisto While((pl=null)&&(ql=null)) Switch i case p->datadata: p=p->next break s-malloc(size), S->data=p->da >next-r->next: r->next-s IS, 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((j= A. last)return f(A.data[I]==B.data[j])/*在A中存在B、C表共有元素,删除*/ Ifor (t=I+l; t< A last; t++)A data[t-1=A data[t]A.last--F j++;k++
8 while((tB.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)单链表(设带头结点) 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 ((j= A.last) return; if (A.data[I]==B.data[j])/*在 A 中存在 B、C 表共有元素,删除*/ {for(t=I+1;t< A.last;t++) A.data[t-1]= A.data[t] A.last--;} j++;k++; } } }
(2)单链表(设含头结点) void ASBC lklist(lklist A, Iklist B, Iklist C swIt case pb->datadata: pc=pc->next; break case pb->data==pc>data/*B、C中找到相同元素* if(pa==nullreturn f(pa->data==pb->data)/*在A中存在B、C表共有元素,删除*/ (q->next= pb=pb->next pc=pc->next; 1].分析设置两个指针,分别指向*S及其后继,然后按循环链表特性,顺序往下查找*s的 直接前趋,找到后删除; oid DELETE Xlklist(Iklist S) while(q->nest!=s) i p-q: q=q->next; p->next=s; free(q) 12.分析:在链表L中依次取元素,若取出的元素是字母,把它插入到字母B中,然后在L 中删除该元素:若取出的元素是数字,把它插入到数字链D中,然后在L中删除该元素 继续取下一个元素,直到链表的尾部。最后B、D、L中分别存放的是字母字符、数字字符 和其它字符 设原表有头结点、头指针L,新建数字字符链D,字母字符链B,其它字符链R。 oid dISM lklist(lklist L, Iklist D, lklist B, lklist R) D=malc( size of(int),D->next=D,/*建D循环链表头结点* B= malloc(( sizeof(char);B->next=B,/*建B循环链表头结点* p=L, =p->next; while(ql=null fif(q-data=0)) {p>next=q->next,/在表L中摘除q结点* q->next=D-next;D->next=q/*将q结点插入D中 ext,/移动q指针* else if (q->datadata>=a')ll q->datadata>=a')) {p>next=q->next/*在表L中删除q结点* q->next=B->nex;B->next=q;/*将q结点插入B中* nex /*移动q指针*
9 (2) 单链表(设含头结点) void ASBC_lklist(lklist A,lklist B,lklist C) {pa= A ->next;q= A; 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->datadata>=’0’)) {p->next=q->next; /*在表 L 中摘除 q 结点*/ q->next= D ->next; D ->next=q; /*将 q 结点插入 D 中*/ q=p->next; /*移动 q 指针*/ } else if (q->datadata>=’a’)||(q->datadata>=’a’)) {p->next=q->next; /*在表 L 中删除 q 结点*/ q->next= B ->next; B ->next=q; /*将 q 结点插入 B 中*/ q=p->next; /*移动 q 指针*/
else(p=q; q=p->next; i *移动q指针* p->next=L R=L /*使R为循环表* 13.分析:使用一维数组,数组下标表示元素的序号,数组值为1表示元素存在,数 值为0表示此元素不存在。若累加数组的下标大于N,再从1开始继续累加数组值,直到 所有元素都输出 Void JSP( int n, k, a(n) {for(l=0;data!=x)) {p=p-> next++;}*未达尾结点又未找到值等于x的结点时继续扫描* f(p->data==x)return () return(0) (3)插入(设含头结点) void insert dlklist(dlklist head, datatype x, int I) /*在表head的第I个位置上插入一个以x为值的新结点* p=head->next;j=1;/*先找第I-1个结点* whle((p!=nu)&&(data=x;/否则生成新结点* S->prop
10 }else {p=q;q=p->next;} /*移动 q 指针*/ } p->next=L;R=L; /*使 R 为循环表*/ } 13.分析:使用一维数组,数组下标表示元素的序号,数组值为 1 表示元素存在,数组 值为 0 表示此元素不存在。若累加数组的下标大于 N,再从 1 开始继续累加数组值,直到 所有元素都输出。 Void JSP( int n, k, a[n]) {for(I=0;Inext =null; t->prior=null; return(t); } (2)定位(设含头结点) int locate_dlklist (dlklist head, datatype x) /*求表 head 中第一个值等于 x 的结点的序号。不存在这种结点时结果为 0 */ {p=head->next;j=1; /*置初值*/ while((p!=null)&&(p->data!=x)) {p=p->next;j++;} /*未达尾结点又未找到值等于 x 的结点时继续扫描*/ if (p->data = = x) return (j); else return (0); } (3) 插入(设含头结点) void insert_dlklist (dlklist head, datatype x, int I) /*在表 head 的第 I 个位置上插入一个以 x 为值的新结点*/ {p=head->next; j=1; /*先找第 I-1 个结点*/ while ((p!=null) &&(jdata=x;/*否则生成新结点*/ s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;