单链表的基本操作代码实现(C语言版)-Toy模板网

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

前言：

单链表的基本操作

准备工作（头文件、各种宏定义以及结构体定义）

一.较简单操作

1.单链表的初始化

2.判断单链表是否为空表

3.单链表的销毁

4.单链表的清空

5.求单链表的表长

二.较重要操作

1.单链表的取值

2.单链表元素的查找

3.单链表的结点插入

4.单链表的结点删除

5.单链表的创建

以下是主函数以及函数声明

补充

前言：

在实现顺序表的基本操作后，觉得自己对单链表基本操作的思路无大问题，因此当时没有对链表基本操作进行实现，在后来的稀疏多项式的运算中需要运用到单链表(顺序表实现会造成大量空间的浪费)，而自己并没有实现过这些基本操作，为防止在做稀疏多项式的运算时出现难以解决的问题，打算再把单链表的基本操作实现一遍。并写一篇博客，耗时：70分钟。

希望能够对您有一定帮助和参考价值。新csdner，有所不足尽管提出。

单链表的基本操作

单链表的基本操作包括单链表的初始化、判断空链表、销毁、清空以及求表长这些较为简单的操作，还有更为重要的单链表的取值、按值查找返回元素所在地址、按值查找返回元素所对应序号、结点插入和删除以及头插法和尾插法建立单链表。目前只实现了这些操作，并进行的测试。

准备工作（头文件、各种宏定义以及结构体定义）

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

#define OK 1
#define ERROR 0        /*用于返回函数执行的状态值*/

typedef int Status;
typedef int ElemType;

typedef struct Node {

	ElemType data;			 //存储数据
	struct Node *next;//存储下一个元素的地址

} Node;

typedef struct Node *LinkList; /* 定义LinkList */

一.较简单操作

1.单链表的初始化

单链表的初始化指生成一个只有头指针的单链表，并将其指向的头结点的指针域置空。需要注意的是，传入的参数为LinkList *L；为什么L本来就是指针类型了还要加 " * "呢，因为你要知道你是要对链表的本质(内存，指针指向等)进行更改而不是使用链表进行元素的查找取值等，如果只是这些操作，只要告诉计算机你要查找的对象是哪个表，即把链表的头指针传过去就行（这样就不需要添加 " * " ）。以下是代码实现：

/* 初始化链式线性表 */
Status IniList(LinkList *L) {
	
	*L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
		
	(*L)->next=NULL; /* 指针域为空 */
	
	return OK;
}

2.判断单链表是否为空表

只需要判断对应单链表头结点的指针域是否为空即可。该实现我使用的是bool类型返回值，实际上c语言中逻辑值就是0，1，因此多此一举了属于是；如果要用bool类型需要添加头文件#include<stdbool.h>。以下是代码实现：

bool Empty(LinkList L) {

	if(L->next==NULL)
		return true;    

	return false;
//main函数中测试bool c=Empty(L); printf("%d",c);  返回 1
}

3.单链表的销毁

单链表的销毁指将链表中的所有结点包括头结点都释放掉（c语言中使用free（），c++中使用delete（））。由于仍然是对单链表的“本质”进行修改，所以参数需加 " * " ，思路是利用头指针以及新指针p(用于释放其指向的结点)，在释放之前，先将头指针后移，否则找不到下一结点。以下是代码实现：

/* 单链表的销毁*/         

Status DestoryList(LinkList *L) {
	LinkList p=*L;              //p此时指向头结点

	//注意此时不能直接释放p，因为头结点中还存放着下一结点的地址，释放就找不到下一个结点了
	while(*L) {
		*L=(*L)->next;
		free(p);            
		p=*L;	
	}

	return OK;

	//测试int b=DestoryList(&L);  printf("%d",b);ListTraverse(L); 输出1，且并不打印其他的
}

4.单链表的清空

将除头结点以外的结点释放，并将头结点的指针域置空。与销毁不同，该操作的头指针不能动，所以还需要新定义一个指针对下一结点进行定位。以下是代码实现：

/*清空链表*/
Status ClearList(LinkList L) {

	LinkList p,q;    //p用于指向需要释放的结点，q用于在p释放之前指向下一结点，以使p移动
	p=L->next;       //p指向首元结点

	while(p) {
		q=p->next;   //q指向下一结点
		free(p);
		p=q;
	}

	//最后不要忘了，结点释放后还需要将头结点的指针域更改为NULL，形成空表
	L->next=NULL;

	return OK;

	/*测试CreateList(&L,n); ClearList(L);ListTraverse(L);//不输出创建时输入的元素*/

}

