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

．[题目分析] 单链表中查找任何结点都必须从头指针开始本题要求将指针p所指结点与其后继结点交换这不仅要求知道p结点还应知道p的前驱结点这样才能在p与其后继结点交换后由原p结点的前驱来指向原p结点的后继结点

另外若无特别说明为了处理的方便统一单链表均设头结点链表的指针就是头结点的指针并且由于链表指针具有标记链表的作用也常用指针名冠以链表名称如链表head既指的是链表的名字是head也指出链表的头指针是head

LinkedList Exchange(LinkedList HEADp)∥HEAD是单链表头结点的指针p是链表中的一个结点本算法将p所指结点与其后继结点交换

{q=head>next;∥q是工作指针指向链表中当前待处理结点

pre=head;∥pre是前驱结点指针指向q的前驱

while(q!=null && q!=p){pre=q;q=q>next;}∥未找到p结点后移指针

if(p>next==null)printf(p无后继结点\n);∥p是链表中最后一个结点无后继

else∥处理p和后继结点交换

{q=p>next;∥暂存p的后继

pre>next=q;∥p前驱结点的后继指向p的后继

p>next=q>next;∥p的后继指向原p后继的后继

q>next=p;∥原p后继的后继指针指向p

}

}∥算法结束

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