C++数据结构之单链表

　　线性表包含 数据域和指针域 其中，data存储数据本身的值，next存储后继元素的地址 下面的图表示的是一个数据节点

10年的杭州网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。成都营销网站建设的优势是能够根据用户设备显示端的尺寸不同，自动调整杭州建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联公司从事“杭州网站设计”,“杭州网站推广”以来，每个客户项目都认真落实执行。

单链表的结构示意图（包括空的单链表）：

单链表的节点类:

 
 
 
 
    
  
  
  
  
  1. 　template  
    2.   
  
  
  
  2. 　　classNode  
    3.   
  
  
  
  3. 　　{  
    4.   
  
  
  
  4. 　　public:  
    5.   
  
  
  
  5. 　　T data;//数据  
    6.   
  
  
  
  6. 　　Node *next;//next指针  
    7.   
  
  
  
  7. 　　Node()  
    8.   
  
  
  
  8. 　　{  
    9.   
  
  
  
  9. 　　this->next=NULL;//构造空的节点  
    10.   
  
  
  
  10. 　　}  
    11.   
  
  
  
  11. 　　Node(T data,Node *next=NULL)//构造一个节点  
    12.   
  
  
  
  12. 　　{  
    13.   
  
  
  
  13. 　　this->data=data;  
    14.   
  
  
  
  14. 　　this->next=next;  
    15.   
  
  
  
  15. 　　}  
    16.   
  
  
  
  16. 　　}; 
    17.

　　单链表类声明如下：

 
 
 
 
    
  
  
  
  
  1. 　　#include  
    2.   
  
  
  
  2. 　　#include "Node.h"//单链表节点类  
    3.   
  
  
  
  3. 　　template  
    4.   
  
  
  
  4. 　　classSinglyLinkedList //单链表类  
    5.   
  
  
  
  5. 　　{  
    6.   
  
  
  
  6. 　　public:  
    7.   
  
  
  
  7. 　　Node *head;//单链表的头指针。  
    8.   
  
  
  
  8. 　　SinglyLinkedList();//构造空的单链表。  
    9.   
  
  
  
  9. 　　SinglyLinkedList(T value[], intn);//构造由指定的数组提供的单链表  
    10.   
  
  
  
  10. 　　~SinglyLinkedList();//析构  
    11.   
  
  
  
  11. 　　boolisEmpty();//判断是否为空。  
    12.   
  
  
  
  12. 　　intlength();//获取长度  
    13.   
  
  
  
  13. 　　Node* getNode(inti);//返回第i(i>=0)个节点指针  
    14.   
  
  
  
  14. 　　T get(inti);//返回第i个元素  
    15.   
  
  
  
  15. 　　boolset(inti,T x);//设置第i个元素为x  
    16.   
  
  
  
  16. 　　template friend std::ostream& operator<<(std::ostream& out,SinglyLinkedList &list);  
    17.   
  
  
  
  17. 　　Node* insert(inti,T x);//插入第I个节点并返回第i个节点的指针  
    18.   
  
  
  
  18. 　　boolremove(inti,T& old);//删除第i个元素，将删除的元素存放到old  
    19.   
  
  
  
  19. 　　voidclear();//清空单链表  
    20.   
  
  
  
  20. 　　voidconcat(SinglyLinkedList &list);//将List链接在当前单链表之后  
    21.   
  
  
  
  21. 　　}; 
    22.

　　单链表部分如构造空的链表对象，析构，判断为空的实现，没有要讲的算法，实现如下：

 
 
 
 
    
  
  
  
  
  1. 　　template  
    2.   
  
  
  
  2. 　　SinglyLinkedList::SinglyLinkedList()//构造空的单链表  
    3.   
  
  
  
  3. 　　{  
    4.   
  
  
  
  4. 　　this->head=NULL;  
    5.   
  
  
  
  5. 　}  
    6.   
  
  
  
  6. 　　template  
    7.   
  
  
  
  7. 　　SinglyLinkedList::~SinglyLinkedList()//析构  
    8.   
  
  
  
  8. 　　{  
    9.   
  
  
  
  9. 　　clear();  
    10.   
  
  
  
  10. 　　}  
    11.   
  
  
  
  11. 　　template  
    12.   
  
  
  
  12. 　　boolSinglyLinkedList::isEmpty()//判断链表是否为空  
    13.   
  
  
  
  13. 　　{  
    14.   
  
  
  
  14. 　　returnthis->head==NULL;  
    15.   
  
  
  
  15. 　　} 
    16.

