程序员经验分享-hwhale

【数据结构 c语言版 】线性表的链式表示和实现

2023-11-06

目录

一  单链表的表示和实现

1.单链表的存储结构

1.1.  头指针、头结点与首元结点

1.2.  带头结点单链表和不带头结点单链表的比较

2. 单链表的初始化

3.  单链表的长度

4.  单链表的插入

5.  单链表的删除

6.  单链表的查看

7.  单链表的撤销

完整代码

二  循环单链表

三  双向链表

1.  双向链表表的存储结构、初始化

2.  双向链表的插入、删除

结点：由数据元素域和一个或若干个指针域组成的一个结构体。
链表：链式存储结构的线性表。

一  单链表的表示和实现

1.单链表的存储结构

typedef char DataType;
typedef struct Node
{	//单链表的储存结构
	DataType data; //存放数据
	struct Node* next;  //存放指针
}SLNode;

1.  每个存储结点都包含两部分：数据域，指针域
2.  在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

1.1.  头指针、头结点与首元结点

 头指针是指向链表中第一个结点

头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。
首元结点是指链表中存储线性表第一个数据元素a0的结点。

1.2.  带头结点单链表和不带头结点单链表的比较

  1）  带头结点的单链表的第一个数据元素插入时，其插入在头结点后。

   2）  不带头结点的单链表的第一个数据元素插入时，其插入在头指针后。

   3） 不带头结点的单链表的其余数据元素插入时，其插入在前一节点后。

 

   4）  删除带头结点的单链表的第一个数据时，头结点指针指向第二个数据

   5） 删除不带头结点的单链表的第一个数据时，头指针指向第二个数据

 结论：插入操作时，有头结点链表方便

单链表一般构造成带头结点的单链表

2. 单链表的初始化

malloc(m)函数:向系统动态申请m字节长度的地址空间，并返回这段空间的首地址；
free(p)函数:释放指针p所指变量的存储空间，即彻底删除一个变量。
sizeof(x)运算符:计算变量x的长度（字节数）；
以上有库函数/算符都在<malloc.h> 中

void ListInitiate(SLNode** hear)
{	//单链表的初始化
	*hear = (SLNode*)malloc(sizeof(SLNode));
	(* hear)->next = NULL;  //链尾标记NULL
}

3.  单链表的长度

int ListLength(SLNode* hear)
{	//单链表的长度
	SLNode* p = hear;  //p 指向头结点
	int size;
	for (size = 0; p->next != NULL; size++)
	{
		p = p->next;
	}
	return size;
}

4.  单链表的插入

实现步骤：

1.  将插入处前一节点指针指向所插入节点的指针

   （即  将所插入节点的指针指向插入处的节点，防止插入处节点丢失）；

2.  将插入处前一节点指针指向所插入节点。

          x 节点先 生成再使用。

int ListInsert(SLNode* head, int i, DataType x)
{	//在顺序表的第i个位置之前插入数据值x
	//插入成功返回1，插入失败返回0
	SLNode* p, * q;
	p = head;
	int j = 0;
	for (j; p->next != NULL && j < i - 1; j++)
	{
		p = p->next;
	}
	if (j != i - 1)
	{
		printf("插入地方错误！\n");
		return 0;
	}
	q = (SLNode*)malloc(sizeof(SLNode));
	q->data = x;
	q->next = p->next;
	p->next = q;
	return 1;

}

5.  单链表的删除

实现步骤：

1.  将要删除节点前一节点的指针指向删除节点的后一节点

   （即  使得要没有指针指向删除节点）；

2.  释放删除节点。

int ListDelete(SLNode* head, int i, DataType* x)
{	//删除顺序表L中位置i的数据元素值并存放到参数x中
	//删除成功返回1，失败返回0
	SLNode* p, * s;
	p = head;
	int j = 0;
	for (j; p->next != NULL && j < i - 1; j++)
	{
		p = p->next;
	}
	if (j != i - 1)
	{
		printf("删除位置错误！\n");
		return 0;
	}
	s = p->next;
	*x = s->data;
	p->next = s->next;
	free(s);
	return 1;

}

6.  单链表的查看

int ListGet(SLNode* head, int i, DataType* x)
{	//取顺序表中第i个元素存于x中
	//取出成功返回1，失败返回0
	SLNode* p;
	p = head;
	int j = 0;
	for (j; p->next != NULL && j < i; j++)
	{
		p = p->next;
	}
	if (j != i)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	*x = p->data;
	return 1;

}

