devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构第三章汇总_队列的队尾指针指向

作者：从前慢现在也慢 | 2024-04-18 07:36:40

赞

踩

队列的队尾指针指向

目录

一、栈

（一）栈的基本概念

（二）栈的顺序存储结构

（三）栈的链式存储结构

二、队列

（一）队列的基本概念

（二）队列的顺序存储结构

（三）队列的链式存储结构

（四）双端队列

三、栈和队列的应用

（一）栈在括号匹配中的应用

（二）栈在表达式中的应用

（三）栈在递归中的应用

（四）队列在层次遍历中的应用

（五）队列在计算机系统中的应用 

 四、特殊矩阵的压缩存储

（一）数组的定义

（二）一维数组存储多维数组

（三）矩阵的压缩存储

（四）稀疏矩阵

一、栈

（一）栈的基本概念

1.栈的定义

        只允许在 一端进行插入或删除操作的线性表

  • 栈顶：允许进行插入删除的一端
  • 栈底：固定的，不允许插入和删除的另一端
  • 空栈：不含任何元素的空表

        栈的一个数学性质，n个不同元素进栈，出栈元素不同排序的个数为

\frac{1}{n+1}C^{n}_{2n}

2.栈的基本操作

基本操作操作函数备注
初始化InitStack(&L)初始化一个空栈
判空StackEmpty(S)若栈空返回true，否则返回false
进栈Push（&S,x）进栈，若栈S未满，则将x加入成为栈顶
出栈Pop（&S）出栈，若栈S非空，则弹出栈顶元素，并用x返回
读栈顶元素GetTop（S,&x）读栈顶元素，若栈S不为空，则用x返回栈顶元素
销毁栈DestroyStack（&S）销毁栈，并释放S占用的存储空间

（二）栈的顺序存储结构

1.顺序栈的实现

  1. #define MaxSize 50
  2. typedef sturct
  3. {
  4.     ElemType data[MaxSize];        //存放在栈中的元素
  5.     int top;                       //栈顶指针在数组中的相对位置
  6. }SqStack;

        栈顶指针：S.top,也就是栈顶在数组中的位置，初始的时候设置为-1

        栈顶元素：S.data[S.top]

        还有一种情况是S.top初始化为0的情况，这种情况表示S.top指向栈顶元素的下一个位置  

2.顺序栈的基本运算

（1）初始化

  1. #define MaxSize 50
  2. typedef sturct
  3. {
  4.     ElemType data[MaxSize];        //存放在栈中的元素
  5.     int top;                       //栈顶指针在数组中的相对位置
  6. }SqStack;
  7.  
  8. void InitStack(SqStack &S)
  9. {
  10.     S.top=-1;                      //初始化栈顶指针
  11. }
  12.  
  13. int main(){
  14.     SqStack S;                      //声明一个顺序栈
  15.     InitStack(S);                   //初始化顺序栈  
  16.     return 0;
  17. }
  18.

（2）判栈空

  1. #define MaxSize 50
  2. typedef sturct
  3. {
  4.     ElemType data[MaxSize];         //存放在栈中的元素
  5.     int top;                        //栈顶指针在数组中的相对位置
  6. }SqStack;
  7.  
  8. bool StackEmpty(SqStack &S)
  9. {
  10.     if(S.top == -1)
  11.         return true;                //栈空
  12.     else
  13.         return false;               //栈不为空
  14. }
  15.  
  16. int main(){
  17.     SqStack S;                      //声明一个顺序栈
  18.     InitStack(S);                   //初始化顺序栈  
  19.     if(StackEmpty(S))               //判空
  20.     print("hello");
  21.     return 0;
  22. }
  23.

（3）进栈

  1. #define MaxSize 50
  2. typedef sturct
  3. {
  4.     ElemType data[MaxSize];         //存放在栈中的元素
  5.     int top;                        //栈顶指针在数组中的相对位置
  6. }SqStack;
  7.  
  8. bool PushStack(SqStack &S,ElemType x)
  9. {
  10.     if(S.top == MaxSize-1)
  11.         return false;               //栈满报错
  12.     else
  13.     {
  14.         S.data[++S.top] = x;        //指针先+1，再进栈
  15.         return true;                       
  16.     }
  17.  
  18. }
  19.  
  20. int main(){
  21.     SqStack S;                      //声明一个顺序栈
  22.     ElemType x;
  23.     InitStack(S);                   //初始化顺序栈  
  24.     PushStack(S,x);                 //进栈操作
  25.     return 0;
  26. }
  27.

