数据结构和算法(C)------4.线性表(2)单链表
2021/11/21 17:10:22
本文主要是介绍数据结构和算法(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)单链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc