數(shù)據(jù)結構導論串講第1頁，課件共148頁，創(chuàng)作于2023年2月

概述

《數(shù)據(jù)結構導論》是計算機科學與技術專業(yè)的一門必修課程。本課程介紹如何組織各種數(shù)據(jù)在計算機中的存儲、傳遞和轉換。內(nèi)容包括：線性表、棧、隊列、串、數(shù)組、樹、二叉樹、圖等基本數(shù)據(jù)結構及其應用；排序和查找的原理與方法；數(shù)據(jù)在外存上的組織方法。第2頁，課件共148頁，創(chuàng)作于2023年2月第一章概論第3頁，課件共148頁，創(chuàng)作于2023年2月第4頁，課件共148頁，創(chuàng)作于2023年2月本章總述要求熟悉各名詞、術語的含義，掌握基本概念。包括數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、邏輯關系和邏輯結構、運算和基本運算、數(shù)據(jù)結構、存儲方式和存儲結構、算法及算法分析等。注意這些概念之間的聯(lián)系。第5頁，課件共148頁，創(chuàng)作于2023年2月本章重點邏輯結構和數(shù)據(jù)結構的概念。本章難點算法的時間復雜性分析。第6頁，課件共148頁，創(chuàng)作于2023年2月本章知識點

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項數(shù)據(jù)—能被計算機存儲、加工的對象通稱為數(shù)據(jù)。數(shù)據(jù)元素—是數(shù)據(jù)的基本單位，在程序中作為一個整體來考慮和處理。具有完整確定的實際意義。數(shù)據(jù)項—是數(shù)據(jù)不可分割的最小標識單位。數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成，數(shù)據(jù)項通常不具有完整確定的實際意義。第7頁，課件共148頁，創(chuàng)作于2023年2月數(shù)據(jù)數(shù)據(jù)項數(shù)據(jù)元素數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項構成了數(shù)據(jù)組織的三個層次，如下圖所示:第8頁，課件共148頁，創(chuàng)作于2023年2月

2.數(shù)據(jù)結構數(shù)據(jù)結構是數(shù)據(jù)元素之間的相互關系。結構分為邏輯結構與物理結構。線性結構樹形結構圖狀結構集合結構第9頁，課件共148頁，創(chuàng)作于2023年2月存儲結構：邏輯結構在計算機中的表示（映像）被稱為存儲結構，其中應該包含數(shù)據(jù)元素的內(nèi)容及其關系的表示。

四種基本存儲方式：

順序存儲方式特點：借助于數(shù)據(jù)元素在存儲器中的位置來表示數(shù)據(jù)元素之間的邏輯關系

鏈式存儲方式特點：借助指示元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關系

索引存儲方式

散列存儲方式第10頁，課件共148頁，創(chuàng)作于2023年2月

3.算法算法就是解決問題的方法。算法分析主要從時間復雜度、空間復雜度方面進行算法分析。時間復雜度:最壞情況時間復雜度,平均時間復雜度。Tnnlog2nn2本章結束第11頁，課件共148頁，創(chuàng)作于2023年2月第二章線性表第12頁，課件共148頁，創(chuàng)作于2023年2月第13頁，課件共148頁，創(chuàng)作于2023年2月本章總述本章主要討論了線性表及它的兩種存儲實現(xiàn)：順序實現(xiàn)和鏈接實現(xiàn)；另外，簡單介紹了串這種特殊的線性表的運算和存儲實現(xiàn)。線性表是一種最簡單最常見的數(shù)據(jù)結構第14頁，課件共148頁，創(chuàng)作于2023年2月本章重點

線性結構的定義和特點；線性表的運算；順序表和單鏈表的組織方法和算法設計。本章難點

單鏈表上的算法設計。第15頁，課件共148頁，創(chuàng)作于2023年2月線性表的邏輯結構定義線性表是一個含有n個數(shù)據(jù)元素的有限序列。L=(a1,a2,a3,a4,a5,a6,....,an)ai-1,

ai

,

ai+1直接前驅

直接后繼線性表長度第16頁，課件共148頁，創(chuàng)作于2023年2月

線性結構的基本特征:線性結構是一個數(shù)據(jù)元素的有序（次序）集

1.集合中必存在唯一的一個“第一元素”；

2.集合中必存在唯一的一個“最后元素”；

3.除最后元素之外，均有唯一的后繼；

4.除第一元素之外，均有唯一的前驅。第17頁，課件共148頁，創(chuàng)作于2023年2月順序存儲結構

用一組地址連續(xù)的存儲單元依次存儲線性表的元素。

順序表特點：

邏輯順序與物理順序一致；

屬隨機存取的存儲結構。第18頁，課件共148頁，創(chuàng)作于2023年2月......a1a2a3a4a5a6anbb+Lb+2Lb+3Lb+(n-1)L假設線性表中每個元素需占用L個存儲單元LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*LL:一個數(shù)據(jù)元素所占存儲量↑基地址第19頁，課件共148頁，創(chuàng)作于2023年2月插入、刪除算法的分析插入算法的數(shù)學期望值刪除算法的數(shù)學期望值設：pi=1/(n+1),qi=1/n，則可以得出：第20頁，課件共148頁，創(chuàng)作于2023年2月順序表表示的優(yōu)缺點優(yōu)點：隨機存取表中的任一結點。缺點：插入和刪除運算不方便，須移動大量的結點；存儲分配只能預先分配。第21頁，課件共148頁，創(chuàng)作于2023年2月鏈式存儲結構用一組任意的存儲單元（可能不連續(xù)）存儲線性表的數(shù)據(jù)元素。......a3......a2......a1......a4...........第22頁，課件共148頁，創(chuàng)作于2023年2月鏈式存儲結構數(shù)據(jù)元素內(nèi)容該數(shù)據(jù)元素的直接后繼地址datanext數(shù)據(jù)域指針域第23頁，課件共148頁，創(chuàng)作于2023年2月L=(a1,a2,a3,a4,a5,a6)結點La1a2a3a4a5a6^以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭指針。第24頁，課件共148頁，創(chuàng)作于2023年2月含有頭結點的空表//////^

ＬL////a1a2......an^頭結點有時為了操作方便，在第一個結點之前附設一個“頭結點”，以指向頭結點的指針為鏈表的頭指針指針域為空第25頁，課件共148頁，創(chuàng)作于2023年2月

特點:邏輯順序與物理順序有可能不一致。屬順序存取的存儲結構，即存取每個數(shù)據(jù)元素所花費的時間不相等。第26頁，課件共148頁，創(chuàng)作于2023年2月datanextprior特點：克服單鏈表的單向性其它形式的鏈表1.雙向鏈表(doublelinkedlist)每個結點有兩個指針域第27頁，課件共148頁，創(chuàng)作于2023年2月

2.循環(huán)鏈表表中最后一個結點的指針域指向頭結點，鏈表形成一個環(huán)。特點從表中任何一個結點出發(fā)可掃描整個鏈表中的所有結點。第28頁，課件共148頁，創(chuàng)作于2023年2月順序實現(xiàn)與鏈接實現(xiàn)的比較時間性能比較定位運算:順序表和單鏈表,均為O(n)讀表元：順序表-O(1)(隨機存取);單鏈表-O(n)鏈入/摘除：順序表-0(n);單鏈表-O(1)（插入、刪除方便）第29頁，課件共148頁，創(chuàng)作于2023年2月第三章棧、隊列和數(shù)組第30頁，課件共148頁，創(chuàng)作于2023年2月第31頁，課件共148頁，創(chuàng)作于2023年2月本章總述棧和隊列是兩種常用的數(shù)據(jù)結構，這兩種結構與線性表有密切的聯(lián)系。棧和隊列的邏輯結構是線性結構，它們的基本運算與線性表的基本運算十分類似，可看作是運算受限的線性表。數(shù)組與線性表也有密切的聯(lián)系。第32頁，課件共148頁，創(chuàng)作于2023年2月本章重點棧和隊列的特點；順序棧和鏈棧上基本運算的實現(xiàn)和簡單算法；鏈隊上基本運算實現(xiàn)和簡單算法設計。本章難點循環(huán)隊的組織，隊滿、隊空的條件及算法設計。第33頁，課件共148頁，創(chuàng)作于2023年2月棧的類型定義插入、刪除只在表尾進行的線性表被稱為棧。a1a2a3a4....an插入刪除第34頁，課件共148頁，創(chuàng)作于2023年2月棧的特點后進先出----LIFO(LastInFirstOut)棧頂浮動棧底固定a1a2a3a4出進棧底棧頂?shù)?5頁，課件共148頁，創(chuàng)作于2023年2月棧的表示和實現(xiàn)順序存儲結構：