7.  单链表的撤销

void Destroy(SLNode **head)
{	//撤销单链表
	SLNode* p, * q;
	p = *head;
	for (p; p != NULL; free(q))
	{
		q = p;
		p = p->next;

	}
	*head = NULL;
}

完整代码

#include<stdio.h>
#include<malloc.h>

typedef char DataType;
typedef struct Node
{	//单链表的储存结构
	DataType data; //存放数据
	struct Node* next;  //存放指针
}SLNode;

void ListInitiate(SLNode** hear)
{	//单链表的初始化
	*hear = (SLNode*)malloc(sizeof(SLNode));
	(* hear)->next = NULL;  //链尾标记NULL
}

int ListLength(SLNode* hear)
{	//单链表的长度
	SLNode* p = hear;  //p 指向头结点
	int size;
	for (size = 0; p->next != NULL; size++)
	{
		p = p->next;
	}
	return size;
}

int ListInsert(SLNode* head, int i, DataType x)
{	//在顺序表的第i个位置之前插入数据值x
	//插入成功返回1，插入失败返回0
	SLNode* p, * q;
	p = head;
	int j = 0;
	for (j; p->next != NULL && j < i - 1; j++)
	{
		p = p->next;
	}
	if (j != i - 1)
	{
		printf("插入地方错误！\n");
		return 0;
	}
	q = (SLNode*)malloc(sizeof(SLNode));
	q->data = x;
	q->next = p->next;
	p->next = q;
	return 1;

}

int ListDelete(SLNode* head, int i, DataType* x)
{	//删除顺序表L中位置i的数据元素值并存放到参数x中
	//删除成功返回1，失败返回0
	SLNode* p, * s;
	p = head;
	int j = 0;
	for (j; p->next != NULL && j < i - 1; j++)
	{
		p = p->next;
	}
	if (j != i - 1)
	{
		printf("删除位置错误！\n");
		return 0;
	}
	s = p->next;
	*x = s->data;
	p->next = s->next;
	free(s);
	return 1;

}

int ListGet(SLNode* head, int i, DataType* x)
{	//查看
    //取顺序表中第i个元素存于x中
	//取出成功返回1，失败返回0
	SLNode* p;
	p = head;
	int j = 0;
	for (j; p->next != NULL && j < i; j++)
	{
		p = p->next;
	}
	if (j != i)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	*x = p->data;
	return 1;

}

void Destroy(SLNode **head)
{	//撤销单链表
	SLNode* p, * q;
	p = *head;
	for (p; p != NULL; free(q))
	{
		q = p;
		p = p->next;

	}
	*head = NULL;
}

void main(void)
{
	SLNode* head;
	DataType x;
	ListInitiate(&head);
	ListInsert(head, 1, 'a');
	ListInsert(head, 2, 'b');
	ListInsert(head, 3, 'c');
	printf("%d\n", ListLength(head));
	ListGet(head, 3, &x);
	printf("%c\n", x);
	ListDelete(head, 2, &x);
	printf("%d\n", ListLength(head));
	ListGet(head, 2, &x);
	printf("%c\n", x);
	Destroy(&head);

}

二  循环单链表

在初始化函数中，将语句(*head)->next = NULL改为(*head)->next =head。

void ListInitiate(SLNode** hear)
{	//单链表的初始化
	*hear = (SLNode*)malloc(sizeof(SLNode));
	(* hear)->next = hear;  //链尾标记hear
}

 在删除与查看函数中，将更改其判断语句。

int ListDelete(SLNode* hear, int i, DataType* x)
{	//删除
	SLNode* p, * q;
	p = hear;
	int j = 0;
	for (j; j < i - 1; j++)
	{
		p = p->next;
		if (p->next == hear)
		{
			p = p->next;
		}
	}
	
	if (j != i - 1)
	{
		printf("删除位置错误！\n");
		return 0;
	}
	q = p->next;
	*x = q->data;
	p->next = q->next;
	free(q);
	return 1;

}

int ListGet(SLNode* head, int i, DataType* x)
{	//查看
	SLNode* p;
	p = head;
	int j = 0;
	for (j; j < i - 1; j++)
	{
		p = p->next;
		if (p->next == head)
		{
			p = p->next;
		}
	}
	
	if (j != i - 1)
	{
		printf("参数！不合法！\n");
		return 0;
	}
	*x = (p->next)->data;
	return 1;
}

