第三章、栈和队列

栈的队列的应用

栈和队列是限定插入和删除只能在表的"端点"进行的线性表。

栈的应用：数制转换、表达式求值、括号匹配问题、八皇后问题、行编辑程序、函数调用、迷宫求解、递归调用的实现。

队列的应用：

• 脱机打印输出：按申请的先后顺序依次输出。
• 多用户系统中，多个用户排成队，分时地循环使用CPU和主存。
• 按用户的优先级排成多个队，每个优先级一个队列。
• 实时控制系统中，信号按接收的先后顺序依次处理。
• 网络电文传输，按到达的时间先后顺序依次进行。

栈的特点

栈：仅在表尾进行插入、删除操作的线性表。

表尾称为****栈顶。表头称为栈底。

1. 案例引入

案例1：进制转换。十进制整数N向其它进制数d(2、8、16)的转换是计算机实现计算的基本问题。

转换法则：除以d倒取余。

public class DecimalToBinary {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        int x = 18;
        while (x > 0) {
            int remain = x % 2;
            s.push(remain);
            x = x >> 1;
        }
        while(!s.empty()) System.out.print(s.pop());
    }
}

案例2：括号匹配的检验

假设表达式中允许包含两种括号：圆括号和方括号。

其嵌套的顺序随意，即：

• ( [] () ) or [ ( [] [] ) ]为正确格式；
• [ ( ] ) or ( [ () ) or ( () ] )为错误格式。

案例3：表达式求值

案例4：舞伴问题。

假设在舞会上，男士和女士各自排成一队。舞会开始时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

分析：显然符合先进先出的特性，可以使用队列作为算法的数据结构。

算法：

• 首先构造两个队列。
• 依次将队头元素出队配成舞伴。
• 某队为空，则另外一队等待着的则是下一舞曲第一个可获得舞伴的人。

2. 栈的存储结构

栈空的标志：top == base。

栈满的标志：top == stacksize。

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top;
} SqStack;

3. 队列的存储结构

第四章、串、数组和广义表

回顾

• 栈和队列是****操作受限的线性表。
• 串、数组和广义表是****内容受限的线性表。
  • 串中的每一个数据元素只能是字符类型。
  • 每一个数据元素是线性表我们称为数组。
  • 广义表中的数据元素又是一个广义表。

1. 串

1.1. 串的术语

串(String)：零个或多个任意字符组成的有限序列。

子串：串中任意个连续字符组成的子序列称为该串的子串。

主串：包含字串的串相应的称为主串。

字符位置：字符在序列中的序号为该字符在串中的位置，

子串位置：子串第一个字符在主串中的位置。

空格串：由一个或多个空格组成的串，与空串不同。

串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。

注：所有的空串都是相等的！

1.2. 串的存储结构

(1)顺序存储结构(实际用的多)

#define MAXSIZE 255
typedef struct {
    char ch[MAXSIZE+1];       // 存储串的一维数组
    int length;               // 串的当前长度
} SqString;

(2)链式存储结构——块链结构

#define CHUNKSIZE 80
​
typedef struct _chunk {
    char ch[CHUNKSIZE];
    struct _chunk* next;
} Chunk;
​
typedef struct {
    Chunk* head;              // 头指针
    Chunk* tail;              // 尾指针
    int curlen;               // 串的当前长度
} LString;

1.3. 串的模式匹配算法

算法目的(定位)：确定主串中所含子串(模式串)第一次出现的位置。

Brute Force——BF算法：穷举法

BF算法：

• 将主串的第 pos个字符和模式串的第一个字符比较；
• 若相等，继续逐个比较后续字符；
• 若不等，从主串的下一字符起，重新与模式串的第一个字符比较。
• 直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功；
• 否则匹配失败，返回-1.

/**
* @Param：S 主串
* @Param：T 模式串
*/
int index_BF(SqString S, SqString T) {
    int i = 0;
    int j = 0;
    while(i < S.length && j < T.length) {
        if(S.ch[i] == T.ch[i]) {
            i++;
            j++;
        } else {
            j = 0;                              // 模式串指针到起始位置
            i = i - j + 1;                      // 主串指针回溯
        }
    }
    if(j >= T.length) return i - T.length;      // 模式串匹配成功
    else return -1;                             // 模式串匹配失败
}

BF算法时间复杂度：O(n*m)。

KMP算法

KMP算法思想：利用已经****部分匹配的结果而加快模式串的滑动速度。且主串的指针不必回溯！可以将时间复杂度提高到 O(n+m)。

(1)模式串最长公共前后缀构造next数组。

(2)next数组构造。

void getNext(SqString T, int &next[]) {
    int i = 1;
    int j = 0;
    next[0] = 0;
    next[1] = 0;
    while(i < T.length) {
        if(j == 0 || T.ch[i] == T.ch[j]) {
            i++;
            j++;
            next[i] = j; 
        }else {
            j = next[j];
        }
    }
}

next数组构造有两种方法：

• 最长公共前后缀(人方便)。
• 根据next数组下标(计算机使用)。

(3)KMP算法。

int index_KMP(SqString S, SqString T) {
    int i = 0;
    int j = 0;
    while(i < S.lengt && j < T.length) {
        if(j == 0 || S.ch[i] == T.ch[j]) {
            i++;
            j++;
        } else {
            j = next[j];                  // i不变，j后退
        }
    }
    if(j >= T.length) return i-T.length;
    else return -1;
}

(4)nextval数组。

2. 数组

数组：按照一定格式排列起来，具有相同类型的数据元素的集合。

注意：数组是多维的，但是存储数据元素的内存单元是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。

二维数组

二维数组行序优先表示。

三维数组

3. 矩阵压缩存储

特殊矩阵的压缩存储

矩阵：一个由m×n个元素排成的m行n列的表。

矩阵的常规存储：将矩阵描述为一个二维数组。

矩阵常规存储的特点：

• 可以对其元素进行随机存取；
• 矩阵运算非常简单，存储密度为1。

不适宜常规存储的矩阵：

• 值相同的元素很多且呈某种规律；
• 零元素多。

什么是矩阵的压缩存储？：

答：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

什么样的矩阵能够压缩？

答：对称矩阵，对角矩阵、三角矩阵、稀疏矩阵等。

对称矩阵

(1)对称矩阵的特点

可以****以行序为主序将元素存放在一个一维数组 sa[n(n+1)/2]中。

(2)对称矩阵的压缩存储

三角矩阵

(1)三角矩阵的压缩存储

对角矩阵

(1)对角矩阵的压缩存储。

稀疏矩阵

(1)三元组法(有序的双下标法)。

数组的 0 号位置表示总行数、总列数、非零元素总个数。

优点：非零元素在表中按行序有序存储，因此便于进行顺序处理的矩阵运算。

缺点：不能随机存取。若按行号存取某一行中的非零元素，则需从头开始进行查找。

(2)十字链表。