版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
常用數(shù)據(jù)結(jié)構(gòu)及其存儲第一頁,共二十七頁,2022年,8月28日[主要內(nèi)容]21.1算法21.2數(shù)據(jù)結(jié)構(gòu)的基本概念21.3線性表21.4棧與隊列21.5樹與二叉樹第二頁,共二十七頁,2022年,8月28日21.1算法
定義:是對特定問題求解步驟的一種描述?;蛘哒f,是為求解某問題的方法和步驟。
特征:有窮性確定性有效性零個或多個輸入一個或多個輸出第三頁,共二十七頁,2022年,8月28日例如:一元二次方程求根算法。鍵盤輸入系數(shù)送到a,b,c中start計算出兩個根放在x1、x2中顯示x1、x2中存放的數(shù)據(jù)end第四頁,共二十七頁,2022年,8月28日算法復(fù)雜度評價一個算法優(yōu)劣的主要標(biāo)準(zhǔn)是:算法的執(zhí)行效率與存儲需求
算法的效率:指的是時間復(fù)雜度(TimeComplexity)
存儲需求:指的是空間復(fù)雜度(SpaceComplexity)
一般情況下,算法中的基本操作重復(fù)操作執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間復(fù)雜度記做:T(n)=O(f(n))第五頁,共二十七頁,2022年,8月28日21.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù):
是描述客觀事物的數(shù)、字符以及所有能輸入到計算機(jī)中并被計算機(jī)程序加工處理的符號的集合。
數(shù)據(jù)元素:
是數(shù)據(jù)的基本元素,即數(shù)據(jù)集合中的個體。
數(shù)據(jù)項:
具有獨(dú)立意義的最小數(shù)據(jù)單位。
數(shù)據(jù)對象:
具有相同特性的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。
數(shù)據(jù)結(jié)構(gòu):互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。
第六頁,共二十七頁,2022年,8月28日數(shù)據(jù)的邏輯結(jié)構(gòu)
集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀或網(wǎng)狀結(jié)構(gòu)第七頁,共二十七頁,2022年,8月28日數(shù)據(jù)的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)主要特點(diǎn):所有元素所占的存儲空間是連續(xù)的;各個元素在存儲空間中是按邏輯順序依次存放的;元素可隨機(jī)存取,但插入、刪除運(yùn)算不便,會引起大量結(jié)點(diǎn)的移動。第八頁,共二十七頁,2022年,8月28日二、鏈?zhǔn)酱鎯Y(jié)構(gòu)主要特點(diǎn):存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù);各結(jié)點(diǎn)的存儲順序與元素之間的邏輯關(guān)系可以不一致,元素之間的邏輯關(guān)系由指針域來確定;插入、刪除操作靈活方便,不必移動結(jié)點(diǎn),只要改變結(jié)點(diǎn)中的指針值即可。
第九頁,共二十七頁,2022年,8月28日數(shù)據(jù)的運(yùn)算
檢索:在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的結(jié)點(diǎn)
插入:往數(shù)據(jù)結(jié)構(gòu)里增加新的結(jié)點(diǎn)
刪除:把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)里去掉
更新:修改指定結(jié)點(diǎn)的一個或多個域的值
排序:保持線性結(jié)構(gòu)的結(jié)點(diǎn)序列里結(jié)點(diǎn)數(shù)不變,將結(jié)點(diǎn)按某種指定的順序重新排列第十頁,共二十七頁,2022年,8月28日21.3線性表線性表是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列。
(a1,a2,…,an)
順序表:指用順序存儲結(jié)構(gòu)存儲的線性表。
鏈表:用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表。
棧和隊列:是對線性表的插入、刪除運(yùn)算可以發(fā)生的位置加以限制的兩種特殊的線性表。第十一頁,共二十七頁,2022年,8月28日順序表
各種高級語言里的一維數(shù)組就是用順序方式存儲的線性表,因此常用一維數(shù)組稱呼順序表。若順序表中結(jié)點(diǎn)個數(shù)為n,則:
插入一個結(jié)點(diǎn)平均需要移動之結(jié)點(diǎn)個數(shù)為
n/2,算法的時間復(fù)雜度是O(n);
刪除一個結(jié)點(diǎn)平均需移動結(jié)點(diǎn)個數(shù)為
(n-1)/2,算法的時間復(fù)雜度是O(n)。第十二頁,共二十七頁,2022年,8月28日鏈表
線性鏈表(單鏈表):刪除算法的時間復(fù)雜度為O(n),其主要執(zhí)行時間是搜索刪除位置。
循環(huán)鏈表:指鏈表的最后一個結(jié)點(diǎn)的指針值指向第一個結(jié)點(diǎn),整個鏈表形成一個環(huán)(如下圖)。…結(jié)點(diǎn)1結(jié)點(diǎn)2結(jié)點(diǎn)n第十三頁,共二十七頁,2022年,8月28日21.4棧和隊列棧:是一種特殊的線性表,是限定僅在表尾進(jìn)行插入和刪除運(yùn)算的線性表,表尾稱為棧頂(top),表頭稱為棧底(bottom)。表中無元素即空棧。棧中有元素a1,a2,…,an,如下頁圖所示,稱a1為棧底元素。新元素進(jìn)棧要置于an之上,刪除或退棧先對an進(jìn)行,即“后進(jìn)先出”(LIFO)的操作原則;
棧的物理存儲可以用順序存儲結(jié)構(gòu)或鏈?zhǔn)酱鎯Y(jié)構(gòu);
棧的運(yùn)算還有取棧頂元素,檢查棧是否為空,清除等。第十四頁,共二十七頁,2022年,8月28日棧的插入和刪除ABACBABAFEBAATOPTOPTOPTOPTOPTOPan…a2a1進(jìn)棧出棧棧底棧結(jié)構(gòu)(3)(1)(2)(5)(4)(6)棧頂?shù)谑屙?,共二十七頁?022年,8月28日隊列隊列:是限定所有的插入都在表的一端進(jìn)行,所有的刪除都在表的另一端進(jìn)行的線性表。進(jìn)行刪除的一端叫隊頭,進(jìn)行插入的一端叫隊尾,如下頁圖所示。在隊列中,新元素總是加入到隊尾,每次刪除的總是對頭元素,即當(dāng)前“最老的”元素,這就是“先進(jìn)先出”(FIFO)的操作原則。隊列的物理存儲可以用:順序存儲結(jié)構(gòu),也可用鏈?zhǔn)酱鎯Y(jié)構(gòu)。第十六頁,共二十七頁,2022年,8月28日隊列的示意圖出隊列
a1a2a3…an
入隊列
隊頭
隊尾第十七頁,共二十七頁,2022年,8月28日隊列的插入和刪除示例第十八頁,共二十七頁,2022年,8月28日21.5樹與二叉樹
樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu),樹和二叉樹是最常見的樹形結(jié)構(gòu)。
樹(Tree):是n(n≥0)個結(jié)點(diǎn)的有限集合。若n=0,則稱為空樹;否則,有且僅有一個特定的結(jié)點(diǎn)被稱為根,當(dāng)n>1時,其余結(jié)點(diǎn)被分成m(m>0)個互不相交的子集T1,T2,…,Tm,每個子集又是一棵樹,稱作這個根的子樹(subtree)。
第十九頁,共二十七頁,2022年,8月28日樹形結(jié)構(gòu)的常用術(shù)語
結(jié)點(diǎn)的度(Degree):一個結(jié)點(diǎn)的子樹的個數(shù)。
樹的度:樹中各結(jié)點(diǎn)的度的最大值。
樹葉(Leaf):度為0的結(jié)點(diǎn)。
分支結(jié)點(diǎn):度不為0的結(jié)點(diǎn)。
雙親(Parent)、子女(Child):結(jié)點(diǎn)的各子樹的根稱作該結(jié)點(diǎn)的子女;相應(yīng)的該結(jié)點(diǎn)稱作其子女的雙親。
兄弟(Sibling):具有相同雙親的結(jié)點(diǎn)互為兄弟。
結(jié)點(diǎn)的層數(shù)(Level);樹的深度(Depth)森林(Forest)第二十頁,共二十七頁,2022年,8月28日二叉樹
二叉樹(BinaryTree):是n(n≥0)個結(jié)點(diǎn)的有限集合,這個集合或者為空集(n=0),或者由一個根結(jié)點(diǎn)及兩棵不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。二叉樹是樹的特殊情形。
二者的區(qū)別是:二叉樹為有序樹。第二十一頁,共二十七頁,2022年,8月28日
二叉樹的性質(zhì):
1、在二叉樹的i層上,最多有2i-1個結(jié)點(diǎn)(i≥1)
2、深度為k的二叉樹最多有2k-1個結(jié)點(diǎn)(k≥1)
3、對于任意一棵二叉樹,如果度為0的結(jié)點(diǎn)個數(shù)為n0,度為2的結(jié)點(diǎn)個數(shù)為n2,則n0=n2+1。
4、具有n個結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。其中,[log2n]是不大于log2n的最大整數(shù)。
第二十二頁,共二十七頁,2022年,8月28日滿二叉樹和完全二叉樹
一棵深度為k且具有2k-1個結(jié)點(diǎn)的二叉樹稱為滿二叉樹(FullBinaryTree)。深度為k,有n個結(jié)點(diǎn)的二叉樹,當(dāng)且僅當(dāng)其妹一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(yīng)時,稱為完全二叉樹。第二十三頁,共二十七頁,2022年,8月28日二叉樹的存儲
二叉樹的存儲通常采用:鏈接方式。每個結(jié)點(diǎn)除存儲結(jié)點(diǎn)自身的信息外再設(shè)置兩個指針域Ichild和rchild,分別指向結(jié)點(diǎn)的左子女和右子女,當(dāng)結(jié)點(diǎn)的某個指針為空時,則相應(yīng)的指針值為空(NIL或∧
)。結(jié)點(diǎn)的形式為:lchilddatarchild第二十四頁,共二十七頁,2022年,8月28日二叉樹的遍歷
遍歷一個樹形結(jié)構(gòu)是指:按一定次序系統(tǒng)的訪問該結(jié)構(gòu)中的所有結(jié)點(diǎn),使每個結(jié)點(diǎn)恰好被訪問一次。前序遍歷法(NLR次序)訪問根,按前序遍歷左子樹,按前序遍歷右子樹。后序遍歷法(LRN次序)按后序遍歷左子樹,按后序遍歷右子樹,訪問根。
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 第13課 五四運(yùn)動
- 《企業(yè)及管理》課件
- 項目里程碑成果展
- 秋分習(xí)俗的地理解讀
- 大班月份工作計劃
- 2023年-2024年項目管理人員安全培訓(xùn)考試題答案標(biāo)準(zhǔn)卷
- 《電流跟電壓》課件
- 隧道隧道內(nèi)環(huán)境監(jiān)測-洞察分析
- 性別平等與人口質(zhì)量的關(guān)系-洞察分析
- 宇宙微波背景輻射的精細(xì)結(jié)構(gòu)分析-洞察分析
- 浙江省臺州市2023-2024學(xué)年高一上學(xué)期期末考試 化學(xué) 含答案
- 一年級數(shù)學(xué)加減法口算題每日一練(25套打印版)
- 2024年度工作總結(jié)模板
- 送貨員崗位勞動合同模板
- 2024年售樓處規(guī)章制度例文(六篇)
- 2024秋期國家開放大學(xué)本科《經(jīng)濟(jì)學(xué)(本)》一平臺在線形考(形考任務(wù)1至6)試題及答案
- 動靜脈內(nèi)瘺成形術(shù)
- 法律意見書(適用于股權(quán)投資)
- JJF(蘇) 276-2024 接觸(觸針)式表面輪廓測量儀校準(zhǔn)規(guī)范
- 黑河黃藏寺水利樞紐工程環(huán)境影響評價報告書-黑河流域管理局
- 污泥(廢水)運(yùn)輸服務(wù)方案(技術(shù)方案)
評論
0/150
提交評論