考研408_数据结构笔记（第三章栈、队列和数组）

发布于：2025-08-03 ⋅ 阅读:(9) ⋅ 点赞:(0)

3.1栈

3.1.1栈（Stack）的基本概念

定义： 只允许在一端进行插入或删除操作的线性表
在这里插入图片描述

逻辑结构：与普通线性表相同
数据的运算：插入、删除操作有区别
栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。
特点： 后进先出。 (LIFO)
栈的基本操作：
InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。
DestroyStack(&S)：销毁栈。销毁并释放栈S所占用的内存空间。
Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素。若栈S非空，则用x返回栈顶元素
StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false

出栈顺序数量：
n个不同元素进栈，出栈元素不同排列的个数为
1n+1C2nn \frac{1}{n+1} C_{2n}^n n+11​C2nn​

3.1.3栈的顺序存储结构

初始化：

#define MaxSize 10          //定义栈中元素的最大个数
#define ElemType int
typedef struct{
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top;                //栈顶指针
}SqStack;

//初始化
void InitStack(SqStack &S){
    S.top=-1;
}

入栈：

bool Push(SqStack &S,ElemType e){
    if(S.top==MaxSize-1)      //栈满，报错
        return false;        
    S.top++;                  //指针++
    S.data[S.top]=e;          //入栈
    //S.data[++S.top]=e;
    return true;
}

出栈：

bool Pop(SqStack &S,ElemType &e){
    if(S.top==-1)
        return false;
    e=S.data[S.top];
    S.top--;
    //e=S.data[S.top--];
    return true;
}

判断是否栈空：

//判断栈空
bool StackEmpty(SqStack S){
    if(S.top==-1)
        return true;      //栈空
    else 
        return false;     //非空
}

共享栈：
两个栈共用一个数组空间，提高了空间利用率。
初始化：

#define MaxSize 10          //定义栈中元素的最大个数
#define ElemType int
typedef struct{
    ElemType data[MaxSize];
    int top0;
    int top1;
}ShStack;

//初始化
void InitStack(ShStack &S){
    S.top0=-1;
    S.top1=MaxSize;
}

top1=top0+1

3.1.3栈的链式存储结构

进栈：头插法建立单链表，也就是对头结点的后插操作
出栈：单链表的删除操作，对头结点的“后删”操作
推荐使用不带头结点的链栈
创销增删查的操作参考链表

#define ElemType int
typedef struct Linknode{
    ElemType data;
    struct Linknode *next;
}*LiStack;

3.2队列

3.2.1队列的基本概念

定义：
只允许在一端进行插入，在另一端删除的线性表

特点：
先进先出 (FIFO)

队列（Queue）:是只允许在一端进行插入，在另一端删除的线性表
队头：允许删除的一端，对应的元素被称为队头元素
队尾：允许插入的一端，对应的元素被称为队尾元素
在这里插入图片描述

基本操作：
InitQueue(&Q)：初始化队列，构造一个空队列Q。
DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。
EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。

3.2.2队列的顺序存储结构

初始化：

#define MaxSize 50
#define ElemType int 
typedef struct{
    ElemType data[MaxSize];
    int front,rear;        //队头指针和队尾指针
}SqQueue;
//初始化
void InitQueue(SqQueue &Q){
    Q.rear=0;
    Q.front=0;
}

入队：

//入队
bool EnQueue(SqQueue &Q,ElemType e){
    if((Q.rear+1)%MaxSize==Q.front)
        return false;
    Q.data[Q.rear]=e;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

出队：

//出队
bool DeQueue(SqQueue &Q,ElemType &e){
    if(Q.rear==Q.front)
        return false;
    e=Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    return true;
}

判断是否为空：

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
    if(Q.front==Q.rear)
        return true;
    return false;
}

判断队列已满/已空
方案1：
使用前面讲的牺牲一个存储空间的方式来解决
初始化时rear=front=0
队列元素个数：(rear+MaxSize-front)%MaxSize
队列已满的条件：队尾指针的再下一个位置是队头，
即(Q.rear+1)%MaxSize == Q.front
队空条件：Q.rear == Q.front

方案2：
不牺牲一个存储空间，在结构体中多建立一个变量size
初始化时rear=front=0；size = 0;
队列元素个数: size
插入成功size++；删除成功size--;
此时队满条件：size == MaxSize
队空条件：size == 0;

方案3：
不牺牲一个存储空间，在结构体中多建立一个变量tag
初始化时rear=front=0；tag = 0;
因为只有删除操作，才可能导致队空，只有插入操作，才可能导致队满因此
每次删除操作成功时，都令tag=0；
每次插入操作成功时，都令tag=1；
队满条件：front == rear && tag == 1
队空条件：front == rear && tag == 0
队列元素个数：(rear+MaxSize-front)%MaxSize

3.2.3队列的链式存储结构

带头结点

初始化：

#include<bits/stdc++.h>
using namespace std;
#define ElemType int
typedef struct LinkNode{     //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{              //链式队列
    LinkNode *front,*rear;   //队列的队头和队尾指针
}LinkQueue;

//初始化(带头结点)
void InitQueue(LinkQueue &Q){
    // front、rear均指向头结点
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

判断是否队空：

//判断队空
bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
        return true;
    else 
        return false;
}

入队：

//入队
void EnQueue(LinkQueue &Q,ElemType e){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data = e;
    s->next = NULL;
    Q.rear->next=s;         //将新结点插入到rear之后
    Q.rear=s;               //修改表尾指针
}

