科技行者

行者学院 转型私董会 科技行者专题报道 网红大战科技行者

知识库

知识库 安全导航

至顶网软件频道基础软件链表的C语言实现之循环链表及双向链表

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

  • 扫一扫
    分享文章到微信

  • 扫一扫
    关注官方公众号
    至顶头条

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

作者:leton2008 来源:BLOG 2007年10月27日

关键字: C语言 循环链表 双向链表 Linux

  • 评论
  • 分享微博
  • 分享邮件
一、循环链表

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

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

  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);
}
    • 评论
    • 分享微博
    • 分享邮件
    闂傚倸鍊风欢锟犲矗鎼淬劌绐楅柡鍥╁亹閺嬪酣鏌曡箛瀣仾濠殿垰銈搁弻鏇$疀鐎n亖鍋撻弽顓ㄧ稏闁跨噦鎷�

    婵犵數濮烽。浠嬪焵椤掆偓閸熷潡鍩€椤掆偓缂嶅﹪骞冨Ο璇茬窞闁归偊鍓涢悾娲⒑闂堟单鍫ュ疾濠婂嫭鍙忔繝濠傜墛閸嬨劍銇勯弽銊с€掗柟钘夊暣閺岀喖鎮滈埡鍌涚彋閻庤娲樺畝绋跨暦閸洖鐓涢柛灞剧矋濞堟悂姊绘担绛嬪殐闁搞劋鍗冲畷銏ゅ冀椤愩儱小闂佹寧绋戠€氼參宕伴崱妯镐簻闁靛牆鎳庢慨顒€鈹戦埥鍡椾簼婵犮垺锚铻炴俊銈呮噺閸嬪倹绻涢崱妯诲碍閻庢艾顦甸弻宥堫檨闁告挾鍠庨锝夘敆娓氬﹦鐭楁繛鎾村焹閸嬫捇鏌e☉娆愬磳闁哄本绋戦埞鎴﹀川椤曞懏鈻婄紓鍌欑劍椤ㄥ懘鎯岄崒鐐靛祦閹兼番鍔岄悞鍨亜閹烘垵顏╅悗姘槹閵囧嫰寮介妸褎鍣ョ紓浣筋嚙濡繈寮婚悢纰辨晣鐟滃秹鎮橀懠顒傜<閺夊牄鍔庣粻鐐烘煛鐏炶姤鍠橀柡浣瑰姍瀹曠喖顢橀悩铏钒闂備浇宕垫慨鎶芥⒔瀹ュ鍨傞柦妯猴級閿濆绀嬫い鏍ㄧ☉濞堟粓姊虹涵鍛【妞ゎ偅娲熼崺鈧い鎺嗗亾闁挎洩濡囧Σ鎰板籍閸繄顓洪梺缁樺姇瀵剙螖閸涱喚鍘搁梺鍓插亽閸嬪嫰鎮橀敃鍌涚厱閻庯綆鍋嗘晶顒傜磼閸屾稑绗ч柟鐟板閹煎湱鎲撮崟闈涙櫏闂傚倷绀侀幖顐も偓姘卞厴瀹曞綊鏌嗗鍛紱閻庡箍鍎遍ˇ浼村磿瀹ュ鐓曢柡鍥ュ妼婢ь垰霉閻樿秮顏堟箒闂佹寧绻傚Λ妤呭煝閺囥垺鐓冪憸婊堝礈濮樿泛钃熼柕濞у嫷鍋ㄩ梺缁樺姇椤曨參鍩㈤弴銏″€甸柨婵嗗€瑰▍鍥ㄣ亜韫囨稐鎲鹃柡灞炬礋瀹曢亶顢橀悢濂変紦

    重磅专题
    往期文章
    最新文章