3.6链队列
#include<stdio.h> #include<malloc.h> //链队列的节点 typedef struct LinkNode{ int data; struct LinkNode*next; }*LinkNodePtr; //链队列 typedef struct LinkQueue{ LinkNodePtr front; LinkNodePtr rear; }*LinkQueuePtr; //construct an empty quene LinkQueuePtr initQueue(){ LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(struct LinkQueue)); //the header,the data is not useful LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(struct LinkNode)); headerPtr->next = NULL; resultPtr->front = headerPtr; resultPtr->rear= headerPtr; return resultPtr; } //initQuene //output the quene void outputLinkQueue(LinkQueuePtr paraQueuePtr){ LinkNodePtr tempPtr =paraQueuePtr->front->next; while(tempPtr!=NULL){ printf("%d ",tempPtr->data); tempPtr=tempPtr->next; } //while printf("\r\n"); } //outputLinkQuene //enquene void enqueue(LinkQueuePtr paraQueuePtr,int paraElement){ //step1 create a new node LinkNodePtr tempNodePtr=(LinkNodePtr)malloc(sizeof(struct LinkNode)); tempNodePtr->data =paraElement; tempNodePtr->next =NULL; //step2 link to the existing rear paraQueuePtr->rear->next =tempNodePtr; //it is the new rear paraQueuePtr->rear =tempNodePtr; } //enquene /*dequeue return the value of the header*/ int dequeue(LinkQueuePtr paraQueuePtr){ int resultValue; LinkNodePtr tempNodePtr; //step1 is the quene empty if(paraQueuePtr->front ==paraQueuePtr->rear){ printf("The queue is empty.\r\n"); return -1; } //if //step2 change the queue tempNodePtr =paraQueuePtr->front->next; resultValue =tempNodePtr->data; paraQueuePtr->front->next =paraQueuePtr->front->next->next; if(paraQueuePtr->rear == tempNodePtr){ paraQueuePtr->rear = paraQueuePtr->front; } //if //step3 free space //free(tempNodePtr) tempNodePtr =NULL; //step4 return return resultValue; } //enquene //unit test void testLinkQueue(){ LinkQueuePtr tempQueuePtr; tempQueuePtr = initQueue(); enqueue(tempQueuePtr,10); enqueue(tempQueuePtr,30); enqueue(tempQueuePtr,50); outputLinkQueue(tempQueuePtr); printf("dequeue gets %d\r\n",dequeue(tempQueuePtr)); printf("dequeue gets %d\r\n",dequeue(tempQueuePtr)); printf("dequeue gets %d\r\n",dequeue(tempQueuePtr)); printf("dequeue gets %d\r\n",dequeue(tempQueuePtr)); enqueue(tempQueuePtr,8); outputLinkQueue(tempQueuePtr); } //testLinkQuene //the entrance int main(){ testLinkQueue(); return 1; } //main运行结果
10 30 50 dequeue gets 10 dequeue gets 30 dequeue gets 50 The queue is empty. dequeue gets -1 8体会
比链表更快，但是没有链表灵活，方便。