2017中国石油大学 数据结构课程设计 在线考试 标准答案
求:设计算法,实现一个任意长的整数进行加法、减法运算的演示程序。例如:1234,5123,4512,3451,2345与-1111,1111,1111,1111,1111的加法结果为:0123,4012,3401,2340,1234。基本要求如下:
(1)利用链表实现长整数的存储,每个节点含一个整型变量;
(2)整型变量的范围:-(2^15 -1)~(2^15 -1);
(3)输入与输出形式每四位一组,组间用逗号分隔开。如:1986,8213,1935,2736,3299;
(4)界面友好,每步给出适当的操作提示,并且系统具有一定的容错能力。
至少给出下面的测试数据:
(1)0; 0
(2)-2345,6789; -7654,3211
(3)-9999,9999; 1,0000,0000,0000
(4)1,0001,0001; -1,0001,0001
(5)1,0001,0001; -1,0001,0000
(6)-9999,9999,9999; -9999,9999,9999
(7)1,0000,9999,9999; 1
1需求分析
1、运算时数值可以包含加“+”减“-”号,并且4位数使用“,”分隔,在存储过程的时候使用一个符号(CHAR类型)存入并将“,”忽略掉,不存储在链表中的节点中。
2、因为需要多次循环判断处理,所以我们使用双循环链表存储数值,方便计算,。
4、运算符号的判断使用单独输入,用于进行运算。
5、输出的结果“+”“—”正负号在链表外边运行,数据输出使用链表遍历的方式一边运行一边输出。
6、开发语言以及运行环境:C++ V
数据结构课程设计的目标是实现一个能够处理任意长度整数加法和减法的程序,采用链表作为数据结构。在这个项目中,链表的每个节点包含一个整型变量,允许存储从-(2^15 -1)到(2^15 -1)的整数。输入和输出的数据格式要求每四位一组,用逗号分隔,如1986,8213,1935,2736,3299。为了确保用户界面友好,程序需要提供清晰的操作提示并具备一定的错误处理能力。
在设计过程中,有以下几个关键点需要注意:
1. **符号处理**:输入的数字可以带有正负号,但符号不存储在链表节点中,而是单独处理。在输入时,程序需识别并存储这些符号。
2. **数据存储**:由于需要进行多次循环和判断,所以选择了双循环链表作为数据结构,这样能更有效地进行计算。
3. **运算符号**:运算符号(加法或减法)由用户单独输入,用于决定运算类型。
4. **输出处理**:输出时,正负号不在链表中处理,而是在遍历链表输出数据时添加。这意味着在显示结果时,需要根据运算结果确定每个数字的正负。
5. **开发环境**:本项目使用C++编程语言,并在Visual Studio 2012环境下运行。
程序设计包括以下几个核心函数:
- **JiaFunction(List &MN1, List &MN2, List &L3)**:这是加法运算函数,接受两个链表MN1和MN2作为输入,将结果存储在L3中。
- **JianFunction(List &MN1, List &MN2, List &L3)**:减法运算函数,功能类似,但执行减法操作。
- **XuanZe(List &A, List &B, List &C, int &n1, int &n2, char &sym1, char &sym2)**:此函数用于判断运算方法,选择加法或减法,以及处理符号。
- **Print(List &L)**:输出结果的函数,遍历链表L并打印其中的元素。
- **Compare(List &MN1, List &MN2, int &mn1, int &mn2)**:比较两个链表中的元素,可能用于比较大小或者计算绝对值。
- **ChuangJian(List &L, int &n)**:创建双向循环链表的函数,从用户输入中读取数据并构建链表。
在详细设计阶段,程序需要包含必要的输入验证,确保输入的数字符合指定格式。例如,它需要能够正确处理像0, -2345,6789这样的测试数据,并在遇到异常输入时给出适当的错误提示。
在实现这些功能时,可能需要使用到的操作包括插入新节点(InsertNumberToTop/InsertNumberToButtom)、链表遍历、比较节点值以及根据符号进行加减运算。此外,还可能涉及到对链表长度的管理,特别是在处理不同长度的数字进行运算时。
为了保证程序的健壮性,应进行充分的测试,覆盖各种边界条件和异常情况,如零值、溢出和无效输入等。测试用例应包括上述的示例数据以及其他可能的输入组合,以验证程序的正确性和效率。