（4）出栈

  1. #define MaxSize 50
  2. typedef sturct
  3. {
  4.     ElemType data[MaxSize];         //存放在栈中的元素
  5.     int top;                        //栈顶指针在数组中的相对位置
  6. }SqStack;
  7.  
  8. bool PopStack(SqStack &S,ElemType x)
  9. {
  10.     if(S.top == -1)
  11.         return false;               //栈空报错
  12.     else
  13.     {
  14.         x = S.data[S.top--]         //先出栈，再指针-1
  15.         return true;                       
  16.     }
  17.  
  18. }
  19.  
  20. int main(){
  21.     SqStack S;                      //声明一个顺序栈
  22.     ElemType x;
  23.     InitStack(S);                   //初始化顺序栈  
  24.     PopStack(S,x);                  //出栈操作
  25.     return 0;
  26. }
  27.

（5）读栈顶元素

  1. #define MaxSize 50
  2. typedef sturct
  3. {
  4.     ElemType data[MaxSize];         //存放在栈中的元素
  5.     int top;                        //栈顶指针在数组中的相对位置
  6. }SqStack;
  7.  
  8. bool GetTop(SqStack &S,ElemType x)
  9. {
  10.     if(S.top == -1)
  11.         return false;               //栈空报错
  12.     else
  13.     {
  14.         x = S.data[S.top]           //记录栈顶元素
  15.         return true;                       
  16.     }
  17.  
  18. }
  19.  
  20. int main(){
  21.     SqStack S;                      //声明一个顺序栈
  22.     ElemType x;
  23.     InitStack(S);                   //初始化顺序栈  
  24.     GetTop(S,x);                    //读栈顶元素
  25.     return 0;
  26. }
  27.

3.共享栈 

        两个顺序栈共享一个一维数组，将两个栈的栈底分别设置在共享空间的两端，栈顶向共享空间中间延伸

        进栈时先动指针再赋值

        出栈时先取值再动指针

（三）栈的链式存储结构

1.链栈的定义

        采用链式存储的栈称为链栈，优点是不存在栈满上溢的情况

        通常用单链表实现，并规定所有操作都是在单链表的表头进行的，这里规定链栈没有头结点，Lhead指向栈顶元素

         栈的链式存储类型代码如下

  1. typedef struct Linknode
  2. {
  3.     ElemType data;
  4.     struct Linknode *next;
  5. }*Listack,Linknode;

 2.链栈的基本操作

         目前参照线性表的链式存储之后再继续完善

二、队列

（一）队列的基本概念

1.队列的定义

        一种受限制的线性表，只允许在表的一端进行插入，而在表的另一端进行删除

        特点：先进先出

2.队列常见的基本操作

        在算法题中一定情况下可以直接拿来使用的

基本操作操作函数备注
初始化InitQueue(&Q)初始化一个空队列Q
判空QueueEmpty(Q)若队空返回true，否则返回false
进队EnQueue（&Q,x）进队，若队列Q未满，则将x加入成为队尾
出队DeQueue（&Q）出队，若队列Q非空，则删除队头元素，并用x返回
读队头元素GetHead（S,&x）读队头元素，若队列Q非空，把队头元素赋值给x

（二）队列的顺序存储结构

1.队列的顺序存储

         分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针和队尾指针

        队头指针指向队头元素，队尾指针指向队尾元素的下一个位置

  1. #define MaxSize 50                    //定义队列中元素的最大个数
  2. typedef struct
  3. {
  4.     ElemType data[MaxSize];           //存放队列元素
  5.     int front,rear;                   //队头指针和队尾指针
  6. }SqQueue;

        初始状态：Q.front==Q.rear==0

        进队操作：先送值到队尾元素，再将队尾指针+1

        出队操作：先取队头元素，再将队头指针+1

        队列中元素数量 = 队尾指针 - 队头指针

         Q.rear == MaxSize不能作为队满条件，比如上图情况（e）和（d），实际上队列中是有空位置的，这是一种假溢出，也就无法入队了

2.循环队列

(1)循环队列的定义

        顺序队列存在假溢出的缺点，因此引入循环队列的概念 ，把存储队列元素从逻辑上视为一个环，物理存储上实际还是个数组

  • 初始时：Q.front=Q.rear=0
  • 队首指针进1：Q.front=（Q.front+1）%MaxSize
  • 队尾指针进1：Q.rear = （Q.rear+1）%MaxSize
  • 出队入队时：指针都按顺时针方向进1

         队空条件是Q.front = Q.rear

