《数据结构第二章课后答案》由会员分享，可在线阅读，更多相关《数据结构第二章课后答案（5页珍藏版）》请在金锄头文库上搜索。
1、2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。解：intInsList(SeqList*L,intX)inti=0,k;if(L-last=MAXSIZE-1)printf(表已满无法插入！)；return(ERROR);while(ilast&L-elemilast;k=I;k-)L-elemk+1=L-elemk;L-elemi=X;L-last+;return(OK);2.5写一算法，从顺序表中删除自第i个元素开始的k个元素。解：intLDel(Seqlist*L,inti,intk)if(i=1|(i+kL-last+1)printf(输入
2、的i,k值不合法”)；return(ERROR);elseif(i+k=L-last+2)L-last=i-2;returnOK;elsej=i+k-1;while(jlast)elemj-k=elemj;j+;L-last=L-last-k+1;returnOK;2.6已知线性表中的元素(整数)以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素)，分析你的算法的时间复杂度(注意：mink和maxk是给定的两个变量，他们的值为任意的整数)。解：intDelete(Linklist,intmink,intmaxk)Node*p
3、,*q;p=L;while(p-next!=NULL)p=p-next;if(mink=maxk|L-next-data=maxk|mink+1=maxk)printf(参数不合法！);returnERROR;elsewhile(p-next-datanext;q=p-next;while(q-datanext=q-next;free(q);q=p-next;returnOK;2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的储存空间将线性表(al,al,，an)逆置为(an,an-1,，al)。(1)以顺序表作存储结构。解：intReversePosition(SpListL)
4、intk，temp，len;intj=0;k=L-last;len=L-last+1;for(j;jelemk-j;elemk-j=elemj;elemj=temp;returnOK;2)以单链表作存储结构。解：intReversePosition(LinklistL)Node*NL,q,r;q=L;r=L;NL=L-next;if(NL=NULL)returnERROR;while(q-next!=NULL)q=q-next;r-next=q;r=q;while(NL-next!=r&NL-next!=NULL)q=NL;while(q-next!=r)q=q-next;r-next=q;r
5、=q;r-next=NL;NL-next=NULL:returnOK;2.8假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减的有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C解：voidmerge(SepList*LA,SepList*LB,SepList*LC)Node*p1,*p2,*q1,*q2;LA-next=p1;LB-next=q1;while(p1!=NULL&q1!=NULL)if(p1-dataq1-data)q2=q1-next;q1-next=LC-next;LC-next=q;q1=q
6、2;elsep2=p1-next;p1-next=LC-next;LC-next=p1;p1=p2;2.9假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。解：ElemTypeDeletePreElem(Node*s)ElemTypetemp;Node*p,*pre;p=s;while(p-next!=s)p=p-next;pre=p;while(p-next!=pre)p=p-next;p-next=s;temp=pre-data;free(pre);returntemp;2.10已知有单链表表示的线性
7、表中含有三类字符的数据元素(如字母字符、数字字符和其他字符)，试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解:LinkList_Divide(LinkList&L,CiList&A,CiList&B,CiList&C)/把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.s=L-next;A=(CiList*)malloc(sizeof(CiLNode);p=A;B=(CiList*)malloc(sizeof(CiLNode);q=B;C=(CiList*)malloc(si
8、zeof(CiLNode);r=C;/建立头结点while(s!=NULL)if(s-data=a&s-datadata=A&s-datanext=s;p=s;elseif(s-data=0&s-datanext=s;q=s;elser-next=s;r=s;p-next=A;q-next=B;r-next=C;2.11设线性表A=(al,a2,am),B=(bl,b2,，bn),试写一个按下列规则合并A、B为线性表C的算法，使得C=(al,bl,，an,bn,an+1,，am)当mn时或者C=(al,bl,，am,bm,bm+1，bn)当mnext;pb=B-next;while(pa!=N
9、ULL&pb!=NULL)r-next=pa;r=pa;pa=pa-next;r-next=pb;r=pb;pb=pb-next;if(pa=NULL)r-next=pb;elser-next=pa;return(C);使这两个多项式中各自仅含奇2.12将一个用循环链表表示的稀疏多项式分解成两个多项式，次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。解：typedefstructPolynodeintcoef;intexp;structpolynode*next;Polynode*PolyList;voidGreateCircleLinklistC(LinklistRL,Node*
10、e)Node*p;p=RL-next;RL-next=e;RL=RL-next;RL-next=p;voidDescouposeList(LinklistRLDescouposeRADescouposeRB)Node*p;p=RL-next;if(p-next=NULL)return;p=p-next;while(p!=RL-next)if(p-exp%2=0)Greate(RB,p);elseGreate(RA,p);p=p-next;data域存2.13建立一个带头节点的线性表，用以存放输入的二进制数，链表中每个结点的放一个二进制位，并在此链上实现对二进制数加1的运算。解：voidBinnaryFod(DlinklistDL)DNode*p,*s;p=DL;while(p-prior!=DL)p=p-prior;if(p-data=0)p-data=1;break;if(p-data=1)p-data=0;if(p-prior=DL)s=(DNode*)malloc(sizeof(DNode);s-data=1;s-next=p;p-prior=s;s-prior=DL;DL-next=s;
