数据结构作业答案.ppt

线性表作业答案 1 编写算法实现顺序表的就地逆置 defineMaxSizetypedefstruct DataTypelist MaxSize intsize SeqList voidConverseSeqList SeqList L intmid i DataTypex mid L size 2 for i 0 ilist i L list i L list L size 1 i L list L size 1 i x 2 编写算法实现单链表的就地逆置 先定义结点结构 typedefstructNode DataTypedata structNode next SLNode voidConverseSList SLNode head SLNode p q p head next head next NULL while p NULL q p p p next q next head next head next q 3 已知线性表中的元素以值递增有序排列 并以单链表作存储结构 设计算法删除表中所有值大于mink且小于maxk的元素 分析 删除的结点的特点 mink maxk voidDelete Between SLNode L intmink intmaxk 删除元素递增排列的链表L中值大于mink且 小于maxk的所有元素 SLNode p pre q s p L next while p 4 已知A B和C为三个有序链表 编写算法从A表中删除B表和C表中共有的数据元素 分析 被删元素的特点 ai bj ck其它元素则为 ai bj或bj ck或ck ai 设三个指针pa pb pc分别指向这三个链表中的相应结点 则算法中的主要操作为 if pa datadata pre pa pa pa next elseif pb datadata pb pb next elseif pc datadata pc pc next else pre next pa next free pa pa pre next 循环条件 三个指针均不为空 voidDelSame SLNode la SLNode lb SLNode lc SLNode pre pa pb pc pre la pa la next pb lb next pc lc next while pa 5 设将n n 1 个整数存放到一维数组R中 试设计一个在时间和空间两方面尽可能高效的算法 将R中的序列循环左移p 0 p n 个位置 即将R中的数据由 x0 x1 xn 1 变换为 xp xp 1 xn 1 x0 x1 xp 1 要求 1 给出算法的基本设计思想 2 根据设计思想 采用C或C 语言描述算法 关键之处给出注释 3 说明你所设计算法的时间复杂度和空间复杂度 1 算法的基本设计思想 先将n个数 x0 x1 xp xn 1 原地逆置 得到 xn 1 xp xp 1 x0 然后再将前n p个和后p个元素分别原地逆置 得到最终结果 xp xp 1 xn 1 x0 x1 xp 1 算法可以用两个函数实现 一个是逆置函数reverse 它将给定的数据逆置 另一个是循环左移函数leftShift 它调用reverse 函数三次 实现相应功能 2 算法实现 voidreverse intr intleft intright intk left j right temp k等于左边界left j等于右边界rightwhile k j 交换r k 与r j temp r k r k r j r j temp k k右移一个位置j j左移一个位置 voidleftShift intr intn intp if p 0 将后p个元素逆置 3 算法的时间复杂度为O n 空间复杂度为O 1 6 假设利用两个线性表LA和LB分别表示两个集合A和B 即 线性表中的数据元素即为集合中的成员 现要求一个新的集合A A B 采用单链表作为存储结构 编写算法 上述问题等价于 要求对线性表作如下操作 扩大线性表LA 将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去 1 从线性表LB中依次察看每个数据元素 2 依值在线性表LA