(2)循环队列队满条件

         但是由于队尾指针指向的会是队尾元素的下一个位置，也就是新元素要进来的位置，所以也可能会出现Q.front = Q.rear的情况

       

         有三种办法可以解决这个情况

        ①空出一个单元来区分

        这个时候队满条件为：（Q.rear+1）%MaxSize = =Q.front

        队列中元素数量为 （Q.rear - Q.front + Maxsize）% Maxsize

         ②类型中增设表示元素个数的数据成员

        队空条件Q.size == 0，队满条件 Q.size = MaxSize - 1

  1. #define MaxSize 50                    //定义队列中元素的最大个数
  2. typedef struct
  3. {
  4.     ElemType data[MaxSize];           //存放队列元素
  5.     int front,rear;                   //队头指针和队尾指针
  6.     int size;                          //队列内元素个数
  7. }SqQueue;

        ③类型中增设tag数据成员

        初始化tag为0，进队操作时tag置为1，出队时tag置为0

        当Q.front == Q.rear时，看tag的值，为1说明是因为进队导致的，说明是队满了

                                                                  为0说明是出队导致的，说明是队空了

  1. #define MaxSize 50                    //定义队列中元素的最大个数
  2. typedef struct
  3. {
  4.     ElemType data[MaxSize];           //存放队列元素
  5.     int front,rear;                   //队头指针和队尾指针
  6.     int tag;                          //表示上次的操作类型
  7. }SqQueue;

(3)循环队列的操作

        ①初始化

  1. #define MaxSize 50                    //定义队列中元素的最大个数
  2. typedef struct
  3. {
  4.     ElemType data[MaxSize];           //存放队列元素
  5.     int front,rear;                   //队头指针和队尾指针
  6. }SqQueue;
  7.  
  8. void InitQueue(SqQueue &Q)
  9. {
  10.     Q.rear = Q.front = 0;
  11. }
  12.  
  13. int main()
  14. {
  15.     SqQueue Q;
  16.     InitQueue(Q);
  17. }

        ②判队空

  1. #define MaxSize 50                    //定义队列中元素的最大个数
  2. typedef struct
  3. {
  4.     ElemType data[MaxSize];           //存放队列元素
  5.     int front,rear;                   //队头指针和队尾指针
  6. }SqQueue;
  7.  
  8. bool QueueEmpty(SqQueue &Q)
  9. {
  10.     if(Q.rear = Q.front)
  11.         return true;
  12.     else
  13.         return false;
  14. }
  15.  
  16. int main()
  17. {
  18.     SqQueue Q;
  19.     if(QueueEmpty(Q))
  20.         print("Empty!");
  21. }

        ③入队

  1. #define MaxSize 50                            //定义队列中元素的最大个数
  2. typedef struct
  3. {
  4.     ElemType data[MaxSize];                   //存放队列元素
  5.     int front,rear;                           //队头指针和队尾指针
  6. }SqQueue;
  7.  
  8. bool EnQueue(SqQueue &Q,Elemtype x)
  9. {
  10.     if((Q.rear + 1) % MaxSize == Q.front)     //很明显，这个是空了一个单元的循环队列
  11.         return false
  12.     Q.data[Q.rear] = x;
  13.     Q.rear = (Q.rear+1) % MaxSize;
  14.     return true
  15.          
  16. }
  17.  
  18. int main()
  19. {
  20.     SqQueue Q;
  21.     EnQueue(Q);
  22. }

        ④出队

  1. #define MaxSize 50                            //定义队列中元素的最大个数
  2. typedef struct
  3. {
  4.     ElemType data[MaxSize];                   //存放队列元素
  5.     int front,rear;                           //队头指针和队尾指针
  6. }SqQueue;
  7.  
  8. bool DeQueue(SqQueue &Q,Elemtype x)
  9. {
  10.     if(Q.rear == Q.front)     
  11.         return false;
  12.     x = Q.data[Q.front];
  13.     Q.front = (Q.front + 1) % MaxSize;
  14.     return true
  15.          
  16. }
  17.  
  18. int main()
  19. {
  20.     SqQueue Q;
  21.     DeQueue(Q);
  22. }

（三）队列的链式存储结构

