《线性表习题答案.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;,
