合工大宣城校区数据结构实验报告-顺序表.doc

数据结构实验报告姓名学号专业班级指导教师实验时间11月3日实验地点计算中心实验一 顺序表实验1. 实验目标 熟练掌握线性表的顺序存储结构。 熟练掌握顺序表的有关算法设计。 根据具体问题的需要，设计出合理的表示数据的顺序结构，并设计相关算法。2. 实验内容和要求.实验要求 顺序表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；比如存储、算法实现放入文件：seqList.h 实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求； 程序有适当的注释。.实验内容求顺序表中第i个元素（函数），若不存在，报错。在第i个结点前插入值为x的结点删除顺序表中第i个元素结点在一个递增有序的顺序表L中插入一个值为x的元素，并保持其递增有序特性将顺序表中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的顺序表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果求两个递增有序顺序表L1和L2中的公共元素，放入新的顺序表L3中删除递增有序顺序表中的重复元素，并统计移动元素次数，要求时间性能最好扩展实验： 递增有序顺序表L1、L2，对2表进行合并，并使得合并后成为一个集合，集合的元素放回L1表中保存，要求时间性能最好（递增有序）顺序表表示集合A、B，实现：C=AB，C=AB，C=A-BA=AB，A=AB，A=A-B（递增有序）顺序表表示集合A、B，判定A是否B的子集(2011)（15 分）一个长度为L（L1）的升序序列S，处在第 个位置的数称为S 的中位数。例如，若序列S1=(11, 13, 15, 17, 19)，则S1 的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2, 4, 6, 8, 20)，则S1 和S2 的中位数是11。 现有两个等长升序序列A 和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数3. 数据结构设计typedef int elementType;class seqList public: seqList();/初始化空表 int Length();/求表长度（元素个数） int Input (int x);/写入数据 bool getElement(int i,elementType &x);/取表元素 int locate(elementType x);/定位元素位置 int listInsert(int i,elementType x);/在第i个结点前插入值为x的结点 int listDelete(int i);/删除顺序表中第i个元素 int seek(int i);/查找第i个元素 elementType dataMAXLEN;/存放表元素的数组 int listLen;/记录表中的元素个数;4. 算法设计、为基本算法，.自后向前，如果找到比该值小的元素值，则插入当前位置，否则就让当前值往后一一位，再判断下一个值。.定义两个顺序表M，N，依次判断表中个元素，如果datai%2=1，则将该值输入M中，否则则输入N中，M储存奇数结点，N储存偶数结点.创建表L3，如果L1.dataiaL2.dataib，则ib+， 如果L1.dataiaL2.dataib，则ia+ ,否则，就将相同元素加入L3中。.将元素分为两部分，一部分是已经处理元素，和待处理元素。已处理部分返回L中，用下标i表示，待处理第一个元素用j表示，如果L.datai=L.dataj，则处理j下一个元素，j+；如果L.dataiL.dataj，令L.datai+1=L.dataj，j+，i+，直至表尾，令表长度为i+1.扩展实验：.对L1与L2中元素进行判断，将L2中元素插入到L1中对应位置，并保证递增有序性不变。.对于采用C的运算，将符合要求的元素插入到C中，对于不采用C的运算，就对A中元素进行插入与删除操作。.对A中元素按顺序进行判断，如果出现A.dataiaB.dataib，则表示A不为B的子集，如果对A中每个元素进行判断，均可在B中找到，则A为B的子集。.因为两个序列A 和B等长升序，故只需按照递增有序的顺序找到第A.listLen的yuansu即可，可以对A，B元素进行排序，到第A.listLen结束即可输出该值为中位数。5. 运行和测试求顺序表中第i个元素（函数），若不存在，报错。第一组数据：顺序表长度n10，i分别为5，n，0，n+1，n+2 输入顺序表1，2，3，4，5，6，7，8，9 I=5在第i个结点前插入值为x的结点。删除顺序表中第i个元素结点。在一个递增有序的顺序表L中插入一个值为x的元素，并保持其递增有序特性。顺序表元素为 （10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8将顺序表中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的顺序表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果。第一组数据：顺序表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）求两个递增有序顺序表L1和L2中的公共元素，放入新的顺序表L3中。第一个顺序表元素为 （1，3，6，10，15，16，17，18，19，20）第二个顺序表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30）删除递增有序顺序表中的重复元素，并统计移动元素次数，要求时间性能最好。第二组数据：顺序表元素为 （1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,9）扩展实验：.递增有序顺序表L1、L2，对2表进行合并，并使得合并后成为一个集合，集合的元素放回L1表中保存（递增有序）顺序表表示集合A、B，实现运算。（递增有序）顺序表表示集合A、B，判定A是否B的子集.6. 总结和心得在程序编写的过程中，由于对程序设计的不全面，导致出现了许多问题，诸如输出的缺少，程序的停止位置，输入内容的错误等等。这给了我不少经验教训，也让我认识到自己的不足，下面总结一下编写过程中的一些问题。1. 在扩展实验一中，插入时输入为元素位置而非元素序号，导致出现错误输出，通过将ia变为ia+1，使其插入在正确位置。2. 在扩展实验二中，在进行A=AB，A=AB，A=A-B操作时直接传地址，导致A内容变化，之后改为传值解决。3. 在重复使用函数时，其内部定义的顺序表在输出第二次的结果时会将上一次的结果也同时输出，造成输出的内容有误。通过在函数调用前将存储结构初始化重置，解决这一问题。4. 初始时设计不合理，导致出现