投稿
  1. 首页
  2. python

数据结构——“双向循环链表“ 易懂刨析双向循环链表（图解+代码）

code • 2022-5-5 • python • 阅读 39

数据结构——“双向循环链表“ 易懂刨析双向循环链表（图解+代码）,第1张

循环链表
  • 单向循环链表
    • 循环链表和单链表的区别
    • 循环链表的特点
  • 双向循环链表——概念
    • 1. 双向循环链表——插入
    • 2. 双向循环链表——删除
  • 双向链表的插入创建
  • 双向链表——查找
  • 双向链表——插入
  • 双向链表——删除

单向循环链表 循环链表和单链表的区别

  1. 表中最后结点的指针不是NULL，而是改为指向头结点，从而整个链表形成了一个环。

  2. 循环单链表中没有指针域为NULL的结点，故判空条件为判断 *A （表尾节点） *A 的next是否为头指针

  3. 空表：if(A->next == H) { 空表 }

循环链表的特点
  • 循环单链表插入，删除算法于单链表几乎一样

正是因为循环单链表是一个“环”，在任何位置插入和删除 *** 作都是等价的，无须判断是否是表全。循环链表可以从任意一个结点开始遍历整个链表，循环链表不设头指针而仅设尾指针，若只设置尾指针A，A->next即为头指针，对表头，表尾进行 *** 作都只要O(n).

  • 关于两个循环链表合并为一个循环链表
双向循环链表——概念

在单链表L中，查找ai的后继Next(L，a;)，耗时仅为O(1)，因为取ai后继指针即可。
但查找ai的直接前驱Prior(L，ai);则需从链表的头指针开始，找到结点ai前一结点即是。故运算Prior(L，ai)依赖表长n，耗时为O(n)。另外，若链表中有一指针值被破坏，则整个链表脱节。这是单链表的不足

为此，引入双向链表。先定义双向链表中的结点:

其中，data和next同单链表，增加一指针域prior，其指向本结点的直接前驱。
结点描述:

typedef int data_t; 
typedef struct dnode_t
{ 
        data_tdata;
        struct dnode_t *prior;
        struct dnode_t *next;
}dlinknode_t , *dlinklist_t;
  • 表L=(a0·····an-1)(设n=2) 的双向循环链表如图：

    设p为链表中某结点的指针，有对称性：
  (p->prior)->next = p =(p->next)->prior
  • 双向链表的查找等运算基本上和单链表类似。
  • 在双向循环链表中，某结点 *p 为尾结点时，p->next == H,当循环双链表尾空表时，某头结点的prior域和next域都等于H

下面我们学习一下双向循环链表的插入和删除运算

1. 双向循环链表——插入

插入： 即实现在链表L的第i结点前插入一结点x的运算，如图

① q->prior = p->prior;
② (p->prior)->next = q;
③ q->next = p;
④ p->prior=q;
  • 算法思路：
    调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在，申请一q结点，存入元素x，然后修改指针，将q结点插入p结点之前。
    此算法时间复杂度主要算在查找算法getlist(L,i);上，故T(n)=O(n);
2. 双向循环链表——删除

删除： 即实现删除链表L的第i结点 的运算，如图

  • 算法思路：
    调用查找算法Getlist(L,i);,获取结点ai的指针p，若p存在，则修改指针删除

概念我们了解了，接下来我们要去实现双向链表的 *** 作。

双向链表的插入创建

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include
#include

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;


extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
#endif


文件二：dlist.c 插入创建双向链表

#include"dlist.h"

