《数据结构习题课2.ppt》由会员分享，可在线阅读，更多相关《数据结构习题课2.ppt（42页珍藏版）》请在三一文库上搜索。
1、数据结构习题 第 2 章,有进步,很多同学的算法写得更好了 有些同学开始尝试自己写算法了,作业2-1,题目描述 编写算法Reverse ( A , n)，将顺序存储的线性表A=( a1, a2, , an )转换为A=( an, a2, a1)，要求转换过程中用尽可能少的辅助空间。,如果不限制辅助空间,辅助数组 双下标i、j, 同时向中间移动 ,只需从线性表的第一个数据元素开始，将第i个数据元素与第n-i+1个数据元素相交换即可。在这个过程中，i的变化范围是1到 。,参考答案,算法Reverse（A，n . A） Reverse1.元素互换 FOR i=1 TO DO Ai An-i+1.,作
2、业情况,错误最多的情况，交换终止位置 下标从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) /*找顺序表A中最小元素的位置*/ FM1初始化 pos 1 FM2 循环 FOR i 2 TO n DO IF(AiApos) pos i. ,作业情况,最多的问题：不求位置
3、，而是求最小值 有些同学求最小值使用第1章的BS,2-6,分析单链表中删除操作的时间复杂度,参考答案,单链表类中的删除操作delete(k,item)，k表示待删元素位置，item保存待删元素的值 定位第k个元素，需要时间k-1. 1= k = n 指针的调整，4步操作 以定位为基本元素，最坏复杂性为O(n). n为单链表中的数据规模,作业情况,错误最多的是：讨论deletefromhead、deletefromtail、delete(T while(p-next != 0) /定位minv前驱 if(p-next-dataminv) break; p=p-next; q=p-next; wh
4、ile(q!=0 ,作业情况,最多的情况是抄了一个网上算法。正确但繁琐 自己写的同学能有交作业的一半，赞一个 常见问题：定位到minv结点，不是前驱，链会删断 不必要的特判：最后一个元素是否小于minv。做这个特判的代价是O(n),2-13,设有一个双向循环链表，每个结点中除有prior、data和next三个域外，还增设一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零。而每当对链表进行一次LOCATE(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访
5、问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的方法。,分析,LOCATE(L,x)的理解 顺序存储？ 返回值是什么 按照教材来,算法 Locate(L,x.L) /*在双向循环链中定位值为x结点，修改freq并按递减序调整，删除第一个碰到的x，有哨兵变量*/ L1定位值为x的元素,修改freq p next(head(L). WHILE(phead(L) public: Deque () head = new DLNode; head-left=head; head-right=head ; Deque () del() ; bool push ( const T,template bool Deque:push ( const T return true； ,template bool Deque:pop (T return true； ,template bool Deque: inject( const T return true； ,template bool Deque:pop (T return true； ,作业2-17,对于顺序堆栈和链式堆栈s，分别编写函数SelectItem（ Stack if (flag) s.Push(n) else loc = -1; return loc; ,