[数据结构] C语言队列(链表实现)

  • A+
所属分类:C++学习 菜鸟笔记

英语课日常摸鱼,写个队列。

懒得封装了,一团糊

队列结构

无论是用数组还是链表来实现队列,关键就在于用front和rear指针去维护整个队列。

注意考虑好各个方法实现的逻辑完整性,不然很容易出现漏洞。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<unistd.h>
#include<string>
#include<iostream>
using namespace std;
#define MAXQSIZE 10
#define MAXMSGSIZE 64u

struct Msg{
    int msgSize;
    char *content;
    Msg *next;
};

typedef struct Queue{
    int count;
    Msg *front;
    Msg *rear;
}QUEUE;

void initNewChunk(Msg *raw){
    raw->msgSize = 0;
    raw->content = NULL;
    raw->next = NULL;
}

QUEUE *init(){
    QUEUE *queue_ptr = (QUEUE*)malloc(sizeof(QUEUE));
    queue_ptr->front = queue_ptr->rear =(Msg*)malloc(sizeof(Msg));
    queue_ptr->count=0;
    initNewChunk(queue_ptr->rear);
    return queue_ptr;
}

void getInput(char *buf,unsigned int maxlen){
    for(int i=0;i<maxlen-1;i++){
        read(0,buf+i,1);
        if(*(buf+i) == '\n'){
            *(buf+i) = '\x00';
            break;
        }
    }
    *(buf+maxlen-1) = '\x00';
}

bool full(QUEUE *queue){
    return (queue->count == MAXQSIZE)?true:false;
}

void queue_flush(QUEUE *queue){
    Msg *tmp;
    while(queue->rear!=queue->front){
        free(queue->front->content);
        tmp = queue->front->next;
        free(queue->front);
        queue->front = tmp;
    }
    queue->count=0;
}

void pre_exit(QUEUE *queue){
    printf("exit...");
    queue_flush(queue);
    free(queue->rear);
    exit(-1);
}

void push(QUEUE *queue){
    unsigned int len;
    printf("How long is your message (maxlen=%d): ",MAXMSGSIZE);
    scanf("%d",&len);
    len = (len>MAXMSGSIZE) ? MAXMSGSIZE:len;
    queue->rear->msgSize = len;
    queue->rear->content = (char *)malloc(len+1);
    if(!(queue->rear->content)){
        printf("Malloc Error!");
        pre_exit(queue);
    }
    memset(queue->rear->content,0,len+1);
    printf("Please leave your message: ");
    getInput(queue->rear->content,len+1);
    fflush(stdin);
    printf("Successfully!");
    queue->rear->next = (Msg*)malloc(sizeof(Msg));
    if(!(queue->rear->next)){
        printf("Malloc Error!");
        pre_exit(queue);
    }
    queue->count++;
    initNewChunk(queue->rear->next);
    queue->rear = queue->rear->next;
}

void pop(QUEUE *queue){
    Msg *tmp;
    puts("Pop a message\n----------------");
    printf("msglen: %d\ncontent: ",queue->front->msgSize);
    write(1,queue->front->content,queue->front->msgSize);
    puts("\n----------------");
    queue->count--;
    free(queue->front->content);
    tmp=queue->front->next;
    free(queue->front);
    queue->front = tmp;
}

void check(QUEUE *queue){
    printf("-------------\ncount:%d MAXQSIZE:%d\n-------------\n",queue->count,MAXQSIZE);
}


int main(){
    int s = 0;
    QUEUE *myqueue = init();
    while(1){
    printf("\nSelect:\n0. Push\n1. Pop\n2. Check queue\n3. flush\n4. Exit\n>>> ");
    scanf("%d",&s);
    fflush(stdin);
    switch(s){
        case 0:
            if(full(myqueue))
                printf("Queue is full, you can try tu flush.\n");
            else
                push(myqueue);
            break;
        case 1:
            if(myqueue->count == 0)
                printf("-------------\nQueue is emptr.\n-------------\n");
            else
                pop(myqueue);
            break;
        case 2:
            check(myqueue);
            break;
        case 3:
            queue_flush(myqueue);
            break;
        case 4:
            return 0;
        default:
            printf("I don't konw!");
        }
    }
}
eqqie

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: