1. Toy模板网首页
  2. > Toy博客

C语言—链表

9月前 作者：@嵌入式小白 分类：Toy博客 阅读(17) 违法举报

这篇具有很好参考价值的文章主要介绍了C语言—链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

文章目录

一，链表的概念

二，静态创建链表和动态遍历

 三，统计链表节点个数及链表查找

 四，链表的插入

1，从指定节点后方插入新节点

2，从指定节点前方插入新节点 

五，链表删除指定节点

六，动态创建链表

           1，头插法：

           2，尾插法：

一，链表的概念

1，什么是链表？

链表是一种数据结构，是一种数据存放的思想；
2，链表和数组的区别

数组的特点：

  • 数组中的每一个元素都属于同一数据类型的；
  • 数组是一组有序数据的集合；
  • 数组是在内存中开辟一段连续的地址空间用来存放一组数据，可以用数组名加下标来访问数组中的元素； 

链表的特点：               

  • 动态地进行存储分配的一种结构；
  • 链表中的各节点在内存中的地址都是不连续的；
  • 链表是由一个个节点组成，像一条链子一样；
  • 链表中的节点一般包括两个部分（1）用户要用的数据（2）下一个节点的地址；

*两者对比：

  •  一个数组只能存放同一种类型的数据，而链表中就可以存放不同的数据类型；
  • 数组中的元素地址是连续的，想删除或添加一个新的元素，十分的麻烦不灵活，而且用数组存放数据是都要先定义好数组的大小(即元素的个数)，如果在定义数组时，定义小了，内存不够用，定义大了，显然会浪费内存；而链表就可以很好的解决这些问题，链表中每一项都是一个结构体，链表中各节点在内存中的地址可以是不连续的，所以你想删除或添加一个新的节点很简单和方便，直接把节点中存放的的地址拿去修改就ok了(具体怎么添加或删除放在后用代码详细讲)，因为链表是一种动态结构，所以链表在建立的时候并不用像数组一样需要提前定义大小和位置(具体怎么创建也放在后面用代码详细讲)。

二，静态创建链表和动态遍历


#include<stdio.h>

struct Test//声明结构体类型
{
	int data;//定义数据域
	struct Test *next;//定义指针域
};

//遍历链表
void printLink(struct Test *head)
{
    struct Test *p = head;//使p指向链表头

	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时，循环结束
		printf("%d ",p->data);//输出当前节点中data的值
		p = p->next;//使p指向下一个节点
	}
    printf("\n");
}

int main()
{
    struct Test* head;
    //定义结构体变量，作为节点，给节点赋值
	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
	
    head = &t1;//将节点t1的起始地址赋给头指针head
	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
	
	printLink(head);//把链表头传到函数printLink中
	
	return 0;
}

c语言链表,C语言,链表,c语言,数据结构

 三，统计链表节点个数及链表查找


#include<stdio.h>

struct Test//声明结构体类型
{
	int data;//定义数据域
	struct Test *next;//定义指针域
};

//遍历链表
void printLink(struct Test *head)
{
    struct Test *p = head;//使p指向链表头

	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时，循环停止
		printf("%d ",p->data);//输出当前节点中data的值
		p = p->next;//使p指向下一个节点
	}
}

//统计节点的个数
int getNodeSum(struct Test *head)
{
	int sum = 0;
	struct Test *p = head;//使p指向链表头
	
	 while(p != NULL){//遍历链表,直到链表尾NULL时停止
		sum++;//统计链表节点的个数
		p = p->next;//使p指向下一个节点
	}
	return sum;//把统计的节点的个数return回去
}

//链表查询
int searchLink(struct Test *head,int  n)
{
	while(head != NULL){//遍历链表，直到链表尾NULL时停止
		if(head->data == n){//判断当前节点中的data(数据域)和要查询的是否相同
			return 1;//相同的话return 1
		}
		head = head->next;//使head指向下一个节点
	}
	return 0;//不相同return 0
}

int main()
{
	int ret;
    struct Test* head;
    //定义结构体变量，作为节点，给节点赋值
	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
	
    head = &t1;//将节点t1的起始地址赋给头指针head
	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
	
	printLink(head);//把链表头传到函数printLink中
	
	ret = getNodeSum(head);
	printf("此链表一共有%d个节点\n",ret);
	
	ret = searchLink(head,2);
	if(ret == 1){//判断return回来的值
	    printf("有1这个节点\n");
	}
	else{
		printf("没有1这个节点\n");
	}
	
	ret = searchLink(head,7);
	if(ret == 1){//判断return回来的值
	    printf("有7这个节点\n");
	}
	else{
		printf("没有7这个节点\n");
	}
	
	return 0;
}

