第2章 顺序表及其顺序存储
一、线性表
- 线性表：属于线性结构。有且仅有一个开始结点，有且仅有一个终端结点，其他结点为内部结点。
- 线性表的存储：顺序存储 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})
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
