《队的操作的算法实现》由会员分享,可在线阅读,更多相关《队的操作的算法实现(9页珍藏版)》请在金锄头文库上搜索。
1、一、顺序循环队的实现算法1 方法一# define maxsize 20typedef struct ElementType datamaxsize;int front,rear;SqQueue;(1) 队列的初始化void InitcycQueue(Cycqueue *sq) sq-front=0;sq-rear=0; (2) 入队列int EnCycQueue(Cycqueue *sq,ElementType x) if(sq-rear+1)%maxsize=sq-front) error(队满); return 0; /*队满,入队列失败*/Else sq-datasq-rear=x;
2、sq-rear=(sq-rear+1)%maxsize;return 1; (3) 出队列int EnCycQueue(Cycqueue *sq, ElementType *x)if(sq-front=sq-rear) error(队空); return 0; /*队空,出队列失败*/else *x=sq-datasq-front; sq-front=(sq-front+1)%maxsize;return 1; (4) 判队空int EmptyCycQueue(Cycqueue *sq)if(sq-rear=sq-front) return 1;else return 0; (5) 取队头in
3、t GetHead(cycqueue *sq, ElementType *x) if(sq-rear=sq-front) return 0;else *x=sq-datasq-front; return 1;2. 方法二typedef struct ElementType datamaxsize;int rear,front;int count; Cycqueue;(1) 队列的初始化initQueue(Cycqueue *sq) sq-count=0; sq-front=sq-rear=0;(2)入队int EntQueue(Cycqueue*sq,ElementType x) if(sq-
4、count=maxsize) printf(“队满n”); return(0);else sq-rear= (sq-rear+1)% maxsize; sq-datasq-rear=x;sq-count+; return(1); (3)出队int DelQueue(Cycqueue*sq,ElementType *x) if(sq-count=0) printf(“队空 n”); return(0);else *x =sq-datasq-front;sq- front = (sq- front +1)% maxsize; sq-count-; return(1); (4) 判队空int Emp
5、tyCycQueue(Cycqueue *sq)if(sq-count=0) return 1;else return 0; (5) 取队头int GetHead(cycqueue *sq, ElementType *x) if(sq-count=0) printf(“队空n”); return(0);else *x =sq-datasq-front; return(1); 二、链队的实现算法链队的类型定义如下:Typedef struct nodeElementType data;Struct node *next;Lqueuenode; (链队结点类型)typedef struct Lqu
6、euenode *front,*rear;linkqueue;(1) 队列的初始化void InitQueue(linkqueue *lq) Lqueuenode *p;p=(Lqueuenode *)malloc(sizeof(Lqueuenode);lq-front=p;lq-rear=p;(lq-front)-next=NULL;(2)入队列void enqueue(linkqueue *lq; ElementType x) Lqueuenode *p;p=(Lqueuenode*)malloc(sizeof(Lqueuenode);p-data=x;p-next=NULL;(lq-re
7、ar)-next=p;lq-rear=p;(3)出队列Int OutQueue(linkqueue * lq, ElementType * x) Lqueuenode *s;if(lq-front=lq-rear) error(队空);return 0;else s=(lq-front)-next; *x=s-data;(lq-front)-next=s-next;if(s-next=NULL) lq-rear=lq-front;free(s); return 1;(4)判队空Int EmptyQueue(linkqueue *lq) if(lq-rear=lq-front) return 1
8、;else return 0;(5)读队头元素Int GetHead(linkqueue *lq, ElementType *x) Lqueuenode *p;if( lq-rear=lq-front) return 0;else p=lq-front-next; *x=p-data; return 1; 三、举例(排队看病例子)看病排队过程,主要重复两件事:(1)病人把病历交给护士,进入等候队列候诊;(2)护士从等候队列取出下一位患者的病历,该患者进入诊室就诊。自然语言算法如下:while(1)接收命令;若为,读入病人的病历号,排队候诊;若为,队列中第一个(队头)病人出队列就诊;若为,队列中
9、剩余病人按顺序依次就诊,结束。队列采用链队,DataType 现为 int。链队结构用 C 语言描述如下:typedef struct linked_queue int data;struct linked_queue * next; LqueueTp;typedef struct queueptr LqueueTp * front, *rear;QueptrTp;用 C 语言描述如下:void see_doctor( ) QueptrTp lq;int n;char ch;InitQueue(&lq)While(1) printf(n 请输入命令:);scanf(%c,ch);switch(upper(ch) caseA:printf(输入病历号n);scanf(%d,n);EnQueue(break;caseN:if (EmptyQueue(lq) OutQueue(else printf(无病人等待就诊n);break;caseQ:printf(排队等候的病人依次就诊n);break;if(upper(ch)=Q) /* 队列中乖余的病人依次就诊 */while(! EmptyQueue(lq) OutQueue(printf(病历号为%d 的病人就诊,n);break;