双链表
双链表
对比与单链表多一个结构体指针指向前一个节点
typedef struct DNode{
int e;//存储的数据可以换成别的数据
struct DNode *next,*prior;
}DNode,*DLinkList;
piror指针指向前一个节点
双链表初始化
#define bool char
#define true 1
#define false 0//用来在c语言实现使用bool类型的效果
#include <stdio.h>
typedef struct DNode{
int e;//存储的数据可以换成别的数据
struct DNode *next,*prior;
}DNode,*DLinkList;
bool InitDLinkList(DLinkList L){
L=(DLinkList)malloc(sizeof(DNode));
if(L=NULL)
return false;
L->next=NULL;
L->priot=NULL;
return true;
}
双链表的插入
这里我只写后插操作的代码
因为位序插入的代码
可以通过找到i-1的节点然后进行后插操作来完成
//前面的bool类型和导库和结构体我就不写了
bool(DLinkList P,DLinkList S){//把S节点插入P节点后面
if(P=NULL||S=NULL)
return false;
S->next=P->next;//该语句不管P有无后继节点，都可以实现
if(P->next!=NULL)
P->next->prior=S;//该语句如果P没有后继节点才会异常，现在有无后继节点都可以插入
P->next=S;
S->prior=P;
}
双链表的删除
删除P节点的后继节点
bool DeleteNextNode(DLinkList P){
if(P==NULL)
return false;//(没有给定的该节点)
DLinkeList L=P->next;
if(L=NULL)
return false;//(没有后继节点)
P->next=L->next;
if(L!=NULL)//(后继节点的后继节点不为空，才有prior)以防后继节点next指向NULL
P->next->prior=P;
free(L);
}
双链表的遍历
小结
循环链表
所谓循环链表就是
把最后一个节点的的next指向第一个节点
如图
这样给其中的任一个节点就能遍历整个链表
单链表版
typedef struct Node{
int e;//存储的数据可以换成别的数据
struct Node *next;
}LNode,*LinkList;
初始化
bool InitList(LinkList L){
L=(LinkList)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next=L;//刚开始最后一个节点就是第一个节点，所以指向他自己
return true;
}
双链表版
typedef struct DNode{
int e;//存储的数据可以换成别的数据
struct DNode *next,*prior;
}DNode,*DLinkList;
初始化
图示
插入与删除
因为循环链表不存在说
next指向NULL的情况
所以不用考虑NULL指针异常的情况
小结
静态链表（少考）
什么是静态链表
系统申请一片连续空间
一个节点存储
一个数据和下一个数据的游标
（底层是根据对应节点占的空间进行内存的±然后找到对应的节点，因为是连续的内存空间喽喽）
定义一个静态链表
一般我们想的方法
课本上的定义
typedef延伸
这样定义
相当于
每定义一个SLinkList a
就相当于
struct Node a[10]
相关基本操作
优缺点
