合工大宣城校区数据结构实验报告顺序表.docx
- 文档编号:14227837
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:9
- 大小:126.94KB
合工大宣城校区数据结构实验报告顺序表.docx
《合工大宣城校区数据结构实验报告顺序表.docx》由会员分享,可在线阅读,更多相关《合工大宣城校区数据结构实验报告顺序表.docx(9页珍藏版)》请在冰点文库上搜索。
合工大宣城校区数据结构实验报告顺序表
数据结构实验报告
学号
专业班级
指导教师
实验时间
11月3日
实验地点
计算中心
实验一顺序表实验
1.实验目标
1熟练掌握线性表的顺序存储结构。
2熟练掌握顺序表的有关算法设计。
3根据具体问题的需要,设计出合理的表示数据的顺序结构,并设计相关算法。
2.实验容和要求
Ⅰ.实验要求
1顺序表结构和运算定义,算法的实现以库文件方式实现,不得在测试主程序中直接实现;比如存储、算法实现放入文件:
seqList.h
2实验程序有较好可读性,各运算和变量的命名直观易懂,符合软件工程要求;
3程序有适当的注释。
Ⅱ.实验容
<1>求顺序表中第i个元素(函数),若不存在,报错。
<2>在第i个结点前插入值为x的结点
<3>删除顺序表中第i个元素结点
<4>在一个递增有序的顺序表L中插入一个值为x的元素,并保持其递增有序特性
<5>将顺序表L中的奇数项和偶数项结点分解开(元素值为奇数、偶数),分别放入新的顺序表中,然后原表和新表元素同时输出到屏幕上,以便对照求解结果
<6>求两个递增有序顺序表L1和L2中的公共元素,放入新的顺序表L3中
<7>删除递增有序顺序表中的重复元素,并统计移动元素次数,要求时间性能最好
扩展实验:
<1>递增有序顺序表L1、L2,对2表进行合并,并使得合并后成为一个集合,集合的元素放回L1表中保存,要求时间性能最好
<2>(递增有序)顺序表表示集合A、B,实现:
C=A⋂B,C=A⋃B,C=A-B
A=A⋂B,A=A⋃B,A=A-B
<3>(递增有序)顺序表表示集合A、B,判定A是否B的子集
<4>(2011)(15分)一个长度为L(L≥1)的升序序列S,处在第个位置的数称为S的中位数。
例如,若序列S1=(11,13,15,17,19),则S1的中位数是15。
两个序列的中位数是含它们所有元素的升序序列的中位数。
例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11。
现有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数
3.数据结构设计
typedefintelementType;
classseqList
{
public:
seqList();//初始化空表
intLength();//求表长度(元素个数)
intInput(intx);//写入数据
boolgetElement(inti,elementType&x);//取表元素
intlocate(elementTypex);//定位元素位置
intlistInsert(inti,elementTypex);//在第i个结点前插入值为x的结点
intlistDelete(inti);//删除顺序表中第i个元素
intseek(inti);//查找第i个元素
elementTypedata[MAXLEN];//存放表元素的数组
intlistLen;//记录表中的元素个数
};
4.算法设计
<1>、<2>、<3>为基本算法,
<4>.自后向前,如果找到比该值小的元素值,则插入当前位置,否则就让当前值往后一一位,再判断下一个值。
<5>.定义两个顺序表M,N,依次判断表中个元素,如果data[i]%2==1,则将该值输入M中,否则则输入N中,M储存奇数结点,N储存偶数结点
<6>.创建表L3,如果L1.data[ia]>L2.data[ib],则ib++,如果L1.data[ia] <7>.将元素分为两部分,一部分是已经处理元素,和待处理元素。 已处理部分返回L中,用下标i表示,待处理第一个元素用j表示,如果L.data[i]==L.data[j],则处理j下一个元素,j++;如果L.data[i] 扩展实验: <1>.对L1与L2中元素进行判断,将L2中元素插入到L1中对应位置,并保证递增有序性不变。 <2>.对于采用C的运算,将符合要求的元素插入到C中,对于不采用C的运算,就对A中元素进行插入与删除操作。 <3>.对A中元素按顺序进行判断,如果出现A.data[ia] <4>.因为两个序列A和B等长升序,故只需按照递增有序的顺序找到第A.listLen的yuansu即可,可以对A,B元素进行排序,到第A.listLen结束即可输出该值为中位数。 5.运行和测试 <1>求顺序表中第i个元素(函数),若不存在,报错。 第一组数据: 顺序表长度n≥10,i分别为5,n,0,n+1,n+2 1输入顺序表1,2,3,4,5,6,7,8,9 2I=5 <2>在第i个结点前插入值为x的结点。 <3>删除顺序表中第i个元素结点。 <4>在一个递增有序的顺序表L中插入一个值为x的元素,并保持其递增有序特性。 顺序表元素为(10,20,30,40,50,60,70,80,90,100), x分别为25,85,110和8 <5>将顺序表L中的奇数项和偶数项结点分解开(元素值为奇数、偶数),分别放入新的顺序表中,然后原表和新表元素同时输出到屏幕上,以便对照求解结果。 第一组数据: 顺序表元素为(1,2,3,4,5,6,7,8,9,10,20,30,40,50,60) <6>求两个递增有序顺序表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) <7>删除递增有序顺序表中的重复元素,并统计移动元素次数,要求时间性能最好。 第二组数据: 顺序表元素为(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,9) 扩展实验: <1>.递增有序顺序表L1、L2,对2表进行合并,并使得合并后成为一个集合,集合的元素放回L1表中保存 <2>(递增有序)顺序表表示集合A、B,实现运算。 <3>(递增有序)顺序表表示集合A、B,判定A是否B的子集 <4>. 6.总结和心得 在程序编写的过程中,由于对程序设计的不全面,导致出现了许多问题,诸如输出的缺少,程序的停止位置,输入容的错误等等。 这给了我不少经验教训,也让我认识到自己的不足,下面总结一下编写过程中的一些问题。 1.在扩展实验一中,插入时输入为元素位置而非元素序号,导致出现错误输出,通过将ia变为ia+1,使其插入在正确位置。 2.在扩展实验二中,在进行A=A⋂B,A=A⋃B,A=A-B操作时直接传地址,导致A容变化,之后改为传值解决。 3.在重复使用函数时,其部定义的顺序表在输出第二次的结果时会将上一次的结果也同时输出,造成输出的容有误。 通过在函数调用前将存储结构初始化重置,解决这一问题。 4.初始时设计不合理,导致出现后期输出时重复输出多次结果,之后通过设计统一的调用函数解决。 5.在输入数据的时候如果输入非递增有序,程序会继续运行并依旧将错误数据输出,最后通过设计一个judge函数进行判断是否递增有序解决。 [7.附录] (源代码清单。 纸质报告不做要求。 电子报告,可直接附源文件,删除编译生成的所有文件)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 合工大 宣城 校区 数据结构 实验 报告 顺序