1.队列的链式存储定义

        队列的链式表示称为链队列，实际上是一个带有队头指针和队尾指针的单链表，也就是带头指针和尾指针的单链表

         代码可描述为

  1. typedef struct                        //链队列的节点
  2. {
  3.     ElemType data;
  4.     struct LinkNode *next;
  5. }LinkNode;
  6.  
  7. typedef sturct                        //链式队列
  8. {
  9.     LinkNode *front,*rear;
  10. }*LinkQueue;

        一般情况下，链队列都设置为带头结点的

2.链式队列的基本操作

（1）初始化

  1. typedef struct                        //链队列的节点
  2. {
  3.     ElemType data;
  4.     struct LinkNode *next;
  5. }LinkNode;
  6.  
  7. typedef sturct                        //链式队列
  8. {
  9.     LinkNode *front,*rear;
  10. }*LinkQueue;
  11.  
  12. void InitQueue(LinkQueue &Q)
  13. {
  14.     Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
  15.     Q.front->next = Null;
  16. }
  17.  
  18. int main()
  19. {
  20.     LinkQueue Q;
  21.     InitQueue(Q);
  22. }

（2）判队空

  1. typedef struct                        //链队列的节点
  2. {
  3.     ElemType data;
  4.     struct LinkNode *next;
  5. }LinkNode;
  6.  
  7. typedef sturct                        //链式队列
  8. {
  9.     LinkNode *front,*rear;
  10. }*LinkQueue;
  11.  
  12. bool QueueEmpty(LinkQueue &Q)
  13. {
  14.     if(Q.front == Q.rear)
  15.         return ture;
  16.     elses
  17.         return false;
  18. }
  19.  
  20. int main()
  21. {
  22.     LinkQueue Q;
  23.     QueueEmpty(Q);
  24. }

（3）入队

  1. typedef struct                        //链队列的节点
  2. {
  3.     ElemType data;
  4.     struct LinkNode *next;
  5. }LinkNode;
  6.  
  7. typedef sturct                        //链式队列
  8. {
  9.     LinkNode *front,*rear;
  10. }*LinkQueue;
  11.  
  12. void EnQueue(LinkQueue &Q,ElemType x)
  13. {
  14.     LinkNode *s;
  15.     s = (LinkNode *)malloc(sizeof(LinkNode));
  16.     s.data = x;
  17.     s->netx = Null;
  18.     Q.rear->next = s;
  19.     Q.rear = s;
  20. }
  21.  
  22. int main()
  23. {
  24.     LinkQueue Q;
  25.     Elemtype x;
  26.     EnQueue(Q,x);
  27. }

（4）出队

        如果删除的是最后一个结点，那么要再多一次判断

  1. typedef struct                        //链队列的节点
  2. {
  3.     ElemType data;
  4.     struct LinkNode *next;
  5. }LinkNode;
  6.  
  7. typedef sturct                        //链式队列
  8. {
  9.     LinkNode *front,*rear;
  10. }*LinkQueue;
  11.  
  12. bool DeQueue(LinkQueue &Q,ElemType x)
  13. {
  14.     if(Q.front == Q.rear)
  15.         return false;
  16.     else
  17.     {
  18.         LinkNode * = Q.front->next;
  19.         x = tmp->data;
  20.         Q.front->next = tmp->next;
  21.         if(Q.rear == tmp)
  22.             Q.rear ==Q.front;
  23.         free(tmp); 
  24.         return true
  25.     }
  26. }
  27.  
  28. int main()
  29. {
  30.     LinkQueue Q;
  31.     Elemtype x;
  32.     DeQueue(Q,x);
  33. }

（四）双端队列

        允许两端都可以入队和出队操作的队列，队列两端分别称为前端和后端，两端都可以入队和出队

1.输入受限的双端队列

 2.输出受限的双端队列

三、栈和队列的应用

