數(shù)據(jù)結構總復習2025/4/11總復習基本概念一、數(shù)據(jù)結構

1、定義研究數(shù)據(jù)的邏輯結構、物理結構以及它們之間的關系。研究數(shù)據(jù)與數(shù)據(jù)之間的關系。2025/4/11總復習基本概念一、數(shù)據(jù)結構

1、定義

2、研究范圍⑴、各種數(shù)據(jù)結構的性質；⑵、相應的運算；⑶、實現(xiàn)的算法；⑷、算法分析；⑸、數(shù)據(jù)的排序和查找技術。2025/4/11總復習基本概念一、數(shù)據(jù)結構

1、定義

2、研究范圍

3、結構類型線性表、棧與隊列、串、廣義表、樹、圖、文件。2025/4/11總復習基本概念一、數(shù)據(jù)結構

1、定義

2、研究范圍

3、結構類型

4、算法分析算法執(zhí)行時間是根據(jù)算法中關鍵語句的執(zhí)行次數(shù)作出的大體估計。2025/4/11總復習基本概念二、線性表

1、線性表的邏輯特征除第一個元素和最后一個元素外，每個元素均有唯一的直接前趨和唯一的直接后繼。2025/4/11總復習基本概念二、線性表

1、線性表的邏輯特征

2、線性表的物理結構⑴、順序結構特點：邏輯上相鄰的結點，在物理上也相鄰。其一般表示形式是：數(shù)組。⑵、鏈式結構特點：邏輯上相鄰的結點在物理上不一定相鄰。其表示形式是：鏈表。包含：單鏈表、單循環(huán)鏈表、雙循環(huán)鏈表。2025/4/11總復習基本概念二、線性表

1、線性表的邏輯特征

2、線性表的物理結構

3、線性表的運算⑴、訪問⑵、插入⑶、刪除⑷、劃分與合并⑸、查找⑹、排序⑺、建立空表2025/4/11總復習基本概念三、棧與隊列

1、棧與隊列的邏輯特征

(1)、棧符合先進后出原則的線性表。即插入、刪除均在表的一端進行的線性表。

可變化端稱為棧頂，非變化端稱為棧底。

(2)、隊列符合先進先出原則的線性表。即插入在表的一端、刪除在表的另一端進行的線性表。

插入端稱為隊列尾，刪除端稱為隊列頭。2025/4/11總復習基本概念三、棧與隊列

1、棧與隊列的邏輯特征2、棧與隊列的物理結構

(1)、順序結構順序結構的棧和隊列稱為順序棧和順序隊列。對于順序隊列可通過頭尾相接，改為循環(huán)順序隊列。

(2)、鏈式結構鏈式結構的棧和隊列稱為鏈棧和鏈隊列。2025/4/11總復習基本概念三、棧與隊列

1、棧與隊列的邏輯特征2、棧與隊列的物理結構3、棧與隊列的運算

(1)、棧建立空棧、判棧空、判棧滿、進(壓)棧、出(彈)棧。

(2)、隊列建立空隊列、判隊列空、判隊列滿、進隊列、出隊列。2025/4/11總復習基本概念四、串

1、串的運算⑴、求串長⑵、聯(lián)接串⑶、求子串⑷、置換子串⑸、插入子串⑹、刪除子串⑺、復制串2025/4/11總復習基本概念四、串

1、串的運算

2、串的物理結構

(1)、順序結構

(2)、鏈式結構

(3)、等量分塊2025/4/11總復習基本概念五、廣義表

1、特殊矩陣可壓縮存貯的矩陣（用一維數(shù)組存貯）⑴、下三角矩陣（對稱矩陣、上三角矩陣）⑵、三對角矩陣2025/4/11總復習基本概念五、廣義表

1、特殊矩陣2、稀疏矩陣

(1)、邏輯特征非零元素少于三分之一的矩陣。

(2)、物理結構順序結構（三元組）、多重鏈式結構和十字鏈表結構。2025/4/11總復習基本概念六、樹

1、定義一棵樹是結點的有限集合。其中：⑴、必有一個稱為根的結點；⑵、其余結點分成n(≥０)個互不相交稱為其子樹的集合。2025/4/11總復習基本概念六、樹

1、定義

2、樹的有關術語⑴、度結點的度為其孩子的個數(shù)；樹的度為樹中最大結點的度。⑵、層次結點所在的層次為根到該結點路徑上的結點數(shù)。⑶、深度樹的深度為其最大的層次數(shù)。⑷、森林

