admin管理员组文章数量:1487745
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
1.单链表的定义 1.1顺序表:
每个结点中只存放数据元素
优点:可随机存取,存储密度高
缺点:要求大片连续空间,改变容量不方便
1、顺序表定义代码回忆
代码语言:javascript代码运行次数:0运行复制#define MaxSize 10 // 定义最大长度
typedef struct{
ElemType data[MaxSize]; // 用静态的“数组”存放数据元素
int length; // 顺序表的当前长度
}SqList;
#include <stdio.h>
#define MaxSize 10
typedef struct{
int data[MaxSize];
int length;
}SqList;
void InitList(SqList &L)
{
// 可以省略,但可能由于遍历时用到MaxSize有脏数据,要用length遍历
for (int i = 0; i < MaxSize; i ++ )
L.data[i] = 0;
L.length = 0; // 不可省略,顺序表初始长度为0
}
int main()
{
SqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
return 0;
}
1.2单链表:
- 每个结点除了存放数据元素外,还要存储指向下一个结点的指针
- 优点:不要求大片连续空间,改变容量方便
- 缺点:不可随机存取,要耗费一定空间存放指针
2.定义一个单链表:
- typedef关键字:数据类型重命名
- typedef <数据类型> <别名>
- typedef struct LNode LNode;
- 之后可以用LNode代替struct LNode
- 这样写每次都要有s t r u c t structstruct有些麻烦,所以教材中使用了t y p e d e f typedeftypedef关键字(C语言),可以把数据类型重命名
- t y p e d e f < 数 据 类 型 > < 别 名 >
2.1 用代码定义一个单链表
代码语言:javascript代码运行次数:0运行复制struct LNode // 定义单链表节点类型
{
ElemType data; // 每个节点存放一个数据元素
struct LNode *next; // 指针指向下一个节点
};
struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode)); // 增加一个新的节点 :在内存中申请一个节点需要的空间,并用指针p指向这个节点
代码语言:javascript代码运行次数:0运行复制struct LNode // 定义单链表节点类型
{
ElemType data; // 每个节点存放一个数据元素
struct LNode *next; // 指针指向下一个节点
};
typedef struct LNode LNode;
LNode *p = (LNode *)malloc(sizeof(LNode));
教材中还有一种更简洁的方式
typedef struct LNode // 定义单链表节点类型
{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
// LinkList - 单链表
// 上面这种写法等价于 :
struct LNode
{
ElemType data;
struct LNode *next;
}
typedef struct LNode LNode;
typedef struct LNode *LinkList;
要表示一个单链表时,只需声明一个头指针L,指向单链表的第一个结点
代码语言:javascript代码运行次数:0运行复制// 声明一个指向单链表第一个结点的指针
LNode *L;
// 等价于
LinkList L; // 代码可读性更强,详见下面例子中,
// GetElem函数的LNode *和LinkList虽然两者时等价的
//但在这个函数中它最终要返回的是第i个结点,所以把返回值的类型定义为LNode *,
// 其实它LNode *就是想强调返回的是一个结点,而LinkList想强调这是一个单链表
代码语言:javascript代码运行次数:0运行复制typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LNode *GetElem(LinkList L, int i)
{
int j = 1;
LNode *p = L -> next;
if (i == 0)
return L;
if (i < 1)
return NULL;
while (p != NULL && j < i)
{
p = p -> next;
j ++ ;
}
return p;
}
补充说明:
- 强调这是一个单链表 - 使用LinkList
- 强调这是一个结点 - 使用LNode *
3.不带头结点的单链表:
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
bool InitList(LinkList &L) // 注意传入引用
{
L = NULL; // 空表,暂时还没有任何结点 防止脏数据!!!
return true;
}
void test()
{
LinkList L; // 声明一个指向单链表的指针 注意,此处并没有创建一个结点!!!
// 初始化一个空表
InitList(L);
}
// (不带头结点)
bool Empty(LinkList L)
{
if (L == NULL)
return true;
else
return false;
}
// 或者
// (不带头结点)
bool Empty(LinkList L)
{
return (L == NULL);
}
/*如果不带头结点 :
头指针所指向的下一个结点就是实际用于存放数据的结点;而如果带头结点的话 :
头指针所指向的这个结点把它称为头结点,
这个头结点是不存放实际数据元素的,
只有这个头结点之后的下一个结点才用于存放数据*/
3.1带头结点的单链表:
typedef struct LNode
{
ElemType 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;
}
void test()
{
LinkList L; // 声明一个指向单链表的指针
InitList(L); // 初始化一个空表
}
// 判断单链表是否为空(带头节点)
bool Empty(LinkList L)
{
if (L -> next == NULL)
return true;
else
return false;
}
3.2区别:
- 不带头结点,写代码更麻烦
- 对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑
- 对空表和非空表的处理需要用不同的代码逻辑
- 我们一般使用的都是带头结点的单链表
4.单链表的插入、删除
按位序插入(带头结点):
ListInsert(&L,i,e):
- 插入操作,在表L中的第i个位置上插入指定元素e
- 找到第i-1个结点,将新结点插入其后
- 若带有头结点,插入更加方便,头结点可以看作“第0个”结点,直接做上面的操作即可
- 若i插在表中则与插在表头一样进行操作,可以插入成功
- 若i插在表尾则s->next为NULL(在表的定义时规定的),可以插入成功
- 若i插在表外(i>Lengh)则p指针指向NULL(While循环一直指向p->next),不能插入成功
- 最好时间复杂度= O(1)
- 最坏时间复杂度= O(n)
- 平均时间复杂度= O(n)
按位序插入(带头结点)代码书写:
代码语言:javascript代码运行次数:0运行复制// 在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e)
{
if (i < 1)
return false;
LNode *p = L; // 指针p指向当前扫描到的结点
int j = 0; // 当前p指向的是第几个结点
while (p != NULL && j < i - 1) // 循环找到第i-1个结点
{
j ++ ;
p = p -> next;
}
if (p == NULL) // i值不合法
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s -> data = e;
s -> next = p -> next;
p -> next = s;
return true;
}
按位序插入(不带头结点):
ListInsert(&L,i,e):
- ListInsert(&L, i, e) :插入操作,在表L中的第i个位置上插入指定元素e
- 找到第i-1个结点,将新结点插入其后
- 不存在“第0个”结点,因此i=1时需要特殊处理
- 不带头结点,则插入、删除第1个元素时,需要更改头指针L
bool ListInsert(LinkList &L, int i, ElemType e)
{
if (i < 1)
return false;
if (i == 1)
{
LNode *s = (LNode *)malloc(sizeof(LNode));
s -> data = e;
s -> next = L;
L = s;
return true;
}
LNode *p = L;
int j = 1; // 注意这里是1!!!不带头结点
while (p != NULL && j < i - 1)
{
p = p -> next;
j ++ ;
}
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s -> data = e;
s -> next = p -> next;
p -> next = s;
return true;
}
- 若i!=1则处理方法和带头结点一模一样
- 值得注意的是int j =1而非带头结点的0(带头结点的头结点为第0个结点)
- 综上结论:不带头结点写代码更不方便,推荐用带头结点
指定结点的后插操作:
bool InsertNextNode(LNode *p, ElemType e)
{
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL) // 内存分配失败,考试可以不写
return false;
s -> data = e;
s -> next = p -> next;
p -> next = s;
return true;
}
- 这一段代码是按位序插入中插入的那一部分代码
- 也可以直接调用InsertNextNode来执行
- 封装代码,以此提高代码复用性,让代码更容易维护
指定结点的前插操作:
- 因为仅知道指定结点的信息和后继结点的指向,因此无法直接获取到前驱结点
- 方法1:获取头结点然后再一步步找到指定结点的前驱
- 方法2:将新结点先连上指定结点p的后继,接着指定结点p连上新结点s,将p中元素复制到s中,将p中元素覆盖为要插入的元素e
方法1:前叉操作伪代码实现
// 前插操作 :在p结点之前插入元素e
// O(1)
bool InsertPriorNode(LNode *p, ElemType e)
{
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL)
return false;
s -> next = p -> next;
p -> next = s;
s -> data = p -> data;
p -> data = e;
return true;
}
代码语言:javascript代码运行次数:0运行复制// 王道书版本
bool InsertPriorNode(LNode *p, LNode *s)
{
if (p == NULL || s == NULL)
return false;
s -> next = p -> next;
p -> next = s;
ElemType temp = p -> data; // 交换数据域部分
p -> data = s -> data;
s -> data = temp;
return true;
}
方法2:按位序删除(带头结点):
ListDelete(&L,i,&e):
- 删除操作,删除表L中第i个位置的元素,并用e返回删除元素的值。
- 找到第i-1个结点,将其指针指向第i+1个结点,并释放第i个结点
bool ListDelete(LinkList &L, int i, ElemType &e)
{
if (i < 1)
return false;
LNode *p = L;
int j = 0;
while (p != NULL && j < i - 1)
{
p = p -> next;
j ++ ;
}
if (p == NULL)
return false;
if (p -> next == NULL) // 第i-1个结点之后已无结点
return false;
LNode *q = p -> next;
e = q -> data;
p -> next = q -> next;
free(q);
return true;
}
指定结点的删除
- 删除结点p,需要修改其前趋结点的next指针
- 方法1 :传入头指针,循环寻找p的前趋结点
- 方法2 :偷天换日(类似于结点前插的实现)
指定结点的删除代码:
代码语言:javascript代码运行次数:0运行复制bool DeleteNode(LNode *p)
{
if (p == NULL)
return false;
LNode *q = p -> next;
p -> data = p -> next -> data;
p -> next = q -> next;
free(q);
return true;
}
方法2注意!!!
如果要删除的结点p是最后一个结点:
- 只能从表头开始依次寻找p的前驱,时间复杂度O(n)
- 这就体现了单链表的局限性:无法逆向检索,有时候不太方便
5.单链表的查找【只探讨“带头结点”的情况】
按位查找:
- GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
- 实际上单链表的插入中找到i-1部分就是按位查找i-1个结点,如下图
- 因此查找第i个结点如下图
单链表的按位查找代码:
代码语言:javascript代码运行次数:0运行复制LNode * GetElem(LinkList L, int i)
{
if (i < 0)
return false;
LNode *p = L;
int j = 0;
while (p != NULL && j < i)
{
p = p -> next;
j ++ ;
}
return p;
}
- 如果i=0则直接不满足j<i则指针p直接返回头结点L
- 如果i超界则当时p指向了NULL,指针p返回NULL
- 平均时间复杂度:O(n)
按值查找:
按值查找代码
代码语言:javascript代码运行次数:0运行复制LNode * LocateElem(LinkList L, ElemType e)
{
LNode *p = L -> next;
while (p != NULL && p -> data != e)
p = p -> next;
return p;
}
- 能找到的情况:p指向了e值对应的元素,返回该元素
- 不能找到的情况:p指向了NULL,指针p返回NULL
- 平均时间复杂度:O(n)
求表的长度
求表的长度代码:
代码语言:javascript代码运行次数:0运行复制int Length(LinkList L)
{
LNode *p = L;
int len = 0;
while (p != NULL)
{
p = p -> next;
len ++ ;
}
return len;
}
6.单链表的建立
尾插法:
- 每次插入元素都插入到单链表的表尾
- 方法1:套用之前学过的位序插入,每次都要从头开始往后面遍历,时间复杂度为O(n^2)
//设置变量length记录链表长度,用ListInsert,O(n^2);设置一个表尾指针,只要每次对r指针进行后插操作InsertNextNode,然后把表尾指针往后移
// O(n)
LinkList List_TailInsert(LinkList &L)
{
int x;
L = (LinkList)malloc(sizeof(LNode)); // 建立头结点
LNode *s, *r = L;
scanf("%d", &x);
while (x != 9999)
{
s = (LNode *)malloc(sizeof(LNode));
s -> data = x;
r -> next = s;
r = s;
scanf("%d", &x);
}
r -> next = NULL;
return L;
}
- 方法2:增加一个尾指针r,每次插入都让r指向新的表尾结点,时间复杂度为O(n)
头插法:
- 每次插入元素都插入到单链表的表头
- 头插法和之前学过的单链表后插操作是一样的,可以直接套用
- L->next=NULL;可以防止野指针
总结:
- 头插法、尾插法:核心就是初始化操作、指定结点的后插操作
- 注意设置一个指向表尾结点的指针
- 头插法的重要应用:链表的逆置
7.双链表
为什么要要使用双链表:
- 单链表:无法逆向检索,有时候不太方便
- 双链表:可进可退,但是存储密度更低一丢丢
双链表的初始化(带头结点)代码实现:
双链表的初始化(带头结点):
双链表的初始化(带头结点)代码:
代码语言:javascript代码运行次数:0运行复制typedef struct LNode // 定义单链表结点类型
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
// 初始化一个循环单链表
bool InitList(LinkList &L)
{
L = (LinkList)malloc(sizeof(LNode));
if (L == NULL)
return false;
L -> next = L; // 头结点next指向头结点
return true;
}
// 判断循环单链表是否为空
bool Empty(LinkList L)
{
if (L -> next == L)
return true;
else
return false;
}
// 判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p)
{
if (p -> next == L)
return true;
else
return false;
}
双链表的插入
双链表的插入代码实现:
代码语言:javascript代码运行次数:0运行复制// 在p结点之后插入s结点(后插),以下是前插法,但由于是双链表,如果要前插,只要找到前一个用后插就可以
bool InsertNextNode(DNode *p, DNode *s)
{
if (p == NULL || s == NULL)
return false;
s -> next = p -> next;
if (p -> next != NULL) // 如果p结点有后继结点
p -> next -> prior = s;
s -> prior = p;
p -> next = s;
return p;
}
- 小心如果p结点为最后一个结点产生的空指针问题,因此循环链表应运而生(详见后面的循环链表插入删除)
- 注意指针的修改顺序
双链表的删除:
双链表的删除代码实现:
代码语言:javascript代码运行次数:0运行复制// 删除p结点的后继结点
bool DeleteNextNode(DNode *p)
{
if (p == NULL)
return false;
DNode *q = p -> next;
if (q == NULL)
return false;
p -> next = q -> next;
if (q -> next != NULL)
q -> next -> prior = p;
free(q);
return true;
}
void DestroyList(DLinkList &L)
{
while (L -> next != NULL)
DeleteNextDNode(L);
free(L); // 释放头结点
L = NULL; // 头结点指向NULL
}
双链表的遍历:
循环链表
循环单链表与单链表的区别:
单链表:
- 表尾结点的next指针指向NULL
- 从一个结点出发只能找到后续的各个结点
循环单链表:
- 表尾结点的next指针指向头结点
- 从一个结点出发可以找到其他任何一个结点
循环单链表初始化:
- 从头结点找到尾部,时间复杂度为O(n)
- 如果需要频繁的访问表头、表尾,可以让L指向表尾元素(插入、删除时可能需要修改L)
- 从尾部找到头部,时间复杂度为O(1)
循环双链表的初始化:
循环双链表的初始化代码实现:
代码语言:javascript代码运行次数:0运行复制typedef struct DNode
{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinkList;
bool InitDLinkList(DLinkList &L)
{
L = (LinkList)malloc(sizeof(LNode));
if (L == NULL)
return false;
L -> prior = L;
L -> next = L;
return true;
}
bool Empty(DLinkList L)
{
if (L -> next == L)
return true;
else
return false;
}
bool isTail(LinkList L, DNode *p)
{
if (p -> next == L)
return true;
else
return false;
}
循环链表的插入:
- 对于双链表来说如果p结点为最后一个结点,因为next结点为null,p->next->prior=s会产生的空指针问题
- 循环链表规避因为最后结点的next结点为头结点因此不会发生问题
循环双链表的插入代码实现
其实是双链表插入的缩减版
代码语言:javascript代码运行次数:0运行复制bool InsertNextDNode(LNode *p, LNode *s)
{
s -> next = p -> next;
p -> next -> prior = s;
s -> prior = p;
p -> next = s;
}
循环链表的删除:
- 与循环链表的插入相同。
循环双链表的删除代码实现
代码语言:javascript代码运行次数:0运行复制//同上
p -> next = q -> next;
q -> next -> prior = p;
free(q);
注意点:
写代码时候注意以下几点,以此规避错误:
- 如何判空
- 如何判断结点p是否是表尾/表头元素(后向/前向遍历的实现核心)
- 如何在表头、表中、表尾插入/删除一个结点
8.静态链表
什么是静态链表:
- 分配一整片连续的内存空间,各个结点集中安置
- 每个结点由两部分组成:data(数据元素)和next(游标)
- 0号结点充当“头结点”,不具体存放数据
- 游标为-1表示已经到达表尾
- 游标充当“指针”,表示下个结点的存放位置,下面举一个例子:
- 每个数据元素4B,每个游标4B(每个结点共8B),设起始地址为addr,e1的存放地址为addr + 8*2(游标值)
定义静态链表:
方法1:
定义静态链表代码实现:
代码语言:javascript代码运行次数:0运行复制#define MaxSize 10;
struct Node
{
ElemType data;
int next;
};
void testSLinkList()
{
struct Node a[MaxSize]; // 数组a作为静态链表
}
方法2:
基本操作:
初始化:
- 把a[0]的next设为-1
- 把其他结点的next设为一个特殊值用来表示结点空闲,如-2
插入位序为i的结点:
- 找到一个空的结点,存入数据元素(设为一个特殊值用来表示结点空闲,如-2)
- 从头结点出发找到位序为i-1的结点
- 修改新结点的next
- 修改i-1号结点的next
删除某个结点:
- 从头结点出发找到前驱结点
- 修改前驱结点的游标
- 被删除结点next设为-2
总结:
- 静态链表:用数组的方式实现的链表
- 优点:增、删操作不需要大量移动元素
- 缺点:不能随机存取,只能从头结点开始依次往后查找;容量固定不可变
- 适用场景:(1)不支持指针的低级语言;(2)数据元素数量固定不变的场景(如操作系统的文件分配表FAT)
9.顺序表和链表的比较 顺序表和链表的比较 顺序表链表逻辑结构都属于线性表,都是线性结构都属于线性表,都是线性结构存储结构
- 优点:支持随机存取、存储密度高
- 缺点:大片连续空间分配不方便,改变容量不方便
- 优点:离散的小空间分配方便,改变容量方便
- 缺点:不可随机存取,存储密度低
开放式问题的解题思路: 问题: 请描述顺序表和链表的bla bla bla…实现线性表时,用顺序表还是链表好? 答案:
- 顺序表和链表的逻辑结构都是线性结构,都属于线性表。
- 但是二者的存储结构不同,顺序表采用顺序存储…(特点,带来的优点缺点);链表采用链式存储…(特点、导致的优缺点)。
- 由于采用不同的存储方式实现,因此基本操作的实现效率也不同。
- 当初始化时…;当插入一个数据元素时…;当删除一个数据元素时…;当查找一个数据元素时
本文标签: 2024重生之回溯数据结构与算法系列学习无论是王道考研人还是IKUN都能包会的不然别给我家鸽鸽丢脸好嘛
版权声明:本文标题:2024重生之回溯数据结构与算法系列学习【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/shuma/1754676153a3176637.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论