江小南

V1

2022/12/10阅读:26主题:萌绿

【408篇】C语言笔记-第十三章(栈与队列&考研真题实战)

第一节:栈的原理

1. 栈

stack:堆栈,又称堆叠,先进后出-FILO(First In Last Out)。

栈:只允许在一端进行插入或删除操作的线性表,栈顶(Top)。

2. 栈的基本操作:

顺序存储实现栈

typedef struct{
    Elemtype data[50];
    int top;
}SqStack;
SqStack S;

元素入栈:

S.data[++S.top]=4

# 相当于以下两行
S.top=S.top+1;
S.data[S.top]=4;

元素出栈:

x=S.data[S.top--];

# 相当于以下两行,x表示出栈的元素值
x=S.data[S.top];
S.top=S.top-1;

空栈:

# 表示栈为空,可以作为初始化栈
S.top=-1

栈满:

# 表示栈满
S.top=MaxSize-1;

链式存储实现栈

初始化栈:

# 空栈,也可以初始化栈
LiStack Lhead=(LiStack)malloc(sizeof(struct Linknode));
Lhead->next=NULL;
LiStack top=NULL;

入栈:

top=(LiStack)malloc(sizeof(struct Linknode));
top->next=NULL;
top->data=1;
top->next=Lhead->next;
Lhead->next=top;

出栈:

# c为要出栈的元素。链表表示栈,相当于头插法,那么出栈就表示为
c=top->data;
Lhead->next=top->next;
free(top);
top=Lhead->next;

栈空栈满:

# 为真,则栈为空
Lhead->next==null

对于链表实现的栈,只要还有剩余内存,就可以继续添加元素。

第二节:初始化栈-入栈-出栈实战

#include <stdio.h>

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];  // 数组
    int top;
}SqStack;

// 初始化栈
void InitStack(SqStack &S){
    S.top=-1// -1代表栈为空
}

// 判断栈是否为空
bool StackEmpty(SqStack S){
    if(S.top==-1){
        return true;
    } else{
        return false;
    }
}
// 入栈
bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1){  // 判断栈是否满了
        return false;
    }
    S.data[++S.top]=x;
    return true;
}
// 出栈
bool Pop(SqStack &S,ElemType x){
    if(-1==S.top){
        return false;
    }
    x=S.data[S.top--];
    return true;
}

// 获取栈顶元素
bool GetTop(SqStack S,ElemType &x){
    if(-1==S.top){
        return false;
    }
    x=S.data[S.top];
    return true;
}
int main() {
    SqStack S;
    InitStack(S); // 初始化栈
    bool flag;
    flag=StackEmpty(S);// 判断栈是否为空
    if(flag){
        printf("stack is empty\n");
    }
    Push(S,3);  // 入栈
    Push(S,4);
    Push(S,5);
    Push(S,6);
    Push(S,7);
    Push(S,8); // 只能放5个元素,8实际没有放入
    ElemType m;
    flag=GetTop(S,m);// 获取栈顶元素
    if(flag){
        printf("top is %d\n",m);
    }
    flag=Pop(S,m); // 出栈
    if(flag){
        printf("pop is %d\n",m);
    }
    flag=GetTop(S,m);// 获取栈顶元素
    if(flag){
        printf("top is %d\n",m);
    }
    return 0;
}
F:\Computer\Project\practice\13\13.2-stack\cmake-build-debug\13_2_stack.exe
stack is empty
top is 7
pop is 7
top is 6

进程已结束,退出代码为 0

第三节:队列-循环队列原理解析

1. 队列

队列(Queue)简称队,也是一种操作受限的线性表,只允许在表的一端插入,而在表的另一端进行删除。向队列中插入元素称为入队或进队,删除元素称为出队或离队。先进先出-FIFO(First In First Out)。

队头(Front)。允许删除的一端,又称队首。

队尾(Rear)。允许插入的一端。

特性就是先进先出(First In First Out,FIFO)

2. 循环队列

#define MaxSize 5
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize]; // 数组,存储MaxSize-1个元素
    int front,rear; // 队列头,队列尾
}SqQueue;

SqQueue Q;

解读:循环队列依靠front和rear两个指针同时工作,当front和rear同时指向同一个位置时,说明是初实化状态,队列为空,但是对于d1图的情况,指向同一个位置,但是并不是为空。所以采用的方法就是d2的情况,牺牲一个存储单元。

循环队列元素入队

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){ // 判断队列是否已满
        return false;
    }
    Q.data[Q.rear]=x; // 放入元素
    Q.rear=(Q.rear+1)%MaxSize; // 改变队尾标记
    return true;
}

循环队列元素出队

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

队列的链式存储

队列的链式表示称为链队列。它实际上是一个同时带有队头指针和队尾指针单链表。头指针指向队头结点,尾指针指向队尾结点,即单链表的最后一个结点。

模拟动画链接: https://www.cs.usfca.edu/~galles/visualization/QueueLL.html

存储结构

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;  // 链表结点的结构体
typedef struct{
    LinkNode *front,*rear; // 链表头,链表尾
}LinkQueue; // 先进先出
LinkQuete Q;

第四节:循环队列实战-数组实现

#include <stdio.h>

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; // 数组,存储MaxSize-1个元素
    int front,rear; // 队列头,队列尾
}SqQueue;

// 队列初始化
void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;  // 初始化两个指针相等且为0
}