在撤销函数中， 增加一标志点以判断循环链表已清空。

void Destroy(SLNode** head)
{	//撤销
	SLNode* p, * q;
	p = *head;
	int i = 0;
	for (p; i != 0 && p->next != *head; free(q))
	{
		q = p;
		p = p->next;
		i++;

	}
	*head = NULL;
}

完整代码，输出卡牌游戏，卡牌第一个位置输出 1 ，第二个位置输出 2 ，以此类推。

#include<stdio.h>
#include<malloc.h>

typedef char DataType;
typedef struct Node
{	
	DataType data; //存放数据
	struct Node* next;  //存放指针
}SLNode;

void ListInitiate(SLNode** head)
{	//初始化
	*head = (SLNode*)malloc(sizeof(SLNode));
	(*head)->next = *head;  //链尾标记hear
}

int ListLength(SLNode* hear)
{	//长度
	SLNode* p = hear;
	int size;
	for (size = 0; p->next != hear; size++)
		p = p->next;
	return size;
}


int ListInsert(SLNode* head, int i, DataType x)
{	//插入
	SLNode* p, * q;
	p = head;
	int j = 0;
	for (j; p->next != head && j < i - 1; j++)
	{
		p = p->next;
	}
	if (j != i - 1)
	{
		printf("插入地方错误！\n");
		return 0;
	}
	q = (SLNode*)malloc(sizeof(SLNode));
	q->data = x;
	q->next = p->next;
	p->next = q;
	return 1;

}

int ListDelete(SLNode* hear, int i, DataType* x)
{	//删除
	SLNode* p, * q;
	p = hear;
	int j = 0;
	for (j; j < i - 1; j++)
	{
		p = p->next;
		if (p->next == hear)
		{
			p = p->next;
		}
	}
	
	if (j != i - 1)
	{
		printf("删除位置错误！\n");
		return 0;
	}
	q = p->next;
	*x = q->data;
	p->next = q->next;
	free(q);
	return 1;

}

int ListGet(SLNode* head, int i, DataType* x)
{	//查看
	SLNode* p;
	p = head;
	int j = 0;
	for (j; j < i - 1; j++)
	{
		p = p->next;
		if (p->next == head)
		{
			p = p->next;
		}
	}
	
	if (j != i - 1)
	{
		printf("参数！不合法！\n");
		return 0;
	}
	*x = (p->next)->data;
	return 1;
}

void Destroy(SLNode** head)
{	//撤销
	SLNode* p, * q;
	p = *head;
	int i = 0;
	for (p; i != 0 && p->next != *head; free(q))
	{
		q = p;
		p = p->next;
		i++;

	}
	*head = NULL;
}


void main(void)
{
	SLNode* hear;
	DataType x;
	ListInitiate(&hear);
	ListInsert(hear, 1, '1');
	ListInsert(hear, 2, 'K');
	ListInsert(hear, 3, '2');
	ListInsert(hear, 4, '8');
	ListInsert(hear, 5, '3');
	ListInsert(hear, 6, '0');
	ListInsert(hear, 7, '4');
	ListInsert(hear, 8, 'j');
	ListInsert(hear, 9, '5');
	ListInsert(hear, 10, '9');
	ListInsert(hear, 11, '6');
	ListInsert(hear, 12, 'q');
	ListInsert(hear, 13, '7');

	ListDelete(hear, 1, &x);
	printf("%c", x);
	ListDelete(hear, 2, &x);
	printf("%c", x);
	ListDelete(hear, 3, &x);
	printf("%c", x);
	ListDelete(hear, 4, &x);
	printf("%c", x);
	ListDelete(hear, 5, &x);
	printf("%c", x);
	ListDelete(hear, 6, &x);
	printf("%c", x);
	ListDelete(hear, 7, &x);
	printf("%c", x);
	ListDelete(hear, 8, &x);
	printf("%c", x);
	ListDelete(hear, 9, &x);
	printf("%c", x);
	ListDelete(hear, 10, &x);
	printf("%c", x);
	ListDelete(hear, 11, &x);
	printf("%c", x);
	ListDelete(hear, 12, &x);
	printf("%c", x);
	ListDelete(hear, 13, &x);
	printf("%c", x);
	Destroy(&hear);



}

