数据结构 实验报告04 |
您所在的位置:网站首页 › 数据结构与算法分析实验心得 › 数据结构 实验报告04 |
一、实验目的和要求
设计算法,用队列计算并打印杨辉三角的前n行的内容。 要求抽象出队列结构进行独立实现。 二、实验环境编译器:DevC++ 系统:Windows10 三、实验内容设计算法,用队列计算并打印杨辉三角的前n行的内容。 四、实验过程 4.1 任务定义和问题分析1.建造功能完善的队列(模板类) 具体实现功能有入队、出队、判空、判满、返回栈顶元素。 2.了解杨辉三角 并知道相邻元素的关系 3.将队列和杨辉三角模型联系起来 利用队列来处理杨辉三角 如何实现以下形式的杨辉三角输出 4.2 数据结构的选择和概要设计 使用模板类来实现队列底层代码 使用的是循环队列 运用的动态数组存储数据 4.3 详细设计 首先我们知道杨辉三角的前一行和后一行是有一定关系的 第一行是1 第二行是1 1 由于是用队列来处理杨辉三角 所以应该使用递推的方式来由已经在队列里的一行循环生成下一行 但边界上不好运用共同的关系 为了更好的符合杨辉三角相邻行之间的关系 应该将第一行补充为 0 1 0 第二行补充为 0 1 1 0
且由于下一行的一个数必定由上一行的两个数来组成 所以定义两个变量l,r来存储左右 初始化为零 没从上一行获取一个值 将右值赋给左值 将取得的值赋给右值 (这里的左值便是存储下一行对应位置左边的值的变量 简称左值 右值同理) 接下来将左值和右值相加的值入队 形成下一行的一个元素 并将出队的元素打印 然后每一行处理的数的个数是一定的 (可以根据循环的层数来确定)
上面的处理过程中是有几处细节的 由于第i行只有i次输出 所以循环层数仅有i 而第i-1行元素在队列中有i+1个元素(首尾追加了0)所以要在循环开始前先出队一次,在处理后,再入队一次(因为第i行应该会有i+2个元素在队列中);在循环结束后 再一次先出队再入队代码最开始跑出来是这样的![]() ![]() ![]() 测试数:5 测试数:9
测试数:10
测试数:15
![]() 由于屏幕大小所限 导致结果在10行以后便不很美观 但当行数过大时宽度固定为10是不够用的 问题出在使用了固定宽度 后期如果优化就需要 根据行数来调整宽度 但当出现上述情况的时候 屏幕就不够用了 就不用修改了 六、实验收获复习了固定宽度输出 printf(“%*d”,len,arry); 七、参考文献无 八、附录(源代码) #include #include #include using namespace std; template class Queue { public: Queue(int Size) { maxSize = Size; front = 0; rear = 0; count = 0; elements = new DataType[Size]; } ~Queue() { delete[] elements; } bool InsertQueue(DataType data) { if (count == maxSize) return false; elements[rear] = data; rear = (rear + 1) % maxSize; count++; return true; } bool IsEmpty() { if (count == 0) { return true; } return false; } bool IsFull() { if (count == maxSize) return true; return false; } DataType GetTop() { return elements[front]; } DataType PopTop() { if (count == 0) exit(1); DataType temp = elements[front]; front = (front + 1) % maxSize; count--; return temp; } int GetNum() { return count; } private: int count, maxSize, front, rear; DataType *elements; }; Queue q(1010); int n; void init() { q.InsertQueue(0); q.InsertQueue(1); q.InsertQueue(0); } void work(int x) { int l=0,r=0; q.InsertQueue(0); r=q.PopTop(); for(int i=1;i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |