C/C++教程
数据结构和算法（C）------4.线性表（2）单链表
本文主要是介绍数据结构和算法（C）------4.线性表（2）单链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
目录
1. 链式存储结构
1.1 定义
1.2 实现方式
1.3 与链式存储有关的术语
1.4 链表（链式存储结构）的特点和优缺点
1.4.1 特点
1.4.2 优点
1.4.3 缺点
2. 单链表的实现
2.1 单链表的存储结构定义
2.2 初始化(构造一个空表 )
2.2.1 算法步骤
2.2.2 算法描述
2.3 销毁（删除整个表）
2.4 清空（删除表中所有数据）
2.5 求表长
2.6 判断表是否为空
2.7 取值（根据位置i获取相应位置数据元素的内容）
2.7.1 算法步骤
2.7.2 算法描述（用e返回i位置上的数据）
2.8 按值查找（返回位置i,不存在返回0）
2.8.1 算法步骤
2.8.2 算法描述
2.8.3 复杂度分析
2.9 插入（插在第 i 个结点之前）
2.9.1 算法步骤
2.9.2 算法描述
2.9.3 复杂度分析
2.10 删除（删除第 i 个结点）
2.10.1 算法步骤
2.10.2 算法描述
2.10.3 复杂度分析
2.11 单链表的建立（头插法）
2.11.1 算法步骤
2.11.2 算法描述
2.12 单链表的建立（尾插法）
2.12.1 算法步骤
2.12.2 算法描述
2.13 main函数调用
3. 完整代码
1. 链式存储结构
1.1 定义
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序映像或链式映像。
1.2 实现方式
各节点有两个域组成：数据域和指针域
数据域：存储数据
指针域：存储后续节点的地址
1.3 与链式存储有关的术语
- 结点
- 链表
- 单链表、双链表、循环链表
- 头指针、头结点和首元结点
1、结点：数据元素的存储映像。由数据域和指针域两部分组成
2、链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
3、单链表、双链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；首尾相接的链表称为循环链表
4、头指针是指向链表中第一个结点的指针；
首元结点是指链表中存储第一个数据元素a1的结点；
头结点是在链表的首元结点之前附设的一个结点，数据域内只放空表标志和表长等信息
5. 单链表有头结点和无头结点的结构示意
思考：
（1）如何表示空表？
有头结点时，当头结点的指针域为空时表示空表。
无头结点时，头指针为空时为空表。
（2）在链表中设置头结点有什么好处？
①便于首元结点的处理
首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
②便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
（3）头结点的数据域内装的是什么？
头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
1.4 链表（链式存储结构）的特点和优缺点
1.4.1 特点
- 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
- 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。
这种存取元素的方法被称为顺序存取法
1.4.2 优点
1.数据元素的个数可以自由扩充
2.插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
1.4.3 缺点
- 存储密度小
- 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问
2. 单链表的实现
2.1 单链表的存储结构定义
typedef int ElemType;
typedef int Status;
enum StatusCode
{
TRUE = 1,
FALSE = 0,
OK = 1,
ERROR = 0,
INFEASIBLE = -1,
OVERFLOW = -2
};
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, *LinkList;
2.2 初始化(构造一个空表 )
2.2.1 算法步骤
-
生成新结点作头结点，用头指针L指向头结点。
-
头结点的指针域置空。
2.2.2 算法描述
Status InitList(LinkList* pL)
{
*pL = (LinkList)malloc(sizeof(LNode));
if ((*pL) == NULL)
{
perror("InitList");
return ERROR;
}
(*pL)->next = NULL;
return OK;
}
其中，参数使用的是LinkList*类型的参数，是二级指针，因为初始化需要对表进行修改，而表是用头指针表示的，所以需要用到二级指针，将表地址传进去。解引用就获得头指针。
2.3 销毁（删除整个表）
Status DestoryList(LinkList* pL)
{
LNode* p = (LinkList)malloc(sizeof(LNode));
while (*pL)
{
p = *pL;
*pL = (*pL)->next;
free(p);
}
p = NULL;
return OK;
}
2.4 清空（删除表中所有数据）
Status ClearList(LinkList* pL)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
LNode* q = (LNode*)malloc(sizeof(LNode));
p = (*pL)->next; //p指向首元结点
while (p) {
q = p->next;
free(p); //释放当前p所指向的空间，避免内存溢出
p = q;
}
(*pL)->next = NULL;
return OK;
}
2.5 求表长
int ListLength(LinkList L)
{
LNode* p = L->next;
int length = 0;
while (p != NULL)
{
p = p->next;
length++;
}
return length;
}
2.6 判断表是否为空
Status IsEmpty(LinkList L)
{
if (L->next == NULL)
return TRUE;
return FALSE;
}
2.7 取值（根据位置i获取相应位置数据元素的内容）
2.7.1 算法步骤
- 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。
- j 做计数器，累计当前扫描过的结点数，j 初值为1
- 当p指向扫描到的下一结点时，计数器j加1
- 当j = i 时，p所指的结点就是要找的第i个结点
2.7.2 算法描述（用e返回i位置上的数据）
Status GetElem(LinkList L, int i, ElemType* e)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
p = L->next;
int j = 1;
while (p && j < i)
{
p = p->next;
j++;
} //找到第i-1位置
if (!p || j > i)return ERROR;
*e = (p->data);
return OK;
}
2.8 按值查找（返回位置i,不存在返回0）
2.8.1 算法步骤
- 从第一个结点起，依次和e相比较。
- 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”
- 如果查遍整个链表都没有找到其值和e相等的元素，则返回0
2.8.2 算法描述
int LocateElem(LinkList L, ElemType e)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
p = L->next;
int loc = 1;
while (p && (p->data != e))
{
p = p->next;
loc++;
}
if (p)
return loc;
else
return 0;
}
2.8.3 复杂度分析
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)
2.9 插入（插在第 i 个结点之前）
2.9.1 算法步骤
- 找到i-1元素存储位置p
-
生成一个新结点*s
-
将新结点*s的数域置为插入的元素
-
新结点*s的指针域指向第i元素
-
令结点*p的指针域指向新结点*s
2.9.2 算法描述
Status InsertList(LinkList* pL, int i, ElemType e)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
p = *pL;
int j = 0;
while (p && (j < i - 1))
{
p = p->next;
j++;
}
if (!p || j > i - 1)return ERROR;
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
2.9.3 复杂度分析
因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
2.10 删除（删除第 i 个结点）
2.10.1 算法步骤
- 找到i-1元素存储位置p
- 保存要删除的结点的值
- 令p-＞next指向第i+1元素
- 释放结点i位置元素空间
2.10.2 算法描述
Status DeleteList(LinkList* pL, int i, ElemType* e)
{
LNode* p = *pL;
int j = 0;
while ((p->next) && j < (i - 1))
{
p = p->next;
j++;
}
if (!(p->next) || (j > i - 1))
return ERROR;
LNode* q = p->next;
p->next = q->next;
*e = q->data; //保存被删除的数据
free(q);
q = NULL;
return OK;
}
思考：能不能直接p->next = p->next->next ？
可以，但是第i个元素空间没有释放，并且也不知道删除了什么元素
2.10.3 复杂度分析
因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
2.11 单链表的建立（头插法）
2.11.1 算法步骤
- 生成新结点
- 将读入数据存放到新结点的数据域中
- 将该新结点插入到链表的前端
2.11.2 算法描述
void CreateList_H(LinkList* pL, int n)
{
*pL = (LinkList)malloc(sizeof(LNode));
(*pL)->next = NULL;
for (int i = 0; i < n; i++)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
scanf("%d", &(p->data));
p->next = (*pL)->next;
(*pL)->next = p;
}
}
2.12 单链表的建立（尾插法）
2.12.1 算法步骤
- 从一个空表 L 开始，将新结点逐个插入到链表的尾部，尾指针 r 指向链表的尾结点。
- 初始时， r 同 L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后， r 指向新结点。
2.12.2 算法描述
void CreateList_T(LinkList* pL, int n)
{
*pL = (LinkList)malloc(sizeof(LNode));
(*pL)->next = NULL;
LNode* tail = (LNode*)malloc(sizeof(LNode));//尾指针
tail = *pL;
for (int i = 0; i < n; i++)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
scanf("%d", &(p->data));
p->next = NULL;
tail->next = p;
tail = p; //让尾指针始终指向最后一个元素
}
}
2.13 main函数调用
int main()
{
LinkList La; //定义链表
CreateList_T(&La, 20);//1,2,3,...,20
printf("%d\n", IsEmpty(La));
int La_len = ListLength(La);
for (int i = 1; i <= La_len; i++)
{
int e;
GetElem(La, i, &e);
printf("%d ", e);
}
printf("%d\n", La_len);
printf("%d\n", LocateElem(La, 10));
int a = 0;
DeleteList(&La, 8, &a);
printf("%d\n", a);
printf("%d\n", ListLength(La));
ClearList(&La);
printf("%d\n", ListLength(La));
printf("%d\n", DestoryList(&La));
return 0;
}
3. 完整代码
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
enum StatusCode
{
TRUE = 1,
FALSE = 0,
OK = 1,
ERROR = 0,
INFEASIBLE = -1,
OVERFLOW = -2
};
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, *LinkList; //LinkList为指向结构体Lnode的指针类型
//初始化链表
Status InitList(LinkList* pL)
{
*pL = (LinkList)malloc(sizeof(LNode));
if ((*pL) == NULL)
{
perror("InitList");
return ERROR;
}
(*pL)->next = NULL;
return OK;
}
//判断单链表是否为空
Status IsEmpty(LinkList L)
{
if (L->next == NULL)
return TRUE;
return FALSE;
}
//销毁单链表,头结点也销毁
Status DestoryList(LinkList* pL)
{
LNode* p = (LinkList)malloc(sizeof(LNode));
while (*pL)
{
p = *pL;
*pL = (*pL)->next;
free(p);
}
p = NULL;
return OK;
}
//清空单链表
Status ClearList(LinkList* pL)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
LNode* q = (LNode*)malloc(sizeof(LNode));
p = (*pL)->next; //p指向首元结点
while (p) {
q = p->next;
free(p);
p = q;
}
(*pL)->next = NULL;
return OK;
}
//求单链表的长度
int ListLength(LinkList L)
{
LNode* p = L->next;
int length = 0;
while (p != NULL)
{
p = p->next;
length++;
}
return length;
}
//单链表的取值
Status GetElem(LinkList L, int i, ElemType* e)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
p = L->next;
int j = 1;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i)return ERROR;
*e = (p->data);
return OK;
}
//按值查找 返回地址
//LNode* LocateElem(LinkList L,ElemType e)
//{
// LNode* p = L->next;
// while (p&&(p->data != e))
// p = p->next;
// return p;
//}
// 按值查找 返回位置序号
int LocateElem(LinkList L, ElemType e)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
p = L->next;
int loc = 1;
while (p && (p->data != e))
{
p = p->next;
loc++;
}
if (p)
return loc;
else
return 0;
}
//在第i个位置插入元素e
Status InsertList(LinkList* pL, int i, ElemType e)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
p = *pL;
int j = 0;
while (p && (j < i - 1))
{
p = p->next;
j++;
}
if (!p || j > i - 1)return ERROR;
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
//
Status DeleteList(LinkList* pL, int i, ElemType* e)
{
LNode* p = *pL;
int j = 0;
while ((p->next) && j < (i - 1))
{
p = p->next;
j++;
}
if (!(p->next) || (j > i - 1))
return ERROR;
LNode* q = p->next;
p->next = q->next;
*e = q->data; //保存被删除的数据
free(q);
q = NULL;
return OK;
}
//头插法创建链表
void CreateList_H(LinkList* pL, int n)
{
*pL = (LinkList)malloc(sizeof(LNode));
(*pL)->next = NULL;
for (int i = 0; i < n; i++)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
scanf("%d", &(p->data));
p->next = (*pL)->next;
(*pL)->next = p;
}
}
//尾插法创建链表
void CreateList_T(LinkList* pL, int n)
{
*pL = (LinkList)malloc(sizeof(LNode));
(*pL)->next = NULL;
LNode* tail = (LNode*)malloc(sizeof(LNode));//尾指针
tail = *pL;
for (int i = 0; i < n; i++)
{
LNode* p = (LNode*)malloc(sizeof(LNode));
scanf("%d", &(p->data));
p->next = NULL;
tail->next = p;
tail = p; //让尾指针始终指向最后一个元素
}
}
int main()
{
LinkList La; //定义链表
CreateList_T(&La, 20);//1,2,3,...,20
printf("%d\n", IsEmpty(La));
int La_len = ListLength(La);
for (int i = 1; i <= La_len; i++)
{
int e;
GetElem(La, i, &e);
printf("%d ", e);
}
printf("%d\n", La_len);
printf("%d\n", LocateElem(La, 10));
int a = 0;
DeleteList(&La, 8, &a);
printf("%d\n", a);
printf("%d\n", ListLength(La));
ClearList(&La);
printf("%d\n", ListLength(La));
printf("%d\n", DestoryList(&La));
return 0;
}
这篇关于数据结构和算法（C）------4.线性表（2）单链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
新能源车企如何通过CRM工具优化客户关系管理，增强客户忠诚度与品牌影响力12-23
-
原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理12-23
-
DevExpress 怎么实现右键菜单（Context Menu）显示中文？-icode9专业技术文章分享12-23
-
怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享12-22
-
el-tabs 组件只被引用了一次，但有时会渲染两次是什么原因？-icode9专业技术文章分享12-22
-
wordpress有哪些好的安全插件？-icode9专业技术文章分享12-22
-
wordpress如何查看系统有哪些cron任务？-icode9专业技术文章分享12-22
-
Svg Sprite Icon教程：轻松入门与应用指南12-21
-
Excel数据导出实战：新手必学的简单教程12-20
-
RBAC的权限实战：新手入门教程12-20
-
Svg Sprite Icon实战：从入门到上手的全面指南12-20
-
LCD1602显示模块详解12-20
-
利用Gemini构建处理各种PDF文档的Document AI管道12-20
-
在 uni-app 中怎么实现 WebSocket 的连接、消息发送和接收？-icode9专业技术文章分享12-20
-
indices.breaker.request.limit 默认是多少？-icode9专业技术文章分享12-20
栏目导航
