數(shù)據(jù)結構期末復習提綱

數(shù)據(jù)結構課程總結數(shù)據(jù)結構課程總結課程目的與任務：系統(tǒng)地介紹軟件設計中常用的幾種數(shù)據(jù)結構和相應的存儲結構和算法及分析方法，以及常用的幾種查找和排序算法。學習組織、處理數(shù)據(jù)的理論和方法，建立良好的編程風格，進一個培養(yǎng)數(shù)據(jù)的抽象能力通過該課程的學習，為后續(xù)課程的學習以及軟件設計水平的提高打下良好基礎。2考試形式考試形式課堂考勤-----------------------10%實驗程序檢查情況-----------10%實驗報告-----------------------10%期末考試-----------------------70%單項選擇題 （20分）判斷題 （10分）簡答題 （36分）算法閱讀題 （20分）算法設計題 （14分）3緒論邏輯結構存儲結構線性結構非線性結構

線性表棧隊列串數(shù)組廣義表樹、二叉樹、森林圖順序存儲結構鏈式存儲結構索引存儲結構散列存儲結構數(shù)據(jù)結構算法算法的基本特征算法分析針對數(shù)據(jù)結構的各種基本算法及應用計算機科學領域兩大核心課題4線性表線性表順序表鏈表線性鏈表（單鏈表）單循環(huán)鏈表雙向鏈表雙向循環(huán)鏈表邏輯結構存儲結構及特點基本操作（算法)及分析建立遍歷插入刪除查找合并(a1,a2,…,an)5棧棧順序棧鏈棧初始化空棧入棧出棧取棧頂判?？誥n……a2a1棧底棧頂入棧出棧邏輯結構存儲結構基本操作（算法）典型應用數(shù)制轉(zhuǎn)換表達式求值棧與遞歸（函數(shù)調(diào)用）語法檢查6隊列

隊列鏈隊列順序隊列（循環(huán)隊列）初始化隊列入隊出隊取隊頭判隊空、滿邏輯結構存儲結構及特點基本操作（算法）典型應用作業(yè)調(diào)度離散事件模擬……隊頭隊尾入隊列出隊列anan-1…a3a2a17串s=＂a1a2……..an＂串邏輯結構存儲結構基本操作(運算)串的比較串的連接求子串子串定位（模式匹配）BF算法KMP算法順序存儲結構鏈式存儲結構定長順序存儲（靜態(tài)）堆分配存儲（動態(tài)）塊鏈結構單字符結點鏈8數(shù)組數(shù)組行優(yōu)先（行主序）列優(yōu)先（列主序）數(shù)組的定義和基本操作數(shù)組的順序表示矩陣的壓縮存儲及運算特殊矩陣稀疏矩陣對稱矩陣三角矩陣對角矩陣三元組順序表帶行邏輯鏈接的順序表十字鏈表9廣義表廣義表表的長度表的深度非空表的表頭和表尾定義

基本操作存儲結構（鏈式存儲）（a1,a2,a3,…,an

）10樹、二叉樹、森林1.定義和性質(zhì)2.存儲結構3.遍歷4.線索化順序結構鏈式結構二叉鏈表三叉鏈表先序線索樹中序線索樹后序線索樹樹二叉樹森林Huffman編/譯碼先序遍歷中序遍歷遍歷存儲結構遍歷孩子--兄弟先根遍歷后根遍歷線索二叉樹Huffman樹應用中序遍歷后序遍歷先序遍歷層次遍歷11圖存儲結構遍歷鄰接矩陣鄰接表十字鏈表鄰接多重表深度優(yōu)先搜索廣度優(yōu)先搜索無向圖的應用應用圖的連通分量圖的生成樹最小生成樹Prim算法Kruskal算法最短路徑Dijkstra算法Floyd算法有向圖的應用拓撲排序(AOV網(wǎng))關鍵路徑問題(AOE網(wǎng))圖12查找比較式查找法計算式查找法基于線性表的查找法（靜態(tài)查找）基于樹的查找法（動態(tài)查找）(HASH查找法)順序查找法折半查找法分塊查找法二叉排序樹

平衡二叉樹哈希函數(shù)構造方法哈希沖突解決方法哈希查找過程及性能分析直接定址法數(shù)字分析法平方取中法

除留余數(shù)法折疊法開放定址法再哈希法鏈地址法公共溢出區(qū)線性探測再散列二次探測再散列13排序基本概念排序的分類排序算法的分析時間復雜