《数据结构习题课.pptx》由会员分享，可在线阅读，更多相关《数据结构习题课.pptx（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、有进步很多同学的算法写得更好了有些同学开始尝试自己写算法了第1页/共42页作业2-1题目描述 编写算法Reverse(A,n)，将顺序存储的线性表A=(a1,a2,an)转换为A=(an,a2,a1)，要求转换过程中用尽可能少的辅助空间。第2页/共42页如果不限制辅助空间辅助数组双下标i、j,同时向中间移动第3页/共42页只需从线性表的第一个数据元素开始，将第i个数据元素与第n-i+1个数据元素相交换即可。在这个过程中，i的变化范围是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-
2、1)+2(n-1)+2n+1n+1第4页/共42页参考答案算法ReverseReverse（A A，n.An.A）Reverse1.Reverse1.元素互换 FOR i=1 TO DOFOR i=1 TO DO Ai Ai An-i+1.An-i+1.第5页/共42页作业情况错误最多的情况，交换终止位置下标从1开始：n/2 (div(n/2)是错误的写法)下标从0开始：(n-1)/2讨论n为奇偶两种情况，写相同的代码不必要的特判（如n=0,n=1）有1位同学：1 (n+1)/2保存到数组B中，A向前窜，然后B中元素放到A的后面第6页/共42页2-3已知长度为n的线性表A采用顺序结构存储，请写
3、一算法，找出该线性表中值最小的元素的位置。第7页/共42页参考答案算法FMIN(A,n.pos)/*找顺序表A中最小元素的位置*/FM1初始化pos 1FM2 循环FOR i 2 TO n DO IF(AiApos)pos i.第8页/共42页作业情况最多的问题：不求位置，而是求最小值有些同学求最小值使用第1章的BS第9页/共42页2-6分析单链表中删除操作的时间复杂度第10页/共42页参考答案单链表类中的删除操作delete(k,item)，k表示待删元素位置，item保存待删元素的值定位第k个元素，需要时间k-1.1=k maxk)THEN RETURN.D2 边定位边删除 pre hea
4、d.p next(head).while(pNULL)(IF(data(p)=mink AND data(p)maxk)THEN BREAK.)第19页/共42页同学的较赞做法（仿车雅玲等）void SLList:Delete(T minv,T maxv)SLNode*p=head,q;while(p-next!=0)/定位minv前驱if(p-next-dataminv)break;p=p-next;q=p-next;while(q!=0&q-data next=q-next;delete q;q=p-next;第20页/共42页作业情况最多的情况是抄了一个网上算法。正确但繁琐自己写的同学能
5、有交作业的一半，赞一个常见问题：定位到minv结点，不是前驱，链会删断不必要的特判：最后一个元素是否小于minv。做这个特判的代价是O(n)第21页/共42页2-13设有一个双向循环链表，每个结点中除有prior、data和next三个域外，还增设一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零。而每当对链表进行一次LOCATE(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的方法。第22
6、页/共42页分析LOCATE(L,x)的理解顺序存储？返回值是什么按照教材来第23页/共42页算法 Locate(L,x.L)/*在双向循环链中定位值为x结点，修改freq并按递减序调整，删除第一个碰到的x，有哨兵变量*/L1定位值为x的元素,修改freq p next(head(L).WHILE(phead(L)&data(p)x)p next(p).IF(p=head(L)THEN RETURN.inc(freq(p).L2 递减序调整 q p./找freq大于等于p的结点q WHILE(qhead(L)AND freq(prior(q)freq(p)DO q prior(q).prior
7、(next(p)prior(p).next(prior(p)=next(p)./删 prior(p)q.next(p)next(q)./插 prior(next(p)p.next(prior(p)p.).第24页/共42页算法 Locate(L,x.L)/*在双向循环链中定位值为x结点，修改freq并按递减序调整，删除所有碰到的x，有哨兵变量*/L1定位值为x的元素,修改freq p next(head(L).WHILE(phead(L)DO(IF(data(p)!=x)THEN(p next(p).CONTINUE.)inc(freq(p).t next(p)./递减序调整 q p./找fr
8、eq大于等于p的结点q WHILE(qhead(L)AND freq(prior(q)DO q prior(q).prior(next(p)prior(p).next(prior(p)=next(p)./删 prior(p)q.next(p)next(q)./插 prior(next(p)p.next(prior(p)p.p t).第25页/共42页作业情况最多的情况是抄了一个网上算法。Exchange是不对的。自己写的同学有多种方法，很好逐步向前交换结点或数据找到在的位置讨论两种情况：头结点后和其它结点第26页/共42页2-14请用图来说明对空栈L执行如下操作序列后堆栈的状态：Push(10
9、),Push(4),Push(7),Pop,Push(15),Pop,Pop,Push(1)第27页/共42页2-25编写并实现双端队列类。双端队列（Deque）是可进行如下操作的线性表。(1)push(item):将元素item插入到双端队列的前端(2)pop(item):从双端队列删除前端元素并赋给item(3)inject(item):将元素item插入到双端队列的尾端(4)eject(item):从双端队列删除尾端元素并赋给item第28页/共42页分析顺序存储还是链式存储？顺序存储：仿照顺序队列类P44链式存储：仿照链式队列类P45第29页/共42页作业情况单链表最多，eject的时
10、间复杂性O(n)有几个同学写了双向循环链有几个同学写了顺序存储(循环队)有一个同学写了固定头指针的顺序存储，push、pop都是O(n)第30页/共42页参考答案（双向循环链版本）template class Dequeprivate:DLNode*head;public:Deque()head=new DLNode;head-left=head;head-right=head;Deque()del();bool push(const T&item)bool pop(T&item);bool inject(const T&item)bool eject(T&item);第31页/共42页tem
11、plate bool Deque:push(const T&item)p=new DLNode(item,head,head-right);if(p=NULL)return false;left(right(p)=p;right(left(p)=p;return true；第32页/共42页template bool Deque:pop(T&item)if(right(head)=head)return false;p=right(head);item=p-data;left(right(p)=left(p);right(left(p)=right(p);return true；第33页/共4
12、2页template bool Deque:inject(const T&item)p=new DLNode(item,head-left,head);if(p=NULL)return false;left(right(p)=p;right(left(p)=p;return true；第34页/共42页template bool Deque:pop(T&item)if(left(head)=head)return false;p=left(head);item=p-data;left(right(p)=left(p);right(left(p)=right(p);return true；第35
13、页/共42页作业2-17对于顺序堆栈和链式堆栈s，分别编写函数SelectItem（Stack&s，int n），要求在堆栈中查找元素n在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用int匹配堆栈的模板）第36页/共42页分析解题思路取栈顶元素，若不匹配，则对 s 进行弹栈操作找到（或无法找到）后恢复原来的元素次序关键在于记录弹出的顺序，后弹出的元素能够先被压回原来的栈 s，因此需要使用一个辅助堆栈第37页/共42页算法思想示例：n=51n=51101051511212s shelpStackhelpStack51517 73 3101051511212s s
14、helpStackhelpStack51517 73 3101051511212s shelpStackhelpStack51517 73 3第38页/共42页参考答案int SelectItem(Stack&s,int n)AStack temp(100);/顺序堆栈 /LStack temp;/链式堆栈 bool flag=false;int loc=0;第39页/共42页 while(!s.isEmpty()&s.Peek()!=n)temp.Push(s.Pop();loc+;if(!s.isEmpty()s.Pop();flag=true;第40页/共42页 while(!temp.isEmpty()s.Push(temp.Pop();if(flag)s.Push(n)else loc=-1;return loc;第41页/共42页感谢您的观看！第42页/共42页