原創：https://blog.csdn.net/mzj15101229871/article/details/107613162
（博主總結的很完整，很厲害，本人為了查看方便，才轉載的。本人只是個小白~）

第一章 緒論

考試大綱

1）了解數據元素、數據結構、抽象數據類型、存儲結構等概念；了解算法概念及算法設計的基本要求 ；
2）掌握算法分析方法、語句的頻度和估算時間復雜度、空間復雜度分析方法。

考查要點

1．數據結構的研究內容
包括數據的邏輯結構、數據的存儲結構和對數據元素施加的操作（即數據的運算）三方面。
2．算法概念及其評價
五大特性：有窮性、確定性、可行性、輸入性、輸出性;
算法評價：正確性、可讀性、健壯性、高效性、低存儲性;
要特別弄清諸如語句頻度、時間復雜度、空間復雜度等的概念，評價一個算法好壞的兩個主要標準——時間復雜度和空間復雜度。
3．算法和程序的區別
a. 程序不一定滿足有窮性(如操作系統)；
b. 程序中的指令必須是機器可執行的，算法中的指令則無此限制；
c. 算法代表了對問題的解，程序則是算法在計算機上的特定的實現(一個算法若用程序設計語言來描述，它才是一個程序);
d. 數據結構+算法=程序。
4．數據結構的相關概念
數據結構包括數據的邏輯結構和數據的存儲結構。
數據元素是組成數據的基本單位。
數據項是數據不可分割的最小單位。
數據邏輯結構的兩大類型（線性結構、非線性結構）、抽象數據類型（是指一個數學模型以及定義在該模型上的一組操作）。
數據的四種邏輯結構（集合、線性、樹形、圖形）
數據的四種存儲結構（順序、鏈式、索引、散列）
不管是順序存儲結構還是鏈式存儲結構，都要存儲數據元素本身和數據元素之間的關系
順序存儲結構、鏈式存儲結構都可存各種邏輯結構
5．數據邏輯結構、存儲結構的區別和聯系
區別：數據的邏輯結構是一個數學模型；數據的存儲結構是數據的邏輯結構在計算機內部的存儲方式。
聯系：一種邏輯結構可以用多種存儲結構來存儲；一種存儲結構可以用來存多種邏輯結構。

課后習題

一、填空題

1. 數據結構包括數據的邏輯結構、數據的存儲結構和 數據的運算 。
2. 數據的邏輯結構可以分為 線性 和 非線性 兩大類型。
3. 在算法正確的前提下，評價一個算法好壞的兩個主要標準是 時間復雜度 和 空間復雜度 。
4. 對于給定的n個元素,可以構造出的邏輯結構有線性、樹形 、 圖形 和 集合 四種。
5. 數據的存儲結構不僅有順序存儲結構、鏈式存儲結構，還有 索引存儲結構 和 散列存儲結構 。
6. 組成數據的基本單位是 數據元素 。
7. 數據結構的兩個要素是 數據元素 和 數據元素之間的關系 。
8. 語句頻度是 語句重復執行的次數 。
9. 算法是 對特定問題求解步驟的一種描述，是指令的有限序列 。
10. 數值計算問題是 操作對象之間的關系可以用數學方程加以描述的問題 ；非數值計算問題是 操作對象之間的關系不能用數學方程加以描述的問題 。
11. 程序是 算法在計算機上的特定的實現 。
12. 抽象數據類型是 指一個數學模型以及定義在該模型上的一組操作 。
13. 學習數據結構課程的目的是 非數值計算問題的程序設計 。
14. 算法可用 自然語言、流程圖、N-S圖、計算機語言、偽碼語言等 描述。
15. 存儲密度是 一個結點中數據元素所占的存儲單元和整個結點所占的存儲單元之比 。

二、簡答題

1. 試說明算法與程序有哪些區別？ 答：至少有四點區別：
   （1）程序不一定滿足有窮性(如操作系統)；
   （2）程序中的指令必須是機器可執行的，算法中的指令則無此限制；
   （3）算法代表了對問題的解，程序則是算法在計算機上的特定的實現(一個算法若用程序設計語言來描述，它才是一個程序);
   （4）數據結構+算法=程序。
