計算機(jī)等級考試二級C語言鏈表復(fù)習(xí)專題

四、循環(huán)鏈表
循環(huán)鏈表是與單鏈表一樣，是一種鏈?zhǔn)降拇鎯�結(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個結(jié)點的指針是指向該循環(huán)鏈表的第一個結(jié)點或者表頭結(jié)點，從而構(gòu)成一個環(huán)形的鏈。
循環(huán)鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點：
1、在建立一個循環(huán)鏈表時，必須使其最后一個結(jié)點的指針指向表頭結(jié)點，而不是象單鏈表那樣置為NULL。此種情況還使用于在最后一個結(jié)點后插入一個新的結(jié)點。
2、在判斷是否到表尾時，是判斷該結(jié)點鏈域的值是否是表頭結(jié)點，當(dāng)鏈域值等于表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。

五、雙向鏈表
雙向鏈表其實是單鏈表的改進(jìn)。
當(dāng)我們對單鏈表進(jìn)行操作時，有時你要對某個結(jié)點的直接前驅(qū)進(jìn)行操作時，又必須從表頭開始查找。這是由單鏈表結(jié)點的結(jié)構(gòu)所限制的。因為單鏈表每個結(jié)點只有一個存儲直接后繼結(jié)點地址的鏈域，那么能不能定義一個既有存儲直接后繼結(jié)點地址的鏈域，又有存儲直接前驅(qū)結(jié)點地址的鏈域的這樣一個雙鏈域結(jié)點結(jié)構(gòu)呢？這就是雙向鏈表。
在雙向鏈表中，結(jié)點除含有數(shù)據(jù)域外，還有兩個鏈域，一個存儲直接后繼結(jié)點地址，一般稱之為右鏈域；一個存儲直接前驅(qū)結(jié)點地址，一般稱之為左鏈域。在c語言中雙向鏈表結(jié)點類型可以定義為：
typedef struct node
{
int data; /*數(shù)據(jù)域*/
struct node *llink,*rlink; /*鏈域，*llink是左鏈域指針，*rlink是右鏈域指針*/
}JD;
當(dāng)然，也可以把一個雙向鏈表構(gòu)建成一個雙向循環(huán)鏈表。
雙向鏈表與單向鏈表一樣，也有三種基本運算：查找、插入和刪除。

雙向鏈表的基本運算：
1、查找
假若我們要在一個帶表頭的雙向循環(huán)鏈表中查找數(shù)據(jù)域為一特定值的某個結(jié)點時，我們同樣從表頭結(jié)點往后依次比較各結(jié)點數(shù)據(jù)域的值，若正是該特定值，則返回指向結(jié)點的指針，否則繼續(xù)往后查，直到表尾。
下例就是應(yīng)用雙向循環(huán)鏈表查找算法的一個程序。
#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("不能分配內(nèi)存空間!");
exit(0);
}
h->name[0]='\0';
h->llink=NULL;
h->rlink=NULL;
p=h;
for(i=0;i{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
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("沒有查找到該數(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);
}

2、插入
對于雙向循環(huán)鏈表，我們現(xiàn)在可以隨意地在某已知結(jié)點p前或者p后插入一個新的結(jié)點。
假若s,p,q是連續(xù)三個結(jié)點的指針，若我們要在p前插入一個新結(jié)點r，則只需把s的右鏈域指針指向r，r的左鏈域指針指向s，r的右鏈域指針指向p，p的左鏈域指針指向r即可。
在p,q之間插入原理也一樣。
下面就是一個應(yīng)用雙向循環(huán)鏈表插入算法的例子：
#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("不能分配內(nèi)存空間!");
exit(0);
}
h->name[0]='\0';
h->llink=NULL;
h->rlink=NULL;
p=h;
for(i=0;i{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
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("沒有查找到該數(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");
}

void insert(stud *p)
{
char stuname[20];
stud *s;
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
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);
}

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

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