当前位置：网站首页>03_线性表_链表
03_线性表_链表
2022-07-02 12:00:00 【听*雨声】
链表：适合插入
链表：逻辑相邻，物理不相邻
头节点:不用于存放数据，只起标记作用
单链表的尾节点next域为空
1 不带头节点的单链表
不带头节点的单链表： 实现时修改指针（ plist)的指向需要传该指针的地址，故需要使用二级指针
2 带头节点的单链表
带头节点的单链表： 实现时不带二级指针，相比不带头节点的单链表操作起来非常简单
优点：带头节点不用判空，因为头节点一直都在。
注意：头节点不用删除，因为用malloc申请的才需要 free
插入操作可分为2大类：
例如：对链表的结构不需要改变：输出操作，查找操作，获取长度…
//判断两条链表是否相交，若相交返回第一个相交节点
Node* intersect(List plist1, List plist2)
{
if (plist1 == nullptr && plist2 == nullptr)return nullptr;
int len1 = GetLength(plist1);
int len2 = GetLength(plist2);
Node* p = len1 > len2 ? plist1 : plist2;
Node* q = len1 > len2 ? plist2 : plist1;
for (int i = 0;i < abs(len1 - len2);i++)//abs ：求绝对值的函数
{
p = p->next;//长的向后跑|len1-len2|步
}
while (p != nullptr)
{
if (p == q)
{
return p;
}
p = p->next;
q = q->next;
}
return nullptr;
}
#include<stdio.h>
#include"list.h"
#include<stdlib.h>
#include<assert.h>
//初始化
void InitList(List plist)
{
assert(plist != NULL);
if (plist == NULL)
return;
//ps->data;头节点的data域不使用
plist->next = NULL;//因为初始化时头就是尾，所有单链表的尾节点next域为空
}
//头插
bool Insert_head(List plist, int val)
{
//动态申请一个新节点
Node* p = (Node*)malloc(sizeof(Node));
assert(p != NULL);
//将val放到新节点
p->data = val;
//插入新节点
p->next = plist->next;
plist->next = p;
return true;
}
//尾插
bool Insert_tail(List plist, int val)
{
assert(plist != NULL);
if (plist == NULL)
{
return false;//不能用exit(1)，因为直接退出了进程:工作中不允许使用
}
Node* p = (Node*)malloc(sizeof(Node));
p->data = val;
//找尾部
Node* q;
for (q = plist;q->next != NULL;q=q->next)
{
;
}
//插入新节点
p->next = q->next;
q->next = p;
return true;
}
//在plist链表的pos位置标插入数据val
bool Insert(List plist, int pos, int val)
{
if (pos<0 || pos>GetLength(plist))
{
return false;
}
Node* p = (Node*)malloc(sizeof(Node));
p->data = val;
//找位置
Node* q;
int i;
for (q = plist, i = 0;i < pos;i++, q = q->next);
//p插入在q的后面
p->next = q->next;
q->next = p;
return true;
}
//判空
bool IsEmpty(List plist)
{
return plist->next == NULL;
}
//获取数据节点个数
int GetLength(List plist)
{
int count = 0;
for (Node* p = plist->next;p != NULL;p->next)
{
count++;
}
return count;
}
//在plist中查找第一个key,找到了返回节点地址，没有找到返回NULL
Node* Search(List plist, int key)
{
for(Node*p=plist->next;p!=NULL;p=p->next)
{
if (p->data == key)
{
return p;
}
}
return NULL;
}
//删除pos位置的值
bool DelPos(List plist, int pos)
{
if (pos<0 || pos>=GetLength(plist))
{
return false;
}
Node* p;
int i;
for (p = plist, i = 0;i < pos;i++, p= p->next);
//删除p后面的节点
Node* q = p->next;
p->next = q->next;
free(q);
return true;
}
//删除第一个val值
bool DelVal(List plist, int val)
{
Node* p = GetPrio(plist, val);
if (p == NULL)
{
return false;
}
Node* q = p->next;//把将要删除的节点地址保存
//将q从链表中剔除
p->next = q->next;//p->next=p->next->next;
//释放q的内存
free(q);
return true;
}
//删除一个节点时间复杂度为O（1）
bool DelVal(List plist, Node* p)
{
if (plist == nullptr && p == nullptr)return false;
if (p->next == nullptr)//尾节点
{
return DelPos(plist, GetLength(plist)-1);
}
Node* q = p->next;
p->data = q->data;
p->next = q->next;
free(q);
q = nullptr;
return true;
}
//返回key的前驱地址，如果不存在返回NULL；
Node* GetPrio(List plist, int key)
{
for (Node* p = plist;p->next != NULL;p = p->next)
{
if (p->next->data == key)//p是前驱地址
{
return p;
}
}
return NULL;
}
//返回key的后继地址，如果不存在返回NULL；
Node* GetNext(List plist, int key)
{
Node* p = Search(plist, key);
if (p == NULL)
return NULL;
return p->next;
}
//输出链表
void Show(List plist)
{
//通过节点指针，遍历所有的数据节点（注意头节点不能访问数据域）
for (Node* p = plist->next;p != NULL;p = p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
//清空数据:删除所有节点
void Clear(List plist)
{
Destory(plist);
}
//销毁整个内存：释放所有的数据节点，头节点不用释放
void Destory1(List plist)//太复杂
{
if (plist == NULL || plist->next == NULL)
{
return;
}
Node* p = plist->next;
Node* q;
plist->next = NULL;
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
}
void Destory2(List plist)//总是删除第一个数据节点
{
Node* p;
while (plist->next != NULL)
{
p = plist->next;
plist->next = p->next;
free(p);
}
}
3 循环链表
循环链表：
1.尾部节点的 next 指向头节点，形成循环
2.带头节点
初始化头节点：
typedef struct CNode
{
int data;
struct CNode* next;
}CNode,*CList;
//初始化
void InitCList(CList plist);
//头插
bool Insert_head(CList plist, int val);
//尾插
bool Insert_tail(CList plist, int val);
//在plist链表的pos位置标插入数据val
bool Insert(CList plist, int pos, int val);
//判空
bool IsEmpty(CList plist);
//获取数据节点个数
int GetLength(CList plist);
//在plist中查找第一个key,找到了返回地址，没有找到返回NULL
CNode* Search(CList plist, int key);
//删除pos位置的值
bool DelPos(CList plist, int pos);
//删除第一个val值
bool DelVal(CList plist, int val);
//返回key的前驱地址，如果不存在返回NULL；
CNode* GetPrio(CList plist, int key);
//返回key的后继地址，如果不存在返回NULL；
CNode* GetNext(CList plist, int key);
//输出顺序表
void Show(CList plist);
//清空数据
void Clear(CList plist);
//销毁整个内存
void Destory(CList plist);
4 双向链表
双向链表：
带头节点的双向链表，不循环，尾节点的后继为空，头节点的前驱为空
使用联合体可以让头节点的数据域不浪费，从而用来记录链表节点的个数
typedef struct DNode
{
union
{
int data;
int length;
};
struct DNode* next;//后继指针
struct DNode* prio;//前驱指针
}DNode,*DList;
typedef struct DNode
{
int data;
struct DNode* next;//后继指针
struct DNode* prio;//前驱指针
}DNode,*DList;
//初始化
void InitDList(DList plist);
//头插
bool Insert_head(DList plist, int val);
//尾插
bool Insert_tail(DList plist, int val);
//在plist链表的pos位置标插入数据val
bool Insert(DList plist, int pos, int val);
//判空
bool IsEmpty(DList plist);
//获取数据节点个数
int GetLength(DList plist);
//在plist中查找第一个key,找到了返回地址，没有找到返回NULL
DNode* Search(DList plist, int key);
//删除pos位置的值
bool DelPos(DList plist, int pos);
//删除第一个val值
bool DelVal(DList plist, int val);
//返回key的前驱地址，如果不存在返回NULL；
DNode* GetPrio(DList plist, int key);
//返回key的后继地址，如果不存在返回NULL；
DNode* GetNext(DList plist, int key);
//输出顺序表
void Show(DList plist);
//清空数据
void Clear(DList plist);
//销毁整个内存
void Destory(DList plist);
5 双向循环链表
代码实现：
//循环链表可执行的操作：（增删改查）
//初始化
void Init_dclist(PDClist pl)
{
assert(pl != NULL);
if(NULL == pl)
return;
//pl->data; 头结点的数据域不使用 浪费掉
pl->next = pl;
pl->prior = pl;
}
DCList * BuyNode(int val)
{
DCList *pnewnode = (DCList *)malloc(sizeof(DCList) * 1);
assert(pnewnode != NULL);
pnewnode->data = val;
pnewnode->next = NULL;
pnewnode->prior = NULL;
return pnewnode;
}
//头插
bool Insert_head(PDClist pl, int val)
{
//1.assert
assert(pl != NULL);
if(pl == NULL)
return false;
//2.申请新节点
DCList *pnewnode = BuyNode(val);
assert(pnewnode != NULL);
//3.插入
pnewnode->next = pl->next;
pnewnode->prior = pl;
if(pl->next != pl)//证明在头插之前，就至少存在一个有效节点
{
pl->next->prior = pnewnode;
}
pl->next = pnewnode;
//下面的代码是对比双向链表新加入的代码
if(pl->prior == pl)//（1.如果插入之前就有有效节点，则这个指针不需要修改 2.如果是个空的链表，则这个指针需要做修改）
{
pl->prior = pnewnode;//是让pl->prior 永远指向最后一个节点
}
return true;
}
//尾插
bool Insert_tail(PDClist pl, int val)
{
//1.assert
//2.创建新节点
DCList *pnewnode = BuyNode(val);
assert(pnewnode != NULL);
//3.找到合适的插入位置
DCList *p = pl;
for(pl; p->next!=pl; p=p->next);
//此时 for循环执行结束，代表指针p此时指向最后一个节点
//4.插入节点
pnewnode->next = p->next;//pnewnode->next = pl;
pnewnode->prior = p;
p->next = pnewnode;
//下面的代码是对比双向链表新加入的代码
pl->prior = pnewnode;//因为是尾插函数，所以每次都得让pl->prior重新指向最后一个有效节点（新插入的节点）
return true;
}
//按位置插入
bool Insert_pos(PDClist pl, int pos, int val)
{
//1.assert pl pos
//2.申请新的节点
DCList *pnewnode = BuyNode(val);
assert(pnewnode != NULL);
//3.找到合适的插入位置
DCList *p = pl;
for(int i=0; i<pos; i++)
{
p = p->next;
}
//4.插入
pnewnode->next = p->next;
pnewnode->prior = p;
if(p->next != pl)
{
p->next->prior = pnewnode;
}
else///else的代码是对比双向链表新加入的代码
{
pl->prior = pnewnode;
}
p->next = pnewnode;
return true;
}
//头删
bool Del_head(PDClist pl)
{
//1.assert
assert(pl!=NULL && pl->next!=pl);
if(pl==NULL || pl->next==pl)
{
return false;
}
//2.找到删除的位置
//3.删除
DCList *p = pl->next;
if(p->next == pl)//删除的节点就是仅存的节点
{
pl->next = pl->prior = pl;
free(p);
p = NULL;
}
else//删除的节点不是仅存的节点
{
pl->next = p->next;
p->next->prior = pl;
free(p);
p = NULL;
}
return true;
}
//尾删
bool Del_tail(PDClist pl)
{
//1.assert
//2.找到删除的位置
DCList *p = pl;
for(p; p->next!=pl; p=p->next);
//此时 for循环执行结束，代表指针p此时指向最后一个节点
//3.删除
if(pl->next == p)//if(p->prior == pl)//删除的节点就是仅存的节点//
{
pl->next = pl;
pl->prior = pl;
}
else//删除的节点不是仅存的节点
{
p->prior->next = pl;//删除节点的上一个节点的next域指向头结点
pl->prior = p->prior;//让头节点的前驱指针指向新的最后一个节点（删除节点的上一个节点）
}
free(p);
p = NULL;
return true;
}
//按位置删除
bool Del_pos(PDClist pl, int pos)
{
//assert pl pos
if(pos == 0)
return Del_head(pl);
if(pos == Get_length(pl)-1)
return Del_tail(pl);
//此时 剩下的情况都是中间节点删除
DCList *p = pl;
for(int i=0; i<pos; i++)
{
p = p->next;
}
DCList *q = p->next;//q 指向的就是删除的节点本身
p->next = q->next;
q->next->prior = p;
free(q);
q = NULL;
return true;
}
//按值删除，删除遇到的第一个值为val的节点 如果值为val的节点不存在，则返回false
bool Del_val(PDClist pl, int val)
{
//assert
DCList *p = Search(pl, val);
if(p == NULL)
{
return false;
}
//这两行代码 兼容任何情况
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
p = NULL;
return true;
}
//查找 查找值为val的第一个节点，找到则返回其节点地址，否则返回NULL
PDClist Search(PDClist pl, int val)
{
//assert
DCList *p = pl->next;
for(p; p!=pl; p=p->next)
{
if(p->data == val)
{
return p;
}
}
return NULL;
}
//判空
bool IsEmpty(PDClist pl)
{
return pl->next == pl;
}
//获取循环链表有效元素个数
int Get_length(PDClist pl)
{
int count = 0;
DCList *p = pl->next;
for(p; p!=pl; p=p->next)
{
count++;
}
return count;
}
//打印
void Show(PDClist pl)
{
DCList *p = pl->next;
for(p; p!=pl; p=p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
//清空
void Clear(PDClist pl)
{
Destroy(pl);
}
//销毁1 一直头删的方式释放内存
void Destroy(PDClist pl)
{
while(pl->next != pl)
{
DCList *p = pl->next;
pl->next = p->next;
free(p);
p = NULL;
}
pl->prior = pl;
}
//销毁2
void Destroy2(PDClist pl)
{
DCList *p = pl->next;
DCList *q;
while(p != pl)
{
q = p->next;
free(p);
p = q;
}
pl->next = pl;
pl->prior = pl;
}
//寻找值为val的节点的前驱
PDClist Get_prior(PDClist pl, int val)
{
DCList *p = Search(pl, val);
if(p == NULL)
{
return NULL;
}
return p->prior;
}
//寻找值为val的节点的后继
PDClist Get_next(PDClist pl, int val)
{
DCList *p = Search(pl, val);
if(p == NULL)
{
return NULL;
}
return p->next;
}
6 静态链表
静态链表：
利用顺序表模拟链表的操作
静态链表包含2条链表：
- 一条为有效数据链表：带头节点的循环链表，且头节点在0下标
- 一条为空闲数据链表：带头节点的循环链表，且头节点在1下标
注意：插入一条空闲节点链表的目的是让插入数据时找空闲节点的速度变为O（1）
好处：不用频繁的申请以及释放内存
对外表现是链表，但是内部存储是顺序表
链表的特点：
- 插入和删除操作快，插入和删除时不需要移动数据
时间复杂度O（1）
和链表相比不需要频繁的创建和删除节点
但是和顺序表对比需要增加一个 next
静态链表可以动态增长，满后扩容，只是需要将扩容的内存添加到空闲链表中
顺序表特点：插入和删除操作慢，适用于查找频繁的操作
typedef struct SNode
{
int data;//数据
int next;//后继指针（下标）
}SNode,SLinkList[MAXSIZE];
//SLinkList s;//s为长度为MAXSIZE的结构体数组
//
//typedef SNode Arr[MAXSIZE];//长度为MAXSIZE的结构体数组类型
//Arr a;// a 是长度为MAXSIZE的结构体数组
//初始化
void InitSList(SNode* ps);
//头插
bool Insert_head(SNode* ps, int val);
//尾插
bool Insert_tail(SNode* ps, int val);
//判空
bool IsEmpty(SNode* ps);
//获取数据节点个数
int GetLength(SNode* ps);
//在plist中查找第一个key,找到了返回地址(地址），没有找到返回-1
int Search(SNode* ps, int key);
//删除第一个val值
bool DelVal(SNode* ps, int val);
//输出顺序表
void Show(SNode* ps);
//清空数据
void Clear(SNode* ps);
边栏推荐
- info [email protected] : The platform “win32“ is incompatible with this module.
- 学习使用php将时间戳转换为大写日期的方法代码示例
- 为什么只会编程的程序员无法成为优秀的开发者？
- N皇后问题的解决
- Solve the problem that El radio group cannot be edited after echo
- Error: NPM warn config global ` --global`, `--local` are deprecated Use `--location=global` instead.
- [c voice] explain the advanced pointer and points for attention (2)
- Introduction to mathjax (web display of mathematical formulas, vector)
- 关于网页中的文本选择以及统计选中文本长度
- Deploy tidb cluster with tiup
猜你喜欢
【NOI模拟赛】伊莉斯elis（贪心，模拟）
Li Chuang EDA learning notes 15: draw border or import border (DXF file)
LeetCode 209. 长度最小的子数组
Solve the problem that El radio group cannot be edited after echo
电脑怎么设置扬声器播放麦克风的声音
[email protected]: The platform “win32“ is incompatible with this module."/>info [email protected]: The platform “win32“ is incompatible with this module.
c语言入门--数组
Kityformula editor configure font size and spacing
C语言习题---（数组）
- [email protected] : The platform “win32“ is incompatible with this module."/>
info [email protected] : The platform “win32“ is incompatible with this module.
随机推荐
. Net core logging system
Tidb data migration scenario overview
C语言中的printf函数和scanf函数
LeetCode 2320. 统计放置房子的方式数
Record an interview
Record an error report, solve the experience, rely on repetition
Find the maximum inscribed circle of the contour
Some Chinese character codes in the user privacy agreement are not standardized, which leads to the display of garbled codes on the web page. It needs to be found and handled uniformly
05_队列
传感器数据怎么写入电脑数据库
07_哈希
[c voice] explain the advanced pointer and points for attention (2)
【NOI模拟赛】伊莉斯elis（贪心，模拟）
Simple verification code generator for 51 single chip microcomputer experiment
LeetCode - 搜索二维矩阵
表格响应式布局小技巧
LeetCode 209. Minimum length subarray
编译原理课程实践——实现一个初等函数运算语言的解释器或编译器
LeetCode_字符串_简单_412.Fizz Buzz
taobao. trade. memo. Add (add remarks to a transaction) interface, Taobao store flag insertion interface, Taobao order flag insertion API interface, oauth2.0 interface