C語言 建立鏈表

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

typedef struct list

{

    int data;

    struct list *next;

} SLIST ;

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

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

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

    此步驟所使用的語句為：

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

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

    此步驟所使用的語句為：

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

    q->data=a[i];

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

此步驟所使用的語句為：

    p->next=*q;

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

此步驟所使用的語句為：

    p=q;

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

⑤重復(fù)2~4步的操作，直到產(chǎn)生鏈表中所有的結(jié)點，為最后一個結(jié)點的地址域賦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é)點，head為指向頭結(jié)點的指針*/

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

    {

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

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

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

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

    }

    p->next=0;

}

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

    SLIST *creatlist(int *a)

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

    {

        …

        return head; /*將產(chǎn)生的鏈表的頭指針返回*/

    }