《线性表习题答案.ppt》由会员分享,可在线阅读,更多相关《线性表习题答案.ppt(30页珍藏版)》请在三一办公上搜索。
1、线性表习题,作业中普遍存在的问题:,自己定义的数据类型不写出其定义,而直接使用它定义变量;混淆顺序表和链表的操作;对函数的类型、形参类型以及形参个数不斟酌,随意乱定。,1.指出以下算法中的错误和低效(即费时)之处,并将它改为一个既正确又高效的算法。,int DeleteK(SqList*a,int i,int k)/本过程从顺序存储结构的线性表a中删除第i个元素 起的k个元素int count,j;if(ia-length)return INFEASIBLE;/参数不合法elsefor(count=1;countlength;j=i+1;j-)a-elemj-1=a-elemj;a-lengt
2、h-;return OK;/DeleteK,参考答案:本题给出的算法的低效之处在第二个循环,该算法的时间复杂度O(n)=k*(a-length-i)本题给出的算法的错误之处有:countlength;j=i+1;j-)a-elemj-1=a-elemj;导致元素的搬移顺序逆反了。,修改后的算法如下:int ModifyDeleteK(SqList*a,int i,int k)/本过程从顺序存储结构的线性表a中删除第i个 元素起的k个元素int j;if(ia-length)return INFEASIBLE;/参数不合法elsefor(j=i+k;jlength;j+)/删除k个元素a-ele
3、mj-k=a-elemj;a-length-=k;return OK;/ModifyDeleteK,新算法的时间复杂度O(n)=a-length-(i+k)+1,2.试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L,X)。,参考答案:typedef struct LNodeElemType data;struct LNode*next;LNode,*LinkList;/线性链表类型,LinkList LOCATE(LinkList L,ElemType X)/*初始条件:线性表L已存在操作结果:返回L中X第一次出现的位置的指针。若X不存在,则返回值为NULL。*/LinkLis
4、t p;int i=0;p=L-next;while(p)+i;/记录遍历的每个节点的位序if(p-data=X)/在链表L中找到Xreturn p;p=p-next;if(!p)return NULL;/链表L中不存在X,3.已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后),假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。,参考答案:typedef struct LNode ElemType data;struc
5、t LNode*next;LNode,*LinkList;/线性链表类型,void MergeList_L(LinkList ha,int m,LinkList hb,int n,LinkList*hc)/*初始条件:单链表ha和hb存在,其长度分别为m和n操作结果:归并ha和hb得到新的单链表hc*/LinkList p;if(m=0)/ha链表为空链表*hc=hb;free(ha);if(n=0)/hb链表为空链表*hc=ha;free(hb);,if(mn)/将ha链表链接在hb链表之后p=hb-next;while(p-next)/寻找hb链表的尾结点p=p-next;p-next=h
6、a-next;*hc=hb;free(ha);else/将hb链表链接在ha链表之后p=ha-next;while(p-next)/寻找hb链表的尾结点p=p-next;p-next=hb-next;*hc=ha;free(hb);,算法的时间复杂度为O(mn?m:n),4.已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第j个元素之前。试问此算法是否正确?若有错,则请改正之。,Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,
7、int len)if(inext;k+;q=p;while(knext;k+;s=lb;k=1;while(knext;k+;s-next=p;q-next=s-next;return OK;/DeleteAndInsertSub,参考答案:#define INFEASIBLE 0#define OK 1#define ERROR 0typedef struct NodeElemType data;struct Node*next;LNode,*LinkedList;,Status DeleteAndInsertSub(LinkedList,if(!q)return INFEASIBLE;if
8、(!prev)la=q-next;else prep-next=q-next;if(j=1)q-next=lb;lb=p;elses=lb;k=1;while(s,5.试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,an)逆置为(an,an-1,a1)。,参考答案:#define MAX 100typedef int ElemType;typedef structElemType elemMAX;/存储空间基址int length;/当前长度SqList;/顺序表类型,void Reverse_SqList(SqList*L)/*初始条件:顺序表L存在且不为空*/*
9、操作结果:顺序表L的内容被逆置*/int i;ElemType x;/顺序表L的第i个元素和倒数第i个元素交换for(i=1;ilength/2;i+)x=L-elemi-1;L-elemi-1=L-elemL-length-i;L-elemL-length-i=x;,6.试写一算法,对单链表实现就地逆置。,参考答案:typedef struct LNodeElemType data;struct LNode*next;LNode,*LinkList;/线性链表类型,void Reverse_L(LinkList L)/*初始条件:单链表L存在操作结果:单链表L被就地逆置*/LinkList
10、p,q;p=L-next;,if(!p)/空表返回return;L-next=NULL;/将L置为空表while(p)q=p-next;p-next=L-next;L-next=p;p=q;,7.假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即A表和B表)的结点空间构造C表。,参考答案:,typedef struct LNodeElemType data;struct LNode*next;LNode,*LinkList;/线性链表类型void Mer
11、geList(LinkList A,LinkList B,LinkList*C)/*初始条件:单链表A、B的元素递增有序排列操作结果:单链表A、B归并成非递增有序的线性表C*/*利用头插法建立单链表C*/LinkList pa=A-next,pb=B-next,q;,if(pa-datadata)/A的首元节点链入C*C=A;(*C)-next=NULL;q=pa-next;pa-next=(*C)-next;(*C)-next=pa;pa=q;free(B);else/B的首元节点链入CC=B;(*C)-next=NULL;q=pb-next;pb-next=(*C)-next;(*C)-n
12、ext=pb;pb=q;free(A);,while(pa,while(pa)/A的剩余节点依次链入Cq=pa-next;pa-next=(*C)-next;(*C)-next=pa;pa=q;while(pb)/A的剩余节点依次链入Cq=pb-next;pb-next=(*C)-next;(*C)-next=pb;pb=q;,8.假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。,参考答案:typedef struct NodeElemType data;struct Node*next;LNode
13、,*LinkList;,int Delete(LinkList s)LinkList p,q;p=s;/查找s所指节点前驱的前驱节点while(p-next-next!=s)p=p-next;q=p-next;p-next=s;free(q);,9.已知有一个单项循环链表,其每个结点中含三个域:prior,data和next,其中data为数据域,next为指向后继结点的指针域,prior也为指针域,但它的值为空(NULL),试编写算法将此单向循环链表改为双向循环链表,即使prior成为指向前驱结点的指针域。,参考答案:typedef int ElemType;typedef struct NodeElemType data;struct Node*prior;struct Node*next;LNode,*LinkList;,void DoubleLinkList(LinkList L)LinkList p,pre;p=L;while(p-next!=L)pre=p;p=p-next;p-prior=pre;L-prior=p;,