线性表习题答案

《线性表习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性表习题作业中普遍存在的问题：自己定义的数据类型不写出其定义，而直接使用它定义变量；混淆顺序表和链表的操作；对函数的类型、形参类型以及形参个数不斟酌，随意乱定。1.指出以下算法中的错误和低效（即费时）之处，并将它改为一个既正确又高效的算法。intDeleteK(SqList*a,inti,intk){//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素intcount,j;if(i<1

2、

3、k<0

4、

5、i+k>a->length)returnINFEASIBLE;//参数不合法else{for(count=1;count

6、){//删除一个元素for(j=a->length;j>=i+1;j--)a->elem[j-1]=a->elem[j];a->length--;}returnOK;}}//DeleteK参考答案：本题给出的算法的低效之处在第二个循环，该算法的时间复杂度O(n)=k*(a->length-i)本题给出的算法的错误之处有：countlength;j>=i+1;j--)a->elem[j-1]=a->elem[j];导致元素的搬移顺序逆反了。修改后的算法如下：intModifyDeleteK(SqList*a,

7、inti,intk){//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素intj;if(i<1

8、

9、k<0

10、

11、i+k>a->length)returnINFEASIBLE;//参数不合法else{for(j=i+k;j<=a->length;j++)//删除k个元素a->elem[j-k]=a->elem[j];a->length-=k;returnOK;}}//ModifyDeleteK新算法的时间复杂度O(n)=a->length-(i+k)+12.试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L,X)。参考答案：ty

12、pedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;//线性链表类型LinkListLOCATE(LinkListL,ElemTypeX){/*初始条件：线性表L已存在操作结果：返回L中X第一次出现的位置的指针。若X不存在，则返回值为NULL。*/LinkListp;inti=0;p=L->next;while(p){++i;//记录遍历的每个节点的位序if(p->data==X)//在链表L中找到Xreturnp;p=p->next;}if(!p)returnNULL;/

13、/链表L中不存在X}3.已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。参考答案：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;//线性链表类型voidMergeList_L(LinkListha,intm,LinkListhb,int

14、n,LinkList*hc){/*初始条件：单链表ha和hb存在,其长度分别为m和n操作结果：归并ha和hb得到新的单链表hc*/LinkListp;if(m==0)//ha链表为空链表{*hc=hb;free(ha);}if(n==0)//hb链表为空链表{*hc=ha;free(hb);}if(m>n)//将ha链表链接在hb链表之后{p=hb->next;while(p->next)//寻找hb链表的尾结点p=p->next;p->next=ha->next;*hc=hb;free(ha);}else//将hb链表链接在ha链表之后{p=ha

15、->next;while(p->next)//寻找hb链表的尾结点p=p->next;p->next=hb->next;*hc=ha;free(hb);}}算法的时间复杂度为O(m

16、

17、j<0

18、

19、l

20、en<0)returnINFEASIBLE;p=la;k=1;while(knext;k++;}q=p;