鏈表的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++進階技術文檔專題，或

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=/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); }