[工學(xué)]c第8章復(fù)雜數(shù)據(jù)類(lèi)型(編輯修改稿)
2025-11-12 18:16 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 刪除學(xué)生記錄結(jié)點(diǎn)時(shí)，如刪除學(xué)號(hào)為“ 1002”學(xué)生結(jié)點(diǎn)時(shí)，只要將其前一個(gè)結(jié)點(diǎn) (即學(xué)號(hào)為“ 1001”)的指針改為 1080即可，所有數(shù)據(jù)不要作任何移動(dòng)。而當(dāng)要插入一個(gè)新的學(xué)生成績(jī)時(shí)，只要將新結(jié)點(diǎn)的地址賦給前一個(gè)結(jié)點(diǎn)的指針，將其后一個(gè)結(jié)點(diǎn)的地址賦給新結(jié)點(diǎn)指針即可。所有數(shù)據(jù)不要作任何移動(dòng)。所以用鏈表可解決記錄增刪困難的問(wèn)題。使記錄的增刪變得較為容易。 鏈表圖 ? 由于學(xué)生成績(jī)管理系統(tǒng)的主要操作是數(shù)據(jù)的輸入、輸出、查詢(xún)、插入、刪除等，所以鏈表的主要操作有鏈表的建立、查詢(xún)、輸出、刪除等。為方便后面的討論，將結(jié)點(diǎn)內(nèi)數(shù)據(jù)成員簡(jiǎn)化為學(xué)號(hào)、成績(jī)與指針三項(xiàng)，簡(jiǎn)化后的結(jié)點(diǎn)類(lèi)型 node定義如下： struct node { int no。 //學(xué)生學(xué)號(hào) int score。 //學(xué)生成績(jī) node *next。 //指針變量 }； 為了用鏈表對(duì)學(xué)生成績(jī)進(jìn)行錄入、查詢(xún)、輸出、插入、刪除等操作，應(yīng)學(xué)會(huì)建立鏈表、輸出鏈表、刪除鏈表、查詢(xún)指定結(jié)點(diǎn)、刪除指定結(jié)點(diǎn)、插入結(jié)點(diǎn)、建立有序鏈表等鏈表的基本操作。而這些基本操作可以用以下函數(shù)來(lái)實(shí)現(xiàn)。 ? (1)建立鏈表函數(shù)： node *Create(void) ? (2)輸出鏈表函數(shù)： void Print (node *head) ? (3)刪除鏈表函數(shù)： void Delchain(node *head) ? (4)刪除指定結(jié)點(diǎn)函數(shù)： node *Delete(node *head,int no) ? (5)插入結(jié)點(diǎn)函數(shù)： node *Insert(node *head,node *pn) ? (6)建立有序鏈表函數(shù)： node *create_order()。 Create() ? 建立無(wú)序鏈表應(yīng)用函數(shù) node *Create(void)實(shí)現(xiàn)，建立無(wú)序鏈表的步驟如下。 ? （ 1）定義三個(gè) node類(lèi)型的指針變量： ? node *head,*pn,*pt。 ? head為頭指針變量，用于存放鏈表首結(jié)點(diǎn)的地址，初值為 0，表示鏈表初始時(shí)為空。 ? pn為新結(jié)點(diǎn)指針變量，用于存放用 new運(yùn)算符動(dòng)態(tài)建立的新結(jié)點(diǎn)地址。 ? pt為尾結(jié)點(diǎn)的指針變量，用于存放鏈表尾結(jié)點(diǎn)地址。 ? （ 2）新建結(jié)點(diǎn)、輸入學(xué)號(hào)與學(xué)生成績(jī)。用 new運(yùn)算符動(dòng)態(tài)分配新結(jié)點(diǎn)空間，將 pn指向該新結(jié)點(diǎn)，給新結(jié)點(diǎn)輸入學(xué)號(hào)與成績(jī)。 ? pn=new node。 ? cinpnnopnscore。 Create() ? (3)將新結(jié)點(diǎn)加入到鏈尾。新結(jié)點(diǎn)加入到鏈尾有鏈表為空與非空兩種情況： ? ①鏈表為空（ head為 0）。當(dāng)鏈表第一次加入結(jié)點(diǎn)時(shí)鏈表為空，此時(shí)鏈表頭指針 head為 0，如圖 84（ a）所示。應(yīng)將新結(jié)點(diǎn)的地址 1000由 pn賦給頭指針 head與尾指針 pt。即執(zhí)行： ? head=pn。pt=pn。 ? 兩條語(yǔ)句即可將新結(jié)點(diǎn)加入鏈表第一個(gè)結(jié)點(diǎn)處，如圖所示 Create() ? ② 鏈表非空。當(dāng)鏈表非空時(shí)，應(yīng)將新結(jié)點(diǎn)追加到鏈尾處。只要將新結(jié)點(diǎn)地址 1040由 pn賦給鏈尾結(jié)點(diǎn)的指針變量 ptnext，就可使新結(jié)點(diǎn)連接到鏈尾。再將 pn賦給pt，使 pt指向新的鏈尾結(jié)點(diǎn)。此項(xiàng)操作只需執(zhí)行： ? ptnext=pn； pt=pn； ? 兩條語(yǔ)句即可完成，如圖 Create() ? 鏈表空與非空的兩種情況可用雙選 if語(yǔ)句實(shí)現(xiàn)如下： ? if(head==0)／／若鏈表為空 ? { head=pn； pt=pn； ) ? else／／否則鏈表非空 ? { ptnext=pn； pt=pn； } ? (4)重復(fù) (2)、 (3)兩步，通過(guò)循環(huán)不斷向鏈表添加新結(jié)點(diǎn)直到學(xué)號(hào)為“ 1”為止。 ? (5)將鏈尾結(jié)點(diǎn)指針賦 0。 ? (6)返回鏈表頭指針 head。 先寫(xiě)出上述步驟中的關(guān)鍵語(yǔ)句，然后用循環(huán)結(jié)構(gòu)連接這些關(guān)鍵語(yǔ)句，即可寫(xiě)出建立無(wú)序鏈表函數(shù)如下： node *Create(void) { int no； ／／定義輸入學(xué)生學(xué)號(hào)臨時(shí)變量 no node *head,*pn,*pt； ／／定義鏈表頭指針、新結(jié)點(diǎn)指針、尾指針 head、 pn、 pt head=0； ／／鏈表頭指針賦 0，表示鏈表為空 cout產(chǎn)生無(wú)序鏈表，請(qǐng)輸入學(xué)生學(xué)號(hào)與成績(jī)，以 1為結(jié)束：endl； cinno； ／／輸入學(xué)號(hào) while(no!=1) ／／學(xué)號(hào)為 1時(shí)結(jié)束輸入 { pn=newnode； ／／動(dòng)態(tài)分配新結(jié)點(diǎn)內(nèi)存空間，并將結(jié)點(diǎn)地址賦給 pn pnno=no； ／／輸入學(xué)號(hào) cinpnscore； ／／輸入成績(jī) 程序接上頁(yè) if(head==0) ／／若鏈表為空 { head=pn。 ／／則將新結(jié)點(diǎn)地址由 pn賦給頭指針 head與尾指針 pt pt=pn； ／／使新結(jié)點(diǎn)加入到鏈?zhǔn)? } else ／／否則鏈表非空 { ptnext=pn。 ／／將新結(jié)點(diǎn)地址由 pn賦給鏈尾的 next指針與尾指針 pt pt=pn； ／／使新結(jié)點(diǎn)加入到鏈尾 } cinno； ／／輸入學(xué)號(hào) } ptnext=0； ／／鏈尾指針變量賦 0 return head； ／／返回鏈表的頭指針 } Print () ? 輸出鏈表中各結(jié)點(diǎn)成績(jī)應(yīng)用函數(shù) void Print (void)實(shí)現(xiàn)。保留輸出鏈表函數(shù)的步驟如下： ? (1)函數(shù)必須用形參 node *head接收來(lái)自主函數(shù)的鏈表頭指針 head。 ? (2)定義指針變量 node *p=head。將 p指向鏈表首結(jié)點(diǎn)。 ? (3)用循環(huán)語(yǔ)句依次輸出每個(gè)結(jié)點(diǎn)的學(xué)號(hào)與成績(jī)，直到鏈尾 (p=0)為止。實(shí)現(xiàn)的語(yǔ)句為： while(p!=0) { coutpno39。＼ t39。pscore39。＼ n39。 p=pnext； } 由步驟中的關(guān)鍵語(yǔ)句可編寫(xiě)輸出鏈表函數(shù)如下： voidPrint (node *head) { node *p=head； cout輸出鏈表中各結(jié)點(diǎn)值 :endl； while(p!=0) { coutpno39。＼ t39。pscoreendl； p=pnext； } } 輸出鏈表各結(jié)點(diǎn)數(shù)據(jù)表 3．刪除鏈表函數(shù) Delchain() ? 刪除鏈表是指刪除鏈表全部結(jié)點(diǎn)，并回收結(jié)點(diǎn)所占用的全部?jī)?nèi)存空間。刪除鏈表用函數(shù) Delchain(node *head)實(shí)現(xiàn)，主要操作步驟如下： ? (1)用形參 node *head接受來(lái)自主函數(shù)的鏈表頭指針： ? (2)定義指針變量 node *p=head：并使指針變量 p指向鏈?zhǔn)祝鐖D所示： (3)用循環(huán)語(yǔ)句依次刪除鏈表的各結(jié)點(diǎn) ? 刪除鏈表的函數(shù)如下： void Delchain(n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1