算法与数据结构实验报告.docx

算法与数据结构实验报告 学院：计算机与信息学院 专业班级： 姓名： 学号： 实验一栈和队列 实验目的： 掌握栈和队列特点、逻辑结构和存储结构 熟悉对栈和队列的-?些基本操作和具体的函数定义。 利用栈和队列的基本操作完成一定功能的程序。 实验任务： 1?给出顺序栈的类定义和函数实现，利用栈的基本操作完成十进制数N与其它d进制数的 转换。(如 N=1357,d=8) 实验原理： 将十进制数N转换为八进制时，采用的是“除取余数法”，即每次川8除N所得的余数作为 八进制数的当前个位，将相除所得的商的整数部分作为新的N值重复上述计算，肓到N为 0为止。此时，将前面所得到的各余数反过来连接便得到最后的转换结果。 程序清单： # includeiostream #includecstdlib using namespace std; typedef int DATA.TYPE; const int MAXLEN=100; enum error_code { success,overflow,underflow }; class stack { public: stack(); bool empty()const; crror_codc gct_top(DATA_TYPE x)const; error_code push(const DATA_TYPE x); error_code pop(); bool full()const; private: DATA_TYPE data[MAXLEN]; int count; }; stack: :stack() { count=0; } bool stack::empty()const { return count==0; } error_code stack::get_top(DATA_TYPE x)const if(empty()) return underflow; else { x=data[count-l J; return success; } } error_code stack::push(const DATA_TYPE x) { if(full()) return overflow; else { data[countj=x; count++; } } error_code stack: :pop() { if(empty()) return underflow; else { count； return success; } } bool stack::full()const { return count==MAXLEN; } void main() stack S; int N,d; cout?u请输入一个I ?进制数N和所需转换的进制dM?endl; cin?N?d; if(N==O) { coutvv “输出转换结果:n?N?endl; } while(N) S.push(N%d); N=N/d; } coutvv输 ill 转换结果:?endl; while(!S.empty ()) { S.get_top(N); cout?N; S.pop(); } cout?endl; } while(!S.empty()) { S.get_top(x); cout?x; S.pop(); 测试数据：N=1348 d=8 运行结果： 谪输入一个十进制数N和所需转换的进制d 1348 影出转换结果： 2504 Press any key to continue 2?给出顺序队列的类定义和函数实现，并利用队列计算并打印杨辉三角的前n行的内容。 (n=8) 实验原理：杨辉三角的规律是每行的第一和最后一个数是1,从第三行开始的其余的数是上 —?行对应位置的左右两个数之和。因此，可用上一行的数來求出对应位置的下一行内容。为 此，需要用队列来保存上一行的内容。每当由上一行的两个数求出卜?行的一个数时，具屮 的前一个便需要删除，而新求出的数就要入队。 程序清单： # includciostrcam #includecstdlib using namespace std; typedef int DATA_TYPE; const int MAXLEN=100; enum error_code { success,underflow,overflow }; class queue { public: queue(); bool empty()const; crror_codc gct_front(DATA_TYPE x)const; crror_codc appcnd(const DATA_TYPE x); error_code serve(); bool full()const; private: