作者：whisper

链接：http://proprogrammar.com:443/article/22

声明：请尊重原作者的劳动，如需转载请注明出处

    说明：本章主要讲栈的类型定义，栈的应用举例 ，栈类型的实现（顺序存储和链式存储结构），队列的类型定义，队列类型的实现（顺序存储和链式存储结构），数组的类型定义 ，数组的顺序表示和实现 ，特殊矩阵的压缩存储

    通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

    线性表

    Insert(L, i, x)  1≤i≤n+1        Delete(L, i)  1≤i≤n

    栈

    Insert(S, n+1, x)        Delete(S, n)

    队列

    Insert(Q, n+1, x)         Delete(Q, 1)

    栈和队列是两种常用的数据结构。

    栈的类型定义

   ADT Stack {

    D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }

    R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }

    基本操作：

    InitStack(&S) DestroyStack(&S) GetTop(S, &e) Push(&S, e)

     StackLength(S) StackEmpty(S) ClearStack(&S) Pop(&S, &e)

     StackTravers(S, visit())

    Push(&S, e)

    初始条件：栈 S 已存在。

    操作结果：插入元素 e 为新的栈顶元素。

    Pop(&S, &e)

    初始条件：栈 S 已存在且非空。

    操作结果：删除 S 的栈顶元素，并用 e 返回其值。

    栈的应用举例

    例 1、 数制转换

    例 2、 括号匹配的检验

    例 3、 行编辑程序问题

    例 4、 表达式求值

    例 5、 实现递归

    例 1、 数制转换

    算法基于原理：

    N = (N div d)×d + N mod d

    例如：（1348)10 = (2504)8，其运算过程如下：

void conversion () {
    InitStack(S); 
    scanf ("%d",N);
    while (N) {
        Push(S, N % 8);
        N = N/8;
    }
    while (!StackEmpty(S)) {
        Pop(S,e);
        printf ( "%d", e );
    }
} // conversion

    例 2、 括号匹配的检验

    假设在表达式中：

    （［］（））或［（［ ］［ ］）］等为正确的格式， ［（ ］）或（［（ ））或 ( ( ) ] )均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。

    例如：考虑下列括号序列：

    [  (  [  ]  [  ]  )  ]

    1 2 3 4 5 6 7 8

    分析可能出现的不匹配的情况:

    1、到来的右括弧非是所“期待”的;

    2、到来的是“不速之客”;

    3、直到结束，也没有到来所“期待”的括弧;

    算法的设计思想：

    1）凡出现左括弧，则进栈；

    2）凡出现右括弧，首先检查栈是否空。若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配

void match(char *exp){
    initStack(s);
    char c; int i=0,b=1; // b匹配标志，为1表示匹配
    while (exp[i]!='\0'&&b==1){
        if (exp[i]=='(' || exp[i]=='[') push(S,exp[i]);
        else if (exp[i]==')' || exp[i]==']'){
            c=Pop(S); if ((exp[i]==')' && c!='(')) || (exp[i]==']' && c!='[')) b=0;
        }
        i++;
    }
    return (b&&StackEmpty(S));
}

    例 3、行编辑程序问题

    如何实现？

    “每接受一个字符即存入存储器”? 并不恰当！

     合理的做法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#”为退格符，“@”为退行符。

    假设从终端接受了这样两行字符：

    whli##ilr#e（s#*s)

        outcha@putchar(*s=#++);

    则实际有效的是下列两行：

    while (*s)

        putchar(*s++);

while (ch != EOF) { //EOF 为全文结束符
    while (ch != EOF && ch != '\n') {
        switch (ch) {
            case '#' : Pop(S, c); break;
            case '@': ClearStack(S); break;// 重置 S 为空栈
            default : Push(S, ch); break; 
        }
        ch = getchar(); // 从终端接收下一个字符
    }
    //将从栈底到栈顶的字符传送至调用过程的数据区；
    ClearStack(S); // 重置 S 为空栈
    if (ch != EOF) ch = getchar();
}

    例 4、 表达式求值

    限于二元运算符的表达式定义:

    表达式 ::= (操作数) + (运算符) + (操作数)

    操作数 ::= 简单变量 | 表达式

    简单变量 :: = 标识符 | 无符号整数

    设 Exp = S1 + OP + S2

    则称 OP + S1 + S2 为前缀表示法

    S1 + OP + S2 为中缀表示法

    S1 + S2 + OP 为后缀表示法

    例如: Exp= a × b + (c − d / e) × f

    前缀式: + × a b × − c / d e f

    中缀式: a × b + c − d / e × f

    后缀式: a b × c d e / − f × +

    结论：

    1）操作数之间的相对次序不变;

    2）运算符的相对次序不同;

    3）中缀式丢失了括弧信息，致使运算的次序不确定;

    4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;

    如何从后缀式求值？先找运算符，再找操作数（运算符与前面的两个操作数运算）

    例如： a b × c d e / − f × +

    分析“原表达式”和“后缀式”中的运算符:

    原表达式: a + b × c − d / e × f

    后缀式: a b c × + d e / f × −

    每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。

    1) 设立暂存运算符的栈;

    3) 若当前字符是操作数，则直接发送给后缀式;

    4) 若当前运算符的优先数高于栈顶运算符，则进栈;

    5) 否则，退出栈顶运算符发送给后缀式;

    6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。 （遇"("进栈，遇")"出栈一直到"("出站为止）

    例 5、实现递归

    当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：

