数据结构【线性表篇】(四）

数据结构【线性表篇】(四）

---

---

前言

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下竞争压力逐渐增大，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个寒假巩固速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

---

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
.

---

目录

一、栈

(一)、栈的顺序存储

参考代码

//顺序栈
#include<bits/stdc++.h>
using namespace std;

#define MaxSize 10                      //定义栈中元素的最大个数

//顺序存储：给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType)
typedef struct{
    int data[MaxSize];                  //静态数组存放栈中元素
    int top;                            //栈顶指针
}SqStack;

void InitStack(SqStack &S){
    S.top = -1;                          //初始化栈顶指针
    //也可以使其等于0，然后判空时，把-1改为0
}

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

//新元素入栈
bool Push(SqStack &S,int x){
    if(S.top==MaxSize-1)               //栈满(top==MaxSize)，报错
        return false;
    S.top = S.top+1;                   //指针先加1
    S.data[S.top]=x;                   //新元素入栈
    //上两句等价于S.data[++S.top]=x;      *注意++S.top，而不是S.top++
    return true;
}

//出栈操作
int Pop(SqStack &S){
    int x;
    if(S.top==-1)                       //栈空，报错,返回-1
        return -1;
    x = S.data[S.top];                  //栈顶元素先出栈
    S.top = S.top-1;                    //指针再减1
    //上两句等价于x = S.data[S.top--];
    return x;
}

//读栈顶元素
int GetTop(SqStack S){
    int x;
    if(S.top==-1)                       //栈顶，报错，返回-1
        return -1;
    x=S.data[S.top];                    //x记录栈顶元素
    return x;
}

void testSqStack(){
    SqStack S;                          //声明一个顺序栈(分配空间)
    InitStack(S);                    //初始化栈

    Push(S,1);                    //新元素入栈
    Push(S,2);
    Push(S,3);

    if(!SqStackEmpty(S)){               //判断栈空
        cout<<"栈非空"<<endl;
    }else cout<<"栈空"<<endl;

    int x = GetTop(S);                  //读取栈顶元素x
    cout<<x<<endl;

    int x1 = Pop(S);                 //弹出栈顶元素x1
    cout<<x1<<endl;

    int x2 = GetTop(S);                 //读取栈顶元素x2
    cout<<x2<<endl;

}
int main(){
    testSqStack();
    return 0;
}

---

(二)、栈的链式存储

#include<bits/stdc++.h>
using namespace std;

typedef struct Linknode{
    int data;                               //数据域
    struct Linknode *next;                    //指针域
}  *LiStack;

int main(){
    return 0;
} 

---

(三)、共享栈

#include<bits/stdc++.h>
#define MaxSize 10                           //定义栈中元素的最大个数
typedef struct {
    int data[MaxSize];                       //静态数组存放栈中元素
    int top0;                                //0号栈栈顶指针
    int top1;                                //1号栈栈顶指针
}ShStack;

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

//栈满的条件：top0+1==top1

---

二、队列

(一)、队列的顺序存储

#include<bits/stdc++.h>
using namespace std;
#define MaxSize 10                         //定义队列中元素的最大个数
typedef struct{
    int data[MaxSize];                    //用静态数组存放队列元素
    int front,rear;                       //队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    //初始时队头、队尾指针指向0
    Q.rear=Q.front=0;
}

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

//入队
bool EnQueue(SqQueue &Q,int x){
    if(Q.rear==MaxSize-1) return false;       //队满则报错
    //if((Q.rear+1)%MaxSize==Q.front)         //循环队列
    Q.data[Q.rear]=x;                         //将x插入队尾
    Q.rear=Q.rear+1;                          //队尾指针后移
    //Q.rear=(Q.rear+1)%MaxSize;              //循环队列——队尾指针加1取模
    return true;
}

//循环队列——出队（删除一个队头元素，并用x返回）
bool DeQueue(SqQueue &Q,int &x){
    if(Q.rear==Q.front) return false;
    x = Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

//获得头元素的值，用x返回
bool GetHead(SqQueue Q,int &x){
    if(Q.rear==Q.front) return false;       //队空则报错
    x = Q.data[Q.front];
    return true;
}


void testQueue(){
    SqQueue Q;                              //声明一个队列（顺序存储）
    InitQueue(Q);                        //初始化队列

    if(SqQueueEmpty(Q)) cout<<"队列为空"<<endl;
    else cout<<"队列非空"<<endl;

    EnQueue(Q,1);                     //入队
    EnQueue(Q,2);
    EnQueue(Q,3);

    if(SqQueueEmpty(Q)) cout<<"队列为空"<<endl;
    else cout<<"队列非空"<<endl;

    int x;
    GetHead(Q,x);                        //获取头元素的值
    cout<<x<<endl;

    DeQueue(Q,x);                     //出队
    cout<<x<<endl;

    GetHead(Q,x);                        //获取更新后的头元素的值
    cout<<x<<endl;

}

int main(){
    testQueue();
    return 0;
}

---

(二)、队列的链式存储

#include<bits/stdc++.h>
using namespace std;
#define Maxsize 10

typedef struct LinkNode{                    //链式队列结点
    int data;
    struct LinkNode *next;
}LinkNode;

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

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

bool IsEmptyWithNode(LinkQueue Q){
    if(Q.front==Q.rear) return true;
    else return false;
}

//初始化队列(不带头结点)
void InitQueueWithoutNode(LinkQueue &Q){
    //初始时 front、rear都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}

//判断队列是否为空(不带头结点)
bool IsEmptyWithoutNode(LinkQueue Q){
    if(Q.front==NULL) return true;
    else return false;
}

//新元素入队(带头结点)
void EnQueueWithNode(LinkQueue &Q,int x){
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;                         //新结点插入到rear之后
    Q.rear=s;                               //修改表尾指针
}

//队头元素出队(带头结点)
bool DeQueueWithNode(LinkQueue &Q,int &x){
    if(Q.front==Q.rear)
        return false;                       //空队
    LinkNode *p=Q.front->next;
    x=p->data;                              //用变量x返回队头元素
    Q.front->next=p->next;                  //修改头结点的next指针
    if(Q.rear==p)                           //此次是最后一个结点出队
        Q.rear=Q.front;                     //修改rear指针
    free(p);                                //释放结点空间
    return true;
}

//队头元素出队(不带头结点)
bool DeQueueWithoutNode(LinkQueue &Q,int &x){
    if(Q.front==NULL)
        return false;                       //空队
    LinkNode *p=Q.front;                    //p指向此次出队的结点
    x=p->data;                              //用变量x返回队头元素
    Q.front=p->next;                        //修改front指针
    if(Q.rear==p) {                         //此次是最后一个结点出队
        Q.front=NULL;                       //front指向NULL
        Q.rear=NULL;                        //rear指向NULL
    }
    free(p);                                //释放结点空间
    return true;
}


//新元素入队(不带头结点)
void EnQueueWithoutNode(LinkQueue &Q,int x){
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL){                      //在空队列中插入第一个元素
        Q.front = s;                        //修改队头队尾指针
        Q.rear = s;
    }else{
        Q.rear->next=s;                     //新结点插入到rear结点之后
        Q.rear=s;                           //修改rear指针
    }
}

//获得头元素的值，用x返回
bool GetHead(LinkQueue Q,int &x){
    if(Q.rear==Q.front) return false;       //队空则报错
    LinkNode *p=Q.front->next;
    x=p->data;
    return true;
}

void testLinkQueue(){
    LinkQueue Q;                            //声明一个队列
    InitQueueWithNode(Q);                //初始化队列

    if(IsEmptyWithNode(Q)) cout<<"队列为空"<<endl;
    else cout<<"队列非空"<<endl;

    EnQueueWithNode(Q,1);                   //入队
    EnQueueWithNode(Q,2);
    EnQueueWithNode(Q,3);

    if(IsEmptyWithNode(Q)) cout<<"队列为空"<<endl;
    else cout<<"队列非空"<<endl;

    int x;                                      //出队，x返回出队元素
    DeQueueWithNode(Q,x);
    cout<<x<<endl;

    GetHead(Q,x);                           //获取出队后的队头元素x
    cout<<x<<endl;
}

int main(){
    testLinkQueue();
    return 0;
}

---

三、结语

感谢大家一直以来的不断支持与鼓励，码题集题库中的进阶塔350题正在逐步更新，之后会逐步跟进星耀，王者的题，尽请期待！！！
同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

愿你的结局，配得上你一路的颠沛流离。