数据结构六

一、关于线性表中栈的顺序存储和链式存储方式的实现方式

1.顺序存储

#include <stdio.h>

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

typedef struct{
    int data[MaxSize];
    int front,rear;//队头指针和队尾指针
}SqQueue;
//初始化队列
void InitQueue(SqQueue* Q){
    Q->front=Q->rear=0;
}
//判断队列是否为空
int EmptyQueue(SqQueue* Q){
    return Q->front==Q->rear;
}
//插入一个元素(入队)
int EnterQueue(SqQueue* Q,int x){
    if((Q->rear+1)%MaxSize==Q->front) return 0;//队列已经满了
    Q->data[Q->rear]=x;
    Q->rear=(Q->rear+1)%MaxSize;//队尾指针加1取模
    return 1;
}
//删除一个元素(出队)
int ExitQueue(SqQueue* Q,int* x){
    if(Q->rear==Q->front)return 0;//队列为空
    *x=Q->data[Q->front];
    Q->front=(Q->front+1)%MaxSize;
    return 1;
}
//获取队头元素
int GetHeader(SqQueue* Q,int* x){
    if(Q->front==Q->rear) return 0;
    *x=Q->data[Q->front];
    return 1;
}
//遍历
void DisplayQueue(SqQueue* Q){
    for (int i = Q->front; i <Q->rear;i++) {
        printf("The %dth data of sequence-queue is %d.\n",i,Q->data[i]);
    }
}
int main() {
    int x=-1;
    //1.声明一个队列
    SqQueue Q;
    //2.初始化队列
    InitQueue(&Q);
    //3.插入元素
    if(EnterQueue(&Q,1)){
        printf("The sequence-queue inserts one data!\n");
    }else{
        printf("The sequence-queue doesn't insert one data,and queue is full!\n");
    }
    EnterQueue(&Q,20);
    EnterQueue(&Q,10);
    EnterQueue(&Q,11);
    //4.删除一个元素
    if(ExitQueue(&Q,&x)){
        printf("The sequence-queue deletes one data,and the data which is deleted is %d.\n",x);
    }else{
        printf("The sequence-queue doesn't delete one data,and queue is empty.\n");
    }
    //5.判断队列是否为空
    printf("The sequence-queue is %s\n", EmptyQueue(&Q)?"empty":"not empty");
    //6.获取队头元素
    if(GetHeader(&Q,&x)){
        printf("The head data of sequence-queue is %d.\n",x);
    }else{
        printf("The sequence-queue is empty.\n");
    }
    //遍历所有元素
    DisplayQueue(&Q);
    return 0;
}

实现结果：

D:\project\clion\ch2\cmake-build-debug\sequence_queue.exe
The sequence-queue inserts one data!
The sequence-queue deletes one data,and the data which is deleted is 1.
The sequence-queue is not empty
The head data of sequence-queue is 20.
The 1th data of sequence-queue is 20.
The 2th data of sequence-queue is 10.
The 3th data of sequence-queue is 11.

Process finished with exit code 0

2.链式存储（有头节点）

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

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

struct LinkQueue{//链式队列
    struct LinkNode* front,* rear;//队列的队头和队尾指针
};
//创建一个节点
struct LinkNode* CreateNode(int x){
    struct LinkNode* s=(struct LinkNode*) malloc(sizeof(struct LinkNode));
    s->data=x;
    s->next=NULL;
    return s;
}
//初始化队列
void InitQueue(struct LinkQueue* Q){
    Q->front=Q->rear=(struct LinkNode *) malloc(sizeof(struct LinkNode));
    Q->front->next=NULL;
}
//判断队列是否为空
int EmptyQueue(struct LinkQueue* Q){
    return Q->front==Q->rear;
}
//插入一个元素(入队)
int EnterQueue(struct LinkQueue* Q,int x){
    struct LinkNode* s= CreateNode(x);
    Q->rear->next=s;
    Q->rear=s;
    return 1;
}
//删除一个元素(出队)
int ExitQueue(struct LinkQueue* Q,int* x){
    struct LinkNode* p=Q->front->next;
    if(Q->front==Q->rear) return 0;
    *x=p->data;//获取待删节点的值
    Q->front->next=p->next;//修改头节点的next的值
    if(Q->rear==p){
        Q->rear=Q->front;
    }
    free(p);
    return 1;
}
//遍历队列
void DisplayQueue(struct LinkQueue* Q){
    struct LinkNode* p=Q->front;
    int j=0;
    while (p!=NULL){
        printf("The %dth node data of linked-queue which doesn't have head is %d\n",j,p->data);
        j++;
        p=p->next;
    }
}
int main(){
    int x=-1;
    //1.声明一个队列
    struct LinkQueue Q;
    //2.初始化队列
    InitQueue(&Q);
    //3.插入元素
    EnterQueue(&Q,1);
    EnterQueue(&Q,10);
    EnterQueue(&Q,2);
    //4.遍历队列
    DisplayQueue(&Q);
    //5.删除元素
    ExitQueue(&Q,&x);
    printf("The linked-queue which has head deletes %d\n",x);

    DisplayQueue(&Q);
    return 0;
}

