数据结构习题课2复习进程.ppt

《数据结构习题课2复习进程.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构习题第2章吉林大学计算机科学与技术学院谷方明有进步很多同学的算法写得更好了有些同学开始尝试自己写算法了作业2-1题目描述编写算法Reverse(A[],n)，将顺序存储的线性表A=(a1,a2,…,an)转换为A=(an,…,a2,a1)，要求转换过程中用尽可能少的辅助空间。如果不限制辅助空间……辅助数组双下标i、j,同时向中间移动……只需从线性表的第一个数据元素开始，将第i个数据元素与第n-i+1个数据元素相交换即可。在这个过程中，i的变化范围是1到。a1a2…an-1ananan-1…a2a11+n2+(n-1)…(

2、n-1)+2n+1参考答案算法Reverse（A，n.A）Reverse1.[元素互换]FORi=1TODOA[i]A[n-i+1].▌作业情况错误最多的情况，交换终止位置下标从1开始：n/2(div(n/2)是错误的写法)下标从0开始：(n-1)/2讨论n为奇偶两种情况，写相同的代码不必要的特判（如n=0,n=1）有1位同学：1–(n+1)/2保存到数组B中，A向前窜，然后B中元素放到A的后面2-3已知长度为n的线性表A采用顺序结构存储，请写一算法，找出该线性表中值最小的元素的位置。参考答案算法FMIN(A,n.pos)/*

3、找顺序表A中最小元素的位置*/FM1[初始化]pos←1FM2[循环]FORi←2TOnDOIF(A[i]

4、deletefromtail、delete(T&item)，并且说delete(T&item)是O(1)的有几位同学说最好是1，最坏是n，因此平均是n/2（平均是指期望时间复杂性）求期望时间复杂性，结论不一作业2-8设计一个算法，将链表的链接完全颠倒。分析ABCDp2p1p3算法Reverse(head.head)/*将指针head所指向的链表倒置*/RV1[空链表]IF(next(head)=NULL)RETURN.RV2[指针初始化]//P1,P2分别指向两个连续的节点P1NULL.P2next(head).RV3[反转

5、链表]WHILE(P2≠NULL)DO(P3next(p2)next(P2)P1.//反转节点指针P1P2.P2P3.//移动3个指针）RV4[head指向反转链表]next(head)P1.▌其它方法使用两个指针i和j，从首尾两侧向中间推进作业中使用最多的方法，注意length()和prev()实现使用数组或堆栈将元素倒置通过堆栈进行倒置（链栈）从表头删除，再插入表尾之后。2-11已知线性表中的元素以data值递增有序排列，并以单链表做存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存

6、在这样的元素），同时释放被删节点空间，并分析该算法的时间复杂度。(注意，mink和maxk是给定的两个参数，它们的值可以跟表中的元素相同，也可以不同)分析边定位边删除时间复杂性T(n)=maxv结点的位置，记为O(n)算法Delete(head,mink,maxk.head)/*删除单链表中值在mink和maxk之间的元素，单链表有哨兵变量*/D1[特殊情况]IF(mink>maxk)THENRETURN.D2[边定位边删除]pre←head.p←next(head).while(p<>NULL)(IF(data(p)

7、)THEN(pre←p.p←next(p).).IF(data(p)>=minkANDdata(p)<=maxk)THEN(next(pre)←next(p).AVAILp.p←next(pre)).IF(data(p)>maxk)THENBREAK.)▌同学的较赞做法（仿车雅玲等）voidSLList::Delete(Tminv,Tmaxv){SLNode*p=head,q;while(p->next!=0){//定位minv前驱if(p->next->data>minv)break;p=p->next;}q=

8、p->next;while(q!=0&&q->datanext=q->next;deleteq;q=p->next;}}作业情况最多的情况是抄了一个网上算法。正确但繁琐自己写的同学能有交作业的一半，赞一个常见问题：定位到minv结点，