c语言链表,C语言,链表,c语言,数据结构

 四，链表的插入

插入一个新节点有两种方法：        

  1.  在指定节点后
  2.  在指定节点前

1，从指定节点后方插入新节点

找到指定节点,把新节点节点的下一个节点放在要新节点的next(指针域)中,再把新节点放在指定节点的next(指针域)中

c语言链表,C语言,链表,c语言,数据结构

#include<stdio.h>

struct Test//声明结构体类型
{
	int data;//定义数据域
	struct Test *next;//定义指针域
};

//遍历链表
void printLink(struct Test *head)
{
    struct Test *p = head;

	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
		printf("%d ",p->data);//输出p节点中data的值
		p = p->next;//使p指向下一节点
	}
	printf("\n");
}

//从指定节点后方插入新节点
void insertFromBehind(struct Test *head,int n,struct Test *new)
{
	struct Test *p = head;
	while(p != NULL){
		if(p->data == n){//判断当前节点是不是指定节点
			new->next = p->next;//把新节点的next(指针域)指向指定节点的下一个节点(这边要注意顺序不能换，否则链表会断掉)
			p->next = new;//再把指定节点的next(指针域)指向新节点
		}
		p = p->next;//使p指向下一节点
	}
}

int main()
{
	struct Test* head;
    //定义结构体变量，作为节点，给节点赋值
	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
	
    head = &t1;//将节点t1的起始地址赋给头指针head
	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
	
	printLink(head);//把链表头传到函数printLink中
	
	struct Test new = {100,NULL};//定义一个新节点
	
	insertFromBehind(head,5,&new);//把链表头,要插入的位置,和新节点的地址传过去
	printLink(head);//把链表头传过去,打印链表
	
	
	return 0;
}

c语言链表,C语言,链表,c语言,数据结构

2，从指定节点前方插入新节点 

要考虑两种情况：

  1. 在第一个节点前插入；
  2. 在中间节点插入；

c语言链表,C语言,链表,c语言,数据结构

#include<stdio.h>

struct Test//声明结构体类型
{
	int data;//定义数据域
	struct Test *next;//定义指针域
};

//遍历链表
void printLink(struct Test *head)
{
    struct Test *p = head;

	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
		printf("%d ",p->data);//输出p节点中data的值
		p = p->next;//使p指向下一节点
	}
	printf("\n");
}

//从指定节点前方插入新节点
struct Test* insertFromfront(struct Test *head,int data,struct Test *new)
{
	struct Test* p = head;
	//在头节点插入(链表头会改变)
	if(p->data == data){//判断指定的节点是不是头节点
	    new->next = p;//让新节点的next(指针域)指向p
		return new;//现在new成为新的链表头了
	}
	//在中间节点插入
	while(p->next != NULL){//因为这里是从中间节点插入，所以会从第二个节点开始遍历链表,直到链表尾NULL时停止
		if(p->next->data == data){//判断当前节点是不是指定节点
			new->next = p->next;//让要插入节点的next(指针域)指向p->next(就是当前节点的下一个节点)
			p->next = new;//在让当前节点next(指针域)指向要插入的节点new
			return head;//再把链表头给return回去
		}
		p = p->next;//使p指向下一节点
	}
	return head;
}

int main()
{ 
	struct Test* head;
    //定义结构体变量，作为节点，给节点赋值
	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
	
    head = &t1;//将节点t1的起始地址赋给头指针head
	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
	
	printLink(head);//将头指针的地址传到函数printLink中
	
	struct Test new = {100,NULL};//定义一个新节点
	
	
	head = insertFromfront(head,5,&new);//把链表头,要插入的位置,和新节点的地址传过去
	printLink(head);//把链表头传过去,打印链表
	
	return 0;
}

c语言链表,C语言,链表,c语言,数据结构

五，链表删除指定节点

要考虑两种情况：

  1. 判断删除的节点是不是第一个节点，如果是第一个节点，直接改链表头，让第二个节点成为新的链表头
  2. 删除的节点如果非第一个节点的话：把要删除节点的前一个节点的next(指针域)越过要删除的节点，然后指向要删除节点的下一个节点；

*注意如果链表是动态创建的记得把删除的这个节点给free掉

c语言链表,C语言,链表,c语言,数据结构

#include<stdio.h>

struct Test//声明结构体类型
{
	int data;//定义数据域
	struct Test *next;//定义指针域
};

