循环链表

单向循环链表

循环链表和单链表的区别

  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<stdio.h>
#include<stdlib.h>

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<stdio.h>
#include<stdlib.h>

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<stdio.h>
#include<stdlib.h>

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<stdio.h>
#include<stdlib.h>

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;
}

在这里插入图片描述

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

在这里插入图片描述

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

# c语言 # 算法 # 数据结构 # 链表
Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

avatar GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

avatar GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m

avatar GitCode 开源社区