【正文】 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 教學(xué)目標(biāo) 鏈表的概念 建立鏈表中指針的運(yùn)用 插入刪除結(jié)點(diǎn)的思路與雙指針作用 建立循環(huán)鏈表的思路 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 鏈表屬于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以類比成一“環(huán)”接一“環(huán)”的鏈條，這里每一“環(huán)”視作一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)串在起形成鏈表。 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 舉例說明鏈表的概念 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 【 任務(wù) 】 某電視臺(tái)希望王小二同學(xué)為他們編一個(gè)程序。該程序可以將節(jié)目串在一起，形成一份有序的節(jié)目預(yù)告。節(jié)目列表有如下三項(xiàng) 節(jié)目名稱 包括 新聞聯(lián)播（ CCTV News） 祖國(guó)各地（ Motherland） 體育之窗（ Sports） 學(xué)校見聞（ College） 電影展播（ Movie） 節(jié)目主持人（ Director） 播放時(shí)間長(zhǎng)度（ Time） 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 我們可以將每一個(gè)節(jié)目單獨(dú)放在一個(gè)結(jié)構(gòu)里，用一個(gè)指針把兩個(gè)結(jié)構(gòu)連在一起，一天的節(jié)目形成一條鏈表。用一個(gè)所謂的頭指針 head 指向鏈表的第一個(gè)結(jié)點(diǎn)。如下圖所示 節(jié)目 2 節(jié)目 n NULL head 頭指針 節(jié)目 1 下面的程序是建立鏈表的過程。 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 建立鏈表的過程 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 //************************************ //* 程 序 名： * //* 作 者： wuwh * //* 編制時(shí)間： 2021年 11月 26日 * //* 主要功能：鏈表 * //************************************ include iostream using namespace std。 struct ActList // 定義一個(gè)名為 ActList 結(jié)構(gòu) { char ActName[20]。 // 節(jié)目名為字符數(shù)組 char director[20]。 // 主持人為字符數(shù)組 int Mtime。 // 節(jié)目長(zhǎng)度為分鐘 ActList *next。 // 指向 ActList 結(jié)構(gòu)的指針 }。 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 ActList *head。 // 鏈頭指針 ActList *Create() // 定義一個(gè)指向 AcitList 結(jié)構(gòu) { //的指針函數(shù)，名為 Create ActList *p=NULL。 // 指針，指向個(gè)待插入的結(jié)點(diǎn) ActList *q=NULL。 // 指針，用于在其后插入結(jié)點(diǎn) head = NULL。 // 一開始鏈表為空 int Time。 // 節(jié)目時(shí)長(zhǎng)，如為 0則退出 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 // 以下是給新結(jié)點(diǎn)輸入節(jié)目信息 cout 輸入節(jié)目時(shí)長(zhǎng)： 。 cin Time。 while(Time != 0) // 當(dāng)該節(jié)目的時(shí)長(zhǎng)不為 0時(shí)，將其 { // 納入鏈表中 p = new ActList。 // 分配內(nèi)存空間給 p結(jié)點(diǎn) pMtime = Time。 // 讓 Time賦給 p結(jié)點(diǎn)的結(jié) 構(gòu)成員 Mtime cout 輸入節(jié)目名稱： 。 // 提示信息 cin pActName。 // 輸入節(jié)目名稱 cout 輸入主持人： 。 // 提示信息 cin pdirector。 // 輸入主持人 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 if (head == NULL) // head為空，要插入第一個(gè) head = p。 // 結(jié)點(diǎn)，讓頭指針指向結(jié)點(diǎn) p else // 否則不是頭結(jié)點(diǎn)，應(yīng)將 p結(jié)點(diǎn) qnext = p。 // 插入到 q結(jié)點(diǎn)的后面 q = p。 // q指向當(dāng)前最后一個(gè)結(jié)點(diǎn) cout \n輸入節(jié)目時(shí)長(zhǎng)： 。 cin Time。 // 輸入下一個(gè)節(jié)目時(shí)長(zhǎng) } // 一旦跳出 while循環(huán)，說明有一個(gè)節(jié)目時(shí)長(zhǎng)為 0 if (head != NULL) qnext = NULL。 // 讓 q所指的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭照f明這已是鏈尾了 return(head)。 // 返回頭指針 } 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 void displayList(ActList *head) { cout 顯示節(jié)目列表 \n。 while(head != NULL) // 當(dāng)指針 head不空，則輸出 { cout headMtime endl headActName endl headdirector endl endl。 head=headnext。 } } 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 int main( ) // 主函數(shù)開始 { // 調(diào)用子函數(shù) displaList() // 調(diào)用時(shí)的實(shí)參為 Create()函數(shù)的返回值 displayList( Create() )。 return 0。 } // 主函數(shù)結(jié)束 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 說明 先從主函數(shù)說起 主函數(shù)只有一條語(yǔ)句 displayList(Create( ))。 這是調(diào)用子函數(shù) displayList，該子函數(shù)的形參為 ActList *head 是一個(gè)指向 ActList 結(jié)構(gòu)的名為 head 的指針變量。在主函數(shù)調(diào)用 displayList 時(shí)所用的實(shí)際參數(shù)來(lái)自運(yùn)行 Create( ) 函數(shù)的返回值。從 Create( ) 的定義 ActList *Create( ) 看出 Create( ) 函數(shù)的返回值應(yīng)該是一個(gè)指向 ActList 的指針。 主函數(shù)在調(diào)用子函數(shù)時(shí)，又遇到該函數(shù)的實(shí)參又是調(diào)用另一個(gè)函數(shù)之后的返回值?？雌饋?lái)的確顯得復(fù)雜，但是我們耐心分析之后，感到并不難。 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 程序開頭為結(jié)構(gòu)定義。在這里我們稱這樣的一個(gè)結(jié)構(gòu)為一個(gè)結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)包含兩個(gè)域：數(shù)據(jù)域和指針域 int MTime。 char ActName[20]。 數(shù)據(jù)域 char director[20] ActList *next。 指針域 結(jié) 點(diǎn) 數(shù)據(jù)域中裝有節(jié)目的信息，而指針域裝的是指向另一個(gè)結(jié)點(diǎn)的地址。顯然這是為形成鏈表而專門設(shè)置的。 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 在定義 Create 函數(shù)之前，先定義了一個(gè)指向結(jié)構(gòu)的頭指針 head，即 ActList *head。 定義 Create函數(shù)，該函數(shù)可返回指向 ActList 結(jié)構(gòu)的指針，即 ActList *Create( ) 分析這個(gè)函數(shù)的功能可分如下 4塊 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 ① 定義 ActList *p = NULL。 ActList *q = NULL。 head = NULL。 int Time。 定義了兩個(gè)指向結(jié)構(gòu) ActList 的指針 p 和 q，并初始化為空，即未指向任何地址。同時(shí)讓頭指針 head 也為空。再定義一個(gè)臨時(shí)變量 Time，是一個(gè)整型數(shù)。 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 ② 提示 “ 輸入節(jié)目時(shí)長(zhǎng) ” ，之后用鍵盤輸入，用了下面兩句： cout “輸入節(jié)目時(shí)長(zhǎng)” 。 cin Time。 這部分程序語(yǔ)句是為下面的 while 循環(huán)做準(zhǔn)備的。如果 Time 不為 0，才做下面的內(nèi)容。 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 ③ while( Time != 0 ) 循環(huán) 在當(dāng)循環(huán)的循環(huán)體內(nèi)完成建立鏈表的過程。首先給 p 結(jié)點(diǎn)分配內(nèi)存空間。這個(gè)內(nèi)存空間的大小要根據(jù) p 結(jié)點(diǎn)的定義（ p 結(jié)點(diǎn)是 ActList 結(jié)構(gòu)）來(lái)確定。接著下面就是幾個(gè)賦值語(yǔ)句 pMTime = Time。 cout “輸入節(jié)目名稱：” 。// 提示 cin pActName。 // 用鍵盤輸入節(jié)目名稱 cout “輸入主持人：” 。 // 提示 cin pdirector。 // 用鍵盤輸入主持人 程序設(shè)計(jì)基礎(chǔ) 第 11章 鏈表 接著是一個(gè)分支語(yǔ)句 if (head==NULL) head=p。 這是說如果頭指針為空，表示鏈表還是空的，這時(shí) p 結(jié)點(diǎn)就是第一個(gè)結(jié)點(diǎn)。讓 head 指向 p 結(jié)點(diǎn)。之后讓 q=p。 這是讓 q 指向剛進(jìn)入鏈表的結(jié)點(diǎn)，讓 p 再去指向待加入的結(jié)點(diǎn)。如果 p 結(jié)點(diǎn)已不是第一個(gè)結(jié)點(diǎn)了， head 必不為 NULL，因此要走 else 分支，即 else