2. 舉一個數據結構的例子，敘述其邏輯結構、存儲結構和運算（操作）三方面的內容。 答：例如有一張學生成績表，記錄了一個班的學生各門課的成績。按學生的姓名為一行記成的表，這個表就是一個數據結構。每個記錄（有姓名、學號、成績等項）就是一個結點，對于整個表來說，只有一個開始結點（它的前面無記錄）和一個終端結點（它的后面無記錄），其它的結點則各有一個也只有一個直接前趨和直接后繼（它的前面和后面均有且只有一個記錄）。這幾個關系就確定了這個表的邏輯結構——線性結構。
   那么我們怎樣把這個表中的數據存儲到計算機里呢? 用高級語言如何表示各結點之間的關系呢?
   是用一片連續的內存單元來存放這些記錄（如用數組存儲，亦即順序存儲）還是隨機存放各結點數據再用指針進行鏈接（鏈式存儲）呢?
   這就是存儲結構的問題，我們都是從高級語言的層次來討論這個問題的。
   最后，我們有了這個表（數據結構），肯定要用它，那么就是要對這張表中的記錄進行查詢、修改、刪除等操作，對這個表可以進行哪些操作以及如何實現這些操作就是數據的運算（操作）問題了。
3. 什么叫算法效率？如何度量算法效率？
   答：算法效率包括時間效率和空間效率。時間效率指算法運行得有多快；空間效率關心算法需要的額外空間。算法效率通常用時間復雜度和空間復雜度來度量。
4. 數據的邏輯結構與存儲結構的區別和聯系是什么？
   答：區別：數據的邏輯結構是一個數學模型；數據的存儲結構是數據的邏輯結構在計算機內部的存儲方式。
   聯系：一種邏輯結構可以用多種存儲結構來存儲；一種存儲結構可以用來存多種邏輯結構。
