| « | November 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | | 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 | | | | | | | |
|
公告 |
| 暂无公告... |
| Blog信息 |
|
blog名称:
日志总数:32
评论数量:44
留言数量:0
访问次数:180614
建立时间:2005年1月4日 |
| |
|
 数据结构--队 列
文章收藏
eaglebetter 发表于 2006/8/6 0:22:57 |
| 4-1 队列的定义和基本运算4-1-1 队列（Queue）的定义1．队列的定义2．队列的特性3．队列的实例4-1-2 队列的基本运算（1） 入队操作：InQueue（q，x）（2）出队操作：OutQueue（q，x）（3）读队头元素：ReadFront（q，x）（4）显示队列中元素ShowQueue（q）（5）判队空操作：QEmpty（q）（6）判队满操作：QFull（q）（7）求队列长度Qlen（q）4-2 队列的存储实现及运算实现4-2-1 顺序队列1．顺序队列#define MAXLEN 10 // 队列的最大容量typedef struct {datatype Q[MAXLEN]; // datatype 可根据用户的需要定义数据类型 int front=-1, rear=-1; // 定义队头、队尾指针，并置队列为空 }Queue; Queue *p; // 定义一个指向队的指针变量p=new Queue; // 申请一个顺序队的存储空间 // 在C中用p = malloc(sizeof(Queue))（1） 判队空（2） 入队 p->rear++; // 先将队尾指针加1 p->Q[p->rear]=x; // 入队（3） 出队 p->front++; x=p->Q[p->front]; // 队头元素送x（4） 队列的长度：m=（p->rear）-（p->front）；（5） 判队满：m= MAXLEN；判队空：m=0时。2．循环队列p->rear= (p->rear+1) % MAXLEN;p->front= (p->front+1) % MAXLEN;typedef struct { datatype Q[MAXLEN]; // 定义数据的类型及数据的存储区 int front，rear; // 定义队头、队尾指针 int n; // 用以记录循环队列中元素的个数 }csequeue; // 循环队列变量名3．循环队列的基本运算（1） 置空队csequeue* IniQueue (){ q=malloc (sizeof (csequeue) );q->front=q->rear=MAXLEN-1;q->n=0; return q;}（2） 入队int InQueue ( csequeue *q , datatype x){ if (n= =MAXLEN) { printf ("队满");return 0; // 队满不能入队，返回0 } else { q->rear=(q->rear+1) % MAXLEN; q->data[q->rear]=x; n++; return 1; // 入队成功，返回1}}（3） 出队int Outsequeue (csequeue *q , datatype *x){if (n= =0) { printf ("队空");return 0; // 队空不能出队，返回0 } else { q->front=(q->front+1) % MAXLEN; *x=q->data[q->front]; // 读出队头元素 num– –; return 1; // 出队成功，返回1}}（4） 判队空int Empsequeue (csequeue *q){ if (n = = 0) return 1; //队空为真返回1 else return 0; //否则返回0 }4-2-2 链队列1．链队列的结构2．链队的描述typedef struct queuenode{datatype data; // datatype为特定的类型，根据具体情况可以是char或int等 struct queuenode *next;}queuenode; // 链队结点的类型datatypetypedef struct{queuenode *front,*rear;}linkqueue; // 将头指针、尾指针封装在一起的链队3．头指针和尾指针封装在一个结构中的链队列4．链队的基本运算（1） 入队（进队）void InQueue (linkqueue *q) // 进队函数{ int x; // 定义入队元素类型queuenode *p=new queuenode; // 申请一个新结点p->data=x; // 输入元素p->next=NULL; // 修改指针if (q->front==NULL) q->front=p;elseq->rear->next=p;q->rear=p;}（2） 出队int OutQueue(linkqueue *q,int *v) // 出队函数{ queuenode *p;if (q->front==NULL) // 若队空，不能出队，返回0return 0;else{ p=q->front; // 若队不空，则作出队处理*v=p->data;q->front=p->next;if(q->front==NULL)q->rear=NULL;delete p; // 回收结点return 1; // 返回1}}（3） 读队头元素void ReadFront (linkqueue *q) // 读队首元素函数{if (q==NULL||q->front==NULL) // 若队空，不能读队头元素printf("队空!");elseprintf (q->front->data); // 若队不空，则读队头元素}（4） 显示队列中元素void ShowQueue(linkqueue *q) // 显示队列{queuenode *p=q->front; if (p==NULL) // 判队空printf("队列为空!"); elsewhile(p!=NULL) // 若队不空，则输出队中元素{printf (p->data);p=p->next; // 修改指针}printf("\n");}4-3 队列应用举例1．队列在输入、输出管理中的应用2．对CPU的分配管理3．优先队列（Priority Queue）4．双队列（Double-ends Queue）（1） 向队列数据输入InQueue( )void InQueue(int val) // 输入队列数据{ rear=(rear++)%MAXLEN;if(front==rear)printf("队列已满!");elsequeue[rear]=val;}（2） 队头输出数据OutQueue_front( )int OutQueue_front() // 从队头输出队列数据{ int t;if(front==rear)return -1;t=queue[++front];if(front==MAXLEN)front=0;return t;}（3） 从队尾输出数据OutQueue_rear( )int OutQueue_rear() // 从队尾输出队列数据{ int t;if(front==rear)return -1;t=queue[rear--];if(rear<0&&front!=-1)rear=MAXLEN-1;return t;}小结实验4 队列子系统1．实验目的2．实验内容3．参考程序#include<stdio.h>typedef struct queuenode{ int data;struct queuenode *next;}queuenode;typedef struct{queuenode *front,*rear;}linkqueue;void InQueue(linkqueue *q) // 进队函数 { int x;queuenode *p=new queuenode;printf("\n\t\t请键入一个整数：");scanf("%d",&x);getchar();p->data=x;p->next=NULL;if(q->front==NULL)q->front=p;elseq->rear->next=p;q->rear=p;if(p)printf("\n\t\t%d进队成功！",x);}int OutQueue(linkqueue *q,int *v) // 出队函数{ queuenode *p;if(q->front==NULL)return 0;else{ p=q->front;*v=p->data;q->front=p->next;if(q->front==NULL)q->rear=NULL;delete p;return 1;}}void ShowQueue(linkqueue *q) // 显示队列函数{ queuenode *p=q->front;if(p==NULL)printf("\t\t队列为空!\n");else { printf("\t\t队列为：");while(p!=NULL){ printf("%6d",p->data);p=p->next;}printf("\n");}}void ReadFront(linkqueue *q) // 读队首元素函数{ if(q==NULL||q->front==NULL)printf("\t\t队列为空!没有队顶元素!\n");elseprintf("\n\t\t队首元素是：%4d。\n",q->front->data);}// 输入受限制的双队列#define MAXLEN 20 // 定义队列最大长度int queue[MAXLEN];int front=-1;int rear=-1;void InQueue (int val) // 输入队列数据{ rear=(rear++)%MAXLEN;if(front==rear)printf ("队列已满!");elsequeue [rear]=val;}int OutQueue_rear () // 从队尾输出队列数据{ int t;if (front==rear)return -1;t=queue[rear--];if (rear<0&&front!=-1)rear=MAXLEN-1;return t;}int OutQueue_front () // 从队头输出队列数据{ int t;if(front==rear)return-1;t=queue [++front];if (front==MAXLEN)front=0;return t;}void DQ() // 输入限制性双向队列{ int choice;int out[5];int in[5]={5,4,3,2,1}; // 输入5个数据 int t,pos=0,i;for(i=0;i<5;i++)InQueue (in[i]);printf ("\n\t\t初始数据顺序是：");for(i=0;i<5;i++)printf ("[%d] ",in[i]);printf ("\n");while (front!=rear){ printf("\t\t1------从队头出队");printf("\t\t2------从队尾出队");printf("\n\t\t请选择：");scanf("%d",&choice);switch(choice){case 1:t=OutQueue_front();out[pos++]=t;break;case 2:t=OutQueue_rear();out[pos++]=t;break;}}printf("\n\t\t数据输出的顺序是：");for(i=0;i<5;i++)printf ("[%d] ",out[i]);printf ("\n");getchar();}void main() // 队列子系统主函数{ linkqueue *q=new linkqueue;int val,i=1;char w,choice;queuenode *ptr,*t;q->front=q->rear=NULL;while (i){ printf("\n\n\n\n");printf("\n\t\t\t\t 队 列 子 系 统\n");printf("\n\t\t******************************************");printf("\n\t\t* 1---------------进 队 *");printf("\n\t\t* 2---------------出 队 *");printf("\n\t\t* 3---------------队 顶 元 素 *");printf("\n\t\t* 4---------------显 示 *");printf("\n\t\t* 5---------------双 向 队 列 *");printf("\n\t\t* 0---------------返 回 *");printf("\n\t\t******************************************");printf("\n\t\t请选择菜单号(0--5):");scanf("%c",&choice);getchar();switch(choice){case '1':InQueue(q);break;case '2':if(OutQueue(q,&val)==0)printf("\n\t\t队列为空!\n");elseprintf("\n\t\t出队元素为：%d",val);break;case '3':ReadFront(q);break;case '4':ShowQueue(q);break;case '5':DQ();break;case '0':i=0;break;default:;}if(choice=='1'||choice=='2'||choice=='3'||choice=='4'||choice=='5'){ printf("\n\t\t按回车键继续,按任意键返回主菜单.\n");w=getchar();if(w!='\xA'){getchar();i=0;}}}ptr=q->front;while(ptr!=NULL){ t=ptr->next;delete ptr;ptr=t;} q->front=q->rear=NULL;} |
|
|