当前位置：首页 > news >正文

C语言双链表，循环链表，静态链表讲解（王道版）

news 来源：原创 2024/5/19 6:45:04

一、双链表

初始化（带头结点）：

双链表的插入：

双链表的遍历

循环链表

循环单链表的初始化

循环双链表的初始化

双链表的插入

双链表的删除

静态链表

定义静态链表

插入

删除

一、双链表

在单链表中，每个元素都附加了一个指针域，指向下一个元素的存储位置。在双向链表中，每个元素都附加了两个指针域，分别指向前驱节点和后继节点。

单链表只能向后操作，不能向前操作。为了向前、向后操作方便，可以给每个元素都附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表被称为双向链表示。

从上图中可以看出，双向链表的每个节点都包含三个域：数据域和两个指针域。两个指针域分别存储前后两个元素的地址，即指向前驱节点和后继节点。

初始化（带头结点）：

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