数据结构第2、3章习题.ppt

StatusInsert Sq SqList La ElemTypex 已知顺序表La中元素依值非递减有序排列 本算法 插入新的元素x并保持原表的有序性 返回OK 若顺序表空间已满 则不再插入并返回OVERFLOWif La length La listsize returnOVERFLOW i 0 while ilength Insert Sq 2 2设顺序表va中的数据元素递增有序 试写一算法 将x插入到顺序表的适当位置上 以保持该表的有序性 2 3试写一算法 在带头结点的单链表结构上实现线性表操作LOCATE L X intLOCATE LinkListL ElemTypeX Status compare ElemType ElemType 在带头结点的单链表L中查找第1个值与X满足compare 的元素的位序 若找到 则返回其在L中的位序 否则返回0i 1 p L next while p 2 4已知指针ha和hb分别指向两个单链表的头结点 并且已知两个链表的长度分别为m和n 试写一算法 将这两个链表连接在一起 即令其中一个表的首元结点连在另一个表的最后一个结点之后 假设指针hc指向连接后的链表的头结点 并要求算法以尽可能短的时间完成连接运算 请分析你的算法的时间复杂度 Connect LinkList ha LinkList hb LinkList hc intm intn 根据给定的两个链表的长度选择较短的链表并找到其尾结点 LinkList p q if mnext p p next p next q next free q 释放头结点ha hb NULL 时间复杂度T n O min m n 题2 5 删除有序表中所有其值大于mink且小于maxk的数据元素 首先分析需要删除的结点的特点 mink maxk pre q p 修改指针 pre next p 释放结点 while q p s q next free q q s voiddelete LinkList L intmink intmaxk delete while p 查找第一个值 mink的结点 if p if q pre next pre next p 修改指针 while q p s q next deleteq q s 释放结点空间 p L next while p 查找第一个值 maxk的结点 返回 2 6试写一算法 对单链表实现就地逆置 即利用原表的存储空间将线性表 a1 a2 an 逆置为 an an 1 a1 voidinvert LinkList head LinkList p q r p head q p next while q NULL 当L没用后续节点时终止 r q next q next p p q q r 实现指针后移head next NULL head p p指向L的最后一个结点 现改为头结点 2 7假设某个单向循环链表的长度大于1 且表中既无头结点也无头指针 已知s为指向链表中某个结点的指针 试编写算法在链表中删除指针s所指结点的前驱结点 LinkList delnode LinkList s LinkList q r q s while q next s q q next r q while r next q r r next r next s free q 2 8已知有一个单向循环链表 其每个结点中含三个域 prior data和next 其中data为数据域 next为指向后继结点的指针域 prior也为指针域 但它的值为空 NULL 试编写算法将此单向循环链表改为双向循环链表 即使prior成为指向前驱结点的指针域 typedefstructLnode Elemtypedata structLnode next prior structLinkList trans structLinkList head structLinkList p q p head next q head while p head 依次从左向右通过每个结点 对每个结点置prior值 p prior q p p next q q next head prior q 此时q指向最后一个结点 将第一个结点的prior域指向最后一个结点 return head 3 1写出下列程序段的输出结果 栈的元素类型SElemType为char voidmain StackS charx y InitStack S x c y k Push S x Push S a Push S y Pop S x Push S t Push S x Pop S x Push S s while StackEmpty S Pop S y printf y printf x 按照四则运算加 减 乘 除和幂运算 优先关系的惯例 并仿照教材例3 2的格式 画出对下列算术表达式求值时操作数栈和运算符栈的变化过程 A B C D E F 写出下列程序段的输出结果 队列中的元素类型QElemType为char voidmain QueueQ InitQueue Q Charx e y c EnQueue Q h EnQueue Q r EnQueue Q y DeQueue Q x EnQueue Q