出队：

//出队
bool DeQueue(LinkQueue &Q,ElemType &e){
    if(Q.front==Q.rear)
        return false;
    LinkNode *p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)            //最后一个结点出队
        Q.rear=Q.front;      //修改rear指针
    free(p);                 //释放结点空间
    return true;
}

不带头结点

初始化：

#define ElemType int
typedef struct LinkNode{     //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
  
typedef struct{              //链式队列
    LinkNode *front,*rear;   //队列的队头和队尾指针
}LinkQueue;

//初始化
void InitQueue(LinkQueue &Q){
    // front、rear均指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}

判断是否队空：

//判断队空
bool IsEmpty(LinkQueue Q){
    if(Q.front==NULL)
        return true;
    else
        return false;
}

入队：

//入队
void EnQueue(LinkQueue &Q,ElemType e){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data = e;
    s->next = NULL;
    if(Q.front==NULL){
        Q.front=s;
        Q.rear=s;
    }else{
        Q.rear->next=s;
        Q.rear=s;
    }
}

出队：

//出队
bool DeQueue(LinkQueue &Q,ElemType &e){
    if(Q.front==NULL)
        return false;
    LinkNode *p=Q.front;
    e=p->data;
    Q.front=p->next;
    if(Q.rear==p){
        Q.front=NULL;
        Q.rear=NULL;
    }
    free(p);
    return true;
}

3.2.4双端队列

双端队列： 只允许从两端插入、从两端删除的线性表。
输入受限的双端队列： 只允许从一端插入、从两端删除的线性表。
输出受限的双端队列： 只允许从两端插入、从一端删除的线性表。

3.3矩阵的压缩存储

一维数组的存储结构：
起始地址：LOC
各数组元素大小相同，且物理上连续存放。
数组元素a[i]的存放地址= LOC + i * sizeof(ElemType)<数组下标从0开始>
在这里插入图片描述

二维数组的存储结构：
分为行优先和列优先，本质就是把二维的逻辑视角转换为内存中的一维储存
M行N列的二维数组b[M][N]中，若按行优先存储，则b[i][j]的存储地址=LOC + (i*N + j) * sizeof(ElemType)
M行N列的二维数组b[M][N]中，若按列优先存储，则b[i][j]的存储地址= LOC + ( j*M+ i ) * sizeof(ElemType)
二维数组也有随机存储的特性
在这里插入图片描述

对称矩阵：
若n阶方阵中任意一个元素ai,j都有ai,j = aj,i则该矩阵为对称矩阵
普通存储：n∗nn * nn∗n二维数组
压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区），按行优先原则将各元素存入一维数组中
数组大小应为多少：(1+n)∗n/2(1+n)*n/2(1+n)∗n/2

按行优先的原则，ai,j是第几个元素：
k={i(i−1)2+j−1,i≥j（下三角区和主对角线元素）j(j−1)2+i−1,i<j（上三角区元素 aij=aji） k = \begin{cases} \frac{i(i-1)}{2} + j - 1, & i \ge j \quad \text{（下三角区和主对角线元素）} \\\\ \frac{j(j-1)}{2} + i - 1, & i < j \quad \text{（上三角区元素 } a_{ij} = a_{ji} \text{）} \end{cases} k=⎩ ⎨ ⎧​2i(i−1)​+j−1,2j(j−1)​+i−1,​i≥j（下三角区和主对角线元素）i<j（上三角区元素 aij​=aji​）​
在这里插入图片描述

三角矩阵：
压缩存储策略：
按行优先原则将橙色区域元素存入一维数组。并在最后一个位置存储常量c

下三角:
按行优先的原则，ai,j是第几个元素：
k={i(i−1)2+j−1,i≥j（下三角区和主对角线元素）n(n+1)2,i<j（上三角区元素 aij=aji） k = \begin{cases} \frac{i(i-1)}{2} + j - 1, & i \ge j \quad \text{（下三角区和主对角线元素）} \\\\ \frac{n(n+1)}{2}, & i < j \quad \text{（上三角区元素 } a_{ij} = a_{ji} \text{）} \end{cases} k=⎩ ⎨ ⎧​2i(i−1)​+j−1,2n(n+1)​,​i≥j（下三角区和主对角线元素）i<j（上三角区元素 aij​=aji​）​
上三角:
按行优先的原则，ai,j是第几个元素：
k={(2n−i+2)(i−1)2+(j−1),i<=j（上三角区和主对角线元素）n(n+1)2,i>j（下三角区元素 aij=aji） k = \begin{cases} \frac{(2n-i+2)(i-1)}{2} + (j - 1), & i <= j \quad \text{（上三角区和主对角线元素）} \\\\ \frac{n(n+1)}{2}, & i > j \quad \text{（下三角区元素 } a_{ij} = a_{ji} \text{）} \end{cases} k=⎩ ⎨ ⎧​2(2n−i+2)(i−1)​+(j−1),2n(n+1)​,​i<=j（上三角区和主对角线元素）i>j（下三角区元素 aij​=aji​）​

在这里插入图片描述

稀疏矩阵：
非零元素的个数远远少于矩阵元素的个数

压缩存储策略：
顺序存储–三元组<行，列，值>，失去了数组随机存储的特性
在这里插入图片描述

压缩存储策略2：链式存储，十字链表法

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布