數據結構考研分類復習真題 第二章 答案[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
　　}
　　}∥算法結束

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23321.html