對C++鏈表進行解讀分析

C++語言是學習數據結構的很好的學習工具，能夠全面的理解了C++中C++鏈表的作用和用途，那麼對於理解其C++描述，Java描述都就輕而易舉了，以後學習什麼語言都不會覺得難了。

單鏈表的交換節點的含義是：給定一個單鏈表，要求交換其中的任意兩個節點。注意這裡鏈表的頭節點是不參與節點交換的。這個看上去是比較簡單，但是實現起來卻還是需要一定的基本功。

對於這個問題，關鍵是要用4個指針來保存兩個交換的節點的前後節點位置，具體實現請參見實現源碼。實際上，還有一個邏輯更加清晰的實現：只要用兩個指針保存當前的兩個交換節點的前一個節點。

• 對C++的設計原則介紹
• 對C++手冊內容簡介
• 深度剖析C++標准程序庫說明
• 如何使C++進行C++開發程序？
• 如何定義C++構造函數

然後依次刪除待交換節點，再在記錄的前一個節點後交替插入刪除的兩個節點，也就是實際上將這個過程轉化為了對於C++鏈表的兩個基本操作就可以完成了。但是要注意的是，這個實現中當兩個交換節點是相鄰節點的時候會出現問題，要單獨處理，具體原因手工操作一次即可得知。後一種方法這裡就不給出了。

實現代碼中要說明的是，交換C++鏈表節點傳入的是兩個交換節點指針，但是為了測試簡單實現，將這兩個節點換成了待交換節點的關鍵字值域），再到C++鏈表中定位。

具體實現源碼為：

//Link.h  
#include <iostream> 
#include <ctime> 
struct Node  
{  
public:  
Node():_val(0),_next(NULL)  
{  
}  
Node(int val):_val(val),_next(NULL)  
{  
}  
Node(int val,Node* next):_val(val),_next(next)  
{  
}  
~Node()  
{  
if (_next)  
delete _next;  
}  
public:  
int _val;  
Node* _next;  
};  
typedef Node* LinkNode;  
Node* CreateLink(int len,int MAX_BOUND = 100)  
{  
srand((unsigned int)time(NULL));  
LinkNode head = new Node(-1);  
LinkNode tmp = head;  
for (int i = 0; i < len; ++i)  
{  
//tmptmp = tmp->_next = new Node(rand() % MAX_BOUND);  
tmptmp = tmp->_next = new Node(i);  
}  
tmp->_next = NULL;  
return head;  
}  
void ExchLinkNode (const LinkNode head,int i1,int i2)  
{  
//head不准被交換  
LinkNode prenode1 = NULL;  //保存待交換節點node1的前一個節點  
LinkNode postnode1 = NULL; //保存待交換節點node1的後一個節點  
LinkNode prenode2 = NULL;  //保存待交換節點node2的前一個節點  
LinkNode postnode2 = NULL; //保存待交換節點node2的後一個節點  
LinkNode node1 = NULL;     //保存待交換的節點  
LinkNode node2 = NULL;     //保存待交換的節點  
LinkNode tmp = head;  
//定位兩個節點  
while ((tmp->_val != i1) && (tmp != NULL))  
{  
tmptmp = tmp->_next;  
}  
if (tmp == NULL)  
{  
return ;  
}  
else  
{  
node1 = tmp;  
}  
tmp = head;  
while ((tmp->_val != i2) && (tmp != NULL))  
{  
tmptmp = tmp->_next;  
}  
if (tmp == NULL)  
{  
return ;  
}  
else  
{  
node2 = tmp;  
}  
//不得和頭節點交換  
if (node1 == head)  
{  
return ;  
}  
else if (node2 == head)  
{  
return ;  
}  
//自己和自己就不必交換了  
if (node1 == node2)  
{  
return ;  
}  
tmp = head;  
while (tmp->_next != node1)  
{  
tmptmp = tmp->_next;  
}  
prenode1 = tmp;  
tmp = head;  
while (tmp->_next != node2)  
{  
tmptmp = tmp->_next;  
}