三  双向链表

双向链表：链表中每个结点除后继指针域和数据域外还有一个前驱指针域。
它有带头结点和不带头结点，循环和非循环结构。双向链表是解决查找前驱结点问题的有效途径。

1.  双向链表表的存储结构、初始化

 初始化时，前驱指针和后继指针各自构成自己的循环单链表。

2.  双向链表的插入、删除

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构 C语言版

数据结构

c语言

链表

【数据结构 c语言版 】线性表的链式表示和实现 的相关文章

  • CSV简单了解

    1 CSV介绍 CSV全称是Comma Separate Values 这种文件格式可以作为不同程序之间的数据交互的格式 csv就是一种纯文本文件 如 txt doc等 即是一组字符序列 字符之间已英文字符的逗号或制表符 Tab 分隔 语法

  • Python数据结构-----leetcode232.用栈实现队列

    目录 前言 方法讲解 示例 代码实现 232 用栈实现队列 前言 我们都知道队列的特征是先进先出 就跟排队一样先到先得 而栈的特征是后进后出 那这里我们怎么去通过两个栈来实现一个队列的功能呢 这一期我们一起来学习吧 方法讲解 这里需要准备好

  • 订单业务中的重要问题：超卖问题的解决方案

    订单业务中的重要问题 超卖问题的解决方案 我在做过的一些项目中都涉及到了订单的业务 如果你的项目中有关于订单的业务模块 那肯定说明你的项目中有卖商品的功能 所以有买卖场景就面临一个很常见的一个问题 那就是超卖问题 下面我就整理一下我在做项目

  • MyBatis与JDBC连接数据库所使用的url之间的差异

    1 在JDBC连接里是这样的 连接无误 2 在Mybatis里配置要这样 3 主要区别 说明 JDBC 方式连接 MySQL 不需要对 进行转义 而在Mybatis里要求一定要对 转义 4 如果是在properties文件里 不用转义的 在

  • IP静态路由实验报告

    一 将192 168 1 0 24划分为4个网段 192 168 1 0 26 192 168 1 64 26 192 168 1 128 26 192 168 1 192 26 1 取192 168 1 0 26继续划分 为主干道添加IP

