数据结构线性表答案

第一章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。2.2填空题。解：(1)在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。(2)顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。(3)在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。(4)在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。2.3在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。2.4对以下单链表分别执行下列各程序段，并画出结果示意图。解：2.5画出执行下列各行语句后各指针及链表的示意图。L=(LinkList)malloc(sizeof(LNode));P=L;for(i=1;i=4;i++){P-next=(LinkList)malloc(sizeof(LNode));P=P-next;P-data=i*2-1;}P-next=NULL;for(i=4;i=1;i--)Ins_LinkList(L,i+1,i*2);for(i=1;i=3;i++)Del_LinkList(L,i);解：2.6已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是__________________。b.在P结点前插入S结点的语句序列是__________________。c.在表首插入S结点的语句序列是__________________。d.在表尾插入S结点的语句序列是__________________。(1)P-next=S;(2)P-next=P-next-next;(3)P-next=S-next;(4)S-next=P-next;(5)S-next=L;(6)S-next=NULL;(7)Q=P;(8)while(P-next!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;解：a.(4)(1)b.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)2.7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是____________________。b.删除P结点的直接前驱结点的语句序列是____________________。c.删除P结点的语句序列是____________________。d.删除首元结点的语句序列是____________________。e.删除尾元结点的语句序列是____________________。(1)P=P-next;(2)P-next=P;(3)P-next=P-next-next;(4)P=P-next-next;(5)while(P!=NULL)P=P-next;(6)while(Q-next!=NULL){P=Q;Q=Q-next;}(7)while(P-next!=Q)P=P-next;(8)while(P-next-next!=Q)P=P-next;(9)while(P-next-next!=NULL)P=P-next;(10)Q=P;(11)Q=P-next;(12)P=L;(13)L=L-next;(14)free(Q);解：a.(11)(3)(14)b.(10)(12)(8)(3)(14)c.(10)(12)(7)(3)(14)d.(12)(11)(3)(14)e.(9)(11)(3)(14)2.8已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是_______________________。b.在P结点前插入S结点的语句序列是_______________________。c.删除P结点的直接后继结点的语句序列是_______________________。d.删除P结点的直接前驱结点的语句序列是_______________________。e.删除P结点的语句序列是_______________________。(1)P-next=P-next-next;(2)P-priou=P-priou-priou;(3)P-next=S;(4)P-priou=S;(5)S-next=P;(6)S-priou=P;(7)S-next=P-next;(8)S-priou=P-priou;(9)P-priou-next=P-next;(10)P-priou-next=P;(11)P-next-priou=P;(12)P-next-priou=S;(13)P-priou-next=S;(14)P-next-priou=P-priou;(15)Q=P-next;(16)Q=P-priou;(17)free(P);(18)free(Q);解：a.(7)(3)(6)(12)b.(8)(4)(5)(13)c.(15)(1)(11)(18)d.(16)(2)(10)(18)e.(14)(9)(17)2.9简述以下算法的功能。(1)StatusA(LinkedListL){//L是无表头结点的单链表if(L&&L-next){Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnOK;}(2)voidBB(LNode*s,LNode*q){p=s;while(p-next!=q)p=p-next;p-next=s;}voidAA(LNode*pa,LNode*pb){//pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(pb,pa);}解：(1)如果L的长度不小于2，将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.10指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。StatusDeleteK(SqList&a,inti,intk){//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if(i1||k0||i+ka.length)returnINFEASIBLE;//参数不合法else{for(count=1;countk;count++){//删除第一个元素for(j=a.length;j=i+1;j--)a.elem[j-i]=a.elem[j];a.length--;}returnOK;}解：StatusDeleteK(SqList&a,inti,intk){//从顺序存储结构的线性表a中删除第i个元素起的k个元素//注意i的编号从0开始intj;if(i0||ia.length-1||k0||ka.length-i)returnINFEASIBLE;for(j=0;j=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;returnOK;}2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。解：StatusInsertOrderList(SqList&va,ElemTypex){//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法inti;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i0,xva.elem[i-1];i--)va.elem[i]=va.elem[i-1];va.elem[i]=x;va.length++;returnOK;}2.12设maaA,,1和nbbB,,1均为顺序表，A和B分别为A和B中除去最大共同前缀后的子表。若BA空表，则BA；若A=空表，而B空表，或者两者均不为空表，且A的首元小于B的首元，则BA；否则BA。试写一个比较A，B大小的算法。解：StatusCompareOrderList(SqList&A,SqList&B){inti,k,j;k=A.lengthB.length?A.length:B.length;for(i=0;ik;i++){if(A.elem[i]B.elem[i])j=1;if(A.elem[i]B.elem[i])j=-1;}if(A.lengthk)j=1;if(B.lengthk)j=-1;if(A.length==B.length)j=0;returnj;}2.13试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);解：intLocateElem_L(LinkList&L,ElemTypex){inti=0;LinkListp=L;while(p&&p-data!=x){p=p-next;i++;}if(!p)return0;elsereturni;}2.14试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。解：//返回单链表的长度intListLength_L(LinkList&L){inti=0;LinkListp=L;if(p)p=p-next;while(p){p=p-next;i++;}returni;}2.15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。解：voidMergeList_L(LinkList&ha,LinkList&hb,LinkList&hc){LinkListpa,pb;pa=ha;pb=hb;while(pa-next&&pb-next){pa=pa-next;pb=pb-next;}if(!pa-next){hc=hb;while(pb-next)pb=pb-next;pb-next=ha-next;}else{hc=ha;while(pa-next)pa=pa-next;pa-next=hb-next;}}2.16已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。StatusDeleteAndInsertSub(LinkedListla,LinkedListlb,inti,intj,intlen){if(i0||j0||len0)returnINFEASIBLE;p=la;k=1;while(ki){p=p-next;k++;}q=p;while(k=len){q=q-next;k++;}s=lb;k=1;while(kj){s=s-next;k++;}s-next=p;q-next=s-next;returnOK;}解：StatusDeleteAndInsertSub(LinkList&la,LinkList&lb,inti,intj,intlen){LinkListp,q,s,prev=