当前位置： 首页 > article >正文

C语言_数据结构总结3:带头结点的单链表

article 2025/3/13 4:37:39

 纯c语言代码，不涉及C++

0. 结点结构

typedef int ElemType;
typedef struct LNode {
    ElemType data;  //数据域
    struct LNode* next;  //指针域
}LNode, * LinkList;
 

1. 初始化

带头结点的初始化，即创建一个头结点，并让头指针指向头结点，头结点的next域初始化为NULL

void InitLink1(LinkList* L) {
	*L = (LinkList)malloc(sizeof(LNode));
	if (*L == NULL)
	{
		printf("内存分配失败!\n");
		exit(1);  //退出系统的操作
	}
	(*L)->next = NULL;
}

2. 头插法

int headInsert(LinkList L,ElemType value) {
	LinkList s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL)
	{
		printf("内存分配失败!\n");
		return -2;
	}
	s->data = value;
	s->next = L->next;
	L->next = s;
	return 0;  //插入成功
}

3. 尾插法

int tailInsert(LinkList L,ElemType value) {
	LinkList s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL)
	{
		printf("内存分配失败!\n");
		return -2;
	}
	s->data = value;
	s->next = NULL;
	LinkList p = L;
	while (p->next != NULL) {
		p = p->next;
	}
	p->next = s;
	return 0;  //插入成功
}

4. 插入

    /*
    插入步骤3中判断 p == NULL 的原因：
当在遍历链表寻找插入位置的前一个结点时，可能会出现以下情况：
一：插入位置超出链表长度
如果要插入的位置 pos 大于链表的实际长度，那么在遍历过程中，指针 p 会沿着链表不断向后移动，最终会移动到链表的末尾（即 p->next == NULL），然后再尝试移动到下一个结点时，p 就会变成 NULL。
二：链表为空且插入位置不为 1
如果链表为空（只有头结点），并且要插入的位置 pos 大于 1，那么在遍历过程中，指针 p 从链表的头结点开始，由于链表没有其他结点，p 会在寻找插入位置的前一个结点时变成 NULL。
在上述两种情况下，如果继续进行插入操作会导致错误，因为此时 p 已经不指向链表中的有效结点，无法进行后续的插入操作。因此，当 p 为 NULL 时，说明插入位置不合法，函数会返回 -1 表示插入失败。
    */

int insertLNode1(LinkList L, int pos, ElemType value) {
	//1. 判断插入位置是否合理
	if (pos < 1)
	{
		printf("插入位置不合法!\n");
		return -1;
	}
	//2. 找到待插入位置的前一个结点
	LinkList p = L;  // 定义一个新指针，让其刚开始指向头结点
	int i = 0;
	while (p != NULL && i < pos - 1) {
		p = p->next;
		i++;
	}
	//3. 判断
	if (p == NULL)
	{
		printf("插入位置不合法!\n");
		return -1;
	}

	LinkList s = (LinkList)malloc(sizeof(LNode));  //为要插入的数据分配空间
	if (s == NULL)
	{
		printf("内存分配失败!\n");
		return -2;
	}
	s->data = value;
	s->next = p->next;
	p->next = s;
	return 0;  //插入成功
}

5. 删除

即：删除第pos个位置上的值

int deleteNode(LinkList L, int pos) {
	if (pos < 1)
	{
		printf("删除位置不合理!\n");
		return -1;
	}
	LinkList p = L;
	int i = 0;
	while (p != NULL && i < pos - 1) {
		p = p->next;
		i++;
	}
	if (p == NULL || p->next == NULL)
	{
		printf("删除位置不合理!\n");
		return -1;
	}
	LinkList temp = p->next;
	p->next = temp->next;
	free(temp);
	return 0;  //删除成功
}

6. 按位查找

即:查找第pos个位置上的value值

int findValueByPos(LinkList L, int pos, ElemType* value) {
	if (pos < 1)
	{
		printf("查找位置不合理!\n");
		return -1;
	}
	LinkList p = L->next;
	int i = 1;
	while (p != NULL && i < pos) {
		p = p->next;
		i++;
	}
	if (p == NULL)
	{
		printf("查找位置超出链表长度!\n");
		return -1;
	}
	*value = p->data;
	return 0; 
}

7. 按值查找

即：查找value值在链表的第pos个位置

int findPosByvalue(LinkList L, ElemType value) {
	LinkList p = L->next;
	int pos = 1;
	while (p != NULL) {
		if (p->data == value)
		{
			return pos;
		}
		p = p->next;
		pos++;
	}
	return -1;  //查找失败
}

8. 链表打印

