数据结构-双链表、循环链表、静态链表（c语言版）

双链表

双链表
对比与单链表多一个结构体指针指向前一个节点

typedef struct DNode{
int e;//存储的数据可以换成别的数据
struct DNode *next,*prior;
}DNode,*DLinkList;
1
2
3
4

piror指针指向前一个节点

双链表初始化

#define bool char
#define true 1
#define false 0//用来在c语言实现使用bool类型的效果
#include 
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;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

双链表的插入

这里我只写后插操作的代码
因为位序插入的代码
可以通过找到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;
		
	
}
1
2
3
4
5
6
7
8
9
10
11
12

双链表的删除

删除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);
}
1
2
3
4
5
6
7
8
9
10
11

双链表的遍历

小结

循环链表

所谓循环链表就是
把最后一个节点的的next指向第一个节点
如图

这样给其中的任一个节点就能遍历整个链表

单链表版

typedef struct Node{
int e;//存储的数据可以换成别的数据
struct Node *next;
}LNode,*LinkList;
1
2
3
4

初始化

bool InitList(LinkList L){
	L=(LinkList)malloc(sizeof(LNode));
	if(L==NULL)
	return false;
	L->next=L;//刚开始最后一个节点就是第一个节点，所以指向他自己
	return true;
	
}
1
2
3
4
5
6
7
8

双链表版

typedef struct DNode{
int e;//存储的数据可以换成别的数据
struct DNode *next,*prior;
}DNode,*DLinkList;
1
2
3
4

初始化

图示

插入与删除

因为循环链表不存在说
next指向NULL的情况
所以不用考虑NULL指针异常的情况

小结

静态链表（少考）

什么是静态链表

系统申请一片连续空间
一个节点存储
一个数据和下一个数据的游标
（底层是根据对应节点占的空间进行内存的±然后找到对应的节点，因为是连续的内存空间喽喽）

定义一个静态链表

一般我们想的方法

课本上的定义
typedef延伸

这样定义
相当于
每定义一个SLinkList a
就相当于
struct Node a[10]

相关基本操作

优缺点