devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

单链表的定义初始化、CRUD （超详细、完整代码）_初始化单链表代码

作者：神奇cpp | 2024-07-18 15:37:39

赞

踩

初始化单链表代码

一、释意

二、基本操作

1.单链表定义（结构体定义）

2.使用头插法建立单链表（含头结点）

3.使用尾插法建立单链表

4.查找结点（按值查找）

5.查找节点（按序查找）

6.单链表插入（图例）

7.单链表按位序插入（带头结点 ，i表示元素位序）

8.单链表按位序插入（不带头结点 ，i表示元素位序）

9.给定指定节点的后插操作

10.指定节点的前插操作

11.删除结点操作

12.删除结点返回被删除结点的值（按位序删）

13.求单链表表长操作（含头结点）

三、完整代码

一、释意

        1.链表实质就是顺序表的链式表示。相比于顺序表有一些不同。顺序表是用一片地址连续的空间进行存储的 因此具有随机存储的特征（时间复杂度为O(1)），但是链表不同，链表不需要一片地址连续的空间 而是通过链（指针）来将所有元素串起来的。顺序表具有随机存储 但是插入、删除原素需要移动大量元素 而链表就是为了改善增删而定的 但是同时也失去了具有随机存取的特征，并且还需要有一个指针域（存储空间就增大了）。当访问某个元素时 只有通过链依次查找 具体看图例。

                                               

                                                            单链表的结点结构

其中data存放数据（a1...an）next存放下一个元素的地址

顺序表：                                                                         链表：        

        2.通常用头指针来标识一个单链表，头指针为NULL时表示此头指针指向的表示空表。并且通常每个链表都可以定义一个头结点（方便操作），头指针指向头结点。头结点当然也有数据域和指针域，但是头结点的数据域不存放元素 一般用于存放表长等信息，而头结点的指针域就存放第一个元素的地址。 如果所示：

引入头结点可以带来的优点：

1.由于第一个数据结点的位置被存放于头结点的指针域中，因此在链表的第一个位置上的操作和在表的其它位置上的操作一致，无需进行特殊处理

2.无论链表是否为空头指针总是指向头结点的非空指针（此时判定空表的方法是头结点指针是否为空）因此空表和非空表的处理也得到了统一

二、基本操作

1.单链表定义（结构体定义）

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct LNode{  
  4. 	int data;
  5. 	struct LNode *next;  
  6. }LNode,*LinkList;

2.使用头插法建立单链表（含头结点）

时间复杂度为o(n)

  1. //使用头插法建立单链表 （含头结点）
  2. LinkList List_HeadInsert (LinkList &L){ //逆向建立单链表
  3. 	LNode *s;int x;
  4.  	L=(LinkList)malloc(sizeof(LNode)); //创建头结点  ;
  5.  	L->next=NULL;
  6.  	scanf("%d",&x);						//输入第一个结点的值 
  7.  	while(x!=9999){                      //输入9999表示结束 
  8. 		s=(LNode*)malloc(sizeof(LNode));
  9. 		s->data=x;
  10.  		s->next=L->next;
  11.  		L->next=s;
  12.  		scanf("%d",&x);
  13.  	}	
  14. 	return L;
  15. }

        图例：采用头插法建立单链表是每次在头结点之后插入新的结点，因此读入数据的顺序与生成的链表中的元素顺序是相反的。但是它常用于链表逆置

 3.使用尾插法建立单链表

时间复杂度为o(n)

  1. //使用尾插法建立单链表（含头结点） 
  2. LinkList List_TailInsert (LinkList &L){ //逆向建立单链表
  3.  	L=(LinkList)malloc(sizeof(LNode)); 	//创建头结点 ;
  4. 	LNode *s,*r=L;int x; 					//s指向新节点  r指向尾结点 
  5.  	L->next=NULL;
  6.  	scanf("%d",&x);						//输入第一个结点的值 
  7.  	while(x!=9999){                      //输入9999表示结束 
  8. 		s=(LNode*)malloc(sizeof(LNode));
  9. 		s->data=x;
  10.  		r->next=s;
  11.  		r=s;
  12.  		scanf("%d",&x);
  13.  	}	
  14.  	r->next=NULL;  						//尾结点置空 
  15. 	return L;
  16. }

        图例：采用尾插法建立单链表可以保证生成链表的结点值顺序和输入顺序一致，但是必须开辟一个尾指针永远指向尾结点（方便插入）

 4.查找结点（按值查找）

时间复杂度为O（n）

        查找方式：从单链表中的第一个结点出发，通过while循环依次查找下一个结点的值是否是目标值，如果是则退出循环并且返回此节点的指针，如果不是继续查找。若未找到则返回NULL；

  1. //按值查找
  2. LNode *LocElement(LinkList &L,int value){
  3. 	LNode *p=L->next;
  4. 	while(p!=NULL&&p->data!=value){
  5. 		p=p->next;		            //未找到目标值的结点则一直往下找 
  6. 	}
  7. 	return p;						//找到了 返回此节点指针 
  8. }

5.查找节点（按序查找）

时间复杂度为O（n）

        查找方式：从单链表中的第一个结点出发，通过while循环依次查找下一个结点知道找到第i个结点为止，找到了则退出循环并且返回此节点的指针，如果不是继续查找。若未找到则返NULL；

  1. //按位序查找
  2. LNode *GetElement(LinkList &L,int i){
  3. 	int j;   						//用于计数 
  4. 	if(i<1){
  5. 		return NULL;           		//判断i值是否合法 
  6. 	}
  7. 	LNode *p=L->next; 
  8. 	while(p!=NULL&&j<i){
  9. 		p=p->next;	
  10. 		j++;	            //未找到目标值的结点则一直往下找 
  11. 	}
  12. 	return p;						//找到了 返回此节点指针 
  13. }

6.单链表插入（图例）

        插入结点操作是将值为value的元素插入到指定单链表的位序i处。算法先测试输入的新节点位序是否合法，如果合法则找到此位序的前一个结点进行后插。见图例，首先查到到序号为i-1的结点p，然后令新节点s的指针域指向p的后继节点，再令结点p的指针域指向新插入的结点s即可。

7.单链表按位序插入（带头结点 ，i表示元素位序）

时间复杂度为O（n）

  1. //单链表插入（按位序插入 带头结点） i表示元素位序 
  2. bool ListInsert(LinkList &L,int i,int e){
  3. 	if(i<1){  //判断输入i值是否合法 
  4. 		return false; 
  5. 	}
  6. 	LNode *p;  //用p来指向每个结点  L就是头结点 
  7. 	p=L;
  8. 	int j=0; 
  9. 	while(p!=NULL && j<i-1){  //循环找到第i-1个结点 
  10. 		p=p->next;
  11. 		j++;
  12. 	} 
  13. 	if(p==NULL){ //判断p指向的是否是空值 
  14. 		return false;
  15. 	}
  16. 	LNode *s=(LNode*)malloc(sizeof(LNode));  //创建要插入的结点 
  17. 	s->data=e;  //这里可以直接
  18. 	s->next=p->next;
  19. 	p->next=s;
  20. 	return true;
  21. }

8.单链表按位序插入（不带头结点 ，i表示元素位序）

时间复杂度为O（n）

  1. //单链表插入（按位序插入 不带头结点） i表示元素位序 不带头结点：L永远指向最后一个结点 
  2. bool ListInsert_NoHeadLNode(LinkList &L,int i,int e){
  3. 	if(i<1){  //判断输入i值是否合法 
  4. 		return false; 
  5. 	}
  6. 	if(i==1){  //当是第一个结点时需要单独考虑 因为它无next  无法插入 
  7. 		LNode *s=(LNode*)malloc(sizeof(LNode));
  8. 		s->data=e;
  9. 		s->next=L;
  10. 		L=s; //头指针指向新节点 
  11. 	} 
  12. 	if(i>1){
  13. 		LNode *p; //让p指向第一个节点  让p去扫描 
  14. 		p=L; 
  15. 		int j=1;
  16. 		while(p!=NULL && j<i-1){ //找到第i-1个结点 循环次数和带头结点的不一样哦 少一次  
  17. 			p=p->next; 
  18. 			j++;
  19. 		}
  20. 		if(p==NULL){  //i值不合法 
  21. 			return false; 
  22. 		}
  23. 		LNode *s=(LNode*)malloc(sizeof(LNode));
  24. 		s->data=e;
  25. 		s->next=p->next;
  26. 		p->next=s;
  27. 	}
  28. 	return true;
  29. }

