C语言双链表，循环链表，静态链表讲解
一、双链表
在单链表中，每个元素都附加了一个指针域，指向下一个元素的存储位置。在双向链表中，每个元素都附加了两个指针域，分别指向前驱节点和后继节点。
单链表只能向后操作，不能向前操作。为了向前、向后操作方便，可以给每个元素都附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表被称为双向链表示。
从上图中可以看出，双向链表的每个节点都包含三个域：数据域和两个指针域。两个指针域分别存储前后两个元素的地址，即指向前驱节点和后继节点。
初始化（带头结点）：
typedef struct DNode{ //定义双链表结点类型
Elemtype date; //数据域
struct DNode *prior,*next; //前驱和后继指针
}DNode,*DLinklist;
//初始化双链表
bool InitDLinkList(DLinklist &L){
L =(DNode*)malloc(sizeof(DNode));
if(L==NULL)
return false;
L->prior = NULL;
L->next = NULL;
}
判断链表是否为空（带头结点）
bool Empty(DLinklist L){
if(L->next == NULL)
return true;
else
return false;
}双链表的插入：
//在p结点之后插入s结点
bool InsertDNode(DNode *p,DNode *s)
{
if(p==NULL||s==NULL)
return false;
s->next = p->next;
if(p->next != NULL) //如果在尾部插入，尾部是NULL，空的不能指向
p->next->prior = s;
s->prior= p;
p->next = s;
return true;
} 双链表的遍历
后序遍历
while(P!=NULL)
{
//对结点p处理如打印
p = p -> next;
}前序遍历
while(p!=NULL){
//对结点p做相应的处理
p = p -> prior;
}前向遍历(跳过头结点）
while(p->prior!=NULL)
{
//对结点p做相应的处理
p = p-> prior;
}双链表不可随机存取，按位查找和按值查找都只能用遍历的方式实现。时间复杂度O(n)
循环链表
在单链表中，只能向后操作，不能向前操作，如果从当前节点开始，则无法访问该节点前面的节点；
如果最后一个节点的指针指向头节点，形成一个环，就可以从任何一个节点出发，访问所有节点，这就是循环链表。
循环链表和普通链表的区别就是最后一个节点的后继指向了头节点。下面看看单链表和单向循环链表的区别。
单向循环链表最后一个节点的next域不为空，而是指向了头节点，
而单链表和单向循环链表判断空表的条件也发生了变化，单链表为空表时，L ->next=NULL；单向循环链表为空表时，L ->next=L 。
双向循环链表除了要让最后一个节点的后继指向第1个节点，还要让头节点的前驱指向最后一个节点
双向循环链表为空表时，L ->next=L ->prior=L ，如下图所示。
循环单链表的初始化
typedef struct LNode{ //定义单链表的结点类型
ElemType date; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;
//初始化一个循环单链表
bool InitList(LinkList &L) {
L = (LNode*) malloc(sizeof(LNode)); //分配一个头结点
if(L==NULL) //内存不足分配失败
return false;
L->next = L； //头接点next指向头结点
return true;
}循环双链表的初始化
//初始化一个循环双链表
typedef struct DNode{
ElemType date;
struct DNode *prior,*next;
}DNode,*DLinklist;
bool InitDLinkList(DLinklist &L){
L = (DNode *) malloc(sizeof(DNode)); //分配一个头结点
if(L==NULL)
return false;
L->prior = L; //头结点的prior指向头结点
L->next = L; //头结点的next指向头结点
return true;
} 此时判断是否为空和判断是否为尾结点的条件就是看next是否为L
双链表的插入
由于是循环双链表，就不用考虑是不是在尾部插入
//在p结点之后插入s结点
bool InsertDNode(DNode *p,DNode *s){
s->next= p->next;
p->next->prior= s;
s->prior = p;
p->next = s;
} 
双链表的删除
//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);静态链表
链表还有另一种静态表示方式，可以用一个数组存储数据，用另一个数组记录当前数据的后继的下标。
用静态链表可以先把数据存储在一维数组data[]中，然后用后继数组next[]记录每个元素的后继下标
定义静态链表
#define Maxsize 10 //静态链表的最大长度
struct Node{ //静态链表的结构类型定义
ElemType date； //存储数据元素
int next; //下一个元素数组下标
}SLinkList[MaxSize];
插入为i的结点：
1）找到一个空的结点存入数据元素
2）从头结点出发找到位序为i-1的结点
3) 修改新的结点next
4）修改i -1 的结点next
插入
若在第6个元素之前插入一个元素25，则只需将25放入data[]数组的尾部，即data[9]=25，然后修改后继数组next[5]=9，next[9]=6
插入之后，next[5]=9，next[9]=6，也就是说节点5的后继为9，节点9的后继为6，节点6的前驱为9，节点9的后继为6
相当于节点9被插入节点5和节点6之间，即插入节点6之前。也就是说，元素49的后继为25，元素25的后继为20。这就相当于把元素25插入49、20之间。是不是也很方便？不需要移动元素，只改动后继数组就可以了。
删除
若删除第3个元素，则只需修改后继数组next[2]=4，。此时，2的后继为4，相当于把第3个元素跳过去了，实现了删除功能，而第3个元素并未被真正删除，只是它已不在链表中。这样做的好处是不需要移动大量的元素。
- 点赞
- 收藏
- 关注作者
评论（0）