第二次作业答案.docx

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、Ldataj=Ldataj-111、n O(n) n/2 O(n)12、L.dataj-2=l.dataj-113、n-1 o(n) (n-1)/2 O(n)14、i=1

2、 iL.last15、O(n) O(1)16、L.last L.datai-117、单链表 循环链表 双链表18、指针 19，单链表20、头结点 表结点21、首结点 尾结点 任何信息、特殊标志 表长22、头结点 头结点23、t=malloc(size) t-next=NULL24、p=haed p=p-next25、(p-next!=NULL)&(jnext!=NULL)&(p-data!=x)27、(p!=NULL)&(p-next!=NULL) p-next28、mailloc(size) p-next29、insert_lklist(head,x,I) I+ n(n-1)/2 O(n2)

3、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，则在语言上可用下述类型定

4、义来描述顺序表： const maxsize=顺序表的容量； typedef struct datatype datamaxsizeint last;sqlist;sqlist L;数据域data是一个一维数组，线性表的第1，2，n个元素分别存放在此数组的第0，1，last-1个分量中，数据域last表示线性表当前的长度，而last-1是线性表的终端结点在顺序表中的位置。常数maxsize称为顺序表的容量，从last到maxsize-1为顺序表当前的空闲区（或称备用区）。Sqlist类型完整地描述了顺序表的组织。L被说明为sqlist类型的变量，即为一顺序表，其表长应写为L.last，而它的终

5、端结点则必须写为 L.dataL.last-1。2、假设数据元素的类型为datatype。单链表的类型定义如下：typedef struct node *pointerstruct node datatype data; pointer next; ;typedef pointer lklist;其中，ponter是指向struct node类型变量的指针类型;struct node是结构体类型规定一个结点是由两个域data和next组成的记录，其中data的结点的数据域,next是结点的链域；lklist与pointer相同类型，用来说明头指针变量的类型，因而lklist也就被用来作为单链表

6、的类型。3、typedef struct dnode *dpointer; struct dnodedatatype data;dpointer prior,next;typedaf dpinter dlklist;链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋和后继指针链接在一起，再加上起标识作用的头指针，就得到双向循环链表。4、顺序串的类型定义与顺序表类似，可描述如下：const maxlen=串的最大长度 typedef struct char chmaxlen int curlen;string5、链串的类型定义为： c

7、onst nodesize=用户定义的结点大小; typedef struct node *pointer; struct node char chnodesize poinernext; typedef pointer strlist;当结点大小为1时，可将ch域简单地定义为：char ch6、head称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指针变量是用于存放头指针的变量。为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。头指针变量的作用：对单链表中任一结点

8、的访问，必须首先根据头指针变量中存放的头指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起来。7、循环单链表、循环双链表。8、空串和空格串：含0个字符的串称为空串，其长度为0。空格串是含有一个或多处空格字符组成的串，其长度不为0。 串变量和串常量：串常量在程序的执行过程中只能引用不能改变而串变量的值在程序执行过程中是可以改变和重新赋值的。 主串和子串：一个

9、串中任意个连续字符组成的子序列称为该串的子串，该串称为它的所以子串的主串。 串变量的名字与串变量的值：串变量的名字表示串的标识符；串变量的值表示串变量的字符序列。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

10、(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=顺序表的容量;typedef struct int datamaxsize int last; sqlist;int CMP_sqlist(sqlis

11、t A ,sqlist B) for (i=0;(iA.last)&(IB.last);i+ if(A.dataiB.datai)return(1);if(A.last= =B.last) return(0);else if(A.lastB.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!=NU

12、LL)&(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

13、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); j=1; p=head;while(jnext; j+if(i= = j) return(p); else return(NULL);(3)、插入INSERT(L，X

14、，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个结点不存在，退出*/elses=malloc(size);s-data=x /*否则生成新结点*/s-next=p-next /*结点*p在链域值传给结点*s的链域*/p-next=s; /*修改*p的链域*/在无头结点的单链表上实现的算法为：void

15、Winsert(lklist head,dataytpe X,int i)/*在表haed的第i个位置上插入一人以x为值的新结点*/if(i=0) error(“idata=X; /*否则生成新结点*/ if(i= =1)s-next=head;head=s; else p=wfind_lklist(lklist head,i-1);if(p= =NULL) error(“in+1”); elses-next=p-next;p-next=s;(4)删除DELDTE(L,i)在带头结点的单链表上实现的算法为：void delete_lklist(lklist head,int i) /*删除表h

16、ead的第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);els

17、ep=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均非空时，找出两表中元

18、素最小的一个元素，然后将此结点插入到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均非空时，依次分别

19、从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、 分析：从有序表的尾部

20、开始依次取元素与插入元素比较，若大于插入元素，此元素后移一位，再取它前面一个元素重复上述步骤；则将待插入元素插入。 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)fori=0;inext; /*将原单链表的元素依次取出到q*/ q-ne

21、xt=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(t=A.last-1)&(j=B.last-1)switch case A.dataiB.data

22、j;j+;break; case A.datai= =B.dataj;C.datak=A.datai;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

23、=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 (jB.last)&(kC.last)switchcase B.datajC.datak:j+;break;case B.datajC.datak:k+;break;case

24、B.dataj=C.datak:/*B、C中找到相同元素*/while(IA.last)&( A.dataI= A.last) return; if (A.dataI=B.dataj)/*在A中存在B、C表共有元素，删除*/ for(t=I+1;tnext;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中找到相同

25、元素*/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中依次取元素，若取出的元素是字母，把它

26、插入到字母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;