数据结构第二章课后答案

1、2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。解：int InsList(SeqList *L,int X) int i=0,k; if(L->last>=MAXSIZE-1)printf("表已满无法插入！")；return(ERROR);while(i<=L->last&&L->elemi<X) i+;for(k=L->last;k>=I;k-)L->elemk+1=L->elemk; L->elemi=X; L->last+; retu

2、rn(OK); 2.5写一算法，从顺序表中删除自第i个元素开始的k个元素。解：int LDel(Seqlist *L,int i,int k)if(i=1|(i+k>L->last+1)printf("输入的i，k值不合法")；return(ERROR);else if(i+k=L->last+2)L->last=i-2;return OK;elsej=i+k-1;while(j<=L->last)elemj-k=elemj;j+;L->last=L->last-k+1;return OK;2.6已知线性表中的元素（整数）以递

3、增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。解：int Delete(Linklist,int mink,int maxk)Node *p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink>=maxk|L->next->data>=maxk|mink+1=maxk)printf("参数不合法！");return ERROR;elsew

4、hile(p->next->data<=mink)p=p->next;q=p->next;while(q->data<maxk && q!=NULL)p->next=q->next;free(q);q=p->next;return OK;2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的储存空间将线性表（a1，a1，,an）逆置为（an，an-1，a1）。 （1）以顺序表作存储结构。解：int ReversePosition(SpList L)int k,temp,len;int j=0;k=L->

5、last;len=L->last+1;for(j;j<len/2;j+)temp=L->elemk-j;elemk-j=elemj;elemj=temp;return OK; （2）以单链表作存储结构。解：int ReversePosition(Linklist L)Node *NL,q,r;q=L;r=L;NL=L->next;if(NL=NULL)return ERROR;while(q->next!=NULL)q=q->next;r->next=q;r=q;while(NL->next!=r&&NL->next!=NU

6、LL)q=NL;while(q->next!=r)q=q->next;r->next=q; r=q;r->next=NL; NL->next=NULL: return OK;2.8假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减的有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C解：void merge(SepList *LA,SepList *LB,SepList *LC)Node *p1,*p2,*q1,*q2;LA->next=p1;LB->next=q1;whi

7、le(p1!=NULL&&q1!=NULL)if(p1->data>q1->data)q2=q1->next;q1->next=LC->next;LC->next=q;q1=q2;elsep2=p1->next;p1->next=LC->next;LC->next=p1;p1=p2;2.9假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。解：ElemType DeletePreElem (Node *s)ElemType t

8、emp;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);return temp;2.10已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其他字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解:LinkList_Divide(LinkList &L,CiLis

9、t &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(sizeof(CiLNode); r=C; /建立头结点 while(s!=NULL) if(s->data>='a'&&s->data<='z'

10、|s->data>='A'&&s->data<='Z') p->next=s; p=s; else if(s->data>='0'&&s->data<='9') q->next=s; q=s; else r->next=s; r=s; p->next=A; q->next=B; r->next=C; 2.11设线性表A=（a1，a2，,am），B=（b1，b2，bn），试写一个按下列规则合并A、B为线性表C的算法，使

11、得C=（a1，b1，an，bn，an+1，am）当m>n时或者C=（a1，b1，am，bm，bm+1，bn）当m<=n时线性表A、B、C均以单链表作为储存结构，且C表利用A表和B表中的结点空间构成。解：Liklist merge(Linklist A Linklist B)Linklist C;Node *pa,*pb,*r;C=A;r=A;pa=A->next;pb=B->next;while(pa!=NULL&&pb!=NULL)r->next=pa;r=pa;pa=pa->next;r->next=pb;r=pb;pb=pb-&g

12、t;next;if(pa=NULL)r->next=pb;elser->next=pa;return(C);2.12将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。解：typedef struct Polynodeint coef;int exp;struct polynode *next;Polynode *PolyList;void GreateCircle LinklistC(Linklist RL,Node *e)Node *p;p=RL->next;RL->next=e;R

13、L=RL->next;RL->next=p;void DescouposeList(Linklist RL Descoupose RA Descoupose RB)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;2.13建立一个带头节点的线性表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位，并在此链上实现对二进制数加1的运算。解：void BinnaryFod(Dlinklist DL)DNode *p,*s;p=DL;while(p->