5. 算法有什么特性？評價一個算法有幾個標準？
   答：一個算法應該具有以下五個特性：
   (1)有窮性。 一個算法必須總是在執行有窮步之后結束,且每一步都在有窮時間內完成 (有限步完成）。
   (2)確定性。算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口（無二義性）。
   (3)可行性。一個算法是可行的。即算法描述的操作都是可以通過已經實現的基本運算執行有限次來實現的（每一步都可通過執行有限次基本操作實現）。
   (4)輸入性。一個算法有零個或多個輸入,這些輸入取自于某個特定的對象集合(有零個或多個輸入）。
   (5)輸出性。一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量（有一個或多個輸出）。
   評價一個算法有以下幾個標準:
   (1)正確性。算法應滿足具體問題的需求。
   (2) 可讀性。 算法應該好讀。以有利于閱讀者對程序的理解。
   (3)健壯性。算法應具有容錯處理。當輸入非法數據時，算法應對其作出反應，而不是產生莫名其妙的輸出結果。
   (4)高效性。指算法執行的時間和執行過程中所需要的最大存儲空間要少。一般，這兩者與問題的規模有關。

思維導圖

第二章 線性表

考試大綱

1）理解線性表的定義和基本操作；線性表的抽象數據類型定義；
2）掌握線性表的順序存儲結構及應用方法；
3）掌握線性表的鏈式存儲結構(單鏈表,雙鏈表,循環鏈表)。

具體要求

要求掌握線性表的順序存儲方式下的元素插入、元素刪除及線性表遍歷算法；要求掌握線性表的鏈式存儲方式下，元素的插入、元素的刪除及線性表遍歷算法（帶頭結點及不帶頭結點的單鏈表）

考查要點

1．線性表的定義
從數據對象、元素間的關系、基本操作三方面進行闡述。
2．線性表的兩種存儲結構及其優缺點
線性表的順序存儲是指在內存中用地址連續的一塊存儲空間對線性表中的各元素按其邏輯順序依次存放，用這種存儲形式存儲的線性表稱為順序表。線性表的鏈式存儲結構是用一組任意的存儲單元存儲線性表的各個數據元素。為了表示線性表中元素的先后關系，每個元素除了需要存儲自身的信息外還需保存直接前趨元素或直接后繼元素的存儲位置。所以，鏈式存儲結構的線性表其元素之間的邏輯關系是通過結點的指針域來表示的。
順序存儲有三個優點:
（1）方法簡單，用數組，容易實現。
（2）不用為表示結點的邏輯關系而增加額外開銷。
（3）具有按元素序號隨機訪問的特點。
兩個缺點：
（1）進行插入、刪除時，平均移動表中一半的元素，
效率較低。
（2）需預先分配足夠大的存儲空間。空間估計過大，會導致空間閑置（造成浪費）；預先分配過小，又會造成溢出。
鏈表的優缺點恰好與順序表相反。
與線性表兩種存儲結構有關的知識有：線性表中邏輯上相鄰的兩個元素其存放位置不一定相鄰；線性表的鏈式存儲表示不一定優于順序存儲表示；鏈式存儲方式以指針表示結點間的邏輯關系;一個需經常作插入、刪除運算的線性表應采用鏈式存儲結構；線性表元素個數穩定、很少進行插入和刪除操作應采用順序存儲結構；若線性表最常用的操作是存取第 i 個元素及其前驅元素的值，則采用順序存儲方式最節省運算時間；在順序存儲結構、鏈式存儲結構上刪除元素的平均時間復雜度。
3．線性表的建立、插入、刪除、輸出
順序表的類型定義、插入、刪除，單鏈表的建立（頭插建立、尾插建立）、插入（后插的基本操作）、刪除、輸出歷來都是重點。
如刪除順序表中某元素多少元素需移動、在順序表中插入一個元素有多少元素需移動等。
再如在一個單鏈表的p所指的結點之后插入一個s所指的結點的操作、根據單鏈表結點類型定義寫出帶頭結點單鏈表的升序插入、在帶頭結點單鏈表中查找元素并返回其地址、刪除帶頭結點單鏈表中某元素、統計帶頭結點單鏈表中元素個數算法（函數）。

例1：設有一帶頭結點的數據域為整型數據的單鏈表h，給出單鏈表結點類型定義，并設計算法輸出單鏈表中的所有元素。

typedef struct node{ int data;struct node *next;} slnode;     
void output(slnode *h){ slnode *p;p=h->next;  while(p!=null){  printf(“%d”,p->data);p=p->next;	         	      }}

例2 設有一帶頭結點的數據域為整型數據的單鏈表H，給出單鏈表結點類型定義，并設計算法統計單鏈表中元素x的個數。

typedef struct node{ int data;struct node *next;} slnode;      
int tj(slnode *H){ slnode *p;int n=0;                       p=H->next;  while(p!=NULL){  if (p->data==x)  n++;p=p->next;	         	      }return n; }

4．單鏈表頭結點的作用：簡化運算。

課后習題

------------------------------------------ 順序表 ------------------------------------------
一.填空題

1. 當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取 線性表中的元素時，應采用 順序 存儲結構。
2. 線性表L=（a1,a2,…,an）用數組表示，假定刪除表中任一元素的概率相同，則刪除一個 元素平均需要移動元素的個數是（n-1）/2 。
3. 順序表中查找某個元素時，從前到后查找與從后到前查找的時間復雜度 相 同。
4. 在具有n個元素的順序表中插入一個元素，合法的插入位置有 n+1 個。
5. 在一個長度為n 的順序表中第i 個元素（1<=i<=n）之前插入一個元素時，需向后移動n-i+1 個元素。
6. 順序存儲結構的線性表中所有元素的地址 一定 連續。
7. 順序存儲結構的線性表其物理結構與邏輯結構是 一致 的。
8. 在具有n個元素的順序存儲結構的線性表任意一個位置中插入一個元素，在等概率條件下，平均需要移動 n/2 _個元素。
9. 在具有n個元素的順序存儲結構的線性表任意一個位置中刪除一個元素，在等概率條件下，平均需要移動__（n-1）/2 __個元素。
10. 在具有n個元素的順序存儲結構的線性表中查找某個元素,平均需要比較（n+1）/2次。
11. 順序存儲結構的線性表中，插入或刪除某個元素時，元素移動的次數與其位置 有 關（填有或無）。
12. 順序存儲結構的線性表中，訪問第i個元素與其位置 無 關。（填有或無）。
13. 在具有n個元素的順序存儲結構的線性表中要訪問第i個元素的時間復雜度是 O(1) 。
14. 在順序表L中的i個位置插入某個元素x，正常插入時，i位置以及i位置以后的元素需要后移，首先后移的是 最后一 個元素。
15. 要刪除順序表L中的i位置的元素x，正常刪除時，i位置以后的元素需要前移，首先前移的是 第i+1個元素(或i+1位置上的元素)。
16. 在具有n個元素的順序存儲結構的線性表中插入某個元素的時間復雜度是 O(n) 。
17. 若順序表中的元素是從1位置開始存放的，要刪除具有n個元素的順序表中某個元素，合法的刪除位置是 1到n 。
18. 在具有n個元素的順序存儲結構的線性表中刪除某個元素的時間復雜度是 O(n) 。
19. 什么是順序存儲結構？順序存儲結構的優點和缺點各是什么？ 答：順序存儲結構是把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中。通常用數組實現。
    順序存儲有三個優點:
    （1）方法簡單，用數組，容易實現。
    （2）不用為表示結點的邏輯關系而增加額外開銷。
    （3）具有按元素序號隨機訪問的特點。
    順序存儲有兩個缺點：
    （1）進行插入、刪除時，平均移動表中一半的元素，效率較低。
    （2）需預先分配足夠大的存儲空間。空間估計過大，會導致空間閑置（造成浪費）；預先分配過小，又會造成溢出。

------------------------------------------ 鏈表------------------------------------------
一.填空題

1. 單鏈表中增加頭結點的目的是為了 簡化操作 。
2. 用單鏈表方式存儲線性表，每個結點需要兩個域，一個是數據域，另一個是 指針域 。
3. 在一個單鏈表的p所指的結點之后插入一個s所指的結點，應執行的操作是：s->next=p->next 和 p->next =s 。
4. 某帶頭結點的單鏈表的頭指針為head，判定該鏈表為空的條件是 head->next==NULL。
5. 在帶有頭結點的單鏈表HL中，要在首元素之前插入一個由指針p指向的結點，則應執行p->next=HL->next及 HL->next=p 操作。
6. 設指針變量p指向單鏈表中某結點A，則刪除結點A的后繼結點需要的操作為p->next=p->next->next （不考慮存儲空間的釋放）。
7. 鏈式存儲結構的線性表其元素之間的邏輯關系是通過結點的 指針 域來表示的。
8. 單循環鏈表L中指針P所指結點為尾結點的條件是 P->next==L 。
9. 訪問具有n個結點的單鏈表中任意一個結點的時間復雜度是 O(n) 。
10. 在單鏈表L中，指針P所指的結點有后繼結點的條件是_ P->next!=NULL__。
11. 鏈式存儲結構的線性表中所有元素的地址 不一定 連續。
12. 鏈式存儲結構的線性表中，插入或刪除某個元素所需的時間與其位置 無 關（填有或無）
13. 在單鏈表L中，指針P所指的結點為尾結點的條件是_ P->next==NULL__。
14. 頭插法建立單鏈表時，元素的輸入順序與在鏈表中的邏輯順序是 相反 的。
15. 尾接法建立單鏈表時，元素的輸入順序與在鏈表中的邏輯順序是 相同 的。
16. 若要將一個單鏈表中的元素倒置，可以借助 頭插法 建立單鏈表的思想將鏈表中的結點重新放置。
17. 線性表用鏈式存儲結構存儲比用順序存儲結構存儲所占的存儲空間 不一定 多（填一定或不一定）。
18. 線性表中邏輯上相鄰的兩個元素其存放位置 不一定 相鄰。
19. 什么是鏈式存儲結構？鏈式存儲結構的優點和缺點各是什么？
    答：鏈式存儲結構是對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關系通過附加的指針字段來表示。通常用指針來實現。
    鏈式存儲有兩個優點：
    （1）進行插入、刪除時，不需移動表中的元素，只需修改指針，效率較高。
    （2）不需預先分配存儲空間，當需要存儲空間時，臨時開辟空間，不會造成空間浪費。
    鏈式存儲有三個缺點:
    （1）方法比順序存儲復雜，不易實現。
    （2）為表示結點的邏輯關系需要增加額外空間。
    （3）不具有按元素序號隨機訪問的特點。
20. 單鏈表中頭指針、頭結點和第一個結點（開始結點）三者的區別是什么？
    答：頭指針是頭結點（或第一個結點）的地址。
    單鏈表如果不帶頭結點的話，頭指針是第一個結點的地址；單鏈表如果帶頭結點的話，頭指針是頭結點的地址。
    頭結點是第一個結點前面的一個結點，它的數據域無定義，指針域中存放的是第一個數據結點的地址，空表時為空。
    第一個結點就是第一個存放數據的結點。

思維導圖

第三章 棧和隊列

考試大綱

1）理解棧的定義和基本操作及棧的抽象數據類型定義；
2）掌握順序棧及鏈式棧的操作方法；
3）掌握棧在遞歸算法、 算術表達式求值及其它應用。
4）理解隊列的定義和基本操作及隊列的抽象數據類型；
5）掌握順序隊列的操作方法，了解鏈式隊列的操作方法；

具體要求

要求掌握棧的順序存儲和鏈式存儲兩種方式下入棧、出棧的算法；循環隊列的順序存儲方式下，入隊和出隊算法。

考查要點

1．棧和隊列的概念、特點
如：棧和隊列是特殊的線性表
棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。
同一棧內各元素的類型必須一致
棧是限定僅能在表尾一端進行插入、刪除操作的線性表；
隊列是限定僅能在表頭進行刪除、表尾進行插入的線性表；
棧的特點是后進先出；
隊列的特點是先進先出。
若將1，2，3按先后次序入棧，出棧順序不可能為3，1，2
在作進棧運算時應先判別棧是否已滿，在作退棧運算時應先判別棧是否已空，當棧中元
素為n個，作進棧運算時發生上溢，則說明該棧的最大容量為n。

2．順序棧、鏈棧、循環隊列、鏈隊列 如循環隊列解決什么問題？假溢出 循環隊列隊空、隊滿判斷： 在少用一個存儲單元的前提下 front ==
rear時隊空； (rear + 1) % maxsize == front 時隊滿。
例：循環隊列用數組A[0…m-1]存放其元素值，已知其頭尾指針分別為front和rear,則當前元素個數為 (rear-front+m)
% m； 為了解決普通順序存儲結構隊列的“假溢出”現象，節約內存單元，通過在隊列操作中加入 數學中的求余運算，可以將其構造成循環隊列；
在循環隊列中，為了能夠區分隊滿和隊空，往往少用一個元素空間。在這種情況下，隊滿的 條件是尾指針+1等于頭指針。

3．什么情況下要用棧？什么情況下要用隊列？
后進先出；先進先出。
如括號匹配、圖的深度遍歷等用棧實現。
二叉樹的層次遍歷、圖的廣度遍歷等用隊列實現。
例：解決計算機與打印機之間速度不匹配問題，須設置一個數據緩沖區，應是一個隊列結構。

4.棧容量大小判斷
如設棧S和隊列Q的初始狀態均為空，元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進入隊列Q，若6個元素出隊序列為 e2,e4,e3,e6,e5,e1, 則棧S的容量至少為多少？（至少為3）。

5.對同一問題的求解程序,遞歸程序無論時間還是空間都不如非遞歸程序。
例：對同一問題的求解程序,遞歸程序比非遞歸程序要花費更多的時間；
任何一個遞歸過程都可以轉換成非遞歸過程；

思維導圖

課后習題

一.填空題

1. 為了解決普通順序存儲結構隊列的“假溢出”現象，節約內存單元，通過在隊列操作中 加入數學中的 求余 運算，可以將其構造成循環隊列。
2. 解決計算機與打印機之間速度不匹配問題，須設置一個數據緩沖區，應是一個 隊列 結構。
3. 循環隊列是為了解決 假溢出 問題而將一個順序表想像成一個首尾相接的順序表。
4. 在循環隊列中，如果其頭指針為front，隊列中元素個數為len，則該隊列為空隊的條件 是 len==0 。
5. 隊列的插入操作在 隊尾 進行。
6. 隊列的刪除操作在 隊頭 進行。
7. 一個棧的輸入序列是：1，2，3 則不可能的棧輸出序列是 3，1，2 。
8. 隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是 先進先出（或后進后出） 。
9. 隊列的特點是 先進先出（或后進后出） 。
10. 隊列 稱作先進先出表。
11. 棧和隊列是兩種 操作受限制的 線性表。
12. 在作進棧運算時要判別棧是否 已滿 。
13. 在作退棧運算時要先判別棧是否 已空 。
14. 在循環隊列中，為了能夠區分隊滿和隊空，往往少用一個元素空間。在這種情況下，隊 滿的條件是 (rear + 1) % MAXSIZE == front ( 假定循環隊列的最大容量為MAXSIZE，隊首是front，隊尾是rear)。
15. 棧的特點是 先進后出（或后進先出） 。

二.簡答題

• 循環隊列的優點是什么？如何判別循環隊列的"空"或"滿"？ 答：循環隊列的優點是：它可以克服順序隊列的"假上溢"現象，能夠使存儲隊列的向量空間得到充分的利用。
  判別循環隊列的"空"或"滿"通常有兩種方法： （1）另設一個變量num記錄當前隊列中的元素個數,當num == 0時隊空，
  num==maxsize時隊滿。 （2）少用一個存儲單元(即少存一個元素), 隊空條件為front = =rear，隊滿條件為(rear +1) % maxsize == front 。

• 棧的特點是什么？隊列的特點是什么？ 答：棧的特點是先進后出，隊列的特點是先進先出。

• 什么是遞歸？遞歸有什么優點？ 答：一個直接調用自己或通過一系列調用間接調用自己的過程稱為遞歸。 遞歸程序結構清晰，可讀性強，而且容易用數學歸納法來證明程序的正確性。

• 什么是棧頂？什么是棧底？ 答：允許插入和刪除的一端是棧頂。
  不允許插入和刪除的一端是棧底。

• 出棧和讀棧頂元素有無區別？若有，其區別是什么？ 答：出棧和讀棧頂元素有區別。在棧s存在且非空的情況下，出棧是將棧s的頂部元素從棧中刪除，棧中少了一個元素，棧發生變化；讀棧頂元素是讀棧頂元素，棧不變化。

• 鏈棧和單鏈表有什么相同點和不同點？ 答：鏈棧實際就是不帶頭結點的單鏈表。其結構完全一樣，不同的是鏈棧只允許頭插、頭刪，而單鏈表可在其它位置插入和刪除。

• 鏈隊列和單鏈表有什么相同點和不同點？ 答：相同點：結點類型相同。
  不同點：鏈隊列只允許頭刪、尾插，而單鏈表可在其它位置插入和刪除。

• 什么是順序表？什么是順序棧？兩者之間有什么聯系和區別？ 答：線性表的順序存儲是指在內存中用地址連續的一塊存儲空間對線性表中的各元素按其邏輯順序依次存放，用這種存儲形式存儲的線性表稱為順序表。利用順序存儲方式實現的棧稱為順序棧。順序棧是順序表的特殊情況，順序棧只允許在棧頂插入和刪除，而順序表可在其它位置插入和刪除。

• 設棧S和隊列Q的初始狀態均為空，元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進入隊列Q，若6個元素出隊序列為 e2,e4,e3,e6,e5,e1, 則棧S的容量至少為多少？寫出其分析過程。 答：至少為3（分析過程略）。

補充

1、利用棧實現表達式的轉換（中綴轉后綴，中綴賺前綴）

1. 中綴轉后綴

利用棧將中綴表達式轉化成后綴表達式
目的：將中綴表達式（即標準形式的表達式）轉換為后綴式。
例子：a+bc+(de+f)g轉換成abc+def+g+

轉換原則

1. 遇到操作數, 直接輸出

2. 操作符的優先級為 () 最大, * / 次之, ± 最小. 遇到操作符后, 假如操作符堆棧為空, 則直接壓入操作符, 否則判斷當前操作符與棧頂操作符的優先關系, 假如棧頂操作符的優先級大于 等于當前操作符的優先級, 那么彈出棧頂操作符, 持續彈出,
   直到棧頂操作符優先級小于當前操作符優先級或棧為空. 最后將當前操作符入棧

3. 如果遇到右括號, 那么將棧頂操作符彈出, 持續彈出直到遇到左括號, 左括號彈出但不輸出

4. 表達式讀入完畢, 若棧不為空, 則持續彈出棧頂操作符, 直到棧為空

2. 中綴轉前綴

建立一個棧來保存運算符，和一個字符容器存字符及運算符的輸出。 從后向前掃描中綴表達式： 1、如果遇到的是普通字符那么存入容器中
2、如果遇到的是‘）’，存入容器中 3、如果遇到的是運算符(大于等于棧頂的優先級就入棧，否則彈棧)
如果當前棧為空或者當前運算符的優先級大于等于棧頂元素的優先級，那么入棧。 如果棧頂元素是‘）’，還是入棧。
如果當前運算符的優先級小于棧頂元素的優先級，那么彈棧存入容器中，一直到棧頂元素為‘）’或
者當前運算符的優先級大于或者等于棧頂元素的優先級。將當前運算符入棧。 4、如果遇到‘（’，那么彈棧存入容器一直遇到到‘）’，將‘）’彈出
5、返向輸出容器中的字符

2、鏈棧進棧出棧代碼實現

第四章 串

考試大綱

1）了解字符串的定義和基本操作及字符串的存儲結構；
2）了解字符串的基本操作；
3）了解字符串模式匹配應用。
了解基本概念即可，不做重點處理

第五章 數組與矩陣廣義表

考試大綱

1）理解數組的定義和基本操作；
2）掌握數組的順序存儲結構及應用；
3）掌握特殊矩陣和稀疏矩陣的壓縮存儲。

具體要求

掌握三角矩陣的壓縮存儲方法和稀疏矩陣三元組法的壓縮存儲方法。

考察要點

元素值 行下標 列下標
0 5 4 4 //第一行，元素值表示該矩陣中稀疏元素的個數，行下標值該矩陣的行數，列下標指該矩陣的列數。
1 1 0 3
2 3 1 2
3 2 1 3
4 1 2 0
5 2 3 1

課后習題

一.填空題

1. 將10階的下三角矩陣A按列優先順序壓縮存儲在一維數組C中，則C數組的大小應為55 。
2. 已知二維數組A[10][20]采用行優先方式存儲，每個元素占2個存儲單元,并且A[0][0]的 存儲地址是1000, 則A[2][8]的存儲地址是 1096 。
3. 對5×5的下三角矩陣進行壓縮存儲時，如果每個元素要占3個字節，共需的存儲單元數為 45 個。
4. 設數組B[0…3，1…5]，數組中的任一元素B[i，j]均占兩個單元，從首地址SA開始，把 數組B按行序為主序進行存放，則元素B[3，4]的地址為 SA+36 。
5. 已知具有n個元素的一維數組采用順序存儲結構，每個元素占k個存儲單元，第一個元素的地址為LOC(a1)，那么，LOC(ai)= LOC(a1)+（i-1）*k 。
6. 字符串（簡稱串）是一種特殊的線性表，它的 數據元素 僅由一個字符組成。
7. 字符串和線性表一樣，它通常采用的存儲方式也是 順序存儲 和 鏈式存儲 。
8. 二維數組的順序存儲可以采用以行為主序存儲，也可采用 以列為主序 存儲。
9. 值相同元素或者零元素分布有一定規律的矩陣稱為 特殊矩陣 。
10. 對稱矩陣是滿足 aij= aji(0 i,j n-1) 條件的矩陣。
11. 有較多值相同元素或較多零元素，且值相同元素或者零元素分布沒有一定規律的矩陣稱 為 稀疏矩陣 。
12. 稀疏矩陣的壓縮存儲除了要保存非零元素的值外，還要保存非零元素在矩陣中的 行和列 。
13. 矩陣壓縮存儲是指為多個值相同的元素分配一個存儲空間，對 值為0的元素 不分配存儲空間。
14. 稀疏矩陣的壓縮存儲通常采用 三元組表 和 十字鏈表 存儲。
15. n階對稱矩陣元素可以只存儲下三角部分，共需 n(n+1)/2 個單元的空間。

二.簡答題

1. 簡述下列術語：空串與空白串，主串和子串，串值和串名。 答：空串與空白串：串中所包含的字符個數稱為該串的長度。長度為零的串稱為空串，它不包含任何字符。僅由一個或多個空格組成的串稱為空白串。空串和空白串不同，例如“
   ”和“”分別表示長度為1的空白串和長度為0的空串。 主串與子串：串中任意連續的字符組成的子序列稱為該串的子串。包含子串的串相應的稱為主串。
   串值和串名：串是零個或多個字符組成的有限序列。一般記作S=“a1a2a3…an”，其中ai(1≦i≦n)
   是一個任意字符，可以是字母、數字或其它字符，S 是串名，引號引起來的字符序列為串值。
2. 按以行序為主序的存儲順序，列出四維數組a[2][3][2][4]中所有元素在內存中的存儲順 序。
   答：
   a[0][0][0][0]、a[0][0][0][1]、a[0][0][0][2]、a[0][0][0][3]、
   a[0][0][1][0]、a[0][0][1][1]、a[0][0][1][2]、a[0][0][1][3]、
   a[0][1][0][0]、a[0][1][0][1]、a[0][1][0][2]、a[0][1][0][3]、
   a[0][1][1][0]、a[0][1][1][1]、a[0][1][1][2]、a[0][1][1][3]、
   a[0][2][0][0]、a[0][2][0][1]、a[0][2][0][2]、a[0][2][0][3]、
   a[0][2][1][0]、a[0][2][1][1]、a[0][2][1][2]、a[0][2][1][3]、
   a[1][0][0][0]、a[1][0][0][1]、a[1][0][0][2]、a[1][0][0][3]、
   a[1][0][1][0]、a[1][0][1][1]、a[1][0][1][2]、a[1][0][1][3]、
   a[1][1][0][0]、a[1][1][0][1]、a[1][1][0][2]、a[1][1][0][3]、
   a[1][1][1][0]、a[1][1][1][1]、a[1][1][1][2]、a[1][1][1][3]、
   a[1][2][0][0]、a[1][2][0][1]、a[1][2][0][2]、a[1][2][0][3]、
   a[1][2][1][0]、a[1][2][1][1]、a[1][2][1][2]、a[1][2][1][3]、
3. 給定整型數組b[3][5]，已知每個元素占2個字節，b[0][0]的存儲地址為1200，試求在行 序為主序的存儲方式下： （1） b[2][4]的存儲地址。 （2） 該數組占用的字節個數。 答：（1）loc(b[2][4])=
   loc(b[0][0])+(25+2)2=1200+24=1224 應該是：loc(b[2][4])=
   loc(b[0][0])+(25+4)2=1200+28=1228 （2）352=30
4. 已知數組A[8][10]，問按列存儲數組元素時A[4][6]的起始地址與數組A按行存儲時的哪 一個元素的起始地址相同？稀疏矩陣的壓縮存儲有哪兩種方法？ 答：（1）假定每個元素占L個存儲單元，按列存儲時loc(A[4][6])=
   loc(A[0][0])+(86+4)L， 設其與數組A按行存儲時的A[i][j]的起始地址相同，則
   loc(A[0][0])+(86+4)L = loc(A[0][0])+(10i+j)L 即86+4=10i+j
   所以i=5，j=2 也就說，數組A[8][10]按列存儲數組元素時A[4][6]的起始地址與數組A按行存儲時A[5][2]的起始地址相同。
   （2）稀疏矩陣的壓縮存儲有三元組表和十字鏈表兩種存儲方法。
5. 什么是稀疏矩陣的三元組表存儲？試寫出以下矩陣A的三元組順序表。
   答：存儲稀疏矩陣非零元素的值、所在行和列，以及稀疏矩陣非零元素的個數、行數、列數的順序存儲叫稀疏矩陣的三元組表存儲。 矩陣A的三元組順序表為： A=( (4,6,5), (1,3,1), (1,5,2), (2,1,3), (3,4,4), (4,2,5)
   ) （用A[0]存儲稀疏矩陣行數、列數、非零元個數）
6. 設A是一個具有m 行n列的元素的二維數組，每個元素占用s 個存儲單元， Loc(aij )為元素aij 的存儲地址，Loc(a00 ) 是a00存儲位置, 也是二維數組A的基址。若以行序為主序的方式存儲二維數組，則元素aij
   的存儲位置是什么？若以列序為主序的方式存儲二維數組，則元素aij 的存儲位置又是什么？ 答：若以行序為主序的方式存儲二維數組，則元素aij
   的存儲位置為： Loc(aij ) = Loc(a00 ) +（ni+j ) s 若以列序為主序的方式存儲二維數組，則元素aij
   的存儲位置為：
   Loc(aij ) = Loc(a00) +（mj+i ) s
