DS第二章-课后习题答案

DS第二章_课后习题答案DS第二章_课后习题答案/NUMPAGES20DS第二章_课后习题答案DS第二章_课后习题答案第二章线性表2.1填空题(1)一半插入或删除的位置(2)静态动态(3)一定不一定(4)头指针头结点的next前一个元素的next2.2选择题(1)A(2)DAGKHDAELIAFIFA(IDA)(3)D(4)D(5)D2.3头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址；头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放；首元素结点：第一个元素的结点。2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。voidInserList(SeqList*L,ElemTypex){inti=L->last;if(L->last>=MAXSIZE-1)returnFALSE;//顺序表已满while(i>=0&&L->elem[i]>x){L->elem[i+1]=L->elem[i];i--;}L->elem[i+1]=x;L->last++;}2.5删除顺序表中从i开始的k个元素intDelList(SeqList*L,inti,intk){intj,l;if(i<=0||i>L->last){printf("TheInitialPositionisError!");return0;}if(k<=0)return1;/*NoNeedtoDelete*/if(i+k-2>=L->last)L->last=L->last-k;/*modifythelength*/for(j=i-1,l=i+k-1;l<L->last;j++,l++)L->elem[j]=L->elem[l];L->last=L->last-k;return1;}2.6已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，删除线性表中所有值为item的数据元素。[算法1]voidDeleteItem(SeqList*L,ElemTypeitem){inti=0,j=L->last;while(i<j){while(i<j&&L->elem[i]!=item)i++;while(i<j&&L->elem[i]==item)j--;if(i<j){L->elem[i]=L->elem[j];i++;j--;}}L->last=i-1;}[算法2]voidDeleteItem(SeqList*L,ElemTypee){ inti,j; i=j=0; while(L->elem[i]!=e&&i<=L->last) i++; j=i+1; while(j<=L->last) { while(L->elem[j]==e&&j<=L->last) j++; if(j<=L->last) { L->elem[i]=L->elem[j]; i++;j++; } } L->last=i-1; }2.7编写算法，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。

voidDeleteRepeatItem(SeqList*L){inti=0,j=1;while(j<=L->last){if(L->elem[i]==L->elem[j])j++;else{L->elem[i+1]==L->elem[j];i++;j++;}}L->last=i;}2.8已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度。voidDelData(LinkListL,ElemTypemink,ElemTypemaxk){ Node*p=L->next,*pre=L; while(!p&&p->data<=mink)//寻找开始删除的位置 {pre=p;p=p->next;} while(p) { if(p->data>maxk) break;else { pre->next=p->next; free(p); p=pre->next; } }}T(n)=O(n);2.9试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2...,an）逆置为（an,an-1,...,a1）。以一维数组作存储结构。以单链表作存储结构。(略)(1)voidReverseArray(ElemTypea[],intn){ inti=0,j=n-1; ElemTypet; while(i<j) {t=a[i];a[i]=a[j];a[j]=t;} }(2)voidReverseList(LinkListL){ p=L->next; L->next=NULL; while(p!=NULL) { q=p->next; p->next=L->next; L->next=p; p=q; }}2.10已知一个带有表头结点的单链表,假设链表只给出了头指针L。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，至返回0。（提示：设置两个指针，步长为k）intSearchNode(LinkListL,intk){ Node*p=L,*q; inti=0; while(i<k&&p) {i++;p=p->next;} if(p==NULL)return0;//不存在倒数第k个元素 q=L->next; while(p->next!=NULL)//p到终点时，q所指结点为倒数第k个 {q=q->next;p=p->next;} printf("%d",q->data); return1;}2.11把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。（头插法）LinkListReverseMerge(LinkList*A,LinkList*B){LinkListC;Node*pa=A->next,*pb=B->next;//pa和pb分别指向A,B的当前元素A->next=NULL;C=A;while(pa!=NULL&&pb!=NULL){if(pa->data<pb->data)/*将pa的元素前插到pc表*/{temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}else{temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将pb的元素前插到pc表*/}while(pb!=NULL){temp=pa->next;pa->next=C->next;C->next=pa;pa=temp;}/*将剩余pa的元素前插到pc表*/while(pb!=NULL){temp=pb->next;pb->next=C->next;C->next=pb;pb=temp;}/*将剩余pb的元素前插到pc表*/returnhc;}2.12一单链表，以第一个元素为基准，将小于该元素的结点全部放到前面，大于该结点的元素全部放到后面。时间复杂度要求为O(n)，不能申请新空间。voidAdjustList(LinkListL){Node*pFlag=L->next,*q=L->next->next,*temp=NULL;pflag->next=NULL;while(q!=NULL){if(q->data<pFlag->data)//插到链表首端{temp=q->next;q->next=L->next;L->next=q;q=temp;}Else//插到pFlag结点后面{temp=q->next;q->next=pFlag->next;pFlag->next=q;q=temp;}}}2.13假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。voidDelPreNode(Node*s){Node*p=s;while(p->next->next!=s)p=p->next;free(p->next);p->next=s;}2.14已知由单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其他字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。//L为待拆分链表//Lch为拆分后的字母链；Lnum为拆分后的数字链，Loth为拆分后的其他字符链//Lch,Lnum,Loth均已被初始化为带头结点的单循环链表，采用头插法voidsplitLinkList(LinkListL,LinkListLch,LinkListLnum,LinkListLoth){ Node*p=L->next; while(p!=NULL) { if((p->data>='a'&&p->data<='z')||(p->data>='A'&&p->data<='Z')) {temp=p->next;p->next=Lch->next;Lch->next=p;p=temp;} elseif(p->data>='0'&&p->data<='9') {temp=p->next;p->next=Lnum->next;Lnum->next=p;p=temp;} else {temp=p->next;p->next=Loth->next;Loth->next=p;p=temp;} }}2.15设线性表A=(a1,a2,…,am)，B=(b1,b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：C=(a1,b1,…,am,bm,bm+1,…,bn)当m≤n时；或者C=(a1,b1,…,an,bn,an+1,…,am)当m>n时。线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。//将A和B合并为C,C已经被初始化为空单链表voidMergeLinkList(LinkListA,LinkListB,LinkListC){ Node*pa=A->next，*pb=B->next,*pc=C; inttag=1; while(pa&&pb) { if(tag) {pc->next=pa->next;pc=pc->next;pa=pa->next;tag=1;} else {pc->next=pb->next;pc=pc->next;pb=pb->next;tag=0;} } if(pa)pc->next=pa->next; elsepc->next=pb->next;s}2.16将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。//A为循环单链表，表示某多项式；将A拆分为B和C//其中B只含奇次项，C只含偶次项；奇偶按照幂次区分//B,C均已被初始化为带头结点的单链表voidSplitPolyList(PolyListA,PolyListB,PolyListC){ PolyNode*pa=A->next,*rb=B,*rc=C; while(pa) { if(pa->exp%2==0)//偶次项 {rc->next=pa->next;rc=rc->next;pa=pa->next;} else //奇次项 {rb->next=pa->next;rb=rb->next;pa=pa->next;} } rb->next=NULL;rc->next=NULL;}2.17建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。voidBinAdd(LinkListl)/*用带头结点的单链表L存储二进制数，实现加1运算*/{ Node*q,*r,*s; q=l->next; r=l;