C語(yǔ)言 建立鏈表

假設(shè)有如下結(jié)構(gòu)包含10個(gè)結(jié)點(diǎn)（不包括頭結(jié)點(diǎn)）的鏈表:

typedef struct list

{

    int data;

    struct list *next;

} SLIST ;

為了建立一個(gè)鏈表，需要經(jīng)過(guò)如下步驟：

①先定義三個(gè)指針，head、p、q，這三個(gè)指針類(lèi)型都為SLIST型。這三個(gè)指針的作用為，h指向頭指針，p為當(dāng)前結(jié)點(diǎn)的指針，q為指向新產(chǎn)生結(jié)點(diǎn)的指針。

    利用malloc()函數(shù)產(chǎn)生頭結(jié)點(diǎn)，并將頭結(jié)點(diǎn)的地址賦給head指針和p指針，頭結(jié)點(diǎn)中不存放數(shù)據(jù)，只存放第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的地址，如圖12-10中第1步所示。

    此步驟所使用的語(yǔ)句為：

    head=p=(SLIST *)malloc(sizeof(SLIST));

②利用mallocO函數(shù)產(chǎn)生一個(gè)新的結(jié)點(diǎn)，并將該結(jié)點(diǎn)的地址賦給q，為新結(jié)點(diǎn)的數(shù)值域賦值，如圖中第2步所示。

    此步驟所使用的語(yǔ)句為：

    q=(SLIST *)malloc(sizeof(SLIST)); 

    q->data=a[i];

③將新產(chǎn)生的q結(jié)點(diǎn)連接到上一結(jié)點(diǎn)，如圖中第3步所示。

此步驟所使用的語(yǔ)句為：

    p->next=*q;

④將剛剛產(chǎn)生的結(jié)點(diǎn)q的地址賦給p, q準(zhǔn)備得到下一新的結(jié)點(diǎn)，但注意此時(shí)q并沒(méi)有被釋放，它仍指向當(dāng)前結(jié)點(diǎn)，如圖中第4步所示。

此步驟所使用的語(yǔ)句為：

    p=q;

用第一個(gè)數(shù)據(jù)結(jié)點(diǎn)，并將該結(jié)點(diǎn)的地址賦給head和p指針的地址域。

⑤重復(fù)2~4步的操作，直到產(chǎn)生鏈表中所有的結(jié)點(diǎn)，為最后一個(gè)結(jié)點(diǎn)的地址域賦NULL，如圖第5步所示。

建立鏈表的具體程序代碼如下:

#define N 10

typedef struct list    /*定義鏈表*/

{

    int data;

    struct list *next;

} SLIST; 

main()

{

    SLIST *head,*p,*q;

int i;

    int a[10]={l,3,5,9,10,12.14.17,18,22};

    head=p=(SLIST *)malloc(sizeof(SLIST));    /*產(chǎn)生頭結(jié)點(diǎn)，head為指向頭結(jié)點(diǎn)的指針*/

    for(i-0; i<N; i++)                        /*循環(huán)產(chǎn)生N個(gè)結(jié)點(diǎn)*/

    {

        q=(SLIST *)malloc(sizeof(SLIST));     /*產(chǎn)生一個(gè)結(jié)點(diǎn)*/

        q->dat a=a[i];                        /*為數(shù)據(jù)域復(fù)制*/

        p->next=q;                            /*將剛剛產(chǎn)生的結(jié)點(diǎn)鏈接到上一結(jié)點(diǎn)，*/

        p=q;                              /*剛剛產(chǎn)生的結(jié)點(diǎn)地址賦給p,q準(zhǔn)備產(chǎn)生下一結(jié)點(diǎn)*/

    }

    p->next=0;

}

    本程序是在main()函數(shù)中實(shí)現(xiàn)的，也可以將產(chǎn)生鏈表的過(guò)程定義為一個(gè)函數(shù)creatlist()，該函數(shù)的功能是產(chǎn)生一個(gè)鏈表，并將鏈表的地址返回，所以函數(shù)的類(lèi)型為SLIST*。具體為：

    SLIST *creatlist(int *a)

    /*形參指針變量a,實(shí)參是數(shù)組名，該數(shù)組在mainO函數(shù)中已經(jīng)被賦值*/ 

    {

        …

        return head; /*將產(chǎn)生的鏈表的頭指針?lè)祷?/

    }