第4章数据结构习题讲解.ppt

4 1 4 1 算法reverse head 将指针head所指向的链表倒置 RV1 指针初始化 P1 head P2分别指向三个连续的节点P1 NULL P2 next head RV2 反转链表 WHILE P2 NULL DO next head P1 反转节点指针P1 head head P2 P2 next P2 移动3个指针 4 3 编写一个函数SelectItem Stack s intn 要求利用堆栈来查找n在栈中第一次出现的位置 并将该位置元素移至栈顶 同时其他元素次序不变 注意 用int匹配堆栈的模板 解题思路 对s进行弹栈操作 然后匹配弹出元素 找到 或无法找到 后能够恢复原来的元素次序要能够恢复原来的元素次序关键在于记录弹出的顺序后弹出的元素能够先被压回原来的栈s因此需要使用一个辅助堆栈 算法思想示例 n 51 4 3 算法SelectItem s n t s2 在堆栈s中查找值为n的元素的位置 返回值t是值为n的元素在s中第一次出现的位置 如果找不到返回 1 s2为将该元素移到栈顶后的栈 SI1 堆栈为空 IFtop 1THEN PRINT anemptystack RETURN top1 1 4 3 SI2 在s中查找n top为s的栈顶指针 top1是temp的栈顶指针WHILE top 1ANDs top n DO 将s中的元素弹出 压入堆栈temp中top1 top1 1 temp top1 s top top top 1 4 3 SI3 如果找到 弹栈并记录位置 IF top 1 THEN t top top top 1 SI4 恢复原有元素顺序 WHILE top1 1 DO top top 1 s top temp top1 top1 top1 1 IF t 1 THEN top top 1 s top n 关于栈的操作CREATS S 建立一个堆栈S 判断堆栈S是否空 ISEMTS S S x 元素x进栈 x S 元素x出栈 Peek S t 查看栈S的栈顶元素 赋值给t 但不弹栈 4 3 算法SelectItem s n t s 在堆栈s中查找值为n的元素位置 返回值t是值为n的元素在s中第一次出现的位置 如果找不到返回 1 s为将该元素移到栈顶后的栈 SI1 堆栈为空 IFISEMTS s THEN PRINT anemptystack RETURN SI2 初始化 CREATS ss count 0 SI3 在s中查找n Peek s temp WHILE NOTISEMTS s ANDtemp n DO 将s中的元素弹出 压入堆栈ss中x s ss x Peek s temp 4 3 4 3 SI4 如果未找到 t值赋为 1 IF ISEMTS s THENt 1 ELSE t 0 temp s SI5 恢复原有元素顺序 WHILE NOTISEMTS ss DO x ss s x count count 1 IF t 1 THEN s temp t t count t记录与n匹配元素距离栈顶的位置 4 11 要求设计一个算法InsertOrder Cnode header Cnode elem 将结点elem插入到一个循环链表中 并将链表中的结点按照data的递增次序重新排列 解题思路 从头结点开始 在链表中查找数据域值最大的结点 将其从原来的位置上删除之 并将其插入哨位结点之后 在剩余的链表中重复上述操作 若干次之后 链表即有序 也可以使用简单插入排序的思想 4 11 算法InsertOrder header elem header IO1 表头结点后插入elem结点 temp next header next elem temp next header elem 4 11 IO2 排序处理 q next header IFnext q headerTHENRETURN 只包含一个结点 4 11 WHILE next q header DO FindDeleteMaxNode header q maxnodep 在以header为头结点的循环链表中 从q结点开始寻找局部链表中数据域值最大的结点 并将该结点从链表中原来的位置删除 由指针maxnodep返回 InsertBehindHeader header maxnodep 将该结点插入到哨位结点之后 中缀表达式转化后缀表达式 算法CINFIX E P 转换中缀表达式为后缀表达式 中缀表达式存储在数组E 1 n 中 相应的后缀表达式存储在数组P 1 m 中 CF1 初始化 CREATS S 建立堆栈S 是栈底标志j 0 输出序列指针i 0 输入串指针 CF2 进行处理 WHILETOP S DO i i 1 IFISOPD E i THEN j j 1 P j E i IFE i THENS E i IFE i