下载文档原格式
#ifndef DS_H#define DS_H#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2//Status是函数的类型，其值是函数结果状态代码typedef int Status;#endif//////////////////////////////////////#include "ds.h"#ifndef SqQueue_H#define SqQueue_H#define MAXQSIZE 100//最大队列长度typedef int QElemType;typedef struct{QElemType *base;//动态分配存储空间int front;//头指针,若队列不空,指向队列头元素int rear; //尾指针,若队列不空,指向队列尾元素的下一个位置}SqQueue;Status InitQueue(SqQueue &,int);Status EnQueue(SqQueue &,QElemType);Status DeQueue(SqQueue &,QElemType &);void GetHead(SqQueue,QElemType &);bool QueueEmpty(SqQueue);#endif///////////////////////////////////////#include <stdlib.h>#include "ds.h"#include "SqQueue.h"Status InitQueue(SqQueue &Q,int x){//构造一个空队列QQ.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;return OK;}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;}void GetHead(SqQueue Q,QElemType &e){e=Q.base[Q.front];}bool QueueEmpty(SqQueue Q){if(Q.front==Q.rear)return true;elsereturn false;}////////////////////////////////////////////////////#include <iostream.h>#include "ds.h"#include "SqQueue.h"void yanghui(int n){//打印输出杨辉三角的前n(n>0)行SqQueue Q;int i;QElemType e;int k;for(i=1;i<=n;i++)cout<<' ';cout<<'1'<<endl;//在中心位置输出杨辉三角最顶端的"1"InitQueue(Q,n+2);// 设置最大容量为n+2的空队列EnQueue(Q,0);//添加行界值EnQueue(Q,1);EnQueue(Q,1 );//第一行的值入队列k=1;while(k<n){//通过循环队列输出前n-1行的值QElemType s;for(i=1;i<=n-k;i++)cout<<' ';//输出n-k个空格以保持三角型EnQueue(Q,0);//行界值"0"入队列do{//输出第k行,计算第k+1行DeQueue(Q,s);GetHead(Q,e);if(e)cout<<e<<' ';//若e为非行界值0,则打印输出e的值并加一空格else cout<<endl;//否则回车换行,为下一行输出做准备EnQueue(Q,s+e);}while(e!=0);k++;}//whileDeQueue(Q,e);//行界值"0"出队列while(!QueueEmpty(Q)){//单独处理第n行的值的输出DeQueue(Q,e);cout<<e<<' ';}//while}//yanghuivoid main(){yanghui(4);}////////////////////////////////////////////。
杨辉三角(一)需求分析1.逐行打印二项展开式(a + b)i 的系数2.要求：输入杨辉三角的阶数n，在屏幕上显示数杨辉三角形。
3.输入的值n以小于12为宜（图形漂亮）。
(二)概要设计1. 首先初始化一个队列，元素为1，然后根据这个队列迭代生成任意行的二项式系数。
2. 判断用户输入的行数，然后决定循环次数。
这些循环中，程序根据杨辉三角的实际构造函数模拟构造过程。
每次形成一个新的二项式系数序列，并将这个序列保持在一个新的队列中。
本次循环结束后，这个心构造的序列将作为下次循环来构造另一个二项式序列的参照序列。
(三)详细设计1.定义队列结点typedef struct QNode{int data;struct QNode *next;}QNode ,*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;2.基本操作函数原型●队列初始化void InitQueue(LinkQueue *Q){Q->front =Q->rear = (QueuePtr)malloc(sizeof(QNode));if(!Q->front) printf("OVERFLOW");Q->front->next= NULL;}●插入元素e为新的队尾元素void EnQueue(LinkQueue *Q,int e){QNode *p;p = (QueuePtr)malloc(sizeof(QNode));if(!p) printf("OVERFLOW");p->data = e;p->next = NULL;Q->rear->next = p;Q->rear = p;}●void DeQueue(LinkQueue *Q){ QNode *p;if(Q->front == Q->rear) printf("ERROR");Q->front->next = Q->front->next->next;}●美化形状for(i = 1;i <= n; i++){printf("\n");c=i;for(b=1;b<=n-c;c++){printf(" ");}}●根据上行系数求下行系数for (j=1;j<=i+2;j++){t = q->front->next->data;DeQueue (q);EnQueue (q,s+t);s = t;if (j!=i+2) printf("%3d ",s);}(四)调试分析1.美化形状时，第一次的输出空格的个数和位置考虑的有瑕疵，导致图像歪歪曲曲的。
//------循环队列—队列的顺序存储结构-----#include<stdio.h>#include<malloc.h>#include<process.h> //exit的头文件#define OK 1#define ERROR 0#define MAXQSIZE 100//最大队列长度#define Status int#define N 10#define QElemType inttypedef 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；//否则返回ERRORif(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；//否则返回ERRORif(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);}//forDeQueue(Q,x);printf("%d",x); //打印第n-1行的最后一个元素EnQueue(Q,1); //第n行的最后一个元素入队printf("\n");}//for}//YangHuiTrianglevoid main(){YangHuiTriangle();}Welcome !!! 欢迎您的下载，资料仅供参考！。
/*用队列方法输出杨辉三角。
*/#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#define ElemType int/*-----LNode的结点类型定义-----*/struct LNode{ElemType data; //值域LNode* next; //链接指针域};/*-----队列的链接存储结构的定义-----*/struct LinkQueue{LNode* front; //队首指针LNode* rear; //队尾指针};/*------1.初始化链队-----*/void InitQueue(LinkQueue& HQ){HQ.front=HQ.rear=NULL; //把队首和队尾指针置为空}/*-----2.向链队中插入一个元素------*/void EnQueue(LinkQueue& HQ, ElemType item){LNode* newptr=new LNode; //得到一个新的结点newptr->data=item; //把item 的值赋给新结点的值域newptr->next=NULL; //把新结点的指针域置为空if(HQ.rear==NULL) //若链队为空，则新结点既是队首又是队尾{HQ.front=HQ.rear=newptr;}else //若链队非空，则新结点被链接到队尾并修改队尾指针{HQ.rear=HQ.rear->next=newptr;}}/*-------3.从队列中删除一个元素-------*/ElemType OutQueue(LinkQueue& HQ){if(HQ.front==NULL) //若链队为空则终止运行{cerr<<"链队为空，无法删除！"<<endl;exit(1);}ElemType temp=HQ.front->data; //暂存队首元素以便返回LNode* p=HQ.front; //暂存队首指针以便收回队首指针HQ.front=p->next; //使队首指针指向下一个结点if(HQ.front==NULL) //若删除后链队为空，则使队尾指针为空{HQ.rear=NULL;}delete p; //回收原队首结点return temp; //返回被删除的队首元素}void YanyHuiTriangular(LinkQueue& HQ, int n){int i,j; //i，j 都是循环变量int first,second; //first,second 分别记录上一行的两个累加数EnQueue(HQ,1);for(i=1; i<n+1; i++){ //第 0 至 n-1 行元素分别入列，并输出；最后第 n 行入列first=0; second=0;//控制每行前头空格的输出for(j=0; j<n-i+1; j++){cout<<setw(3)<<' ';}for(j=0; j<i; j++){second=OutQueue(HQ);cout<<setw(3)<<second<<setw(3)<<' ';EnQueue(HQ,first+second);first=second;}cout<<endl; //输完一行，回车EnQueue(HQ,second);}//最后输出最后一行元素（即第 n 行出列）for(j=0; j<n+1; j++){cout<<setw(3)<<OutQueue(HQ)<<setw(3)<<' '; }cout<<endl;}void main(){LinkQueue LQ;InitQueue(LQ);cout<<"用队列输出杨辉三角!"<<endl<<endl; int n;cout<<"请输入要输出多少行杨辉三角："; cin>>n;YanyHuiTriangular(LQ,n);}。
实习报告1.实习题目：杨辉三角2.实习内容：用循环队列或者链队列实现杨辉三角的输出3.程序代码说明（结合流程图，详细介绍关键算法的编程思路和所应用的数据结构知识）：#include"iostream.h"#include"stdlib.h"typedef int QElemType;typedef struct LNode{QElemType data;struct LNode *next;}LNode,*QueuePtr; //链表typedef struct{QueuePtr front; //队头指针QueuePtr rear; //队尾指针} LinkQueue; //链队列void InitQueue( LinkQueue &Q){//构造一个空队列(带头结点)Q.front=Q.rear=new LNode;Q.front->next=NULL;}void DestroyQueue(LinkQueue &Q){//销毁队列,头结点也被销毁while(Q.front){Q.rear=Q.front->next;delete Q.front;Q.front = Q.rear;}//while}void EnQueue (LinkQueue &Q,QElemType e){//插入元素e为Q的新的队尾元素QueuePtr p;p=new LNode;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;}bool DeQueue (LinkQueue &Q, QElemType &e){//若队列不空，则删除Q的队头元素，用e返回其值,并返回TRUE，//否则返回FALSE；QueuePtr p;if(Q.front==Q.rear)return false;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)//保护尾指针Q.rear=Q.front;delete p;return true;}bool GetHead(LinkQueue &Q,QElemType &e){//获取队头元素if(Q.front==Q.rear)return false;else{e=Q.front->next->data;return true;}}void YangHui(int n){ int i,k;QElemType e,s;// 打印输出杨辉三角的前n ( n > 0 )行LinkQueue Q;for(i=0;i<n;i++) cout<<' ';cout<<'1'<<endl;//在中心位置输出杨辉三角最顶端的“1”InitQueue(Q);//设置最大容量为n+2的空队列EnQueue(Q,0);//添加行界值EnQueue(Q,1);EnQueue(Q,1);//第一行的值入队列k=1;while(k<n){//通过循环队列输出前n-1行的值for(i=1;i<=n-k;i++)cout<<' ';//输出n-k个空格以保持三角型EnQueue(Q,0);//行界值“0”入队列do{//输出第k行，计算第k+1行DeQueue(Q,s);//取出并删除队头元素GetHead(Q,e);//用e返回队头元素if(e) cout<<e<<' ';//若e为非行界值0，则打印输出e的值并加一空格else cout<<endl;//否则回车换行，为下一行输出做准备EnQueue(Q,s+e);//插入队尾元素s+e}while(e!=0);k++;}DeQueue(Q,e);while(Q.rear!=Q.front){DeQueue(Q,e);cout<<e<<' ';}cout<<' '<<endl;}//杨辉三角void main(){int n;cout<<"输入n值:";cin>>n;YangHui(n);}。
数据结构实验报告实验一杨辉三角形(Pascal’s triangle)一、需求分析1.输入的形式和输入值的范围本程序中，需输入的杨辉三角级数level为正整数，由键盘输入，以回车结束2.输出的形式通过屏幕输出杨辉三角3.程序所能达到的功能用户从键盘输入需要的杨辉三角级数，从屏幕输出杨辉三角4.测试数据输入：5输出： 1 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1二、概要设计以链队列结构实现该实验1.抽象数据类型定义ADT Queue {数据对象：D = { ai | ai∈ElemSet , i = 1,2,…,n,n≥0 }数据关系：R1={<ai-1,ai> | ai-1 , ai∈D, i=2,…,n}约定其中ai端为队列头，an端为队列尾基本操作：InitQueue ( &Q )操作结果：构造一个空队列QDestroyQueue ( &Q )初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在ClearQueue ( &Q )初始条件：队列Q已存在操作结果：将Q清为空队列QueueEmpty ( Q )初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则FALSEQueueLength ( Q )初始条件：队列Q已存在操作结果：返回Q的元素个数，即队列长度GetHead ( Q , &e )初始条件：Q为非空队列操作结果：用e返回Q的队头元素EnQueue ( &Q , e )初始条件：队列Q已存在操作结果：插入元素e为Q的新队尾元素DeQueue ( &Q , &e )初始条件：Q为非空队列操作结果：删除Q的队头元素，并用e返回其值QueueTraverse ( Q , visit( ) )初始条件：Q已存在且非空操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit( )。
实验4 杨辉三角1 实验要求打印二项展开式（a+b）^i的系数，将其系数构成杨辉三角形。
2 简单的需求分析1，该程序的描述是：建立一个循环队列，以及一个利用队列实现逐行打印杨辉三角形的前n行的算法，最后在主函数中输入所要打印的杨辉三角形的行数，调用函数输出结果。
2，程序运行后,首先会出现"请输入二项式为几次幂"，用户根据自己的选择输入后，系统便会输出打印的情况。
3 概要设计1、所用的抽象数据类型：（1）//循环队列的类定义template<class T>class SeqQueue{public:SeqQueue(int sz=10); //构造函数~SeqQueue(){delete[] elements;} //析构函数bool EnQueue(const T& x); //若队列不满，则将x进队，否则队溢出处理bool DeQueue(T& x); //若队列不空，则退出队头元素x并由函数返回true，否则队空，返回falseprotected:int rear,front; //队尾与队头指针T* elements; //存放队列元素的数组int maxSize; //队列最大可容纳元素个数};（2） //链式栈的类定义void YANGVI(int n){//分行打印二项式(a+b)^n展开式的系数，在程序中利用一个队列，在输出上一行系数时，将其//下一行的系数预先放入队列中，在各行系数之间插入一个0int k;SeqQueue<int> q(n+2); //建立队列对象并初始化int i=1,j,s=k=0,t,u,m; //计算下一行系数时用到的工作单元q.EnQueue(i);q.EnQueue(i); //预先放入第一行的两个系数for(i=1;i<=n;i++) //逐行处理{cout<<endl; //换一行q.EnQueue(k); //各行间插入一个0for(j=1;j<=i+2;j++) //处理第i行的i+2个系数（包括一个0）{q.DeQueue(t); //读取一个系数u=s+t; q.EnQueue(u); //计算下一行系数，并进队列s=t;if(j!=i+2) cout<<s<<' '; //打印一个系数，第i+2个是0 }}}2、函数调用关系：在main（）函数中，先输入所要打印的杨辉三角形的行数，然后调用YANGVI(int n)函数4 详细设计部分#include<iostream.h>#include<assert.h>#include<stdio.h>//循环队列的类定义template<class T>class SeqQueue{public:SeqQueue(int sz=10); //构造函数~SeqQueue(){delete[] elements;} //析构函数bool EnQueue(const T& x); //若队列不满，则将x进队，否则队溢出处理bool DeQueue(T& x); //若队列不空，则退出队头元素x并由函数返回true，否则队空，返回falseprotected:int rear,front; //队尾与队头指针T* elements; //存放队列元素的数组int maxSize; //队列最大可容纳元素个数};//循环队列的构造函数template<class T>SeqQueue<T>::SeqQueue(int sz):front(0),rear(0),maxSize(sz){//建立一个最大具有maxSize个元素的空队列elements=new T[maxSize];//创建队列空间assert(elements!=NULL);//断言：动态存储分配成功与否}//循环队列的进队template<class T>bool SeqQueue<T>::EnQueue(const T& x){if((rear+1)%maxSize==front) {return false;} //队列满则插入失败，返回else{elements[rear]=x; //按照队尾指针指示位置插入rear=(rear+1)%maxSize; //队尾指针加1return true; //插入成功，返回}}//循环队列的出队template<class T>bool SeqQueue<T>::DeQueue(T& x){if(front==rear) {return false;} //若队列空则删除失败，返回else{x=elements[front];front=(front+1)%maxSize; //队头指针加1return true;//删除成功，返回}}//打印杨辉三角形的前n行函数定义void Y ANGVI(int n){//分行打印二项式(a+b)^n展开式的系数，在程序中利用一个队列，在输出上一行系数时，将其//下一行的系数预先放入队列中，在各行系数之间插入一个0int k;SeqQueue<int> q(n+2); //建立队列对象并初始化int i=1,j,s=k=0,t,u,m; //计算下一行系数时用到的工作单元q.EnQueue(i);q.EnQueue(i); //预先放入第一行的两个系数for(i=1;i<=n;i++) //逐行处理{cout<<endl; //换一行q.EnQueue(k); //各行间插入一个0for(j=1;j<=i+2;j++) //处理第i行的i+2个系数（包括一个0）{q.DeQueue(t); //读取一个系数u=s+t; q.EnQueue(u); //计算下一行系数，并进队列s=t;if(j!=i+2) cout<<s<<' '; //打印一个系数，第i+2个是0}}}//主函数void main(){int m;cout<<"请输入二项式为几次幂"<<endl;cin>>m;Y ANGVI(m);cout<<endl;}/5 调试与测试1.输入所要打印的杨辉三角形的行数2，显示结果。
打印杨辉三角形C语言程序引言杨辉三角形是数学中一种经典的图形，它具有许多有趣的性质和应用。
在本文中，我们将使用C语言编写一个程序来打印杨辉三角形。
通过分析程序实现过程和结果展示，我们可以深入探讨杨辉三角形的形成规律和数学性质。
程序实现过程步骤一：确定杨辉三角形的行数在开始编写程序之前，我们需要确定要打印的杨辉三角形的行数。
用户可以通过程序输入或者直接在代码中指定。
步骤二：创建二维数组我们将使用一个二维数组来存储杨辉三角形的数字。
数组的行数等于用户指定的行数，而每一行的列数等于该行的索引加1。
例如，第一行只有一个数字，第二行有两个数字，以此类推。
步骤三：初始化数组在创建数组后，我们需要对其进行初始化。
杨辉三角形的第一行和第一列的值都是1，其他位置的值等于其上方数字与左上方数字之和。
步骤四：打印杨辉三角形通过循环遍历数组，并将其值打印出来，我们可以在控制台上输出杨辉三角形的图形。
程序代码示例下面是使用C语言编写的打印杨辉三角形的程序：#include <stdio.h>// 定义最大行数#define MAX_ROWS 10int main() {int rows, coef = 1, space, i, j;// 获取用户输入的行数printf("请输入杨辉三角形的行数：");scanf("%d", &rows);// 判断行数是否超过最大行数rows = (rows > MAX_ROWS) ? MAX_ROWS : rows;// 打印杨辉三角形for(i = 0; i < rows; i++) {for(space = 1; space <= rows - i; space++) printf(" ");for(j = 0; j <= i; j++) {if (j == 0 || i == 0)coef = 1;elsecoef = coef * (i - j + 1) / j;printf("%4d", coef);}printf("\n");}return 0;}程序结果展示通过运行上述代码，我们可以得到以下结果示例：请输入杨辉三角形的行数：611 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1杨辉三角形的数学性质杨辉三角形具有许多有趣的数学性质，下面我们将逐一探讨一些常见的性质：性质一：对称性杨辉三角形是关于中心对称的，也就是每一行的数字从中间开始以对称的方式排列。