（一）栈在括号匹配中的应用

        假设表达式中允许包含两个括号：圆括号和方括号，其嵌套顺序任意，即([]())或[([][])]等均为正确格式，[(])或([())或(()]均为不正确的格式

        考虑下列括号序列：

[        (        [        ]        [        ]        )        ]

1       2       3      4        5      6       7       8

        算法分析如下：

1.初始设置一个空栈，顺序读入括号

2.若是右括号，则或者使置于栈顶的最急迫期待得以消解，或者是不合法的情况（括号序列不匹配，退出程序）

3.若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有栈中的所有未消解的期待的急迫性降低了一级

4.算法结束时，栈为空，否则括号序列不匹配

（二）栈在表达式中的应用

1.计算后缀表达式的值

        ABCD-*+EF/-，算法描述如下：

（1）顺序扫描表达式中的每一项

（2）根据每一项的类型做出相应操作，如果是操作数则压入栈中，如果是操作符，则弹出栈中的两个操作数并把计算完成后的数重新压入栈中

（3）当表达式所有项都扫描并处理完后，栈顶存放的就是最后的计算结果

         转完就E/F-（A+B*（C-D）） 

 2.中缀表达式转后缀表达式

        中缀表达式a+b-a*((c+d)/e-f)+g转换为后缀表达式ab+acd+e/f-*-g+

        算法思想

（1）从左向右扫描中缀表达式

（2）遇到数字时，加入后缀表达式

（3）遇到符号时

  • 若为'(',入栈
  • 若为')',则依次把栈中运算符加入后缀表达式，直到出现'('，从栈中删除'('
  • 若为其他运算符，当其优先级高于栈顶运算符时，直接入栈；否则从栈顶开始依次弹出比当前处理运算符优先级高和优先级相当的运算符，直到一个比它优先级低或者遇到了一个左括号位置

（三）栈在递归中的应用

        递归是一种程序设计方法。若在一个函数、过程或数据结构的定义中又应用到了它本身，则这个函数、过程或数据结构成为是递归定义的，简称递归

        通常把大型的复杂问题转化为一个与原问题相似的规模较小的问题来求解，大大减少程序代码量，但在通常情况下，效率并不太高

以斐波拉契数为例，其定义为

Fib(n)=\left\{\begin{matrix} Fib(n-1)+Fib(n-2),&n>1 \\ 1,& n=1 & \\ 0,& n=0 &\\ \end{matrix}\right.

        代码实现如下：

  1. int Fib(int n)
  2. {
  3.     if(n==0)
  4.         return 0;                            //边界条件
  5.     else if (n==1);
  6.         return 1;                            //边界条件
  7.     else
  8.         return Fib(n-1)+Fib(n-2);            //递归表达式
  9. }

（四）队列在层次遍历中的应用

        算法思想是根节点出子节点进

（五）队列在计算机系统中的应用 

  1.解决主机与外部设备之间不匹配的问题

        主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，由于速度不匹配，直接把数据送给打印机显然不行

        解决办法：

        设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他事情，打印机就从缓冲区中按先进先出顺序依次取出数据打印

 2.CPU资源的竞争

        在一个带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU的请求。

        操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用

四、特殊矩阵的压缩存储

（一）数组的定义

        数组是由n（n≥1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界

        数组与线性表的关系：数组是线性表的推广，一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变，因此除了结构的初始化和销毁外，数组只有存取元素和修改元素的操作

（二）一维数组存储多维数组

1.按行优先方式存储

        对于数组A_{2\times3},按行优先存储形式 如下：

2.按列优先方式存储

        对于数组A_{2\times3},按行优先存储形式 如下：

（三）矩阵的压缩存储

        压缩存储：多个值相同的元素只分配一个存储空间，对值为零的元素 不分配空间

        特殊矩阵：指具有许多相同矩阵元素或者零元素，并且这些元素的分布有一定规律性的矩阵。常见的有对称矩阵、上（下）三角矩阵、对角矩阵

        特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中

1.对称矩阵

        最明显的一个特点就是a_{i,j}=a_{j,i}

        对于对称矩阵，若仍采用二维数组存放，则会浪费一半空间，为此将对称矩阵存放在一维数组中

         比如只存放下三角部分的元素

        要找上三角部分的元素也就是i<j时，把i和j对换一下，带入上面的公式中即可

2.三角矩阵

        三角矩阵的特点就是上三角或者下三角部分所有元素均为同一常量

        存储思想与对称矩阵类似，不同之处在于存储完下三角区或者上三角区元素后，还要留下一个空间存储常量

        无论是行优先，还是列优先，核心思想：找到前面的所有元素，然后再加上本行或者本列的序号，看数组下标从0还是1开始，判断最后是否要做减一处理

（1）下三角矩阵

 （2）上三角矩阵

 3.三对角矩阵

        对角矩阵也称为带状矩阵

        也就是除了对角线上元素及两个相邻元素外，其他元素全为0

（四）稀疏矩阵

        矩阵中非0元素个数t相对于矩阵元素个数s来说非常少，即s>>t的矩阵称为稀疏矩阵

       通常0元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储非零元素所在的行和列

        将非零元素的值、行、列构成一个三元组（行标、列标、值）

         可以转换成三元组

ijv
004
126
219
3123

        稀疏矩阵的三元组可以用数组存储，也可以采用十字链表法存储

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/444715
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号