順序棧鏈式存儲結構：

鏈棧第36頁，課件共148頁，創(chuàng)作于2023年2月隊列定義若線性表的插入操作在一端進行，刪除操作在另一端進行，則稱此線性表為隊列。第37頁，課件共148頁，創(chuàng)作于2023年2月a1,a2,a3,a4,...,an刪除端插入端隊頭front隊尾rear第38頁，課件共148頁，創(chuàng)作于2023年2月隊列特點FIFO(FirstInFirstOut)隊頭、隊尾均是浮動的隊列類型的實現(xiàn)鏈隊列——鏈式映象循環(huán)隊列——順序映象第39頁，課件共148頁，創(chuàng)作于2023年2月q4q3q2q1frontrear3210入隊

Q[rear++]=e;出隊

e=Q[front++]隊列的順序存儲結構第40頁，課件共148頁，創(chuàng)作于2023年2月隊列的順序存儲結構frontrear“假溢出”現(xiàn)象解決的方法:將隊列構成環(huán)狀q4q3q2q1第41頁，課件共148頁，創(chuàng)作于2023年2月循環(huán)隊列012345678q1q2q3q4q5rearfront入隊操作：sq.rear=(sq.rear+1)%maxsize;出隊操作：sq.front=(sq.front+1)%maxsize;隊列空：sq.rear=sq.front隊列滿：((sq.rear+1)%maxsize)==sq.front;第42頁，課件共148頁，創(chuàng)作于2023年2月數(shù)組是一種已經(jīng)在高級語言中實現(xiàn)了的數(shù)據(jù)結構。通常采用順序存儲結構來存放數(shù)組。

有兩種順序映象的方式（二維數(shù)組）:

1)以行序為主序(低下標優(yōu)先);

2)以列序為主序(高下標優(yōu)先);第43頁，課件共148頁，創(chuàng)作于2023年2月例如：

稱為基地址或基址。以“行序為主序”的存儲映象二維數(shù)組A中任一元素ai,j

的存儲位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

第44頁，課件共148頁，創(chuàng)作于2023年2月矩陣的壓縮存儲矩陣可用二維數(shù)組來表示。實際問題中，會碰到階數(shù)高的矩陣，但存在許多值相同的元素和零元素。壓縮存儲的基本思想：值相同的多個元素只分配一個存儲空間，零元素不分配空間。特殊矩陣的壓縮存儲(對稱矩陣，三角矩陣)稀疏矩陣的壓縮存儲(三元組順序表)第45頁，課件共148頁，創(chuàng)作于2023年2月第四章樹第46頁，課件共148頁，創(chuàng)作于2023年2月第47頁，課件共148頁，創(chuàng)作于2023年2月本章總述本章是數(shù)據(jù)結構課程的重點之一。主要內(nèi)容包括：樹形結構的基本概念，定義在樹形結構上的兩種重要的數(shù)據(jù)結構-二叉樹和樹，它們的常見存儲結構、遍歷運算的實現(xiàn)以及它們之間的轉換。第48頁，課件共148頁，創(chuàng)作于2023年2月本章重點樹形結構的概念；二叉樹的定義、存儲結構和遍歷算法本章難點二叉樹的遍歷算法第49頁，課件共148頁，創(chuàng)作于2023年2月二叉樹或為空樹；或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結點左子樹右子樹第50頁，課件共148頁，創(chuàng)作于2023年2月二叉樹的五種基本形態(tài)：N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹第51頁，課件共148頁，創(chuàng)作于2023年2月二叉樹的重要特性性質1:

在二叉樹的第i

層上至多有2i-1個結點。(i≥1)性質2:

深度為k的二叉樹上至多含2k-1個結點（k≥1）性質3:

對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為2的結點，則必存在關系式：n0=n2+1兩類特殊的二叉樹：（1）滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。（2）完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。性質4:

具有n個結點的完全二叉樹的深度為log2n+1第52頁，課件共148頁，創(chuàng)作于2023年2月性質5:

若對含n個結點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為i的結點：

(1)若i=1，則該結點是二叉樹的根，無雙親,否則，編號為i/2的結點為其雙親結點;

(2)若2i>n，則該結點無左孩子，

否則，編號為2i的結點為其左孩子結點；

(3)若2i+1>n，則該結點無右孩子結點，