•     将所有的实在参数、返回地址等信息传递给被调用函数保存;
•     为被调用函数的局部变量分配存储区;
•     将控制转移到被调用函数的入口。

    从被调用函数返回调用函数之前，应该完成下列三项任务：

•      保存被调函数的计算结果；
•      释放被调函数的数据区；
•      依照被调函数保存的返回地址将控制转移到调用函数。

     多个函数嵌套调用的规则是: 后调用先返回 ！此时的内存管理实行“栈式管理”

     例如：

void main( ){
…
a( );
…
}//main

void a( ){
…
b( );
…
}// a

void b( ){
…
}// b

     栈类型的实现

    顺序栈

    链栈

    顺序栈：类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。

    //栈的顺序存储表示 （动态分配）

#define STACK_INIT_SIZE 100
typedef struct {
    SElemType *base; 
    SElemType *top; 
    int stacksize; 
} SqStack;

    注意，非空栈时 top 始终在栈顶元素的下一个位置。

Status InitStack (SqStack &S, int maxsize){
    // 构造一个最大空间为 maxsize 的空顺序栈 S
    S.base = new ElemType[maxsize];
    if (!S.base) exit (OVERFLOW);
    //存储分配失败
    S.top = S.base;
    S.stacksize = maxsize;
    return OK;
}

Status Push (SqStack &S, SElemType e) 
{ 
// 若栈不满，则将 e 插入栈顶
    if (S.top - S.base >= S.stacksize) //栈满
        return OVERFLOW;
    *S.top++ = e;
    return OK;
}

