【文章內(nèi)容簡(jiǎn)介】 例 86 結(jié)構(gòu)體指針作函數(shù)參數(shù)示例。 結(jié)構(gòu)體數(shù)組名 鏈表概述 ? 使用鏈表存儲(chǔ)學(xué)生信息 ? 鏈表的特點(diǎn) ? 動(dòng)態(tài)內(nèi)存管理函數(shù) ? 定義鏈表結(jié)構(gòu) 鏈表的概念 ? 鏈表 是結(jié)構(gòu)體最重要的應(yīng)用，它 是一種非固定長(zhǎng)度的數(shù)據(jù)結(jié)構(gòu) ， 是一種動(dòng)態(tài)存儲(chǔ)技術(shù) ，它能夠根據(jù)數(shù)據(jù)的結(jié)構(gòu)特點(diǎn)和數(shù)量使用內(nèi)存，尤其適用于數(shù)據(jù)個(gè)數(shù)可變的數(shù)據(jù)存儲(chǔ)。 ? 使用鏈表存儲(chǔ)表中前 3個(gè)學(xué)生數(shù)據(jù)。 9 9 0 1l i u j i aM8 79 9 0 2w a n g k a iM8 99 9 0 3x i a o h u aF8 1N U L Lh e a d學(xué)號(hào) 姓名 性別 成績(jī) 9901 liujia M 87 9902 wangkai M 89 9903 xiaohua F 81 9904 zhangli F 82 9905 wangfeng M 88 ⑴ 用 calloc()申請(qǐng)一段內(nèi)存 M，并把它分成兩部分：一部分存儲(chǔ)數(shù)據(jù)；另一部分存儲(chǔ)下一個(gè)內(nèi)存段的地址。 ⑵ 將一個(gè)學(xué)生數(shù)據(jù)存儲(chǔ)在 M的數(shù)據(jù)區(qū)中。 ⑶ 若當(dāng)前是第一個(gè)數(shù)據(jù)，則將 M的首地址保存在指針變量 head中；否則將 M的首地 保存在上一個(gè)內(nèi)存段中。 ⑷ 重復(fù)⑴、⑵、⑶的過程，直到所有數(shù)據(jù)存儲(chǔ)完畢，在最后一段內(nèi)存的地址區(qū)存儲(chǔ)結(jié)束標(biāo)志。 鏈表的特點(diǎn) ⑴ 鏈表中的結(jié)點(diǎn)具有完全相同的結(jié)構(gòu)，每一個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)獨(dú)立的結(jié)構(gòu)體數(shù)據(jù)； ⑵ 鏈表的結(jié)點(diǎn)由系統(tǒng)隨機(jī)分配，它們?cè)趦?nèi)存中的位置可能是相鄰的，也可能是不相鄰的，結(jié)點(diǎn)之間的聯(lián)系是通過指針域?qū)崿F(xiàn)的； ⑶ 為了能準(zhǔn)確的定位第一個(gè)結(jié)點(diǎn)，每個(gè)鏈表要有一個(gè)表頭指針，從第一個(gè)結(jié)點(diǎn)開始，沿指針鏈能遍歷鏈表中的所有結(jié)點(diǎn)； ⑷ 鏈表中的結(jié)點(diǎn)是在需要時(shí)用 calloc()申請(qǐng)的，當(dāng)不再需要時(shí)，應(yīng)有 free()函數(shù)釋放所占用的內(nèi)存段。 ⑸ 一個(gè)鏈表不需要事先說明它要包括的結(jié)點(diǎn)數(shù)目，在需要存儲(chǔ)新的數(shù)據(jù)時(shí)，就可增加結(jié)點(diǎn)，需要?jiǎng)h除數(shù)據(jù)時(shí)，就減少結(jié)點(diǎn)，鏈表結(jié)點(diǎn)是動(dòng)態(tài)變化的。 動(dòng)態(tài)內(nèi)存管理函數(shù) ?動(dòng)態(tài)分配內(nèi)存 按需分配內(nèi)存，申請(qǐng)獲得制。 ?C語言通過動(dòng)態(tài)內(nèi)存管理函數(shù)，實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存管理。鏈表每一個(gè)結(jié)點(diǎn)的建立和刪除過程，都需要使用動(dòng)態(tài)內(nèi)存管理函數(shù)。 動(dòng)態(tài)內(nèi)存管理函數(shù) 1． malloc()函數(shù) ?函數(shù)原型 void *malloc(unsigned int size)。 ?功能 分配一塊長(zhǎng)度為 size字節(jié)的連續(xù)空間，并將該空間的首地址作為函數(shù)的返回值。如果函數(shù)沒有成功執(zhí)行，返回值為空指針（ NULL或 0）。由于返回的指針的基類型為 void，應(yīng)該通過顯式類型轉(zhuǎn)換后才能存入其他基類型的指針變量中，否則會(huì)有警告提示。 例如： int *p。 p=(int *)malloc(sizeof(int))。 動(dòng)態(tài)內(nèi)存管理函數(shù) 2． free()函數(shù) ?函數(shù)原型 void free(void *block)。 ?功能 釋放以前分配給指針變量 block的動(dòng)態(tài)空間，但指針變量 block不會(huì)自動(dòng)變成空指針。 3. calloc()函數(shù) ?函數(shù)原型 void *calloc(unsigned n,unsigned size)。 ?功能 以 size為單位大小共分配 n*size個(gè)字節(jié)的連續(xù)空間，并將該空間的首地址作為函數(shù)的返回值。如果函數(shù)沒有成功執(zhí)行，返回值為空指針(NULL或 0)。 例如： int *p。 p=(int *)calloc(10,sizeof(int))。 定義鏈表結(jié)構(gòu) ? 要定義一個(gè)鏈表結(jié)點(diǎn)的結(jié)構(gòu)，須有兩項(xiàng)內(nèi)容： ? 定義數(shù)據(jù)存儲(chǔ)所對(duì)應(yīng)的各個(gè)成員； ? 定義指向其他結(jié)點(diǎn)的指針成員。 例如： 假若要用鏈表逐個(gè)存儲(chǔ)一批整數(shù)，其結(jié)點(diǎn)結(jié)構(gòu)可定義如下： struct node { int data。 struct node *next。 }。 n e w d a ta n e x t存儲(chǔ)具體數(shù)據(jù) 存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址 d a t a 1 d a t a 2 d a t a 3 d a t a n ∧. . .h e a d?struct node類型的結(jié)點(diǎn)形成的鏈表 頭指針 空指針 定義鏈表結(jié)構(gòu) 9 9 0 1l i u j i aM8 79 9 0 2w a n g k a iM8 99 9 0 3x i a o h u aF8 1N U L Lh e a d學(xué)號(hào) 姓名 性別 成績(jī) 9901 liujia M 87 9902 wangkai M 89 9903 xiaohua F 81 9904 zhangli F 82 9905 wangfeng M 88 struct student { int num。 char name[20]。 char sex。 int score。 struct student *next。 }。 必須的成員，否則構(gòu)不成鏈表 ?學(xué)生鏈表的結(jié)點(diǎn)定義 ?結(jié)點(diǎn) 鏈表的基本操作 ? 鏈表結(jié)點(diǎn)的插入 ? 鏈表結(jié)點(diǎn)的刪除 ? 鏈表結(jié)點(diǎn)的查找 鏈表結(jié)點(diǎn)的插入 ? 在鏈表中插入結(jié)點(diǎn)，就是把一個(gè)新結(jié)點(diǎn)連接到鏈表中。 ? 兩種情況： ?在空鏈表中插入一個(gè)結(jié)點(diǎn)； ?在鏈表的 p結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)。 鏈表結(jié)點(diǎn)的插入 1．在空鏈表中插入一個(gè)結(jié)點(diǎn) 空鏈表就是頭指針 head為空的鏈表。 ⑴ 申請(qǐng)一個(gè) new結(jié)點(diǎn)。 new=(struct node *)calloc(1,sizeof(struct node))。 ⑵ 為 p結(jié)點(diǎn)填充數(shù)據(jù)。 將要存儲(chǔ)的數(shù)據(jù)對(duì)應(yīng)賦值給 p結(jié)點(diǎn)數(shù)據(jù)域的各個(gè)成員。 ⑶ 修改有關(guān)指針的指向。 ① 將 new的 next成員置空，使 new結(jié)點(diǎn)成為鏈表的最后一個(gè)結(jié)點(diǎn)。 ② 將 head指向 new結(jié)點(diǎn)。 n e w d a ta n e x th e a d d a t a∧ 鏈表結(jié)點(diǎn)的插入 2．在 head鏈表的 p結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn) head鏈表和要插入結(jié)點(diǎn) new如圖所示。要將 new結(jié)點(diǎn)插入在 p結(jié)點(diǎn)之后，就是將 new結(jié)點(diǎn)變成結(jié)點(diǎn) C的下一個(gè)結(jié)點(diǎn)，而使 new的下一個(gè)結(jié)點(diǎn)成為結(jié)點(diǎn) D。 ⑴ 使 new的指針域存儲(chǔ)結(jié)點(diǎn) D的首地址。 newnext=pnext。 ⑵ 把 new的首地址存儲(chǔ)到結(jié)點(diǎn) p的指針域中 。 pnext=new。 d a t a 1 d a t a 2 d a t a 3 d a t a 4 ∧h e a dpd a t