否則，編號為2i+1的結點為其右孩子結點。第53頁，課件共148頁，創(chuàng)作于2023年2月二叉樹的存儲結構1、二叉樹的順序存儲表示

適用于完全二叉樹或滿二叉樹。2、二叉樹的鏈式存儲表示

二叉鏈表三叉鏈表第54頁，課件共148頁，創(chuàng)作于2023年2月二叉樹遍歷

順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次。

遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法以遍歷為基礎，可以實現(xiàn)二叉樹上的許多復雜運算。第55頁，課件共148頁，創(chuàng)作于2023年2月

若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：第56頁，課件共148頁，創(chuàng)作于2023年2月

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。中（根）序的遍歷算法：第57頁，課件共148頁，創(chuàng)作于2023年2月

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。后（根）序的遍歷算法：第58頁，課件共148頁，創(chuàng)作于2023年2月PreOrder:abcdegfhInOrder:cbegdfahPostOrder:cgefdbhaabcdefgh第59頁，課件共148頁，創(chuàng)作于2023年2月樹和森林

樹的三種存儲結構雙親表示法孩子鏈表表示法孩子-兄弟存儲表示法

樹的遍歷先根遍歷后根遍歷層次遍歷

樹、森林與二叉樹的關系(相互轉換)注意：（1）與樹對應的二叉樹的根結點的右子樹一定為空（2）和樹對應的二叉樹，其左、右子樹的概念已改變?yōu)椋鹤笫呛⒆樱沂切值艿?0頁，課件共148頁，創(chuàng)作于2023年2月樹的帶權的路徑長度樹中所有葉子結點的帶權路徑長度之和

Huffman樹設有n個權值{w1,w2,……wn}，構造一棵有n個葉子結點的二叉樹，每個葉子的權值為wi,則wpl最小的二叉樹叫Huffman樹哈夫曼算法判定樹和哈夫曼樹本章結束第61頁，課件共148頁，創(chuàng)作于2023年2月第五章圖第62頁，課件共148頁，創(chuàng)作于2023年2月第63頁，課件共148頁，創(chuàng)作于2023年2月本章總述本章主要討論圖這一重要的數(shù)據(jù)結構。圖不同于線性結構，也不同于樹形結構，在任何兩個頂點之間都可能存在鄰接關系。圖的存儲結構、圖的遍歷以及圖的應用—最小生成樹、拓撲排序。第64頁，課件共148頁，創(chuàng)作于2023年2月本章重點圖的存儲結構和連通圖的遍歷。本章難點

Prim算法。第65頁，課件共148頁，創(chuàng)作于2023年2月名詞和術語網(wǎng)、子圖完全圖、稀疏圖、稠密圖鄰接點、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強連通圖、強連通分量生成樹、生成森林第66頁，課件共148頁，創(chuàng)作于2023年2月圖的存儲結構一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示鄰接表是圖的一種鏈式存儲結構。為圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點Vi的邊（有向圖中指以Vi為尾的?。?。第67頁，課件共148頁，創(chuàng)作于2023年2月鄰接矩陣特點無向圖的鄰接矩陣是對稱矩陣；有向圖的鄰接矩陣不一定是對稱矩陣；判斷任意兩個點的鄰接關系容易；適用于稠密圖的表示。ABDCE0101000100000010010011000ABCDEABCDE第68頁，課件共148頁，創(chuàng)作于2023年2月鄰接表特點無向圖中:頂點Vi的度為第i個單鏈表中的結點數(shù)。有向圖中：頂點Vi的出度為第i個單鏈表中的結點個數(shù)；頂點Vi的入度需遍歷整個鄰接表,鄰接點域指向Vi的結點個數(shù)。第69頁，課件共148頁，創(chuàng)作于2023年2月圖的遍歷從圖中某個頂點出發(fā)訪問圖中每個頂點一次且僅一次的過程。連通圖深度優(yōu)先搜索連通圖廣度優(yōu)先搜索深度優(yōu)先搜索：V0V1V3V7V4V2V5V6廣度優(yōu)先搜索序列：V0V1V2V3V4V5V6V7V0V1V3V4V2V6V5V7第70頁，課件共148頁，創(chuàng)作于2023年2月從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖中的其余頂點，直至圖中所有和V0有路徑相通的頂點都被訪問到為止。連通圖的深度優(yōu)先搜索遍歷第71頁，課件共148頁，創(chuàng)作于2023年2月

