鏈表的C語言實現之單鏈表的插入運算

2019-11-17 05:10:24

字體：大中小

來源：轉載

供稿：網友

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

　　下例是應用插入算法的一個例子：

#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) /*建立單鏈表的函數*/
{
　stud *p,*h,*s;
　int i;
　if((h=(stud *)malloc(sizeof(stud)))==NULL)
　{
　　PRintf("不能分配內存空間!");
　　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("不能分配內存空間!");
　　　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) /*查找函數*/
{
　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("沒有查找到該數據!");
}

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

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

}