//遍历链表
void printLink(struct Test *head)
{
    struct Test *p = head;

	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
		printf("%d ",p->data);//输出p节点中data的值
		p = p->next;//使p指向下一节点
	}
	printf("\n");
}

//删除指定节点
struct Test* deleteNode(struct Test *head,int data)
{
	struct Test* p = head;
	//删除第一个节点
	if(p->data == data){//判断要删除的节点是不是头节点
	    head = head->next;//让p指向下一个节点
		return head;//把新的链表头传回去
	}
	//删除非第一个节点
	while(p->next != NULL){//从第二个节点开始遍历链表
		if(p->next->data == data){//判断当前节点是不是要删除的节点
			p->next = p->next->next;//把要删除节点的前一个节点的next(指针域)越过要删除的节点，然后指向要删除节点的下一个节点
			return head;//把链表头传回去
		}
		p = p->next;//使p指向下一节点
	}
	return head;
}

int main()
{ 
	struct Test* head;
    //定义结构体变量，作为节点，给节点赋值
	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
	
    head = &t1;//将节点t1的起始地址赋给头指针head
	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
	
	printLink(head);//将头指针的地址传到函数printLink中
	printf("删除指定节点后的链表：\n");
	head = deleteNode(head,5);//把链表头，和要删除第几个节点传过去
	printLink(head);//把链表头传过去,打印链表
	
	return 0;
}

c语言链表,C语言,链表,c语言,数据结构

六，动态创建链表

动态创建链表也是有两种方法：

1，头插法：

每一次创建的新节点插在之前的链表头之前，再让新节点做为新的链表头；

#include<stdio.h>
#include<stdlib.h>

struct Test//声明结构体类型
{
	int data;//定义数据域
	struct Test *next;//定义指针域
};

//遍历链表
void printLink(struct Test *head)
{
    struct Test *p = head;

	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
		printf("%d ",p->data);//输出p节点中data的值
		p = p->next;//使p指向下一节点
	}
	printf("\n");
}

struct Test* insertFromHead(struct Test* head,struct Test* new)
{
	
	if(head == NULL){//判断链表是否为空
		head = new;//如果为空把创建的新节点当作链表头
	}else{
		new->next = head;//当链表不为空的时候，让新节点插在链表头的前面(称之为头插法)
		head = new;//再让新节点成为链表头
	}
	return head;
}

//动态创建链表(头插法)
struct Test* creatLink(struct Test* head)
{
	struct Test* new;
	while(1){
		new = (struct Test*)malloc(sizeof(struct Test));//开辟空间
		new->next = NULL;
		printf("input your ne node data:\n");
		scanf("%d",&(new->data));//输入节点的数据域(data)
	    if(new->data == 0){//判断每次输入的值是否为0，如果为0，停止创建新节点
		    printf("0 quit\n");
			return head;
		}
		head = insertFromHead(head,new);
    }	
	return head;
}

int main()
{
	struct Test* head = NULL;
    head = creatLink(head);	
	printLink(head);
	
	return 0;
}

c语言链表,C语言,链表,c语言,数据结构

2，尾插法：

如果链表为空，创建的第一个节点做为链表头，然后每一次创建的新节点插在链表最后一个节点的指针域(next)中；

#include<stdio.h>
#include<stdlib.h>

struct Test//声明结构体类型
{
	int data;//定义数据域
	struct Test *next;//定义指针域
};

//遍历链表
void printLink(struct Test *head)
{
    struct Test *p = head;

	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
		printf("%d ",p->data);//输出p节点中data的值
		p = p->next;//使p指向下一节点
	}
	printf("\n");
}

struct Test* insertBehind(struct Test* head,struct Test* new)
{
	struct Test* p = head;
	
	if(p == NULL){//判断链表是否为空
		return head = new;//如果为空把创建的新节点当作链表头
	}
	while(p->next != NULL){//遍历到最后一个节点
		p = p->next;//使p指向下一节点
	}
	p->next = new;//把新节点插入最后一个节点的指针域(next)中
	return head;//把链表头传回去
}

//动态创建链表(尾插法)
struct Test* creatLink(struct Test* head)
{
	struct Test* new;
	while(1){
		new = (struct Test*)malloc(sizeof(struct Test));//开辟空间
		new->next = NULL;
		printf("input your ne node data:\n");
		scanf("%d",&(new->data));//输入节点的数据域(data)
	    if(new->data == 0){//判断每次输入的值是否为0，如果为0，停止创建新节点
		    printf("0 quit\n");
			return head;
		}
		head = insertBehind(head,new);
	}
}