// 判空
bool isEmpty(SqQueue &Q){
    if(Q.rear==Q.front){  // 不需要为0
        return true;
    } else{
        return false;
    }
}

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

// 出队
bool DeQueue(SqQueue &Q,ElemType &x){
    bool ret;
    ret=isEmpty(Q);
    if(ret){
        return false;
    }
    x=Q.data[Q.front]; // 先进先出
    Q.front=(Q.front+1)%MaxSize;
    return true;
}
int main() {
    SqQueue Q;
    bool ret; // 存储返回值
    InitQueue(Q);  // 队列初始化
    ret=isEmpty(Q); // 判空
    if(ret){
        printf("queue is empty\n");
    } else{
        printf("queue is not empty\n");
    }
    ret=EnQueue(Q,3);
    ret=EnQueue(Q,4);
    ret=EnQueue(Q,5);
    ret=EnQueue(Q,6); // 最大入队MaxSize-1个元素
    if(ret){
        printf("enqueue success\n");
    } else{
        printf("enqueue failed\n");
    }
    ret=EnQueue(Q,7); // 超过最大MaxSize-1,无法入队
    if(ret){
        printf("enqueue success\n");
    } else{
        printf("enqueue failed\n");
    }
    ElemType e; // 保存出队元素
    ret=DeQueue(Q,e);
    if(ret){
        printf("deque success %d\n",e);
    } else{
        printf("deque failed\n");
    }
    ret=DeQueue(Q,e);
    if(ret){
        printf("deque success %d\n",e);
    } else{
        printf("deque failed\n");
    }
    return 0;
}
F:\Computer\Project\practice\13\13.3-cycle-queue\cmake-build-debug\13_3_cycle_queue.exe
queue is empty
enqueue success
enqueue failed
deque success 3
deque success 4

进程已结束,退出代码为 0

第五节:循环队列实战-链表实现

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear; // 链表头,链表尾
}LinkQueue; // 先进先出

// 初始化队列
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*) malloc(sizeof(LinkNode)); // 头和尾指向同一个结点
    Q.front->next=NULL// 头结点的next指针为NULL
}

// 入队 尾部插入法
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode*) malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; // rear始终指向尾部
    Q.rear=s;
}

// 出队 头部删除法
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear){
        return false// 队列尾空
    }
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;  // 断链
    if(Q.rear==p){
        Q.rear=Q.front; // 队列置为空
    }
    free(p);
    return true;
}
int main() {
    LinkQueue Q;
    InitQueue(Q);  // 初始化队列
    EnQueue(Q,3);  // 入队
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);
    bool ret;
    ElemType e; // 存储出队元素
    ret=DeQueue(Q,e);
    if(ret){
        printf("dequeue success %d\n",e);
    } else{
        printf("dequeue failed\n");
    }
    return 0;
}
F:\Computer\Project\practice\13\13.5-queue-cycle\cmake-build-debug\13_5_queue_cycle.exe
dequeue success 3

进程已结束,退出代码为 0

第六节:考研真题

解答

(1)采用链式存储结构(两段式单向循环链表),队头指针为front,队尾指针为rear。因为第二个要求入队时,允许增加队列占用空间,所以必须采用链式存储

(2)初始时,创建一个只有一个空闲结点的两段式单向循环链表,头指针front和尾指针rear均指向空闲结点。

队空的判定条件:front=rear。

队满的判定条件:front==rear->next。

(3)

(4)入队操作和出队操作的基本过程

入队:

若(front==rear->next) // 队满

则在rear后面插入一个新的空闲结点。入队元素保存到rear所值节点中,rear=rear->next;返回。

出队:

若(front==rear) // 队空

则出队失败,返回;

取front所指结点中的元素e,front=front->next;返回e。

不要求代码实现,但为了理解原理,源码如下:

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next; // 指向下一个结点
}LNode,*LinkList;

// 入队
void EnQueue(LinkList front,LinkList &rear,ElemType val){
    LinkList pnew;
    if(rear->next==front){
        // 队列满,申请一个结点的空间,放入队列
        pnew=(LinkList) malloc(sizeof(LNode));
        rear->data=val; // 把入队元素放入rear指向的节点
        rear->next=pnew; // 放了一个结点,相当于做了分割
        pnew->next=front;
        rear=pnew;
    } else// 队列不满时,直接放入,让rear后移一个结点
        rear->data=val;
        rear=rear->next;
    }
}

// 出队
void DeQueue(LinkList &front,LinkList rear){
    if(front==rear){
        printf("queue is empty\n");
    } else{
        printf("the data is %d\n",front->data);
        front=front->next;
    }
}

void CircleQueue(LinkList &front,LinkList &rear){
    // 队列头和队列尾都指向同一个结点,这是队列既是空的,也是满的
    front=(LinkList) malloc(sizeof(LNode));
    rear=front;
    rear->next=front;
    // 入队
    EnQueue(front,rear,3);
    EnQueue(front,rear,4);
    EnQueue(front,rear,5);
    // 出队
    DeQueue(front,rear);
    DeQueue(front,rear);
    DeQueue(front,rear);
}
int main() {
    LinkList front,rear;
    CircleQueue(front,rear);
    return 0;
}
F:\Computer\Project\practice\13\13.6-2019-42\cmake-build-debug\13_6_2019_42.exe
the data is 3
the data is 4
the data is 5

进程已结束,退出代码为 0

分类:

后端

标签:

C++

作者介绍

江小南
V1