数据结构习题课学习教案.pptx

《数据结构习题课学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构习题课学习教案.pptx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)习题课习题课第一页，共42页。有进步有进步(jnb)n n很多同学的算法写得更好了n n有些(yuxi)同学开始尝试自己写算法了第1页/共42页第二页，共42页。作业作业(zuy)2-1n n题目描述n n n n 编写算法Reverse(A,n)，将顺序存储的线性表A=(a1,a2,an)转换(zhunhun)为A=(an,a2,a1)，要求转换(zhunhun)过程中用尽可能少的辅助空间。第2页/共42页第三页，共42页。如果不限制辅助如果不限制辅助(fzh)空间空间n n辅助数组n n双下标i、j,同时(tngsh)向中间移动n n第3页/共

2、42页第四页，共42页。n n只需从线性表的第一个数据元素只需从线性表的第一个数据元素(yun s)(yun s)开始，将第开始，将第i i个数个数据元素据元素(yun s)(yun s)与第与第n-i+1n-i+1个数据元素个数据元素(yun s)(yun s)相交换即相交换即可。在这个过程中，可。在这个过程中，i i的变化范围是的变化范围是1 1到到 。a a1 1a a2 2a an-1n-1a an na an na an-1n-1a a2 2a a1 11+n1+n2+(n-2+(n-1)1)(n-1)+2(n-1)+2n+1n+1第4页/共42页第五页，共42页。参考答案参考答案算

3、法算法算法算法(sun f)Reverse(sun f)Reverse(sun f)Reverse(sun f)Reverse（A A A A，n.An.An.An.A）Reverse1.Reverse1.Reverse1.Reverse1.元素互换元素互换元素互换元素互换 FOR i=1 FOR i=1 FOR i=1 FOR i=1 TOTOTOTO DO DO DO DO Ai Ai Ai Ai An-i+1.An-i+1.An-i+1.An-i+1.第5页/共42页第六页，共42页。作业作业(zuy)情况情况n n错误最多的情况，交换终止位置(wi zhi)n n下标从1开始：n/2

4、(div(n/2)是错误的写法)n n下标从0开始：(n-1)/2n n讨论n为奇偶两种情况，写相同的代码n n不必要的特判（如n=0,n=1）n n有1位同学：1 (n+1)/2保存到数组B中，A向前窜，然后B中元素放到A的后面第6页/共42页第七页，共42页。2-3n n已知长度为n的线性表A采用顺序结构(jigu)存储，请写一算法，找出该线性表中值最小的元素的位置。第7页/共42页第八页，共42页。参考答案参考答案算法FMIN(A,n.pos)/*找顺序表A中最小元素的位置(wi zhi)*/FM1初始化pos 1FM2 循环FOR i 2 TO n DO IF(AiApos)pos i

5、.第8页/共42页第九页，共42页。作业作业(zuy)情况情况n n最多的问题(wnt)：不求位置，而是求最小值n n有些同学求最小值使用第1章的BS第9页/共42页第十页，共42页。2-6n n分析单链表中删除(shnch)操作的时间复杂度第10页/共42页第十一页，共42页。参考答案参考答案n n单链表类中的删除操作delete(k,item)，k表示待删元素位置，item保存待删元素的值n n定位第k个元素，需要时间k-1.1=k maxk)THEN RETURN.IF(minkmaxk)THEN RETURN.D2 D2 边定位边删除边定位边删除边定位边删除边定位边删除 pre hea

