循环链表及双向链表

举报
清雨小竹 发表于 2022/09/25 00:55:30 2022/09/25
【摘要】 一、循环链表   循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。   循环链表的运算与单链表的运算基本一致。所不同的有以下几点:   1、在...
一、循环链表
  循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。
  循环链表的运算与单链表的运算基本一致。所不同的有以下几点:
  1、在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。 
  2、在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域值等于表头指针时,说明已到表尾。而非象单链表那样判断链域值是否为NULL。 

二、双向链表 
双向链表其实是单链表的改进。
当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有 一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。
在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域;一个存储直接前驱结点地址,一般称之为左链域。在c语言中双向链表结点类型可以定义为: 
typedef struct node
{
  int data; /*数据域*/
  struct node *llink, *rlink; /*链域,*llink是左链域指针,*rlink是右链域指针*/
} JD;
 
  当然,也可以把一个双向链表构建成一个双向循环链表。
  双向链表与单向链表一样,也有三种基本运算:查找、插入和删除。
  双向链表的基本运算:
  1、查找
  假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时,我们同样从表头结点往后依次比较各结点数据域的值,若正是该特定值,则返回指向结点的指针,否则继续往后查,直到表尾。
下例就是应用双向循环链表查找算法的一个程序。 
#include <stdio.h>
#include <malloc.h>
#define N 10
 
typedef struct node
{
     char name[20];
     struct node *llink,*rlink;
}stud;
 
stud * creat(int n)
{
   stud *p, *h, *s;
   int i;
   if((h=(stud *)malloc(sizeof(stud)))==NULL)
     
    {
         printf("不能分配内存空间!");
         exit(0);
        }
     h->name[0]=’\0’;
     h->llink=NULL;
     h->rlink=NULL;
     p=h;
     for(i=0;i<n;i++)
     
    {
         if((s= (stud *) malloc(sizeof(stud)))==NULL)
         
       {
              printf("不能分配内存空间!");
              exit(0);
             }
         p->rlink=s;
         printf("请输入第%d个人的姓名",i+1);
         scanf("%s",s->name);
         s->llink=p;
         s->rlink=NULL;
         p=s;
        }
     h->llink=s;
     p->rlink=h;
     return(h);
}
 
stud * search(stud *h, char *x)
{
   stud *p;
   char *y;
   p=h->rlink;
   while(p!=h)
     
    {
         y=p->name;
         if(strcmp(y,x)==0)
          return(p);
         
       else p=p->rlink;
        }
     printf("没有查找到该数据!");
}
 
void print(stud *h)
{
   int n;
   stud *p;
   p=h->rlink;
   printf("数据信息为:\n");
   while(p!=h)
     
    {
          printf("%s ",&*(p->name));
         p=p->rlink;
        }
     printf("\n");
}
 
main()
{
   int number;
   char studname[20];
   stud *head, *searchpoint;
   number=N;
   clrscr();
   head=creat(number);
   print(head);
   printf("请输入你要查找的人的姓名:");
   scanf("%s", studname);
   searchpoint=search(head, studname);
   printf("你所要查找的人的姓名是:%s", *&searchpoint->name);
}
 
  2、插入
  对于双向循环链表,我们现在可以随意地在某已知结点p前或者p后插入一个新的结点。
  假若s,p,q是连续三个结点的指针,若我们要在p前插入一个新结点r,则只需把s的右链域指针指向r,r的左链域指针指向s,r的右链域指针指向p,p的左链域指针指向r即可。
  在p,q之间插入原理也一样。
下面就是一个应用双向循环链表插入算法的例子:
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define N 10
 
typedef struct node
{
     char name[20];
     struct node *llink,*rlink;
}stud;
 
stud * creat(int n)
{
   stud *p, *h, *s;
   int i;
   if((h=(stud *)malloc(sizeof(stud)))==NULL)
     
    {
         printf("不能分配内存空间!");
         exit(0);
        }
     h->name[0]=’\0’;
     h->llink=NULL;
     h->rlink=NULL;
     p=h;
     for(i=0;i<n;i++)
     
    {
         if((s= (stud *) malloc(sizeof(stud)))==NULL)
         
       {
              printf("不能分配内存空间!");
              exit(0);
             }
         p->rlink=s;
         printf("请输入第%d个人的姓名",i+1);
         scanf("%s",s->name);
         s->llink=p;
         s->rlink=NULL;
         p=s;
        }
     h->llink=s;
     p->rlink=h;
     return(h);
}
 
stud * search(stud *h, char *x)
{
   stud *p;
   char *y;
   p=h->rlink;
   while(p!=h)
     
    {
         y=p->name;
         if(strcmp(y,x)==0)
          return(p);
         
       else p=p->rlink;
        }
     printf("没有查找到该数据!");
}
 
void print(stud *h)
{
   int n;
   stud *p;
   p=h->rlink;
   printf("数据信息为:\n");
   while(p!=h)
     
    {
         printf("%s ",&*(p->name));
         p=p->rlink;
        }
     printf("\n");
}
 
void insert(stud *p)
{
   char stuname[20];
   stud *s;
   if((s= (stud *) malloc(sizeof(stud)))==NULL)
     
    {
         printf("不能分配内存空间!");
         exit(0);
        }
     printf("请输入你要插入的人的姓名:");
     scanf("%s",stuname);
     strcpy(s->name,stuname);
     s->rlink=p->rlink;
     p->rlink=s;
     s->llink=p;
     (s->rlink)->llink=s;
}
 
main()
{
   int number;
   char studname[20];
   stud *head, *searchpoint;
   number=N;
   clrscr();
   head=creat(number);
   print(head);
   printf("请输入你要查找的人的姓名:");
   scanf("%s", studname);
   searchpoint=search(head, studname);
   printf("你所要查找的人的姓名是:%s\n", *&searchpoint->name);
   insert(searchpoint);
   print(head);
} [url=http://www.bccn.net/Article/kfyy/cyy/jszl/200603/3845.html][/url]
  3、删除
  删除某个结点,其实就是插入某个结点的逆操作。还是对于双向循环链表,要在连续的三个结点s,p,q中删除p结点,只需把s的右链域指针指向q,q的左链域指针指向s,并收回p结点就完成了。
下面就是一个应用双向循环链表删除算法的例子:
#include 
#include 
#include 
#define N 10 
 
typedef struct node
{
   char name[20];
   struct node *llink, *rlink;
} stud;
 
stud * creat(int n)
{
   stud *p, *h, *s;
   int i;
   if((h=(stud *)malloc(sizeof(stud)))==NULL)
     
    {
         printf("不能分配内存空间!");
         exit(0);
        }
     h->name[0]=’\0’;
     h->llink=NULL;
     h->rlink=NULL;
     p=h;
     for(i=0;i〈n;i++)
     
    {
         if((s= (stud *) malloc(sizeof(stud)))==NULL)
         
       {
              printf("不能分配内存空间!");
              exit(0);
             }
         p-〉rlink=s;
         printf("请输入第%d个人的姓名",i+1);
         scanf("%s",s->name);
         s->llink=p;
         s->rlink=NULL;
         p=s;
        }
     h->llink=s;
     p->rlink=h;
     return(h);
}
 
stud * search(stud *h, char *x)
{
   stud *p;
   char *y;
   p=h->rlink;
   while(p!=h)
     
    {
         y=p->name;
         if(strcmp(y,x)==0)
          return(p);
         
       else p=p->rlink;
        }
     printf("没有查找到该数据!");
}
 
void print(stud *h)
{
   int n;
   stud *p;
   p=h->rlink;
   printf("数据信息为:\n");
   while(p!=h)
     
    {
         printf("%s ",&*(p->name));
         p=p->rlink;
        }
     printf("\n");
}
 
void del(stud *p)
{
   (p->rlink)->llink=p->llink;
     (p->llink)->rlink=p->rlink;
     free (p);
}
 
main()
{
   int number;
   char studname[20];
   stud *head, *searchpoint;
   number=N;
   clrscr();
   head=creat(number);
   print(head);
   printf("请输入你要查找的人的姓名:");
   scanf("%s", studname);
   searchpoint=search(head, studname);
   printf("你所要查找的人的姓名是:%s\n", *&searchpoint->name);
   del(searchpoint);
   print(head);
}

文章来源: zzzili.blog.csdn.net,作者:清雨小竹,版权归原作者所有,如需转载,请联系作者。

原文链接:zzzili.blog.csdn.net/article/details/8265335

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。