チェーンテーブルを使用してキューを実現する-----「データ構造とアルゴリズム分析-C言語記述」

ubuntuのgcc検証を経て
一、ヘッダファイルque_link.h
 

#ifndef _QUE_LINK_H_

#define _QUE_LINK_H_





struct que_record;

typedef struct que_record* que;

struct link_node;

typedef struct link_node* node;

typedef int elementType;









int IsFull(que q);

int IsEmpty(que q);

que creatQue(int max_num);

void makeEmpty(que q);

void enque(elementType x,que q);

void deque(que q);

elementType front_que(que q);

elementType front_deque(que q);

void dispose_que(que q);





struct que_record

{

    node front;

    node rear;

    int size;

};





struct link_node

{

    elementType data;

    struct link_node* next;

};





#endif

 
二、cファイル:que_link.c
 

#include <stdio.h>

#include <stdlib.h>

#include "que_link.h"

#define MAXSIZE 10





int IsFull(que q)

{

    return q->size == MAXSIZE;

}





int IsEmpty(que q)

{

    return q->size == 0;

}





que creatQue(int max_num)

{

    que q;

    q = (que)malloc(sizeof(struct que_record));

    q->size = 0;

    q->front = q->rear = (node)malloc(sizeof(struct link_node));

    q->front->next = q->rear->next = NULL;

    return q;

}





void makeEmpty(que q)

{

    if(NULL == q)

    {

        printf("the que is not exsit 
");

        exit(-1);

    }





    while(q->size)

        deque(q);

}









void deque(que q)

{





    node ptr = NULL;





    ptr = q->front->next;

    free(q->front);

    q->front = ptr;

    q->size--;





    if(q->size == 0)

    {

        //q->front->next = q->rear->next = NULL;

        q->front = q->rear = NULL;

    }

}





void enque(elementType x, que q)

{

    if(q)

    {

        if(IsFull(q))

        {

            printf("the que is full 
");

            exit(-4);

        }





        printf("the enque x is %d
",x);

        static int init_flag = 0;

          if(!init_flag)

        {

            q->rear->data = x;

            q->rear->next = NULL;

            q->size++;

            init_flag = 1;

        }

        else

        {

            node ptr=(node )malloc(sizeof(struct link_node));

            ptr->data = x;

            q->rear->next = ptr;

            q->rear = q->rear->next;

            q->rear->next = NULL;

            q->size++;

        }

    }

}





elementType front_que(que q)

{

    if(q)

    {

        if(IsEmpty(q))

        {

            printf("the que is empty
");

            exit(-5);

        }





        return q->front->data;

    }

}



  elementType front_deque(que q)

{

    if(q)

    {

        if(IsEmpty(q))

        {

            printf("the que is empty,so can't deque
");

            exit(-6);

        }





        elementType x;

        x = q->front->data;

        deque(q);

        return x;

    }

}





void dispose_que(que q)

{

    if(q)

    {

        makeEmpty(q);

        free(q);

    }

}









int main(int argc,char *argv[])

{

    elementType val;

    int i = 0;

    que q;

     q = creatQue(10);

    while(i++ < 10 )

    {

        printf("now ,please input the value:
");

        scanf("%d",&val);

        printf("the val is %d
",val);

        enque(val,q);

        printf("the q size is %d
",q->size);

        if(val == 0)

           break;

    }





    while(q->size)

    {

        val = front_deque(q);

        printf("the val is %d
",val);

        sleep(1);

    }





    dispose_que(q);





    return 0;

}             

 
三、印刷出力
 

hangma@ubuntu:~/test/test/protest/que_test$ gcc  que_link.c -o que_link

hangma@ubuntu:~/test/test/protest/que_test$ ./que_link 

now ,please input the value:

1

the val is 1

the enque x is 1

the q size is 1

now ,please input the value:

2

the val is 2

the enque x is 2

the q size is 2

now ,please input the value:

3

the val is 3

the enque x is 3

the q size is 3

now ,please input the value:

4

the val is 4

the enque x is 4

the q size is 4

now ,please input the value:

5

the val is 5

the enque x is 5

the q size is 5

now ,please input the value:

6

the val is 6

the enque x is 6

the q size is 6

now ,please input the value:

7

the val is 7

the enque x is 7

the q size is 7

now ,please input the value:

8

the val is 8

the enque x is 8

the q size is 8

now ,please input the value:

9

the val is 9

the enque x is 9

the q size is 9

now ,please input the value:

10

the val is 10

the enque x is 10

the q size is 10

the val is 1

the val is 2

the val is 3

the val is 4

the val is 5

the val is 6

the val is 7

the val is 8

the val is 9

the val is 10