• 数据结构之单链表（c++（c语言）通用版）

    我们创建一个长度为n的链表时，可以采取头插法创建或者尾插法创建，本篇博客我们采取头插法来创建，（作者只学了头插，尾插等以后来补qwq，补上喽)。

    头插原理

    我们先来画图来看看头插的创建形式把，会了原理再写代码。

    首先是我们的一号和二号节点，我们发现他们是相连的。现在我们使用头插法创建链表要怎么做呢，其实很简单，头插就是把我们新创建的节点放到最前面，我们每次都把创建的节点放到最前面，也就是1好节点的后面。大家注意了，这个一号节点不要存储任何数据或者（这能存储链表的长度信息，）它是我们的头节点。我们创建它只是为了好遍历以后的节点信息。

    看图：

    我们把一号节点的next地址连接到三号节点，三号的next地址连接到2号节点上，这就是头插。

    上代码解释：

    头插详细代码

    1. void InitList(LinkedList a,int n){
    2. 	int e;
    3. 	for(e=0;e
    4. 		Lnode *b=(Lnode*)malloc(sizeof(Lnode));
    5. 		b->a=e;
    6. 		b->next=a->next;
    7. 		a->next=b;
    8. 	}
    9. }
    10. //a号节点是指向节点，我们之后创建的节点都是不断放在a号节点的后面，a号节点只是用来方便遍历。
    11. //我们创建一个b节点，并为他的数据域赋予数值，接着，我们令b号节点链接a号节点链接的节点，并使得a号节点可以连接到b号节点。
    12. //如果是一开始，只有指向a号节点，我们就相当于创建一个尾节点，指向空，令a号节点联系到尾节点

    结构体代码：

    1. typedef struct Lnode{
    2. 	int a;
    3. 	struct Lnode* next;
    4. }Lnode,*LinkedList;//创建结构体，把结构体的别名起为Lnode
    5. //把结构体Lnode的指针起名为LinkedList
    6. //学过Java的同学是不是DNA动了呢qwq

    创建指向节点的代码：

    1. void test(){
    2. 	LinkedList a=(LinkedList)malloc(sizeof(Lnode));//动态开辟空间
    3.  
    4. 	a->next=NULL;//令指向节点的next指向域为NULL
    5. 	int b;
    6. 	cin>>b;//输入链表的长度
    7. 	InitList(a,b);
    8. 	for(int c=0;c//打印验证成果
    9. 		a=a->next;
    10. 		cout<a<
    11. 	}
    12. 	free(a);//释放a的空间
    13. }

    头插总代码详细代码：

    1. #include
    2. using namespace std;
    3. typedef struct Lnode{
    4. 	int a;
    5. 	struct Lnode* next;
    6. }Lnode,*LinkedList;
    7. void InitList(LinkedList a,int n){
    8. 	int e;
    9. 	for(e=0;e
    10. 		Lnode *b=(Lnode*)malloc(sizeof(Lnode));
    11. 		b->a=e;
    12. 		b->next=a->next;
    13. 		a->next=b;
    14. 	}
    15. }
    16. void test(){
    17. 	LinkedList a=(LinkedList)malloc(sizeof(Lnode));
    18. 	a->next=NULL;
    19. 	int b;
    20. 	cin>>b;
    21. 	InitList(a,b);
    22. 	for(int c=0;c
    23. 		a=a->next;
    24. 		cout<a<
    25. 	}
    26. 	free(a);
    27. }
    28. int main(){
    29. test();
    30.  
    31. 	return 0;
    32. }

    运行结果：

    大家可以看到这个6是我输入的，5到0为答案。为什么呢，我们采用头插，会把新创建的节点不断往前安防，而我们赋值又是从0开始，这就使得我们的最后一次赋值5用头插放到最前面了。

    按照约定补上尾插：

    尾插法原理：

    尾插简单多了，顾名思义我们每次都插在最后面即可，别忘记最后一个节点要给他的next域赋值为NULL

    尾插代码：

    1. void creatweicha(LinkedList a,int length){
    2. 	Lnode* b=a;//创建指向节点来作为我们的指向
    3. 	int c=0;
    4. 	for(c=1;c<=2length;c++){///从1开始创建节点
    5. 		Lnode* p=(Lnode*)malloc(sizeof(Lnode));
    6. 		p->shuju=c;//节点存储的值为1到n
    7. 		b->next=p;//让指向节点链接到我们创建的节点上
    8. 		b=p;//同时移动指向节点让其指向我们创建的节点，以方便以后继续尾插
    9. 	}
    10. 	b->next=NULL;//别忘记最后一个节点的next域要赋值为NULL
    11. }

    在单链表中位置n插入一个元素代码

    1. bool LinkedList_L(LinkedList a,int blocation,int c){
    2. 	int d=0;
    3. 	Lnode* p=(Lnode*)malloc(sizeof(Lnode));//动态开辟节点p来寻找查询节点的前驱节点
    4. 	p=a;
    5. 	while(true){
    6. 		d++;//d代表着我们这是第几号节点，节点编号从1号开始
    7. 		p=p->next;//不断使得p节点往后移动
    8. 		if(blocation<=0||p==NULL){//如果位置非法或者插入位置的前驱节点为NULL则代表着不存在前驱
    9. 			return false; //节点，返回false代表无法插入
    10. 		}
    11. 			if(d==blocation-1){
    12. 			break;//如果找到前驱节点那么结束循环
    13. 		}
    14. 	}
    15. 	Lnode* n=(Lnode*)malloc(sizeof(Lnode));
    16. 	n->shuju=c;//创建节点，并赋予其初始值
    17. 	n->next=p->next;//插入节点链接后面的节点
    18. 	p->next=n;//链接前驱节点
    19. 	return true;
    20. 	
    21. }

    附带插入函数的头插建立单链表附带验证的总代码：

    1. #include
    2. using namespace std;
    3. typedef struct Lnode{
    4. 	int shuju;
    5. 	struct Lnode* next;
    6. }Lnode,*LinkedList;
    7. void InitList(LinkedList a,int b){
    8. 	int c;
    9. 	for(c=1;c<=b;c++){
    10. 		Lnode* p=(Lnode*)malloc(sizeof(Lnode));
    11. 		p->shuju=c;
    12. 		p->next=a->next;
    13. 		a->next=p;
    14. 	}
    15. }
    16. bool LinkedList_L(LinkedList a,int blocation,int c){
    17. 	int d=0;
    18. 	Lnode* p=(Lnode*)malloc(sizeof(Lnode));
    19. 	p=a;
    20. 	while(true){
    21. 		d++;
    22. 		p=p->next;
    23. 		if(blocation<=0||p==NULL){
    24. 			return false; 
    25. 		}
    26. 			if(d==blocation-1){
    27. 			break;
    28. 		}
    29. 	}
    30. 	Lnode* n=(Lnode*)malloc(sizeof(Lnode));
    31. 	n->shuju=c;
    32. 	n->next=p->next;
    33. 	p->next=n;
    34. 	return true;
    35. 	
    36. }
    37. void testtoucha(){
    38. 	LinkedList a=(LinkedList)malloc(sizeof(Lnode));
    39. 	a->next=NULL;
    40. 	int b;
    41. 	cin>>b;
    42. 	InitList(a,b);
    43. 	Lnode* a1=a;
    44. 	for(int c=0;c
    45. 		a1=a1->next;
    46. 		cout<shuju<
    47. 	}
    48. 	cout<<"--------------------------------------"<
    49. 	LinkedList_L(a,3,100);
    50. 	Lnode* b1=a;
    51. 	while(true){
    52. 		b1=b1->next;
    53. 		if(b1==NULL){
    54. 			break;
    55. 		}
    56. 		else{
    57. 			cout<shuju<
    58. 		}
    59. 	}
    60. 	free(a);
    61. }
    62. int main(){
    63. 	testtoucha();
    64. 	return 0;
    65. }

    我们可以看到，我们头插创建十个节点，在第三个节点处插入数值为100的节点。

    删除指定位置的节点

    1. bool shanchu(LinkedList a,int b){
    2. 	Lnode* c=a;//创建节点，并把指向节点给与其
    3. 	int d=0;
    4. 	while(true){
    5. 		c=c->next;//不断往后移动节点
    6. 		d++;//记录这是第几个节点，下表从1开始
    7. 		if(b<=0||c==NULL){//如果删除位置不合法，或者要删除的位置的前驱为空，直接返回删除失败
    8. 			return false;
    9. 		}
    10. 		if(d==b-1){
    11. 			break;//找到合法的前驱节点，结束循环
    12. 		}
    13. 	}
    14. 	Lnode* m=c->next;//定义节点m来确定删除的节点
    15. 	if(m==NULL){
    16. 		return true;//如果m已经为NULL那么就不用管了。
    17. 	}
    18. 	else{//不为空，则删除节点m
    19. 		c->next=m->next;
    20. 		free(m);
    21. 		return true;
    22. 	}
    23. }

    带有删除节点函数的尾插创建的单链表验证：

    1. #include
    2. using namespace std;
    3. typedef struct Lnode{
    4. 	int shuju;
    5. 	struct Lnode* next;
    6. }Lnode,*LinkedList;
    7. bool shanchu(LinkedList a,int b){
    8. 	Lnode* c=a;
    9. 	int d=0;
    10. 	while(true){
    11. 		c=c->next;
    12. 		d++;
    13. 		if(b<=0||c==NULL){
    14. 			return false;
    15. 		}
    16. 		if(d==b-1){
    17. 			break;
    18. 		}
    19. 	}
    20. 	Lnode* m=c->next;
    21. 	if(m==NULL){
    22. 		return true;
    23. 	}
    24. 	else{
    25. 		c->next=m->next;
    26. 		free(m);
    27. 		return true;
    28. 	}
    29. }
    30. void creatweicha(LinkedList a,int length){
    31. 	Lnode* b=a;
    32. 	int c=0;
    33. 	for(c=1;c<=2length;c++){
    34. 		Lnode* p=(Lnode*)malloc(sizeof(Lnode));
    35. 		p->shuju=c;
    36. 		b->next=p;
    37. 		b=p;
    38. 	}
    39. 	b->next=NULL;
    40. }
    41. void test(){
    42. 	LinkedList a=(LinkedList)malloc(sizeof(Lnode));
    43. 	a->next=NULL;
    44. 	int c;
    45. 	cin>>c;
    46. 	creatweicha(a,c);
    47. 	Lnode* p=a;
    48. 	while(true){
    49. 		p=p->next;
    50. 		if(p!=NULL){
    51. 			cout<shuju<
    52. 		}
    53. 		else{
    54. 			break;
    55. 		}
    56. 	}
    57. 	cout<<"AAAAAAA"<
    58. 	shanchu(a,3);
    59. 	Lnode* p1=a;
    60. 	while(true){
    61. 		p1=p1->next;
    62. 		if(p1!=NULL){
    63. 			cout<shuju<
    64. 		}
    65. 	  else{
    66. 	  	break;
    67. 	  }
    68. 	}
    69. 	free(a);
    70. 	
    71. }
    72. int main(){
    73. 	test();
    74. 	return 0;
    75. }

    可以看到我们创建了9个节点，成功删除了第三号节点。

    一点小更正：

    如果大家要单独写初始化函数的化，那么初始化函数就必须要加引用：

    带初始化函数的尾插法：

    1. #include
    2. using namespace std;
    3. typedef struct Lnode{
    4. 	int shuju;
    5. 	struct Lnode* next;
    6. }Lnode,*LinkedList;
    7. bool shanchu(LinkedList a,int b){
    8. 	Lnode* c=a;
    9. 	int d=0;
    10. 	while(true){
    11. 		c=c->next;
    12. 		d++;
    13. 		if(b<=0||c==NULL){
    14. 			return false;
    15. 		}
    16. 		if(d==b-1){
    17. 			break;
    18. 		}
    19. 	}
    20. 	Lnode* m=c->next;
    21. 	if(m==NULL){
    22. 		return true;
    23. 	}
    24. 	else{
    25. 		c->next=m->next;
    26. 		free(m);
    27. 		return true;
    28. 	}
    29. }
    30. void creatweicha(LinkedList a,int length){
    31. 	Lnode* b=a;
    32. 	int c=0;
    33. 	for(c=1;c<=length;c++){
    34. 		Lnode* p=(Lnode*)malloc(sizeof(Lnode));
    35. 		p->shuju=c;
    36. 		b->next=p;
    37. 		b=p;
    38. 	}
    39. 	b->next=NULL;
    40. }
    41. void chushihua(LinkedList &a){//加引用，不然初始化失败
    42. 	a=(LinkedList)malloc(sizeof(Lnode));
    43. 	a->next=NULL;
    44. 	
    45. }
    46. void test(){
    47.  
    48. 	
    49. 		LinkedList a;
    50. 		 chushihua(a);//=(LinkedList)malloc(sizeof(Lnode));
    51. 		//a->next=NULL;
    52. 	int c;
    53. 	cin>>c;
    54. 	creatweicha(a,c);
    55. 	Lnode* p=a;
    56. 	while(true){
    57. 		p=p->next;
    58. 		if(p!=NULL){
    59. 			cout<shuju<
    60. 		}
    61. 		else{
    62. 			break;
    63. 		}
    64. 	}
    65. 	cout<<"AAAAAAA"<
    66. 	shanchu(a,3);
    67. 	Lnode* p1=a;
    68. 	while(true){
    69. 		p1=p1->next;
    70. 		if(p1!=NULL){
    71. 			cout<shuju<
    72. 		}
    73. 	  else{
    74. 	  	break;
    75. 	  }
    76. 	}
    77. 	free(a);
    78. 	
    79. }
    80. int main(){
    81. 	test();
    82. 	return 0;
    83. }

    头插亦同理

    1. #include
    2. using namespace std;
    3. typedef struct Lnode{
    4. 	int a;
    5. 	struct Lnode* next;
    6. }Lnode,*LinkedList;
    7. void InitList(LinkedList a,int n){
    8. 	int e;
    9. 	for(e=0;e
    10. 		Lnode *b=(Lnode*)malloc(sizeof(Lnode));
    11. 		b->a=e;
    12. 		b->next=a->next;
    13. 		a->next=b;
    14. 	}
    15. }
    16. void chushihua(LinkedList &a){
    17. 	a=(LinkedList)malloc(sizeof(Lnode));
    18. 	a->next=NULL;
    19. }
    20. void test(){
    21. 	LinkedList a;
    22. 	chushihua(a);//=(LinkedList)malloc(sizeof(Lnode));
    23. 	//a->next=NULL;
    24. 	int b;
    25. 	cin>>b;
    26. 	InitList(a,b);
    27. 	for(int c=0;c
    28. 		a=a->next;
    29. 		cout<a<
    30. 	}
    31. 	free(a);
    32. }
    33. int main(){
    34. test();
    35.  
    36. 	return 0;
    37. }

  • 相关阅读:
    【iOS开发】——Category底层原理、Extension、关联对象
    自媒体写作，怎么写出让人看了就想点击的标题呢？
    【师兄啊师兄2】公布，李长寿成功渡劫，敖乙叛变，又一美女登场
    Spring Cloud 与dubbo微服务架构选型
    机器学习:在线学习和离线学习区别
    如何与斯堪尼亚SCANIA建立EDI连接？
    设计模式 实践案例
    day26 java Stream
    Camera2开发基础知识篇——手机影像参数
    net-java-php-python-健身俱乐部管理系统计算机毕业设计程序
  • 原文地址：https://blog.csdn.net/m0_73862548/article/details/132723825