void printLink1(LinkList L) {
	if (L == NULL || L->next == NULL)
	{
		printf("链表为空!\n");
		return;//提前结束函数
	}
	/*
		对判断条件的分析
1. L == NULL
	 L 是指向链表头结点的指针。
	 当 L == NULL 时，意味着这个指针没有指向任何有效的头结点，
	 也就是根本不存在链表，自然可以判定链表为空。
	 这可能是由于初始化失败或者其他异常情况导致头结点的内存分配没有成功，
	 使得头指针没有指向有效的内存区域。
2. L->next == NULL
	 当 L->next == NULL 时，说明头结点的 next 指针为空。
	 在带头结点的单链表中，头结点的 next 指针指向的是第一个存储实际数据的结点。
	 如果这个指针为空，那就表示链表中没有存储实际数据的结点，也就是链表为空。
	 虽然存在头结点，但它不存储实际数据，链表中没有有效的数据元素，所以可以判定链表为空。
	*/
	LinkList s = L->next;  //即让指针s指向了头结点后的第一格结点
	while (s != NULL) {
		printf("%d ", s->data);
		s = s->next;
	}
	printf("\n--------------------------------\n");
}

9. 释放空间

void freeList1(LinkList L) {
	LinkList p = L;  // 定义一个临时指针指向头结点（和头指针一样，指向头结点，不同的是，该结点后续有变动）
	while (p != NULL) {
		LinkList temp = p;  // 在每次循环中，创建一个临时指针 temp，并将其指向当前结点 p。这是因为在释放当前结点之前，需要先保存该结点的地址，以便后续调用 free 函数释放其内存。
		p = p->next;
		free(temp);
	}
}

10. 测试代码

int main() {
	//测试插入方法
	LinkList L1;
	InitLink1(&L1);
	insertLNode1(L1, 1, 11);
	insertLNode1(L1, 2, 22);
	insertLNode1(L1, 3, 33);
	printLink1(L1);  // 11 22 33 
	freeList1(L1);

	// 测试头插法
	LinkList L2;
	InitLink1(&L2);
	headInsert(L2, 1);
	headInsert(L2, 2);
	headInsert(L2, 3);
	printLink1(L2);  // 3 2 1
	freeList1(L2);

	// 测试尾插法
	LinkList L3;
	InitLink1(&L3);
	tailInsert(L3, 1);
	tailInsert(L3, 2);
	tailInsert(L3, 3);
	printLink1(L3);  // 1 2 3


	// 测试删除
	deleteNode(L3, 3);
	printf("删除第三个结点后：");
	printLink1(L3);  // 删除第三个结点后：1 2

	//测试按值查找
	printf("数值1在第%d个位置\n", findPosByvalue(L3, 1));  //数值1在第1个位置

	//测试按位查找
	ElemType value;
	findValueByPos(L3, 1, &value);
	printf("第1个位置的值为%d\n", value);  //第1个位置的值为1

	freeList1(L3);

	return 0;
}

11. 完整代码

#include<stdio.h>
#include<stdlib.h>
/*
    带头结点的单链表
*/

typedef int ElemType;
typedef struct LNode {
	ElemType data;  //数据域
	struct LNode* next;  //指针域
}LNode, * LinkList;

//操作1—— 带头结点的初始化，即创建一个头结点，并让头指针指向头结点，头结点的next域初始化为NULL
void InitLink1(LinkList* L) {
	*L = (LinkList)malloc(sizeof(LNode));
	if (*L == NULL)
	{
		printf("内存分配失败!\n");
		exit(1);  //退出系统的操作
	}
	(*L)->next = NULL;
}


// 操作2——带头结点的插入操作
int insertLNode1(LinkList L, int pos, ElemType value) {
	//1. 判断插入位置是否合理
	if (pos < 1)
	{
		printf("插入位置不合法!\n");
		return -1;
	}
	//2. 找到待插入位置的前一个结点
	LinkList p = L;  // 定义一个新指针，让其刚开始指向头结点
	int i = 0;
	while (p != NULL && i < pos - 1) {
		p = p->next;
		i++;
	}
	//3. 判断
	if (p == NULL)
	{
		printf("插入位置不合法!\n");
		return -1;
	}
	
	LinkList s = (LinkList)malloc(sizeof(LNode));  //为要插入的数据分配空间
	if (s == NULL)
	{
		printf("内存分配失败!\n");
		return -2;
	}
	s->data = value;
	s->next = p->next;
	p->next = s;
	return 0;  //插入成功
}

// 操作2.1——带头结点的头插法建立单链表方法
int headInsert(LinkList L,ElemType value) {
	LinkList s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL)
	{
		printf("内存分配失败!\n");
		return -2;
	}
	s->data = value;
	s->next = L->next;
	L->next = s;
	return 0;  //插入成功
}

// 操作2.2——带头结点的尾插法建立单链表方法
int tailInsert(LinkList L,ElemType value) {
	LinkList s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL)
	{
		printf("内存分配失败!\n");
		return -2;
	}
	s->data = value;
	s->next = NULL;
	LinkList p = L;
	while (p->next != NULL) {
		p = p->next;
	}
	p->next = s;
	return 0;  //插入成功
}

