計算機(jī)二級數(shù)據(jù)結(jié)構(gòu)與算法

關(guān)于計算機(jī)二級數(shù)據(jù)結(jié)構(gòu)與算法第一頁，共六十七頁，2022年，8月28日1.基本數(shù)據(jù)結(jié)構(gòu)與算法第二頁，共六十七頁，2022年，8月28日21.1算法1.1.1算法(algorithm)基本概念對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。第三頁，共六十七頁，2022年，8月28日3算法的基本特征可行性確定性有窮性擁有足夠的情報輸入和輸出第四頁，共六十七頁，2022年，8月28日4算法的基本要素

1、對數(shù)據(jù)對象的運(yùn)算和操作算術(shù)運(yùn)算：加、減、乘、除等運(yùn)算邏輯運(yùn)算：“與”、“或”、“非”等運(yùn)算關(guān)系運(yùn)算：“大于”、“等于”等運(yùn)算數(shù)據(jù)傳輸：賦值、輸入、輸出等運(yùn)算第五頁，共六十七頁，2022年，8月28日5算法的基本要素

2、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等一個算法一般可以用順序、選擇、循環(huán)三種基本機(jī)構(gòu)組合而成。第六頁，共六十七頁，2022年，8月28日6算法設(shè)計基本方法列舉法歸納法遞推遞歸（以簡潔的形式設(shè)計和描述算法）減半遞推技術(shù)回溯法第七頁，共六十七頁，2022年，8月28日71.1.2算法復(fù)雜度時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。一般用算法在執(zhí)行過程中所需要的基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。算法中基本運(yùn)算執(zhí)行次數(shù)和問題的規(guī)模有關(guān)。算法的工作量＝f(n)

有時在固定規(guī)模下，基本運(yùn)算執(zhí)行次數(shù)還和具體輸入有關(guān)。第八頁，共六十七頁，2022年，8月28日8

平均性態(tài)最壞情況復(fù)雜性X出現(xiàn)的概率算法在輸入x時所執(zhí)行的基本運(yùn)算次數(shù)規(guī)模為n時，算法執(zhí)行時所有可輸入的集合第九頁，共六十七頁，2022年，8月28日9算法的空間復(fù)雜度一般是指執(zhí)行這個算法所需要的內(nèi)存空間一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間一個上機(jī)執(zhí)行的程序除了需要存儲空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為實(shí)現(xiàn)計算所需信息的輔助空間。第十頁，共六十七頁，2022年，8月28日101.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的圖形表示線性結(jié)構(gòu)與非線性結(jié)構(gòu)第十一頁，共六十七頁，2022年，8月28日111.2.1數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容當(dāng)今計算機(jī)應(yīng)用的特點(diǎn)：所處理的數(shù)據(jù)量大且具有一定的關(guān)系；對其操作不再是單純的數(shù)值計算，而更多地是需要對其進(jìn)行組織、管理和檢索。第十二頁，共六十七頁，2022年，8月28日12應(yīng)用舉例——學(xué)籍檔案管理

假設(shè)用計算機(jī)管理學(xué)生檔案，研究對象為：學(xué)生，常用操作查找、刪除、修改、插入等一個學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表1-1所示的學(xué)生信息。第十三頁，共六十七頁，2022年，8月28日13第十四頁，共六十七頁，2022年，8月28日14特點(diǎn)：每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格。表中每個學(xué)生的信息依據(jù)學(xué)號的順序存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)。對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。

第十五頁，共六十七頁，2022年，8月28日15

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。1.2.2基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個方面的問題：1.數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。2.在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。3.對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。位置：P6，重要。第十六頁，共六十七頁，2022年，8月28日16能輸入到計算機(jī)中并能被計算機(jī)程序處理的符號的集合。整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2)字符串(Beijing)、圖形、聲音。1.2.2基本概念和術(shù)語

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。第十七頁，共六十七頁，2022年，8月28日171.2.2基本概念和術(shù)語計算機(jī)管理圖書問題在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排如何將查詢圖書的這些信息存入計算機(jī)中既要考慮查詢時間短，又要考慮節(jié)省空間

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。第十八頁，共六十七頁，2022年，8月28日18最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如1.2.2基本概念和術(shù)語

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。第十九頁，共六十七頁，2022年，8月28日19將各種邏輯結(jié)構(gòu)的數(shù)據(jù)存放在計算機(jī)存儲空間中。目的不同，最佳的存儲方方法就不同。

數(shù)據(jù)元素在計算機(jī)中的表示

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。1.2.2基本概念和術(shù)語第二十頁，共六十七頁，2022年，8月28日20對數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理(插入、刪除、修改、查找、排序)1.2.2基本概念和術(shù)語

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運(yùn)算的一般方法的學(xué)科。第二十一頁，共六十七頁，2022年，8月28日21數(shù)據(jù)元素(DataElement)

現(xiàn)實(shí)世界中客觀存在得一切個體或個體相關(guān)的操作都可以抽象為數(shù)據(jù)元素。如：四季的名稱：春、夏、秋、冬由季節(jié)抽象而來，可以作為季節(jié)的數(shù)據(jù)元素。同理，父親、兒子、女兒可以作為家庭成員的數(shù)據(jù)元素。

簡單的說，數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。第二十二頁，共六十七頁，2022年，8月28日22數(shù)據(jù)元素(DataElement)

甚至客觀存在的事件，如演出、借書、比賽等也可以抽象為數(shù)據(jù)元素。在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在某種關(guān)系，這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間的這種固有的關(guān)系簡單地用前后件關(guān)系來描述。第二十三頁，共六十七頁，2022年，8月28日23數(shù)據(jù)的邏輯結(jié)構(gòu)表示數(shù)據(jù)元素的信息表示數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)邏輯結(jié)構(gòu)通常用二元組表示數(shù)據(jù)邏輯結(jié)構(gòu)也可用圖形表示第二十四頁，共六十七頁，2022年，8月28日24數(shù)據(jù)邏輯結(jié)構(gòu)可表示為：B=（D，R）B表示數(shù)據(jù)結(jié)構(gòu)D表示數(shù)據(jù)元素的集合R表示數(shù)據(jù)元素間前后件關(guān)系為反映前后件關(guān)系，通常用二元組(a,b)來表示，它表示a是b的前件。第二十五頁，共六十七頁，2022年，8月28日25B=(D,R)D={父親，兒子，女兒}R={(父親，兒子)，(父親，女兒)}B=(D,R)D={春，夏，秋，冬}R={(春，夏)，(夏，秋)，(秋，冬)}第二十六頁，共六十七頁，2022年，8月28日26數(shù)據(jù)結(jié)構(gòu)的圖形表示春夏秋冬一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示ABCD第二十七頁，共六十七頁，2022年，8月28日27數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間的表示。各數(shù)據(jù)元素在計算機(jī)存儲空間中的位置與邏輯關(guān)系不一定相同。常用的存儲結(jié)構(gòu)有：順序、鏈接、索引等。第二十八頁，共六十七頁，2022年，8月28日28數(shù)據(jù)的存儲結(jié)構(gòu)....6427531....字節(jié)....6427531....冬夏秋春....6427531....兒子女兒4006父親第二十九頁，共六十七頁，2022年，8月28日29二級公共基礎(chǔ)05年4月試題（1）數(shù)據(jù)的存儲結(jié)構(gòu)是指

A）存儲在外存中的數(shù)據(jù)B）數(shù)據(jù)所占的存儲空間量C）數(shù)據(jù)在計算機(jī)中的順序存儲方式D）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示第三十頁，共六十七頁，2022年，8月28日30線性結(jié)構(gòu)與非線性結(jié)構(gòu)有且只有一個根結(jié)點(diǎn)（沒有前件的結(jié)點(diǎn)）。每一個結(jié)點(diǎn)最多只有一個前件，也最多只有一個后件。第三十一頁，共六十七頁，2022年，8月28日31線性結(jié)構(gòu)

A,B,C,·······，X,Y,Z學(xué)生成績表86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學(xué)號線性表——結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié)ABC第三十二頁，共六十七頁，2022年，8月28日32非線性結(jié)構(gòu)

