C语言实现链表基本操作

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

目录

一、什么是链表

二、为什么要使用链表

三、链表相关知识

四、链表实现

1.定义结构体

2.创建链表

3.遍历链表

4.判断链表是否为空

5.计算链表长度

6.插入一个数据

7.删除数据

8.全部代码


一、什么是链表

如果把数据比喻成珠子,指针就是线,链表通过指针这条线就是把数据这些珠子串起来。

二、为什么要使用链表

数组是我们接触c语言时学到的一种重要的数据存储方式,是连续的,可以快速查找某个位置的数据。都是要对数组实现删除和插入等功能时,需要移动大量的数据,耗时长。而且数组使用前就分配好内存,分配的内存过小可能不够用,过大就造成浪费。

而链表实现对数据删除和插入的功能时具有优势,而且可以要用时才分配,可以说基本不存在内存不足和浪费的情况。链表分配内存时一小块一小块的,数组则是连续的一大块。假如我们要存储学生的成绩,那就要一个学生的姓名,学号,课程名字,课程成绩等等,假定一个学生要二十字节的空间,一个学院五千人,那就要10万字节。如果你硬要用数组存储,你得找到一块连续的10万字节的空间,很难吧。用链表就不需要,一块连续且这么大的空间。

三、链表相关知识

头结点:单链表的第一个结点,头结点的数据域不存储信息,指针域指向第一个有效结点即首结点。头结点的作用是使所有链表(包括空表)的头指针非空,其实头结点的作用是为了方便操作。

首结点:存放第一个有效数据的节点。

头指针:指向头节点的指针。

尾节点:存放最后一个有效数据的节点。

尾指针:指向尾节点的指针。

四、链表实现

1.定义结构体

typedef struct Node
{
	Elemtype data;//数据域
	struct Node* pNext;//指针域

}NODE, * PNODE;//NODE相当于struct Node,* PNODE相当于struct Node *

结构体大同小异,主要分为数据域和指针域。看需求修改数据域,比如你存放学生成绩,那就多定义一些数据类型就好。

2.创建链表

PNODE create_list()//创建链表
{
	int length, value;

	PNODE pHead = (PNODE)malloc(sizeof(NODE));//分配头结点
	if (NULL == pHead)
	{
		printf("分配内存失败,程序结束!\n");
		exit(-1);
	}
	PNODE pTail = pHead;//尾结点,每次增加结点时,尾结点跟着后移
	pTail->pNext = NULL;

	printf("链表结点个数:");
	scanf("%d", &length);
	for (int i = 0; i < length; i++)
	{
		printf("输入第%d个结点的值:", i + 1);
		scanf("%d", &value);
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pNew)
		{
			printf("分配内存失败,程序结束\n");
			exit(-1);
		}
		pNew->data = value;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}

	return pHead;
}

使用尾指针方便操作,链表操作里面,经常要多定义一两个指针辅助功能实现。

3.遍历链表

void traverse_list(PNODE pHead)//遍历链表
{
	PNODE p = pHead->pNext;//用指针p指向第一个结点

	while (p != NULL)
	{
		printf("%-4d", p->data);
		p = p->pNext;
	}
	printf("\n");

}

把头指针赋值给另外一个新的指针,遍历时就移动新指针就好了。

4.判断链表是否为空

bool is_empty(PNODE pHead)//判断链表是否为空
{
	if (NULL == pHead->pNext)
		return true;
	else
		return false;
}

5.计算链表长度

int length_list(PNODE pHead)//计算链表长度
{
	PNODE p = pHead->pNext;
	int length = 0;
	while (p != NULL)
	{
		length++;
		p = p->pNext;
	}
	return length;
}

6.插入一个数据

bool insert_list(PNODE pHead, int position, int value)//在第position个结点前面插入一个结点
{
	int i = 0;
	PNODE p = pHead;

	while (p != NULL && i < position - 1)
	{
		p = p->pNext;
		i++;
	}

	if (i > position - 1 || NULL == p)
		return false;
	
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew)
	{
		printf("内存分配失败\n");
		exit(-1);
	}
	pNew->data = value;
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;
	return true;
}

7.删除数据

bool delect_list(PNODE pHead, int position, int* value)//删除第position个结点
{
	int i = 0;
	PNODE p = pHead;

	while (p->pNext != NULL && i < position - 1)
	{
		p = p->pNext;
		i++;
	}

	if (i > position - 1 || NULL == p->pNext)
		return false;

	PNODE q = p->pNext;
	*value = q->data;
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
	return true;
}

