熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

自學考試《數據結構》復習指導-1

2013-11-15 15:22:11  來源: 數據結構 

    第一章緒論

  一概念

  數據結構是一門研究程序設計中計算機操作的對象以及它們之間的關系和運算的一門學科

  數據是描述額觀事物的數字符以及所有能輸入到計算機中被計算機程序加工處理的信息的集合

  數據元素數據元素是數據的基本單位(一個數據項或多個數據項(域)數據項是數據的最小單位結點頂點記錄

  數據對象是性質相同的數據元素的集合

  數據結構研究是是數據元素之間抽象化的相互關系和這種關系在計算機中的存貯表示並對每種結構定義各自的運算設計出相應的算法而且經過運算後所得的新結構一般仍然是原來的結構類型

  數據類型是指程序設計語言中各變量可取的數據種類

  算法是執行特定計算的有窮過程特點

  ·動態有窮·確定性·輸入·輸出·可行性

  第二章 線性表和數組

  概念

  一線性表是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哈夫曼碼

[] []


From:http://tw.wingwit.com/Article/program/sjjg/201311/23308.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.