如果數(shù)據(jù)結(jié)構(gòu)不滿足線性結(jié)構(gòu)的條件，則稱之為非線性結(jié)構(gòu)。此外，在線線結(jié)構(gòu)中插入或刪除一個結(jié)點(diǎn)，還應(yīng)是線線結(jié)構(gòu)，否則此結(jié)構(gòu)非線線ABCD第三十三頁，共六十七頁，2022年，8月28日33樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式計算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)第三十四頁，共六十七頁，2022年，8月28日34ABCDEFGH樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGA第三十五頁，共六十七頁，2022年，8月28日351.3線性表1.3.1線性表的定義線性表是n個元素的有限序列，它們之間的關(guān)系可以排成一個線性序列：

a1，a2，……，ai，……，an其中n稱作表的長度，當(dāng)n=0時，稱作空表。第三十六頁，共六十七頁，2022年，8月28日36線性表的特點(diǎn)：1.線性表中所有元素的性質(zhì)相同。2.除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個前件和一個后件。第一個數(shù)據(jù)元素?zé)o前件，最后一個數(shù)據(jù)元素?zé)o后件。3.數(shù)據(jù)元素在表中的位置只取決于它自身的序號。在線性表上常用的運(yùn)算有：初始化、求長度、取元素、修改、前插、刪除、檢索、排序。第三十七頁，共六十七頁，2022年，8月28日371.3.2線性表的順序存儲結(jié)構(gòu)線性表順序存儲結(jié)構(gòu)的特點(diǎn)：

1、線性表所有元素所占的存儲空間是連續(xù)的。

2、線性表各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。

在計算機(jī)中存放線性表，采用順序存儲是一種簡單方便的方法。

第三十八頁，共六十七頁，2022年，8月28日38元素an……..元素ai……..元素a2元素a1bADR(a1)

+k存儲地址內(nèi)存狀態(tài)順序存儲結(jié)構(gòu)示意圖(順序表)：首地址ADR(a1)每個元素所占用的存儲單元個數(shù)ADR(a1)

+(i-1)*

kADR(a1)

+(n-1)*

kADR(ai)=ADR(a1)

+(i-1)*

k第三十九頁，共六十七頁，2022年，8月28日39n-1線性表的插入和刪除運(yùn)算示意圖ai-1…..a2a1an…ai+1aixai-1…..a2a1

aiai+1…alength

an……ai+1aix刪除運(yùn)算插入運(yùn)算第四十頁，共六十七頁，2022年，8月28日40若長度為n的線性表表示為：(a1,a2,…,ai,…an)運(yùn)算后表示為：(a’1,a’2,…,a’i,…a’n)，則滿足以下關(guān)系：插入新元素b后a’jaj1<=j<=i-1b

j=iaj-1i+1<=j<=n+1長度增加為：n+1刪除第i個元素后a’jaj1<=j<=i-1aj+1i<=j<=n-1長度減少為：n-1第四十一頁，共六十七頁，2022年，8月28日411.4棧和隊(duì)列1.4.1棧和隊(duì)列的定義

棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。第四十二頁，共六十七頁，2022年，8月28日42棧的定義棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為先進(jìn)后出(FILO)或后進(jìn)先出(LIFO)設(shè)棧s=（a1，a2，...,ai，...，an），其中a1是棧底元素，an是棧頂元素。棧頂（top)：允許插入和刪除的一端；棧底（bottom):不允許插入和刪除的一端。約定用指針top始終指向棧頂?shù)奈恢?，用指針bottom指向棧底。

a1a2….ai進(jìn)棧出棧topbottomn1第四十三頁，共六十七頁，2022年，8月28日431.4.2棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算a2a1a1a2top

用順序存儲結(jié)構(gòu)表示的棧。

順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置。基本運(yùn)算：壓（進(jìn)）棧：PUSH出棧：POP讀棧頂元素第四十四頁，共六十七頁，2022年，8月28日44進(jìn)棧示例

棧滿：棧頂指針指向存儲空間的最后一個位置第四十五頁，共六十七頁，2022年，8月28日45退棧示例第四十六頁，共六十七頁，2022年，8月28日461.4.1.2隊(duì)列(

Queue)的定義定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。a1,

