- 算法1： 鏈隊(duì)列(存儲結(jié)構(gòu)由c3-2.h定義)的基本操作(9個)
void InitQueue(LinkQueue &Q) { // 構(gòu)造一個空隊(duì)列Q。 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); // 生成頭結(jié)點(diǎn) if(!Q.front) // 生成頭結(jié)點(diǎn)失敗 exit(OVERFLOW); Q.front->next=NULL; // 頭結(jié)點(diǎn)的next域?yàn)榭?} void DestroyQueue(LinkQueue &Q) { // 銷毀隊(duì)列Q(無論空否均可)。 while(Q.front) // Q.front不為空 { Q.rear=Q.front->next; // Q.rear指向Q.front的下一個結(jié)點(diǎn) free(Q.front); // 釋放Q.front所指結(jié)點(diǎn) Q.front=Q.rear; // Q.front指向Q.front的下一個結(jié)點(diǎn) } } void ClearQueue(LinkQueue &Q) { // 將隊(duì)列Q清為空隊(duì)列 DestroyQueue(Q); // 銷毀隊(duì)列Q InitQueue(Q); // 重新構(gòu)造空隊(duì)列Q } Status QueueEmpty(LinkQueue Q) { // 若隊(duì)列Q為空隊(duì)列，則返回TRUE；否則返回FALSE if(Q.front->next==NULL) return TRUE; else return FALSE; } int QueueLength(LinkQueue Q) { // 求隊(duì)列Q的長度 int i=0; // 計(jì)數(shù)器，初值為0 QueuePtr p=Q.front; // p指向頭結(jié)點(diǎn) while(Q.rear!=p) // p所指不是尾結(jié)點(diǎn) { i++; // 計(jì)數(shù)器+1 p=p->next; // p指向下一個結(jié)點(diǎn) } return i; } Status GetHead(LinkQueue Q,QElemType &e) { // 若隊(duì)列Q不空，則用e返回Q的隊(duì)頭元素，并返回OK；否則返回ERROR QueuePtr p; if(Q.front==Q.rear) // 隊(duì)列空 return ERROR; p=Q.front->next; // p指向隊(duì)頭結(jié)點(diǎn) e=p->data; // 將隊(duì)頭元素的值賦給e return OK; } void EnQueue(LinkQueue &Q,QElemType e) { // 插入元素e為隊(duì)列Q的新的隊(duì)尾元素。在教科書第62頁 QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); // 動態(tài)生成新結(jié)點(diǎn) if(!p) exit(OVERFLOW); // 失敗則退出 p->data=e; // 將值e賦給新結(jié)點(diǎn) p->next=NULL; // 新結(jié)點(diǎn)的指針域?yàn)榭? Q.rear->next=p; // 原隊(duì)尾結(jié)點(diǎn)的指針指向新結(jié)點(diǎn) Q.rear=p; // 尾指針指向新結(jié)點(diǎn) } Status DeQueue(LinkQueue &Q,QElemType &e) { // 若隊(duì)列Q不空，刪除Q的隊(duì)頭元素，用e返回其值， // 并返回OK；否則返回ERROR。 QueuePtr p; if(Q.front==Q.rear) // 隊(duì)列空 return ERROR; p=Q.front->next; // p指向隊(duì)頭結(jié)點(diǎn) e=p->data; // 將隊(duì)頭元素的值賦給e Q.front->next=p->next; // 頭結(jié)點(diǎn)指向下一個結(jié)點(diǎn) if(Q.rear==p) // 刪除的是隊(duì)尾結(jié)點(diǎn) Q.rear=Q.front; // 修改隊(duì)尾指針指向頭結(jié)點(diǎn)(空隊(duì)列) free(p); // 釋放隊(duì)頭結(jié)點(diǎn) return OK; } void QueueTraverse(LinkQueue Q,void(*visit)(QElemType)) { // 從隊(duì)頭到隊(duì)尾依次對隊(duì)列Q中每個元素調(diào)用函數(shù)visit() QueuePtr p=Q.front->next; // p指向隊(duì)頭結(jié)點(diǎn) while(p) // p指向結(jié)點(diǎn) { visit(p->data); // 對p所指元素調(diào)用visit() p=p->next; // p指向下一個結(jié)點(diǎn) } - 算法2： 用單鏈表的基本操作實(shí)現(xiàn)鏈隊(duì)列(存儲結(jié)構(gòu)由c3-2.h定義)的基本操作(9個) typedef QElemType ElemType; // 定義單鏈表的元素類型為隊(duì)列的元素類型 #define LinkList QueuePtr // 定義單鏈表的類型為相應(yīng)的鏈隊(duì)列的類型 #define LNode QNode #include"bo2-2.cpp" // 單鏈表的基本操作 void InitQueue(LinkQueue &Q) { // 構(gòu)造一個空隊(duì)列Q InitList(Q.front); // 以Q.front為頭指針，構(gòu)造空鏈表(調(diào)用單鏈表的基本操作) Q.rear=Q.front; // Q.rear與Q.front共同指向鏈隊(duì)列的頭結(jié)點(diǎn) } void DestroyQueue(LinkQueue &Q) { // 銷毀隊(duì)列Q(無論空否均可) DestroyList(Q.front); // 銷毀Q.front為頭指針的鏈表，且置Q.front為空 Q.rear=Q.front; // 置Q.rear也為空 } void ClearQueue(LinkQueue &Q) { // 將隊(duì)列Q清為空隊(duì)列 ClearList(Q.front); // 清空以Q.front為頭指針的鏈表，頭結(jié)點(diǎn)的指針域?yàn)榭? Q.rear=Q.front; // Q.rear也指向空隊(duì)列的頭結(jié)點(diǎn) } Status QueueEmpty(LinkQueue Q) { // 若隊(duì)列Q為空隊(duì)列，則返回TRUE；否則返回FALSE return ListEmpty(Q.front); // 以Q.front為頭指針的單鏈表為空，則隊(duì)列Q為空，反之亦然 } int QueueLength(LinkQueue Q) { // 求隊(duì)列Q的長度 return ListLength(Q.front); // 隊(duì)列Q的長度即為以Q.front為頭指針的單鏈表的長度 } Status GetHead(LinkQueue Q,QElemType &e) { // 若隊(duì)列Q不空，則用e返回Q的隊(duì)頭元素，并返回OK；否則返回ERROR return GetElem(Q.front,1,e); // 隊(duì)頭元素即為以Q.front為頭指針的單鏈表的第1個元素 } void EnQueue(LinkQueue &Q,QElemType e) { // 插入元素e為隊(duì)列Q的新的隊(duì)尾元素 ListInsert(Q.front,ListLength(Q.front)+1,e); // 在最后一個元素之后插入e } Status DeQueue(LinkQueue &Q,QElemType &e) { // 若隊(duì)列Q不空，刪除Q的隊(duì)頭元素，用e返回其值，并返回OK；否則返回ERROR if(Q.front->next==Q.rear) // 隊(duì)列僅有1個元素(刪除的也是隊(duì)尾元素) Q.rear=Q.front; // 令隊(duì)尾指針指向頭結(jié)點(diǎn) return ListDelete(Q.front,1,e); // 刪除以Q.front為頭指針的單鏈表的第1個元素 } void QueueTraverse(LinkQueue Q,void(*visit)(QElemType)) { // 從隊(duì)頭到隊(duì)尾依次對隊(duì)列Q中每個元素調(diào)用函數(shù)visit() ListTraverse(Q.front,visit); // 依次對以Q.front為頭指針的單鏈表的元素調(diào)用visit() }- 算法3： 循環(huán)隊(duì)列(存儲結(jié)構(gòu)由c3-3.h定義)的基本操作(9個)
void InitQueue(SQQueue &Q) { // 構(gòu)造一個空隊(duì)列Q。在教科書第64頁 Q.base=(QElemType*)malloc(MAX_QSIZE*sizeof(QElemType)); if(!Q.base) // 存儲分配失敗 exit(OVERFLOW); Q.front=Q.rear=0; } void DestroyQueue(SqQueue &Q) { // 銷毀隊(duì)列Q，Q不再存在 if(Q.base) // 隊(duì)列Q存在 free(Q.base); // 釋放Q.base所指的存儲空間 Q.base=NULL; // Q.base不指向任何存儲單元 Q.front=Q.rear=0; } void ClearQueue(SqQueue &Q) { // 將隊(duì)列Q清為空隊(duì)列 Q.front=Q.rear=0; } Status QueueEmpty(SqQueue Q) { // 若隊(duì)列Q為空隊(duì)列，則返回TRUE；否則返回FALSE if(Q.front==Q.rear) // 隊(duì)列空的標(biāo)志 return TRUE; else return FALSE; } Status GetHead(SqQueue Q,QElemType &e) { // 若隊(duì)列Q不空，則用e返回Q的隊(duì)頭元素，并返回OK；否則返回ERROR if(Q.front==Q.rear) // 隊(duì)列空 return ERROR; e=Q.base[Q.front]; // 將隊(duì)頭元素的值賦給e return OK; } Status EnQueue(SqQueue &Q,QElemType e) { // 插入元素e為隊(duì)列Q的新的隊(duì)尾元素。在教科書第65頁 if((Q.rear+1)%MAX_QSIZE==Q.front) // 隊(duì)列滿 return ERROR; Q.base[Q.rear]=e; // 將e插在隊(duì)尾 Q.rear=(Q.rear+1)%MAX_QSIZE; // 隊(duì)尾指針+1后對MAX_QSIZE取余 return OK; } int QueueLength(SqQueue Q) { // 返回隊(duì)列Q的元素個數(shù)，即隊(duì)列的長度。在教科書第64頁 return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE; } Status DeQueue(SqQueue &Q,QElemType &e) // 在教科書第65頁 { // 若隊(duì)列Q不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK；否則返回ERROR if(Q.front==Q.rear) // 隊(duì)列空 return ERROR; e=Q.base[Q.front]; // 將隊(duì)頭元素的值賦給e Q.front=(Q.front+1)%MAX_QSIZE; // 移動隊(duì)頭指針 return OK; } void QueueTraverse(SqQueue Q,void(*visit)(QElemType)) { // 從隊(duì)頭到隊(duì)尾依次對隊(duì)列Q中每個元素調(diào)用函數(shù)visit() int i=Q.front; // i最初指向隊(duì)頭元素 while(i!=Q.rear) // i指向隊(duì)列Q中的元素 { visit(Q.base[i]); // 對i所指元素調(diào)用函數(shù)visit() i=(i+1)%MAX_QSIZE; // i指向下一個元素 } printf("/n"); }新聞熱點(diǎn)
疑難解答