实现结果：

D:\project\clion\ch2\cmake-build-debug\linked_queue_have_head.exe
The 0th node data of linked-queue which doesn't have head is 1925056
The 1th node data of linked-queue which doesn't have head is 1
The 2th node data of linked-queue which doesn't have head is 10
The 3th node data of linked-queue which doesn't have head is 2
The linked-queue which has head deletes 1
The 0th node data of linked-queue which doesn't have head is 1925056
The 1th node data of linked-queue which doesn't have head is 10
The 2th node data of linked-queue which doesn't have head is 2

Process finished with exit code 0

3.链式存储（无头结点）

#include "stdio.h"
#include "stdlib.h"

struct LinkNode{
    int data;
    struct LinkNode* next;
};

struct LinkQueue{
    struct LinkNode* front,* rear;
};
struct LinkNode* CreateNode(int x){
    struct LinkNode* s=(struct LinkNode*) malloc(sizeof(struct LinkNode));
    if(!s){
        printf("No enough memory to allocate!\n");
        exit(0);
    }
    s->data=x;
    s->next=NULL;
    return s;
}
//初始化队列链表
void InitQueue(struct LinkQueue* Q){
    Q->front=Q->rear=NULL;
}
//判断链队是否为空
int EmptyQueue(struct LinkQueue* Q){
    return Q->front==NULL;
}
//插入一个元素
int EnterQueue(struct LinkQueue* Q,int x){
    struct LinkNode* s=CreateNode(x);
    if(Q->front==NULL){//在空队列中插入第一个元素
        Q->front=s;//修改队头队尾指针
        Q->rear=s;
    }else{//将新节点插入到rear节点之后
        Q->rear->next=s;//新节点插入到rear节点之后
        Q->rear=s;//修改rear指针
    }
    return 1;
}
//删除一个元素
int ExitQueue(struct LinkQueue* Q,int* x){
    struct LinkNode* p=Q->front;
    if(Q->front==NULL) return 0;//空队
    *x=p->data;
    Q->front=p->next;//修改front值
    if(Q->front==p){//如果是最后一个节点
        Q->front=NULL;
        Q->rear=NULL;
    }
    free(p);
    return 1;
}
//遍历链队
void DisplayQueue(struct LinkQueue* Q){
    int j=1;
    struct LinkNode* p=Q->front;
    while (p!=NULL){
        printf("The %dth node data of linked-queue which doesn't have head is %d\n",j,p->data);
        j++;
        p=p->next;
    }
}
int main(){
    int x=-1;
    //1.声明一个队列
    struct LinkQueue Q;
    //2.初始化队列
    InitQueue(&Q);
    //3.插入元素
    EnterQueue(&Q,1);
    EnterQueue(&Q,23);
    EnterQueue(&Q,3);
    EnterQueue(&Q,33);
    //4.队列判空
    printf("The linked-queue which doesn't have head is %s\n",EmptyQueue(&Q)==1?"empty":"not empty");
    //5.遍历队列
    DisplayQueue(&Q);
    //6.删除一个元素
    ExitQueue(&Q,&x);
    printf("The linked-queue which doesn't have head deletes one data,and data is %d\n",x);

    DisplayQueue(&Q);
    return 0;
}

实现结果：

D:\project\clion\ch2\cmake-build-debug\linked_queue_no_have_head.exe
The linked-queue which doesn't have head is not empty
The 1th node data of linked-queue which doesn't have head is 1
The 2th node data of linked-queue which doesn't have head is 23
The 3th node data of linked-queue which doesn't have head is 3
The 4th node data of linked-queue which doesn't have head is 33
The linked-queue which doesn't have head deletes one data,and data is 1
The 1th node data of linked-queue which doesn't have head is 23
The 2th node data of linked-queue which doesn't have head is 3
The 3th node data of linked-queue which doesn't have head is 33

Process finished with exit code 0