//创建双向链表
dlistnode *dlist_create(){
   dlistnode *H,*p,*r;
   int num;

   if(( H =(dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	puts("malloc failed");
	return NULL;
   }
   //建立空双向链表
   H->prior = H;   //头结点前驱后继都指向自己
   H->next = H;    
   r = H;          //指针r 指向头结点
   //用户输入
   while(1) {
       puts("please input(-1 exit):");
       scanf("%d",&num);
       if(num == -1){
	       puts("-1 exit");
	       break;
       }

       if((p = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	puts("malloc failed");
	return NULL;
       }
       //新节点赋值
       p->data = num;
       
       //插入双向链表
       p->prior = r;
       p->next = r->next;
       r->next = p;
       H->prior = p;
       r = p;

   } 
   return H;
}

//遍历链表并输出链表数据
void dlist_show(dlistnode *H){

   dlistnode *p;
   p = H->next;

   while(p != H){
       printf("%d ",p->data);
       p=p->next;
   }
   puts("");
}

文件三：test.c 插入创建双向链表

#include"dlist.h"


int main(){

   dlistnode *H;

   H=dlist_create();

   dlist_show(H);

   return 0;
}

双向链表——查找

查找：getlist(L,i);提供要查找结点ai的编号，返回指向该结点ai的指针

结点个数 n=3; i的范围【0，n-1】

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include
#include

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos)；
#endif

文件二：dlist.c 按位查找双向链表

dlistnode *dlist_get(dlistnode *H,int pos){
    int i =-1;
    dlistnode *p = H;

    if(pos < 0){
        puts("pos < 0,invalid");
        return NULL;
    }
    
    while(i < pos){
	   p = p->next;
	   i++;
	   if(p == H){
	       puts("pos is invalid");
	       return NULL;
	   }
    }
    return p;
}

文件三：test.c 用户输入按位查找双向链表

#include"dlist.h"


int main(){

   dlistnode *H,*p;
   int pos;

   H=dlist_create();

   dlist_show(H);
   
   //用户输入按位查找
   while(1){
      puts("input pos");
      scanf("%d",&pos);
      p =  dlist_get(H,pos);
      if(p){
         printf("%d \n",p->data);
      }
   }
   return 0;
}

双向链表——插入

插入： 即实现在链表L的第i结点前插入一结点x的运算，如图

  • 算法思路：
    调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在，申请一q结点，存入元素x，然后修改指针，将q结点插入p结点之前。
    此算法时间复杂度主要算在查找算法getlist(L,i);上，故T(n)=O(n);

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include
#include

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos);
extern int dlist_insert(dlistnode *H , int value ,int pos);
#endif

文件二：dlist.c 按位插入双向链表

int dlist_insert(dlistnode *H , int value ,int pos){
	dlistnode *p,*q;

	p = dlist_get(H,pos);
	if(p == NULL){
            return -1;
	}
        
        if((q = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	   puts("malloc failed");
	   return -1;
        } 
	q->data = value;

	q->prior = p->prior;
	q->next = p;
	p->prior->next = q;
	q->prior = q;

	return 0;
}

文件三：test.c 用户输入按位插入双向链表

#include"dlist.h"


int main(){

   dlistnode *H;
   int pos;

   H=dlist_create();

   dlist_show(H);
   
   //用户输入按位查找
     while(1){
      puts("input pos");
      scanf("%d",&pos);
      
      dlist_insert(H,100,pos);
      dlist_show(H);
      }
   return 0;
}

双向链表——删除

删除： 即实现删除链表L的第i结点 的运算，如图

 p->prior->next = p->next;
 p->next->prior = p-prior;
  • 算法思路：
    调用查找算法Getlist(L,i);,获取结点ai的指针p，若p存在，则修改指针删除
    文件一：dlist.h 插入创建双向链表
#ifndef __DLIST_H__
#define __DLIST_H__
#include
#include

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos);
extern int dlist_insert(dlistnode *H , int value ,int pos);
extern int dlist_delete(dlistnode *H ,int pos);
#endif

文件二：dlist.c 用户输入按位删除双向链表

int dlist_delete(dlistnode *H ,int pos){
    dlistnode *p;

    p = dlist_get(H,pos);
    if(p == NULL){
            return -1;
    }
    
    p->prior->next = p->next;
    p->next->prior = p-prior;

    free(p);
    p=NULL;
    return 0;
}

文件三：test.c 用户输入按位删除双向链表

#include"dlist.h"

int main(){

   dlistnode *H;
   int pos;

   H=dlist_create();

   dlist_show(H);

    while(1){
      puts("input pos");
      scanf("%d",&pos);
      
      dlist_delete(H,pos);
      dlist_show(H);
    }
   return 0;
}

-----------------------------------------很棒学习完了数据结构的 双向循环链表--------------------------------------------------

--------------------------------------------------------[下期预告：线性表的应用举例]------------------------------------------------------

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/790728.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表（0条）

保存