【文章內(nèi)容簡(jiǎn)介】 點(diǎn)的第一條弧指針 }VNode,AdjList[MAX_VERTEX_NUM]。 typedef struct //鄰接表圖 { AdjList vertices。 int vexnum,arum。}ALGraph。 typedef struct ArcCell { int adj。}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。typedef struct { int vexs[MAX_VERTEX_NUM]。AdjMatrix arcs。int vexnum,arum。}MGraph。//鄰接矩陣圖的定義 Boolean visited[MAX_VERTEX_NUM]。//訪(fǎng)問(wèn)數(shù)組 void CreateALGraph(ALGraph *G) //創(chuàng)建圖 { ArcNode *s。 int i,j,k。 cout //對(duì)于有向圖指弧的數(shù)目，對(duì)無(wú)向圖邊數(shù)為弧的 2倍 cinGvexnumGarum。 coutvexnum for(i=0。ivexnum。i++) { cinGvertices[i].data。 Gvertices[i].firstarc =NULL。 } coutarum for(k=0。karum。k++) { cout cinij。 s=(ArcNode *)new ArcNode。 sadjvex =j1。 snextarc =Gvertices [i1].firstarc。 Gvertices[i1].firstarc =s。 } } void BFS(ALGraph *G,int k) //寬度優(yōu)先搜索 { for(int v=0。vvexnum。v++) visited[v]=FALSE。ArcNode *p。int i,Q[MAX_VERTEX_NUM],front,rear。front=rear=0。coutvertices[k].data。visited[k]=TRUE。Q[rear]=k。rear=(rear+1)%MAX。 while(front!=rear){ i=Q[front]。 front=(front+1)%MAX。 p=Gvertices[i].firstarc。 while(p) { if(!visited[padjvex]) { coutvertices [padjvex ].data。 visited[padjvex]=TRUE。 Q[rear]=padjvex。 rear=(rear+1)%MAX。 } p=pnextarc。 } } } void DFS(ALGraph *G,int v)。 void DFSTraverse(ALGraph *G)//深度優(yōu)先搜索 { int i。 for(i=0。ivexnum。i++) visited[i]=FALSE。cout for(i=0。ivexnum。i++) if(!visited[i])DFS(G,i)。} void DFS(ALGraph *G,int v){ coutvertices[v].data。 visited[v]=TRUE。 ArcNode *p。 p=Gvertices[v].firstarc。 while(p) { if(!visited[padjvex])DFS(G,padjvex)。 p=pnextarc。 } } void change(ALGraph G,MGraph M){ =。 =。 int i,j。 ArcNode *p。 for(i=0。i for(j=0。j [i][j].adj =0。 for(i=0。i { p=[i].firstarc。 while(p) { j=padjvex。 [i][j].adj=1。 p=pnextarc。 } } } void printMGraph(MGraph G){ int i,j。cout for(j=0。j {cout ”。 if((1+j)% ==0) cout printMGraph()。void main(){ ALGraph G。MGraph M。int v。CreateALGraph(G)。for(v=0。v if(!visited[v]) BFS(G,v)。 cout DFSTraverse(G)。cout 3 實(shí)驗(yàn)要求 按要求編寫(xiě)實(shí)驗(yàn)程序，將實(shí)驗(yàn)程序上機(jī)調(diào)試運(yùn)行，并提交實(shí)驗(yàn)報(bào)告。 第二篇：數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱 《數(shù)據(jù)結(jié)構(gòu)與算法》教學(xué)大綱 課程編號(hào)： 030816 適用專(zhuān)業(yè)：教育技術(shù)學(xué) 總學(xué)時(shí)數(shù)： 64 學(xué) 分： 4 編制單位：茂名學(xué)院理學(xué)院教育與信息技術(shù)系 編制時(shí)間： 2024年 6月 20 日 一、課程地位、性質(zhì)和任務(wù) 《數(shù)據(jù)結(jié)構(gòu)與算法》課程是計(jì)算機(jī)相關(guān)學(xué)科專(zhuān)業(yè)的基礎(chǔ)課程中的一門(mén)重要的核心課程。通過(guò)本課程的教學(xué)，使學(xué)生知道求解非數(shù)值類(lèi)問(wèn)題的基本模型（表、樹(shù)、圖），模型的特點(diǎn)和適用場(chǎng)合，能夠根據(jù)問(wèn)題設(shè)計(jì)和選擇好的算法，為學(xué)習(xí)后續(xù)的操作系統(tǒng)、編譯原理和軟件工程等專(zhuān)業(yè)課程，設(shè)計(jì)應(yīng)用程序打下基礎(chǔ)。 本課程以提高學(xué)生的計(jì)算機(jī)應(yīng)用能力和綜合素質(zhì)為目標(biāo)，通過(guò)課程教學(xué)，為學(xué)生構(gòu)建數(shù)據(jù)結(jié)構(gòu)與算 法方面的知識(shí)體系，使學(xué)生一方面能夠根據(jù)問(wèn)題選擇合適的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)高效的算法，提高程序設(shè)計(jì)能力，另一方面，在工程應(yīng)用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個(gè)方面，提高學(xué)生的程序設(shè)計(jì)能力。 二、與其他課程的關(guān)系 先修課：程序設(shè)計(jì)基礎(chǔ)、離散數(shù)學(xué)、計(jì)算機(jī)組成原理、計(jì)算機(jī)文化基礎(chǔ) 三、教學(xué)內(nèi)容、課時(shí)安排和基本要求 （一）教學(xué)部分 第 1章 緒論（ 2學(xué)時(shí)） 基本概念和術(shù)語(yǔ) 抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn) 算法和算法分析（算法及其設(shè)計(jì)的要求，算法效率的度量，算法的存 儲(chǔ)空間需求） 問(wèn)題求解 基本要求： 了解：抽象數(shù)據(jù)類(lèi)型，算法設(shè)計(jì)方法與算法分析。 掌握：數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)、算法的基本概念；問(wèn)題求解的方法與步驟 重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)和算法的概念，算法的描述形式和評(píng)價(jià)方法，問(wèn)題求解的一般步驟 難點(diǎn)：評(píng)價(jià)算法的標(biāo)準(zhǔn)和評(píng)價(jià)方法，最壞情況和平均情況的區(qū)分。 第 2章 線(xiàn)性表（ 8學(xué)時(shí)） 線(xiàn)性表的類(lèi)型定義 線(xiàn)性表的順序表示和實(shí)現(xiàn) 線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（線(xiàn)性鏈表，循環(huán)鏈表，雙向鏈表） 一元多項(xiàng)式的表示及相加 基本要求： 了解：兩種存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ) 結(jié)構(gòu)）及一元多項(xiàng)式的表示及相加。 掌握：要求熟練掌握處理線(xiàn)性表的各種算法。為后繼章節(jié)的學(xué)習(xí)打基礎(chǔ)。重點(diǎn)：各種算法。難點(diǎn)：鏈表的理解。 第 3章 棧與隊(duì)列（ 4學(xué)時(shí)） 棧（定義，棧的表示和實(shí)現(xiàn)） 棧的應(yīng)用舉例（數(shù)制轉(zhuǎn)換，括號(hào)匹配的檢驗(yàn)，行編輯程序，迷宮求解，表達(dá)式求值） 棧與遞歸的實(shí)現(xiàn) 隊(duì)列及其實(shí)現(xiàn)（定義，鏈隊(duì)列，循環(huán)隊(duì)列） *離散事件模擬 教學(xué)要求：熟練掌握棧和隊(duì)列的特性和在不同存儲(chǔ)結(jié)構(gòu)前提下的算法實(shí)現(xiàn)。棧和隊(duì)列是表最基本和重要的數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)。 基本要求： 了解： 棧和隊(duì)列的定義及其實(shí)現(xiàn)。 掌握： 熟練掌握棧和隊(duì)列的特性和在不同存儲(chǔ)結(jié)構(gòu)前提下的算法實(shí)現(xiàn)。重點(diǎn)： 棧和隊(duì)列的算法實(shí)現(xiàn)。難點(diǎn)： 棧和隊(duì)列的算法實(shí)現(xiàn)。 第 4章 串（ 2學(xué)時(shí)） 串類(lèi)型的定義 串的表示和實(shí)現(xiàn)（定長(zhǎng)順序存儲(chǔ)，堆分配存儲(chǔ)，串的塊鏈存儲(chǔ)） 串的模式匹配算法（求子串位置的定位函數(shù)，模式匹配的一種改進(jìn)算法） 串操作應(yīng)用舉例（文本編輯，建立詞索引表） 基本要求： 了解：串的基本概念及主要操作和運(yùn)算。掌握：掌握串的基本概念和運(yùn)算。重點(diǎn)：主要操作和運(yùn)算。難點(diǎn)：模式匹配及串的應(yīng)用。 第 5章 數(shù)組（ 2學(xué)時(shí)） 數(shù)組的定義 數(shù)組的順序表示和實(shí)現(xiàn) 矩陣的壓縮存儲(chǔ)（特殊矩陣，稀疏矩陣） 廣義表的定義 廣義表的存儲(chǔ)結(jié)構(gòu) m元多項(xiàng)式的表示 廣義表的遞歸算法（求廣義表的深度，復(fù)制廣義表，建立廣義表的存儲(chǔ)結(jié)構(gòu)） 基本要求： 了解：了解作為抽象數(shù)據(jù)類(lèi)型的數(shù)組和 C語(yǔ)言的數(shù)組。認(rèn)識(shí)到數(shù)組可以作為順序存儲(chǔ)結(jié)構(gòu)用于順序表、字符串和稀疏矩陣的實(shí)現(xiàn)。也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 掌握：掌握基本概念和算法。重點(diǎn)：算法。 難點(diǎn)：廣義表的遞歸算法。 第 6章 樹(shù)與二叉樹(shù)（ 15學(xué)時(shí)） 樹(shù)的定義和基本術(shù)語(yǔ) 二叉樹(shù)（二叉樹(shù)的定義，二叉樹(shù)的性質(zhì)，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)） 遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)（遍歷二叉樹(shù)，線(xiàn)索二叉樹(shù)） 樹(shù)和森林（樹(shù)的存儲(chǔ)結(jié)構(gòu)，森林與二叉樹(shù)的轉(zhuǎn)換，樹(shù)和森林的遍歷） 樹(shù)與等價(jià)問(wèn)題 赫夫曼樹(shù)及其應(yīng)用（最優(yōu)二叉樹(shù)（赫夫曼樹(shù)），赫夫曼編碼） 回溯法與樹(shù)的遍歷 樹(shù)的計(jì)數(shù) 基本要求： 了解：理解樹(shù)與森林的定義與術(shù)語(yǔ)。 掌握：熟練掌握二叉樹(shù)性質(zhì)和遍歷算法，掌握樹(shù)與森林的孩子兄弟存儲(chǔ)表示和遍歷。掌握哈夫曼樹(shù)構(gòu)造的方法和算法。重點(diǎn)： 樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷算法。難點(diǎn)：哈夫曼樹(shù)構(gòu)造的方法和算法 第 7章 圖（ 11學(xué)時(shí)） 圖的定義和術(shù)語(yǔ) 圖的存儲(chǔ)結(jié)構(gòu)（數(shù)組表示法，鄰接表，十字鏈表，鄰接多重表） 圖的遍歷（深度優(yōu)先搜索，廣度優(yōu)先搜索） 圖的連通性問(wèn)題（無(wú)向圖的連通分量和生成樹(shù)，有向圖的強(qiáng)連通分量，最小生成樹(shù)，關(guān)節(jié)點(diǎn)和重連通分量） 有向無(wú)環(huán)圖及其應(yīng)用（拓?fù)渑判?，關(guān)鍵路徑） 最短路徑（從某個(gè)源點(diǎn)到其 余各項(xiàng)點(diǎn)的最短路徑，每一對(duì)頂點(diǎn)之間的最短路徑）基本要求： 了解：圖的基本概念和相關(guān)術(shù)語(yǔ)。 掌握：圖的兩種主要存儲(chǔ)結(jié)構(gòu)及遍歷算法。掌握最小生成樹(shù)、最短路徑和活動(dòng)網(wǎng)算法的思想。 重點(diǎn)：圖的兩種主要存儲(chǔ)結(jié)構(gòu)及遍歷算法。難點(diǎn)：圖的遍歷算法，最短路徑算法。 第 8章 查找（ 8學(xué)時(shí)） 靜態(tài)查找表（順序表，有序表，靜態(tài)樹(shù)表，索引順序表） 動(dòng)態(tài)查找表（二叉排序樹(shù)和平衡二叉樹(shù)， B_樹(shù)和 B+樹(shù)，鍵樹(shù)） 哈希表（定義，構(gòu)造方法，處理沖突的方法，查找及其分析） 基本要求： 了解： 各種查找法的基本概念及實(shí)現(xiàn)的基本 思想。 掌握：熟練掌握搜索結(jié)構(gòu)的折半查找、二叉搜索樹(shù)、平衡二叉樹(shù)主要搜索算法。掌握哈希表查找算法。重點(diǎn)：各種算法的基本思想及實(shí)現(xiàn)。難點(diǎn)：哈希表查找算法。 第 9章 內(nèi)部排序（ 8學(xué)時(shí)） 概述 插入排序（直接插入，其他插入，希爾） 交換排序（冒泡排序、快速排序） 選擇排序（簡(jiǎn)單，樹(shù)形，堆） 歸并排序 基數(shù)排序（多關(guān)鍵字，鏈?zhǔn)剑? 排序算法分析 基本要求： 了解：基數(shù)排序，排序算法分析方法 掌握：排序的基本概念，插入排序，交換排序，選擇排序，歸并排序重點(diǎn)：內(nèi) 部排序算法 難點(diǎn)：基數(shù)排序（多關(guān)鍵字，鏈?zhǔn)剑? 第 10章 *外部排序（ 2學(xué)時(shí)） 外存信息的存取 外部排序的方法 多路平衡歸并的實(shí)現(xiàn) 置換 選擇排序 最佳歸并樹(shù) 基本要求： 了解：外部排序的基本概念和相關(guān)術(shù)語(yǔ)。 掌握：基本掌握外排算法的基本思想，不同排序方法的比較。重點(diǎn)：外部排序算法 難點(diǎn)：多路平衡歸并的實(shí)現(xiàn) 第 11章 算法設(shè)計(jì)的一般方法（ 2學(xué)時(shí)） 1．重點(diǎn) （ 1）有效算法的概念，問(wèn)題固有難度的概念； （ 2）遞歸法；分治法；平衡原則；貪心法；動(dòng)態(tài)規(guī)劃的基本原理；（ 3）搜索 回溯法的基本原理和本質(zhì) .2．難點(diǎn) （ 1）問(wèn)題固有難度的概念； （ 2）遞歸分治法的效率分析（寫(xiě)出時(shí)間耗費(fèi)的遞推式，并求解）；（ 3）動(dòng)態(tài)規(guī)劃法中的狀態(tài)轉(zhuǎn)移方程的確定。 （二）實(shí)驗(yàn)、實(shí)習(xí)部分 課程安排五個(gè)類(lèi)別的實(shí)驗(yàn)，實(shí)驗(yàn)時(shí)數(shù)為 12 課時(shí)，其中： 實(shí)驗(yàn) 一、線(xiàn)性鏈表及運(yùn)算 2課時(shí) 實(shí)驗(yàn) 二、棧和隊(duì)列 2課時(shí) 實(shí)驗(yàn) 三、樹(shù)和二叉樹(shù) 4課時(shí) 實(shí)驗(yàn) 四、圖及其應(yīng)用 2課時(shí) 實(shí)驗(yàn) 五、查找與排序 2課時(shí) 四、課程考核方式 閉卷考試 70%、平時(shí)作業(yè)與實(shí)驗(yàn) 30% 五、建議教材和教學(xué)參考書(shū) 參考教材： 《數(shù)據(jù)結(jié)構(gòu)》（ C語(yǔ)言描述）高等教育出版社 耿國(guó)華主編 《數(shù)據(jù)結(jié)構(gòu)》（ C語(yǔ)言版）清華大學(xué)出版社 嚴(yán)蔚敏，吳偉民編者 《數(shù)據(jù)結(jié)構(gòu)題集》（ C語(yǔ)言版）清華大學(xué)出版社 嚴(yán)蔚敏，吳偉民編者 《數(shù)據(jù)結(jié)構(gòu)》算法實(shí)現(xiàn)及解析（第二版）西安電子科技大學(xué)出版社 高一凡 六、說(shuō)明 因課時(shí)安排少，教學(xué)內(nèi)容多。建議采用多媒體教學(xué)。 由于本課程內(nèi)容較多，在實(shí)際教學(xué)中可根據(jù)大綱內(nèi)容，進(jìn)行適當(dāng)調(diào)整。 第三篇：數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱 中央廣播電視大學(xué) “ 開(kāi)放教育試點(diǎn) ” 計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)（本科） 《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱 第一部 分 大綱說(shuō)明 一、課程的性質(zhì)和任務(wù) 《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)本科生的一門(mén)必修課程。本課程介紹如何組織各種數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)、傳遞和轉(zhuǎn)換。內(nèi)容包括：數(shù)組、鏈接表、棧和隊(duì)列、遞歸、樹(shù)與森林、圖、堆與優(yōu)先級(jí)隊(duì)列、集合與搜索結(jié)構(gòu)、排序、索引與散列結(jié)構(gòu)等。課程采用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)技術(shù)，并以兼有面向過(guò)程和面向?qū)ο箅p重特色的 C++語(yǔ)言作為算法的描述工具，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和面向?qū)ο蟪绦蛟O(shè)計(jì)基本能力的雙基訓(xùn)練。為后續(xù)計(jì)算機(jī)專(zhuān)業(yè)課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。 二、先修課要求 面向?qū)ο蟪绦蛟O(shè)計(jì)、計(jì)算機(jī)數(shù)學(xué) (離散數(shù)學(xué) )。 三、課程的教學(xué)基本要求 掌握重要數(shù)據(jù)結(jié)構(gòu)的概念、使用方法及實(shí)現(xiàn)技術(shù)；