【文章內(nèi)容簡(jiǎn)介】 鏈表 是一種最常見的數(shù)據(jù)結(jié)構(gòu) ， 分為 動(dòng)態(tài)鏈表 和 靜態(tài)鏈表 。 程序員經(jīng)常使用的是動(dòng)態(tài)鏈表 ，它能進(jìn)行動(dòng)態(tài)內(nèi)存分配 ， 可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況 ， 并且可以方便地進(jìn)行數(shù)據(jù)元素的插入 、刪除等操作 。 鏈表有 單向鏈表 、 雙向鏈表 、 循環(huán)鏈表 等形式 。 下圖是一個(gè)單向鏈表的結(jié)構(gòu)示意圖 。 用指針處理鏈表 頭指針 :每個(gè)鏈表都有一個(gè) “ 頭指針 ” 變量 ， 圖中以head表示 ， 它存放一個(gè)地址 ， 指向鏈表的 第一個(gè)元素 。 結(jié)點(diǎn) :鏈表中每一個(gè)元素被稱為一個(gè) “ 結(jié)點(diǎn) ” (node)。每個(gè)結(jié)點(diǎn)都應(yīng)包含兩部分 ， 第一部分是鏈表中存放的用戶需要用的 實(shí)際數(shù)據(jù) ， 在圖中以Ａ 、 Ｂ 、 Ｃ 、 Ｄ表示；第二部分是 一個(gè)地址 ， 指向 下一個(gè)結(jié)點(diǎn) 。 表尾 :鏈表中最后一個(gè)結(jié)點(diǎn)稱為 “ 表尾 ” ， 表尾結(jié)點(diǎn)存放一個(gè) NULL(表示空地址 )， 因此該結(jié)點(diǎn)不再指向其它結(jié)點(diǎn) 。 0050 A 1010 B 1300 C 1456 D NULL 0050 1010 1300 1456 head 鏈表 是一種最常見的數(shù)據(jù)結(jié)構(gòu) ， 分為 動(dòng)態(tài)鏈表 和 靜態(tài)鏈表 。 程序員經(jīng)常使用的是動(dòng)態(tài)鏈表 ，它能進(jìn)行動(dòng)態(tài)內(nèi)存分配 ， 可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況 ， 并且可以方便地進(jìn)行數(shù)據(jù)元素的插入 、刪除等操作 。 鏈表有 單向鏈表 、 雙向鏈表 、 循環(huán)鏈表 等形式 。 下圖是一個(gè)單向鏈表的結(jié)構(gòu)示意圖 。 鏈表中各結(jié)點(diǎn)在內(nèi)存中可以不是連續(xù)存放的 ， 要找到某一結(jié)點(diǎn) ,必須先找到上一個(gè)結(jié)點(diǎn) ,根據(jù)它提供的下一個(gè)結(jié)點(diǎn)的地址才能找到下一個(gè)結(jié)點(diǎn) 。 結(jié)點(diǎn)中的地址用 指針變量 來實(shí)現(xiàn) 。 即一個(gè)結(jié)點(diǎn)中應(yīng)包含一個(gè)指針變量 ,用它存放下一個(gè)結(jié)點(diǎn)的地址 。 用 結(jié)構(gòu)變量 作鏈表中的結(jié)點(diǎn)是最合適的 ， 一個(gè)結(jié)構(gòu)體變量包含若干成員 ， 它們可以是數(shù)值類型 、 字符類型 、 數(shù)組類型 ， 也可以是指針類型 。 我們用這個(gè) 指針類型成員來存放下一個(gè)結(jié)點(diǎn)的地址 。 0050 A 1010 B 1300 C 1456 D NULL 0050 1010 1300 1456 head 鏈表 是一種最常見的數(shù)據(jù)結(jié)構(gòu) ， 分為 動(dòng)態(tài)鏈表 和 靜態(tài)鏈表 。 程序員經(jīng)常使用的是動(dòng)態(tài)鏈表 ，它能進(jìn)行動(dòng)態(tài)內(nèi)存分配 ， 可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況 ， 并且可以方便地進(jìn)行數(shù)據(jù)元素的插入 、刪除等操作 。 鏈表有 單向鏈表 、 雙向鏈表 、 循環(huán)鏈表 等形式 。 下圖是一個(gè)單向鏈表的結(jié)構(gòu)示意圖 。 struct student { int num。 float score。 student *next。 } ； 每個(gè) 結(jié)點(diǎn)數(shù)據(jù) 都屬于student結(jié)構(gòu)類型，因而 next也應(yīng)為一個(gè) student類型的結(jié)構(gòu)指針，它指向 下一結(jié)點(diǎn)的地址 。用這種方法可以建立鏈表。 0001 0002 0003 76 90 NULL num score next 0050 A 1010 B 1300 C 1456 D NULL 0050 1010 1300 1456 head 鏈表 是一種最常見的數(shù)據(jù)結(jié)構(gòu) ， 分為 動(dòng)態(tài)鏈表 和 靜態(tài)鏈表 。 程序員經(jīng)常使用的是動(dòng)態(tài)鏈表 ，它能進(jìn)行動(dòng)態(tài)內(nèi)存分配 ， 可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況 ， 并且可以方便地進(jìn)行數(shù)據(jù)元素的插入 、刪除等操作 。 鏈表有 單向鏈表 、 雙向鏈表 、 循環(huán)鏈表 等形式 。 下圖是一個(gè)單向鏈表的結(jié)構(gòu)示意圖 。 struct student { int num。 float score。 student *next。 } ； 每個(gè) 結(jié)點(diǎn)數(shù)據(jù) 都屬于student結(jié)構(gòu)類型，因而 next也應(yīng)為一個(gè) student類型的結(jié)構(gòu)指針，它指向 下一結(jié)點(diǎn)的地址 。用這種方法可以建立鏈表。 0001 0002 0003 76 90 NULL num score next 鏈表的 特點(diǎn) 在于 動(dòng)態(tài) 地進(jìn)行內(nèi)存分配，即在需要時(shí)才會(huì)開辟一個(gè)結(jié)點(diǎn)的存儲(chǔ)空間，當(dāng)某個(gè)存儲(chǔ)空間不再需要時(shí)可以釋放。在Ｃ ++語言中，可使用 new和 delete兩個(gè)運(yùn)算符進(jìn)行動(dòng)態(tài)內(nèi)存的分配和釋放。 算法分析 : 假設(shè)輸入的 學(xué)號(hào)為 0時(shí) ， 表示建立鏈表的過程結(jié)束 ，該結(jié)點(diǎn)不應(yīng)鏈接到鏈表中 。 根據(jù)題目要求 ， 鏈表中結(jié)點(diǎn)數(shù)據(jù)應(yīng)采用 結(jié)構(gòu)體類型 來描述 。 同時(shí)定義三個(gè)指針變量 head， p1， p2， 它們都是結(jié)構(gòu)類型的指針變量 。 結(jié)構(gòu)指針變量 head的初值為 NULL(即等于 0),此時(shí)是空鏈表 (head不指向任何結(jié)點(diǎn) ,鏈表中無結(jié)點(diǎn) )， 當(dāng)鏈表建成后 ， 應(yīng)使 head指向 第一個(gè)結(jié)點(diǎn) 。 ? 例 寫一個(gè)函數(shù)，建立一個(gè)有 5名學(xué)生數(shù)據(jù) (包含學(xué)號(hào)和成績(jī) )的單向動(dòng)態(tài)鏈表。 struct student { long num。 float score。 student *next。 }。 student *head, *p1, *p2。 int n=0。 //n為結(jié)點(diǎn)個(gè)數(shù)，初值為 0 p1 數(shù)據(jù)域 p1 num p1 score p1 next 指針域 建立鏈表的過程 : ① 首先利用 new運(yùn)算符 ， 在內(nèi)存中開辟一個(gè)存儲(chǔ)空間 ,用來存放新結(jié)點(diǎn) 。 使 p1,p2都指向該存儲(chǔ)空間 ,然后從鍵盤上輸入一個(gè)學(xué)生的數(shù)據(jù)進(jìn)行判斷 ,如果輸入的 p1num不等于 0， 而且是第一個(gè)結(jié)點(diǎn)數(shù)據(jù) （ n＝ 1） ,則把 p1的值賦給 head(head=p1),這樣 ， 結(jié)構(gòu)指針 head就指向了鏈表中的 第一個(gè)結(jié)點(diǎn) 。 p2 p1 head (n=1) 建立表頭結(jié)點(diǎn) 0001 p2 p1 head 0001 ② 然后利用 new再開辟一個(gè)新的存儲(chǔ)空間 ， 用來存放另一個(gè)結(jié)點(diǎn) ， 并使 p1指向 新開辟的存儲(chǔ)空間 ， 然后輸入該結(jié)點(diǎn)的數(shù)據(jù) 。 如果輸入的 p1num不等于 0， 而且不是第一個(gè)結(jié)點(diǎn) （ n≠1） 時(shí) ， 則應(yīng)將新建結(jié)點(diǎn)與前一個(gè)結(jié)點(diǎn)連接在一起 ,即 :執(zhí)行 p2 next=p1， 使第一個(gè)結(jié)點(diǎn)的 next 成員指向第二個(gè)結(jié)點(diǎn) 。 接著使 p2＝ p1， 即 :使 p2指向 剛剛建立的結(jié)點(diǎn) (即建立鏈表進(jìn)程中的 最后一個(gè)結(jié)點(diǎn) ) 。 建立中間結(jié)點(diǎn) (n=2) p2 p1 head 0001 ② 然后利用 new再開辟一個(gè)新的存儲(chǔ)空間 ， 用來存放另一個(gè)結(jié)點(diǎn) ， 并使 p1指向 新開辟的存儲(chǔ)空間 ， 然后輸入該結(jié)點(diǎn)的數(shù)據(jù) 。 如果輸入的 p1num不等于 0， 而且不是第一個(gè)結(jié)點(diǎn) （ n≠1） 時(shí) ， 則應(yīng)將新建結(jié)點(diǎn)與前一個(gè)結(jié)點(diǎn)連接在一起 ,即 :執(zhí)行 p2 next=p1， 使第一個(gè)結(jié)點(diǎn)的 next 成員指向第二個(gè)結(jié)點(diǎn) 。 接著使 p2＝ p1， 即 :使 p2指向 剛剛建立的結(jié)點(diǎn) (即建立鏈表進(jìn)程中的 最后一個(gè)結(jié)點(diǎn) ) 。 建立中間結(jié)點(diǎn) (n=2) 0002 76 p2 p1 head 0001 ② 然后利用 new再開辟一個(gè)新的存儲(chǔ)空間 ， 用來存放另一個(gè)結(jié)點(diǎn) ， 并使 p1指向 新開辟的存儲(chǔ)空間 ， 然后輸入該結(jié)點(diǎn)的數(shù)據(jù) 。 如果輸入的 p1num不等于 0， 而且不是第一個(gè)結(jié)點(diǎn) （ n≠1） 時(shí) ， 則應(yīng)將新建結(jié)點(diǎn)與前一個(gè)結(jié)點(diǎn)連接在一起 ,即 :執(zhí)行 p2 next=p1， 使第一個(gè)結(jié)點(diǎn)的 next 成員指向第二個(gè)結(jié)點(diǎn) 。 接著使 p2＝ p1， 即 :使 p2指向 剛剛建立的結(jié)點(diǎn) (即建立鏈表進(jìn)程中的 最后一個(gè)結(jié)點(diǎn) ) 。 建立中間結(jié)點(diǎn) (n=2) 0002 76 p2 p1 head 0001 ② 然后利用 new再開辟一個(gè)新的存儲(chǔ)空間 ， 用來存放另一個(gè)結(jié)點(diǎn) ， 并使 p1指向 新開辟的存儲(chǔ)空間 ， 然后輸入該結(jié)點(diǎn)的數(shù)據(jù) 。 如果輸入的 p1num不等于 0， 而且不是第一個(gè)結(jié)點(diǎn) （ n≠1） 時(shí) ， 則應(yīng)將新建結(jié)點(diǎn)與前一個(gè)結(jié)點(diǎn)連接在一起 ,即 :執(zhí)行 p2 next=p1， 使第一個(gè)結(jié)點(diǎn)的 next 成員指向第二個(gè)結(jié)點(diǎn) 。 接著使 p2＝ p1， 即 :使 p2指向 剛剛建立的結(jié)點(diǎn) (即建立鏈表進(jìn)