第一章緒論
一概念
數據結構是一門研究程序設計中計算機操作的對象以及它們之間的關系和運算的一門學科
數據是描述額觀事物的數字符以及所有能輸入到計算機中被計算機程序加工處理的信息的集合
數據元素數據元素是數據的基本單位(一個數據項或多個數據項(域)數據項是數據的最小單位結點頂點記錄
數據對象是性質相同的數據元素的集合
數據結構研究是是數據元素之間抽象化的相互關系和這種關系在計算機中的存貯表示並對每種結構定義各自的運算設計出相應的算法而且經過運算後所得的新結構一般仍然是原來的結構類型
數據類型是指程序設計語言中各變量可取的數據種類
算法是執行特定計算的有窮過程特點
·動態有窮·確定性·輸入·輸出·可行性
第二章 線性表和數組
概念
一線性表是N個元素構成的有限序列
順序存貯結構地址計算插入刪除
鏈式存貯結構單鏈表查找插入刪除
循環鏈表
雙向鏈表
二數組
以行為主;
以列為主;計算地址
三棧是一種特殊的線性表這種表只能在固定的一端進行插入與刪除運算
隊列是另一種特殊的線性表刪除運算限定在表的一端進行而插入運算在另一端進行
第三章串
概念:是由N個字符組成的有限序列
存貯結構
順序表示法
緊縮格式 非緊縮格式 以單字節為單位的存貯方式
鏈式表示法
串名的存貯映象
第四章樹
一概念
樹是一個或多個結點的有窮集合T且滿足以下條件
有且僅有一個指定的稱作樹根的結點;
除根以外的其余結點被分成m個不相交的集合這些集合的每一個又都是樹並且稱為根的子樹
結點的度結點N的子樹數稱為結點的度
樹的度樹T中各結點的度的最大值稱的樹T的度
葉子樹中度為的結點稱為葉子(終端結點)
分枝結點樹中度不為的結點稱為分枝結點(非終端結點)
雙親和孩子若樹中結點P的一棵子樹的根是結點C則我們稱P是C的雙親或父母反之稱C是P的孩子
結點的層數樹的層數為其余任一結點的層數等於它的雙親的層數加
樹的深度樹中各結點的層數的最大值稱為T的深度(高度)
兄弟和堂兄弟同一雙親的孩子之間互稱為兄弟其雙親在同一層的結點互為堂兄弟
祖先和子孫一個點的祖先是指從樹的根到該結點所經分枝上的所有結點一個結點的子樹的所有結點都稱為該結點的子孫
有序樹和無序樹如果樹中結點各棵子樹規定從左至右是有次序的則稱樹為有序樹否則為無序樹
森林N棵互不相交的樹的集合稱為森林
二樹的存貯表示
雙親數組表示記錄型一維數組dataparent
孩子鏈表表示法
·多重鏈表表示法: datadegreelinklink…
·單鏈表表示法:datalikn
左孩子右兄弟鏈表示法lchilddatarsibling
三二叉樹
概念是有限個結點的集合它或者為空集或者是由一個根結點以及兩棵互不相交的且分別稱為根的左子樹和右子樹的二叉樹組成五種形態空根左右左右 性質
·位於二叉樹第I層上的結點最多為I;(I)=
·深度為K的二叉樹的結點總數最多為K(K)=
·N=N+
滿二叉樹一棵深度為K的具有K個結點的二叉樹
完全二叉樹在一棵二叉樹中若所有結點的度為或為的二叉樹
順序二叉樹如果深度為K的具有N個結點的二叉樹它的每一個結點都與深度為K的滿二叉樹中順序編號是到N的結點相對應的二叉樹
三二叉樹的存貯表示
順序存貯
鏈表表示lchilddatarchlid
遍歷
·前序根—左—右
·中序左—根—右
·後序左—右—根
四線索二叉樹
五樹的二叉樹表示森林與二叉樹的轉換
六路徑長度樹中一個結點到另一個結點之關的路徑由這兩個結點之間的分枝所構成路徑上的分枝數目稱為它的路徑長度
哈夫曼樹WPL哈夫曼碼
第五章圖
概念一個圖G由兩個集合V和E組成V是有限的非空頂點集E是用頂點對表示的邊集
無向圖有向圖;
鄰接關聯鄰接到(於)關聯於孤立頂點
頂點的度圖G中關聯於頂點V的邊的數目稱為V的度
所有頂點的度等於邊的兩倍
子圖
完全圖每對頂點之間都有一條邊相連的圖在有向圖中每對頂點之間都有兩條有向邊相互關聯的圖
在無向完全圖中邊的總數為Cn=n(n)/
在有向完全圖中邊的總數為Pn=n(n)
路徑由邊組成
回路
連通圖對於無向圖如果圖中任何兩頂點都是可達的則稱此圖為連能圖
對於有向圖如果圖中任何兩個頂點都是相互可達的則此有向圖是強連通的如果圖中任何兩頂點至少有一個頂點另一個頂點可達則稱此有向圖是單向連通的
強連通分量有向圖的最大強連通子圖稱為它的強連通分量 樹圖其本質特征是連通性和無圈性把不含圈的無向連通圖稱為樹圖
網絡是每條邊上帶有數量指標的連通圖
鄰接矩陣鄰接表
第六章 查找
查找就是確定一個已給的數據是否出現在某個數據表中
域(字段)組成記錄的每個數據項
關鍵字通常記錄中總存在某個或某組數據項它們的值能唯一標識一個記錄這個(組)數據項稱為關鍵字
方法順序
二分
線性插值
分區
二叉排序樹如果將記錄的鍵碼按二叉樹的結構來組織並且假定樹中任意非葉子結點的鍵碼大於其左子樹所有結點的鍵碼(若左子樹存在的話)而小於其右子樹所有結點的鍵碼(如右子樹存在的話)這樣的二叉樹叫二叉排序樹(二叉查找樹) 哈 希查找
哈希函數能把關鍵字映射成記錄存貯地址的函數
哈希表假定數組HT[··m]為存貯記錄的地址空間哈希函數H以每個記錄的關鍵字值K作為輸入產生一個落在[··m]內的整數H(K)並以它作為K所標識的記錄在表HT中的地址或索引號這樣產生的記錄表H(K)叫做 ··]
構造哈希函數的方法
直接定址法
除留余數法
平方取中法
折疊法與移位法
數字分析法
沖突處理
開放定址法 線性探測法 偽隨機探測法
鏈地址法
第七章排序
內部排序
外部排序
內部冒泡 選擇 插入 歸並 堆排序 快速排序 基數
堆每個非終端結點的關鍵字大於等於它的孩子結點的關鍵字
第八章文件
基本概念
From:http://tw.wingwit.com/Article/program/sjjg/201311/23397.html