7. 什么是字符串？它和線性表有什么聯系和區別？ 答：字符串（簡稱串）是一種特殊的線性表，它的數據元素僅由一個字符組成。 字符串的邏輯結構、存儲結構和線性表一樣，除第一個元素外，其它每一個元素有一
   個且僅有一個直接前驅，除最后一個元素外，其它每一個元素有一個且僅有一個直接后繼，它通常采用的存儲方式也是順序存儲和鏈式存儲。字符串和線性表的區別僅在于，線性表中的數據元素可以是任意數據，而字符串中的數據元素只能是一個字符。
8. 什么是三角矩陣？如何將三角矩陣存儲到一個一維數組中？ 答：以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數。下三角矩陣正好相反，它的主對角線上方均為常數，如圖所示。在大多數情況下，三角矩陣常數為零。
   a00 a01 … a0n-1 a00 c … c
   c a11 … a1n-1 a10 a11 … c
   …………………… …………………
   c … c an-1n-1 an-10 an-11 … an-1n-1
   (a)上三角矩陣 (b)下三角矩陣 三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到一維數組sa[0…n(n+1)/2]中，其中c存放在數組的最后一個分量中。
   上三角矩陣中，主對角線之上的第p行(0≦p<n)恰有n-p個元素，按行優先順序存放上三角矩陣中的元素aij時，aij之前的i行一共有

個元素，在第i行上，aij前恰好有j-i個元素：aii,aii+1,…,aij-1。因此，sa[k]和aij的對應關系是：
當i≦j k= i(2n-i+1)/2+j-i
當i>j k=n(n+1)/2 下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應關系是：
當i≧j k=i(i+1)/2+j
當i<j k=n(n+1)/2

思維導圖