| 導購 | 订阅 | 在线投稿
分享
 
 
當前位置: 王朝網路 >> 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-31集大結局分集劇情介紹

簡介 《極品家丁》講述了現代白領林晚榮無意回到古代金陵,並追隨蕭二小姐化名“林三”進入蕭府,不料卻陰差陽錯上演了一出低級家丁拼搏上位的“林三升職記”。...

李溪芮《極品家丁》片尾曲《你就是我最愛的寶寶》歌詞

你就是我最愛的寶寶 - 李溪芮 (電視劇《極品家丁》片尾曲) 作詞:常馨內 作曲:常馨內 你的眉 又鬼馬的挑 你的嘴 又壞壞的笑 上一秒吵鬧 下...

烏梅的功效與作用以及烏梅的食用禁忌有哪些?

烏梅,又稱春梅,中醫認爲,烏梅味酸,性溫,無毒,具有安心、除熱、下氣、祛痰、止渴調中、殺蟲的功效,治肢體痛、肺痨病。烏梅泡水喝能治傷寒煩熱、止吐瀉,與幹姜一起制...

什麽是脂肪粒?如何消除臉部脂肪粒?

什麽是脂肪粒 在我們的臉上總會長一個個像脂肪的小顆粒,弄也弄不掉,而且顔色還是白白的。它既不是粉刺也不是其他的任何痘痘,它就是脂肪粒。 脂肪粒雖然也是由油脂...

網絡安全治理:國家安全保障的主要方向是打擊犯罪,而不是處置和懲罰受害者

來源:中國青年報 新的攻擊方法不斷湧現,黑客幾乎永遠占據網絡攻擊的上風,我們不可能通過技術手段杜絕網絡攻擊。國家安全保障的主要方向是打擊犯罪,而不是處置和懲罰...

河南夫妻在溫嶺網絡直播“造人”內容涉黃被刑事拘留

夫妻網絡直播“造人”爆紅   1月9日,溫嶺城北派出所接到南京警方的協查通告,他們近期打掉了一個涉黃直播APP平台。而根據掌握的線索,其中有一對涉案的夫妻主播...

如何防止牆紙老化?牆紙變舊變黃怎麽辦?

如何防止牆紙老化? (1)選擇透氣性好的牆紙 市場上牆紙的材質分無紡布的、木纖維的、PVC的、玻璃纖維基材的、布面的等,相對而言,PVC材質的牆紙最不透氣...

鮮肌之謎非日本生産VS鮮肌之謎假日貨是謠言

觀點一:破日本銷售量的“鮮肌之謎” 非日本生産 近一段時間,淘寶上架了一款名爲“鮮肌之謎的” 鲑魚卵巢美容液,號稱是最近日本的一款推出的全新護膚品,産品本身所...

中國最美古詩詞精選摘抄

系腰裙(北宋詞人 張先) 惜霜蟾照夜雲天,朦胧影、畫勾闌。人情縱似長情月,算一年年。又能得、幾番圓。 欲寄西江題葉字,流不到、五亭前。東池始有荷新綠,尚小如...

關于女人的經典語句

關于女人的經典語句1、【做一個獨立的女人】 思想獨立:有主見、有自己的人生觀、價值觀。有上進心,永遠不放棄自己的理想,做一份自己喜愛的事業,擁有快樂和成就...

未來我們可以和性愛機器人結婚嗎?

你想體驗機器人性愛嗎?你想和性愛機器人結婚嗎?如果你想,機器人有拒絕你的權利嗎? 近日,第二屆“國際人類-機器人性愛研討會”大會在倫敦金史密斯大學落下帷幕。而...

全球最變態的十個地方

10.土耳其地下洞穴城市 變態指數:★★☆☆☆ 這是土耳其卡帕多西亞的一個著名景點,傳說是當年基督教徒們爲了躲避戰爭而在此修建。裏面曾住著20000人,...

科學家稱,人類死亡後意識將在另外一個宇宙中繼續存活

據英國《每日快報》報道,一位科學家兼理論家Robert Lanza博士宣稱,世界上並不存在人類死亡,死亡的只是身體。他認爲我們的意識借助我們體內的能量生存,而且...

《屏裏狐》片頭曲《我愛狐狸精》歌詞是什麽?

《我愛狐狸精》 - 劉馨棋   (電視劇《屏裏狐》主題曲)   作詞:金十三&李旦   作曲:劉嘉   狐狸精 狐狸仙   千年修...

 
 
 
一、循環鏈表   循環鏈表是與單鏈表一樣,是一種鏈式的存儲結構,所不同的是,循環鏈表的最後一個結點的指針是指向該循環鏈表的第一個結點或者表頭結點,從而構成一個環形的鏈。   循環鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點:   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=/bbs/detail_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); }
󰈣󰈤
 
 
 
  免責聲明:本文僅代表作者個人觀點,與王朝網路無關。王朝網路登載此文出於傳遞更多信息之目的,並不意味著贊同其觀點或證實其描述,其原創性以及文中陳述文字和內容未經本站證實,對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾,請讀者僅作參考,並請自行核實相關內容。
 
 
陽光靓麗的模特兒(8)
陽光靓麗的模特兒(7)
陽光靓麗的模特兒(6)
陽光靓麗的模特兒(5)
秋-印象
德慶盤龍峽 一
松江印象之三
雲之南(寬幅)
 
>>返回首頁<<
 
 
 
 熱帖排行
 
 
 
 
© 2005- 王朝網路 版權所有