一个C语言链式结构实现的队列 mQueue (GCC编译)。
1 /** 2 * @brief C语言实现的链式队列 3 * @author wid 4 * @date 2013-10-31 5 * 6 * @note 若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢! 7 */ 8 9 #include10 #include 11 12 #define TRUE 1 13 #define FALSE 0 14 15 typedef struct Point2D 16 { 17 int x; 18 int y; 19 }ElemType; //元素结构 20 21 typedef struct QNODE 22 { 23 ElemType *pe; 24 struct QNODE *next; 25 }QueueNode; //队列节点结构 26 27 typedef struct MQUEUE 28 { 29 QueueNode *rear; //队列尾节点 30 QueueNode *front; //队列头节点 31 int len; //队列长度 32 }mQueue; 33 34 //队列方法声明 35 mQueue *CreateQueue(); ///创建一个空队列 36 void DestroyQueue( mQueue *pQueue ); ///销毁队列 pQueue 37 void ClearQueue( mQueue *pQueue ); ///置空队列 pQueue 38 int IsEmpty( mQueue *pQueue ); ///是否为空空队列 39 int GetLength( mQueue *pQueue ); ///获取队列长度 40 int EnQueue( mQueue *pQueue, ElemType *pe ); ///将元素pe插入到队尾 41 int DeQueue( mQueue *pQueue, ElemType **pe ); ///将将队头元素出队 42 int GetHead( mQueue *pQueue, ElemType **pe ); ///获取队头元素(不出队) 43 void ForEachQueue( mQueue *pQueue, void (*func)(ElemType *pe) ); ///从队头到队尾依次执行func函数 44 45 46 //队列方法实现 47 /** 48 * @brief 创建一个空队列 49 * 50 * @return 返回指向新创建的队列的指针 51 */ 52 mQueue *CreateQueue() 53 { 54 ///创建队列 55 mQueue *pQueue = (mQueue *)malloc( sizeof(mQueue) ); 56 57 ///令队头指向队尾 58 pQueue->front = pQueue->rear = (QueueNode *)malloc( sizeof(QueueNode) ); 59 60 ///队尾的next节点指向NULL 61 pQueue->rear->next = NULL; 62 63 ///队头的next节点指向队尾 64 pQueue->front->next = pQueue->rear; 65 66 ///初始化队长为 0 67 pQueue->len = 0; 68 69 return pQueue; 70 } 71 72 /** 73 * @brief 销毁队列 pQueue 74 * 75 * @param pQueue 指向待销毁的队列 76 */ 77 void DestroyQueue( mQueue *pQueue ) 78 { 79 QueueNode *tmp = NULL; 80 81 ///释放队列内元素 82 while( pQueue->front != NULL ) 83 { 84 tmp = pQueue->front->next; 85 free( pQueue->front ); 86 pQueue->front = tmp; 87 } 88 89 ///释放队列 90 free( pQueue ); 91 } 92 93 /** 94 * @brief 将队列中的元素全部清除 95 * 96 * @param pQueue 指向待置空的队列 97 */ 98 void ClearQueue( mQueue *pQueue ) 99 {100 QueueNode *tmp = NULL;101 102 ///释放队列内元素(保留一队尾节点)103 while( pQueue->front->next != NULL )104 {105 tmp = pQueue->front->next;106 free( pQueue->front );107 pQueue->front = tmp;108 }109 110 pQueue->len = 0;111 }112 113 /**114 * @brief 是否为空队列115 *116 * @param pQueue 指向待检测的队列117 *118 * @return 若为空则返回 TRUE, 否则返回 FALSE119 */120 int IsEmpty( mQueue *pQueue )121 {122 return pQueue->len == 0 ? TRUE : FALSE;123 }124 125 /**126 * @brief 获取队列长度127 *128 * @param pQueue 指向待获取长度的队列129 *130 * @return 返回队列当前长度131 */132 int GetLength( mQueue *pQueue )133 {134 return pQueue->len;135 }136 137 /**138 * @brief 将元素pe插入到队尾139 *140 * @param pQueue 指向待入队的队列141 * @param pe 指向待插入的元素142 *143 * @return 插入成功则返回入队后队列的长度, 否则返回 -1144 */145 int EnQueue( mQueue *pQueue, ElemType *pe )146 {147 ///请求一个新节点148 QueueNode *pNode = (QueueNode *)malloc( sizeof(QueueNode) );149 150 ///新节点的数据元素指向传入的元素151 pNode->pe = pe;152 153 ///新节点的next节点指向 NULL154 pNode->next = NULL;155 156 ///队尾的next节点指向新节点157 pQueue->rear->next = pNode;158 159 ///令队尾指向新节点160 pQueue->rear = pNode;161 162 return ++pQueue->len;163 }164 165 /**166 * @brief 将队头元素出队167 *168 * @param pQueue 指向待出队的队列169 * @param pe 指向接收元素的指针的指针170 *171 * @return 成功出队后返回出队后队列的长度, 否则返回 -1172 */173 int DeQueue( mQueue *pQueue, ElemType **pe )174 {175 176 ///队列是否为空177 if( pQueue->front == pQueue->rear )178 return -1;179 180 ///得到队头元素181 *pe = pQueue->front->next->pe;182 183 ///令队头指向上一节点184 QueueNode *tmp = pQueue->front;185 pQueue->front = pQueue->front->next;186 free( tmp );187 188 return --pQueue->len;189 }190 191 /**192 * @brief 获取队头元素, 不出栈193 *194 * @param 指向待获取队头元素的队列195 * @param 指向接收出栈元素的指针的指针196 *197 * @return 获取成功则返回元素在队列中的位置, 否则返回 -1, 且 *pe 指向 NULL198 *199 * @note 元素位置由 0 计起200 */201 int GetHead( mQueue *pQueue, ElemType **pe )202 {203 ///队列是否为空204 if( pQueue->front == pQueue->rear )205 {206 *pe = NULL;207 return -1;208 }209 210 ///得到队头元素211 *pe = pQueue->front->next->pe;212 213 return pQueue->len - 1;214 }215 216 /**217 * @brief 从队头到队尾对每个元素依次执行 func 函数218 *219 * @param pQueue 指向待处理的队列220 * @param func 回调函数221 */222 void ForEachQueue( mQueue *pQueue, void (*func)(ElemType *pe) )223 {224 QueueNode *tmp = pQueue->front;225 226 ///遍历执行 func227 while( tmp != pQueue->rear && (tmp = tmp->next) )228 {229 func( tmp->pe );230 }231 }232 233 //测试234 235 /**236 * @brief 输出元素 pe237 */238 void display( ElemType *pe )239 {240 printf( "(%d,%d )", pe->x, pe->y );241 }242 243 int main()244 {245 ///准备数据元素246 ElemType pt1 = { 10, 10 };247 ElemType pt2 = { 20, 20 };248 ElemType pt3 = { 30, 30 };249 ElemType pt4 = { 40, 40 };250 ElemType pt5 = { 50, 50 };251 252 ///测试 CreateQueue253 mQueue *pque = CreateQueue();254 255 ///测试 IsEmpty、GetLength256 if( IsEmpty(pque) == TRUE )257 printf( "队列当前长度:%d, 是否为空队列:%d\n", GetLength(pque), IsEmpty(pque) );258 259 ///测试 EnQueue260 EnQueue( pque, &pt1 );261 if( IsEmpty(pque) != TRUE )262 printf( "入队1元素后队列当前长度:%d, 是否为空队列:%d\n", GetLength(pque), IsEmpty(pque) );263 264 ///测试 ClearQueue265 ClearQueue( pque );266 printf( "清空队列, 当前长度:%d\n", GetLength(pque) );267 268 ///入队5元素269 printf( "\n连续入队5元素..\n" );270 EnQueue( pque, &pt1 );271 EnQueue( pque, &pt2 );272 EnQueue( pque, &pt3 );273 EnQueue( pque, &pt4 );274 EnQueue( pque, &pt5 );275 276 ///测试 ForEachQueue277 printf( "测试 ForEachQueue:" );278 ForEachQueue( pque, display );279 280 ///测试 DeQueue281 ElemType *p = NULL;282 if( DeQueue(pque, &p) != -1 )283 printf( "\n\n测试DeQueue, 出队元素为:(%d,%d), 出队后队列长度:%d\n", p->x, p->y, GetLength(pque) );284 285 ///测试 GetHead286 if( GetHead(pque, &p) != -1 )287 printf( "\n测试GetHead, Head元素为(%d,%d)\n", p->x, p->y );288 289 ///全部出队290 printf( "\n执行全部出队...\n" );291 while( DeQueue(pque, &p) != -1 )292 {293 printf( "当前出队:(%d,%d), 队列剩余长度:%d, 是否为空队列%d\n", p->x, p->y, GetLength(pque), IsEmpty(pque) );294 }295 296 ///销毁队列297 printf( "\n销毁队列...\n" );298 DestroyQueue( pque );299 300 return 0;301 }
运行测试:
若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢。