C語(yǔ)言單鏈隊(duì)列的表示與實(shí)現(xiàn)實(shí)例詳解
1.概述:
C語(yǔ)言的隊(duì)列(queue),是指先進(jìn)先出(FIFO, First-In-First-Out)的線(xiàn)性表。在具體應(yīng)用中通常用鏈表或者數(shù)組來(lái)實(shí)現(xiàn)。隊(duì)列只允許在后端(稱(chēng)為rear)進(jìn)行插入操作,在前端(稱(chēng)為front)進(jìn)行刪除操作。
而單鏈隊(duì)列使用鏈表作為基本數(shù)據(jù)結(jié)果,因此不存在偽溢出的問(wèn)題,隊(duì)列長(zhǎng)度也沒(méi)有限制。但插入和讀取的時(shí)間代價(jià)會(huì)比較高
2.實(shí)例代碼:
/* 單鏈隊(duì)列——隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) */ typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front,rear; /* 隊(duì)頭、隊(duì)尾指針 */ }LinkQueue; /* 鏈隊(duì)列的基本操作(9個(gè)) */ void InitQueue(LinkQueue *Q) { /* 構(gòu)造一個(gè)空隊(duì)列Q */ Q->front=Q->rear=malloc(sizeof(QNode)); if(!Q->front) exit(OVERFLOW); Q->front->next=NULL; } void DestroyQueue(LinkQueue *Q) { /* 銷(xiāo)毀隊(duì)列Q(無(wú)論空否均可) */ while(Q->front) { Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } } void ClearQueue(LinkQueue *Q) { /* 將Q清為空隊(duì)列 */ QueuePtr p,q; Q->rear=Q->front; p=Q->front->next; Q->front->next=NULL; while(p) { q=p; p=p->next; free(q); } } Status QueueEmpty(LinkQueue Q) { /* 若Q為空隊(duì)列,則返回TRUE,否則返回FALSE */ if(Q.front->next==NULL) return TRUE; else return FALSE; } int QueueLength(LinkQueue Q) { /* 求隊(duì)列的長(zhǎng)度 */ int i=0; QueuePtr p; p=Q.front; while(Q.rear!=p) { i++; p=p->next; } return i; } Status GetHead_Q(LinkQueue Q,QElemType *e) { /* 若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR */ QueuePtr p; if(Q.front==Q.rear) return ERROR; p=Q.front->next; *e=p->data; return OK; } void EnQueue(LinkQueue *Q,QElemType e) { /* 插入元素e為Q的新的隊(duì)尾元素 */ QueuePtr p= (QueuePtr)malloc(sizeof(QNode)); if(!p) /* 存儲(chǔ)分配失敗 */ exit(OVERFLOW); p->data=e; p->next=NULL; Q->rear->next=p; Q->rear=p; } Status DeQueue(LinkQueue *Q,QElemType *e) { /* 若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR */ QueuePtr p; if(Q->front==Q->rear) return ERROR; p=Q->front; /* 指向頭結(jié)點(diǎn) */ *e=p->data; Q->front=p->next; /* 摘下頭節(jié)點(diǎn) */ if(Q->rear==p) Q->rear=Q->front; free(p); return OK; } void QueueTraverse(LinkQueue Q,void(*vi)(QElemType)) { /* 從隊(duì)頭到隊(duì)尾依次對(duì)隊(duì)列Q中每個(gè)元素調(diào)用函數(shù)vi() */ QueuePtr p; p=Q.front->next; while(p) { vi(p->data); p=p->next; } printf("\n"); }
相關(guān)文章
C++智能指針shared_ptr與weak_ptr的實(shí)現(xiàn)分析
shared_ptr是一個(gè)標(biāo)準(zhǔn)的共享所有權(quán)的智能指針,允許多個(gè)指針指向同一個(gè)對(duì)象,定義在 memory 文件中,命名空間為 std,這篇文章主要介紹了C++ 中 shared_ptr weak_ptr,需要的朋友可以參考下2022-09-09基于C語(yǔ)言的庫(kù)封裝發(fā)布技術(shù)詳解
在編程的過(guò)程中,使用已經(jīng)封裝好的庫(kù)函數(shù)是十分方便的,也是十分高效的,這篇文章主要給大家介紹了關(guān)于C語(yǔ)言庫(kù)的封裝和使用的相關(guān)資料,需要的朋友可以參考下2021-08-08常用排序算法的C語(yǔ)言版實(shí)現(xiàn)示例整理
這篇文章主要介紹了常用排序算法的C語(yǔ)言版實(shí)現(xiàn)示例整理,包括快速排序及冒泡排序等,基本上都給出了時(shí)間復(fù)雜度,需要的朋友可以參考下2016-03-03C++Node類(lèi)Cartographer開(kāi)始軌跡的處理深度詳解
這篇文章主要介紹了C++Node類(lèi)Cartographer開(kāi)始軌跡的處理,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2023-03-03詳解C++?STL模擬實(shí)現(xiàn)vector
這篇文章主要為大家詳細(xì)介紹了C++如何模擬實(shí)現(xiàn)STL容器vector,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)C++有一定幫助,需要的可以參考一下2023-01-01