| 订阅 | 在线投稿
分享
 
 
 

链表的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);

  }
 
 
一、循环链表   循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。   循环链表的运算与单链表的运算基本一致。所不同的有以下几点:   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); }
󰈣󰈤
日版宠物情人插曲《Winding Road》歌词

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

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

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

网络安全治理:国家安全保障的主要方向是打击犯罪,而不是处置和惩罚受害者

来源:中国青年报 新的攻击方法不断涌现,黑客几乎永远占据网络攻击的上风,我们不可能通过技术手段杜绝网络攻击。国家安全保障的主要方向是打击犯罪,而不是处置和惩罚...

 
 
 
>>返回首页<<
 为你推荐
 
 
 
 转载本文
 UBB代码 HTML代码
复制到剪贴板...
 
 
 热帖排行
 
美女灿烂的笑容(二)
美女灿烂的笑容(一)
...雨秋
欧洲
 
 
王朝网络微信公众号
微信扫码关注本站公众号wangchaonetcn
 
  免责声明:本文仅代表作者个人观点,与王朝网络无关。王朝网络登载此文出于传递更多信息之目的,并不意味着赞同其观点或证实其描述,其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
©2005- 王朝网络 版权所有