第2章 順序表及其順序存盤
目錄- 一、線性表
- 二、順序表
- 2.1 順序表的基本概念及描述
- 2.2 順序表的實作
- 2.2.1 順序表的存盤結構
- 2.2.2 順序表的插入操作（演算法）
- 2.2.3 順序表的洗掉操作（演算法）
- 三、堆疊
- 3.1 堆疊的基本概念及描述
- 3.2 順序堆疊及其實作
- 3.2.1 順序堆疊的存盤結構
- 3.3 堆疊的應用之一（括號匹配）
- 3.4 堆疊的應用之二（算術運算式求值）
- 3.4.1 中綴運算式轉換為后綴運算式步驟
- 四、佇列
- 4.1 佇列的基本概念及描述
- 4.2 順序佇列及其實作
- 4.2.1 順序佇列的存盤結構
- 4.3 順序回圈佇列及其實作
- 4.3.1 順序回圈佇列的存盤結構
- 五、演算法設計題
- 5.1 順序表值為x的結點的個數（演算法）
- 5.2 順序表倒置（演算法）
- 5.3 有序順序表插入結點并仍然有序（真題）（演算法）
- 六、錯題集
一、線性表
- 線性表：屬于線性結構，有且僅有一個開始結點，有且僅有一個終端結點，其他結點為內部結點，
- 線性表的存盤：順序存盤 or 鏈式存盤
二、順序表
2.1 順序表的基本概念及描述
- 順序表：線性表采用順序存盤的方式
- 注：每個結點占用\(len\)個記憶體單元，\(location(k_i)\)為順序表中第\(i\)個結點\(k_i\)所占記憶體空間的第\(1\)個單元的地址
- \(location(k_i) = location(k_i) + len\)
- \(location(k_i) = location(k_1) + (i-1)len\)
2.2 順序表的實作
- 注：陣列中下標為\(i\)的元素對應的是順序表中第\(i+1\)個結點
- 順序表的常用操作（簡單且大概率不考，因此無代碼展示，后不提醒）
- 順序表的初始化
- 順序表后部進行插入操作
- 列印順序表的各結點值
- 判斷順序表是否為空
- 查找順序表中值為x的結點位置
- 取得順序表中第i個結點的值
2.2.1 順序表的存盤結構
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype a[MAZXSIZE];
int size;
} sequence_list;
2.2.2 順序表的插入操作（演算法）
- 將值為\(x\)的結點插入到第\(i\)個位置的步驟：
- 判斷順序表是否是滿的
- 判斷指定的位置是否不存在
- 將\(k_i,\cdots,k_{n-1}\)這些結點對應的陣列元素依次后移一個位置，空出\(k_i\)原先的位置存放新插入的結點，（從后往前移）
- 將值為\(x\)的結點插入到第\(i\)個位置
- 順序表的長度加\(1\)
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype a[MAZXSIZE];
int size;
} sequence_list;
void insert(sequence_list *slt, datatype x, int position) {
int i;
if (slt->size == MAXSIZE) {
printf("\n順序表是滿的！沒法插入！");
exit(1);
}
if (position < 0 || position > slt->size) // 如size為10，slt->a[i-1=9]存在，既可以不用>=
{
printf("\n指定的插入位置不存在！");
exit(1);
}
for (i = slt->size; i > position; i--) {
slt->a[i] = slt->a[i - 1];
}
slt->a[position] = x;
slt->size++;
}
時間復雜度：\(O(n)\)
2.2.3 順序表的洗掉操作（演算法）
- 洗掉順序表中第\(i\)個結點的步驟：
- 判斷順序表是否為空
- 判斷洗掉位置是否存在
- 將順序表中的\(k_{i+1},\cdots,k_{n-1}\)元素依次前移一個位置，（從前往后移）
- 順序表的長度減\(1\)
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype a[MAZXSIZE];
int size;
} sequence_list;
void dele(sequence_list *slt, int position) {
int i;
if (slt->size == 0) {
pringf("\n順序表是空的！");
exit(1);
}
if (position < 0 || position >= slt->size) // 如size為10，postion為10，slt->a[i+1=11]不存在，即不可以>
{
printf("\n指定的洗掉位置不存在！");
exit(1);
}
for (i = position; i < slt->size - 1; i++) // 回圈到倒數第二個元素即可，因為后面是a[i+1]
{
slt->a[i] = slt->a[i + 1];
}
slt->size--;
}
時間復雜度：\(O(n)\)
三、堆疊
3.1 堆疊的基本概念及描述
- 堆疊：特殊的線性表，插入運算和洗掉運算均在線性表的同一端進行
- 堆疊頂：進行插入（進堆疊）和洗掉（出堆疊）的一端
- 堆疊底：不進行操作的一端
- 堆疊的性質：后進先出（先進后出）
- 出堆疊元素不同排列個數：\(\frac{1}{n+1}C_{2n}^{n}\)
3.2 順序堆疊及其實作
- 堆疊（順序存盤）的常用操作：
- 堆疊的存盤結構
- 堆疊初始化
- 判斷堆疊是否為空
- 取得堆疊頂結點值
- 堆疊的插入操作
- 堆疊的洗掉操作
3.2.1 順序堆疊的存盤結構
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype a[MAXSIZE];
int top;
} sequence_stack;
3.3 堆疊的應用之一（括號匹配）
- 括號匹配解決步驟：
- 從左向右掃描運算式
- 遇到開括號則將遇到的開括號存放于堆疊中
- 遇到閉括號則查看是否與堆疊頂結點匹配，匹配洗掉堆疊頂結點，不匹配說明運算式中的括號是不匹配的（結束）
- 掃描整個運算式后，堆疊是空的，說明運算式中的括號是匹配的；否則是不匹配的（結束）
3.4 堆疊的應用之二（算術運算式求值）
- 中綴運算式：運算子處于兩個運算元之間
- 前綴運算式：運算子處于兩個運算元之前
- 后綴運算式：運算子處于兩個運算元之后
- 后綴運算式求值：每遇到一個運算子，則將前面的兩個運算元執行相應的操作
- 后綴運算式求解步驟：
- 把遇到的運算元暫存于一個堆疊中
- 遇到運算子，則從堆疊中取出兩個運算元執行相應的操作，并將結果壓入堆疊中
- 直到對后綴運算式中最后一個運算子處理完
- 最后壓入堆疊中的樹就是后綴運算式的計算結果
3.4.1 中綴運算式轉換為后綴運算式步驟
-
從左到右掃描中綴運算式，如果是數字字符和圓點“.”，直接寫入后綴運算式
-
遇到開括號，將開括號壓入堆疊中，遇到匹配的閉括號，將堆疊中元素彈出并放入后綴運算式，直到堆疊頂元素為匹配的開括號時，彈出該開括號
-
遇到的是運算子：
- 遇到的運算子優先級<=堆疊頂元素，彈出堆疊頂元素放入后綴運算式（回圈判斷）
- 遇到的運算子優先級>堆疊頂元素，將遇到的運算子壓入堆疊中
-
重復上述步驟，直到遇到結束標記“#”，彈出堆疊中的所有元素并放入后綴運算式陣列中
-
運算子優先級：\(\#,(,+-,*/\)
| -1 | 0 | 1 | 2 |
|---|---|---|---|
| # | ( | +- | */ |
四、佇列
4.1 佇列的基本概念及描述
- 佇列：一種特殊的線性表，插入（進隊）和洗掉（出隊）操作分別在表的兩端進行
- 隊尾：插入的一端
- 對首：洗掉的一端
- 佇列的性質：先進先出
4.2 順序佇列及其實作
- 佇列（順序存盤）的常用操作：
2. 佇列初始化
3. 判斷佇列是否為空
4. 列印佇列的結點值
5. 取得佇列的隊首結點值
6. 佇列的插入操作
7. 佇列的洗掉操作
4.2.1 順序佇列的存盤結構
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype a[MAXSIZE];
int front;
int rear;
} sequence_queue;
4.3 順序回圈佇列及其實作
- 普通佇列的列滿狀態指標：\(rear = MAXSIZE\)
- 回圈佇列的作用：在普通佇列處于列滿狀態時，利用陣列前部的空閑位置
- 回圈佇列的列滿狀態指標：
- 設定一個標志：由于\(rear\)增\(1\)使\(rear = front\)，為隊滿；由于\(front\)增\(1\)使\(rear = front\)，隊空
- 犧牲一個陣列元素空間：\((rear + 1) \% MAXSIZE = front\)，隊滿；\(rear = front\)，隊空
- 回圈佇列（順序存盤）的常用操作（相比較普通佇列在指標增\(1\)中增加一個取模操作）：
- 回圈佇列的插入操作
- 回圈佇列的洗掉操作
4.3.1 順序回圈佇列的存盤結構
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype a[MAXSIZE];
int front;
int rear;
} sequence_queue;
五、演算法設計題
5.1 順序表值為x的結點的個數（演算法）
設計一個演算法，求順序表中值為x的結點的個數
演算法步驟：
- 設定初始值\(c\)計數
- 每找到一個值為\(x\)的結點，計數加\(1\)
- 回傳\(c\)
// 順序表的存盤結構定義如下（檔案名seqlist.h）
#include <stdio.h>
#define N 100 // 預定義最大的資料域空間
typedef int datatype; // 假設資料型別為整型
typedef struct {
datatype data[N]; // 此處假設資料元素只包含一個整型的關鍵字域
int length; // 線性表長度
} seqlist; // 預定義的順序表型別
// 演算法countx(L, x)用于求順序表L中值為x的結點的個數
int countx(seqlist *L, datatype x) {
int c = 0;
int i;
for (i = 0; i < L->length; i++) {
if (L->data[i] == x) c++;
}
return c;
}
5.2 順序表倒置（演算法）
設計一個演算法，將一個順序表倒置，即，如果順序表各個結點值存盤在一維陣列\(a\)中，倒置的結果是使得陣列\(a\)中的\(a[o]\)等于原來的最后一個元素，\(a[1]\)等于原來的倒數第\(2\)個元素，\(\cdots\)，\(a\)的最后一個元素等于原來的第一個元素
演算法步驟：
- 定位最后一個元素
- 用\(t\)保留第個一元素的值，并且第一個元素和最后一個元素的值交換
- 回圈到最后一個元素
// 順序表的存盤結構定義如下（檔案名seqlist.h）
#include <stdio.h>
#define N 100 // 預定義最大的資料域空間
typedef int datatype; // 假設資料型別為整型
typedef struct {
datatype data[N]; // 此處假設資料元素只包含一個整型的關鍵字域
int length; // 線性表長度
} seqlist; // 預定義的順序表型別
// 演算法verge(L)用于順序表倒置
void verge(seqlist *L) {
int t, i, j;
i = 0;
j = L->length - 1;
while (i < j) {
t = L->data[i];
L->data[i++] = L->data[j];
L->data[j--] = t;
}
}
5.3 有序順序表插入結點并仍然有序（真題）（演算法）
已知一個順序表中的各結點值是從小到大有序的，設計一個演算法，插入一個值為\(x\)的結點，使順序表中的結點仍然是從小到大有序
演算法步驟：
- 從最后一個元素開始與\(x\)比較大小，元素值大于該\(x\)值，則往后挪一個位置
- 找到比\(x\)小的元素停止
- 在該元素的位置上插入\(x\)值
// 順序表的存盤結構定義如下（檔案名seqlist.h）
#include <stdio.h>
#define N 100 // 預定義最大的資料域空間
typedef int datatype; // 假設資料型別為整型
typedef struct {
datatype data[N]; // 此處假設資料元素只包含一個整型的關鍵字域
int length; // 線性表長度
} seqlist; // 預定義的順序表型別
// 演算法insertx(L, x)用于有序順序表插入結點并仍然有序
void insertx(seqlist *L, datatype x) {
int j;
if (L->length < N) {
j = L->length - 1;
while (j >= 0 && L->data[j] > x) {
L->data[j + 1] = L->data[j]; // 元素統一往后挪
j--;
}
L->data[j + 1] = x;
L->length++;
}
}
六、錯題集
-
長為 \(n\) 的順序表中，任意位置插入的可能次數為n+1?次（包括頭前和尾后）
-
設堆疊 \(S\) 和佇列 \(Q\) 的初始狀態為空，元素 e1、$e\(2、\)e\(3、\)e\(4、\)e$5 和 $e$6 依次通過堆疊 \(S\)，
一個元素出堆疊后即進入佇列 \(Q\)，若 6 個元素出隊的序列為 $e\(2、\)e\(4、\)e\(3、\)e\(6、\)e$5 和 $e$1，則堆疊 \(S\)
的容量至少應該為3?
-
編號為 \(1,2,3,4\) 的四列火車通過一個堆疊式的列車調度站，可能得到的調度結果總共有14種
- 使用公式：出堆疊元素不同排列個數為 \(\frac{1}{n+1}C_{2n}^{n}\)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/152733.html
標籤：其他
上一篇：第1章 概論
下一篇：頭檔案：你真的懂我嗎？？？