鏈表的C語言實現(xiàn)之單鏈表的插入運算

2019-11-17 05:10:24

字體：大中小

供稿：網(wǎng)友

　　假設(shè)在一個單鏈表中存在2個連續(xù)結(jié)點p、q（其中p為q的直接前驅(qū)），若我們需要在p、q之間插入一個新結(jié)點s，那么我們必須先為s分配空間并賦值，然后使p的鏈域存儲s的地址，s的鏈域存儲q的地址即可。(p-＞link=s;s-＞link=q)，這樣就完成了插入操作。

　　下例是應(yīng)用插入算法的一個例子：

#include ＜stdio.h＞
#include ＜malloc.h＞
#include ＜string.h＞
#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＜n;i++)
　{
　　if((s= (stud *) malloc(sizeof(stud)))==NULL)
　　{
　　　printf("不能分配內(nèi)存空間!");
　　　exit(0);
　　}
　　p-＞link=s;
　　printf("請輸入第%d個人的姓名:",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é)點地址的*/
　if((s= (stud *) malloc(sizeof(stud)))==NULL)
　{
　　printf("不能分配內(nèi)存空間!");
　　exit(0);
　}
　printf("請輸入你要插入的人的姓名:");
　scanf("%s",stuname);
　strcpy(s-＞name,stuname); /*把指針stuname所指向的數(shù)組元素拷貝給新結(jié)點的數(shù)據(jù)域*/
　s-＞link=p-＞link; /*把新結(jié)點的鏈域指向原來p結(jié)點的后繼結(jié)點*/
　p-＞link=s; /*p結(jié)點的鏈域指向新結(jié)點*/
}

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

}