随机推荐

  • Spring 加载、解析applicationContext.xml 流程

    概要 Spring 框架使用了BeanFactory 进行加载 xml 和生成 bean 实例 下面我们分析下Spring加载xml文件的过程 spring 版本是最新的 4 3 9 release 版本 示例 XmlBeanFactory

  • java 转换tif图片为jpg，解决转换后颜色异常问题

    java 转换tif图片为jpg 解决转换后颜色异常问题 说明 正常情况下 tif转换jpg图片会出现颜色失真 丢失部分颜色 原因是两种图片的色彩模式不同 jpg默认使用的是RGB色彩模式 TIF默认使用的是CMYK色彩模式 RGB的色域比

  • 有关“ModuleNotFoundError: No module named ‘flask._compat’”错误的解决过程

    在进行flask安装后 运行程序的过程中出现了 ModuleNotFoundError No module named flask compat 的错误 在查询了多个网站后给出了不同的答案 其报错原因是flask版本过高导致无法识别该语法

  • 仿京东 项目笔记2（注册登录）

    这里写目录标题 1 注册页面 1 1 注册 登录页面 接口请求 1 2 Vue开发中Element UI的样式穿透 1 2 1 v deep的使用 1 2 2 elementUI Dialog内容区域显示滚动条 1 3 注册页面 步骤条和表

  • 服务器i5 和e系列,e5和i5有什么区别

    两个系列的处理器主要在设计规格和面向范围方面存在区别 设计规格上 前者核心数更多 多线程能力更强 但睿频能力相对较弱 后者核心数较少 多线程能力不如前者 但睿频能力更强 面向范围上 前者主要面向服务器 嵌入式等企业设备 后者主要面向消费级硬

  • (LeetCode)全排列

    目录 题目要求 题目理解以及思路分析 代码分部讲解 第一部分 第二部分 题目要求 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 你可以 按任意顺序 返回答案 示例 1 输入 nums 1 2 3 输出 1 2 3 1 3

  • 规则引擎Drools使用 第十一篇 Drools 的高级语法之LHS增强

    前面我们已经知道了在规则体中的LHS部分是介于when和then之间的部分 主要用于模式匹配 只有匹配结果为true时 才会触发RHS部分的执行 下面我们会针对LHS部分学习几个新的用法 目录 复合值限制in not in 条件元素eval

  • 升压电路(BOOST)与降压电路(BUCK)

    一 电路中产生电流的条件是 1 电路里必须有电源供电 2 电路必须形成闭合回路 降压元器件 升降压电路构成的核心元器件 1 电感 储存能量 电感是无法突变的 工作状态是线性的 2 二极管 3 mos管 首先先分清楚mos是N mos还是P

  • Qt全局宏和变量

    1 Qt 全局宏定义 Qt版本号 QT VERSION major lt lt 16 minor lt lt 8 patch 检测版本号 QT VERSION CHECK major minor patch major lt lt 16 m

  • virtio代码分析(一)-qemu部分

    virtio内容众多 代码分布于qemu linux dpdk等中 而且分为frontend和backend 可以运行于userspace也可以运行于kernelspace 极其难以理解 不看代码只看原理性文档往往流于表面 只有真正看懂了代

  • 大数据准备——安装JDK

    1 解压Linux版本的JDK压缩包 命令行敲入 mkdir home software cd home software rz 上传jdk tar包 这里添加自己tar包的名字 如果rz命令不能使用 先执行yum install lrzs

  • C语言关键字解析

    在C语言中有32个关键字 如下表所示 释 1 声明 1 告诉编译器 这个名字已经匹配到一块内存上 2 告诉编译器 这个名字已经预定了 其他地方再也不能用它来作为变量名或对象名 2 定义 编译器创建一个对象 为这个对象分配一块内存空间 并给它

  • 前端 配色网站 自用 免费 颜色很全

    1 中国色彩 http zhongguose com 3 ColorHex https www colorhexa com 4 优色网配色专区 https color uisdc com 4 ColorDrop https www colo

  • cuda学习

    GPU中有多个流处理器SM 当一个线程块被指定给一个SM后 里面的线程会被划分成线程束 32个线程 在SM上交替运行 也就是说SM上一个时刻只有一个线程束在运行 函数修饰符 global 表示该函数只能在GPU上运行 但是可以从CPU或者G

  • qt.network.ssl: QSslSocket: cannot call unresolved function SSLv23_client_method

    最近在做一个网络音乐播放器时 由于出现qt network ssl QSslSocket cannot call unresolved function SSLv23 client method 而不能播放网络歌曲 上网搜了半天 都说要在电

  • Jmeter(二十七) - 从入门到精通 - Jmeter Http协议录制脚本（详解教程）

    1 简介 LoadRunner的录制功能让性能测试脚本编写对于不懂代码的人变成了一件容易上手的事 但是由于LoadRunner收费高昂 庞大 一般企业很少用 除非必须使用 Jmeter作为性能测试中的王者也少不了提供录制功能 Jmeter的

  • 靠！我被项目经理和同事嘲笑了，因为不会远程debug调试...

    大家好 我是曹尼玛 刚从培训机构毕业 去一家单位上班一周了 这一周项目经理让我熟悉了项目业务 架构和设计 不算难 凭借我培训机构第一名的成绩 还是很顺溜 今天项目经理把同事们叫到一起 说线上438x6项目出现奇葩问题 但是开发环境初步测试没

  • SSM框架练习—主从表的业务模型

    需要实现的整体功能 系统的登录并进行用户名的校验 团购信息的列表展示 团购信息的添加 团购信息的检索 1 数据库创建 CREATE DATABASE mydb USE mydb drop table if exists vaccunit C

  • MySQL数据库关于表的一系列操作

    MySQL中的数据类型 varchar 动态字符串类型 最长255位 可以根据实际长度来动态分配空间 例如 varchar 100 char 定长字符串 最长255位 存储空间是固定的 例如 char 10 int 整数型 最长11位 lo

  • 【数据结构 c语言版 】线性表的链式表示和实现

    目录 一 单链表的表示和实现 1 单链表的存储结构 1 1 头指针 头结点与首元结点 1 2 带头结点单链表和不带头结点单链表的比较 2 单链表的初始化 3 单链表的长度 4 单链表的插入 5 单链表的删除 6 单链表的查看 7 单链表的撤

热门标签