|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
//自己写的链式结构队列 // 要实现的操作有： 初始化initqueue ， 销毁destroyqueue ， 判断为空emptyqueue // 进队列enqueue ， 出队列dequeue 打印队列prntqueue #include<bits/stdc++.h> using namespace std; typedef struct qnode{ int data; struct qnode *next; }datanode; typedef struct{ datanode *front; datanode *rear; }squeue; void initqueue(squeue*&q){ q=(squeue*)malloc(sizeof(squeue)); q->front=q->rear=NULL; } void destroyqueue(squeue*&q){ datanode*pre=q->front,*p; if(pre!=NULL) { p=pre->next; while(p!=NULL){ free(pre); pre=p;p=p->next; } free(pre); } free(q); } bool emptyqueue(squeue*&q){ return (q->rear==NULL); } void enqueue(squeue*&q,int e){ //这里有两种情况，1队列为空，2队列不空 datanode *p; p=(datanode*)malloc(sizeof(datanode)); p->data=e; p->next=NULL; if(q->rear==NULL) q->rear=q->front=p; else{ q->rear->next=p; q->rear=p; } } bool dequeue(squeue*&q,int &e){ //这里有三种情况，1队列为空，2队列中只有一个结点，3队列中有两个及其以上结点 datanode*p; if(q->rear==NULL) return false; p=q->front; if(q->rear==q->front) q->rear=q->front=NULL; else q->front=q->front->next; e=p->data; free(p); return true; } void printqueue(squeue*q){ datanode *p=q->front; while(p){ cout<<p->data<<" "; p=p->next; } cout<<endl; } int main(){ int e; squeue * q; initqueue(q); for(int i=1;i<10;i++) enqueue(q,i); printqueue(q); dequeue(q,e); dequeue(q,e); printqueue(q); } |
教材标准队列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
//链队运算算法 #include <stdio.h> #include <malloc.h> typedef char ElemType; typedef struct DataNode { ElemType data; struct DataNode *next; } DataNode; //链队数据结点类型 typedef struct { DataNode *front; DataNode *rear; } LinkQuNode; //链队类型 void InitQueue(LinkQuNode *&q) { q=(LinkQuNode *)malloc(sizeof(LinkQuNode)); q->front=q->rear=NULL; } void DestroyQueue(LinkQuNode *&q) { DataNode *p=q->front,*r;//p指向队头数据结点 if (p!=NULL) //释放数据结点占用空间 { r=p->next; while (r!=NULL) { free(p); p=r;r=p->next; } } free(p); free(q); //释放链队结点占用空间 } bool QueueEmpty(LinkQuNode *q) { return(q->rear==NULL); } void enQueue(LinkQuNode *&q,ElemType e) { DataNode *p; p=(DataNode *)malloc(sizeof(DataNode)); p->data=e; p->next=NULL; if (q->rear==NULL) //若链队为空,则新结点是队首结点又是队尾结点 q->front=q->rear=p; else { q->rear->next=p; //将p结点链到队尾,并将rear指向它 q->rear=p; } } bool deQueue(LinkQuNode *&q,ElemType &e) { DataNode *t; if (q->rear==NULL) //队列为空 return false; t=q->front; //t指向第一个数据结点 if (q->front==q->rear) //队列中只有一个结点时 q->front=q->rear=NULL; else //队列中有多个结点时 q->front=q->front->next; e=t->data; free(t); return true; } |
双端队列
为了节约时间，我就没写了
教材标准双端队列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
//双端队列算法 #include "sqqueue.cpp" bool deQueue1(SqQueue *&q,ElemType &e) //从队尾删除 { if (q->front==q->rear) //队空 return false; e=q->data[q->rear]; //提取队尾元素 q->rear=(q->rear-1+MaxSize)%MaxSize; //修改除尾指针 return true; } bool enQueue1(SqQueue *&q,ElemType e) //从队头插入 { if ((q->rear+1)%MaxSize==q->front) //队满 return false; q->data[q->front]=e; //e元素进队 q->front=(q->front-1+MaxSize)%MaxSize; //修改队头指针 return true; } int main() { ElemType e; int i; SqQueue *q; InitQueue(q); printf("从队尾插入a,b,从队头插入c,d,从队尾插入e\n"); enQueue(q,'a'); //从队尾插入'a' enQueue(q,'b'); //从队尾插入'b' enQueue1(q,'c'); //从队头插入'c' enQueue1(q,'d'); //从队头插入'd' enQueue(q,'e'); //从队尾插入'e' printf("从队头出队两个元素:"); for (i=1;i<=2;i++) { deQueue(q,e); //从队头删除 printf("%c ",e); } printf("\n从队尾出队其他元素:"); while (!QueueEmpty(q)) { deQueue1(q,e); //从队尾删除 printf("%c ",e); } printf("\n"); return 1; } |
报数问题
设有n个人站成一排，从左向右的编号分别为1-n，现在从左边往右报数“1，2，1，2，。。。“，数到”1“的人出列，数到”2”的人立即站到队伍的最右端。报数过程反复进行，直到n个人都出列为止。要求给出他们的出列顺序。
例如，当n=8时初始序列为：
1 2 3 4 5 6 7 8
则出列顺序为：
1 3 5 7 2 6 4 8
我就用自己写的队列来做把
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
//自己写的链式结构队列 // 要实现的操作有： 初始化initqueue ， 销毁destroyqueue ， 判断为空emptyqueue // 进队列enqueue ， 出队列dequeue 打印队列prntqueue #include<bits/stdc++.h> using namespace std; typedef struct qnode{ int data; struct qnode *next; }datanode; typedef struct{ datanode *front; datanode *rear; }squeue; void initqueue(squeue*&q){ q=(squeue*)malloc(sizeof(squeue)); q->front=q->rear=NULL; } void destroyqueue(squeue*&q){ datanode*pre=q->front,*p; if(pre!=NULL) { p=pre->next; while(p!=NULL){ free(pre); pre=p;p=p->next; } free(pre); } free(q); } bool emptyqueue(squeue*&q){ return (q->rear==NULL); } void enqueue(squeue*&q,int e){ //这里有两种情况，1队列为空，2队列不空 datanode *p; p=(datanode*)malloc(sizeof(datanode)); p->data=e; p->next=NULL; if(q->rear==NULL) q->rear=q->front=p; else{ q->rear->next=p; q->rear=p; } } bool dequeue(squeue*&q,int &e){ //这里有三种情况，1队列为空，2队列中只有一个结点，3队列中有两个及其以上结点 datanode*p; if(q->rear==NULL) return false; p=q->front; if(q->rear==q->front) q->rear=q->front=NULL; else q->front=q->front->next; e=p->data; free(p); return true; } void printqueue(squeue*q){ datanode *p=q->front; while(p){ cout<<p->data<<" "; p=p->next; } cout<<endl; } int main(){ squeue *q; initqueue(q); int n;//声明n个人 n=8;//因为题目中是8个人 for(int i=1;i<=n;i++) enqueue(q,i); printqueue(q); int e; int match=0;//喊一喊二 while(q->rear!=NULL){ match=(match+1)%2; if(match){ dequeue(q,e); cout<<e<<" "; } else{ dequeue(q,e); enqueue(q,e); } } } |
标准答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
//求解报数问题 #include <stdio.h> #include <malloc.h> #define MaxSize 100 typedef int ElemType; //---------------------------------------------------------- //-环形队列的基本运算算法----------------------------------- //---------------------------------------------------------- typedef struct { ElemType data[MaxSize]; //存放队中元素 int front,rear; //队头和队尾指针 } SqQueue; //顺序队类型 void InitQueue(SqQueue *&q) //初始化队列 { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=0; } void DestroyQueue(SqQueue *&q) //销毁队列 { free(q); } bool QueueEmpty(SqQueue *q) //判断队列是否为空 { return(q->front==q->rear); } bool enQueue(SqQueue *&q,ElemType e) //进队列 { if ((q->rear+1)%MaxSize==q->front) //队满上溢出 return false; q->rear=(q->rear+1)%MaxSize; q->data[q->rear]=e; return true; } bool deQueue(SqQueue *&q,ElemType &e) //出队列 { if (q->front==q->rear) //队空下溢出 return false; q->front=(q->front+1)%MaxSize; e=q->data[q->front]; return true; } //---------------------------------------------------------- void number(int n) { int i; ElemType e; SqQueue *q; //环形队列指针 InitQueue(q); //初始化队列 for (i=1;i<=n;i++) //构建初始序列 enQueue(q,i); printf("报数出列顺序:"); while (!QueueEmpty(q)) //队列不空循环 { deQueue(q,e); //出队一个元素e printf("%d ",e); //输出元素编号 if (!QueueEmpty(q)) //队列不空 { deQueue(q,e); //出队一个元素e enQueue(q,e); //将刚出列的元素进队 } } printf("\n"); DestroyQueue(q); //销毁队列q } int main() { int i,n=8; printf("初始序列:"); for (i=1;i<=n;i++) printf("%d ",i); printf("\n"); number(n); return 1; } |
求解迷宫
