鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

链式队列的实现

来源:互联网 作者:佚名 时间:2017-02-11 10:29
今天实现以下链式的队列,首先,要清楚对列是什么: 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(head)进行删除操作,而在表的后端(tail)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的

今天实现以下链式的队列,首先,要清楚对列是什么:
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(head)进行删除操作,而在表的后端(tail)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
这里写图片描述
所以总结一下队列就是后进前出的一种数据结构,在这里,我们首先来写出链队列的实现。

linked_queue.h

#define _CRT_SECURE_NO_WARNINGS 1

#ifndef __QUEUE_H__
#define __QUEUE_H__


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

typedef int datatype;

typedef struct queue
{
    datatype data;
    struct queue *next;
}Quenode,*PtrQueue;

typedef struct queue_list
{
    PtrQueue Head;
    PtrQueue Tail;
}LinkQueue, *pLinkQueue;

enum  
{
    EXIT,
    INIT,
    DESTORY,
    CLEAR,
    LENGTH,
    ENQUEUE,
    DEQUEUE,
    PRINTQUEUE
};

void InitQueue(pLinkQueue q);

void DestoryQueue(pLinkQueue q);

void ClearQueue(pLinkQueue q);

int QueueIsEmpty(pLinkQueue q);

int QueueLength(pLinkQueue q);

void GetHead(pLinkQueue q, datatype *p);

void EnQueue(pLinkQueue q ,datatype x);

void Dequeue(pLinkQueue q);

void PrintQueue(pLinkQueue q);

void menu();

#endif //!__QUEUE_H__


linked_queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"queue.h"


void menu()
{
    printf("$$$$$$$$$$$$$$    QUEUE    $$$$$$$$$$$$$$$$\n");
	printf("$$$$$$$$$$$$$$$$$$$$$¥$$$$$$$$$$$$$$$$$$$$\n");
	printf("$$$  1.init            2.destory        $$$\n");
    printf("$$$  3.clear           4.length         $$$\n");
    printf("$$$  5.enqueue         6.dequeue        $$$\n");
    printf("$$$  7.printqueue      0.EXIT           $$$\n");
    printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");

}
void InitQueue(pLinkQueue q)
{
    assert(q);
    q->Head = q->Tail = (PtrQueue)malloc(sizeof(Quenode));
    if (q->Head == NULL)
    {
        printf("out of memory");
        exit(EXIT_FAILURE);
    }
    q->Head->next = NULL;

}

void DestoryQueue(pLinkQueue q)
{
    assert(q);
    while (q->Head != NULL)
    {
        q->Tail = q->Head->next;
        free(q->Head);
        q->Head = q->Tail;
    }
}

void ClearQueue(pLinkQueue q)
{
    assert(q);
    PtrQueue p = q->Head->next;
    while (p != NULL)
    {
        PtrQueue tmp = p;
        p = p->next;
        free(tmp);
        tmp = NULL;
    }
    p = q->Head;
    q->Head = q->Tail = NULL;
    free(p);
}

int QueueIsEmpty(pLinkQueue q)
{
    assert(q);

    if (q->Head == q->Tail)
        return 1;
    else
        return 0;

}

int QueueLength(pLinkQueue q)
{
    assert(q);

    PtrQueue cur = q->Head->next;
    int count = 0;
    while (cur != NULL)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

void GetHead(pLinkQueue q, datatype *p)
{
    assert(q);

    if (QueueIsEmpty(q))
    {
        printf("队列为空队列!\n");
    }
    *p = q->Head->data;

}

void EnQueue(pLinkQueue q , datatype x)
{
    assert(q);
    PtrQueue cur = q->Head;
    PtrQueue newnode = (PtrQueue)malloc(sizeof(Quenode));
    if (newnode == NULL)
    {
        printf("out of memory");
        exit(EXIT_FAILURE);
    }
    newnode->data = x;
    newnode->next = NULL;
    while (cur->next != NULL)
    {
        cur = cur->next;
    }
    cur ->next= newnode;
    q->Tail = newnode;
}

void Dequeue(pLinkQueue q)
{
    assert(q);
    PtrQueue del = NULL,cur=NULL;
    if (q->Head == q->Tail)
    {
        printf("队列为空\n");
        return;
    }
    cur = q->Head->next;
    del = cur;
    q->Head ->next= cur->next;
    free(del);
    del = NULL;

}

void PrintQueue(pLinkQueue q)
{
    assert(q);
    PtrQueue cur = q->Head->next;
    if (q->Head == q->Tail)
        return;

    while (cur != NULL)
    {
        printf("%3d", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1


#include"queue.h"


void Test()
{
    LinkQueue que;
    int input =1 ;
    int length = 0;
    datatype x = 0;
    InitQueue(&que);
    while (input)
    {
        menu();
        printf("请选择:");
        scanf("%d", &input);
        switch (input)
        {
        case EXIT:
            DestoryQueue(&que);
            break;
        case INIT:
            InitQueue(&que);
            break;
        case DESTORY:
            DestoryQueue(&que);
            break;
        case CLEAR:
            ClearQueue(&que);
            break;
        case LENGTH:
            length=QueueLength(&que);
            printf("%d\n", length);
            break;
        case ENQUEUE:
            printf("请输入你所要入队元素的值:");
            scanf("%d", &x);
            fflush(stdin);
            EnQueue(&que,x);
            break;
        case DEQUEUE:
            Dequeue(&que);
            break;
        case PRINTQUEUE:
            PrintQueue(&que);
            break;
        default:
            input = 1 ;
            break;
        }

    }



}

int main()
{
    Test();
    system("pause");
    return 0;
}
网友评论
<