a2,

a3,

a4,…………

an-1,

an

隊(duì)列示意圖隊(duì)頭隊(duì)尾隊(duì)列只允許在隊(duì)尾插入，在對頭刪除。隊(duì)頭指針：front：指向排頭元素的前一個位置隊(duì)尾指針：rear：指向隊(duì)尾元素此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）或后進(jìn)后出(LILO)。第四十七頁，共六十七頁，2022年，8月28日47隊(duì)列的主要運(yùn)算（1）插入一個新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（2）刪除隊(duì)頭元素，稱為出隊(duì)；（3）讀取隊(duì)頭元素；當(dāng)有新元素入隊(duì)時，尾指針加1，當(dāng)有元素出隊(duì)時，頭指針加1。故在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素前一個位置，而尾指針始終指向隊(duì)尾元素的位置第四十八頁，共六十七頁，2022年，8月28日48隊(duì)列的進(jìn)隊(duì)和出隊(duì)

進(jìn)隊(duì)時隊(duì)尾指針先進(jìn)一rear=rear+1，再將新元素按rear指示位置加入。出隊(duì)時隊(duì)頭指針先進(jìn)一front=front+1，再將下標(biāo)為front的元素取出。

隊(duì)滿時再進(jìn)隊(duì)將溢出出錯；隊(duì)空時再出隊(duì)將隊(duì)空處理。隊(duì)滿：隊(duì)尾指針指向存儲空間的最后一個位置第四十九頁，共六十七頁，2022年，8月28日49定義：存儲隊(duì)列的線型空間被模擬為首尾相接的環(huán)形空間處理。循環(huán)隊(duì)列（長度為m）的的性質(zhì)：循環(huán)隊(duì)列的初始狀態(tài)：front

=rear=m隊(duì)頭、隊(duì)尾指針加1時若結(jié)果等于m＋1置為1。循環(huán)隊(duì)列(CircularQueue)第五十頁，共六十七頁，2022年，8月28日50Q(1:m)…21mrearfront第五十一頁，共六十七頁，2022年，8月28日51Q(1:6）rearfrontAECDBF第五十二頁，共六十七頁，2022年，8月28日52隊(duì)空時：front==rear;隊(duì)滿時：front==rear

由于隊(duì)滿和對空的條件一樣，無法判斷循環(huán)隊(duì)列的狀態(tài)，所以增加了一個標(biāo)志s，s的定義如下：s1表示隊(duì)列非空0表示隊(duì)列空P19-20詳細(xì)說明第五十三頁，共六十七頁，2022年，8月28日531.5鏈表線性鏈表指針數(shù)據(jù)線性鏈表節(jié)點(diǎn)指針數(shù)據(jù)指針數(shù)據(jù)第五十四頁，共六十七頁，2022年，8月28日541.5.1線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

將線性表的元素放到一個具有頭指針的鏈表中，鏈表中每個結(jié)點(diǎn)包含數(shù)據(jù)域和指針域。

數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點(diǎn)的地址，最后一個結(jié)點(diǎn)的指針域?yàn)榭铡＿壿嬌舷噜彽臄?shù)據(jù)元素在內(nèi)存中的物理存儲空間不一定相鄰。第五十五頁，共六十七頁，2022年，8月28日55上圖的線性表為ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG第五十六頁，共六十七頁，2022年，8月28日56線性鏈表表示法:0第五十七頁，共六十七頁，2022年，8月28日57雙向鏈表在每個結(jié)點(diǎn)中設(shè)置兩個指針，一個指向后繼，一個指向前驅(qū)?？芍苯哟_定一個結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)?？商岣咝?。datanextbefore第五十八頁，共六十七頁，2022年，8月28日58鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)

插入、刪除靈活方便，不需要移動結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可。適合于線性表是動態(tài)變化的,不進(jìn)行頻繁查找操作、但經(jīng)常進(jìn)行插入刪除時使用。

鏈表的查找只能從頭指針開始順序查找。

第五十九頁，共六十七頁，2022年，8月28日59babaxHH線性鏈表的插入運(yùn)算S在H所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)1.5.2線性鏈