数据结构王道强化应用题打卡表【第二章】（代码部分）

代码更贴近伪代码，未经过调试，仅用于回答初试题目准备

2.1 栈

1. 顺序栈（数组）

1. 写代码：定义顺序存储的栈（数组实现），数据元素是 int 型
2. 实现“出栈、入栈、判空、判满”四个基本操作

#define Maxsize 50

typedef struct{
    int data[Maxsize];
    int top; //栈顶指针，所指为栈顶元素
}stack;

//初始化
void Init(stack &s){
    s.top = -1;
}

//判空
bool empty(stack s){
    if(s.top == -1)
        return true;
    else 
        return false;
}

//判满
bool full(stack s){
    if(s.top == Maxsize - 1)
        return true;
    else 
        return false;
}

//入栈
bool push(stack &s, int x){
    if(full(s) == false){
        s.data[++s.top] = x; //栈顶指针先移动一位，再赋值
        return true;
    }
    else
        return false;      
}

//出栈
bool pop(stack &s){
    if(empty(s) == false){
        x = s.data[top--]; //取出栈顶元素，指针再移动
        return true;
    }
    else false;
}

2. 链式栈(单链)

写代码：定义链式存储的栈（单链表实现）

栈顶在链头，实现“出栈、入栈、判空、判满”四个基本操作

//节点定义
typedef struct node{
    int data;
    struct node *next;
}*stack, node;

//初始化
//带头结点
bool init(stack &s){
    s = (stack)malloc(sizeof(node));
    if(s == NULL) return false; //申请失败
    S->next = NULL; //此时栈为空
    return true;
}

//判空
bool empty(stack s){
    if(s->next == NUll) 
        return true;
    else
        false;
}

//无判满

//入栈
//头插法（头一直是不动的）
bool push(stack &s, int x){
    node *p;
    p = (node*)malloc(sizeof(node)); //申请一个新结点
    if(p == NULL) return false; //申请结点失败返回
    p->data = x;
    p->next = s->next;
    s->next = p;
    return true; //插入成功
}

//出栈
//弹出头结点后的第一个结点
///int pop(stack &s){ //万一为空返回值不好确定，故舍弃这种方法
bool pop(stack &s, int &x){
    if(empty(s) == true) return false; //栈空则无法弹栈
    node *p; 
    p = s->next; //记录要弹出的结点
    s->next = p->next; //头结点指向下下一个结点
    x = p->data; //记录结点权值
    free(p); //释放弹出的结点的空间
    return true;
}

3. 链式栈（双链）

1. 定义链栈
2. 实现基本操作（要求双链表实现，栈顶在链尾）

//定义栈结点
typedef struct node{
    int data;					//保存int型元素
    struct node *front, *next; //向前的指针和向后的指针
}node;

//定义链式栈（双链）
typedef struct stack{
    struct node *head, *rear; //定义两个指向链头和链尾的指针
}stack, *stackpo;

//初始化双向链栈
bool init(stackpo &s){
	s = (stack *)malloc(sizeof(stack)); //初始化一个链栈
    node *p = (node *)malloc(sizeof(node)); //新建一个头结点
    p->next = NULL; //此时栈空
    p->front = NULL;
    
    s->head = p; //链表头尾都是头结点
    s->rear = p;
       
    return true;
}

//判空
bool empty(stackpo s){
    if(s->head == s->rear)
        return true;
    else 
        return false;
}

//入栈（栈顶在链尾，从链尾插入）
bool push(stackpo &s, int x){
    node *p = (node *)malloc(sizeof(node)); //新建一个结点
    p->data = x; //结点赋值
    p->next = NULL; //
    p->front = s->rear;
    s->rear->next = p;
    s->rear = p;
    return true;
}

bool pop(stackpo &s,int &x){
    if(empty(s))
        return false;
    node *p = s->rear;
    x = p->data; //保存栈顶元素值
    s->rear = p->front; //更新链尾指针
    s->rear->next = NULL; //链尾next指向NULL
    free(p);
    return true;
}

2.2 队列

1. 顺序队列

1. 定义顺序存储的队列（数组实现），不要求循环

2. 实现“出队、入队、判空、判满”四个基本操作

//定义
#define Maxsize 50

typedef struct queue{
    int data[Maxsize];
    int head,rear;
}queue;

//初始化
void init(queue &q){
    q.head = q.rear = 0; //队尾指针指向最后一个元素的下一个位置；队头就队头
}

//判空
bool empty(queue q){
    if(q.head == q.rear) return true;
    else return false;
    
}

//判满（不完善）
bool full(queue q){
    if(q.rear == Maxsize) return true; //并不能代表队列已满，只是不能再入队了（eg.队列中仅有一个元素，放在数组最后一个位置，但队列仍有很多空位）
    else return false;
}

//入队
bool push(stack &q, int x){
    if(full(q)) return false;
    else{
        q.data[q.rear++] = x;
        return true;
    }
}

//出队
bool pop(stack &q, int &x){
    if(empty(q))
        return false;
    else{
        x = q.data[q.head++];
    	return true;
    }
}