從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，隨后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有與V0有路徑相通的頂點都被訪問到為止。連通圖的廣度優(yōu)先搜索遍歷第72頁，課件共148頁，創(chuàng)作于2023年2月最小生成樹問題的提出：假設要在n個城市之間建立通訊聯(lián)絡網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？該問題等價于：構造網(wǎng)的一棵最小生成樹，即：在e條帶權的邊中選取n-1條邊（不構成回路），使“權值之和”為最小。第73頁，課件共148頁，創(chuàng)作于2023年2月最小生成樹構造—普里姆Prim算法指定圖中某個頂點v作為生成樹的根，隨后往生成樹上添加新的頂點w。在添加的頂點w和已經(jīng)在生成樹上的頂點v之間必定存在一條邊，并且該邊的權值在所有連通頂點v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點，直至生成樹上含有n個頂點為止。第74頁，課件共148頁，創(chuàng)作于2023年2月12abcdegf例如:1951418271682137aedcbgf所得生成樹權值和=14+8+3+5+16+21=67第75頁，課件共148頁，創(chuàng)作于2023年2月如何進行拓撲排序？

1.從有向圖中選取一個沒有前驅的頂點，并輸出之；

2.從有向圖中刪去此頂點以及所有以它為尾的??；

重復上述兩步，直至圖空或者圖不空但找不到無前驅的頂點為止。第76頁，課件共148頁，創(chuàng)作于2023年2月3614752初始AOV網(wǎng)361475輸出結點2后36147輸出結點5后3647輸出結點1后367輸出結點4后67輸出結點3后6輸出結點7后空輸出結點6后本章結束第77頁，課件共148頁，創(chuàng)作于2023年2月第六章查找表第78頁，課件共148頁，創(chuàng)作于2023年2月第79頁，課件共148頁，創(chuàng)作于2023年2月本章總述本章主要介紹了查找表和查找的概念，查找表的分類，并分別詳細討論了靜態(tài)查找表與動態(tài)查找表的各種常用的實現(xiàn)方法。散列是一種重要的查找方法。散列技術的原始動機是無需鍵值比較而完成查找。第80頁，課件共148頁，創(chuàng)作于2023年2月本章重點二分查找二叉排序樹的查找散列表的查找本章難點二叉排序樹的插入算法第81頁，課件共148頁，創(chuàng)作于2023年2月查找表概念查找表是由同一類型的數(shù)據(jù)元素(或記錄)構成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著松散的關系，因此查找表是一種應用靈活且方便的結構。第82頁，課件共148頁，創(chuàng)作于2023年2月查找表的常見操作1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。第83頁，課件共148頁，創(chuàng)作于2023年2月查找表的兩個類別：

靜態(tài)查找表僅作查詢和檢索操作的查找表。

動態(tài)查找表有時在查詢之后，還需要將“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結果為“在查找表中”的數(shù)據(jù)元素。第84頁，課件共148頁，創(chuàng)作于2023年2月靜態(tài)查找表一、順序查找表在等概率查找的情況下，順序表查找成功的平均查找長度為：二、有序查找表(二分查找)三、索引順序表靜態(tài)查找表的上述三種不同實現(xiàn)方法各有優(yōu)缺點。順序查找效率最低但限制最少；二分查找效率最高但限制最強；分塊查找則介于上述二者之間。第85頁，課件共148頁，創(chuàng)作于2023年2月動態(tài)查找表--二叉排序樹1．定義2．查找算法3．插入算法4．刪除算法5．查找性能的分析第86頁，課件共148頁，創(chuàng)作于2023年2月二叉排序樹定義二叉排序樹或者是一棵空二叉樹;或者是具有如下特性的二叉樹：（1）若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；（2）若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；（3）它的左、右子樹也都分別是二叉排序樹。

重要性質：中根遍歷一棵二叉樹所得的結點訪問序列是鍵值的遞增序列。第87頁，課件共148頁，創(chuàng)作于2023年2月查找性能的分析對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關鍵字，構造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。第88頁，課件共148頁，創(chuàng)作于2023年2月由關鍵字序列3，1，2，5，4構造而得的二叉排序樹，由關鍵字序列1，2，3，4，5構造而得的二叉排序樹，2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2第89頁，課件共148頁，創(chuàng)作于2023年2月二叉平衡樹是二叉排序樹的另一種形式，其特點為：樹中每個結點的左、右子樹深度之差的絕對值不大于1，即548254821是平衡樹不是平衡樹構造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉技術。第90頁，課件共148頁，創(chuàng)作于2023年2月散列表

