数据结构与算法实验报告C版.doc

算法与数据结构 实验报告 实验一：栈与队列 一、实验目的 1、掌握栈和队列特点、逻辑结构和存储结构 2、熟悉对栈和队列的一些基本操作和具体的函数定义。 3、利用栈和队列的基本操作完成一定功能的程序。 二、实验任务 出顺序栈的类定义和函数实现，利用栈的基本操作完成十进制数N与其它d进制数的转换。（如N=1357,d=8） 给出顺序队列的类定义和函数实现，并利用队列计算并打印杨辉三角的前n行的内容。(n=8) 给出链栈的类定义和函数实现，并设计程序完成如下功能：读入一个有限大小的整数n，并读入n个数，然后按照与输入次序相反的次序输出各元素的值。 三、实验原理 1、将十进制数N转化为d进制时，用除去余数法，用d除N所得余数作为d进制当前 个位，将相除所得的商的整数部分作为新的N值重复上述计算，直到N为0为止。 将 前所得到的各余数反过来连接便得到最终结果。将每次求出的余数入栈，求解结束后， 再依次出栈。 2、在杨辉三角中可用上一行的数来求出对应位置的下一行的内容。用队列保存上行内容， 每当由上行的两个数求出下行的一个数时，其中的前一个便需要删除，而求出的数就 入队。为便于求解，在每行的第一个位置添加一个0作为辅助。 3、输出操作应在读入所有输入的整数后才能进行，用栈来存储这些数据，调用入栈出栈 函数实现相关功能。 四、程序清单 第一题 #include iostream.h #ifndef STACK_H #define STACK_H const int maxlen=256; typedef int elementtype; enum error_code{success, underflow, overflow}; class stack{ public: stack(); bool empty() const; bool full() const; error_code get_top(elementtype x) const; error_code push(const elementtype x); error_code pop(); private: int count; elementtype data[maxlen]; }; stack::stack(){count=0;} bool stack::empty() const { if(count==0) return true; return false; } error_code stack::get_top(elementtype x) const { if(empty()) return underflow; else{x=data[count-1]; return success; } } error_code stack::push(const elementtype x) { if(full()) return overflow; data[count]=x; count++; return success; } error_code stack::pop() { if(empty()) return underflow; count--; return success; } bool stack::full() const { if(count==maxlen) return true; return false; } #endif void Dec_to_Ocx(int N, int d) { stack S; int Mod,x; while(N!=0) { Mod=N%d; S.push(Mod); N=N/d; } while(!S.empty()) { S.get_top(x); S.pop(); coutx; } } void main() { int N;int d; cinN; cind; Dec_to_Ocx(N,d); }  第二题 #include iostream.h const int maxlen=256; typedef int elementtype; enum error_code{success, underflo