9.给定指定节点的后插操作

时间复杂度为O（n）

  1. //给定指定节点的后插操作
  2. bool InsertNextNode(LNode *p,int e){
  3. 	if(p==NULL){
  4. 		return false;
  5. 	}
  6. 	LNode *s=(LNode*)malloc(sizeof(LNode));
  7. 	if(s==NULL) {  //内存分配失败 
  8. 		return false;
  9. 	}
  10. 	s->data=e; 
  11. 	s->next=p->next;
  12. 	p->next=s;
  13. }

10.指定节点的前插操作

时间复杂度为O（n）

        这个算法很巧妙，其实质就是后插操作之后 再将两个结点的data值互换，即实现前插。（链表的作用是什么呢不就是存储数据吗？依靠存储数据而生 失去数据而亡）

  1. //指定节点的前插操作 6  
  2. bool InsertPriorNode(LNode *p,int e){
  3. 	if(p==NULL){
  4. 		return false;
  5. 	}
  6. 	LNode *s=(LNode*)malloc(sizeof(LNode));
  7. 	if(s==NULL){ //内存不足 
  8. 		return false;
  9. 	}
  10. 	s->next=p->next;
  11. 	p->next=s;
  12. 	s->data=p->data;
  13. 	p->data=e;
  14. 	return true;
  15. }

11.删除结点操作

时间复杂度为O（n）

        删除结点操作就是将链表中位序为i的结点删除。同单链表的插入相同有含头结点和不含头结点的，这里按带头结点的展开。也同单链表的插入一样 需要先找到位序为i-1的结点 对它进行施法图例：

        其实质就是将i-1元素的指针域直接指向i+1的元素就把位序为i的元素删掉了。但是为了不浪费存储空间也需要用一个指针指向被删元素并将它free（释放）掉

12.删除结点返回被删除结点的值（按位序删）

时间复杂度为O（n）

  1. //按位序删除（带头节点）
  2. bool ListDelete(LinkList &L,int i,int &e){
  3. 	if(i<1){
  4. 		return false;
  5. 	}
  6. 	int j=0; 
  7. 	LNode *p;				      //用来指向被删除元素的前一个
  8. 	while(p!=NULL && j<i-1){
  9. 		p=p->next;
  10. 		j++;
  11. 	}
  12. 	if(p==NULL){
  13. 		return false;
  14. 	}	
  15. 	if(p->next==NULL){
  16. 		return false;
  17. 	}
  18. 	e=p->next->data;   			  //取到被删元素的值 
  19. 	LNode *deletedNode;		      //用来指向被删除元素 因为需要free()
  20. 	deletedNode=p->next;
  21. 	p->next=deletedNode->next;
  22. 	free(deletedNode);
  23. 	return true;
  24. }

        同指定结点的前插操作一样，删除结点p的操作可以用删除p的后继结点操作实现。实质就是将后继结点的值赋予自身 然后删除后继结点。

13.求单链表表长操作（含头结点）

时间复杂度为O（n）

求表长操作就是计算单链表中的结点数（表长不含头结点！！！）从第一个结点开始顺序遍历每个结点。设置一个计数器 访问完一个结点（若此结点不空）计数器自增

  1. //求表长操作（带头结点)
  2. int ListLength(LinkList &L){
  3. 	int i=0,j;     			//i是计数器 j用于循环 
  4. 	LNode *p=L->next;        //p指向第一个结点 (头结点不算入表长)
  5. 	while(p!=NULL){
  6. 		i++;
  7. 		p=p->next;
  8. 	}
  9. 	return i;
  10. }