1)散列函數(shù)是一個映象，即：將關鍵字的集合映射到某個地址集合上，它的設置很靈活，只要不超出地址集合允許的范圍即可；

2)由于散列函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而H(key1)=H(key2)。第91頁，課件共148頁，創(chuàng)作于2023年2月構造散列函數(shù)的方法對數(shù)字的關鍵字可有下列構造方法：

1.數(shù)字分析法

2.平方取中法

3.基數(shù)轉換法

4.除留余數(shù)法

5.隨機數(shù)法實際造表時，采用何種構造哈希函數(shù)的方法取決于建表的關鍵字集合的情況(包括關鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。第92頁，課件共148頁，創(chuàng)作于2023年2月散列表按照組織形式的不同，通常有兩類散列表：開散列表與閉散列表。開散列表的組織方式：將所有散列地址相同的記錄都鏈接在同一鏈表中。閉散列表解決沖突的基本思想：為每個鍵值生成一個散列地址序列d0d1…di…dm-1

d0=H(K),是K的散列地址，其余di(0<i<m)是后繼散列地址。

線性探測法二次探測法

多重散列法公共溢出區(qū)法散列技術的原始動機是無需鍵值比較而完成查找。但由于同義詞的存在，不能實現(xiàn)。本章結束第93頁，課件共148頁，創(chuàng)作于2023年2月第七章文件第94頁，課件共148頁，創(chuàng)作于2023年2月第95頁，課件共148頁，創(chuàng)作于2023年2月本章總述本章針對在外存儲器中的數(shù)據(jù)，討論了它的組織方法和操作方法。文件結構是以記錄的集合作為邏輯結構。如何有效的實現(xiàn)文件結構是本章的重點。本章著重介紹了順序文件、索引文件以及散列文件等幾種常見的組織方法。第96頁，課件共148頁，創(chuàng)作于2023年2月本章總要求

熟悉文件的概念；熟悉順序文件、索引文件和散列文件的組織方式和操作方式。第97頁，課件共148頁，創(chuàng)作于2023年2月通常將存放在外存中的數(shù)據(jù)稱為文件。文件是由特性相同的記錄所構成的集合，每個記錄由一個或多個數(shù)據(jù)項構成，這是文件的邏輯結構。文件在存儲介質（如磁盤和磁帶）上的實際組織方式稱為文件的存儲結構或物理結構，常見的有四種：順序組織、索引組織、散列組織和鏈組織。文件在外存儲器上組織結構主要有三種：順序文件散列文件索引文件第98頁，課件共148頁，創(chuàng)作于2023年2月

ISAM文件索引順序存取方法ISAM(IndexedSequentialMethod)是一種專為磁盤存取設計的索引順序文件組織方式。

ISAM文件由多級主索引、柱面索引、磁道索引和主文件組成。第99頁，課件共148頁，創(chuàng)作于2023年2月

VSAM文件

VSAM(VirtualStorageAccessMethod)虛擬存儲存取方法，是一種索引順序文件的組織方式，采用動態(tài)索引結構。

B-樹與B+樹定義

B-樹與B+樹的差異

B+樹廣泛的使用在包括VSAM文件在內(nèi)的多種文件系統(tǒng)中。本章結束第100頁，課件共148頁，創(chuàng)作于2023年2月第八章排序第101頁，課件共148頁，創(chuàng)作于2023年2月第102頁，課件共148頁，創(chuàng)作于2023年2月本章總述對于數(shù)據(jù)處理工作，排序是其最基本的運算之一。為了提高計算機的工作效率，人們提出了各種各樣的排序方法和算法。本章重點介紹了5種內(nèi)部排序算法：直接插入排序、快速排序、直接選擇排序、堆排序和歸并排序。另外，也介紹了冒泡排序等。第103頁，課件共148頁，創(chuàng)作于2023年2月本章重點快速排序，堆排序。本章難點堆排序。第104頁，課件共148頁，創(chuàng)作于2023年2月什么是排序？所謂排序是指將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列的過程。例如：下列是一組記錄對應的關鍵字序列

(52,49,80,36,14,58,61,23,97,75)調(diào)整為

(14,23,36,49,52,58,61,75,80,97)第105頁，課件共148頁，創(chuàng)作于2023年2月內(nèi)部排序和外部排序若整個排序過程不需要訪問外存便能完成，則稱此類排序為內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個排序過程不可能在內(nèi)存中完成，則稱此類排序為外部排序。

第106頁，課件共148頁，創(chuàng)作于2023年2月內(nèi)部排序的方法按照內(nèi)部排序過程使用的基本手段可以將排序方法分為5個類別：插入排序交換排序選擇排序歸并排序分配排序第107頁，課件共148頁，創(chuàng)作于2023年2月

1.插入排序不斷地將無序子序列中的記錄“插入”到有序序列中，從而逐漸地增加有序子序列的長度，直到所有記錄都進入有序序列中為止。直接插入排序（基于順序查找）折半插入排序（基于折半查找）第108頁，課件共148頁，創(chuàng)作于2023年2月

2.交換排序不斷地考查待排序列中關鍵字之間的有序性，一旦發(fā)現(xiàn)非有序關系，將其“交換”，直到所有記錄均按照有序性就位為止。冒泡排序快速排序第109頁，課件共148頁，創(chuàng)作于2023年2月

3.選擇排序不斷地從無序子序列中“選擇”關鍵字最小(或最大)者，并將其加入到有序子序列中，以此方法增加有序子序列的長度，直到所有的記錄都進入有序序列中為止。簡單選擇排序堆排序第110頁，課件共148頁，創(chuàng)作于2023年2月

4.歸并排序通過“歸并”兩個或兩個以上的有序子序列，逐步增加有序序列的長度，直到所有的記錄都進入一個有序序列中為止。

2-路歸并排序第111頁，課件共148頁，創(chuàng)作于2023年2月堆排序堆是滿足下列性質的記錄序列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)1234567891011第112頁，課件共148頁，創(chuàng)作于2023年2月rir2ir2i+1通常將該記錄序列看作一棵完全二叉樹，則r2i

