计算机数据结构算法实验报告

计算机基础算法实验报告 班级计算机10-7 学号3 姓名李欣 指导教师 陈子军 完成日期2011年12月20日 一、两个长整数相加 1. 实验任务 要求用链表单链表或双向链表实现任意位数的整数相加。 2. 设计思想 首先考虑如何表示长整数 线性表的表头存放个位，向后以此存放高位 这样方便求和 线性表的每一项表示长整数的十进制的三位，这样方便输出 考虑构造函数的参数 unsigned long 或者 const char* 3. 主要变量说明 CLList为一个链式线性表模板类 Clonglnt长整数类包括一个CLList对象用于存放长整数 4. 算法描述 求和两个长整数的线性表的每项，结果加进位对1000取余append 到新长整数对象的线性表中，结果加进位除以1000为新的进位。 For imax_len || array array 二 vl. Iist[i]v2. list[i]array; vO. list, appendarrar1000; arrayarray1000; 5. 程序结构 Clonglnt typedef CLListint CList; m_vec CList Clonglnt int num 二 0; Clonglnt const char *num; void print ; void addClonglnt vl, Clonglnt v2; friend Clonglnt operator Clonglnt vl, Clonglnt v2; friend ostreamfe operatorostream cou, Clonglnt vl; 6. 调试情况 忽略了当所有位相加后，最后产生的进位。 自己的CLList模板类没有拷贝构造函数导致了拷贝错误。 7. 运行结果 123, 999, 999, 000 1,000 124, 000, 000, 000 8. 设计技巧 封装了 CLList iterator类对象，如果迭代器超范围则返回零。 这样可以简化加法实现 9. 心得体会 体会到数据结构这个工具的意义。 体会到使用工具的重要性。 程序清单 Clonglnt内部封装的CLList迭代器类 struct itor{ void operator ifm_start m_final m_start; } int operator* { ifm_start m_final return *m_start; return 0; } 〃省略了变量定义 }； Clonglnt的字段 CLList m_vec;〃唯一字段 实现 void ClonglntaddClongInt vl,Clonglnt v2 { 「 「 〃版本三 int max_len v 1 .m_vec. size v2 .m_vec. size vl.m_vec.sizev2.m_vec.size; int array 0; itor pVlvl.m_vec .begin,v l.m_vec.end; itor pV 2v2.m_vec .begin。, v2 .m_vec. end; forint i0;imax_len || array;i { array *pVl *pV2 array; m_vec .appendarray ARRAY; array array/ARRAY; pVl;pV2; 二、算术表达式求值 1. 实验任务 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式, 利用给定的算符优先关系，实现对算术四则混合运算表达式的求值，并 演示在求值过程中运算符栈、操作数栈、操作数栈和主要操作的变化过 程。注意要求表达式中的整数可以是多位的。 2. 设计思想 使用栈储存暂时不用的数值 3. 主要变量说明 两个栈对象 CLstackmun_op m_num_stack; CLstackmun_op m_op_stack; 4. 算法描述 如果当前运算符的级别小于栈顶运算符，则取出数据栈的两个数进 行运算。 5. 程序结构 〃返回运算符的枚举值 OPTYPE orderchar theta; //判断是否为运算符 bool VT char str; 6. 调试情况 为了方便输入默认235等价于2* 35 但是没有考虑到21ogl0等价于2*logl0 7. 运行结果 25*2 14. 8. 设计技巧 为了不实例化多个模板，统一使用一个模板，参数为 Union numop{ Double num; OPTYPE op; }； 9. 心得体会 将一个问题抽象，在将它实现。 这样使代码结构简单逻辑清晰，不容易出错。 程序清单 运算符优先级表格 1,-1,-1,-1, 1, 1}, 1,1,-1,-1,1J}, {1,1,2,2,1,1}, {-1, -1, -1, -1,0, 2}, 1, 1,2,2, 1, 1], {-1,-1,-1,-1,2,0}