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

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

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

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

有時在固定規(guī)模下，基本運算執(zhí)行次數(shù)還和具體輸入有關(guān)。第8頁，共67頁，2022年，5月20日，6點11分，星期六8

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

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

第15頁，共67頁，2022年，5月20日，6點11分，星期六15

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(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ù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)。3.對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。位置：P6，重要。第16頁，共67頁，2022年，5月20日，6點11分，星期六16能輸入到計算機中并能被計算機程序處理的符號的集合。整數(shù)(1,2)、實數(shù)(1.1,1.2)字符串(Beijing)、圖形、聲音。1.2.2基本概念和術(shù)語

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

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

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。第19頁，共67頁，2022年，5月20日，6點11分，星期六19將各種邏輯結(jié)構(gòu)的數(shù)據(jù)存放在計算機存儲空間中。目的不同，最佳的存儲方方法就不同。

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

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

數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。第21頁，共67頁，2022年，5月20日，6點11分，星期六21數(shù)據(jù)元素(DataElement)

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

簡單的說，數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。第22頁，共67頁，2022年，5月20日，6點11分，星期六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)系來描述。第23頁，共67頁，2022年，5月20日，6點11分，星期六23數(shù)據(jù)的邏輯結(jié)構(gòu)表示數(shù)據(jù)元素的信息表示數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)邏輯結(jié)構(gòu)通常用二元組表示數(shù)據(jù)邏輯結(jié)構(gòu)也可用圖形表示第24頁，共67頁，2022年，5月20日，6點11分，星期六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的前件。第25頁，共67頁，2022年，5月20日，6點11分，星期六25B=(D,R)D={父親，兒子，女兒}R={(父親，兒子)，(父親，女兒)}B=(D,R)D={春，夏，秋，冬}R={(春，夏)，(夏，秋)，(秋，冬)}第26頁，共67頁，2022年，5月20日，6點11分，星期六26數(shù)據(jù)結(jié)構(gòu)的圖形表示春夏秋冬一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示ABCD第27頁，共67頁，2022年，5月20日，6點11分，星期六27數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間的表示。各數(shù)據(jù)元素在計算機存儲空間中的位置與邏輯關(guān)系不一定相同。常用的存儲結(jié)構(gòu)有：順序、鏈接、索引等。第28頁，共67頁，2022年，5月20日，6點11分，星期六28數(shù)據(jù)的存儲結(jié)構(gòu)....6427531....字節(jié)....6427531....冬夏秋春....6427531....兒子女兒4006父親第29頁，共67頁，2022年，5月20日，6點11分，星期六29二級公共基礎(chǔ)05年4月試題（1）數(shù)據(jù)的存儲結(jié)構(gòu)是指

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

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

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

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

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

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

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

第38頁，共67頁，2022年，5月20日，6點11分，星期六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第39頁，共67頁，2022年，5月20日，6點11分，星期六39n-1線性表的插入和刪除運算示意圖ai-1…..a2a1an…ai+1aixai-1…..a2a1

aiai+1…alength

an……ai+1aix刪除運算插入運算第40頁，共67頁，2022年，5月20日，6點11分，星期六40若長度為n的線性表表示為：(a1,a2,…,ai,…an)運算后表示為：(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第41頁，共67頁，2022年，5月20日，6點11分，星期六411.4棧和隊列1.4.1棧和隊列的定義

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

a1a2….ai進棧出棧topbottomn1第43頁，共67頁，2022年，5月20日，6點11分，星期六431.4.2棧的順序存儲結(jié)構(gòu)及其基本運算a2a1a1a2top

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

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

棧滿：棧頂指針指向存儲空間的最后一個位置第45頁，共67頁，2022年，5月20日，6點11分，星期六45退棧示例第46頁，共67頁，2022年，5月20日，6點11分，星期六461.4.1.2隊列(

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

a2,

a3,

a4,…………

an-1,

an

隊列示意圖隊頭隊尾隊列只允許在隊尾插入，在對頭刪除。隊頭指針：front：指向排頭元素的前一個位置隊尾指針：rear：指向隊尾元素此種結(jié)構(gòu)稱為先進先出（FIFO）或后進后出(LILO)。第47頁，共67頁，2022年，5月20日，6點11分，星期六47隊列的主要運算（1）插入一個新的隊尾元素，稱為進隊；（2）刪除隊頭元素，稱為出隊；（3）讀取隊頭元素；當有新元素入隊時，尾指針加1，當有元素出隊時，頭指針加1。故在非空隊列中，頭指針始終指向隊頭元素前一個位置，而尾指針始終指向隊尾元素的位置第48頁，共67頁，2022年，5月20日，6點11分，星期六48隊列的進隊和出隊

進隊時隊尾指針先進一rear=rear+1，再將新元素按rear指示位置加入。出隊時隊頭指針先進一front=front+1，再將下標為front的元素取出。

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

=rear=m隊頭、隊尾指針加1時若結(jié)果等于m＋1置為1。循環(huán)隊列(CircularQueue)第50頁，共67頁，2022年，5月20日，6點11分，星期六50Q(1:m)…21mrearfront第51頁，共67頁，2022年，5月20日，6點11分，星期六51Q(1:6）rearfrontAECDBF第52頁，共67頁，2022年，5月20日，6點11分，星期六52隊空時：front==rear;隊滿時：front==rear

由于隊滿和對空的條件一樣，無法判斷循環(huán)隊列的狀態(tài)，所以增加了一個標志s，s的定義如下：s1表示隊列非空0表示隊列空P19-20詳細說明第53頁，共67頁，2022年，5月20日，6點11分，星期六531.5鏈表線性鏈表指針數(shù)據(jù)線性鏈表節(jié)點指針數(shù)據(jù)指針數(shù)據(jù)第54頁，共67頁，2022年，5月20日，6點11分，星期六541.5.1線性表的鏈式存儲結(jié)構(gòu)

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

數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點的地址，最后一個結(jié)點的指針域為空。邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的物理存儲空間不一定相鄰。第55頁，共67頁，2022年，5月20日，6點11分，星期六55上圖的線性表為ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG第56頁，共67頁，2022年，5月20日，6點11分，星期六56線性鏈表表示法:0第57頁，共67頁，2022年，5月20日，6點11分，星期六57雙向鏈表在每個結(jié)點中設(shè)置兩個指針，一個指向后繼，一個指向前驅(qū)?？芍苯哟_定一個結(jié)點的前驅(qū)和后繼結(jié)點。可提高效率。datanextbefore第58頁，共67頁，2022年，5月20日，6點11分，星期六58鏈式存儲結(jié)構(gòu)的特點

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

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

第59頁，共67頁，2022年，5月20日，6點11分，星期六59babaxHH線性鏈表的插入運算S在H所指向的結(jié)點之后插入新的結(jié)點1.5.2線性鏈表的運算第60頁