ch2部分习题解答

Chapter2线性表练习 找出以下算法中的错误和低效之处 并将它改写为一个既正确又高效的算法 intDeletek SeqList L inti intk 从顺序表L中删除第i个元素起的k个元素 intcount j if iL size printf n参数不合法 return0 else for count 1 countsize j i 1 j L list j 1 L list j L size return1 改进 intDeletek SeqList L inti intk 从顺序表L中删除第i个元素起的k个元素 intcount j if iL size printf n参数不合法 return0 else 删除k个元素 for j i k jsize j L list j k L list j L size k return1 2010考研题 设将n n 1 个整数存放到一维数组R中 试设计一个在时间和空间两方面尽可能高效的算法 将R中的序列循环左移P 0 P n 个位置 即将R中的数据由 x0 x1 xn 1 变换为 xp xp 1 xn 1 x0 x1 xp 1 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 inti left j right temp i等于左边界left j等于右边界right while i j 交换r i 与r j temp r i r i r j r j temp i i右移一个位置 j j左移一个位置 voidleftShift intr intn intp if p 0 将后p个元素逆置 3 算法复杂性算法的时间复杂度为O n 空间复杂度为O 1 书P46 2 19voidListDeleteMore SLNode L DataTypex 在带头结点的单链表中删除所有值为x的数据元素 SLNode p s p L while p next NULL s p next if s data x p next s next 删除值为x的结点 free s elsep s 补充 已知一个带头结点的递增有序单链表L 试编写一高效算法 删除该链表中所有元素值大于x且小于y的结点 补充 已知两个带表头结点的非递减有序单链表 头指针分别为la和lb 试编写算法 先将两个表合并为一个带表头结点的非递减有序单链表 然后删除表中结点值 data值 相同的冗余结点 最后返回新单链表的头指针 要求新单链表利用原来两个链表的结点空间 不另外生成新结点 voidListMergeDelete SLNode la SLNode lb SLNode lc SLNode pa pb pc 归并两个有序表 lc la pa la next pb lb next pc la while pa 删除冗余结点 pa lc next while pa pb pa next while pb 书P46 2 21 判断两个集合是否存在包含关系 intListSetInclude SLNode L1 SLNode L2 判断带头结点的单链表L1中的数据元素是否都是单链表L2中的数据元素 SLNode p1 p2 p1 L1 next while p1 NULL p2 L2 next while p2 NULL 补充作业1 创建单链表 从表头 表尾 intListCreate SLNode la intn 从键盘输入n个数 建立以la为头指针的带头结点的单链表 inti SLNode p q if la SLNode malloc sizeof SLNode NULL printf 内存空间不足 n return0 q la for i 0 idata q next p q p 新结点p插入在表尾 q next NULL return1 补充作业2 已知一个带头结点的循环双向链表 从第二个结点至表尾递增有序 编写一个算法 将第一个结点删除并插入表中适当位置 使整个链表递增有序 voidListDIDL DLNode h DLNode p s p h next if p h h next p next p next prior h 删除链表中的第一个结点 elsereturn 并用p指针保存 s h next while s h p结点插入在s结点之前 2009考研题 已知一个带头结点的单链表 假设该链表只给出了头指针 在不改变链表的前提下 请设计一个尽可能高效的算法 查找链表中倒数第k个结点 k为正整数 若查找成功 算法输出该结点的data域的值 并返回1 否则 只返回0 intLocatek SLNode h intk SLNode p q