6、d.p next(head).pre head.p next(head).while(pNULL)(while(pNULL)(IF(data(p)mink)THEN(pre p.pnext(p).).IF(data(p)=mink AND data(p)=mink AND data(p)maxk)THEN BREAK.IF(data(p)maxk)THEN BREAK.)第19页/共42页第二十页，共42页。同学同学(tng xu)的较赞做法（仿的较赞做法（仿车雅玲等）车雅玲等）void SLList:Delete(T minv,T maxv)void SLList:Delete(T minv

7、,T maxv)SLNode*p=head,q;SLNode*p=head,q;while(p-next!=0)/while(p-next!=0)/定位定位minvminv前驱前驱(qinq)(qinq)if(p-next-dataminv)break;if(p-next-dataminv)break;p=p-next;p=p-next;q=p-next;q=p-next;while(q!=0&q-data data next=q-next;p-next=q-next;delete q;delete q;q=p-next;q=p-next;第20页/共42页第二十一页，共42页。作业作业(zu

8、y)情况情况n n最多的情况是抄了一个网上算法。正确但繁琐n n自己写的同学能有交作业的一半，赞一个n n常见问题：定位到minv结点，不是前驱，链会删断n n不必要的特判：最后(zuhu)一个元素是否小于minv。做这个特判的代价是O(n)第21页/共42页第二十二页，共42页。2-13n n设有一个双向循环链表，每个结点中除有prior、data和next三个域外，还增设一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零。而每当(mi dn)对链表进行一次LOCATE(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值增1，同时调整链表中结点

9、之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的方法。第22页/共42页第二十三页，共42页。分析分析(fnx)n nLOCATE(L,x)的理解n n顺序存储？n n返回值是什么(shn me)n n按照教材来第23页/共42页第二十四页，共42页。算法算法算法算法 Locate(L,x.L)Locate(L,x.L)/*/*在双向循环链中定位值为在双向循环链中定位值为在双向循环链中定位值为在双向循环链中定位值为x x结点，修改结点，修改结点，修改结点，修改freqfreq并按递减序调整，删并按递减序调整，删

10、并按递减序调整，删并按递减序调整，删除第一个碰到的除第一个碰到的除第一个碰到的除第一个碰到的x x，有哨兵，有哨兵，有哨兵，有哨兵(shobng)(shobng)变量变量变量变量*/*/L1L1定位值为定位值为定位值为定位值为x x的元素的元素的元素的元素,修改修改修改修改freqfreq p next(head(L).p next(head(L).WHILE(phead(L)&data(p)x)p next(p).WHILE(phead(L)&data(p)x)p next(p).IF(p=head(L)THEN RETURN.IF(p=head(L)THEN RETURN.inc(freq

11、(p).inc(freq(p).L2 L2 递减序调整递减序调整递减序调整递减序调整 q p./q p./找找找找freqfreq大于等于大于等于大于等于大于等于p p的结点的结点的结点的结点q q WHILE(qhead(L)AND freq(prior(q)freq(p)DO q WHILE(qhead(L)AND freq(prior(q)freq(p)DO q prior(q).prior(q).prior(next(p)prior(p).next(prior(p)=next(p)./prior(next(p)prior(p).next(prior(p)=next(p)./删删删删 p

12、rior(p)q.next(p)next(q)./prior(p)q.next(p)next(q)./插插插插 prior(next(p)p.next(prior(p)p.).prior(next(p)p.next(prior(p)p.).第24页/共42页第二十五页，共42页。算法算法算法算法 Locate(L,x.L)Locate(L,x.L)/*/*在双向循环链中定位值为在双向循环链中定位值为在双向循环链中定位值为在双向循环链中定位值为x x结点，修改结点，修改结点，修改结点，修改freqfreq并按递减并按递减并按递减并按递减(dji(dji n)n)序调整，删除所有碰到的序调整，删除

13、所有碰到的序调整，删除所有碰到的序调整，删除所有碰到的x x，有哨兵变量，有哨兵变量，有哨兵变量，有哨兵变量*/*/L1L1定位值为定位值为定位值为定位值为x x的元素的元素的元素的元素,修改修改修改修改freqfreq p next(head(L).p next(head(L).WHILE(phead(L)DO(WHILE(phead(L)DO(IF(data(p)!=x)THEN(p next(p).CONTINUE.)IF(data(p)!=x)THEN(p next(p).CONTINUE.)inc(freq(p).t next(p).inc(freq(p).t next(p)./递减

14、递减递减递减(dji(dji n)n)序调整序调整序调整序调整 q p./q p./找找找找freqfreq大于等于大于等于大于等于大于等于p p的结点的结点的结点的结点q q WHILE(qhead(L)AND freq(prior(q)DO q WHILE(qhead(L)AND freq(prior(q)DO q prior(q).prior(q).prior(next(p)prior(p).next(prior(p)=next(p)./prior(next(p)prior(p).next(prior(p)=next(p)./删删删删 prior(p)q.next(p)next(q)./

15、prior(p)q.next(p)next(q)./插插插插 prior(next(p)p.next(prior(p)p.prior(next(p)p.next(prior(p)p.p t).p t).第25页/共42页第二十六页，共42页。作业作业(zuy)情况情况n n最多的情况是抄了一个网上算法。Exchange是不对的。n n自己写的同学有多种方法，很好n n逐步向前交换结点或数据(shj)n n找到在的位置讨论两种情况：头结点后和其它结点第26页/共42页第二十七页，共42页。2-14n n请用图来说明对空栈L执行如下(rxi)操作序列后堆栈的状态：n nPush(10),Push(

16、4),Push(7),Pop,n nPush(15),Pop,Pop,Push(1)第27页/共42页第二十八页，共42页。2-25n n编写并实现双端队列类。双端队列（编写并实现双端队列类。双端队列（DequeDeque）是可进行如下操作）是可进行如下操作(cozu)(cozu)的线性表。的线性表。n n(1)push(item):(1)push(item):将元素将元素itemitem插入到双端队列的前端插入到双端队列的前端n n(2)pop(item):(2)pop(item):从双端队列删除前端元素并赋给从双端队列删除前端元素并赋给itemitemn n(3)inject(item):

17、(3)inject(item):将元素将元素itemitem插入到双端队列的尾端插入到双端队列的尾端n n(4)eject(item):(4)eject(item):从双端队列删除尾端元素并赋给从双端队列删除尾端元素并赋给itemitem第28页/共42页第二十九页，共42页。分析分析(fnx)n n顺序存储(cn ch)还是链式存储(cn ch)？n n顺序存储(cn ch)：仿照顺序队列类P44n n链式存储(cn ch)：仿照链式队列类P45第29页/共42页第三十页，共42页。作业作业(zuy)情况情况n n单链表最多，eject的时间(shjin)复杂性O(n)n n有几个同学写了双

18、向循环链n n有几个同学写了顺序存储(循环队)n n有一个同学写了固定头指针的顺序存储，push、pop都是O(n)第30页/共42页第三十一页，共42页。参考答案（双向循环参考答案（双向循环(xnhun)链版本）链版本）template template class Dequeclass Deque private:private:DLNode*head;DLNode*head;public:public:Deque()head=new DLNode;head-left=head;head-right=head;Deque()head=new DLNode;head-left=head;he

19、ad-right=head;Deque()del()Deque()del();bool push(const T&item)bool push(const T&item)bool pop(T&item);bool pop(T&item);bool inject(const T&item)bool inject(const T&item)bool eject(T&item);bool eject(T&item);第31页/共42页第三十二页，共42页。template template bool Deque:push(const T&item)bool Deque:push(const T&it

20、em)p=new DLNode(item,head,head-right);p=new DLNode(item,head,head-right);if(p=NULL)return false;if(p=NULL)return false;left(right(p)=p;left(right(p)=p;right(left(p)=p;right(left(p)=p;return true return true；第32页/共42页第三十三页，共42页。template template bool Deque:pop(T&item)bool Deque:pop(T&item)if(right(he

21、ad)=head)return false;if(right(head)=head)return false;p=right(head);p=right(head);item=p-data;item=p-data;left(right(p)=left(p);left(right(p)=left(p);right(left(p)=right(p);right(left(p)=right(p);return true return true；第33页/共42页第三十四页，共42页。template template bool Deque:inject(const T&item)bool Deque

22、:inject(const T&item)p=new DLNode(item,head-left,head);p=new DLNode(item,head-left,head);if(p=NULL)return false;if(p=NULL)return false;left(right(p)=p;left(right(p)=p;right(left(p)=p;right(left(p)=p;return true return true；第34页/共42页第三十五页，共42页。template template bool Deque:pop(T&item)bool Deque:pop(T&

23、item)if(left(head)=head)return false;if(left(head)=head)return false;p=left(head);p=left(head);item=p-data;item=p-data;left(right(p)=left(p);left(right(p)=left(p);right(left(p)=right(p);right(left(p)=right(p);return true return true；第35页/共42页第三十六页，共42页。作业作业(zuy)2-17n n对于顺序堆栈和链式堆栈对于顺序堆栈和链式堆栈s，分别编写函数，

24、分别编写函数SelectItem（Stack&s，int n），要求在堆栈中查，要求在堆栈中查找元素找元素n在栈中第一次出现的位置，并将该在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次序不位置元素移至栈顶，同时其他元素次序不变。（注意：用变。（注意：用int匹配匹配(ppi)堆栈的模板）堆栈的模板）第36页/共42页第三十七页，共42页。分析分析(fnx)n n解题思路解题思路n n取栈顶元素，若不匹配，则对取栈顶元素，若不匹配，则对 s s 进行弹栈操作进行弹栈操作n n找到（或无法找到）后恢复原来的元素次序找到（或无法找到）后恢复原来的元素次序n n关键在于记录弹出的顺序，

25、后弹出的元素能够先被压回原关键在于记录弹出的顺序，后弹出的元素能够先被压回原来的栈来的栈 s s，因此需要使用一个，因此需要使用一个(y(y )辅助堆栈辅助堆栈第37页/共42页第三十八页，共42页。n n算法思想算法思想算法思想算法思想(sxing)(sxing)(sxing)(sxing)示例：示例：示例：示例：n=51 n=51 n=51 n=51101051511212s shelpStackhelpStack51517 73 3101051511212s shelpStackhelpStack51517 73 3101051511212s shelpStackhelpStack515

26、17 73 3第38页/共42页第三十九页，共42页。参考答案参考答案int SelectItem(Stack&s,int n)int SelectItem(Stack&s,int n)AStack temp(100);/AStack temp(100);/顺序顺序顺序顺序(shnx)(shnx)堆栈堆栈堆栈堆栈 /LStack temp;/LStack temp;/链式堆栈链式堆栈链式堆栈链式堆栈 bool flag=false;bool flag=false;int loc=0;int loc=0;第39页/共42页第四十页，共42页。while(while(!s.isEmpty()&s.Peek()!=n!s.isEmpty()&s.Peek()!=n )temp.Push(s.Pop();temp.Push(s.Pop();loc+;loc+;if(if(!s.isEmpty()!s.isEmpty()s.Pop();flag=true;s.Pop();flag=true;第40页/共42页第四十一页，共42页。while(!temp.isEmpty()s.Push(temp.Pop();if(flag)s.Push(n)else loc=-1;return loc;第41页/共42页第四十二页，共42页。