數(shù)據(jù)結(jié)構(gòu)教案C語言版

1、課程教案歡迎下載13數(shù)據(jù)結(jié)構(gòu)課程名稱:授課教師:學(xué)習(xí)對象: 任課時間:學(xué)生情況分析C語言程數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的一門核心專業(yè)課程。學(xué)生在前期的學(xué)習(xí)中已經(jīng)學(xué)習(xí)了 序設(shè)計課程。通過本課程學(xué)習(xí)使學(xué)生對提高編寫程序的能力以及解決實際問題的能力。二、課程教學(xué)目標(biāo)數(shù)據(jù)結(jié)構(gòu)是計算機學(xué)科中一門核心專業(yè)基礎(chǔ)課。主要介紹如何合理地組織數(shù)據(jù)、 有效地存儲和處理數(shù)據(jù)，正確地設(shè)計算法以及對算法的分析和評價。通過本課程的學(xué)習(xí)， 使學(xué)生深透地理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)算法，培養(yǎng)基本 的、良好的程序設(shè)計技能，編制高效可靠的程序，為學(xué)習(xí)操作系統(tǒng)、編譯原理和數(shù)據(jù)庫等 課程奠定基礎(chǔ)。三、課程教學(xué)內(nèi)容第一章緒

2、論教學(xué)內(nèi)容:1）什么是數(shù)據(jù)結(jié)構(gòu)2）抽象數(shù)據(jù)類型概念；數(shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；用于描述數(shù)據(jù)結(jié)構(gòu)的 語百3）數(shù)據(jù)結(jié)構(gòu)的抽象層次4）算法定義5）性能分析與度量；算法的性能標(biāo)準(zhǔn)；算法的后期測試；算法的事前估計；空間復(fù) 雜度度量；時間復(fù)雜度度量；時間復(fù)雜度的漸進表示法；教學(xué)要求：了解：數(shù)據(jù)結(jié)構(gòu)基本概念及數(shù)據(jù)結(jié)構(gòu)的抽象層次了解：抽象數(shù)據(jù)類型概念了解：算法的定義及算法特性掌握：算法的性能分析與度量方法第二章線性表教學(xué)內(nèi)容：1）線性表的定義和特點2）線性表的順序存儲及查找、插入和刪除操作3）線性表的鏈?zhǔn)酱鎯安檎摇⒉迦牒蛣h除操作4）使用線性表的實例教學(xué)要求：了解：線性表的定義和特點熟練掌握：線性表的

3、順序存儲結(jié)構(gòu)的查找、插入和刪除等基本操作熟練掌握：單鏈表、循環(huán)鏈表及雙向鏈表的定義及實現(xiàn)掌握：熟練掌握單鏈表的應(yīng)用方法第三章棧和隊列教學(xué)內(nèi)容：1）棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲表示；棧的鏈?zhǔn)酱鎯Ρ硎?）隊列：隊列的抽象數(shù)據(jù)類型；隊列的順序存儲表示；隊列的鏈?zhǔn)酱鎯Ρ硎?）隊列的應(yīng)用舉例教學(xué)要求：熟練掌握：棧的定義及實現(xiàn)熟練掌握：隊列的定義及實現(xiàn)掌握：能運用棧和隊列解決簡單實際問題第四章串教學(xué)：內(nèi)容：1)字符串的抽象數(shù)據(jù)類型2) 字符串操作的實現(xiàn)3) 字符串的模式匹配教學(xué)要求：熟練掌握：字符串的定義方式熟練掌握：字符串的各種操作的實現(xiàn)了解：字符串的模式匹配算法第五章數(shù)組和廣義表教學(xué)：內(nèi)容：1)

4、 數(shù)組的定義和初始化2) 作為抽象數(shù)據(jù)類型的數(shù)組的順序存儲方式教學(xué)要求：了解：作為抽象數(shù)據(jù)類型的數(shù)組的定義熟練掌握：順序表的數(shù)組定義方式及實現(xiàn)第六章樹和二叉樹教學(xué)內(nèi)容：1) 樹和森林的概念：樹的定義；樹的術(shù)語；樹的抽象數(shù)據(jù)類型；森林的概念2) 二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型3) 二叉樹的表示：數(shù)組表示；鏈表存儲表示4) 二叉樹的遍歷：中序遍歷；前序遍歷；后序遍歷；應(yīng)用二叉樹遍歷的實例;叉樹的中序非遞歸算法5) 線索化二叉樹：線索；中序線索化二叉樹；前序與后序的線索化6) 樹與森林：樹的存儲表示；森林與二叉樹的轉(zhuǎn)換；樹的遍歷；森林的遍歷7) 二叉樹的計數(shù)8) 霍夫曼樹：

5、路徑長度；霍夫曼樹；霍夫曼樹編碼教學(xué)要求：了解：樹和森林的概念掌握：二叉樹的概念、性質(zhì)及二叉樹的表示熟練掌握：二叉樹的遍歷方法掌握：線索化二叉樹的特性及尋找某結(jié)點的前驅(qū)和后繼的方法掌握：樹和森林的實現(xiàn)及遍歷方法掌握：二叉樹的計數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法掌握：霍夫曼樹的實現(xiàn)方法及霍夫曼編碼的概念第七章圖教學(xué)內(nèi)容：9) 圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型10) 的存儲表示：鄰接矩陣；鄰接表；鄰接多重表11) 的遍歷與連通性；深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量12) 小生成樹：克魯斯卡爾算法；普里姆算法教學(xué)要求：掌握：圖的基本概念和圖的存儲表示熟練掌握：圖的兩種遍歷方法與求

6、解連通性問題的方法掌握：構(gòu)造最小生成樹的 Prim和Kruskal方法第九章查找教學(xué)內(nèi)容：1） 靜態(tài)查找表：順序表的查找；有序表的查找；索引順序表的查找2）二叉排序樹：二叉排序樹上的搜索、插入和刪除教學(xué)要求：熟練掌握：靜態(tài)搜索表的順序搜索和折半搜索方法熟練掌握：二叉搜索樹的表示、搜索、插入、刪除算法及其性能分析方法 第十章內(nèi)部排序教學(xué)內(nèi)容：1） 概述2）插入排序：直接插入排序；對分插入排序；鏈表插入排序；希爾排序3）選擇排序：直接選擇排序；堆排序教學(xué)要求：掌握：排序的基本概念和性能分析方法一講：緒論掌握：插入排序、選擇排序、等內(nèi)排序的方法及性能分析方法單元名稱：第教學(xué)目標(biāo)1 .了解數(shù)據(jù)結(jié)構(gòu)課程

7、的體系結(jié)構(gòu)2 .掌握本章介紹的各種基本概念和術(shù)語3 .了解數(shù)據(jù)結(jié)構(gòu)的二元組表示4 .掌握邏輯結(jié)構(gòu)與物理結(jié)構(gòu)之間的映像關(guān)系。二、重點與難點重點：數(shù)據(jù)結(jié)構(gòu)的基本概念；邏輯結(jié)構(gòu)與物理結(jié)構(gòu)之間的映像關(guān)系。難點：邏輯結(jié)構(gòu)與物理結(jié)構(gòu)之間的映像關(guān)系。三、教學(xué)內(nèi)容與教學(xué)過程介紹本學(xué)期課程的內(nèi)容及安排本課程是計算機專業(yè)的重要專業(yè)課之一，主要介紹常用的數(shù)據(jù)結(jié)構(gòu)以及相關(guān)算法。本課 程主要講授線性表、棧和隊列、串、數(shù)組、樹和二叉樹、圖、查找、排序等內(nèi)容。成績考核方式為：期末成績 +平時成績，其中期末成績占70%,平時成績占30%,平時成績?yōu)椋鹤鳂I(yè)成績 +出勤率+上機成績。講授新課1.1 什么是數(shù)據(jù)結(jié)構(gòu)講解：（數(shù)據(jù)結(jié)構(gòu)

8、課程的研究背景）從計算機最初以數(shù)值計算為主到大量非數(shù)值計算出現(xiàn)引出數(shù)據(jù)結(jié)構(gòu)。講解：（數(shù)據(jù)結(jié)構(gòu)課程的研究對象）例1-1圖書館的書目檢索系統(tǒng)自動化問題。1-2計算機和人機對奕問題1-3多叉路口交通燈的管理問題總結(jié)：從以上三個例子可以看出，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如線性表、樹和圖等之類的數(shù)據(jù)結(jié)構(gòu)，這些都是數(shù)據(jù)結(jié)構(gòu)課程的研究對象。因此， 簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之 間的關(guān)系和操作等等的學(xué)科。介紹數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展以及與其他課程之間的關(guān)系。1.2 基本概念和術(shù)語基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、結(jié)構(gòu)（

9、1）常見基本結(jié)構(gòu)（邏輯結(jié)構(gòu)）：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)一般用一個二元組來表示：Data_Structure=（D,S）其中：D是數(shù)據(jù)元素的有限集，S是D上的關(guān)系的有限集DS表示一種數(shù)據(jù)結(jié)構(gòu)，它由數(shù)據(jù)元素集合K和在K上定義的一種二元關(guān)系的集合 R所組成。其中：K Ki |0 i n，n 0是數(shù)據(jù)元素的有限集合，n為DS中數(shù)據(jù)元素的個數(shù)。R Rj |0 j m,m 0是k上關(guān)系的有限集合，m為k上關(guān)系的個數(shù)，通常情況下m 的取值為1。K上任何一個二元關(guān)系 Rj是序偶的集合。對于 Rj中的任一序偶<x, y> （x, y K）,稱x 為第一

10、個元素（或y的前驅(qū)），y為第二個元素（或 x的后繼）。數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系還可以用圖形直觀地表示出來。圖形中的 每個結(jié)點對應(yīng)一個數(shù)據(jù)元素，兩結(jié)點之間帶箭頭的連線對應(yīng)二元關(guān)系中的一個序偶，其中序 偶的第一個元素稱為弧尾，第二個元素稱為弧頭。舉例講解：例 數(shù)據(jù)Z構(gòu) line=K, R,其中 K=01 , 02, 03, 04,05, 06, 07,08,09, 10, R=r,r=<01 , 02>, <02, 03>,<03, 04>,<04,05>, <05, 06>,<06, 07>,<07,0

11、8>, <08, 09>,<09, 10>。例數(shù)據(jù)結(jié)構(gòu) tree=K ,R,其中 K=01, 02, 03, 04, 05, 06, 07,08,09, 10, R=r,r=<01 , 02>, <01, 03>,<01, 04>, <02,05>, <02, 06>,<04, 07>,<04,08>, <06, 09>,<06, 10>。例數(shù)據(jù)吉構(gòu) graph=K , R,其中 K=01 , 02, 03, 04, 05 , R=r , r=<01

12、, 02>, <02, 01>, <01, 04>, <04, 01>, <01, 03>, <03, 01>, <02, 04>, <04, 02>, <03, 05>, <05, 03>。介紹常見數(shù)據(jù)結(jié)構(gòu)(集合、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu))具體表示方式(2)邏輯結(jié)構(gòu)上述數(shù)據(jù)結(jié)構(gòu)的定義是對操作對象的一種數(shù)學(xué)描述，是從操作對象抽象出來的數(shù)學(xué)模型。結(jié)構(gòu)定義中的 關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。根據(jù)這種邏輯關(guān)系通常將數(shù)據(jù)結(jié)構(gòu)劃分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，

13、其中非線性結(jié)構(gòu)又分為樹型結(jié)構(gòu) 和圖型結(jié)構(gòu)。(3)物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(存儲映象)稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲結(jié)構(gòu)，它涉及到數(shù)據(jù)元素及其相互關(guān)系在計算機內(nèi)部的表示形式。數(shù)據(jù)元素之間的關(guān)系在計算機中有兩種不同 的表示方法：順序映像和非順序映像。根據(jù)數(shù)據(jù)元素相互之間的關(guān)系在計算機中的表示形式 將數(shù)據(jù)的物理結(jié)構(gòu)劃分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。順序映像的特點是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非 順序映像的特點是借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。注意：數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個方面，任何一個算法的設(shè)計取決于 選定的數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依

14、賴于采用的存儲結(jié)構(gòu)。(4)數(shù)據(jù)結(jié)構(gòu)一般包括三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運算(舉例講解)小結(jié)：總結(jié)本講的主要內(nèi)容四、作業(yè)布置見習(xí)題集單元名稱：第 二講：線性表的類型定義，線性表的順序存儲、教學(xué)目標(biāo)掌握線性表的順序表示和實現(xiàn).、重點與難點線性表的順序表示和實現(xiàn)。三、教學(xué)過程的具體安排講授新課2.1線性表的類型定義線性表的定義：一個線性表是n個數(shù)據(jù)元素的有限序列。其中每個數(shù)據(jù)元素的具體含義，在不同的情況下各不相同，但是同一線性表中的元素必定具有相同特性，即屬于同一數(shù) 據(jù)對象。例如：26個英文字母表；學(xué)生健康情況登記表(圖 2.1)等。例如線性表(ai,ai-ia,ai+i,an

15、),稱ai-i是ai的直接前驅(qū)元素，a+i是ai的直接后繼。引導(dǎo)學(xué)生自己總結(jié)線性結(jié)構(gòu)的特點。線性表的長度：線性表中元素的個數(shù)(n> 0) , n=0為空表。 線性表中數(shù) 據(jù)元素的位序(如數(shù)據(jù)元素ai在線性表中的位序為i)。抽象數(shù)據(jù)類型線性表的定義：講解定義中的數(shù)據(jù)對象，數(shù)據(jù)關(guān)系以及基本操作(教材Pi9),重點講解 常用的基本操作含義。通過示例2-i , 2-2講解更復(fù)雜的基本操作，并分析時間復(fù)雜度。2.2線性表的順序表示和實現(xiàn)(i )線性表的順序表示：用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù) 據(jù)元素。# 2)順序儲存的地址關(guān)系：假設(shè)線性表的每個元素需占用l個存儲單元， 并以所占的第一個

16、單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+i 個數(shù)據(jù)元素的存儲位置LOC( a i+ i)和第i個數(shù)據(jù)元素的存儲位置LOC(a i)之間滿 足下列關(guān)系：LOC(a i+i)=LOC(a i)+l線性表的第i個數(shù)據(jù)元素ai的存儲位置為：LOC(a i)=LOC(a i)+(i-i)*l,其中 LOC(a i)為線性表的基地址。# 3)順序表及其特點，順序儲存結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。# 4)線性表的動態(tài)分配順序存儲結(jié)構(gòu)。# define LIST_INIT_SIZEi00# define LISTINCREMENT10Typedef struct ElemType*elem;in

17、tlength;intlistsize;SqList;(1)基于順序存儲結(jié)構(gòu)的基本操作的實現(xiàn)主要介紹下面的基本操作并且分析時間復(fù)雜度。InitList_Sq(SqList &L);ListInsert_Sq(SqList &L, int i, ElemType e);ListDelete_Sq(SqList &L, int i, ElemType &e);LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType);MergeList_Sq(SqList La,SqList L

18、b, SqList &Lc);重點講解：順序存儲結(jié)構(gòu)上實現(xiàn)線性表的插入操作設(shè)線性表A %a2, ,ai 1,a,ai 1, ,an ,為了保證線性表的有序性，當(dāng)在位 置i1 i n 1之前插入一個新的數(shù)據(jù)元素x時，需要將第i個到第n個數(shù)據(jù)元素均向后移動一個位置，然后將數(shù)據(jù)元素x存儲到第i個位置上并改變線性表 的長度。Status ListInsert_Sq(SqList &L, int i, ElemType e) /在順序線性表L的第i個元素之前插入新的元素e,/ i 的合法值為 K i < Listlength_Sq(L)+1if (i < 1 | i >

19、 L.length+1) return ERROR; 插入位置不合法if (L.length >= L.listsize) /當(dāng)前存儲空間已滿，增加 分配newbase = (ElemType *)realloc(L.elem,(ElemType);存儲分配失敗增加存儲容量(L.listsize+LISTINCREMENT)*sizeof if (!newbase) exit(OVERFLOW); / L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; /q = &(L.elemi-1); q 指示插入位置for (p = &

20、amp;(L.elemL.length -1); p >= q; -p) *(p+1) = *p;/插入位置及之后的元素右移# q = e; / 插入 e+L.length; 表長增 1return OK; / ListInsert_Sq平均時間雜度分析：f(n) (0 1 2n)/(n 1)n/2 。順序存儲結(jié)構(gòu)上實現(xiàn)線性表的刪除操作設(shè)線性表A 如九,a 11ai,ai 1, a ，為了保證線性表的有序性，當(dāng)刪除 第i(1 i n)個位置上的元素后，需要將第i+1個到第n個數(shù)據(jù)元素均向前移動 一個位置并改變線性表的長度。Status ListDelete_Sq(SqList &

21、L, int i, ElemType &e) /在順序線性表L中刪除第i個元素，并用e返回其值。/ i 的合法值為 1 w i w ListLength_Sq(L)if (i < 1) | (i > L.length) return ERROR;/ 刪除位置不合法p = &(L.elemi-1);/ p為被刪除元素的位置e = *p;/被刪除元素的值賦給eq = L.elem+L.length -1;/ 表尾元素 的位置for (+p; p <= q; +p) *(p-1) = *p;/被刪除元素之后的元素左移# -L.length; / 表長減 1retur

22、n OK;(n 1)/n n 1/2 O(n)"/ ListDelete_Sq平均時間復(fù)雜度分析：f(n) (0 1 2總結(jié)： 順序存儲結(jié)構(gòu)的優(yōu)缺點順序結(jié)構(gòu)的優(yōu)點是結(jié)構(gòu)簡單，對數(shù)據(jù)元素既可以實現(xiàn)順序訪問，又可以實 現(xiàn)隨機訪問；缺點是插入和刪除操作需要移動大量的數(shù)據(jù)元素。小結(jié)：本講主要介紹了線性表的邏輯結(jié)構(gòu)定義和基本運算，線性表的插入和刪除操作在順序存儲結(jié)構(gòu)上的實現(xiàn)。小結(jié)：總結(jié)本講的主要內(nèi)容四、作業(yè)布置見習(xí)題集實驗作業(yè)見實驗指導(dǎo)單元名稱：第三講：線性表鏈?zhǔn)酱鎯?、教學(xué)目標(biāo)掌握單鏈表的表示和實現(xiàn)、重點與難點單鏈表的存儲結(jié)構(gòu)和基本操作實現(xiàn)。三、教學(xué)內(nèi)容與教學(xué)過程復(fù)習(xí)線性表的順序存儲結(jié)構(gòu)的特點

23、引入另一種表示方法鏈?zhǔn)酱鎯Y(jié)構(gòu)。講授新課2.3.1線性鏈表（1 ）線性鏈表線性鏈表：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這組存儲單元 可以是連續(xù)的，也可以是不連續(xù)的）。線性鏈表的存儲結(jié)構(gòu)：以元素（數(shù)據(jù)元素的映象）+指針（指示后繼元素存儲位置尸結(jié)點（表示數(shù)據(jù)元 素 或 數(shù)據(jù)元素的映象），其中指針域只有一個。舉例講解：教材圖2.5線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭 指針。有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點”，以指向頭結(jié) 點的指針為鏈表的頭指針。線性表為空時，頭結(jié)點的指針域為空。舉例如圖2.7.線性表的單鏈表存儲結(jié)構(gòu)的C語言描述：typedef s