// 操作3——删除第pos个位置上的值
int deleteNode(LinkList L, int pos) {
	if (pos < 1)
	{
		printf("删除位置不合理!\n");
		return -1;
	}
	LinkList p = L;
	int i = 0;
	while (p != NULL && i < pos - 1) {
		p = p->next;
		i++;
	}
	if (p == NULL || p->next == NULL)
	{
		printf("删除位置不合理!\n");
		return -1;
	}
	LinkList temp = p->next;
	p->next = temp->next;
	free(temp);
	return 0;  //删除成功
}

// 操作4——按位查找：查找第pos个位置上的value值
int findValueByPos(LinkList L, int pos, ElemType* value) {
	if (pos < 1)
	{
		printf("查找位置不合理!\n");
		return -1;
	}
	LinkList p = L->next;
	int i = 1;
	while (p != NULL && i < pos) {
		p = p->next;
		i++;
	}
	if (p == NULL)
	{
		printf("查找位置超出链表长度!\n");
		return -1;
	}
	*value = p->data;
	return 0; 
}

// 操作5——按值查找：查找value值在链表的第pos个位置
int findPosByvalue(LinkList L, ElemType value) {
	LinkList p = L->next;
	int pos = 1;
	while (p != NULL) {
		if (p->data == value)
		{
			return pos;
		}
		p = p->next;
		pos++;
	}
	return -1;  //查找失败
}

// 操作6——带头结点的单链表打印操作
void printLink1(LinkList L) {
	if (L == NULL || L->next == NULL)
	{
		printf("链表为空!\n");
		return;//提前结束函数
	}
	LinkList s = L->next;  //即让指针s指向了头结点后的第一格结点
	while (s != NULL) {
		printf("%d ", s->data);
		s = s->next;
	}
	printf("\n--------------------------------\n");
}

// 操作7——释放带头结点链表内存
void freeList1(LinkList L) {
	LinkList p = L;  // 定义一个临时指针指向头结点（和头指针一样，指向头结点，不同的是，该结点后续有变动）
	while (p != NULL) {
		LinkList temp = p;  // 在每次循环中，创建一个临时指针 temp，并将其指向当前结点 p。这是因为在释放当前结点之前，需要先保存该结点的地址，以便后续调用 free 函数释放其内存。
		p = p->next;
		free(temp);
	}
}



int main() {
	//测试插入方法
	LinkList L1;
	InitLink1(&L1);
	insertLNode1(L1, 1, 11);
	insertLNode1(L1, 2, 22);
	insertLNode1(L1, 3, 33);
	printLink1(L1);  // 11 22 33 
	freeList1(L1);

	// 测试头插法
	LinkList L2;
	InitLink1(&L2);
	headInsert(L2, 1);
	headInsert(L2, 2);
	headInsert(L2, 3);
	printLink1(L2);  // 3 2 1
	freeList1(L2);

	// 测试尾插法
	LinkList L3;
	InitLink1(&L3);
	tailInsert(L3, 1);
	tailInsert(L3, 2);
	tailInsert(L3, 3);
	printLink1(L3);  // 1 2 3


	// 测试删除
	deleteNode(L3, 3);
	printf("删除第三个结点后：");
	printLink1(L3);  // 删除第三个结点后：1 2

	//测试按值查找
	printf("数值1在第%d个位置\n", findPosByvalue(L3, 1));  //数值1在第1个位置

	//测试按位查找
	ElemType value;
	findValueByPos(L3, 1, &value);
	printf("第1个位置的值为%d\n", value);  //第1个位置的值为1

	freeList1(L3);

	return 0;
}

12. 运行截图


http://www.kler.cn/a/582282.html

相关文章：

  • deepseek R1提供的3d迷宫设计方案
  • 爬虫中一些有用的用法
  • PHP框架加载不上.env文件中的变量
  • Mysql 的 Query Cache为什么被废弃
  • Linux losetup循环设备
  • 阿里云ECS防勒索数据安全新选择：安当RDM防勒索组件——低成本、高可靠的主动防御方案
  • 网络防火墙是什么有什么用_网络防火墙：守护信息安全的重要屏障
  • 为你的python程序上锁：软件序列号生成器
  • 从零开始 | C语言基础刷题DAY1
  • 文件上传实验（upload-labs靶场实验）
  • 【Go沉思录】朝花夕拾：探究 Go 接口型函数
  • 烟火烟雾明火分割数据集labelme格式4065张2类别
  • Pycharm中脚本执行的3种模式——unittest框架、pytest框架及普通模式
  • Android Compose remember 详解
  • mysql表的创建
  • Go 语言编程全解析：Web 微服务与数据库十大专题深度精讲
  • 【商城实战(23)】筑牢安全防线，防范常见漏洞
  • 免费送源码：Java+PHP+MySQL “爱学术”期刊采编系统的设计与实现 计算机毕业设计原创定制
  • AI+视频监控电力巡检：EasyCVR视频中台方案如何赋能电力行业智能化转型
  • Photoshop 中如何快速抠图？