Status Pop (SqStack &S, SElemType &e) {
    // 若栈不空，则删除 S 的栈顶元素，
    // 用 e 返回其值，并返回 OK；
    // 否则返回 ERROR
    if (S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}

typedef struct node{ 
    SElemType data;
    struct node *next;
}StackNode，* LinkStack;

     说明 top 为栈顶指针：LinkStack top;

typedef struct QNode {// 结点类型
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct { // 链队列类型
    QueuePtr front; // 队头指针
    QueuePtr rear; // 队尾指针
} LinkQueue;

    注：链队列有头结点

Status InitQueue (LinkQueue &Q) {
    // 构造一个空队列 Q
    Q.front = Q.rear = new QNode;
    if (!Q.front) exit (OVERFLOW);
    //存储分配失败
    Q.front->next = NULL;
    return OK;
}

Status EnQueue (LinkQueue &Q, QElemType e) {
    // 插入元素 e 为 Q 的新的队尾元素
    p = new QNode;
    if (!p) exit (OVERFLOW); //存储分配失败
    p->data = e; p->next = NULL;
    Q.rear->next = p; Q.rear = p;
    return OK;
}

Status DeQueue (LinkQueue &Q, QElemType &e) {
    // 若队列不空，则删除 Q 的队头元素，
    //用 e 返回其值，并返回 OK；否则返回 ERROR
    if (Q.front == Q.rear) return ERROR;
    p = Q.front->next; e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front;
    delete (p); 
    return OK;
}

    附设两个指针 front 和 rear 分别指示队头元素的位置和队尾元素的下一个位置。

    初始化建空队列时令 front=rear=0,插入新的队尾元素时尾指针增 1，删除队头元素时头指针增 1.

 （1）另设一个标志位区别队列的“空”和“满”。

 （2）使用一个计数器记录队列中元素的总数（实际上是队列长度）。

 （3）少用一个元素的空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈“满”状态的标志。（在后续算法中我们使用这种方法）

     循环队列类型定义

#define MAXQSIZE 100 //最大队列长度
typedef struct {
    QElemType *base; // 动态分配存储空间
    int front; // 头指针，若队列不空，
    // 指向队列头元素
    int rear; // 尾指针，若队列不空，指向
     // 队列尾元素 的下一个位置
    int queuesize; 
} SqQueue;

Status InitQueue (SqQueue &Q,int maxsize) {
    // 构造一个最大存储空间为 maxsize 的
    // 空循环队列 Q
    Q.base = new ElemType[maxsize];
    if (!Q.base) exit (OVERFLOW);
    Q.queuesize = maxsize;
    Q.front = Q.rear = 0;
    return OK;
}

Status EnQueue (SqQueue &Q, ElemType e) {
    // 插入元素 e 为 Q 的新的队尾元素
    if ((Q.rear+1) % Q.queuesize == Q.front) 
        return ERROR; //队列满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1) % Q.queuesize;
    return OK;
}

Status DeQueue (SqQueue &Q, ElemType &e) { 
    // 若队列不空，则删除 Q 的队头元素，
    // 用 e 返回其值，并返回 OK; 否则返回 ERROR
    if (Q.front == Q.rear) return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front+1) % Q.queuesize;
    return OK;
}

    循环队列中需要注意的几点:

    （2）如果 (Q.rear + 1)%MAXQSIZE==Q.front，则可以判断循环队列为满

    （3）无论是对循环队列进行插入或删除元素时，均可能涉及到尾指针或头指针的调整（非简单地对指针进行+1 操作），即Q.rear=(Q.rear+1)%MAXQSIZE 或 Q.front=(Q.front+1)%MAXQSIZE

    （4）如何理解 (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE 即为循环队列的长度

      2）当 Q.rear时，循环队列长度=(Q.rear-Q.front+MAXQSIZE)

      3）综合考虑以上两种情况，循环队列长度（任何情况下）=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE

    队列与循环链表

     （1）一串数据依次通过一个栈，可以产生多种出栈序列。可能的不同出栈序列数目的计算可利用 Catalan 函数算出。

     一串数据通过一个栈后的次序由每个数据之间的入栈、出栈操作序列决定，只有当所有数据“全部入栈后再全部出栈”才能使数据倒置。事实上，存在一种操作序列“入栈、出栈、入栈、出栈……” 可以使数据通过栈后仍然保持次序不变。

      几种特殊的队列：

     双端队列：可以在双端进行插入和删除操作的线性表。

     输入受限的双端队列：线性表的两端都可以输出数据元素，但是只能在一端输入数据元素。

     数组的类型定义

     数据对象:

    数据关系:

    ROW = {<ai,j, ai+₁,j>| 0≤i≤b1-2, 0≤j≤b2-1}

    COL = {<ai,j, ai,j+₁>| 0≤i≤b1-1, 0≤ j≤b2-2}

    数组的顺序表示和实现

    类型特点:

    1) 只有引用型操作，没有加工型操作;

    2) 数组是多维的结构，而存储空间是一个一维的结构。

    有两种顺序映象的方式:

    1)以行序为主序(低下标优先);

    2)以列序为主序(高下标优先);

    例如：

    以“行序为主序”的存储映象

    二维数组 A 中任一元素 ai,j 的存储位置

    注：b2为每行的元素数量，L为每个元素占用的空间

    特殊矩阵的压缩存储

    何谓稀疏矩阵？

    假设 m 行 n 列的矩阵含 t 个非零元素，则称为稀疏因子.通常认为 δ ≤ 0.05 的矩阵为稀疏矩阵。

   

    常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:

    （1）零值元素占了很大空间;

     解决问题的原则:

    （1）尽可能少存或不存零值元素;

    （3）操作方便; 即:能尽可能快地找到与下标值 (i, j) 对应的元素;能尽可能快地找到同一行或同一列的非零值元;

    有两类矩阵：

    （1）特殊矩阵：非零元在矩阵中的分布有一定规则。例如: 对称矩阵、三角矩阵、 对角矩阵

    对称矩阵

    在一个 n 阶方阵 A 中，若元素满足下述性质：aij=aji 0≦i,j≦n-1，称 A 为对称矩阵。

    在这个下三角矩阵中，第 i 行恰有 i+1 个元素，元素总数为：(i+1)=n(n+1)/2。

    若 i≥j，则 aij在下三角形中。aij之前的 i 行（从第 0 行到第 i-1 行）一共有 1+2+…+i=i(i+1)/2 个元素，在第 i 行上， aij之前恰有 j 个元素（即 ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j 0≦k

    令 I=max(i,j)， J=min(i,j)，则 k 和 i, j 的对应关系可统一为： k=I*(I+1)/2+J 0 ≦ k

               LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d

    注：d为一个元素占用的空间

    对于任意给定一组下标(i，j)，均可在 sa[k]中找到矩阵元素 aij，反之，对所有的k=0,1,2,…n(n-1)/2-1，都能确定 sa[k]中的元素在矩阵中的位置(i,j)。

    三角矩阵

#define MAXSIZE 12500
typedef struct {
    int i, j; //该非零元的行下标和列下标
    ElemType e; // 该非零元的值
} Triple; // 三元组类型

typedef union {
    Triple data[MAXSIZE + 1]; 
    int mu, nu, tu; 
} TSMatrix; // 稀疏矩阵类型

亲爱的读者：有时间可以点赞评论一下