5.求单链表的表长

以下是代码实现：

/*求链表的表长*/
int ListLength(LinkList L) {

	LinkList p;   //用于指向除头结点以外的结点
	int count=0;
	p=L->next;

	while(p) {
		count++;
		p=p->next;
	}

	return count;	

 //测试  printf("%d",ListLength(L)); 输出正确
}

二.较重要操作

1.单链表的取值

取出链表中位置 i 对应的元素，i表示的是序号，不按逻辑层面确定。思路：将指针p移动到对应序号逻辑层面存储位置，随后将其指向的元素返回即可。注意循环终止条件，以下是代码实现：

/*获得某一元素*/  //返回链表中第i位置的元素
Status GetElem(LinkList L,int i,ElemType *e) {

	Node *p;
	p=L->next;
	int j = 1;

	for(; p&&j<i ;) {
		p = p->next; /*p所指元素存在且j<1时循环执行*/
		++j;
	}

	if(!p||j>i) //j大于i的情况：如i传入的为0或负数
		return ERROR;

	*e=p->data;

	return OK;
 //测试：元素返回正确
}

2.单链表元素的查找

查找分为按值查找返回元素所在地址和返回所在序号，思路：定义一个指针p指向头结点，随后利用循环将指针p进行移动即对链表进行遍历，将每次循环时结点的数据与待查找数据比较，如果找到则返回对应地址(反映为当前指针的指向),以及对应的序号。以下是代码实现：

//查找
/*按值查找数据所在地址并返回*/  //参数为所需查询链表，需要查询的数据，返回p的地址
LinkList searchAD(LinkList L,ElemType e) {

	LinkList p;
	p=L->next;

	for(int i=0; p&&i<ListLength(L); i++) {
		if(p->data==e)
			break;
		p=p->next;
	}

	return p; 

//测试；printf("%p",searchAD(L,5));  5所在元素次序不同，打印的地址不同

}

/*按值查找数据所在链表的序号(第几个元素)*/  //参数：所需查询链表，所需查询数据，返回数据所在序号
int searchNum(LinkList L,ElemType e) {

	LinkList p;
	p=L->next;

	for(int i=0; p&&i<ListLength(L) ; i++) {
		if(p->data==e) {    //遍历链表中p所指项结点的数据，与e比较，找到后返回对应序号即可
			return i+1;
		}

		p=p->next; //当前结点的数据不等于e则p指针后移
	}

	return 0; 

 //测试：printf("%d",searchNum(L,5));  返回5所在位置正确,如果不存在所查询数据，返回0
}

3.单链表的结点插入

思路：先将待插入位置找到，利用其前一个位置的指针p对其后继进行保留，随后定义一个新结点并用指向它的指针q，进行前驱后继的链接。以下是代码实现：

//链表元素的插入    //参数:需要插入数据的链表，需要插入元素的位置，需要插入的数据，返回插入结束状态
Status ListInsert(LinkList L,int i,ElemType e) {

	LinkList p,q;
	p=L;        //指向头结点

	//先新建并初始化好需要插入的结点，用指针q指向它
	q=(Node *)malloc(sizeof(Node));
	q->data=e;
	q->next=NULL;


	for(int j=0; p&&j<i-1 ; j++) { 

		if(i>ListLength(L)+1)
			return ERROR;   //如果插入的位置大于链表的尾结点后面的一个位置,则返回错误
		p=p->next; 
	}

	//将待插入结点的前后结点与之形成链式关系

	q->next=p->next;    //接后继结点
	p->next=q;	        //接前驱结点

	return OK;

	/*		测试：ListInsert(L,4,99);	ListTraverse(L); 在表中元素为5个的情况下
		插入位置为1--6均可正确插入，如果插入位置大于等于7，则不插入元素	              */
}

4.单链表的结点删除

思路：同样是先找到待删除结点，将q指针指向它，并新定义一个指针p对其前驱进行指向，以便后续链接，接好待删除结点的前驱后继后即可释放该结点。以下是实现代码：