删完记得释放内存,否则造成内存泄漏。

排序

void sort_list(PNODE pHead)//排序
{
	int length = length_list(pHead);
	int i, j, t;
	PNODE p, q;
	for (i = 0,p = pHead->pNext; i < length - 1; i++, p = p->pNext)
	{
		for (j = i + 1, q = p->pNext; j < length; j++, q = q->pNext)
		{
			if (p->data > q->data)
			{
				t = p->data;
				p->data = q->data;
				q->data = t;
			}
		}
	}
}

8.全部代码

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#pragma warning(disable : 4996)

typedef int Elemtype;

typedef struct Node
{
	Elemtype data;//数据域
	struct Node* pNext;//指针域

}NODE, * PNODE;//NODE相当于struct Node,* PNODE相当于struct Node *

PNODE create_list();
void traverse_list(PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE pHead);
bool insert_list(PNODE pHead, int position, int value);
bool delect_list(PNODE pHead, int position, int* value);
void sort_list(PNODE pHead);


int main()
{
	PNODE pHead = NULL;
	int value;
	pHead = create_list();//创建非循环单链表
	traverse_list(pHead);
	if (is_empty(pHead))
		printf("链表为空\n");
	else
		printf("链表不为空\n");
	int length = length_list(pHead);
	printf("链表长度为%d\n", length);

	insert_list(pHead, 4, 75);
	traverse_list(pHead);
	sort_list(pHead);
	traverse_list(pHead);
	if (delect_list(pHead, 4, &value))
	{
		printf("删除成功,删除的元素为%d\n", value);
	}
	else
	{
		printf("删除失败,删除的元素不存在\n");
	}
	traverse_list(pHead);

	return 0;
}

PNODE create_list()//创建链表
{
	int length, value;

	PNODE pHead = (PNODE)malloc(sizeof(NODE));//分配头结点
	if (NULL == pHead)
	{
		printf("分配内存失败,程序结束!\n");
		exit(-1);
	}
	PNODE pTail = pHead;//尾结点,每次增加结点时,尾结点跟着后移
	pTail->pNext = NULL;

	printf("链表结点个数:");
	scanf("%d", &length);
	for (int i = 0; i < length; i++)
	{
		printf("输入第%d个结点的值:", i + 1);
		scanf("%d", &value);
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pNew)
		{
			printf("分配内存失败,程序结束\n");
			exit(-1);
		}
		pNew->data = value;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}

	return pHead;
}

void traverse_list(PNODE pHead)//遍历链表
{
	PNODE p = pHead->pNext;//用指针p指向第一个结点

	while (p != NULL)
	{
		printf("%-4d", p->data);
		p = p->pNext;
	}
	printf("\n");

}

bool is_empty(PNODE pHead)//判断链表是否为空
{
	if (NULL == pHead->pNext)
		return true;
	else
		return false;
}

int length_list(PNODE pHead)//计算链表长度
{
	PNODE p = pHead->pNext;
	int length = 0;
	while (p != NULL)
	{
		length++;
		p = p->pNext;
	}
	return length;
}

bool insert_list(PNODE pHead, int position, int value)//在第position个结点前面插入一个结点
{
	int i = 0;
	PNODE p = pHead;

	while (p != NULL && i < position - 1)
	{
		p = p->pNext;
		i++;
	}

	if (i > position - 1 || NULL == p)
		return false;
	
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew)
	{
		printf("内存分配失败\n");
		exit(-1);
	}
	pNew->data = value;
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;
	return true;
}

bool delect_list(PNODE pHead, int position, int* value)//删除第position个结点
{
	int i = 0;
	PNODE p = pHead;

	while (p->pNext != NULL && i < position - 1)
	{
		p = p->pNext;
		i++;
	}

	if (i > position - 1 || NULL == p->pNext)
		return false;

	PNODE q = p->pNext;
	*value = q->data;
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
	return true;
}

void sort_list(PNODE pHead)//排序
{
	int length = length_list(pHead);
	int i, j, t;
	PNODE p, q;
	for (i = 0,p = pHead->pNext; i < length - 1; i++, p = p->pNext)
	{
		for (j = i + 1, q = p->pNext; j < length; j++, q = q->pNext)
		{
			if (p->data > q->data)
			{
				t = p->data;
				p->data = q->data;
				q->data = t;
			}
		}
	}
}

主函数内容仅仅是测试功能而已,最重要是理解各个函数是实现对应的功能。文章来源地址https://www.toymoban.com/news/detail-740329.html

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

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

领支付宝红包 赞助服务器费用

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包