n（≥０）棵互不相交的樹的集合。2025/4/11總復習基本概念六、樹

1、定義

2、樹的有關術語

3、樹的邏輯特征除根結點以外，每個結點均有唯一的直接前趨，但可以有不止一個的直接后繼。其邏輯表示方式：層次分支、園括號和凹入式。2025/4/11總復習基本概念六、樹

1、定義

2、樹的有關術語

3、樹的邏輯特征

4、樹的物理結構⑴、多重鏈（廣義表）結點中鏈域數(shù)等于樹的度。⑵、雙重鏈左鏈指長子，右鏈指次弟。2025/4/11總復習基本概念六、樹

5、二叉樹⑴、定義二叉樹是結點的有限集合。其中一個結點稱為根，兩個稱為這個根的左子樹和右子樹且互不相交的結點集合。⑵、有關術語①、滿二叉樹深度為k且具有2k-1個結點的二叉樹。②、完全二叉樹深度為k具有n個結點，且與深度為k的滿二叉樹序號從1至n對應的二叉樹。2025/4/11總復習基本概念六、樹

5、二叉樹

⑶、有關性質①、第i層結點數(shù)最多為2i-1個。整棵樹的結點最多為2k-1個。②、n個結點的完全二叉樹的深度k為：

k=[log2n]+1③、在n個結點的完全二叉樹中，對于結點i：其父結點為[i/2]i>1

其左孩子為2i2i<=n

其右孩子為2i+12i+1<=n2025/4/11總復習基本概念六、樹

5、二叉樹

6、二叉樹的遍歷與線索化⑴、前序、中序、后序遍歷（左子樹在右子樹之前）⑵、中序線索二叉樹利用不指孩子的指針域，讓其指線索。左鏈域空，左鏈域指其前趨；右鏈域空，右鏈域指其后繼。增加兩個標志域，標志為0，表示其鏈域是指孩子，標志為1，表示其鏈域是指線索。2025/4/11總復習基本概念六、樹

5、二叉樹

6、二叉樹的遍歷與線索化

7、二叉排序樹樹中結點的值按中序從小到大排序。其構造的方法：⑴、第一個結點為根；⑵、第二個結點若小于前一結點，則為其左子樹，否則為其右子樹；⑶、其余結點如此遞歸。2025/4/11總復習基本概念六、樹

5、二叉樹

6、二叉樹的遍歷與線索化

7、二叉排序樹

8、二叉查找樹與哈夫曼樹⑴、二叉查找樹的評價方法一般二叉查找樹根據(jù)其內(nèi)部路徑長度來評價。加權二叉查找樹根據(jù)其加權外部路徑來評價。（一般是權越大的結點越靠樹根的二叉樹的查找效率越高）2025/4/11總復習基本概念六、樹

5、二叉樹

6、二叉樹的遍歷與線索化

7、二叉排序樹

8、二叉查找樹與哈夫曼樹⑴、二叉查找樹的評價方法⑵、哈夫曼樹最佳加權二叉查找樹。2025/4/11總復習基本概念七、圖

1、定義圖由非空有限的頂點集合與有限的邊的集合構成。Ｇ＝｛Ｖ（Ｇ），Ｅ（Ｇ）｝

圖的邏輯特征：每個結點均可以有不止一個的直接前趨，也可以有不止一個的直接后繼。2025/4/11總復習基本概念七、圖

1、定義

2、有關術語⑴、有向圖與無向圖邊無方向構成無向圖；邊有方向構成有向圖。⑵、完全圖具有最多邊數(shù)的圖。n個頂點的無向圖的最多邊數(shù)為n(n-1)/2，n個頂點的有向圖的最多邊數(shù)為n(n-1)。⑶、網(wǎng)邊擁有權的圖。2025/4/11總復習基本概念七、圖

1、定義

2、有關術語⑷、子圖若有Ｇ’滿足：

V(G')≤V(G)，且E(G')≤E(G)，則Ｇ’為Ｇ的子圖。

⑸、鄰接有邊直接相連的兩個頂點稱為相鄰接。⑹、度與某頂點相鄰接的頂點個數(shù)稱為該頂點的度。對于有向圖還分入度與出度。2025/4/11總復習基本概念七、圖

1、定義