//链表元素的删除  //参数需要删除元素的链表，需要删除的结点
Status deleElem(LinkList L,int i) {

	LinkList p,q;   //p指向删除位置的前一结点,q指向需要删除的结点
	p=L;  //p指向头结点


	//首先需要将p移动到删除结点的前一结点
	for(int j=0; p&&j<i-1; j++) {
		p=p->next;
	}

	q=p->next;  //如果所需删除结点存在,则将q指向它，如果不存在返回错误，不执行删除

	if(!q)
		return ERROR;  //判断删除的结点是否存在


	p->next=p->next->next;  //也可以p->next=q->next;但一定要在释放之前将p指向下一结点，否则找不到
	free(q);


	return OK;
	/*
	测试：
	deleElem(L,1);
	ListTraverse(L);假设表中有5个元素，则第1--5个位置的元素正常删除，如果为大于等于6的位置，不删除
	*/
}

5.单链表的创建

包括尾插法和头插法，进行单链表的内存分配和结点的添加与赋值。以下是代码实现：

/*头插法创建链表*/ //输入n个元素 ，元素从头开始依次插入

Status CreateList_H(LinkList *L,int n) {
	LinkList p,r;  //p用于指向新结点,r指向头结点

	//建立一个带有头结点的单链表并将指针域置为空
	*L=(LinkList)malloc(sizeof(Node));
	r=*L;
	r->next=NULL;
//结点添加与赋值
	for(int i=n; i>0; i--) {
		p=(Node *)malloc(sizeof(Node));
		printf("请输入该链表的第%d个元素：",i);
		scanf("%d",&p->data);
		p->next=NULL;
		p->next=r->next;
		r->next=p;
	}

	return OK;

	/*测试:printf("请输入头插法创建链表的元素个数：");
	scanf("%d",&n);
	CreateList_H(&L_H,n);
	ListTraverse(L_H);  新建正常
	*/
}

/*尾插法创建链表*/ //输入n个元素， 元素从尾部依次接入
Status CreateList(LinkList *L,int n) {

	LinkList p,r;//p用于指向新结点(待插入结点)，r指向尾部结点

	*L = (LinkList)malloc(sizeof(Node));
	r=*L;  //刚开始时r指向头结点
	r->next=NULL;

	for(int i=0; i<n; i++) {
		p=(Node *)malloc(sizeof(Node));   //注意这里不要忘记将这块内存定义为Node的指针类型
		printf("请输入该链表的第%d个元素：",i+1);
		scanf("%d",&p->data);
		p->next=NULL;
		r->next=p;
		r=r->next;
	}
	r->next=NULL;
	return OK;
}

以下是主函数以及函数声明

对应操作的运行截图就不搞了，主函数也没有对所有函数进行调用，但是各个操作都已进行测试，程序的健壮性还是有的。

Status IniList(LinkList *L);
Status GetElem(LinkList L,int i,ElemType *e);
Status CreateList(LinkList *L,int n);  //尾插法
Status CreateList_H(LinkList *L,int n);//头插法
Status visit(ElemType c);
Status ListTraverse(LinkList L);
bool Empty(LinkList L);
Status DestoryList(LinkList *L);
Status ClearList(LinkList L);
int ListLength(LinkList L);
LinkList searchAD(LinkList L,ElemType e);
int searchNum(LinkList L,ElemType e);
Status ListInsert(LinkList L,int i,ElemType e);
Status deleElem(LinkList L,int i);

int main() {
	LinkList L,L_H;
	int n;
	int a=IniList(&L);     //a用于判断是否成功初始化

	printf("请输入尾插法创建链表的元素个数：");
	scanf("%d",&n);
	CreateList(&L,n);
	ListTraverse(L);
	printf("请输入头插法创建链表的元素个数：");
	scanf("%d",&n);
	CreateList_H(&L_H,n);
	ListTraverse(L_H);
	return 0;
}

补充

为了更方便的对链表进行输出，新定义了两个子函数实现，代码如下：

//打印元素
Status visit(ElemType c) {
	printf("%d ",c);
	return OK;
}
//遍历链表
Status ListTraverse(LinkList L) {
	LinkList p=L->next;
	printf("链表中所有元素为： ");
	if(!p)
		return ERROR;//如果首元结点不存在返回0

	while(p) {
		visit(p->data);
		p=p->next;
	}
	printf("\n");
	return OK;
}

我的小站：Kris20030907.gitee.io，有需要的话可以交换友链哦，评论区留言文章来源地址https://www.toymoban.com/news/detail-847439.html

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