是ri

的左孩子；r2i+1

是ri

的右孩子。1236276549817355403498是堆14不第113頁，課件共148頁，創(chuàng)作于2023年2月

堆排序是指利用堆的特性對記錄序列進行排序的一種排序方法?；具^程：1。根據(jù)原始記錄序列創(chuàng)建堆；2。將根與堆中的最后一個結點交換；3。將堆中的最后結點從堆中刪去；4。將剩余的結點重新調(diào)整成堆。第114頁，課件共148頁，創(chuàng)作于2023年2月1、如何“建初堆”？需要解決的兩個問題:2、如何調(diào)整“堆”？第115頁，課件共148頁，創(chuàng)作于2023年2月建“初堆”的基本方法：從堆中最后一個有孩子的結點開始利用調(diào)整。40554973816436122798（40,55,49,73,12,27,98,81,64,36)12368173499881735598494064361227第116頁，課件共148頁，創(chuàng)作于2023年2月9881497355641236274012在98和12進行互換之后，破壞了“堆”的特性，因此，需要對它進行“篩選”。98128173641298第117頁，課件共148頁，創(chuàng)作于2023年2月73496455129836274081在81和12進行互換之后，破壞了“堆”的特性，因此，需要對它進行“篩選”。1281比較1273比較645512第118頁，課件共148頁，創(chuàng)作于2023年2月73644955128198362740在73和12進行互換之后，破壞了“堆”的特性，因此，需要對它進行“篩選”。127312645512第119頁，課件共148頁，創(chuàng)作于2023年2月64554912738198362740在64和40進行互換之后，破壞了“堆”的特性，因此，需要對它進行“篩選”。6440405540第120頁，課件共148頁，創(chuàng)作于2023年2月55404912738198362764在55和27進行互換之后，破壞了“堆”的特性，因此，需要對它進行“篩選”。5527274927第121頁，課件共148頁，創(chuàng)作于2023年2月49402712738198365564在49和36進行互換之后，破壞了“堆”的特性，因此，需要對它進行“篩選”。49364036第122頁，課件共148頁，創(chuàng)作于2023年2月12273640738198495564排序后的記錄序列：{12，27，36，40，49，55，64，73，81，98}第123頁，課件共148頁，創(chuàng)作于2023年2月各種排序方法的綜合比較1.平均的時間性能時間復雜度為O(nlogn)：快速排序、堆排序和歸并排序時間復雜度為O(n2)：直接插入排序、冒泡排序和簡單選擇排序第124頁，課件共148頁，創(chuàng)作于2023年2月2.最壞時間性能時間復雜度為O(nlogn)：堆排序和歸并排序時間復雜度為O(n2)：快速排序、直接插入排序、冒泡排序和簡單選擇排序第125頁，課件共148頁，創(chuàng)作于2023年2月

