数据结构习题课2.ppt

数据结构习题第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 元素互换 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 找顺序表A中最小元素的位置 FM1 初始化 pos 1FM2 循环 FORi 2TOnDOIF A i A pos pos i 作业情况 最多的问题 不求位置 而是求最小值有些同学求最小值使用第1章的BS 2 6 分析单链表中删除操作的时间复杂度 参考答案 单链表类中的删除操作delete k item k表示待删元素位置 item保存待删元素的值定位第k个元素 需要时间k 1 1 k n指针的调整 4步操作以定位为基本元素 最坏复杂性为O n n为单链表中的数据规模 作业情况 错误最多的是 讨论deletefromhead deletefromtail delete T item 并且说delete T item 是O 1 的有几位同学说最好是1 最坏是n 因此平均是n 2 平均是指期望时间复杂性 求期望时间复杂性 结论不一 作业2 8 设计一个算法 将链表的链接完全颠倒 分析 A B C D p2 p1 算法Reverse head head 将指针head所指向的链表倒置 RV1 空链表 IF next head NULL RETURN RV2 指针初始化 P1 P2分别指向两个连续的节点P1 NULL P2 next head RV3 反转链表 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的元素 若表中存在这样的元素 同时释放被删节点空间 并分析该算法的时间复杂度 注意 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 pNULL IF data p minkANDdata 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 p next while q 0 作业情况 最多的情况是抄了一个网上算法 正确但繁琐自己写的同学能有交作业的一半 赞一个常见问题 定位到minv结点 不是前驱 链会删断不必要的特判 最后一个元素是否小于minv 做这个特判的代价是O n 2 13 设有一个双向循环链表 每个结点中除有prior data和next三个域外 还增设一个访问频度域freq 在链表被起用之前 频度域freq的值均初始化为零 而每当对链表进行一次LOCATE L x 的操作后 被访问的结点 即元素值等于x的结点 中的频度域freq的值增1 同时调整链表中结点之间的次序 使其按访问频度非递增的次序顺序排列 以便始终保持被频繁访问的结点总是靠近表头结点 试编写符合上述要求的LOCATE操作的方法 分析 LOCATE L x 的理解顺序存储 返回值是什么按照教材来 算法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 THENRETURN inc freq p L2 递减序调整 q p 找freq大于等于p的结点qWHILE qhead L ANDfreq prior q freq p DOq 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 算法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 找freq大于等于p的结点qWHILE qhead L ANDfreq prior q DOq 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 作业情况 最多的情况是抄了一个网上算法 Exchange是不对的 自己写的同学有多种方法 很好逐步向前交换结点或数据找到在的位置讨论两种情况 头结点后和其它结点 2 14 请用图来说明对空栈L执行如下操作序列后堆栈的状态 Push 10 Push 4 Push 7 Pop Push 15 Pop Pop Push 1 2 25 编写并实现双端队列类 双端队列 Deque 是可进行如下操作的线性表 1 push item 将元素item插入到双端队列的前端 2 pop item 从双端队列删除前端元素并赋给item 3 inject item 将元素item插入到双端队列的尾端 4 eject item 从双端队列删除尾端元素并赋给item 分析 顺序存储还是链式存储 顺序存储 仿照顺序队列类P44链式存储 仿照链式队列类P45 作业情况 单链表最多 eject的时间复杂性O n 有几个同学写了双向循环链有几个同学写了顺序存储 循环队 有一个同学写了固定头指针的顺序存储 push pop都是O n 参考答案 双向循环链版本 templateclassDeque private DLNode head public Deque head newDLNode head left head head right head Deque del boolpush constT templateboolDeque push constTreturntrue templateboolDeque pop Treturntrue templateboolDeque inject constTreturntrue templateboolDeque pop Treturntrue 作业2 17 对于顺序堆栈和链式堆栈s 分别编写函数SelectItem Stack s intn 要求在堆栈中查找元素n在栈中第一次出现的位置 并将该位置元素移至栈顶 同时其他元素次序不变 注意 用int匹配堆栈的模板 分析 解题思路取栈顶元素 若不匹配 则对s进行弹栈操