算法与数据结构习题答案

《算法与数据结构习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构习题答案3.3在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：　　在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。3.12已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的

2、结点空间，头结点可另辟空间。解：　　要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。算法如下：　　//设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针.　　voidDivideList(LinkListL,LinkListA,LinkListB,LinkListC)　　　{　　　　ListNode*p=L->next,*q;　　　　while(p)　　　　　{　　　　　　if(p->data>='a'&&p

3、->data<='z'

4、

5、p->data>='A'&&p->data<='Z')　　　　　　　{　　　　　　　　q=p->next;　　　　　　　　p=p->next;//指向下一结点　　　　　　　　q->next=A->next;//将字母结点链到A表中　　　　　　　　A->next=q;A=q;　　　　　　　}　　　　　　elseif(p->data>='0'&&p->data<='9')　　　　　　　　　{//分出数字结点　　　　　　　　　　q=p->next;　　　　　　　　　　p=p->next;//指

6、向下一结点　　　　　　　　　　q->next=B->next;//将数字结点链到B表中　　　　　　　　　　B->next=q;B=q;　　　　　　　　　}　　　　　　　　else{//分出其他字符结点　　　　　　　　　　　　q=p->next;　　　　　　　　　　　　p=p->next;//指向下一结点　　　　　　　　　　　　q->next=C->next;//将其他结点链到C表中　　　　　　　　　　　　C->next=q;C=q;　　　　　　　　　　　}　　　　　}　　　}//结束3.13设有一个双链表，每个结

7、点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。解：　　LocateNode运算的基本思想就是在双向链表中查找值为x的结点，具体方法与单链表中查找一样。找到结点*p后给freq域的值加1。由于原来比*p结点查找频度高的结点

8、都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p结点频度的结点*q后，将*p结点从原来的位置删除，并插入到*q后就可以了。算法如下：　//双向链表的存储结构　　　typedefstructdlistnode{　　　　　DataTypedata;　　　　　structdlistnode*prior,*next;　　　　　intfreq;　　　　}DListNode;　　　typedefDListNode*DLinkList;　　　voidLocateNode(LinkListL,DataTypex

9、)　　　　{　　　　　ListNode*p,*q;　　　　　p=L->next;//带有头结点　　　　　while(p&&p->data!=x)　　　　　　p=p->next;　　　　　if(!p)ERROR("xisnotinL");//双链表中无值为x的结点　　　　　else{p->freq++;//freq加1　　　　　　　　q=p->prior;//以q为扫描指针寻找第一个频度大于或等于*p频度的结点　　　　　　　　while(q!=L&&q->freqfreq)　　　　　　　　　q=q->pri

10、or;　　　　　　　　if(q->next!=p)//若*q结点和*p结点不为直接前趋直接后继关系，　　　　　　　　　　　　　　　//则将*p结点链到*q结点后　　　　　　　　　{p->prior->next=p->next;//将*p从原来位置摘下　　　　　　　　　　p->next->prior=p->prior;　　　　　　　　　　q->next->prior=p;/