(单)链表根据《数据结构》这本书 需要会写初始化、插入、查找、删除、取长度的函数。
首先是结构体的定义：
链表的每一个节点由本身的数据、下一个节点的地址组成。
typedef的意思是取别名。把lei这个小名 给int 修改线性表数据类型的时候可以直接改动
1. typedef int lei; 2. struct ss 3. { 4. lei data; 5. ss *next; 6. };
第一个是初始化函数。这里写的是有头指针的链表，所以只需要new一个头结点，让头结点的next指向NULL。
1. ss* chushihua() 2. { 3. ss*L=new ss; 4. L->next=NULL; 5. return L; 6. }
第二个是取长度函数。只要让一个临时指针指向头指针，然后一直遍历下去就好了，最终返回链表的长度。
1. int size(ss* L) 2. { 3. int len=0; 4. while(L->next !=NULL) 5. { 6. L=L->next; 7. len++; 8. } 9. return len; 10. }
第三个是查找函数，根据书的要求，有两种查找函数，其一是根据编号来查找。
可以让L指针一直遍历下去，当L的下一个节点为空节点或者到达所需要的编号停止。
如果这个时候L不为空切cnt==所需要的序号，就说明该节点存在，返回即可；否则返回空指针表示不存在。
1. ss* find_num(ss *L,int xuhao) 2. { 3. int cnt=0; 4. while(L->next!=NULL && cnt<xuhao) 5. { 6. L=L->next; 7. cnt++; 8. } 9. if(cnt==xuhao && L) return L; 10. return NULL; 11. }
其二是根据值查找，这个就比较无脑了，一直遍历下去，直到找到或者找到结尾，如果找到就会返回，没找到也会自然而然的返回空指针。
1. ss* find_data(ss* L,lei data) 2. { 3. L=L->next; 4. while(L && L->data!=data) 5. { 6. L=L->next; 7. } 8. return L; 9. }
第四个是插入函数。先查找这个位置是否可以查，如果存在该位置的前一个为空的情况，就返回错误。
否则new一个新节点，新的节点的下一个指向现在n-1的节点的下一个，让现在n-1的节点指向新的节点,就这样转接完成，返回true。
1. bool charu(ss* L,lei data,int weizhi) 2. { 3. ss *a; 4. ss *b=L; 5. int cnt=0; 6. while(b && cnt < weizhi - 1 ) 7. { 8. b=b->next; 9. cnt++; 10. } 11. if(b==NULL||cnt!=weizhi - 1) 12. { 13. cout<<"插入位置错误"<<endl; 14. return false; 15. } 16. a=new ss; 17. a->data=data; 18. a->next=b->next; 19. b->next=a; 20. return true; 21. }
第五个是删除函数。
先找到需要删除节点的前一个位置，如果发现要删除的节点不存在，则返回false。
如果存在，让删除节点的前一个节点的next指向需要删除节点的next，然后把需要删除的节点释放掉就可以了。
1. bool shanchu(ss *L,int weizhi) 2. { 3. ss *a; 4. ss *b=L; 5. int cnt=0; 6. while(b && cnt<weizhi-1) 7. { 8. b=b->next; 9. cnt++; 10. } 11. if(b==NULL ||b->next == NULL|| cnt!=weizhi - 1) 12. { 13. cout<<"删除错误"<<endl; 14. return false; 15. } 16. a=b->next; 17. b->next = a->next; 18. free(a); 19. return true; 20. }
接下来是全部代码：
1. #include<iostream> 2. #include<algorithm> 3. #include<cstring> 4. using namespace std; 5. typedef int lei; 6. struct ss 7. { 8. lei data; 9. ss *next; 10. }; 11. ss* chushihua() 12. { 13. ss*L=new ss; 14. L->next=NULL; 15. return L; 16. } 17. int size(ss* L) 18. { 19. int len=0; 20. while(L->next !=NULL) 21. { 22. L=L->next; 23. len++; 24. } 25. return len; 26. } 27. ss* find_num(ss *L,int xuhao) 28. { 29. int cnt=0; 30. while(L->next!=NULL && cnt<xuhao) 31. { 32. L=L->next; 33. cnt++; 34. } 35. if(cnt==xuhao && L) return L; 36. return NULL; 37. } 38. ss* find_data(ss* L,lei data) 39. { 40. L=L->next; 41. while(L && L->data!=data) 42. { 43. L=L->next; 44. } 45. return L; 46. } 47. bool charu(ss* L,lei data,int weizhi) 48. { 49. ss *a; 50. ss *b=L; 51. int cnt=0; 52. while(b && cnt < weizhi - 1 ) 53. { 54. b=b->next; 55. cnt++; 56. } 57. if(b==NULL||cnt!=weizhi - 1) 58. { 59. cout<<"插入位置错误"<<endl; 60. return false; 61. } 62. a=new ss; 63. a->data=data; 64. a->next=b->next; 65. b->next=a; 66. return true; 67. } 68. bool shanchu(ss *L,int weizhi) 69. { 70. ss *a; 71. ss *b=L; 72. int cnt=0; 73. while(b && cnt<weizhi-1) 74. { 75. b=b->next; 76. cnt++; 77. } 78. if(b==NULL ||b->next == NULL|| cnt!=weizhi - 1) 79. { 80. cout<<"删除错误"<<endl; 81. return false; 82. } 83. a=b->next; 84. b->next = a->next; 85. free(a); 86. return true; 87. } 88. int main() 89. { 90. ss *L=chushihua(); 91. cout<<"该链表的长度为："<<size(L)<<endl; 92. charu(L,1,1); 93. charu(L,3,2); 94. charu(L,5,3); 95. cout<<"该链表的长度为："<<size(L)<<endl; 96. cout<<"编号为1的元素的地址："<<find_num(L,1)<<endl; 97. cout<<"编号为2的元素的地址："<<find_num(L,2)<<endl; 98. cout<<"值为3的元素的地址 ："<<find_data(L,3)<<endl; 99. cout<<"该链表的长度为："<<size(L)<<endl; 100. cout<<"删除最后一个元素 "<<endl; 101. shanchu(L,3); 102. cout<<"该链表的长度为："<<size(L)<<endl; 103. return 0; 104. }
