【正文】 List Lb, SqList amp。e)。 ListDelete_Sq(SqList amp。ListInsert_Sq(SqList amp。InitList_Sq(SqList amp。}SqList。 int length。（4）線性表的動態(tài)分配順序存儲結(jié)構(gòu)。則線性表中第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)+(i1)*l，其中LOC(a1)為線性表的基地址。 線性表的順序表示和實現(xiàn)（1）線性表的順序表示：用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。抽象數(shù)據(jù)類型線性表的定義：講解定義中的數(shù)據(jù)對象，數(shù)據(jù)關(guān)系以及基本操作（教材P19），重點講解常用的基本操作含義。線性表的長度：線性表中元素的個數(shù)（n≥0），n=0為空表。 例如線性表（a1,…,ai1,ai,ai+1,…,an），稱ai1是ai的直接前驅(qū)元素， ai+1是 ai的直接后繼。其中每個數(shù)據(jù)元素的具體含義，在不同的情況下各不相同，但是同一線性表中的元素必定具有相同特性，即屬于同一數(shù)據(jù)對象。（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)。非順序映像的特點是借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。根據(jù)數(shù)據(jù)元素相互之間的關(guān)系在計算機中的表示形式將數(shù)據(jù)的物理結(jié)構(gòu)劃分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(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)部的表示形式。結(jié)構(gòu)定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。例 數(shù)據(jù)結(jié)構(gòu)graph={K，R}，其中K={01，02，03，04，05}，R={r}，r={01，02，02，01，01，04，04，01，01，03，03，01，02，04，04，02，03，05，05，03}。舉例講解：例 數(shù)據(jù)結(jié)構(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，08，08，09，09，10}。數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系還可以用圖形直觀地表示出來。K上任何一個二元關(guān)系Rj是序偶的集合。其中：是數(shù)據(jù)元素的有限集合，n為中數(shù)據(jù)元素的個數(shù)。介紹數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展以及與其他課程之間的關(guān)系。12計算機和人機對奕問題13多叉路口交通燈的管理問題總結(jié)：從以上三個例子可以看出，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如線性表、樹和圖等之類的數(shù)據(jù)結(jié)構(gòu)，這些都是數(shù)據(jù)結(jié)構(gòu)課程的研究對象。講授新課 什么是數(shù)據(jù)結(jié)構(gòu) 講解：（數(shù)據(jù)結(jié)構(gòu)課程的研究背景）從計算機最初以數(shù)值計算為主到大量非數(shù)值計算出現(xiàn)引出數(shù)據(jù)結(jié)構(gòu)。本課程主要講授線性表、棧和隊列、串、數(shù)組、樹和二叉樹、圖、查找、排序等內(nèi)容。難點：邏輯結(jié)構(gòu)與物理結(jié)構(gòu)之間的映像關(guān)系。三、課程教學(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ù)雜度的漸進表示法；教學(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) 《數(shù)據(jù)結(jié)構(gòu)》課程的體系結(jié)構(gòu)。主要介紹如何合理地組織數(shù)據(jù)、有效地存儲和處理數(shù)據(jù)，正確地設(shè)計算法以及對算法的分析和評價。通過本課程學(xué)習(xí)使學(xué)生對提高編寫程序的能力以及解決實際問題的能力。課程教案課程名稱： 數(shù)據(jù)結(jié)構(gòu) 授課教師：學(xué)習(xí)對象：任課時間：一、學(xué)生情況分析數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的一門核心專業(yè)課程。學(xué)生在前期的學(xué)習(xí)中已經(jīng)學(xué)習(xí)了C語言程序設(shè)計課程。二、課程教學(xué)目標(biāo)《數(shù)據(jù)結(jié)構(gòu)》是計算機學(xué)科中一門核心專業(yè)基礎(chǔ)課。通過本課程的學(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ǔ)。二、重點與難點重點：數(shù)據(jù)結(jié)構(gòu)的基本概念；邏輯結(jié)構(gòu)與物理結(jié)構(gòu)之間的映像關(guān)系。