鏈表的C語言實(shí)現(xiàn)之循環(huán)鏈表及雙向鏈表

2019-11-17 05:01:50

字體：大中小

供稿：網(wǎng)友

一、循環(huán)鏈表

　　循環(huán)鏈表是與單鏈表一樣，是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn)，從而構(gòu)成一個(gè)環(huán)形的鏈。

　　循環(huán)鏈表的運(yùn)算與單鏈表的運(yùn)算基本一致。所不同的有以下幾點(diǎn)：

　　1、在建立一個(gè)循環(huán)鏈表時(shí)，必須使其最后一個(gè)結(jié)點(diǎn)的指針指向表頭結(jié)點(diǎn)，而不是象單鏈表那樣置為NULL。此種情況還使用于在最后一個(gè)結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)。

　　2、在判定是否到表尾時(shí)，是判定該結(jié)點(diǎn)鏈域的值是否是表頭結(jié)點(diǎn)，當(dāng)鏈域值等于表頭指針時(shí)，說明已到表尾。而非象單鏈表那樣判定鏈域值是否為NULL。

　　二、雙向鏈表

　　雙向鏈表其實(shí)是單鏈表的改進(jìn)。

　　當(dāng)我們對單鏈表進(jìn)行操作時(shí)，有時(shí)你要對某個(gè)結(jié)點(diǎn)的直接前驅(qū)進(jìn)行操作時(shí)，又必須從表頭開始查找。這是由單鏈表結(jié)點(diǎn)的結(jié)構(gòu)所限制的。因?yàn)閱捂湵砻總€(gè)結(jié)點(diǎn)只有一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址的鏈域，那么能不能定義一個(gè)既有存儲(chǔ)直接后繼結(jié)點(diǎn)地址的鏈域，又有存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址的鏈域的這樣一個(gè)雙鏈域結(jié)點(diǎn)結(jié)構(gòu)呢？這就是雙向鏈表。

　　在雙向鏈表中，結(jié)點(diǎn)除含有數(shù)據(jù)域外，還有兩個(gè)鏈域，一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址，一般稱之為右鏈域；一個(gè)存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址，一般稱之為左鏈域。在c語言中雙向鏈表結(jié)點(diǎn)類型可以定義為：

typedef strUCt node
{
int data; /*數(shù)據(jù)域*/
struct node *llink,*rlink; /*鏈域，*llink是左鏈域指針，*rlink是右鏈域指針*/
}JD;
　　當(dāng)然，也可以把一個(gè)雙向鏈表構(gòu)建成一個(gè)雙向循環(huán)鏈表。

　　雙向鏈表與單向鏈表一樣，也有三種基本運(yùn)算：查找、插入和刪除。

　　雙向鏈表的基本運(yùn)算：

　　1、查找

　　假若我們要在一個(gè)帶表頭的雙向循環(huán)鏈表中查找數(shù)據(jù)域?yàn)橐惶囟ㄖ档哪硞€(gè)結(jié)點(diǎn)時(shí)，我們同樣從表頭結(jié)點(diǎn)往后依次比較各結(jié)點(diǎn)數(shù)據(jù)域的值，若正是該特定值，則返回指向結(jié)點(diǎn)的指針，否則繼續(xù)往后查，直到表尾。

　　下例就是應(yīng)用雙向循環(huán)鏈表查找算法的一個(gè)程序。

#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)
　{
　　　　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("不能分配內(nèi)存空間!");
　　　exit(0);
　　}
　　p-＞rlink=s;
　　printf("請輸入第%d個(gè)人的姓名",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("沒有查找到該數(shù)據(jù)!");
}

void print(stud *h)
{
　int n;
　stud *p;
　p=h-＞rlink;
　printf("數(shù)據(jù)信息為：/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);