鏈表的C語言實現之循環鏈表及雙向鏈表

一、循環鏈表

循環鏈表是與單鏈表一樣,是一種鏈式的存儲結構,所不同的是,循環鏈表的最後一個結點的指針是指向該循環鏈表的第一個結點或者表頭結點,從而構成一個環形的鏈。

循環鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點:

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

}

用VB實現雙向循環鏈表
作者:zgl郵箱:yoshiro_gl@21cn.com  發現大多數人對VB中應用指針不太了解,作一些說明。  VB的指針挺簡單的,用著也很方便,其實對象變量就可以看成是指針,當你用Set A=Obj時,A就是指向Obj的地址。不用API就...查看完整版>>用VB實現雙向循環鏈表
 
JAVA 語言中鏈表和雙向鏈表的實現
鏈表是一種重要的數據結構,在程序設計中占有很重要的地位。C語言和C++語言中是用指針來實現鏈表結構的,由于Java語言不提供指針,所以有人認爲在JAVA語言中不能實現鏈表,其實不然,JAVA語言比C和C++更輕易實現鏈表...查看完整版>>JAVA 語言中鏈表和雙向鏈表的實現
 
JAVA語言中鏈表和雙向鏈表的實現
  鏈表是一種重要的數據結構,在程序設計中占有很重要的地位。C語言和C++語言中是用指針來實現鏈表結構的,由于JAVA語言不提供指針,所以有人認爲在JAVA語言中不能實現鏈表,其實不然,JAVA語言比C和C++更容易實現...查看完整版>>JAVA語言中鏈表和雙向鏈表的實現
 
Java語言中鏈表和雙向鏈表的實現
出處:csdn鏈表是一種重要的數據結構,在程序設計中占有很重要的地位。C語言和C++語言中是用指針來實現鏈表結構的,由于Java語言不提供指針,所以有人認爲在Java語言中不能實現鏈表,其實不然,Java語言比C和C++更...查看完整版>>Java語言中鏈表和雙向鏈表的實現
 
循環鏈表以及相關操作(VB實現)
循環鏈表以及相關操作(VB實現)首先建立一個工程,然後增加一個類並且命名爲(node,cls),在node.cls中加入以下代碼.Option ExplicitPublic x As LongPublic count As LongPublic nextnode As node在Form1.frm中加入以...查看完整版>>循環鏈表以及相關操作(VB實現)
 
鏈表的C語言實現之刪除結點
  假如我們已經知道了要刪除的結點p的位置,那麽要刪除p結點時只要令p結點的前驅結點的鏈域由存儲p結點的地址該爲存儲p的後繼結點的地址,並回收p結點即可。   以下便是應用刪除算法的實例:      #include ...查看完整版>>鏈表的C語言實現之刪除結點
 
DataStructure---LinkList 鏈表C語言實現代碼
//=============================================================//鏈表具體函數實現部分//=============================================================#include "LinkList.h"#include <malloc.h...查看完整版>>DataStructure---LinkList 鏈表C語言實現代碼
 
用C++編寫的基于雙向鏈表的CPtrArray類
用過VC的人可能都用過其中各種各樣的Array類,在我也常用到,這讓我編寫程序方便了很多。 做電力自動化的同行可能都知道,咱這行興組態這個方法,不管理是做什麽軟件,都要組態一把,呵呵,說來笑話,直到今天我...查看完整版>>用C++編寫的基于雙向鏈表的CPtrArray類
 
單片機C語言實現循環移位
首先聲明:我學習單片機C語言還不到半年,所以我還是菜鳥,我貼出的東西或許你們都知道,但我只想把我學習的經曆給記錄下來,希望你能找到你所想要的. 我記得做學單片機做的第一個實驗就是做循環彩燈的實驗,如果用彙編RL...查看完整版>>單片機C語言實現循環移位
 
 
回到王朝網路移動版首頁