链式队列【数据结构-朱战立】

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 //#include <malloc.h>
  4 
  5 //定义抽象数据
  6 typedef int DataType;
  7 typedef struct queue{
  8     DataType data;
  9     struct  queue *next;
 10 }Queue;
 11 
 12 //定义链式队列的头尾指针
 13 typedef struct{
 14     Queue *front;
 15     Queue *rear;
 16 }ListQueue;
 17 
 18 //链式队列初始化
 19 void ListQueueInit(ListQueue *myQ)
 20 {
 21     myQ->front = NULL;
 22     myQ->rear = NULL;
 23 }
 24 
 25 //链式队列判断是否为空
 26 int ListQueueNoEmpty(ListQueue myQ)
 27 {
 28     if (myQ.front==NULL)
 29     {
 30         return 0;
 31     }
 32     else
 33     {
 34         return 1;
 35     }
 36 }
 37 
 38 //链式队列的入队操作
 39 int ListQueuePush(ListQueue *myQ, DataType x)
 40 {
 41     Queue *pTemp;
 42     if ((pTemp=(Queue*)malloc(sizeof(Queue)))==NULL)
 43     {
 44         return 0;
 45     }
 46     pTemp->data = x;
 47     pTemp->next = NULL;        //2018年8月16日 16:23:06  更正    最致命错误
 48 
 49 
 50     if (myQ->rear!=NULL)    //第一次入队的时候rear为null所以不执行。
 51     {
 52         myQ->rear->next = pTemp;
 53     }
 54     myQ->rear = pTemp;     //将队尾指针指向第一个入队的元素。
 55     if (myQ->front==NULL)
 56     {
 57         myQ->front = pTemp;//将队头指针指向第一个入队的元素，然后不再移动。
 58     }
 59     return 1;
 60 }
 61 
 62 //链式队列的出队操作
 63 int ListQueuePop(ListQueue *myQ, DataType *x)
 64 {
 65     ListQueue *del;
 66     /*if ((del = (ListQueue*)malloc(sizeof(ListQueue))) == NULL)
 67     {
 68         return 0;
 69     }*/
 70     if (myQ->front==NULL/*&&myQ->rear==NULL*/)
 71     {
 72         return 0;
 73     }
 74     else
 75     {
 76         *x = myQ->front->data;
 77         del = myQ->front;
 78         myQ->front = myQ->front->next;
 79         if (myQ->front == NULL)//如果只有一个节点
 80         {
 81             myQ->rear = NULL;
 82         }
 83         free(del);
 84         return 1;
 85     }
 86     
 87 }
 88 
 89 //链式队列取队头
 90 int ListQueueTop(ListQueue myQ,DataType *num)
 91 {
 92     if (myQ.front==NULL)
 93     {
 94         return 0;
 95     }
 96     else
 97     {
 98         *num = myQ.front->data;
 99         return 1;
100     }
101     
102 }
103 
104 
105 //销毁队列内存
106 void ListQueueDes(ListQueue myQ)
107 {
108     ListQueue *temp,*pre;
109     pre =myQ.front;
110     while (pre!=NULL)
111     {
112         temp = pre;
113         pre->front= pre->front->next;
114         free(temp);
115         temp = NULL;
116     }
117     myQ.front = NULL;
118     myQ.rear = NULL;
119 }
120 
121 //主函数
122 void main(void)
123 {
124     ListQueue Q;
125     int i;
126     DataType x,m;
127 
128     ListQueueInit(&Q);
129     for ( i = 0; i <10; i++)
130     {
131         if ((ListQueuePush(&Q, i + 1)) == 0)
132         {
133             printf("1error");
134             getchar();
135             return;
136         }
137     }
138     /*if ((ListQueueTop(&Q,&m))==0)
139     {
140         printf("2error");
141         getchar();
142         return;
143     }
144     else
145     {
146         printf("队头：%d
", m);
147     }*/
148     ListQueueTop(Q, &x);
149     printf("
取出队头为：%d
", x);
150     ListQueuePop(&Q, &x);
151     while ((ListQueueNoEmpty(Q)) == 1)
152     {
153         if ((ListQueueTop(Q,&x))==0)
154         {
155             printf("3error");
156             return;
157         }
158         else
159         {
160             printf("%d    ", x);
161             ListQueuePop(&Q, &x);
162         }
163     }
164     ListQueueDes(Q);
165     getchar();
166 }