通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

第二章 栈、队列、数组

5273人浏览 / 0人评论 / | 作者:因情语写  | 分类: 数据结构  | 标签: 数据结构  | 

作者:因情语写

链接:https://www.proprogrammar.com/article/22

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


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

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

    线性表

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

    栈

    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, n0 }

    数据关系:

    R1={ <ai-1, ai >| ai-1, aiD, i=2,...,n }

    约定 a 端为栈顶,a1 端为栈底。

    基本操作:

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

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

     StackTravers(S, visit())

    } ADT Stack

    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)凡出现右括弧,首先检查栈是否空。若栈空,则表明该“右括弧”多余,否则和栈顶元素比较,若相匹配,则“左括弧出栈”,否则表明不匹配

    3)表达式检验结束时,若栈空,则表明表达式中匹配正确,否则表明“左括弧”有余
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#es#*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)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;

    5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;

    如何从后缀式求值?先找运算符,再找操作数(运算符与前面的两个操作数运算)

    例如: a b × c d e / f × +

    如何从原表达式求得后缀式? (后缀式:前两个内容一定是操作数,最后一个内容一定是运算符)

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

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

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

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

    从原表达式求得后缀式的规律为:

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

    2) 设表达式的结束符为“#,予设运算符栈的栈底为“#

    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;

    因为栈中的主要运算是在栈顶插入、删除,显然在链表的头部做栈顶是最方便的,而且没有必要象单链表那样为了运算方便附加一个头结点(无头结点)。

    队列的类型定义

    ADT Queue {

    数据对象:

     D{ai | aiElemSet, i=1,2,...,n, n0}

     数据关系:

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

     约定其中 a1 端为队列头, a端为队列尾

     基本操作:

     InitQueue(&Q) DestroyQueue(&Q) QueueEmpty(Q) QueueLength(Q)

    GetHead(Q, &e) ClearQueue(&Q) EnQueue(&Q, e) DeQueue(&Q, &e)

    QueueTravers(Q, visit())

} ADT Queue

    队列类型的实现

    链队列——链式映象

    循环队列——顺序映象

    链队列——链式映象

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.

    因为在对队列的操作中,头尾指针只增加不减小,导致被删除元素的空间永远无法重新利用。尽管队列中实际的元素个数可能远远小于存储空间的规模,但仍不能做入队列操作,该现象称为“假上溢”。

    克服“假上溢”现象的方法是将顺序队列想象为一个首尾相接的圆环,称之为环队列

 

    循环队列中无法通过 Q.front=Q.rear 来判断队列“空”还是“满” 。解决此问题的方法至少有三种:

 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;
}

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

    (1)如果 Q.front==Q.rear,则可以判断循环队列为空

    (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 即为循环队列的长度

      1)当 Q.rear>Q.front 时,循环队列长度=Q.rear-Q.front

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

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

    队列与循环链表

    队列(包括循环队列)是一个逻辑概念,而链表是一个存储概念。一个队列是否是循环队列,不取决于它将采用何种存储结构,根据实际的需要,循环队列可以采用顺序存储结构,也可以采用链式存储结构,包括采用循环链表作为存储结构。

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

                                                                         C(2n,n)/(n+1)

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

    (2)一串数据通过一个队列,只有一种出队列顺序,就是其入队列顺序。

      几种特殊的队列:

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

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

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

     数组的类型定义

    二维数组的定义:

     数据对象:

    D = {aij | 0≤ib1-1, 0 jb2-1}

    数据关系:

    R = { ROW, COL }

    ROW = {<ai,j, ai+,j>| 0≤ib1-2, 0jb2-1}

    COL = {<ai,j, ai,j+>| 0≤ib1-1, 0jb2-2}

    数组的顺序表示和实现

    类型特点:

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

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

    有两种顺序映象的方式:

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

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

    例如:

   

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

   

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

   

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

    特殊矩阵压缩存储

    何谓稀疏矩阵

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

   

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

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

    (2)计算中进行了很多和零值的运算,遇除法,还需判别除数是否为零;

     解决问题的原则:

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

    (2)尽可能减少没有实际意义的运算;

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

    有两类矩阵:

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

    (2随机稀疏矩阵:非零元在矩阵中随机出现。

    对称矩阵

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

    对称矩阵中的元素关于主对角线对称,故只要存储矩阵中上三角或下三角中的元素,让每两个对称的元素共享一个存储空间,这样,能节约近一半的存储空间。不失一般性,按“行优先顺序”存储主对角线(包括对角线)以下的元素,其存储形式如图所示:

 

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

    因此,将这些元素存放在一个向量 sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵 A中的元素,必须在 aijsa[k]之间找一个对应关系。

    ij,则 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 0k

    若 i,则 aij是在上三角矩阵中。因为 aij=aji,所以只要交换上述对应关系式中的 i j 即可得到:k=j*(j+1)/2+i 0k

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

    因此,aij的地址可用下列式计算:

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

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

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

    例如 a21a12均存储在 sa[4]中,这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4

    三角矩阵

    以主对角线划分,三角矩阵有上三角和下三角两种。上三角矩阵的下三角(不包括主对角线)中的元素均为常数。下三角矩阵正好相反,它的主对角线上方均为常数。在大多数情况下,三角矩阵常数为零。

   

      三角矩阵中的重复元素 c 可共享一个存储空间,其余的元素正好有 n(n+1)/2 个,因此,三角矩阵可压缩存储到向量 sa[0..n(n+1)/2]中,其中 c 存放在向量的最后一个分量中。  

     上三角矩阵中,主对角线之上的第 p (0≦p恰有 n-p 个元素,按行优先顺序存放上三角矩阵中的元素 aij时,aij之前的 i 行一共有i(2n-i+1)/2 个元素,在第 i 上,aij前恰好有 j-i 个元素:aii,aii+1,aij-1

    因此,sa[k]aij的对应关系是:

    i(2n-i+1)/2+j-i ij

    n(n+1)/2 i>j

    下三角矩阵的存储和对称矩阵类似,sa[k]aij 对应关系是:

    i(i+1)/2+j  ij

    n(n+1)/2  i>j

    对角矩阵

    对角矩阵中,所有的非零元素集中在以主对角线为了中心的带状区域中,即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外,其余元素皆为零。

    非零元素仅出现在主对角(aii,0in-1) 上,紧邻主对角线上面的那条对角线上(ai i+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0≦in-2)。显然,当∣i-j>1 时,元素 aij=0

    由此可知,一个 k 对角矩阵(k 为奇数)A 是满足下述条件的矩阵:若∣i-j>(k-1)/2 ,则元素 aij=0

    对角矩阵可按行优先顺序或对角线的顺序,将其压缩存储到一个向量中,并且也能找到每个非零元素和向量下标的对应关系。

    在三对角矩阵里附满足条件 i=0j=01,或 i=n-1j=n-2n-1 j=i-1i、i+1(i0,in-1) 的元素 aij外,其余元素都是零。

    对这种矩阵,我们也可按行优序为主序来存储。除第 0 行和第 n-1 行是 2 个元素外,每行的非零元素都要是 3 个,因此,需存储的元素个数为 3n-2

    数组 sa 中的元素 sa[k]与三对角带状矩阵中的元素 aij存在一一对应关系,在 aij前有 i ,共有 3*i-1 个非零元素,在第 i 行,有 j-i+1 个非零元素,这样,非零元素 aij 的地址为:

    LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d

    上例中,a34对应着 sa[10]k=2*i+j=2*3+4=10a21对应着 sa[5]k=2*2+1=5由此,我们称 sa[0..3*n-2]是三阶对角带状矩阵 A 的压缩存储表示。

    上述的各种特殊矩阵,其非零元素的分布都是有规律的,因此总能找到一种方法将它们压缩存储到一个向量中,并且一般都能找到矩阵中的元素与该向量的对应关系,通过这个关系,仍能对矩阵的元素进行随机存取。

    随机稀疏矩阵的压缩存储方法

    三元组顺序表

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

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

    归纳总结

    1、两个对称矩阵相加,结果是对称矩阵;两个对称矩阵相乘,结果可能不对称,除非两个矩阵相同。

    2、两个三对角矩阵相加,结果是三对角矩阵;两个三对角矩阵相乘,结果不再是三对角矩阵。

    3、两个稀疏矩阵相加,结果是稀疏矩阵(当然有可能 0 元素个数会有变化);两个稀疏矩阵相乘,结果不一定是稀疏矩阵。

    本章学习重点

    1. 掌握栈和队列类型的特点,并能在相应的应用问题中正确选用它们。

    2. 熟练掌握栈类型的两种实现方法,特别应注意栈满和栈空的条件以及它们的描述方法。

    3. 熟练掌握循环队列和链队列的基本操作实现算法,特别注意队满和队空的描述方法。

    4.了解数组的两种存储表示方法,并掌握数组在以行为主的存储结构中的地址计算方法。

    5.掌握对特殊矩阵进行压缩存储时的下标变换公式。
 

 

 
 

 

 

 


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

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告