数据结构-利用循环队列打印杨辉三角.docx

//------循环队列—队列的顺序存储结构----- #includestdio.h #includemalloc.h #includeprocess.h //exit的头文件 #define OK 1 #define ERROR 0 #define MAXQSIZE 100//最大队列长度 #define Status int #define N 10 #define QElemType int typedef struct{ QElemType *base;//初始化的动态分配存储空间 int front; //头指针，若队列不空，指向队列头元素 int rear; //尾指针，若队列不空，指向队列队尾元素的下一位置 }SqQueue; //-----循环队列的基本操作的算法描述---- Status InitQueue(SqQueue Q){ //构造一个空队列 Q.base=(QElemType *)malloc(MAXQSIZE * sizeof(QElemType)); if(!Q.base)exit(-1);//存储分配失败 Q.front=Q.rear=0; return OK; } int QueueLength(SqQueue Q){ //返回Q的元素个数，即队列的长度 return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; } Status EnQueue(SqQueue Q,QElemType e){ //插入元素e为Q的新的队尾元素 if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;//队列满 Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; } Status DeQueue(SqQueue Q,QElemType e){ //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK； //否则返回ERROR if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; } Status GetHead(SqQueue Q,QElemType e){ //若队列不空，则用e返回Q的队头元素，并返回OK； //否则返回ERROR if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; return OK; } //----打印杨辉三角(前N行)------------- void YangHuiTriangle() { int i,n,temp,x; SqQueue Q; InitQueue(Q); EnQueue(Q,1); //第一行元素入队 for(n=2;n=N;n++) //产生第n行元素并入队，同时打印第n-1行的元素 { EnQueue(Q,1); //第n行的第一个元素入队 for(i=1;i=n-2;i++) //利用队中第n-1行元素产生第n行的中间n-2个元素并入队 { DeQueue(Q,temp); printf(%d,temp); //打印第n-1行的元素 GetHead(Q,x); temp=temp+x; //利用队中第n-1行元素产生第n行元素 EnQueue(Q,temp); }//for DeQueue(Q,x); printf(%d,x); //打印第n-1行的最后一个元素 EnQueue(Q,1); //第n行的最后一个元素入队 printf(\n); }//for }//YangHuiTriangle void main() { YangHuiTriangle(); }