int main()
{
	struct Test* head = NULL;
	head = creatLink(head);
	printLink(head);
	
}

c语言链表,C语言,链表,c语言,数据结构

写在最后：

博主是一位在校中专生，刚学不久，实力有限，内容仅供参考，有不对地方欢迎大神指出，一起讨论，一起进步文章来源地址https://www.toymoban.com/news/detail-734566.html

到了这里，关于C语言—链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C语言数据结构之链表

    C语言数据结构之链表

    在上一篇博客中我们提到，线性表包括顺序表和链表，顺序表在上篇博客中已经介绍，本篇博客介绍一下另一种线性表—— 链表 。 概念：链表是⼀种 物理存储结构上⾮连续、⾮顺序 的存储结构，数据元素的 逻辑顺序是通过链表中的指针链接次序实现的 。 链表的结构跟⽕

    2024年04月22日
    浏览(44)
  • C语言数据结构-双向链表

    C语言数据结构-双向链表

    带头链表的头结点,实际是\\\"哨兵位\\\",哨兵位节点不存储任何有效元素,只是站在这里\\\"放哨的\\\". 哨兵位的意义:遍历循环链表避免死循环. 笔者在删除,插入数据时,画好图后,也好了代码,但是在调试中多次出现 代码位置出错 ,导致写的代码的含义不符合预期. 所以说思路一定要清晰

    2024年02月04日
    浏览(48)
  • 数据结构链表（C语言实现）

    数据结构链表（C语言实现）

            机遇对于有准备的头脑有特别的亲和力。本章将讲写到链表其中主要将写到单链表和带头双向循环链表的如何实现。    话不多说安全带系好，发车啦 （建议电脑观看） 。 附：红色，部分为重点部分；蓝颜色为需要记忆的部分（不是死记硬背哈，多敲）；黑色加粗

    2024年02月10日
    浏览(37)

  • 数据结构——单向链表（C语言版）

    在数据结构和算法中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在C语言中，我们可以使用指针来实现单向链表。下面将详细介绍如何用C语言实现单向链表。 目录 1. 定义节点结构体 2. 初始化链表 3. 插入节点 4. 删除节点

    2024年03月24日
    浏览(42)

  • Go语言数据结构（一）双向链表

    Go语言中list容器定义在\\\"container/list\\\"包中，实现了一个双向链表。本文第一部分总结源码包中的方法，第二部分展示使用list包的常见示例用法以及刷题时的用法。 食用指南：先看第二部分的常用示例用法然后再用到时在第一部分找对应的方法。 更多内容以及其他Go常用数据结

    2024年01月19日
    浏览(38)
  • 双向链表--C语言实现数据结构

    双向链表--C语言实现数据结构

    本期带大家一起用C语言实现双向链表🌈🌈🌈 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；简单来说，线性表的链式存储结构生成的表，称作“链表”。 每个元素本身由两部分组成： 1、本身的信息，称

    2024年02月04日
    浏览(57)
  • ＜数据结构＞ 链表 - 单链表（c语言实现）

    ＜数据结构＞ 链表 - 单链表（c语言实现）

    哨兵位结点也叫哑节点。哨兵位结点 也是头结点 。该节点 不存储有效数据，只是为了方便操作 （如尾插时用带哨兵位的头结点很爽，不需要判空）。 有哨兵位结点的链表，第一个元素应该是链表第二个节点（head - next，head为哨兵位结点）对应的元素。 有哨兵位结点的链表

    2023年04月11日
    浏览(113)

  • 数据结构——双向链表（C语言版）

    上一章： 数据结构——单向链表（C语言版）-CSDN博客 目录 什么是双向链表？ 双向链表的节点结构 双向链表的基本操作 完整的双向链表示例 总结 什么是双向链表？ 双向链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两个指针：一个指向前一个节点，一个

    2024年03月26日
    浏览(52)
  • C语言进阶——数据结构之链表（续）

    C语言进阶——数据结构之链表（续）

    hello，大家好呀，我是Humble，本篇博客承接之前的 C语言进阶——数据结构之链表 的内容 （没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~） ，上次我们重点说了链表中的 单链表 ，即 不带头单向不循环链表 还说到了链表的分类虽

    2024年01月25日
    浏览(57)
  • 【数据结构】—C语言实现双向链表（超详细!）

    【数据结构】—C语言实现双向链表（超详细!）

                                          食用指南：本文在有C基础的情况下食用更佳                                       🔥 这就不得不推荐此专栏了：C语言                                     🍀 双向链表 前 置知识 ：单链表      

    2024年02月13日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包