鏈表的C語(yǔ)言實(shí)現(xiàn)之單鏈表的實(shí)現(xiàn)

一、單鏈表的建立
    有了動(dòng)態(tài)內(nèi)存分配的基礎(chǔ)，要實(shí)現(xiàn)鏈表就不難了。
    所謂鏈表，就是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表元素的一種數(shù)據(jù)結(jié)構(gòu)。鏈表又分為單鏈表、雙向鏈表和循環(huán)鏈表等。我們先講講單鏈表。所謂單鏈表，是指數(shù)據(jù)接點(diǎn)是單向排列的。一個(gè)單鏈表結(jié)點(diǎn)，其結(jié)構(gòu)類型分為兩部分：
    1、數(shù)據(jù)域：用來(lái)存儲(chǔ)本身數(shù)據(jù)
    2、鏈域或稱為指針域：用來(lái)存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址或者說(shuō)指向其直接后繼的指針。
    例：
    typedef struct node
    {
    char name[20];
    struct node *link;
    }stud;
    這樣就定義了一個(gè)單鏈表的結(jié)構(gòu)，其中char name[20]是一個(gè)用來(lái)存儲(chǔ)姓名的字符型數(shù)組，指針*link是一個(gè)用來(lái)存儲(chǔ)其直接后繼的指針。
    定義好了鏈表的結(jié)構(gòu)之后，只要在程序運(yùn)行的時(shí)候愛數(shù)據(jù)域中存儲(chǔ)適當(dāng)?shù)臄?shù)據(jù)，如有后繼結(jié)點(diǎn)，則把鏈域指向其直接后繼，若沒(méi)有，則置為NULL。
    下面就來(lái)看一個(gè)建立帶表頭（若未說(shuō)明，以下所指鏈表均帶表頭）的單鏈表的完整程序。
    #include ＜stdio.h＞
    #include ＜malloc.h＞ /*包含動(dòng)態(tài)內(nèi)存分配函數(shù)的頭文件*/
    #define N 10 /*N為人數(shù)*/
    typedef struct node
    {
    char name[20];
    struct node *link;
    }stud;
    stud * creat(int n) /*建立單鏈表的函數(shù)，形參n為人數(shù)*/
    {
    stud *p,*h,*s; /* *h保存表頭結(jié)點(diǎn)的指針，*p指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，*s指向當(dāng)前結(jié)點(diǎn)*/
    int i; /*計(jì)數(shù)器*/
    if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空間并檢測(cè)*/
    {
    printf("不能分配內(nèi)存空間!");
    exit(0);
    }
    h-＞name[0]='\0'; /*把表頭結(jié)點(diǎn)的數(shù)據(jù)域置空*/
    h-＞link=NULL; /*把表頭結(jié)點(diǎn)的鏈域置空*/
    p=h; /*p指向表頭結(jié)點(diǎn)*/
    for(i=0;i＜n;i++)
    {
    if((s= (stud *) malloc(sizeof(stud)))==NULL) /*分配新存儲(chǔ)空間并檢測(cè)*/
    {
    printf("不能分配內(nèi)存空間!");
    exit(0);
    }
    p-＞link=s; /*把s的地址賦給p所指向的結(jié)點(diǎn)的鏈域，這樣就把p和s所指向的結(jié)點(diǎn)連接起來(lái)了*/
    printf("請(qǐng)輸入第%d個(gè)人的姓名",i+1);
    scanf("%s",s-＞name); /*在當(dāng)前結(jié)點(diǎn)s的數(shù)據(jù)域中存儲(chǔ)姓名*/
    s-＞link=NULL;
    p=s;
    }
    return(h);
    }
    main()
    {
    int number; /*保存人數(shù)的變量*/
    stud *head; /*head是保存單鏈表的表頭結(jié)點(diǎn)地址的指針*/
    number=N;
    head=creat(number); /*把所新建的單鏈表表頭地址賦給head*/
    }
    這樣就寫好了一個(gè)可以建立包含N個(gè)人姓名的單鏈表了。寫動(dòng)態(tài)內(nèi)存分配的程序應(yīng)注意，請(qǐng)盡量對(duì)分配是否成功進(jìn)行檢測(cè)。