2. 顺序循环队列

要求数组空间可以循环利用（修复上述bug）

• 2.1 - 2.3使用rear指向下一个要插入的位置的方法

• 2.4 - 2.6使用rear指向队列最后一个元素的方法（就是把上一点里的rear往前移一个位置，操作时需要+1）

2.1 牺牲一个位置区分队满队空

#define Maxsize 50

typedef struct queue{
    int data[Maxsize];
    int head, rear;
}queue;

//初始化
void init(queue &q){
    q.head = q.rear = 0; //head指向队头元素，rear指向下一个要插入的位置
}

//判空
bool empty(queue q){
    if(q.rear == q.head)
        return true;
    else false;
}

//判满
bool full(queue q){
    if((q.rear + 1) % Maxsize == q.head)
        return true;
    else 
        return false;
}

//入队
bool in(queue &q, int &x){
    if(!full(q)){
        q.data[q.rear] = x;
        q.rear = (q.rear + 1) % Maxsize;
        return true
    }
    else
        return false;     
}

//出队
bool out(queue &q, int &x){
    if(!empty(q)){
        x = q.data[q.head];
        q.head = (q.head + 1) % Maxsize;
        return true;
    }
    else 
        return false;
}

2.2 设count记录队列中元素个数

#define Maxsize 50

typedef struct queue{
    int data[Maxsize];
    int head, rear;
    int count; //记录当前队列中元素的个数
}queue;

//初始化
void init(queue &q){
    q.hear = q.rear = 0;
    q.count = 0;
}

//判满
bool full(queue q){
    if(q.count == Maxsize) //队列中元素数量已经到达最大值(第一次写这里写错了->_-> 不是Maxsize - 1啦)
        return true;
    else
        return false;
}

//判空
bool empty(queue q){
    if(q.count == 0)
        return true;
    else 
        return false;
}

//入队
bool (queue &q, int x){
    if(!full(q)){	//队列不满，可以入队
        q.data[q.rear] = x;
        q.rear = (q.rear + 1) % Maxsize;
        q.count ++;	//其实就比2.1方法多这一句->_->
        return true;
    } 
    else 
        return false;
        
}

//出队
bool out(queue &q, int &x){
    if(!empty(q)){ //不空就能出队
        x = q.data[q.head];
        q.head = (q.head + 1) % Maxsize;
        q.count --;
        return true;
        
    }
    else 
        return false;
}

2.3 使用flag区分队满队空

#define Maxsize 50

typedef struct queue{
    int data[Maxsize];
    int head, rear;
    int flag;
}queue;

//初始化
void init(queue &q){
    q.head = q.rear = 0;
    q.flag = 0; //flag为0表示队列上一个操作是出队（可能导致head==rear（此时队列为空））；为1表示为上一个操作是入队（可能导致head==rear(此时队列为满））
}

//判满
bool full(queue q){
    if(q.flag == 1 && q.head == q.rear)
        return true;
    else 
        return false;
}

//判空
bool empty(queue q){
    if(q.flag == 0 && q.head == q.rear)
        return true;
    else 
        return false;
}

//入队
bool in(queue &q, int x){
    if(!full(q)){
        q.data[q.rear] = x;
        q.rear = (q.rear + 1) % Maxsize;
        q.flag = 1;  //此次为入队，flag置1
        return true;
        
    }
    else 
        return false;
}

//出队
bool out(queue &q, int &x){
    if(!empty(q)){
        x = q.data[q.head];
        q.head = (q.head + 1) % Maxsize;
        q.flag = 0;	//此次是出队，flag置0
        return true;
        
    }
    else
        return false;
}

---

2.4 牺牲一个空间

#define Maxsize 50

typedef struct queue{
    int data[Maxsize];
    int head, rear;
}queue;

//初始化
void init(queue &q){
    q.head = 0;
    q.rear = -1; //此时队列为空，没有最后一个元素，插入一个才是下标为0是队尾元素
}

//判满
bool full(queue q){
    if((q.rear + 2) % Maxsize == q.head)
        return true;
    else 
        return false;
}

//判空
bool empty(queue q){
    if((q.rear + 1) % Maxsize == q.head)
        return true;
    else return false;
    
}

//入队
bool in(queue &q, int x){
    if(!full(q)){
        q.rear = (q.rear + 1) % Maxsize; //先移rear,再插入
        q.data[q.rear] = x;
        return true;
        
    }
    else 
        return false;
}

//出队
bool out(queue &q, int &x){
    if(!empty(q)){
        x = q.data[q.head];
        q.head = (q.head + 1) % Maxsize; //队（对）头就队（对）头 ->_->
        return true;
        
    }
    else
        return false;
}

2.5 增加队列元素个数count记录

#define Maxsize 50

typedef struct queue{
    int data[Maxsize];
    int head, rear;
    int count;
}queue;

//初始化
void init(queue &q){
    q.head = 0;
    q.rear = -1;
    q.count = 0; //初始队列为空
}

//判满
bool full(queue q){
    if(q.count == Maxsize)
        return true;
    else
        return false;
}