　　单链表的遍历操作，遍历单链表是指从第一个节点开始访问，沿着节点的Next可依次访问单链表中的各个节点，并且各个节点只被访问一次。实现的单链表遍历的基本算法如下：

 
 
 
 
    
  
  
  
  
  1. 　　intj=0;  
    2.   
  
  
  
  2. 　　Node *p=head;  
    3.   
  
  
  
  3. 　　while(p!=NULL&&j  
  
  
  
  4. 　　{  
    5.   
  
  
  
  5. 　　j++;  
    6.   
  
  
  
  6. 　　p=p->next;  
    7.   
  
  
  
  7. 　　} 
    8.

　　单链表的length(),get(),set(),clear()和输出等操作都基于以上算法。

 
 
 
 
    
  
  
  
  
  1. 　　template  
    2.   
  
  
  
  2. 　　intSinglyLinkedList::length()  
    3.   
  
  
  
  3. 　　{  
    4.   
  
  
  
  4. 　inti=0;  
    5.   
  
  
  
  5. 　　Node *p=head;//创建一个用于遍的变量  
    6.   
  
  
  
  6. 　　while(p!=NULL)  
    7.   
  
  
  
  7. 　　{  
    8.   
  
  
  
  8. 　　i++;  
    9.   
  
  
  
  9. 　　std::cout<data;  
    10.   
  
  
  
  10. 　　p=p->next;  
    11.   
  
  
  
  11. 　　}  
    12.   
  
  
  
  12. 　returni;  
    13.   
  
  
  
  13. 　　}  
    14.   
  
  
  
  14. 　　template  
    15.   
  
  
  
  15. 　　Node* SinglyLinkedList::getNode(inti)  
    16.   
  
  
  
  16. 　　{  
    17.   
  
  
  
  17. 　　if(i<0)  
    18.   
  
  
  
  18. 　　returnNULL;  
    19.   
  
  
  
  19. 　　intj=0;  
    20.   
  
  
  
  20. 　　Node *p=head;  
    21.   
  
  
  
  21. 　　while(p!=NULL&&j  
  
  
  
  22. 　　{  
    23.   
  
  
  
  23. 　　j++;  
    24.   
  
  
  
  24. 　　p=p->next;  
    25.   
  
  
  
  25. 　　}  
    26.   
  
  
  
  26. 　　returnp;  
    27.   
  
  
  
  27. 　　}  
    28.   
  
  
  
  28. 　　template  
    29.   
  
  
  
  29. 　　T SinglyLinkedList::get(inti)  
    30.   
  
  
  
  30. 　　{  
    31.   
  
  
  
  31. 　　Node *p=getNode(i);  
    32.   
  
  
  
  32. 　　if(p!=NULL)  
    33.   
  
  
  
  33. 　　returnp->data;  
    34.   
  
  
  
  34. 　　T d;  
    35.   
  
  
  
  35. 　　returnd;  
    36.   
  
  
  
  36. 　　//throw "单链表为空或者参数指定的元素不存在";  
    37.   
  
  
  
  37. 　　}  
    38.   
  
  
  
  38. 　　template  
    39.   
  
  
  
  39. 　　boolSinglyLinkedList::set(inti,T x)  
    40.   
  
  
  
  40. 　　{  
    41.   
  
  
  
  41. 　　Node *p=getNode(i);  
    42.   
  
  
  
  42. 　　if(p!=NULL)  
    43.   
  
  
  
  43. 　　{  
    44.   
  
  
  
  44. 　　p->data=x;  
    45.   
  
  
  
  45. 　　returntrue;  
    46.   
  
  
  
  46. 　　}  
    47.   
  
  
  
  47. 　　returnfalse;  
    48.   
  
  
  
  48. 　　}  
    49.   
  
  
  
  49. 　　template  
    50.   
  
  
  
  50. 　　std::ostream& operator<<(std::ostream& out,SinglyLinkedList &list)  
    51.   
  
  
  
  51. 　　{  
    52.   
  
  
  
  52. 　　Node *p=list.head;  
    53.   
  
  
  
  53. 　　out<<"(";  
    54.   
  
  
  
  54. 　　while(p!=NULL)  
    55.   
  
  
  
  55. 　　{  
    56.   
  
  
  
  56. 　　out<data;  
    57.   
  
  
  
  57. 　　p=p->next;  
    58.   
  
  
  
  58. 　　if(p!=NULL)  
    59.   
  
  
  
  59. 　　out<<",";  
    60.   
  
  
  
  60. 　　}  
    61.   
  
  
  
  61. 　　out<<") ";  
    62.   
  
  
  
  62. 　　returnout;  
    63.   
  
  
  
  63. 　　}  
    64.   
  
  
  
  64. 　　template  
    65.   
  
  
  
  65. 　　voidSinglyLinkedList::clear()  
    66.   
  
  
  
  66. 　　{  
    67.   
  
  
  
  67. 　　Node *p=head;  
    68.   
  
  
  
  68. 　　while(p!=NULL)  
    69.   
  
  
  
  69. 　　{  
    70.   
  
  
  
  70. 　　Node *q=p;  
    71.   
  
  
  
  71. 　　p=p->next;  
    72.   
  
  
  
  72. 　　delete q;  
    73.   
  
  
  
  73. 　　}  
    74.   
  
  
  
  74. 　　head=NULL;  
    75.   
  
  
  
  75. 　} 
    76.

 　　单链表的插入操作，单链表不像顺序表，对与表的插入和删除很简单：

　　空表插入/头插入

 
 
 
 
    
  
  
  
  
  1. 　　Node *q=NULL;  
    2.   
  
  
  
  2. 　　if(head==NULL||i<0)//头插入(单链表为空或者)  
    3.   
  
  
  
  3. 　　{  
    4.   
  
  
  
  4. 　　q=newNode(x,head);  
    5.   
  
  
  
  5. 　　head=q;  
    6.   
  
  
  
  6. 　　}  
    7.   
  
  
  
  7. 　　中间插入/尾插入  
    8.   
  
  
  
  8. 　　p->next=newNode(x,p->next);  
    9.   
  
  
  
  9. 　　单链表insert()以及参数构造函数：  
    10.   
  
  
  
  10. 　template  
    11.   
  
  
  
  11. 　　Node* SinglyLinkedList::insert(inti,T x)  
    12.   
  
  
  
  12. 　　{  
    13.   
  
  
  
  13. 　　Node *q=NULL;  
    14.   
  
  
  
  14. 　　if(head==NULL||i<0)//头插入(单链表为空或者)  
    15.   
  
  
  
  15. 　　{  
    16.   
  
  
  
  16. 　　q=newNode(x,head);  
    17.   
  
  
  
  17. 　　head=q;  
    18.   
  
  
  
  18. 　　}  
    19.   
  
  
  
  19. 　　else 
    20.   
  
  
  
  20. 　　{  
    21.   
  
  
  
  21. 　　intj=0;  
    22.   
  
  
  
  22. 　　Node *p=head;  
    23.   
  
  
  
  23. 　　while(p->next!=NULL&&j  
  
  
  
  24. 　　{  
    25.   
  
  
  
  25. 　　j++;  
    26.   
  
  
  
  26. 　　p=p->next;  
    27.   
  
  
  
  27. 　　}  
    28.   
  
  
  
  28. 　　q=newNode(x,p->next);  
    29.   
  
  
  
  29. 　p->next=q;  
    30.   
  
  
  
  30. 　　}  
    31.   
  
  
  
  31. 　　returnq;  
    32.   
  
  
  
  32. 　　}  
    33.   
  
  
  
  33. 　template  
    34.   
  
  
  
  34. 　　SinglyLinkedList::SinglyLinkedList(T table[],intn)  
    35.   
  
  
  
  35. 　　{  
    36.   
  
  
  
  36. 　　head=NULL;  
    37.   
  
  
  
  37. 　　if(n>0)  
    38.   
  
  
  
  38. 　　{  
    39.   
  
  
  
  39. 　　head=newNode(table[0]);//创建节点  
    40.   
  
  
  
  40. 　Node *rear=head;//创建一个指向头节点的指针  
    41.   
  
  
  
  41. 　　inti=1;  
    42.   
  
  
  
  42. 　while(i  
  
  
  
  43. 　　{  
    44.   
  
  
  
  44. 　　rear->next=newNode(table[i++]);  
    45.   
  
  
  
  45. 　　rear=rear->next;  
    46.   
  
  
  
  46. 　　}  
    47.   
  
  
  
  47. 　　}  
    48.   
  
  
  
  48. 　　} 
    49.

 　单链表的删除操作也分两类：

　　头删除

 
 
 
 
    
  
  
  
  
  1. 　　Node *q=head;  
    2.   
  
  
  
  2. 　　head=head->next;  
    3.   
  
  
  
  3. 　　delete q; 
    4.

　　中间/尾删除

 
 
 
 
    
  
  
  
  
  1. 　　Node *q=p->next;  
    2.   
  
  
  
  2. 　　if(q!=NULL)//判断删除节点  
    3.   
  
  
  
  3. 　　{  
    4.   
  
  
  
  4. 　　p->next=q->next;//让删除节点的前驱Next指针下一节点  
    5.   
  
  
  
  5. 　　delete q;//删除该节点  
    6.   
  
  
  
  6. 　　} 
    7.

 　　单链表的删除函数remove（）实现：

 
 
 
 
    
  
  
  
  
  1. 　　template  
    2.   
  
  
  
  2. 　　boolSinglyLinkedList::remove(inti,T &old)  
    3.   
  
  
  
  3. 　　{  
    4.   
  
  
  
  4. 　　if(i<0||head==NULL)  
    5.   
  
  
  
  5. 　　{  
    6.   
  
  
  
  6. 　　Node *q=head;  
    7.   
  
  
  
  7. 　　old=q->data;  
    8.   
  
  
  
  8. 　　head=head->next;  
    9.   
  
  
  
  9. 　　delete q;  
    10.   
  
  
  
  10. 　}  
    11.   
  
  
  
  11. 　　else 
    12.   
  
  
  
  12. 　　{  
    13.   
  
  
  
  13. 　　Node *p=getNode(i-1);//获取删除节点的前驱  
    14.   
  
  
  
  14. 　if(p!=NULL&&p->next!=NULL)//判断删除节点和删除节点是否为空  
    15.   
  
  
  
  15. 　　{  
    16.   
  
  
  
  16. 　　Node *q=p->next;//新建一个节点指针，将删除接点复制过去  
    17.   
  
  
  
  17. 　　old=q->data;  
    18.   
  
  
  
  18. 　　p->next=q->next;//让删除节点的前驱Next指针下一节点  
    19.   
  
  
  
  19. 　　delete q;//删除该节点  
    20.   
  
  
  
  20. 　returntrue;  
    21.   
  
  
  
  21. 　　}  
    22.   
  
  
  
  22. 　}  
    23.   
  
  
  
  23. 　　returnfalse;  
    24.   
  
  
  
  24. 　　}  
    25.   
  
  
  
  25. 　　单链表的链接函数：concat()  
    26.   
  
  
  
  26. 　　template  
    27.   
  
  
  
  27. 　　voidSinglyLinkedList::concat(SinglyLinkedList &list)  
    28.   
  
  
  
  28. 　　{  
    29.   
  
  
  
  29. 　　if(this->head==NULL)  
    30.   
  
  
  
  30. 　　{  
    31.   
  
  
  
  31. 　　this->head=list->head;  
    32.   
  
  
  
  32. 　　}  
    33.   
  
  
  
  33. 　　else 
    34.   
  
  
  
  34. 　　{  
    35.   
  
  
  
  35. 　　Node *p=head;  
    36.   
  
  
  
  36. 　　while(p->next!=NULL)  
    37.   
  
  
  
  37. 　　{  
    38.   
  
  
  
  38. 　　p=p->next;  
    39.   
  
  
  
  39. 　　}  
    40.   
  
  
  
  40. 　　p=list->head;  
    41.   
  
  
  
  41. 　　}  
    42.   
  
  
  
  42. 　　list->head=NULL;//设置单链表为空，否则运行出错  
    43.   
  
  
  
  43. 　　} 
    44.

 　　以上对C++单链表的分析 添加一个学生结构和一个测试函数：

 
 
 
 
    
  
  
  
  
  1. 　　Student.h  
    2.   
  
  
  
  2. 　　structStudent  
    3.   
  
  
  
  3. 　　{  
    4.   
  
  
  
  4. 　　charnumber[10]; //学号  
    5.   
  
  
  
  5. 　　charname[20]; //姓名  
    6.   
  
  
  
  6. 　　doublescore; //得分  
    7.   
  
  
  
  7. 　　friend std::ostream& operator<<(std::ostream& out,Student &stu)  
    8.   
  
  
  
  8. 　　{  
    9.   
  
  
  
  9. 　　out<<"学号："<  
  
  
  
  10. 　　returnout;  
    11.   
  
  
  
  11. 　　}  
    12.   
  
  
  
  12. 　　};  
    13.   
  
  
  
  13. 　　主函数：  
    14.   
  
  
  
  14. 　　#include  
    15.   
  
  
  
  15. 　　#include "SinglyLinkedList.h" 
    16.   
  
  
  
  16. 　　#include "Student.h" 
    17.   
  
  
  
  17. 　　void_TestToSinglyLinkedList()  
    18.   
  
  
  
  18. 　　{  
    19.   
  
  
  
  19. 　　Student data[]={{"090313018","Silvester",45.4},{"090313018","捐赠",45.4},{"090313018","版主",45.6}};  
    20.   
  
  
  
  20. 　　SinglyLinkedList m(data,3);  
    21.   
  
  
  
  21. 　　Student t;  
    22.   
  
  
  
  22. 　　std::cout<<(m.isEmpty()?"不为空！":"该链表为空！")<  
  
  
  
  23. 　　std::cout<<"长度："<  
  
  
  
  24. 　　std::cout<<"移除2个学生"<  
  
  
  
  25. 　　std::cout<<"t:"<  
  
  
  
  26. 　　std::cout<<"2个学生信息"<  
  
  
  
  27. 　　Student s={"415646","fdsfs",453.1};  
    28.   
  
  
  
  28. 　　std::cout<  
  
  
  
  29. 　　}  
    30.   
  
  
  
  30. 　　voidmain()  
    31.   
  
  
  
  31. 　{  
    32.   
  
  
  
  32. 　　_TestToSinglyLinkedList();  
    33.   
  
  
  
  33. 　　system("pause");  
    34.   
  
  
  
  34. 　　} 
    35.

　　提供源代码下载地址：http://39327.42la.com.cn/DataFile/Code/C++/SinglyLinkedList.zip

原文地址：http://www.cnblogs.com/Arrays/archive/2012/02/01/2335164.html

当前文章：C++数据结构之单链表
文章来源：http://www.csdahua.cn/qtweb/news1/398451.html

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

广告

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

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

云服务器知识

分类信息网站

诚信建站　　 　成都名片印刷　　 　乐山服务器托管　　 　域名注册　　 　温江网站建设　　 　郫县明安消防器材　　 　h5页面制作　　 　专业网站设计　　 　租用服务器　　 　手机网站建设套餐　　 　成都定制高级网站建设　　 　电子商务商城网站　　 　定制网站　　 　都江堰做网站　　 　梅州网站建设　　 　腾讯香港虚拟主机　　 　雕琢时光　　 　鸿程源茂　　 　成都做网站　　 　Google外贸推广