部分习题参考答案.ppt

部分习题参考答案.ppt

ID:51629951

大小:726.81 KB

页数:59页

时间:2020-03-26

部分习题参考答案.ppt_第1页
部分习题参考答案.ppt_第2页
部分习题参考答案.ppt_第3页
部分习题参考答案.ppt_第4页
部分习题参考答案.ppt_第5页
资源描述:

《部分习题参考答案.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、练习题2习题2.2、2.3、2.4、2.5和2.6。2.2设计一个算法,将x插入到一个有序(从小到大排序)的线性表(顺序存储结构)的适当位置上,并保持线性表的有序性。voidInsert(SqList*&L,ElemTypex){inti=0,j;while(ilength&&L->data[i]length-1;j>=i;j--)L->data[j+1]=L->data[j];L->data[i]=x;L->length++;}2.3设计一个算法,将一个带头结点的数据域依次为a1,a2,…,an(n≥3)的单链表的所有结点逆

2、置,即第一个结点的数据域变为an,…,最后一个结点的数据域为a1。voidReverse(LinkList*&L){LinkList*p=L->next,*q;L->next=NULL;while(p!=NULL)//扫描所有的结点{q=p->next;//让q指向*p结点的下一个结点p->next=L->next;//总是将*p结点作为第一个数据结点L->next=p;p=q;//让p指向下一个结点}}2.4设有一个双链表,每个结点中除有prior、data和next三个域外,还有一个访问频度域freq,在链表被起用之前,其值均初始化为零。每当进行LocateNo

3、de(h,x)运算时,令元素值为x的结点中freq域的值加1,并调整表中结点的次序,使其按访问频度的递减序排列,以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。boolLocateNode(DLinkList*h,ElemTypex){DLinkList*p=h->next,*q;while(p!=NULL&&p->data!=x)p=p->next;//找data域值为x的节点*pif(p==NULL)//未找到的情况returnfalse;else//找到的情况{p->freq++;//频度增1q=p->prior;//*q

4、为p前驱节点while(q!=h&&q->freqfreq){p->prior=q->prior;p->prior->next=p;//交换*p和*q的位置q->next=p->next;if(q->next!=NULL)//*p不为最后一个节点时q->next->prior=q;p->next=q;q->prior=p;q=p->prior;//q重指向*p的前趋节点}returntrue;}}2.5设ha=(a1,a2,…,an)和hb=(b1,b2,…,bm)是两个带头结点的循环单链表,编写将这两个表合并为带头结点的循环单链表hc的算法。voidMer

5、ge(LinkList*ha,LinkList*hb,LinkList*&hc){LinkList*p=ha->next;hc=ha;while(p->next!=ha)//找到ha的最后一个节点*pp=p->next;p->next=hb->next;//将ha的最后一个节点的next指向hb的第一个数据节点while(p->next!=hb)p=p->next;//找到hb的最后一个节点*pp->next=hc;//构成循环单链表free(hb);//释放hb单链表的头节点}2.6设非空线性表ha和hb都用带头节点的循环双链表表示。设计一个算法Insert(ha

6、,hb,i)。其功能是:i=0时,将线性表hb插入到线性表ha的最前面;当i>0时,将线性表hb插入到线性表ha中第i个节点的后面;当i大于等于线性表ha的长度时,将线性表hb插入到线性表ha的最后面。voidInsert(DLinkList*&ha,DLinkList*&hb,inti){DLinkList*p=ha->next,*q;intlena=1,j=0;while(p->next!=ha)//求出ha的长度lena{lena++;p=p->next;}if(i==0)//将hb的所有数据结点插入到ha的头结点和第1个数据结点之间{p=hb->prior;

7、//p指向hb的最后一个结点/p->next=ha->next;//将*p链到ha的第1个数据结点前面ha->next->prior=p;ha->next=hb->next;hb->next->prior=ha;//将ha头结点与hb的第1个数据结点链起来}elseif(inext;while(jnext;j++;}q=p->next;//q指向*p结点的后继结点/p->next=hb->next;//hb->prior指向hb的最后一个结点hb->next->pr

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。