数据结构实验报告
专业班姓名 学号 级 实验地指导教师 实验时间 11月3日 点
计算中心 实验一 顺序表实验
1. 实验目标
① 熟练掌握线性表的顺序存储结构。 ② 熟练掌握顺序表的有关算法设计。
③ 根据具体问题的需要，设计出合理的表示数据的顺序结构，并设计相关算法。
2. 实验内容和要求 Ⅰ.实验要求
① 顺序表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；比如存储、算法实现放入文件：seqList.h
② 实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求； ③ 程序有适当的注释。
Ⅱ.实验内容
<1>求顺序表中第i个元素（函数），若不存在，报错。 <2>在第i个结点前插入值为x的结点
<3>删除顺序表中第i个元素结点
<4>在一个递增有序的顺序表L中插入一个值为x的元素，并保持其递增有序特性
<5>将顺序表Ｌ中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的顺序表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果
<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的子集
L/2?? <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. 数据结构设计
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 data[MAXLEN];//存放表元素的数组 int listLen;//记录表中的元素个数 }; 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]
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，2，3，4，5，6，7，8，9 ② I=5 <2>在第i个结点前插入值为x的结点。