数据结构考研分类复习真题 第二章 答案[40]

类似本题的另外叙述题的解答

()[题目分析] 本题应先查找第i个结点记下第i个结点的指针然后从第i+个结点起直至第m(<i<m)个结点止依次插入到第i个结点之后最后将暂存的第i个结点的指针指向第m结点形成新的循环链表结束了倒置算法

LinkedList PatternInvert(LinkedList Lint im)∥L是有m个结点的链表的头结点的指针表中从第i(<i<m)个结点到第m个结点构成循环部分链表本算法将这部分循环链表倒置

{if(i<|| i>=m || m<){printf(%d%d参数错误\nim);exit();}

p=L>next>next;∥p是工作指针初始指向第二结点(已假定i>)

pre=L>next;∥pre是前驱结点指针最终指向第i个结点

j=;∥计数器

while(j<i)∥查找第i个结点

{j++;pre=p;p=p>next;}∥查找结束p指向第i个结点

q=p;∥暂存第i个结点的指针

p=p>next;∥p指向第i+个结点准备逆置

j+=;∥上面while循环结束时j=i现从第i+结点开始逆置

while(j<=m)

{r=p>next;∥暂存p的后继结点

p>next=pre>next;∥逆置p结点

pre>next=p;

p=r;∥p恢复为当前待逆置结点

j++;∥计数器增

}

q>next=pre>next;∥将原第i个结点的后继指针指向原第m个结点

[算法讨论] 算法中未深入讨论imj的合法性因题目的条件是m>且<i<m因此控制循环并未用指针判断(如一般情况下的p!=null)结束循环也未用指针判断注意最后一句q>next=pre>next实现了从原第i个结点到原第m个结点的循环最后pre>next正是指向原第m个结点不可用p>next代替pre>next

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []