第4章 习题讲解.pptVIP

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 ， int n ） ，要求利用堆栈来查找n在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用int匹配堆栈的模板） 解题思路： 对 s 进行弹栈操作，然后匹配弹出元素。 找到（或无法找到）后能够恢复原来的元素次序 要能够恢复原来的元素次序关键在于记录弹出的顺序后弹出的元素能够先被压回原来的栈 s 因此需要使用一个辅助堆栈 算法思想示例： n = 51 4-3 算法 SelectItem(s , n . t , s2) /* 在堆栈 s 中查找值为 n 的元素的位置，返回值 t是值为 n 的元素在 s 中第一次出现的位置，如果找不到返回-1, s2 为将该元素移到栈顶后的栈 */ SI1[堆栈为空 ？] IF top = ?1 THEN （  PRINT “an empty stack! ”. RETURN. ） top1 ? -1. 4-3 SI2[在 s 中查找 n ] //top 为 s 的栈顶指针，top1是temp的栈顶指针 WHILE ( top≠-1 AND s.[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[堆栈为空 ？] IF ISEMTS(s) THEN （ PRINT “an empty stack! ”. RETURN. ） SI2[初始化] CREATS(ss). count ? 0. 4-3 SI3[在 s 中查找 n ] Peek(s.temp) . WHILE (NOT ISEMTS(s) AND temp ≠ n ) DO ( //将s中的元素弹出，压入堆栈ss中 x ? s. ss ? x. Peek(s.temp) . ) 4-3 SI4[如果未找到，t值赋为-1] IF（ ISEMTS(s) ）THEN t ? -1. ELSE （t ?0. temp ? s ). SI5[恢复原有元素顺序] WHILE (NOT ISEMTS(ss) ) DO ( x ? ss. s ? x. count ? count+1. ) IF（ t ≠ -1 ）THEN （s ? temp. t ?t+count). // t记录与n匹配元素距离栈顶的位置 ▌ 4-11 要求设计一个算法InsertOrder(CnodeT * header, CnodeT* elem)，将结点elem插入到一个循环链表中，并将链表中的结点按照data的递增次序重新排列。 解题思路： 从头结点开始，在链表中查找数据域值最大的结点，将其从原来的位置上删除之，并将其插入哨位结点之后。