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

四、單鏈表的基本運(yùn)算
建立了一個(gè)單鏈表之后，如果要進(jìn)行一些如插入、刪除等操作該怎么辦？所以還須掌握一些單鏈表的基本算法，來(lái)實(shí)現(xiàn)這些操作。單鏈表的基本運(yùn)算包括：查找、插入和刪除。下面我們就一一介紹這三種基本運(yùn)算的算法，并結(jié)合我們建立單鏈表的例子寫出相應(yīng)的程序。
1、查找
對(duì)單鏈表進(jìn)行查找的思路為：對(duì)單鏈表的結(jié)點(diǎn)依次掃描，檢測(cè)其數(shù)據(jù)域是否是我們所要查好的值，若是返回該結(jié)點(diǎn)的指針，否則返回NULL。
因?yàn)樵趩捂湵淼逆溣蛑邪�含了后繼結(jié)點(diǎn)的存儲(chǔ)地址，所以當(dāng)我們實(shí)現(xiàn)的時(shí)候，只要知道該單鏈表的頭指針，即可依次對(duì)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行檢測(cè)。
以下是應(yīng)用查找算法的一個(gè)例子：
#include
#include
#include /*包含一些字符串處理函數(shù)的頭文件*/
#define N 10

typedef struct node
{
char name[20];
struct node *link;
}stud;

stud * creat(int n) /*建立鏈表的函數(shù)*/
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
h->name[0]='\0';
h->link=NULL;
p=h;
for(i=0;i{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
p->link=s;
printf("請(qǐng)輸入第%d個(gè)人的姓名",i+1);
scanf("%s",s->name);
s->link=NULL;
p=s;
}
return(h);
}

stud * search(stud *h,char *x) /*查找鏈表的函數(shù)，其中h指針是鏈表的表頭指針，x指針是要查找的人的姓名*/
{
stud *p; /*當(dāng)前指針，指向要與所查找的姓名比較的結(jié)點(diǎn)*/
char *y; /*保存結(jié)點(diǎn)數(shù)據(jù)域內(nèi)姓名的指針*/
p=h->link;
while(p!=NULL)
{
y=p->name;
if(strcmp(y,x)==0) /*把數(shù)據(jù)域里的姓名與所要查找的姓名比較，若相同則返回0，即條件成立*/
return(p); /*返回與所要查找結(jié)點(diǎn)的地址*/
else p=p->link;
}
if(p==NULL)
printf("沒有查找到該數(shù)據(jù)!");
}

main()
{
int number;
char fullname[20];
stud *head,*searchpoint; /*head是表頭指針，searchpoint是保存符合條件的結(jié)點(diǎn)地址的指針*/
number=N;
head=creat(number);
printf("請(qǐng)輸入你要查找的人的姓名:");
scanf("%s",fullname);
searchpoint=search(head,fullname); /*調(diào)用查找函數(shù)，并把結(jié)果賦給searchpoint指針*/
}

2、插入（后插）
假設(shè)在一個(gè)單鏈表中存在2個(gè)連續(xù)結(jié)點(diǎn)p、q（其中p為q的直接前驅(qū)），若我們需要在p、q之間插入一個(gè)新結(jié)點(diǎn)s，那么我們必須先為s分配空間并賦值，然后使p的鏈域存儲(chǔ)s的地址，s的鏈域存儲(chǔ)q的地址即可。(p->link=s;s->link=q)，這樣就完成了插入操作。
下例是應(yīng)用插入算法的一個(gè)例子：
#include
#include
#include
#define N 10

typedef struct node
{
char name[20];
struct node *link;
}stud;

stud * creat(int n) /*建立單鏈表的函數(shù)*/
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
h->name[0]='\0';
h->link=NULL;
p=h;
for(i=0;i{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
p->link=s;
printf("請(qǐng)輸入第%d個(gè)人的姓名:",i+1);
scanf("%s",s->name);
s->link=NULL;
p=s;
}
return(h);
}

stud * search(stud *h,char *x) /*查找函數(shù)*/
{
stud *p;
char *y;
p=h->link;
while(p!=NULL)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->link;
}
if(p==NULL)
printf("沒有查找到該數(shù)據(jù)!");
}

void insert(stud *p) /*插入函數(shù)，在指針p后插入*/
{
char stuname[20];
stud *s; /*指針s是保存新結(jié)點(diǎn)地址的*/
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
printf("請(qǐng)輸入你要插入的人的姓名:");
scanf("%s",stuname);
strcpy(s->name,stuname); /*把指針stuname所指向的數(shù)組元素拷貝給新結(jié)點(diǎn)的數(shù)據(jù)域*/
s->link=p->link; /*把新結(jié)點(diǎn)的鏈域指向原來(lái)p結(jié)點(diǎn)的后繼結(jié)點(diǎn)*/
p->link=s; /*p結(jié)點(diǎn)的鏈域指向新結(jié)點(diǎn)*/
}

main()
{
int number;
char fullname[20]; /*保存輸入的要查找的人的姓名*/
stud *head,*searchpoint;
number=N;
head=creat(number); /*建立新鏈表并返回表頭指針*/
printf("請(qǐng)輸入你要查找的人的姓名:");
scanf("%s",fullname);
searchpoint=search(head,fullname); /*查找并返回查找到的結(jié)點(diǎn)指針*/
insert(searchpoint); /*調(diào)用插入函數(shù)*/
}