結(jié)構(gòu)體

利用結(jié)構(gòu)體構(gòu)成鏈表

結(jié)構(gòu)體中含有可以指向本結(jié)構(gòu)體的指針成員

當(dāng)一個(gè)結(jié)構(gòu)體中含有一個(gè)或多個(gè)成員的基本類型就是本結(jié)構(gòu)體類型時(shí)，稱這種結(jié)構(gòu)體為可以“引用自身的結(jié)構(gòu)體”

struct node 
{
    int data;
    struct node * next;
}a;

next是一個(gè)可以指向struct node 類型變量的指針成員。因此，a.next=&a是合法的表達(dá)式，由此構(gòu)成的存儲(chǔ)結(jié)構(gòu) 引用自身的結(jié)構(gòu)體

鏈表的概念

數(shù)組屬于靜態(tài)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)組織形式），在編譯時(shí)，一次性地分配所申請(qǐng)的存儲(chǔ)空間。而實(shí)際使用的存儲(chǔ)空間經(jīng)常小于所申請(qǐng)的空間，因此靜態(tài)數(shù)據(jù)結(jié)構(gòu)存在空間浪費(fèi)現(xiàn)象；而且數(shù)組元素在內(nèi)存中是連續(xù)存放，當(dāng)插入或刪除一個(gè)數(shù)據(jù)時(shí)，需要移動(dòng)大量元素。
C語言可利用指針來建立動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，稱之為鏈表。

動(dòng)態(tài)鏈表的概念

每次為一個(gè)結(jié)構(gòu)動(dòng)態(tài)分配的內(nèi)存空間稱之為一個(gè)結(jié)點(diǎn)。鏈表的結(jié)點(diǎn)包含數(shù)據(jù)域和指針域兩個(gè)部分。數(shù)據(jù)域可以存放任何類型的數(shù)據(jù)，指針域用于指向下一個(gè)結(jié)點(diǎn)的地址，以便通過這些指針把各個(gè)結(jié)點(diǎn)連接起來，形成鏈表。由于鏈表中的每個(gè)存儲(chǔ)單元都動(dòng)態(tài)分配獲得，故這樣的鏈表為“動(dòng)態(tài)鏈表”
在單鏈表中，一般設(shè)置頭指針（head），用于指向鏈表中第一個(gè)結(jié)點(diǎn)。有時(shí)為了簡(jiǎn)化操作，在第一個(gè)結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。

struct student
{
    int data;
    struct student* next;
}a;

指針域中存放下一個(gè)結(jié)點(diǎn)的首地址，其中第0個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)，他存放有第一個(gè)結(jié)點(diǎn)的首地址，他沒有數(shù)據(jù)，只是一個(gè)指針變量。最后一個(gè)結(jié)點(diǎn)因沒有后續(xù)結(jié)點(diǎn)，它的數(shù)據(jù)域存放最后一個(gè)學(xué)生的實(shí)際數(shù)據(jù)，而指針域置成‘\0’（NULL）值，一般在圖中用“^”表示。

創(chuàng)建動(dòng)態(tài)鏈表所需的函數(shù)

使用時(shí)需要在程序開頭包含文件stdlib.h

• malloc函數(shù)

void* malloc(unsigned int size);

功能：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)分配大小為size字節(jié)的連續(xù)空間，并將該區(qū)域的起始地址作為函數(shù)值返回。malloc（）函數(shù)的返回值為指向void類型的指針。

p=(long*)malloc(8);

用malloc（8）申請(qǐng)一個(gè)長度為8字節(jié)的內(nèi)存空間，一個(gè)指向long型的指針變量p，指向這段空間的首地址。
在內(nèi)存沒有足夠大的空間進(jìn)行分配時(shí)，malloc函數(shù)值為NULL（空指針），即地址為0。

• calloc 函數(shù)

void* calloc(unsigned int num,unsigned int size);

功能：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)分配num個(gè)大小字節(jié)的連續(xù)空間，函數(shù)的返回值為該空間的首地址。如果分配不成功返回NULL。

• free 函數(shù)

void free (void*p);

功能：把以前分配的由p指向的存儲(chǔ)空間釋放，歸還給系統(tǒng)。該函數(shù)的返回值為空。p是最近一次由malloc函數(shù)和calloc函數(shù)返回的地址。

• realloc函數(shù)

void *realloc(void *p unsigned int size)

功能：將p所指存儲(chǔ)空間的大小改為size個(gè)字節(jié)，即擴(kuò)大或縮小原來的存儲(chǔ)空間。如果分配不成功，則返回NULL。