数据结构第二章课后答案VIP免费

下载本文档

阅读 142
下载 13
格式 doc
大小 52 KB
约7页
2024-11-19 发布于河南
收藏
评论
点赞(0)
海报
举报

1/7页

2/7页

3/7页

在线预览已结束，请下载后查看完整版，加入VIP享文档下载特权

文本预览下载提示常见问题

2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。解：intInsList(SeqList*L,intX){inti=0,k;if(L->last>=MAXSIZE-1){printf("表已满无法插入！")；return(ERROR);}while(i<=L->last&&L->elem[i]last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(OK);}2.5写一算法，从顺序表中删除自第i个元素开始的k个元素。解：intLDel(Seqlist*L,inti,intk){if(i=1||(i+k>L->last+1)){printf("输入的i，k值不合法")；return(ERROR);}elseif(i+k==L->last+2){L->last=i-2;returnOK;}else{j=i+k-1;while(j<=L->last){elem[j-k]=elem[j];j++;}L->last=L->last-k+1;returnOK;}}2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。解：intDelete(Linklist,intmink,intmaxk){Node*p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink>=maxk||L->next->data>=maxk||mink+1=maxk){printf("参数不合法！");returnERROR;}else{while(p->next->data<=mink)p=p->next;q=p->next;while(q->datanext=q->next;free(q);q=p->next;}returnOK;}}2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的储存空间将线性表（a1，a1，…,an）逆置为（an，an-1，…，a1）。（1）以顺序表作存储结构。解：intReversePosition(SpListL){intk,temp,len;intj=0;k=L->last;len=L->last+1;for(j;jelem[k-j];elem[k-j]=elem[j];elem[j]=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=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->data>q1->data){q2=q1->next;q1->next=LC->next;LC->next=q;q1=q2;}else{p2=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已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其他字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解: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(sizeof(CiLNode));r=C;//建立头结点while(s!=NULL){if(s->data>='a'&&s->data<='z'||s->data>='A'&&s->data<='Z'){p->next=s;p=s;}elseif(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的算法，使得C=（a1，b1，…，an，bn，an+1，…，am）当m>n时或者C=（a1，b1，…，am，bm，bm+1，…，bn）当m<=n时线性表A、B、C均以...

1、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
3、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。

碎片内容

数据结构第二章课后答案

4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性

解：intInsList(SeqList*L,intX){inti=0,k;if(L->last>=MAXSIZE-1){printf("表已满无法插入

")；return(ERROR);}while(ilast&&L->elem[i]last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(OK);}2

5写一算法，从顺序表中删除自第i个元素开始的k个元素

解：intLDel(Seqlist*L,inti,intk){if(i=1||(i+k>L->last+1)){printf("输入的i，k值不合法")；return(ERROR);}elseif(i+k==L->last+2){L->last=i-2;returnOK;}else{j=i+k-1;while(jlast){elem[j-k]=elem[j];j++;}L->last=L->last-k+1;returnOK;}}2

6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构

试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）

解：intDelete(Linklist,intmink,intmaxk){Node*p,*q;p=L;while(p->next

=NULL)p=p->next;if(mink>=maxk||L->next->data>=maxk||mink+1=maxk){printf("参数不合法

");returnERROR;}else{while(p->next->datanext;q=p

您可能关注的文档

一米阳光 + 关注: 实名认证
内容提供者

爱好英语教学和互联网行业，热爱教育事业，兢兢业业

收藏店铺进入空间

数据结构第二章课后答案VIP免费

数据结构第二章课后答案

您可能关注的文档

相关文档

热门下载

相关标签