//判空
bool empty(queue q){
    if(q.count == 0)
        return true;
    else 
        return false;
}

//入队
bool in(queue &q, int x){
    if(!full(q)){
        q.rear = (q.rear + 1) % Maxsize;
        q.data[q.rear] = x;
        q.count ++;
        return true;
    }
    else
        return false;
}

//出队
bool out(queue &q, int &x){
    if(!empty(q)){
        x = q.data[q.head];
        q.head = (q.head + 1) % Maxsize;
        q.count --;
        return true;
    }
    else
        return false;
}

2.6 增设flag判断上一个操作 区分队满队空

#define Maxsize 50

typedef struct queue{
    int data[Maxsize];
    int head, rear;
    int flag;
}queue;

//初始化
void init(queue &q){
    q.head = 0;
    q.rear = -1;
    q.flag = 0;
}

//判满
bool full (queue q){
    if(q.flag == 1 && q.head == (q.rear + 1) % Maxsize)
}

//判空
bool empty(queue q){
    if(q.flag == 0 && q.head == (q.rear + 1) % Maxsize)
        return true;
    else 
        return false;
}

//入队
bool in(queue &q, int x){
    if(!full(q)){
        q.rear = (q.rear + 1) % Maxsize;
        q.data[q.rear] = x;
        q.flag = 1;
        return true;
    }
   else
       return false;
   
}

//出队
bool out(queue &q, int &x){
    if(!empty(q)){
        x = q.data[q.head];
        q.head = (q.head + 1) % Maxsize;
        q.flag = 0;
        return true;
        
    }
    else 
        return false;
}

2.7 链队列（带头结点）

入队在rear后面，出队在head的后面（head还是那个head，不变）

typedef struct node{
    int data;
    struct node *next;
}node;

typedef struct queue{
    node *head, *rear;
}queue;

//初始化
void init(queue &q){
    q.head = q.rear = (node *)malloc(sizeof(node)); //新申请一个结点作为头结点，头结点里不存数据
    q.rear->next = NULL; //队尾指针指向NULL
}

//判满
//不会满，不用判

//判空
bool empty(queue q){
    if(q.head == q.rear)	//此时head和rear都指向头结点
        return true;
    else
        false;
}

//入队
bool in(queue &q, int x){
    node *p = (node *)malloc(sizeof(node)); //申请新结点放x
    if(p == NULL)
        return false;	//申请结点失败
    p->data = x;	//新结点赋值
    p->next = NULL; //这里不能直接写NULL？？？只能写q.rear->next???
    
    q.rear->next = p;//①连上新的
    q.rear = p;//②改队尾指针
    return true;
    
}

//出队
//！出队的时候注意只有一个结点的情况，要改下rear
bool out(queue &q, int &x){
    if(!empty(q)){
        node *p = (node *)malloc(sizeof(node));
        if(p == NULL) return false; //申请结点失败
        p = q.head->next; //p指向头结点后的结点，即要出队的元素
        x = p->data; //用x传值
        
        q.head->next = p->next; //①改变head的next为next的next（可能为NULL，可能为结点），所以不能单纯像入队那样改为NULL
        if(p == q.rear) //此时队列只有这一个元素
            q.rear = q.head; //队尾指针只能指向队头（空结点）了
        free(p); //②释放这个结点空间
        return true;
    }
    else
        return false;
}

2.8 链队列（不带头结点）

typedef struct node{
    int data;
    struct node *next;
}node;

typedef struct queue{
    node *head, *rear;
}queue;

//初始化
void init(queue &q){
    q.head = q.rear = NULL;
}

//判满
//不用判

//判空
bool empty(queue q){
    if(q.head == NULL)
        return true;
    else 
        return false;
}

//入队
//不带头结点多一个队空的情况
bool in(queue &q, int x){
    node *p = (node *)malloc(sizeof(node)); //申请新结点保存x
    if(p == NULL) return false;
    p->data = x; //给新结点赋值x
    p->next = NULL;//插入队尾，next为NULL
    
    if(empty(q)){ //此时队空
        q.head = q.rear = p; //队头队尾都指向这个元素
    }
    else{ //队不空就常规操作
        q.rear->next = p;	//①先改rear的next指向新结点
        q.rear = p;    //②改队尾指针
    }
    return true;
}

//出队
bool out(queue &q, int &x){
    if(!empty(q)){
        node *p = (node *)malloc(sizeof(node));	//申请新结点
        if(p == NULL) return false;	//申请结点失败
        
        p = q.head; //p指向头结点
        x = p->data;//用x传值
        q.head = p->next; //①头结点后移一位（可能是NULL可能是结点）
    	if(q.head == q.rear){	//队列中只有一个元素
            q.rear = NULL;		//要修改队尾指针为NULL
        }    
        free(p); //②释放空间
        return true;
    }
    else 
        return false;
}

参考文档：

1. CSDN博客——王道考研数据结构代码总结

2. 王道官方数据结构应用题打卡表——【数据结构应用题】打卡表参考文档