三、完整代码

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct LNode{  //struct相当于java里的对象 使用typedef后struct LNode 类型可表示为LNode类型 
  4. 	int data;
  5. 	struct LNode *next;  //指针类型是 LNode 指向下一个整体 
  6. }LNode,*LinkList; //LinkList类型等价于 LNode*类型； 使用不同的代表不同含义 创建结点用LNode 
  7.  
  8. //使用头插法建立单链表 （含头结点）
  9. LinkList List_HeadInsert (LinkList &L){ //逆向建立单链表
  10. 	LNode *s;int x;
  11.  	L=(LinkList)malloc(sizeof(LNode)); //创建头结点  ;
  12.  	L->next=NULL;
  13.  	scanf("%d",&x);						//输入第一个结点的值 
  14.  	while(x!=9999){                      //输入9999表示结束 
  15. 		s=(LNode*)malloc(sizeof(LNode));
  16. 		s->data=x;
  17.  		s->next=L->next;
  18.  		L->next=s;
  19.  		scanf("%d",&x);
  20.  	}	
  21. 	return L;
  22. }
  23.  
  24. //使用尾插法建立单链表（含头结点） 
  25. LinkList List_TailInsert (LinkList &L){ //逆向建立单链表
  26.  	L=(LinkList)malloc(sizeof(LNode)); 	//创建头结点 ;
  27. 	LNode *s,*r=L;int x; 					//s指向新节点  r指向尾结点 
  28.  	L->next=NULL;
  29.  	printf("依次输入结点值 输入9999表示结束");
  30.  	scanf("%d",&x);						//输入第一个结点的值 
  31.  	while(x!=9999){                      //输入9999表示结束 
  32. 		s=(LNode*)malloc(sizeof(LNode));
  33. 		s->data=x;
  34.  		r->next=s;
  35.  		r=s;
  36.  		scanf("%d",&x);
  37.  	}	
  38.  	r->next=NULL;  						//尾结点置空 
  39. 	return L;
  40. }
  41.  
  42. //按值查找
  43. LNode *LocElement(LinkList &L,int value){
  44. 	LNode *p=L->next;
  45. 	while(p!=NULL&&p->data!=value){
  46. 		p=p->next;		            //未找到目标值的结点则一直往下找 
  47. 	}
  48. 	return p;						//找到了 返回此节点指针 
  49. } 
  50.  
  51. //按位序查找
  52. LNode *GetElement(LinkList &L,int i){
  53. 	int j;   						//用于计数 
  54. 	if(i<1){
  55. 		return NULL;           		//判断i值是否合法 
  56. 	}
  57. 	LNode *p=L->next; 
  58. 	while(p!=NULL&&j<i){
  59. 		p=p->next;	
  60. 		j++;	            //未找到目标值的结点则一直往下找 
  61. 	}
  62. 	return p;						//找到了 返回此节点指针 
  63. } 
  64.  
  65. //单链表插入（按位序插入 带头结点） i表示元素位序 
  66. bool ListInsert(LinkList &L,int i,int e){
  67. 	if(i<1){  //判断输入i值是否合法 
  68. 		return false; 
  69. 	}
  70. 	LNode *p;  //用p来指向每个结点  L就是头结点 
  71. 	p=L;
  72. 	int j=0; 
  73. 	while(p!=NULL && j<i-1){  //循环找到第i-1个结点 
  74. 		p=p->next;
  75. 		j++;
  76. 	} 
  77. 	if(p==NULL){ //判断p指向的是否是空值 
  78. 		return false;
  79. 	}
  80. 	LNode *s=(LNode*)malloc(sizeof(LNode));  //创建要插入的结点 
  81. 	s->data=e;  //这里可以直接
  82. 	s->next=p->next;
  83. 	p->next=s;
  84. 	return true;
  85. }
  86.  
  87. //单链表插入（按位序插入 不带头结点） i表示元素位序 不带头结点：L永远指向最后一个结点 
  88. bool ListInsert_NoHeadLNode(LinkList &L,int i,int e){
  89. 	if(i<1){  //判断输入i值是否合法 
  90. 		return false; 
  91. 	}
  92. 	if(i==1){  //当是第一个结点时需要单独考虑 因为它无next  无法插入 
  93. 		LNode *s=(LNode*)malloc(sizeof(LNode));
  94. 		s->data=e;
  95. 		s->next=L;
  96. 		L=s; //头指针指向新节点 
  97. 	} 
  98. 	if(i>1){
  99. 		LNode *p; //让p指向第一个节点  让p去扫描 
  100. 		p=L; 
  101. 		int j=1;
  102. 		while(p!=NULL && j<i-1){ //找到第i-1个结点 循环次数和带头结点的不一样哦 少一次  
  103. 			p=p->next; 
  104. 			j++;
  105. 		}
  106. 		if(p==NULL){  //i值不合法 
  107. 			return false; 
  108. 		}
  109. 		LNode *s=(LNode*)malloc(sizeof(LNode));
  110. 		s->data=e;
  111. 		s->next=p->next;
  112. 		p->next=s;
  113. 	}
  114. 	return true;
  115. }
  116.  
  117. //给定指定节点的后插操作
  118. bool InsertNextNode(LNode *p,int e){
  119. 	if(p==NULL){
  120. 		return false;
  121. 	}
  122. 	LNode *s=(LNode*)malloc(sizeof(LNode));
  123. 	if(s==NULL) {  //内存分配失败 
  124. 		return false;
  125. 	}
  126. 	s->data=e; 
  127. 	s->next=p->next;
  128. 	p->next=s;
  129. }
  130.  
  131. //指定节点的前插操作 6  
  132. bool InsertPriorNode(LNode *p,int e){
  133. 	if(p==NULL){
  134. 		return false;
  135. 	}
  136. 	LNode *s=(LNode*)malloc(sizeof(LNode));
  137. 	if(s==NULL){ //内存不足 
  138. 		return false;
  139. 	}
  140. 	s->next=p->next;
  141. 	p->next=s;
  142. 	s->data=p->data;
  143. 	p->data=e;
  144. 	return true;
  145. }
  146.  
  147. //按位序删除（带头节点）
  148. bool ListDelete(LinkList &L,int i,int &e){
  149. 	if(i<1){
  150. 		return false;
  151. 	}
  152. 	int j=0; 
  153. 	LNode *p=L;				      //用来指向被删除元素的前一个
  154. 	while(p!=NULL && j<i-1){
  155. 		p=p->next;
  156. 		j++;
  157. 	}
  158. 	if(p==NULL){
  159. 		return false;
  160. 	}	
  161. 	if(p->next==NULL){
  162. 		return false;
  163. 	}
  164. 	e=p->next->data;   			  //取到被删元素的值 
  165. 	LNode *deletedNode;		      //用来指向被删除元素 因为需要free()
  166. 	deletedNode=p->next;
  167. 	p->next=deletedNode->next;
  168. 	free(deletedNode);
  169. 	return true;
  170. } 
  171.  
  172. //求表长操作（带头结点)
  173. int ListLength(LinkList &L){
  174. 	int i=0,j;     			//i是计数器 j用于循环 
  175. 	LNode *p=L->next;        //p指向第一个结点 (头结点不算入表长)
  176. 	while(p!=NULL){
  177. 		i++;
  178. 		p=p->next;
  179. 	}
  180. 	return i;
  181. } 
  182.  
  183. //打印链表(带头结点)
  184. void PrintList(LinkList &L){
  185. 	int i;
  186. 	int j=ListLength(L);
  187. 	LNode *p=L->next;
  188. 	for(i=0;i<j;i++){
  189. 		printf("%d\n",p->data);
  190. 		p=p->next;
  191. 	}
  192. }
  193.  
  194. //test 
  195. int main(){
  196. 	int e;
  197. 	LinkList L;
  198. 	List_TailInsert(L);   //输入9999表示结束
  199. 	int j=ListLength(L);
  200. 	bool k=ListDelete(L,3,e);
  201. 	PrintList(L);
  202. 	printf("%d\n",j);
  203. 	printf("%d\n",e);
  204. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/846433
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号