数据结构——考研笔记（三）线性表之单链表
文章目录
- 2.3 单链表
- 2.3.1 知识总览
- 2.3.2 什么是单链表
- 2.3.3 不带头结点的单链表
- 2.3.4 带头结点的单链表
- 2.3.5 不带头结点 VS 带头结点
- 2.3.6 知识回顾与重要考点
- 2.3.7 单链表的插入和删除
- 2.3.7.1 按位序插入（带头结点）
- 2.3.7.2 按位序插入（不带头结点）
- 2.3.7.3 指定结点的后插操作
- 2.3.7.4 指定结点的前插操作
- 2.3.7.5 按位序删除（带头结点）
- 2.3.7.6 知识回顾与重要考点
- 2.3.8 单链表的查找
- 2.3.8.1 按位查找
- 2.3.8.2 按值查找
- 2.3.8.3 知识回顾与重要考点
- 2.3.9 单链表的建立
- 2.3.9.1 尾插法
- 2.3.9.2 头插法
2.3 单链表
2.3.1 知识总览
2.3.2 什么是单链表
-
顺序表：
- 优点：可随机存取，存储密度高
- 缺点：要求大片连续空间，改变容量不方便
-
单链表：
- 优点：不要求大片连续空间，改变容量方便
- 缺点：不可随机存取，要消耗一定空间存放指针
-
用代码实现单链表
typedef struct LNode{ //定义单链表结点类型 ElemType data; //每个节点存放一个数据元素 struct LNode* next; //指针指向下一个节点 }LNode,*LinkList;2.3.3 不带头结点的单链表
#include typedef struct LNode { //定义单链表结点类型 int data; //每个节点存放一个数据元素 struct LNode* next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList& L) { L = NULL; //空表，暂时还没有任何结点 return true; } //判断单链表是否为空 bool Empty(LinkList L) { if (L == NULL) return true; else return false; } void test() { LinkList L; //声明一个指向单链表的指针 //初始化一个空表 InitList(L); //……后续代码…… }2.3.4 带头结点的单链表
#include typedef struct LNode { //定义单链表结点类型 int data; //每个节点存放一个数据元素 struct LNode* next; //指针指向下一个节点 }LNode, * LinkList; //初始化一个空的单链表 bool InitList(LinkList& L) { L = (LNode*)malloc(sizeof(LNode)); //分配一个头节点 if (L == NULL) //内存不足，分配失败 return false; L->next = NULL; //头结点之后暂时还没有节点 return true; } //判断单链表是否为空 bool Empty(LinkList L) { if (L->next == NULL) return true; else return false; } void test() { LinkList L; //声明一个指向单链表的指针 //初始化一个空表 InitList(L); //……后续代码…… }2.3.5 不带头结点 VS 带头结点
- 不带头结点：写代码更麻烦对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑对空表和非空表的处理需要用到不同的代码逻辑
- 带头结点：写代码更方便。
2.3.6 知识回顾与重要考点
2.3.7 单链表的插入和删除
2.3.7.1 按位序插入（带头结点）
- ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
- 代码展示
#include typedef struct LNode { //定义单链表结点类型 int data; //每个节点存放一个数据元素 struct LNode* next; //指针指向下一个节点 }LNode, * LinkList; //初始化一个空的单链表 bool InitList(LinkList& L) { L = (LNode*)malloc(sizeof(LNode)); //分配一个头节点 if (L == NULL) //内存不足，分配失败 return false; L->next = NULL; //头结点之后暂时还没有节点 return true; } //判断单链表是否为空 bool Empty(LinkList L) { if (L == NULL) return true; else return false; } //在第i个位置插入元素e(带头结点) bool ListInsert(LinkList& L, int i, int e) { if (i next; j++; } if (p == NULL) //i值不合法 return false; LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; //将结点s连到p之后 return true; //插入成功 } void main() { LinkList L; //声明一个指向单链表的指针 //初始化一个空表 InitList(L); //……后续代码…… }2.3.7.2 按位序插入（不带头结点）
- 代码展示
#include typedef struct LNode { //定义单链表结点类型 int data; //每个节点存放一个数据元素 struct LNode* next; //指针指向下一个节点 }LNode, * LinkList; //初始化一个空的单链表 bool InitList(LinkList& L) { L = (LNode*)malloc(sizeof(LNode)); //分配一个头节点 if (L == NULL) //内存不足，分配失败 return false; L->next = NULL; //头结点之后暂时还没有节点 return true; } //判断单链表是否为空 bool Empty(LinkList L) { if (L == NULL) return true; else return false; } //在第i个位置插入元素e(带头结点) bool ListInsert(LinkList& L, int i, int e) { if (i data = e; s->next = L; L = s; //头指针指向新节点 return true; } LNode* p; //指针p指向当前扫描到的结点 int j = 1; //当前p指向的是第几个结点 p = L; //L指向头结点，头结点是第0个结点（不存数据） while (p != NULL && j next; j++; } if (p == NULL) //i值不合法 return false; LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; //将结点s连到p之后 return true; //插入成功 } void main() { LinkList L; //声明一个指向单链表的指针 //初始化一个空表 InitList(L); //……后续代码…… }2.3.7.3 指定结点的后插操作
//后插操作：在p结点之后插入元素e bool InsertNextNode(LNode* p, int e) { if (p == NULL) return false; LNode* s = (LNode*)malloc(sizeof(LNode)); if (s == NULL) //内存分配失败 return false; s->data = e; //用结点s保存数据元素e s->next = p->next; p->next = s; //将结点s连到p之后 return true; }2.3.7.4 指定结点的前插操作
- 代码展示
//前插操作：在p结点之前插入元素e bool InsertPriorNode(LNode* p, int e) { if (p == NULL) //内存分配失败 return false; LNode* s = (LNode*)malloc(sizeof(LNode)); s->next = p->next; p->next = s; //新结点s连到p之后 s->data = p->data; //将p中元素复制到s中 p->data = e; //p中元素覆盖为e return true; }2.3.7.5 按位序删除（带头结点）
- ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
- 代码展示
//删除表中第i个元素 bool ListDelete(LinkList& L, int i, int& e) { if (i next; j++; } if (p == NULL) //i值不合法 return false; if (p->next == NULL) //第i-1个结点之后无其他结点 return false; LNode* q = p->next; //令q指向被删除结点 e = q->data; //用e返回元素的值 p->next = q->next; //将*q结点从链中“断开” free(q); //释放结点的存储空间 return true; //删除成功 }2.3.7.6 知识回顾与重要考点
2.3.8 单链表的查找
- GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
- LocalteElem(L,e)：按值查找。在表L中查找具有给定关键字值的元素。
2.3.8.1 按位查找
- 代码展示
//按位查找，返回第i个元素（带头结点） LNode* GetElem(LinkList L, int i) { if (i next; j++; } return p; }2.3.8.2 按值查找
- 代码展示
//按值查找，找到数据域==e的结点 LNode* LocateElem(LinkList L, int e) { LNode* p = L->next; //从第1个结点开始查找数据域为e的结点 while (p != NULL && p->data != e) p = p->next; return p; //找到后返回该结点指针，否则返回NULL }2.3.8.3 知识回顾与重要考点
2.3.9 单链表的建立
如果给你很多个数据元素（ElemType），要把它们存到一个单链表里边，怎么办呢？
step1：初始化一个单链表
step2：每次取一个数据元素，插入到表尾/表头
2.3.9.1 尾插法
- 代码展示
//尾插法 LinkList List_TailInsert(LinkList& L) { //正向建立单链表 int x; L = (LinkList)malloc(sizeof(LNode));//建立头结点 LNode* s, * r = L; //r为表尾指针 scanf("%d", &x); //输入结点的值 while (x != 9999) { //输入9999表示结束 s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; //r指向新的表尾结点 scanf("%d", &x); } r->next = NULL; //尾结点指针置空 return L; }2.3.9.2 头插法
- 代码展示
//头插法 LinkList List_HeadInsert(LinkList& L) { LNode* s; int x; L = (LNode*)malloc(sizeof(LNode)); //建立头结点 L->next = NULL; //初始化空链表 scanf_s("%d", &x); //输入结点的值 while (x != 9999) { //输入9999表示结束 s = (LNode*)malloc(sizeof(LNode));//创建新结点 s->data = x; s->next = L->next; L->next = s; //将新结点插入表中，L为头指针 scanf_s("%d", &x); } return L; }
- 代码展示
- 代码展示
- 代码展示
- 代码展示
- 代码展示
- ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
- 代码展示
- 代码展示
- 代码展示
- ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
-
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
