【正文】 據(jù)元素的集合，另一個(gè)是關(guān)系的集合。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，也稱網(wǎng)狀結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。該結(jié)構(gòu)的數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、所含結(jié)點(diǎn)個(gè)數(shù)都無(wú)關(guān)。線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存取的存儲(chǔ)結(jié)構(gòu)。散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針類型來(lái)實(shí)現(xiàn)。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像）稱為數(shù)據(jù)的物理（存儲(chǔ)）結(jié)構(gòu)。線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)全稱為非線性結(jié)構(gòu)。（1）.分類：數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)。有些時(shí)候事情也會(huì)反過(guò)來(lái)，我們根據(jù)特定算法來(lái)選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通過(guò)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、基本算法和相關(guān)應(yīng)用問(wèn)題來(lái)介紹其基本知識(shí)和應(yīng)用知識(shí)。在軟件開(kāi)發(fā)過(guò)程中要求“高效地”組織數(shù)據(jù)和設(shè)計(jì)“好的”算法，并使算法用程序來(lái)實(shí)現(xiàn)，通過(guò)調(diào)試而成為軟件，必須具備數(shù)據(jù)結(jié)構(gòu)領(lǐng)域和算法設(shè)計(jì)領(lǐng)域的專門知識(shí)。附錄二開(kāi)發(fā)步驟、目的； ；； ； 、上機(jī)調(diào)試； 、評(píng)價(jià)。成績(jī)分為優(yōu)、良、中、及格和不及格五等。五、考核方法學(xué)習(xí)成績(jī)的評(píng)定方式：考查。（鼓勵(lì)學(xué)生創(chuàng)新。：按照軟件開(kāi)發(fā)規(guī)范的要求書(shū)寫(xiě)設(shè)計(jì)報(bào)告（參見(jiàn)附錄三報(bào)告書(shū)寫(xiě)格式）；要求報(bào)告層次結(jié)構(gòu)清晰、圖表完整、語(yǔ)言通順、字跡工整。：指導(dǎo)教師擬定（參考題目見(jiàn)附錄1）：指導(dǎo)教師擬定設(shè)計(jì)題目，學(xué)生研究具體問(wèn)題、進(jìn)行需求分析、選擇合適的數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法、編寫(xiě)并調(diào)試代碼、書(shū)寫(xiě)文檔材料、提交設(shè)計(jì)報(bào)告，最后，由指導(dǎo)教師驗(yàn)收并評(píng)定成績(jī)。四、教學(xué)內(nèi)容：應(yīng)用所掌握的線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問(wèn)題。、勤奮工作、勇于創(chuàng)新、勇于探索、勇于實(shí)踐，虛心向指導(dǎo)教師請(qǐng)教，向同學(xué)學(xué)習(xí)，獨(dú)立完成設(shè)計(jì)任務(wù)。三、基本要求、設(shè)計(jì)、上機(jī)實(shí)現(xiàn)等諸環(huán)節(jié)上投入精力，加強(qiáng)指導(dǎo)、討論和答疑的力度。1．學(xué)生通過(guò)實(shí)踐掌握線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)； 2．培養(yǎng)學(xué)生利用數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問(wèn)題的能力。通過(guò)這個(gè)實(shí)驗(yàn)，培養(yǎng)學(xué)生綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和程序設(shè)計(jì)基本知識(shí)，解決實(shí)際問(wèn)題，提高程序設(shè)計(jì)的能力和團(tuán)隊(duì)協(xié)作精神。主要參考書(shū)：[1]《數(shù)據(jù)結(jié)構(gòu)與算法教程》鄒永林 周蓓 唐曉陽(yáng) 楊劍勇 編著 機(jī)械工業(yè)出版社[2]《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》(含CD)嚴(yán)蔚敏 吳為民 編著 清華大學(xué)出版社[3]《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語(yǔ)言版)》嚴(yán)蔚敏 編著 清華大學(xué)出版社[4]《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)》張世和 編著 清華大學(xué)出版社第三篇：《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)大綱（Data Structures amp。本課強(qiáng)調(diào)能力的培養(yǎng)，期末采用半開(kāi)卷考試(允許同學(xué)攜帶一頁(yè)A4紙的總結(jié)資料)。上機(jī)訓(xùn)練由平時(shí)的上機(jī)訓(xùn)練和小學(xué)期的實(shí)訓(xùn)課程設(shè)計(jì)兩部分組成。五、大綱說(shuō)明課堂講述的論題只是核心或有特色的知識(shí)內(nèi)容，還有相當(dāng)數(shù)量的篇章內(nèi)容留給學(xué)生自學(xué)，所確定的自學(xué)部分內(nèi)容亦屬考查范圍。查找(3學(xué)時(shí))實(shí)驗(yàn)九 順序查找 實(shí)驗(yàn)十 折半查找 實(shí)驗(yàn)十一 哈希表的應(yīng)用 實(shí)驗(yàn)十二 二叉排序樹(shù)的綜合練習(xí)要求：了解查找的基本思想及查找成功和不成功的概念；掌握在順序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長(zhǎng)度；理解并掌握二叉排序樹(shù)，平衡二叉樹(shù)B樹(shù)的各種算法。深刻理解二叉樹(shù)的定義，性質(zhì)及其存儲(chǔ)方法；熟練掌握二叉樹(shù)的二叉鏈表存儲(chǔ)方式，結(jié)點(diǎn)結(jié)構(gòu)和類型定義；理解并掌握二叉樹(shù)的三種遍歷算法；掌握二叉樹(shù)的線索化方法；靈活運(yùn)用二叉樹(shù)的遍歷方法解決相關(guān)的應(yīng)用問(wèn)題。數(shù)組和廣義表()實(shí)驗(yàn)六 稀疏矩陣的應(yīng)用要求：理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式；理解并掌握矩陣和特殊矩陣元素在存儲(chǔ)區(qū)中地址的計(jì)算；領(lǐng)會(huì)稀疏矩陣的壓縮方式和簡(jiǎn)單運(yùn)算；了解廣義表的定義和基本運(yùn)算。隊(duì)列()實(shí)驗(yàn)四 隊(duì)列的應(yīng)用要求：理解隊(duì)列的定義，特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。四、實(shí)驗(yàn)教學(xué)內(nèi)容的基本要求及學(xué)時(shí)分配線性表(1學(xué)時(shí))實(shí)驗(yàn)一 順序表的應(yīng)用 實(shí)驗(yàn)二 鏈表的應(yīng)用要求：理解線性表的定義及其運(yùn)算；理解順序表和鏈表的定義，組織形式，結(jié)構(gòu)特征和類型說(shuō)明；掌握在這兩種表上實(shí)現(xiàn)的插入，刪除和按值查找的算法；了解循環(huán)鏈表，雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入，刪除等操作。重點(diǎn)和難點(diǎn)：本章重點(diǎn)在于了解各種文件的結(jié)構(gòu)特點(diǎn)及其適用場(chǎng)合。知識(shí)點(diǎn)：排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、2路歸并排序、基數(shù)排序、排序方法的綜合比較。按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類：O(n2)的簡(jiǎn)單排序方法，O(n*logn)的高效排序方法和O(d*n)的基數(shù)排序方法；(3)理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。排序方法有不同的分類方法，基于“關(guān)鍵字間的比較”進(jìn)行排序的方法可以按排序過(guò)程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計(jì)數(shù)排序等五類；(2)掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。知識(shí)點(diǎn)：順序表、有序表、索引順序表、靜態(tài)查找樹(shù)、二叉查找樹(shù)、二叉平衡樹(shù)、哈希表。查找(6學(xué)時(shí))學(xué)習(xí)目標(biāo)：(1)理解“查找表”的結(jié)構(gòu)特點(diǎn)以及各種表示方法的適用性；(2)熟練掌握以順序表或有序表表示靜態(tài)查找表時(shí)的查找方法；(3)熟悉靜態(tài)查找樹(shù)的構(gòu)造方法和查找算法，理解靜態(tài)查找樹(shù)和折半查找的關(guān)系；(4)熟練掌握二叉查找樹(shù)的構(gòu)造和查找方法；(5)理解二叉平衡樹(shù)的構(gòu)造過(guò)程；(6)熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別；(7)掌握描述查找過(guò)程的判定樹(shù)的構(gòu)造方法，以及按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。重點(diǎn)和難點(diǎn)：圖的應(yīng)用極為廣泛，而且圖的各種應(yīng)用問(wèn)題的算法都比較經(jīng)典，因此本章重點(diǎn)在于理解各種圖的算法及其應(yīng)用場(chǎng)合。知識(shí)點(diǎn)：樹(shù)的類型定義、二叉樹(shù)的類型定義、二叉樹(shù)的存儲(chǔ)表示、二叉樹(shù)的遍歷以及其它操作的實(shí)現(xiàn)、線索二叉樹(shù)、樹(shù)和森林的存儲(chǔ)表示、樹(shù)和森林的遍歷以及其它操作的實(shí)現(xiàn)、最優(yōu)樹(shù)和赫夫曼編碼。樹(shù)和二叉樹(shù)(8學(xué)時(shí))學(xué)習(xí)目標(biāo)：(1)領(lǐng)會(huì)樹(shù)和二叉樹(shù)的類型定義，理解樹(shù)和二叉樹(shù)的結(jié)構(gòu)差別；(2)熟記二叉樹(shù)的主要特性，并掌握它們的證明方法；(3)熟練掌握二叉樹(shù)的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其它操作；(4)理解二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法；(5)熟練掌握二叉樹(shù)和樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法；(6)學(xué)會(huì)編寫(xiě)實(shí)現(xiàn)樹(shù)的各種操作的算法；(7)了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和赫夫曼編碼的方法。重點(diǎn)和難點(diǎn)：本章重點(diǎn)是學(xué)習(xí)數(shù)組類型的定義及其存儲(chǔ)表示。知識(shí)點(diǎn)：串的類型定義、串的存儲(chǔ)表示、串匹配、KMP算法。重點(diǎn)和難點(diǎn)：相對(duì)于其它各個(gè)知識(shí)點(diǎn)而言，本章非整個(gè)課程的重點(diǎn)，鑒于串已是多數(shù)高級(jí)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型，因此本章重點(diǎn)僅在于了解串類型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法，并學(xué)會(huì)利用這些基本操作來(lái)實(shí)現(xiàn)串的其它操作。知識(shí)點(diǎn)：順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列。棧和隊(duì)列(4學(xué)時(shí))學(xué)習(xí)目標(biāo)：(1)掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們；(2)熟練掌握棧類型的兩種實(shí)現(xiàn)方法；(3)熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法；(4)理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針 p 和結(jié)點(diǎn) *p 之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表；(2)熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；(3)