24、truc LNode/定義單鏈表結(jié)點ElemTypestruct LNodeLNode, *LinkList ;單鏈表操作的實現(xiàn)：GetElem(L, i, e)ListInsert(&L, i, e)ListDele CreateList(&L, n)data;*next ;/指向后繼的指針域/取第i個數(shù)據(jù)元素/插入數(shù)據(jù)元素/生成含n個數(shù)據(jù)元素的鏈表CreateList(&L, n)/生成含n個數(shù)據(jù)元素的鏈表MergeList (&La,&Lb,&Lc) 合并兩個有序鏈表（1）建立單鏈表（要求從頭部插入）L。void CreateList_L(

25、LinkList &L, int n) /逆位序輸入n個元素的值，建立帶表頭結(jié)點的單鏈線性表L = (LinkList) malloc (sizeof (LNode);L->next = NULL; /先建立一個帶頭結(jié)點的單鏈表for (i = n; i > 0; -i ) p = (LinkList) malloc (sizeof (LNode); /生成新結(jié)點scanf(&p->data); / 輸入元素值p->next = L->next; L->next = p; /插入至 U表頭 / CreateList_L注：從頭部插入元素建立單

26、向鏈表得到的線性序列為輸入序列的逆序列。（2）建立單鏈表（要求從尾部插入）void CreateList_L（LinkList &L, int n） L。正位序輸入n個元素的值，建立帶表頭結(jié)點的單鏈線性表L = (LinkList) malloc (sizeof (LNode);r = L;L->next = NULL; /先建立一個帶頭結(jié)點的單鏈表for (i = n; i > 0; -i ) p = (LinkList) malloc (sizeof (LNode); /生成新結(jié)點scanf(&p->data); / 輸入元素值p->next=r-&

27、gt;next; r->next=p; r = p; /插入至 U表尾 CreateList_L(3)在帶頭結(jié)點的單鏈表中插入結(jié)點分析：設(shè)在結(jié)點a和結(jié)點b之間插入數(shù)據(jù)為 x的結(jié)點，通過圖來分析則插入前和插入后的 情況。Status ListInsert_L(LinkList L, int i, ElemType e) /在帶頭結(jié)頭的單鏈表L中第i位置之前插入元素 ep = L; j = 0;while (p && j < i-1) p = p->next; +j; 尋找第 i-1 個結(jié)點if (!p | j > i-1) return ERROR; i

28、小于 1 或者大于表長s = (LinkList) malloc ( sizeof (LNode); /生成新結(jié)點s->data = e; s->next = p->next; / 插入 L 中p->next = s;return OK; / LinstInsert_L(4)在帶頭結(jié)點的單鏈表中刪除結(jié)點Status ListDelete_L(LinkList L, int i, ElemType &e)p = L; j = 0;while (p->next && j < i-1) p = p->next; +j; 尋找第i個結(jié)點

29、并令p指向其前趨if (!(p->next) | j > i-1) return ERROR; /刪除位置不合理q = p->next; p->next = q->next; / 刪除并釋放結(jié)點e = q->data; free(q);return OK;"/ ListDelete_L注：上述兩個算法的時間復(fù)雜度均為O(n)。單鏈表的優(yōu)點：它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預(yù)先分配空間插入、刪除操作方便單鏈表的缺點：指針占用額外存儲空間不能隨機存取，查找速度慢小結(jié)：本講主要介紹了單鏈表的存儲結(jié)構(gòu)，以及的基本操作（建立、插入和刪除）的實

30、現(xiàn)。四、作業(yè)布置見習(xí)題集實驗作業(yè)見實驗指導(dǎo)。第四講 循環(huán)鏈表，雙向鏈表，鏈表應(yīng)用、教學(xué)目標(biāo)1 . 了解循環(huán)鏈表和的基本概念；2 .掌握雙向鏈表的插入和刪除操作；3 .掌握一元多項式的表示及加法在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)、重點與難點雙向鏈表的存儲結(jié)構(gòu)和基本操作實現(xiàn)。三、教學(xué)內(nèi)容與教學(xué)過程講授新課單向循環(huán)鏈表設(shè)指針p指向單向鏈表中最后一個結(jié)點，則 p->next的值是0,表示該結(jié)點是單向鏈表的最后一個結(jié)點。如果將單向鏈表中的最后一個結(jié)點的指針域改為存放單向鏈表中第一個結(jié)點的地址值，使得整個線性鏈表構(gòu)成一個環(huán)，則稱這種線性鏈表為單向循環(huán)鏈表。設(shè)p指向單向循環(huán)鏈表中的最后一個結(jié)點， 則p->n

31、ext的值不是。而是等于指向循環(huán)鏈表中的第一個結(jié)點head的值。雙向鏈表如果鏈表中的每個結(jié)點都有兩個指針域，分別指向其前驅(qū)結(jié)點和后繼結(jié)點，則稱這種鏈表為雙向鏈表。雙向鏈表中的結(jié)點類型描述如下：typedef struct DuLNode ElemType data;/ 數(shù)據(jù)域struct DuLNode *prior; /指向前驅(qū)的指針域struct DuLNode *next; /指向后繼的指針域 DuLNode, *DuLinkList;設(shè)指針p指向雙向鏈表中的某個結(jié)點，則顯然有以下的結(jié)論：p->prior->next=p=p->next->prior(1)雙向鏈表

32、的插入操作設(shè)指針變量p指向雙向鏈表中的結(jié)點 A,指針變量q指向被插入的新結(jié)點B,則在結(jié)點A的后面插入結(jié)點 B的操作序列為：(1) q->next=p->next ;(2) p->next->prior=q ;(3) p->next=q ;(4) q->prior=p ;(2)雙向鏈表的刪除操作設(shè)指針變量p指向雙向鏈表中被刪除的結(jié)點X,則刪除結(jié)點X的操作序列為：(1) p->prior->next=p->next ;(2) p->next->prior=p->prior ;(3) free(p);注：在雙向鏈表或雙向循環(huán)鏈表

33、中進行插入和刪除操作時，尤其要注意修改有關(guān)結(jié)點指針域的操作次序，以免丟失鏈域信息而造成鏈表中斷的錯誤。鏈?zhǔn)酱鎯Y(jié)構(gòu)的應(yīng)用：一元多項式的表示及相加一元多項式Pn(x)可按升哥寫成：Pn(x)P0Px P2x2 LPnxn它由n+1個系數(shù)唯一確定。在計算機中，可用一個線性表P來表示：P(Po,P,P2,L , R)每項系數(shù)i隱含在系數(shù)P的序號里。若Qm(x)為一個一元多項式，同樣用線性表 Q表示：歡迎下載14Q(Qo,Qi,Q2,L ,Qm)這兩個多項式可以相加，結(jié)果為R(x) E(x) Qm(x),其中設(shè)n m,則用線性表表示R為：R (Po Qo小 Ql,P2 Q2,L ,Pm Qm,Pm1,

34、L ,E)我們可以采用順序存儲結(jié)構(gòu)存放P、Q和R,使得多項式相加算法定義十分簡介。然而，在通常的應(yīng)用中，多項式的次數(shù)很高且變化很大，使得順序存儲結(jié)構(gòu)的最大長度很難確定，特別是在處理形如S(x)=1+3x 10001+2x20000的多項式時，要用長度為 20001的線性表來表示。如果對每個元素使用兩個數(shù)據(jù)項，一個為系數(shù)項，另一個為指數(shù)項，則這樣構(gòu)成的線性表可表 示成：P (品,，),(P,ei),(P2©),L ,(Pn,en)因此上式S(x)可表示成(1,0 ),(3, 1001), (2, 20000 )。顯然這樣的線性表應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。課本P41圖2.17中兩個線性鏈表分別

35、表示一元多項式A(x)=7+3x+9x 8+5x11和一元多項式B(x)=8x+22x 7-9x8,由這兩個多項式得到的和多項式如圖課本P412.18所示。用鏈表表示多項式時，鏈表中的數(shù)據(jù)類型描述成：typedef struct polynomialfloat coef;int expn ;struct polynomial *next;ElemType;根據(jù)一元多項式相加的運算規(guī)則：對于兩個一元多項式中所有指數(shù)相同的項，對應(yīng)系數(shù) 相加，若其和不為零，則構(gòu)成和多項式中的一項；對于兩個一元多項式中所有指數(shù)不相同的 項則分別抄到和多項式中去。第一步：分別從A表和B表的表頭開始，根據(jù)比較pa->

36、;expn和pb->expn的比較結(jié)果分三種情況討論，直到 A表或B表全部處理完。(1) pa->expn=pb->expn :則相加此兩項的系數(shù)，如果相加后該項系數(shù)不等于0,則在C表中生成一個新結(jié)點存放該項，修改pa和pb使其指向各自的下一個結(jié)點。(2) pa->expn > pb->expn ：則復(fù)制A表中pa所指向的結(jié)點到 C表中，修改pa使其指向下 一個結(jié)點。(3) pa->expn < pb->expn ：則復(fù)制B表中pb所指向的結(jié)點到 C表中，修改pb使其指向 下一個結(jié)點。第二步：若B表沒有處理完，將 B表中剩余結(jié)點復(fù)制到C表中

37、；反之則將 A表中剩余結(jié)點復(fù)制到C表中。void create_item(LinkList &pc,float coef,int expn)p=(LinkList)malloc(sizeof(LNode);p->coef=coef; p->expn=expn; pc->next=p; pc=p;void ploy_add(LinkList pah,LinkList pbh,LinkList &pch)pa = pah; pb = pbh;pc = pch=(LinkList *)malloc(sizeof(LNode); / 為 c 鏈表添加一個頭結(jié)點whil

38、e(pa!=0 && pb!=0)if(pa->expn=pb->expn)x=pa->coef+pb->coef;if(x!=0) create_item(pc,x,pa->expn);pa=pa->next; pb=pb->next;else if(pa->expn>pb->expn)create_item(pc,pa->coef,pa->expn);pa=pa->next;else create_item(pc,pb->coef,pb->expn); pb=pb->next;w

39、hile (pa!=0) create_item(pc,pa->coef,pa->expn);pa=pa->next;while (pb!=0) create_item(pc,pb->coef,pb->expn);pb=pb->next;pc->next=0; pc=pch; pch=pch->next; free(pc); /* 釋放 c鏈中的頭結(jié)點*/小結(jié)：本講主要介紹了循環(huán)鏈表和雙向鏈表的基本概念，雙向鏈表的插入和刪除操作，一元 多項式的表示及相加在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)。四、作業(yè)布置見習(xí)題集實驗作業(yè)見實驗指導(dǎo)。單元名稱：第五講：棧一、教學(xué)目

40、標(biāo)1 , 了解棧的基本概念和基本操作；2 .掌握棧的基本操作在兩種存儲結(jié)構(gòu)上的實現(xiàn)。二、重點與難點棧的基本操作在兩種存儲結(jié)構(gòu)上實現(xiàn)。三、教學(xué)內(nèi)容與教學(xué)過程首先復(fù)習(xí)線性表的知識，引入限定性的數(shù)據(jù)結(jié)構(gòu)棧和隊列。講授新課3.1 棧3.1.1 抽象數(shù)據(jù)類型棧的定義棧：限定僅在表尾進行插入或刪除操作的線性表，表尾一棧頂，表頭一棧 底，不含元素的空表稱空棧。通過教材P44的圖3.1講解棧頂，棧底以及棧后進先出的特點。棧的抽象數(shù)據(jù)類型定義：ADT Stack 數(shù)據(jù)對象：D = ai | ai C ElemSet, i=1,2,n, n > 0 數(shù)據(jù)關(guān)系：R1 = <ai-1, ai >|

41、ai-1, ai C D, i=2,n 約定 an 端為棧頂，a1端為棧底?；静僮鳎篒nitStack(&S) DestroyStack(&S) ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S, &e)Push(&S, e) Pop(&S, &e) ADT Stack3.1.2 棧的表示和實現(xiàn)順序棧類似于線性表的順序映象實現(xiàn)，指向表尾的指針可以作為棧頂指針。100;10;棧的順序存儲表示：#defineSTACK_INIT_SIZE#defineSTACKINCREMENTtypede

42、f struct SElemType*base;SElemType*top;int stacksize; SqStack;順序棧的基本操作的算法描述：初始化，返回棧頂元素，入棧，i(a)?？諚M條件?？諚l件：top=base棧滿 條件：base-top=stacksize(b)入棧操作Status Push (SqStack &S, SElemType e) if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if

43、(!S.base ) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMEN T;歡迎下載17*S.top+ = e;return OK;(c)出棧操作Status Pop (SqStack &S, SElemType &e) if (S.top=S.base) return ERROR;e=*-S.top;return OK;鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)。棧頂指針就是鏈表的頭指針棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)類似單鏈表的存儲結(jié)構(gòu)，鏈表中第一個結(jié)點表示棧頂，最后一個結(jié)點 表示棧底。由于鏈表的長度可以動態(tài)增長，因此進行入棧

44、操作時無需考慮棧的上溢，但進行 出棧操作時，必需考慮棧的下溢，下溢的條件是top的值為0。鏈?zhǔn)綏５娜霔２僮鱏tatus Push(LinkList &top, ElemType x)p=(LinkList *)malloc(sizeof(LNode);p->data=x; p->next=top; top=p; return OK;(2)鏈?zhǔn)綏５某鰲２僮鱏tatus Pop(LinkStack &top, ElemTye &y)if (top=0) return ERROR;p=top; y=p->data; top=p->next; free(

45、p);return OK;小結(jié)；本講主要介紹了棧的基本概念，棧的基本運算，棧在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上 實現(xiàn)基本操作。四、作業(yè)布置見習(xí)題集實驗作業(yè)見實驗指導(dǎo)。單元名稱：第六講：隊列教學(xué)目標(biāo)1 , 了解棧的基本概念和基本操作；2 .掌握棧的基本操作在兩種存儲結(jié)構(gòu)上的實現(xiàn)。歡迎下載18二、重點與難點棧的基本操作在兩種存儲結(jié)構(gòu)上實現(xiàn)。三、教學(xué)內(nèi)容與教學(xué)過程講授新課隊列的基本概念隊列是一種限制所有插入操作在線性表的一端進行，而所有的刪除操作在線性表的另一端進行的特殊線性表。允許插入(入隊)操作的一端稱為隊尾，允許刪除(出隊)操作的一端稱為隊頭。設(shè)隊列為q (ai,a2,L ,an),則ai是隊頭元

46、素，小是隊尾元素。隊列中的元素按照ai,a2,L ,烝的順序進入隊 列的，退出隊列也只能按照這個次序依次退出，即只有在 ai,a2,L ,41都退出隊列后，an才能退出隊列。因此隊列也稱為先進先出 (FIFO)的線性表。 2、隊列的基本操作InitQueue(&Q)DestroyQueue(&Q) ClearQueue(&Q)QueueEmpty(Q) QueueLength(Q) GetHead(Q, &e)EnQueue(&Q, e) DeQueue(&Q, &e)3、隊列的順序存儲結(jié)構(gòu)和循環(huán)隊列在隊列的順序存儲結(jié)構(gòu)中，除了用一組地址

47、連續(xù)的存儲單元依次存放從隊 頭到隊尾的元素之外，還需要附設(shè)兩個指針front 和rear 。為了在C語言中描 述方便起見，在此我們約定：初 始化建立空隊列時，令front=rear=0 ，每當(dāng)插 入新的隊尾元素時，尾指針rear增1;每當(dāng)刪除隊頭元素時，頭指針front 增 1。因此，在非空隊列中，頭指針始終指向隊列頭元素，尾指針始終指向隊列尾 元素的下一個位置。討論：將數(shù)據(jù)10 , 20 , 30 , 40 , 50, 60按照入隊列、入隊列、入隊列、出 隊列、出隊列、入隊列、入隊列、入隊列、出隊列和出隊列的順序，觀察隊列 中隊頭和隊尾指針的變化狀態(tài)。假設(shè)當(dāng)前為隊列分配的最大空間為6 ,則不

