首页 > 代码库 > 优化后队列的实现(C语言实现)
优化后队列的实现(C语言实现)
上一篇中的队列的定义与实现(C语言实现) 中,无论是顺序队列还是链式队列,在尾加和删除头部的操作时,总有一个时间复杂度让人不满意。比如在顺序队列中,删除头部的操作后,总要将后面所有的结点都向前移动一位,这里消耗的较大的;又如在在链式队列中,尾加结点时,为了寻找到最后一位结点,要遍历整个队列,时间复杂度同样是O(n)。
为此,这里需要做出一些改变。其中严蔚敏老师的数据结构书中就是这么干的。
循序队列的优化方案:
定义front使其始终代表队头的下标
出队时将队头元素返回,且 且front++
定义rear使其始终代表队尾下一个元素的下标
入队时将新元素插入, 且rear++
头文件:
#ifndef _SEQQUEUE_H_ #define _SEQQUEUE_H_ typedef void SeqQueue; SeqQueue* SeqQueue_Create(int capacity); void SeqQueue_Destroy(SeqQueue* queue); void SeqQueue_Clear(SeqQueue* queue); int SeqQueue_Append(SeqQueue* queue, void* item); void* SeqQueue_Retrieve(SeqQueue* queue); void* SeqQueue_Header(SeqQueue* queue); int SeqQueue_Length(SeqQueue* queue); int SeqQueue_Capacity(SeqQueue* queue); #endif
源文件:
// 优化的顺序队列.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "SeqQueue.h" #include <stdlib.h> typedef unsigned int TSeqQueueNode; typedef struct _tag_SeqQueue { int capacity; int length; int front; int rear; TSeqQueueNode* node; } TSeqQueue; SeqQueue* SeqQueue_Create(int capacity) { TSeqQueue* ret = NULL; if (capacity > 0) { ret = (TSeqQueue*)malloc(sizeof(TSeqQueue) + sizeof(TSeqQueueNode) * capacity); } if (NULL != ret) { ret->capacity = capacity; ret->front = 0; //代表队头的下标 ret->length = 0; //长度 ret->node = (TSeqQueueNode*)(ret + 1); //指向的结点 ret->rear = 0; //队尾下一个结点的下标 } return ret; } void SeqQueue_Destroy(SeqQueue* queue) { free(queue); } void SeqQueue_Clear(SeqQueue* queue) { TSeqQueue* sQueue = (TSeqQueue*)queue; if (NULL != sQueue) { sQueue->front = 0; //代表队头的下标 sQueue->length = 0; //长度 sQueue->rear = 0; //队尾下一个结点的下标 } } //在尾部插入 int SeqQueue_Append(SeqQueue* queue, void* item) { TSeqQueue* sQueue = (TSeqQueue*)queue; int ret = 0; if ((NULL != sQueue) && (NULL != item) && (sQueue->length+1 <= sQueue->capacity)) { ret = 1; sQueue->node[sQueue->rear] = (TSeqQueueNode)item; sQueue->rear = (sQueue->rear + 1) % sQueue->capacity; sQueue->length++ ; } return ret; } //删除头部 void* SeqQueue_Retrieve(SeqQueue* queue) { TSeqQueue* sQueue = (TSeqQueue*)queue; void* ret = SeqQueue_Header(queue); if( ret != NULL ) { sQueue->front = (sQueue->front + 1) % sQueue->capacity; sQueue->length--; } return ret; } //获得头部 void* SeqQueue_Header(SeqQueue* queue) { TSeqQueue* sQueue = (TSeqQueue*)queue; void* ret = NULL; if ((NULL != sQueue) && (sQueue->length > 0)) { ret = (void*)(sQueue->node[sQueue->front]); } return ret; } int SeqQueue_Length(SeqQueue* queue) { TSeqQueue* sQueue = (TSeqQueue*)queue; int ret = -1; if( sQueue != NULL ) { ret = sQueue->length; } return ret; } int SeqQueue_Capacity(SeqQueue* queue) { TSeqQueue* sQueue = (TSeqQueue*)queue; int ret = -1; if( sQueue != NULL ) { ret = sQueue->capacity; } return ret; } int _tmain(int argc, _TCHAR* argv[]) { SeqQueue* queue = SeqQueue_Create(20); int a[10] = {0}; int i = 0; for(i=0; i<10; i++) { a[i] = i + 1; SeqQueue_Append(queue, a + i); } printf("Header: %d\n", *(int*)SeqQueue_Header(queue)); printf("Length: %d\n", SeqQueue_Length(queue)); printf("Capacity: %d\n", SeqQueue_Capacity(queue)); while( SeqQueue_Length(queue) > 0 ) { printf("Retrieve: %d\n", *(int*)SeqQueue_Retrieve(queue)); } SeqQueue_Destroy(queue); system("pause"); return 0; }
运行结果:
Header: 1 Length: 10 Capacity: 20 Retrieve: 1 Retrieve: 2 Retrieve: 3 Retrieve: 4 Retrieve: 5 Retrieve: 6 Retrieve: 7 Retrieve: 8 Retrieve: 9 Retrieve: 10 请按任意键继续. . .
=========================================================================
链式队列的优化:
定义front指针始终指向链表中的第一个结点
定义rear指针始终指向链表中的最后一个结点
入队时将新元素通过rear插入队尾, 且将rear指向新元素
头文件:
#ifndef _LINKQUEUE_H_ #define _LINKQUEUE_H_ typedef void LinkQueue; LinkQueue* LinkQueue_Create(); void LinkQueue_Destroy(LinkQueue* queue); void LinkQueue_Clear(LinkQueue* queue); int LinkQueue_Append(LinkQueue* queue, void* item); void* LinkQueue_Retrieve(LinkQueue* queue); void* LinkQueue_Header(LinkQueue* queue); int LinkQueue_Length(LinkQueue* queue); #endif
源文件:
// 优化的链式队列.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <malloc.h> #include <stdlib.h> #include "LinkQueue.h" typedef struct _tag_LinkQueueNode TLinkQueueNode; struct _tag_LinkQueueNode { TLinkQueueNode* next; void* item; }; typedef struct _tag_LinkQueue { TLinkQueueNode* front; TLinkQueueNode* rear; int length; } TLinkQueue; int _tmain(int argc, _TCHAR* argv[]) { LinkQueue* queue = LinkQueue_Create(); int a[10] = {0}; int i = 0; for(i=0; i<10; i++) { a[i] = i + 1; LinkQueue_Append(queue, a + i); } printf("Header: %d\n", *(int*)LinkQueue_Header(queue)); printf("Length: %d\n", LinkQueue_Length(queue)); while( LinkQueue_Length(queue) > 0 ) { printf("Retrieve: %d\n", *(int*)LinkQueue_Retrieve(queue)); } LinkQueue_Destroy(queue); system("pause"); return 0; } LinkQueue* LinkQueue_Create() { TLinkQueue* ret = (TLinkQueue*)malloc(sizeof(TLinkQueue)); if (NULL != ret) { ret->front = NULL; ret->length = 0; ret->rear = NULL; } return ret; } void LinkQueue_Destroy(LinkQueue* queue) // O(n) { LinkQueue_Clear(queue); free(queue); } void LinkQueue_Clear(LinkQueue* queue) // O(n) { while( LinkQueue_Length(queue) > 0 ) { LinkQueue_Retrieve(queue); } } int LinkQueue_Append(LinkQueue* queue, void* item) { TLinkQueue * sQueue= (TLinkQueue*)queue; TLinkQueueNode * node = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode)); int ret = 0; if ((NULL != queue) && (NULL != item) && (NULL != node)) { ret = 1; node->item = item; if (sQueue->length > 0) { sQueue->rear->next = node; sQueue->rear = node; node->next = NULL; } else { sQueue->front = node; sQueue->rear = node; node->next = NULL; } sQueue->length++; } if( !ret ) { free(node); } return ret; } void* LinkQueue_Retrieve(LinkQueue* queue) { TLinkQueue* sQueue = (TLinkQueue*)queue; TLinkQueueNode* node = NULL; void* ret = NULL; if( (sQueue != NULL) && (sQueue->length > 0) ) { node = sQueue->front; sQueue->front = node->next; ret = node->item; free(node); sQueue->length--; if( sQueue->length == 0 ) { sQueue->front = NULL; sQueue->rear = NULL; } } return ret; } void* LinkQueue_Header(LinkQueue* queue) // O(1) { TLinkQueue* sQueue = (TLinkQueue*)queue; void* ret = NULL; if( (sQueue != NULL) && (sQueue->length > 0) ) { ret = sQueue->front->item; } return ret; } int LinkQueue_Length(LinkQueue* queue) // O(1) { TLinkQueue* sQueue = (TLinkQueue*)queue; int ret = -1; if( sQueue != NULL ) { ret = sQueue->length; } return ret; }
运行结果:
Header: 1 Length: 10 Retrieve: 1 Retrieve: 2 Retrieve: 3 Retrieve: 4 Retrieve: 5 Retrieve: 6 Retrieve: 7 Retrieve: 8 Retrieve: 9 Retrieve: 10 请按任意键继续. . .
如有错误,望不吝指出。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。