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