2、有關術語⑺、路徑從某頂點到另一頂點若有邊相連（可經(jīng)過其它頂點），則稱兩頂點之間有路徑。其路徑長度為所經(jīng)過的邊數(shù)。若為網(wǎng)則其路徑長度為所經(jīng)過的邊上權之和。若起點與終點為同一頂點，則此路徑稱為回路。⑻、連通若無向圖中任兩個頂點之間均有路徑，則稱圖是連通的。2025/4/11總復習基本概念七、圖

1、定義

2、有關術語

3、圖的存貯⑴、鄰接矩陣

n個頂點的圖的鄰接矩陣為n階方陣，元素為：┌1(i,j)或<i,j>∈E(G)A[i,j]=│（圖）└0(i,j)或<i,j>不∈E(G)┌Ｗij

(i,j)或<i,j>∈E(G)A[i,j]=│∞(i,j)或<i,j>不∈E(G)（網(wǎng)）└0i=j2025/4/11總復習基本概念七、圖

1、定義

2、有關術語

3、圖的存貯

⑵、鄰接表表頭數(shù)組存放每個頂點，每個表頭指針指向與其相鄰接的頂點構成的鏈表。表頭數(shù)組元素兩個域：頂點、指針域；鏈表中結點兩（或三）個域：頂點、指針（及權）域。2025/4/11總復習基本概念七、圖

1、定義

2、有關術語

3、圖的存貯

⑶、邊集數(shù)組數(shù)組元素為兩（或三）個域：頭頂點、尾頂點（及權）域。數(shù)組元素個數(shù)由圖的邊數(shù)確定。2025/4/11總復習基本概念七、圖

1、定義

2、有關術語

3、圖的存貯

4、圖的遍歷深度、廣度優(yōu)先搜索法。2025/4/11總復習基本概念七、圖

1、定義

2、有關術語

3、圖的存貯

4、圖的遍歷

5、生成樹、最小代價生成樹連通無回路的圖稱為樹；圖的每一個包含所有頂點且構成樹的子圖均稱為其生成樹；生成樹中權值之和最小的為其最小代價生成樹。2025/4/11總復習基本概念七、圖

1、定義

2、有關術語

3、圖的存貯

4、圖的遍歷

5、生成樹、最小代價生成樹

6、圖的拓撲排序在有向圖中排列出各個頂點的先后線性順序，稱為拓撲排序。2025/4/11總復習基本概念八、查找

1、概念⑴、關鍵字數(shù)據(jù)元素中的一個特定數(shù)據(jù)項，用以標識一數(shù)據(jù)元素，以區(qū)別其它數(shù)據(jù)元素。⑵、查找查找關鍵字值等于某給定值的數(shù)據(jù)元素在文件中的位置。2025/4/11總復習基本概念八、查找

1、概念

2、順序表查找⑴、順序查找在文件中按順序依次比較元素的關鍵字值。⑵、折半查找在有序文件中，依次比較某范圍中點的關鍵字值，并縮小查找范圍。2025/4/11總復習基本概念八、查找

1、概念

2、順序表查找

3、索引查找（分塊查找）分級查找，第一步在索引表中查找，進一步在確定的文件某塊中查找。2025/4/11總復習基本概念八、查找

1、概念

2、順序表查找

3、索引查找（分塊查找）

4、散列查找其特點：查找時間與文件大小無關。哈希函數(shù)：直接定址法、平方取中法、質數(shù)除余法、折疊法。處理沖突的方法：開放地址法（線性探測、隨機探測）、鏈地址法、再散列法。影響查找效率的主要因素為裝填因子（裝填度）。2025/4/11總復習基本概念九、排序

1、概念⑴、排序按關鍵字值從小到大（或從大到?。┲匦屡帕性氐奈恢?。⑵、穩(wěn)定性排序期間相同關鍵字元素的相對位置不變，則稱此排序是穩(wěn)定的。2025/4/11總復習基本概念九、排序

1、概念

2、插入排序每次考慮一個元素，將其插入到部分有序文件的適當位置。插入排序有：直接插入排序（較慢）、折半插入排序（中等）、希爾排序（較快）。其中前兩種為穩(wěn)定的，后一種為不穩(wěn)定的。2025/4/11總復習基本概念九、排序

1、概念

2、插入排序

3、選擇排序每次選擇當前范圍內(nèi)的最小元素，將其放在該范圍內(nèi)的第一位。選擇排序有：直接選擇排序（較慢）、堆排序（較快）。前者為穩(wěn)定的，后者為不穩(wěn)定的。2025/4/11總復習基本概念九、排序