48、可再繼續(xù)插入新的隊尾元素， 否則會因數(shù)組越界而導(dǎo)致程序代碼被破環(huán)，然而，此時又不宜如順序棧那樣進 行存儲再分配擴大數(shù)組空間，因為隊列的實際可用空間并末占滿。解決這個問 題的巧妙方法是將順序隊列的存儲空間想象成一個邏輯上首尾相連的環(huán)狀空 間，這種存儲結(jié)構(gòu)稱為循環(huán)隊列。分析課本P64圖3.14 可知，Q.front=Q.rear 無法判斷隊列空間是"滿" 還是“空”。解決這個問題有兩種方法：其一是另設(shè)一個標(biāo)志位以區(qū)別隊列是 “空”還是“滿”；其二是少用一個元素空間，約定以隊頭指針在隊尾指針的 下一個位置上作為隊列“滿”的標(biāo)志。因此，判斷隊列空的條件為 Q.front=Q.rea

49、r ;判斷隊列滿的條件為 Q.front = (Q.rear+1) % MAXQSIZE。(a) 順序循環(huán)隊列的類型描述typedef struct QElemType *base; int front; int rear; SqQueue;(b) 順序循環(huán)隊列的入隊列操作status EnQueue(SqQueue&Q, QelemType e)if (Q.rear+1)%MAXSIZE=Q.front) return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;歡迎下載19return OK;(c) 順序循環(huán)隊列的出隊列操作stat

50、us DeQueue(SqQueue &Q, QelemType &e) if (Q.rear=Q.front) return ERROR;e = Q.baseQ.front;Q.front = (Q.front+1)%MAXSIZE;return OK;4、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)實際上是一個同時帶有頭指針和尾指針的單向鏈表， 頭指針指向隊頭元素，尾指針指向隊尾元素。為了操作方便起見，給鏈?zhǔn)疥犃?添加一個頭結(jié)點。空的鏈?zhǔn)疥犃械呐袛鄺l件為頭指針和尾指針都指向頭結(jié)點。(d) 鏈?zhǔn)窖h(huán)隊列的類型描述typedef struct QNode QElemType data;

51、struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; /隊 頭指針QueuePtr rear; /隊尾指針 LinkQueue;(e) 鏈?zhǔn)疥犃械娜腙犃胁僮鱯tutus EnQueue(LinkQueue &Q, QelemType e)p=(QueuePtr)malloc(sizeof(Qnode);if(!p)exit(OVERFLOW);p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p;return OK;(f) 鏈?zhǔn)疥犃械某鲫犃胁?/p>

52、作。status DeQueue (LinkQueue &Q, QelemType &e) if(Q.front=Q.rear returnERROR;p=Q.front->next; e=p->data; Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;注意：當(dāng)隊列中最后一個元素被刪除后，隊列尾指針也丟失了，因此需要對 隊尾指針重新賦值。小結(jié)：主講主要介紹了隊列的基本概念和基本操作，以及隊列的基本操作在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)。四、作業(yè)布置見習(xí)題集實驗作業(yè)見

53、實驗指導(dǎo)。歡迎下載25教學(xué)目標(biāo)單元名稱：第七講：串1 .熟悉串的定義以及基本操作的定義，并能利用這些基本操作來實現(xiàn)串的 其它各種操作的方法。2 .熟練掌握在串的定長順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法。3 .掌握串的堆分配存儲結(jié)構(gòu)以及在其上實現(xiàn)串操作的基本方法。4 .了解串的塊鏈存儲結(jié)構(gòu)二、重點與難點串的存儲結(jié)構(gòu)以及基本操作的實現(xiàn)。三、教學(xué)內(nèi)容與教學(xué)過程講授新課4.1 串類型的定義(1 )基本概念：串(string ):由零個或多個字符組成的有限序列，也稱字符串。記為：S ='ala2a3an' (n 0) 如：A= 'BEIJING', B= 'JIN

54、G'串的長度：串中字符的數(shù)目n ?？沾翰缓魏巫址拇?，串長度為0,空格串：僅由一個或多個空格組成的串，長度為串中空格字符的個數(shù)。如： ， C= ' BEI JING '子串：由串中任意個連續(xù)的字符組成的子序列。主串：包含子串的串。如：A= ' BEIJING ' B= ' JING '字符在串中的位置：字符在序列中的序號。子串在主串中的位置：以子串的第一個字符在主串中的位置來表示。如：A= ' BEIJING B= 'JING B 在 A 中的位置為 4。串相等：當(dāng)且僅當(dāng)兩個串的值相等。也就是說，只有兩個串的長度相等

55、且各個對應(yīng)位置的字符都相等時才相等。(2)串的抽象數(shù)據(jù)類型定義：ADT String 數(shù)據(jù)對象：D = ai |ai £ CharacterSet, i=1,2,n, n> 0 數(shù)據(jù)關(guān)系：R1 = < ai-1, ai > | ai-1, ai C D, i=2,n 基本操作：(見教材P71 ) ADT String通過基本操作可以實現(xiàn)更復(fù)雜的操作。如通過判等、求串長和求子串等操 作可以實現(xiàn)定位函數(shù)Index 。4.2 串的表示和實現(xiàn)4.2.1 定長順序存儲表示用一組地址連續(xù)的存儲單元存儲串值的字符序列，類似于線性表的順序存 儲結(jié)構(gòu)。所謂定長順序存儲結(jié)構(gòu)，是直接使用

56、定長的字符數(shù)組來定義，數(shù)組的 上界預(yù)先給出：#define MAXSTRLEN 255/ 用 戶可在 255以內(nèi) 定義最大串長typedef unsigned char SStringMAXSTRLEN + 1;/ 0 號單元存放串的長度特點：串的實際長度可在這個予定義長度的范圍內(nèi)隨意設(shè)定，超過予定義長度的 串值則被舍去，稱之為截斷”。按這種串的表示方法實現(xiàn)的串的運算時，其基本操作為 字符序列的復(fù)制” (通過串聯(lián)接和求子串來講解)。4.2.2 堆分配存儲表示以一組地址連續(xù)的存儲單元存儲串值的字符序列，存儲空間在程序執(zhí)行過 程中動態(tài)分配。C語言中提供的串類型就是以這種存儲方式實現(xiàn)的。系統(tǒng)利用函數(shù)malloc() 和free()進行串值空間的動態(tài)管理，為每一個新產(chǎn)生的串分配一個存儲區(qū)，稱 串值共享的存儲空間為堆”。C語言中的串以一個空字符為結(jié)束符，串長是一個隱含值。串堆分配存儲表示：typedef struct