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

. 課程教案課程名稱： 數(shù)據(jù)結(jié)構(gòu) 授課教師：學(xué)習(xí)對象：任課時間：一、學(xué)生情況分析數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)的一門核心專業(yè)課程。學(xué)生在前期的學(xué)習(xí)中已經(jīng)學(xué)習(xí)了C語言程序設(shè)計課程。通過本課程學(xué)習(xí)使學(xué)生對提高編寫程序的能力以及解決實際問題的能力。二、課程教學(xué)目標(biāo)數(shù)據(jù)結(jié)構(gòu)是計算機(jī)學(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)容第一章 緒論教學(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ù)雜度的漸進(jìn)表示法；教學(xué)要求： 了解：數(shù)據(jù)結(jié)構(gòu)基本概念及數(shù)據(jù)結(jié)構(gòu)的抽象層次 了解：抽象數(shù)據(jù)類型概念 了解：算法的定義及算法特性 掌握：算法的性能分析與度量方法第二章 線性表教學(xué)內(nèi)容：1） 線性表的定義和特點2） 線性表的順序存儲及查找、插入和刪除操作3） 線性表的鏈?zhǔn)酱鎯安檎?、插入和刪除操作4） 使用線性表的實例教學(xué)要求：了解：線性表的定義和特點熟練掌握：線性表的順序存儲結(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) 數(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) 霍夫曼樹：路徑長度；霍夫曼樹；霍夫曼樹編碼教學(xué)要求：了解：樹和森林的概念掌握：二叉樹的概念、性質(zhì)及二叉樹的表示熟練掌握：二叉樹的遍歷方法掌握：線索化二叉樹的特性及尋找某結(jié)點的前驅(qū)和后繼的方法掌握：樹和森林的實現(xiàn)及遍歷方法掌握：二叉樹的計數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法掌握：霍夫曼樹的實現(xiàn)方法及霍夫曼編碼的概念第七章 圖教學(xué)內(nèi)容：1）圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型2）圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表3）圖的遍歷與連通性；深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量4）最小生成樹：克魯斯卡爾算法；普里姆算法教學(xué)要求：掌握：圖的基本概念和圖的存儲表示熟練掌握：圖的兩種遍歷方法與求解連通性問題的方法掌握：構(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)課程的體系結(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)容及安排本課程是計算機(jī)專業(yè)的重要專業(yè)課之一，主要介紹常用的數(shù)據(jù)結(jié)構(gòu)以及相關(guān)算法。本課程主要講授線性表、棧和隊列、串、數(shù)組、樹和二叉樹、圖、查找、排序等內(nèi)容。成績考核方式為：期末成績+平時成績，其中期末成績占70%，平時成績占30%，平時成績?yōu)椋鹤鳂I(yè)成績+出勤率+上機(jī)成績。講授新課1.1 什么是數(shù)據(jù)結(jié)構(gòu) 講解：（數(shù)據(jù)結(jié)構(gòu)課程的研究背景）從計算機(jī)最初以數(shù)值計算為主到大量非數(shù)值計算出現(xiàn)引出數(shù)據(jù)結(jié)構(gòu)。講解：（數(shù)據(jù)結(jié)構(gòu)課程的研究對象）例1-1圖書館的書目檢索系統(tǒng)自動化問題。1-2計算機(jī)和人機(jī)對奕問題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è)計問題中計算機(jī)的操作對象以及它們之間的關(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)（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)系的有限集表示一種數(shù)據(jù)結(jié)構(gòu)，它由數(shù)據(jù)元素集合K和在K上定義的一種二元關(guān)系的集合R所組成。其中：是數(shù)據(jù)元素的有限集合，n為中數(shù)據(jù)元素的個數(shù)。是K上關(guān)系的有限集合，m為K上關(guān)系的個數(shù)，通常情況下m的取值為1。K上任何一個二元關(guān)系Rj是序偶的集合。對于Rj中的任一序偶（x，yK），稱x為第一個元素（或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ù)結(jié)構(gòu)line=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，,，。例數(shù)據(jù)結(jié)構(gòu)tree=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=，。例 數(shù)據(jù)結(jié)構(gòu)graph=K，R，其中K=01，02，03，04，05，R=r，r=，。介紹常見數(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)，其中非線性結(jié)構(gòu)又分為樹型結(jié)構(gòu)和圖型結(jié)構(gòu)。(3) 物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示（存儲映象）稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲結(jié)構(gòu)，它涉及到數(shù)據(jù)元素及其相互關(guān)系在計算機(jī)內(nèi)部的表示形式。數(shù)據(jù)元素之間的關(guān)系在計算機(jī)中有兩種不同的表示方法：順序映像和非順序映像。根據(jù)數(shù)據(jù)元素相互之間的關(guān)系在計算機(jī)中的表示形式將數(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)依賴于采用的存儲結(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）等。 例如線性表（a1,ai-1,ai,ai+1,an），稱ai-1是ai的直接前驅(qū)元素， ai+1是 ai的直接后繼。引導(dǎo)學(xué)生自己總結(jié)線性結(jié)構(gòu)的特點。線性表的長度：線性表中元素的個數(shù)（n0），n=0為空表。 線性表中數(shù)據(jù)元素的位序（如數(shù)據(jù)元素ai在線性表中的位序為i）。抽象數(shù)據(jù)類型線性表的定義：講解定義中的數(shù)據(jù)對象，數(shù)據(jù)關(guān)系以及基本操作（教材P19），重點講解常用的基本操作含義。通過示例2-1，2-2講解更復(fù)雜的基本操作，并分析時間復(fù)雜度。2.2 線性表的順序表示和實現(xiàn)（1）線性表的順序表示：用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。（2）順序儲存的地址關(guān)系：假設(shè)線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC( a i+1)和第i個數(shù)據(jù)元素的存儲位置LOC(a i)之間滿足下列關(guān)系：LOC(a i+1)=LOC(a i)+l 線性表的第i個數(shù)據(jù)元素ai的存儲位置為：LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)為線性表的基地址。（3）順序表及其特點, 順序儲存結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。（4）線性表的動態(tài)分配順序存儲結(jié)構(gòu)。 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 Typedef struct ElemType *elem;int length;int listsize;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 Lb, SqList &Lc);重點講解：順序存儲結(jié)構(gòu)上實現(xiàn)線性表的插入操作設(shè)線性表，為了保證線性表的有序性，當(dāng)在位置i之前插入一個新的數(shù)據(jù)元素x時，需要將第i個到第n個數(shù)據(jù)元素均向后移動一個位置，然后將數(shù)據(jù)元素x存儲到第i個位置上并改變線性表的長度。Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序線性表L的第i個元素之前插入新的元素e，/ i的合法值為1iListlength_Sq(L)+1if (i L.length+1) return ERROR; / 插入位置不合法if (L.length = L.listsize) / 當(dāng)前存儲空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存儲分配失敗L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存儲容量q = &(L.elemi-1); / q指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表長增1return OK; / ListInsert_Sq平均時間復(fù)雜度分析： 順序存儲結(jié)構(gòu)上實現(xiàn)線性表的刪除操作設(shè)線性表 ，為了保證線性表的有序性,當(dāng)刪除第個位置上的元素后，需要將第i+1個到第n個數(shù)據(jù)元素均向前移動一個位置并改變線性表的長度。Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在順序線性表L中刪除第i個元素，并用e返回其值。/ i的合法值為1iListLength_Sq(L)if (i L.length) return ERROR; / 刪除位置不合法p = &(L.elemi-1); / p為被刪除元素的位置e = *p; / 被刪除元素的值賦給eq = L.elem+L.length-1; / 表尾元素的位置for (+p; p 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; / 插入到表頭 / CreateList_L注：從頭部插入元素建立單向鏈表得到的線性序列為輸入序列的逆序列。(2) 建立單鏈表（要求從尾部插入）void CreateList_L(LinkList &L, int n) /正位序輸入n個元素的值，建立帶表頭結(jié)點的單鏈線性表L。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-next; r-next=p; r = p; / 插入到表尾 / 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 next; +j; / 尋找第i-1個結(jié)點if (!p | j i-1) return ERROR; / i小于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 next; +j; /尋找第i個結(jié)點并令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ù)先分配空間插入、刪除操作方便單鏈表的缺點：指針占用額外存儲空間不能隨機(jī)存取，查找速度慢小結(jié)：本講主要介紹了單鏈表的存儲結(jié)構(gòu)，以及的基本操作（建立、插入和刪除）的實現(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-next的值不是0而是等于指向循環(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) 雙向鏈表的插入操作設(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)鏈表中進(jìn)行插入和刪除操作時，尤其要注意修改有關(guān)結(jié)點指針域的操作次序，以免丟失鏈域信息而造成鏈表中斷的錯誤。鏈?zhǔn)酱鎯Y(jié)構(gòu)的應(yīng)用：一元多項式的表示及相加一元多項式可按升冪寫成：它由n+1個系數(shù)唯一確定。在計算機(jī)中，可用一個線性表P來表示：每項系數(shù)i隱含在系數(shù)的序號里。若為一個一元多項式，同樣用線性表Q表示：這兩個多項式可以相加，結(jié)果為，其中設(shè)，則用線性表表示R為：我們可以采用順序存儲結(jié)構(gòu)存放P、Q和R，使得多項式相加算法定義十分簡介。然而，在通常的應(yīng)用中，多項式的次數(shù)很高且變化很大，使得順序存儲結(jié)構(gòu)的最大長度很難確定，特別是在處理形如S(x)=1+3x10001+2x20000的多項式時，要用長度為20001的線性表來表示。如果對每個元素使用兩個數(shù)據(jù)項，一個為系數(shù)項，另一個為指數(shù)項，則這樣構(gòu)成的線性表可表示成：因此上式S(x)可表示成(1, 0 ),(3, 1001), (2, 20000 )。顯然這樣的線性表應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。課本 P41 圖2.17中兩個線性鏈表分別表示一元多項式A(x)=7+3x+9x8+5x11和一元多項式B(x)=8x+22x7-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-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 expn：則復(fù)制B表中pb所指向的結(jié)點到C表中，修改pb使其指向下一個結(jié)點。第二步：若B表沒有處理完，將B表中剩余結(jié)點復(fù)制到C表中；反之則將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é)點while(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-expnpb-expn)create_item(pc,pa-coef,pa-expn); pa=pa-next;else create_item(pc,pb-coef,pb-expn); pb=pb-next;while (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é)目標(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ù)類型棧的定義棧：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾棧頂，表頭棧底，不含元素的空表稱空棧。通過教材P44的圖3.1講解棧頂，棧底以及棧后進(jìn)先出的特點。棧的抽象數(shù)據(jù)類型定義：ADT Stack 數(shù)據(jù)對象：D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：InitStack(&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)，指向表尾的指針可以作為棧頂指針。 棧的順序存儲表示： #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;順序棧的基本操作的算法描述：初始化，返回棧頂元素，入棧，出棧。(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(!S.base ) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*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)增長，因此進(jìn)行入棧操作時無需考慮棧的上溢，但進(jìn)行出棧操作時，必需考慮棧的下溢，下溢的條件是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(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)。二、重點與難點棧的基本操作在兩種存儲結(jié)構(gòu)上實現(xiàn)。三、教學(xué)內(nèi)容與教學(xué)過程講授新課隊列的基本概念隊列是一種限制所有插入操作在線性表的一端進(jìn)行，而所有的刪除操作在線性表的另一端進(jìn)行的特殊線性表。允許插入（入隊）操作的一端稱為隊尾，允許刪除（出隊）操作的一端稱為隊頭。設(shè)隊列為，則是隊頭元素，是隊尾元素。隊列中的元素按照的順序進(jìn)入隊列的，退出隊列也只能按照這個次序依次退出，即只有在都退出隊列后，才能退出隊列。因此隊列也稱為先進(jìn)先出（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)中，除了用一組地址連續(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，則不可再繼續(xù)插入新的隊尾元素，否則會因數(shù)組越界而導(dǎo)致程序代碼被破環(huán)，然而，此時又不宜如順序棧那樣進(jìn)行存儲再分配擴(kuò)大數(shù)組空間，因為隊列的實際可用空間并末占滿。解決這個問題的巧妙方法是將順序隊列的存儲空間想象成一個邏輯上首尾相連的環(huán)狀空間，這種存儲結(jié)構(gòu)稱為循環(huán)隊列。分析課本P64圖3.14可知，Q.front=Q.rear無法判斷隊列空間是“滿”還是“空”。解決這個問題有兩種方法：其一是另設(shè)一個標(biāo)志位以區(qū)別隊列是“空”還是“滿”；其二是少用一個元素空間，約定以隊頭指針在隊尾指針的下一個位置上作為隊列“滿”的標(biāo)志。因此，判斷隊列空的條件為Q.front=Q.rear；判斷隊列滿的條件為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;return OK;(c) 順序循環(huán)隊列的出隊列操作status 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é)點。(a) 鏈?zhǔn)窖h(huán)隊列的類型描述typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; / 隊頭指針QueuePtr rear; / 隊尾指針 LinkQueue;(b) 鏈?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;(c) 鏈?zhǔn)疥犃械某鲫犃胁僮?。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è)見實驗指導(dǎo)。單元名稱：第 七 講：串一、教學(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 = a1a2a3an (n0) 如：A= BEIJING， B= JING串的長度：串中字符的數(shù)目n ?？沾翰缓魏巫址拇?，串長度為0，空格串：僅由一個或多個空格組成的串，長度為串中空格字符的個數(shù)。如： ， C= BEI JING 子串：由串中任意個連續(xù)的字符組成的子序列。主串：包含子串的串。如：A= BEIJING B= JING 字符在串中的位置：字符在序列中的序號。子串在主串中的位置：以子串的第一個字符在主串中的位置來表示。如：A= BEIJING ，B= JING ，B在A中的位置為4。串相等：當(dāng)且僅當(dāng)兩個串的值相等。也就是說，只有兩個串的長度相等且各個對應(yīng)位置的字符都相等時才相等。（2）串的抽象數(shù)據(jù)類型定義：ADT String 數(shù)據(jù)對象：D ai |aiCharacterSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 | ai-1, ai 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)，是直接使用定長的字符數(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( )進(jìn)行串值空間的動態(tài)管理，為每一個新產(chǎn)生的串分配一個存儲區(qū)，稱串值共享的存儲空間為“堆”。C語言中的串以一個空字符為結(jié)束符，串長是一個隱含值。串堆分配存儲表示：typedef struct char *ch; / 若是非空串，則按串長分配存儲區(qū),否則ch為NULLint length; / 串長度 HString;這類串操作實現(xiàn)的算法為：先為新生成的串分配一個存儲空間，然后進(jìn)行串值的復(fù)制（以串的復(fù)制操作為例）。講解串堆分配的表示與實現(xiàn) （P76，77）4.2.3 塊鏈存儲表示 以鏈表存儲串值，除頭指針外還可以附設(shè)一個尾指針指示鏈表中的最后一個結(jié)點，并給出當(dāng)前串的長度。稱如此定義的傳存儲結(jié)構(gòu)為塊鏈結(jié)構(gòu)。#define CHU