3.當待排記錄序列按關鍵字順序有序時直接插入排序和起泡排序能達到O(n)的時間復雜度，快速排序的時間性能退化為O(n2)。

4.簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關鍵字的分布而改變。第126頁，課件共148頁，創(chuàng)作于2023年2月

5.空間性能指的是排序過程中所需的輔助空間大小

1.所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復雜度為O(1)；

2.快速排序為O(logn)，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；

3.歸并排序所需輔助空間最多，其空間復雜度為O(n)。本章結束第127頁，課件共148頁，創(chuàng)作于2023年2月考情交流本課程的應試方法和技巧復習技巧最近幾年必考的內(nèi)容考試情況的預測分析歷年考題真題示例講解第128頁，課件共148頁，創(chuàng)作于2023年2月本課程的應試方法和技巧通過對歷年自考試卷的分析和以往教學環(huán)節(jié)的整理總結，我認為這門課程大家學習的時候要以本課程大綱中所確定的識記、領會和應用的有關要求為依據(jù)，同時要求大家認真分析歷屆的真題，抓住考題的方向和規(guī)律，將理論和實際的應用聯(lián)系與結合起來。大家一定要注意，不是書上所有的東西都要背下來，而是要根據(jù)不同的知識結構特點，記住基礎知識，領會基本原理，認真思考實際應用。第129頁，課件共148頁，創(chuàng)作于2023年2月復習技巧1.注意歸納整理2.注意聯(lián)系實際3.熟記基礎理論4.學會獨立思考第130頁，課件共148頁，創(chuàng)作于2023年2月考試題型一、單項選擇題二、填空題三、應用題四、算法設計題第131頁，課件共148頁，創(chuàng)作于2023年2月最近幾年必考的內(nèi)容1這幾年出題頻率高的知識點如下：1.線性表的插入刪除（順序表、鏈表）2.數(shù)組、矩陣的存儲（地址計算）3.二叉樹的相關性質、存儲以及遍歷等算法4.圖的鄰接表存儲第132頁，課件共148頁，創(chuàng)作于2023年2月

5.Prim算法構造最小生成樹

6.散列表的構建及平均查找長度分析

7.構建二叉排序樹

8.排序方法，如：冒泡排序、直接插入排序、快速排序；堆排序的過程（建立初始堆、調(diào)整堆）最近幾年必考的內(nèi)容2第133頁，課件共148頁，創(chuàng)作于2023年2月考試情況的預測分析根據(jù)歷年來的考題分析推理，我預計（只代表個人意見）這門課的出題方向主要集中在以下知識環(huán)節(jié)上：

1.線性表的存儲結構及操作（順序表、鏈表）

2.基本概念理論（棧、循環(huán)隊列的特點等）

3.數(shù)組、矩陣的存儲

4.二叉樹的相關性質、存儲及遍歷算法

5.圖的存儲結構及應用（鄰接矩陣、鄰接表）

6.散列表的構建及平均查找長度分析

7.各種排序方法排序過程及時間復雜度分析第134頁，課件共148頁，創(chuàng)作于2023年2月

1.單項選擇題：若在長度為n的順序表中插入一個結點，則其結點的移動次數(shù)（）。

A、最少為0，最多為n

B、最少為1，最多為n

C、最少為0，最多為n+1

D、最少為1，最多為n+1

答案：A歷年考題真題示例講解第135頁，課件共148頁，創(chuàng)作于2023年2月

2.填空題：對順序表執(zhí)行刪除操作，其刪除算法的平均時間復雜性為

（n-1）/2

。

其他算法定位算法：平均時間復雜性量級為O(n)求表長算法、讀表元算法：時間復雜性為O(1).第136頁，課件共148頁，創(chuàng)作于2023年2月3.選擇題：設一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（D）

A．a(chǎn)，b，c，d B.a，b，d，cC.d，c，b，a D.c，d，a，b第137頁，課件共148頁，創(chuàng)作于2