| 订阅 | 在线投稿
分享
 
 
当前位置: 王朝网络 >> c/c++ >> 链表的C语言实现之循环链表及双向链表
 

链表的C语言实现之循环链表及双向链表

2008-06-01 02:07:11 编辑來源:互联网 繁體版 评论
 
 
  一、循环链表

  循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。

  循环链表的运算与单链表的运算基本一致。所不同的有以下几点:

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

  }
链表的C语言实现之循环链表及双向链表
更多内容请看C/C++进阶技术文档专题,或

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

  }
 
 
 
上一篇《C语言的常用库函数使用方法分析及用途》
下一篇《在C语言中如何处理时间和日期》
 
 
 
 
 
 
日版宠物情人插曲《Winding Road》歌词

日版宠物情人2017的插曲,很带节奏感,日语的,女生唱的。 最后听见是在第8集的时候女主手割伤了,然后男主用嘴帮她吸了一下,插曲就出来了。 歌手:Def...

兄弟共妻,我成了他们夜里的美食

老钟家的两个儿子很特别,就是跟其他的人不太一样,魔一般的执着。兄弟俩都到了要结婚的年龄了,不管自家老爹怎么磨破嘴皮子,兄弟俩说不娶就不娶,老父母为兄弟两操碎了心...

如何磨出破洞牛仔裤?牛仔裤怎么剪破洞?

把牛仔裤磨出有线的破洞 1、具体工具就是磨脚石,下面垫一个硬物,然后用磨脚石一直磨一直磨,到把那块磨薄了,用手撕开就好了。出来的洞啊很自然的。需要猫须的话调几...

我就是扫描下图得到了敬业福和爱国福

先来看下敬业福和爱国福 今年春节,支付宝再次推出了“五福红包”活动,表示要“把欠大家的敬业福都还给大家”。 今天该活动正式启动,和去年一样,需要收集“五福”...

冰箱异味产生的原因和臭味去除的方法

有时候我们打开冰箱就会闻到一股异味,冰箱里的这种异味是因为一些物质发出的气味的混合体,闻起来让人恶心。 产生这些异味的主要原因有以下几点。 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.wangchao.net.cn/bbsdetail_1785395.html][img]http://image.wangchao.net.cn/it/1323423604313.gif[/img][/url] 更多内容请看C/C++进阶技术文档专题,或   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); }
󰈣󰈤
 
 
 
  免责声明:本文仅代表作者个人观点,与王朝网络无关。王朝网络登载此文出于传递更多信息之目的,并不意味着赞同其观点或证实其描述,其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
赏心悦目的模特儿(9)
赏心悦目的模特儿(8)
赏心悦目的模特儿(7)
赏心悦目的模特儿(6)
周六一日游--绿野翠蜂场(一)
骆驼峰
下一站上环
杂乱的几张Danang
 
>>返回首页<<
 
 
 为你推荐
 
 
 
 转载本文
 UBB代码 HTML代码
复制到剪贴板...
 
 热帖排行
 
 
 
 
©2005- 王朝网络 版权所有