1、概念

2、插入排序

3、選擇排序

4、交換排序兩兩元素比較，若反序則交換位置。交換排序有：冒泡排序（較慢）、快速排序（較快）。前者為穩(wěn)定的，后者為不穩(wěn)定的，另外快速排序占用一定的輔助空間。2025/4/11總復習基本概念九、排序

1、概念

2、插入排序

3、選擇排序

4、交換排序

5、歸并排序將文件劃分為幾個有序子文件，再相鄰子文件兩兩歸并，在歸并中排序。此排序較快，排序是穩(wěn)定的，另外占用較大的輔助空間。2025/4/11總復習基本概念九、排序

1、概念

2、插入排序

3、選擇排序

4、交換排序

5、歸并排序

6、基數(shù)排序按關鍵字本身的基數(shù)和位數(shù)排序?；鶖?shù)排序較快，排序為穩(wěn)定的，另外占用的輔助空間是所有排序中最大的。2025/4/11總復習基本操作一、樹

1、二叉樹的遍歷對于給定的二叉樹寫出其前序、中序、后序遍歷序列。

2、二叉樹的線索化對于給定的二叉樹畫出其中序線索二叉樹。

3、構造二叉排序樹對于給定的一組結點值，構造出相應的中序二叉排序樹。

4、哈夫曼樹對于給定的一組權值，畫出相應的哈夫曼樹的構造過程。2025/4/11總復習基本操作二、圖1、作鄰接矩陣與鄰接表對于給定的圖作出其鄰接矩陣，按頂點序號由小到大畫出其鄰接表。

2、遍歷按頂點序號由小到大寫出深度優(yōu)先與廣度優(yōu)先搜索遍歷頂點序列。3、最小代價生成樹對于給定的網(wǎng)能根據(jù)克魯斯卡爾方法寫出其最小代價生成樹的生成過程。

4、拓撲排序對于給定頂點的優(yōu)先關系，畫出其AOV網(wǎng)，通過排列出的拓撲序列，確定該AOV網(wǎng)是否可行。2025/4/11總復習基本操作三、查找

1、哈希函數(shù)典型哈希函數(shù)的使用，平方取中法、質數(shù)除余法、折疊法。

2、沖突處理作出相應開放地址法、鏈地址法的存貯圖。2025/4/11總復習基本操作四、排序

1、排序過程能按排序方法的要求，寫出排序的過程。

2、算法分析根據(jù)某算法，分析所用時間的量級。2025/4/11總復習基本算法一、線性表

1、順序結構⑴、插入結點

a0

a1

……ai……an-1

for(j=n-1;j>=i;j--)/*插入點之后結點依次后移*/

a[j+1]=a[j];a[i]=a;/*新結點插入*/插入點2025/4/11總復習基本算法一、線性表

1、順序結構

a0

a1

……ai……an-1

for(j=i;j<n-1;j++)/*刪除點之后結點依次前移*/

a[j]=a[j+1];刪除點⑵、刪除結點2025/4/11總復習基本算法一、線性表

p=h;while()訪問點

2、鏈式結構訪問結點a0……aa1an-1∧h(p!=NULL)p=p->link;

/*若p不空則指向被訪問結點*/&&(p->data!=a)2025/4/11總復習基本算法二、棧與隊列

1、棧順序棧⑴、進棧s[top]=a;

/*結點先壓入棧頂

*/top++;

/*棧頂指針上推

*/aia1a0topatop2025/4/11總復習基本算法二、棧與隊列

1、棧順序棧--top;

/*棧頂指針下移

*/

a=s[top];

/*結點從棧頂彈出

*/aia1a0topatop⑵、出棧2025/4/11總復習基本算法二、棧與隊列rear=(rear+1)%L;/*隊列尾指針后移

*/q[rear]=a;

/*結點進入隊列尾

*/

2、隊列順序隊列⑴、進隊列frontrearaiajaL-10……rear2025/4/11front總復習基本算法二、棧與隊列front=(front+1)%L;

/*隊列頭指針后移

*/a=q[front];

/*結點從隊列頭取出

*/

2、隊列順序隊列frontaiajaL-10……rear⑵、出隊列2025/4/11

for(i=0;i++)

switch(s[i]){case‘(’:case‘[’:case‘{’: