对C++链表进行解读分析

C++语言是学习数据结构的很好的学习工具，能够全面的理解了C++中C++链表的作用和用途，那么对于理解其C++描述，Java描述都就轻而易举了，以后学习什么语言都不会觉得难了。

单链表的交换节点的含义是：给定一个单链表，要求交换其中的任意两个节点。注意这里链表的头节点是不参与节点交换的。这个看上去是比较简单，但是实现起来却还是需要一定的基本功。

对于这个问题，关键是要用4个指针来保存两个交换的节点的前后节点位置，具体实现请参见实现源码。实际上，还有一个逻辑更加清晰的实现：只要用两个指针保存当前的两个交换节点的前一个节点。#t#

然后依次删除待交换节点，再在记录的前一个节点后交替插入删除的两个节点，也就是实际上将这个过程转化为了对于C++链表的两个基本操作就可以完成了。但是要注意的是，这个实现中当两个交换节点是相邻节点的时候会出现问题，要单独处理，具体原因手工操作一次即可得知。后一种方法这里就不给出了。

实现代码中要说明的是，交换C++链表节点传入的是两个交换节点指针，但是为了测试简单实现，将这两个节点换成了待交换节点的关键字（值域），再到C++链表中定位。

具体实现源码为：

 
 
 
    
  
  
  
  1. //Link.h  
    2. 
  
  
  
  2. 　　#include  
    3. 
  
  
  
  3. 　　#include  
    4. 
  
  
  
  4. 　　struct Node  
    5. 
  
  
  
  5. 　　{  
    6. 
  
  
  
  6. 　　public:  
    7. 
  
  
  
  7. 　　Node():_val(0),_next(NULL)  
    8. 
  
  
  
  8. 　　{  
    9. 
  
  
  
  9. 　　}  
    10. 
  
  
  
  10. 　　Node(int val):_val(val),_next(NULL)  
    11. 
  
  
  
  11. 　　{  
    12. 
  
  
  
  12. 　　}  
    13. 
  
  
  
  13. 　　Node(int val,Node* next):_val(val),_next(next)  
    14. 
  
  
  
  14. 　　{  
    15. 
  
  
  
  15. 　　}  
    16. 
  
  
  
  16. 　　~Node()  
    17. 
  
  
  
  17. 　　{  
    18. 
  
  
  
  18. 　　if (_next)  
    19. 
  
  
  
  19. 　　delete _next;  
    20. 
  
  
  
  20. 　　}  
    21. 
  
  
  
  21. 　　public:  
    22. 
  
  
  
  22. 　　int _val;  
    23. 
  
  
  
  23. 　　Node* _next;  
    24. 
  
  
  
  24. 　　};  
    25. 
  
  
  
  25. 　　typedef Node* LinkNode;  
    26. 
  
  
  
  26. 　　Node* CreateLink(int len,int MAX_BOUND = 100)  
    27. 
  
  
  
  27. 　　{  
    28. 
  
  
  
  28. 　　srand((unsigned int)time(NULL));  
    29. 
  
  
  
  29. 　　LinkNode head = new Node(-1);  
    30. 
  
  
  
  30. 　　LinkNode tmp = head;  
    31. 
  
  
  
  31. 　　for (int i = 0; i < len; ++i)  
    32. 
  
  
  
  32. 　　{  
    33. 
  
  
  
  33. 　　//tmptmp = tmp->_next = new Node(rand() % MAX_BOUND);  
    34. 
  
  
  
  34. 　　tmptmp = tmp->_next = new Node(i);  
    35. 
  
  
  
  35. 　　}  
    36. 
  
  
  
  36. 　　tmp->_next = NULL;  
    37. 
  
  
  
  37. 　　return head;  
    38. 
  
  
  
  38. 　　}  
    39. 
  
  
  
  39. 　　void ExchLinkNode (const LinkNode head,int i1,int i2)  
    40. 
  
  
  
  40. 　　{  
    41. 
  
  
  
  41. 　　//head不准被交换  
    42. 
  
  
  
  42. 　　LinkNode prenode1 = NULL;  //保存待交换节点node1的前一个节点  
    43. 
  
  
  
  43. 　　LinkNode postnode1 = NULL; //保存待交换节点node1的后一个节点  
    44. 
  
  
  
  44. 　　LinkNode prenode2 = NULL;  //保存待交换节点node2的前一个节点  
    45. 
  
  
  
  45. 　　LinkNode postnode2 = NULL; //保存待交换节点node2的后一个节点  
    46. 
  
  
  
  46. 　　LinkNode node1 = NULL;     //保存待交换的节点  
    47. 
  
  
  
  47. 　　LinkNode node2 = NULL;     //保存待交换的节点  
    48. 
  
  
  
  48. 　　LinkNode tmp = head;  
    49. 
  
  
  
  49. 　　//定位两个节点  
    50. 
  
  
  
  50. 　　while ((tmp->_val != i1) && (tmp != NULL))  
    51. 
  
  
  
  51. 　　{  
    52. 
  
  
  
  52. 　　tmptmp = tmp->_next;  
    53. 
  
  
  
  53. 　　}  
    54. 
  
  
  
  54. 　　if (tmp == NULL)  
    55. 
  
  
  
  55. 　　{  
    56. 
  
  
  
  56. 　　return ;  
    57. 
  
  
  
  57. 　　}  
    58. 
  
  
  
  58. 　　else  
    59. 
  
  
  
  59. 　　{  
    60. 
  
  
  
  60. 　　node1 = tmp;  
    61. 
  
  
  
  61. 　　}  
    62. 
  
  
  
  62. 　　tmp = head;  
    63. 
  
  
  
  63. 　　while ((tmp->_val != i2) && (tmp != NULL))  
    64. 
  
  
  
  64. 　　{  
    65. 
  
  
  
  65. 　　tmptmp = tmp->_next;  
    66. 
  
  
  
  66. 　　}  
    67. 
  
  
  
  67. 　　if (tmp == NULL)  
    68. 
  
  
  
  68. 　　{  
    69. 
  
  
  
  69. 　　return ;  
    70. 
  
  
  
  70. 　　}  
    71. 
  
  
  
  71. 　　else  
    72. 
  
  
  
  72. 　　{  
    73. 
  
  
  
  73. 　　node2 = tmp;  
    74. 
  
  
  
  74. 　　}  
    75. 
  
  
  
  75. 　　//不得和头节点交换  
    76. 
  
  
  
  76. 　　if (node1 == head)  
    77. 
  
  
  
  77. 　　{  
    78. 
  
  
  
  78. 　　return ;  
    79. 
  
  
  
  79. 　　}  
    80. 
  
  
  
  80. 　　else if (node2 == head)  
    81. 
  
  
  
  81. 　　{  
    82. 
  
  
  
  82. 　　return ;  
    83. 
  
  
  
  83. 　　}  
    84. 
  
  
  
  84. 　　//自己和自己就不必交换了  
    85. 
  
  
  
  85. 　　if (node1 == node2)  
    86. 
  
  
  
  86. 　　{  
    87. 
  
  
  
  87. 　　return ;  
    88. 
  
  
  
  88. 　　}  
    89. 
  
  
  
  89. 　　tmp = head;  
    90. 
  
  
  
  90. 　　while (tmp->_next != node1)  
    91. 
  
  
  
  91. 　　{  
    92. 
  
  
  
  92. 　　tmptmp = tmp->_next;  
    93. 
  
  
  
  93. 　　}  
    94. 
  
  
  
  94. 　　prenode1 = tmp;  
    95. 
  
  
  
  95. 　　tmp = head;  
    96. 
  
  
  
  96. 　　while (tmp->_next != node2)  
    97. 
  
  
  
  97. 　　{  
    98. 
  
  
  
  98. 　　tmptmp = tmp->_next;  
    99. 
  
  
  
  99. 　　} 
    100.

分享文章：对C++链表进行解读分析
文章网址：http://www.csdahua.cn/qtweb/news36/310836.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

标签优化知识

同城分类信息

成都网站改版　　 　重庆网站制作　　 　成都网络公司　　 　手提袋印刷制作　　 　南充网站建设　　 　校园网站建设方案　　 　网站方案　　 　艾瑞格衣柜　　 　网络推广公司　　 　成都网站设计　　 　雅安电信机房　　 　芦山网站建设　　 　高端网站建设　　 　子晨包装　　 　光华服务器托管　　 　成都做网站　　 　网站开发　　 　高端网站策划　　 　成都木托盘　　 　圣月阀门