建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
對C++鏈表進行解讀分析
C++語言是學習數(shù)據(jù)結構的很好的學習工具，能夠全面的理解了C++中C++鏈表的作用和用途，那么對于理解其C++描述，Java描述都就輕而易舉了，以后學習什么語言都不會覺得難了。
單鏈表的交換節(jié)點的含義是：給定一個單鏈表，要求交換其中的任意兩個節(jié)點。注意這里鏈表的頭節(jié)點是不參與節(jié)點交換的。這個看上去是比較簡單，但是實現(xiàn)起來卻還是需要一定的基本功。
對于這個問題，關鍵是要用4個指針來保存兩個交換的節(jié)點的前后節(jié)點位置，具體實現(xiàn)請參見實現(xiàn)源碼。實際上，還有一個邏輯更加清晰的實現(xiàn)：只要用兩個指針保存當前的兩個交換節(jié)點的前一個節(jié)點。#t#
然后依次刪除待交換節(jié)點，再在記錄的前一個節(jié)點后交替插入刪除的兩個節(jié)點，也就是實際上將這個過程轉化為了對于C++鏈表的兩個基本操作就可以完成了。但是要注意的是，這個實現(xiàn)中當兩個交換節(jié)點是相鄰節(jié)點的時候會出現(xiàn)問題，要單獨處理，具體原因手工操作一次即可得知。后一種方法這里就不給出了。
實現(xiàn)代碼中要說明的是，交換C++鏈表節(jié)點傳入的是兩個交換節(jié)點指針，但是為了測試簡單實現(xiàn)，將這兩個節(jié)點換成了待交換節(jié)點的關鍵字（值域），再到C++鏈表中定位。
具體實現(xiàn)源碼為：
- //Link.h
- #include
- #include
- 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; //保存待交換節(jié)點node1的前一個節(jié)點
- LinkNode postnode1 = NULL; //保存待交換節(jié)點node1的后一個節(jié)點
- LinkNode prenode2 = NULL; //保存待交換節(jié)點node2的前一個節(jié)點
- LinkNode postnode2 = NULL; //保存待交換節(jié)點node2的后一個節(jié)點
- LinkNode node1 = NULL; //保存待交換的節(jié)點
- LinkNode node2 = NULL; //保存待交換的節(jié)點
- LinkNode tmp = head;
- //定位兩個節(jié)點
- 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;
- }
- //不得和頭節(jié)點交換
- 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;
- }
文章題目：對C++鏈表進行解讀分析
文章源于：http://m.jiaoqi3.com/article/coescph.html
