1． 利用本次实验提供的文件（listinarray.h、listinarray.cpp、content.cpp），创建并观察项目，回答下面问题。
文件说明： 【listinarray.h】顺序表的类型声明和操作接口声明 【listinarray.cpp】顺序表的操作实现代码
【content.cpp】顺序表应用程序（main函数）
(1) 程序如何定义顺序表的抽象数据类型？
答：程序使用数组定义顺序表的抽象数据类型的集合和关系，数组元素的插入、删除、查询等操作作为运算。
(2) 找出程序中定义顺序表抽象数据类型中的数据结构的代码？
typedef struct {
ElemType data[MaxSize];
int length;
} SqList;
(3) 找出程序中定义顺序表抽象数据类型中的操作接口的代码？
//初始化空线性表
void InitList(SqList &L);
//判断线性表是否为空
bool ListEmpty(SqList L);
//求出线性表长度
int ListLength(SqList L);
//向线性表指定位置插入一个新元素
bool ListInsert(SqList &L, int pos, ElemType item);
//从线性表中删除第一个与指定值匹配的元素
bool ListDelete(SqList &L, int pos, ElemType &item);
//获取顺序表中指定位置上的数据元素
bool GetElem(SqList L, int pos, ElemType &item);
//从线性表中查找元素，返回第一个与指定值匹配元素位置
int Find(SqList L, ElemType item);
//遍历输出线性表
void TraverseList(SqList L);
//合并线性表
void MergeList(SqList &L1, SqList L2);
//降序合并线性表
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc);
(4) 在头文件中找出顺序表数据元素类型声明的代码，并指出当前程序中的顺序表的数据元素是什么类型的数据？假设在顺序表中保存的数据元素要更改为字符时该如何修改代码？
答：typedef int ElemType; //声明元素类型
顺序表中的数据元素是整型的数据，若要更改为字符类型时，代码可修改为：typedef char ElemType;
(5) 程序中是如何表示顺序表中相邻数据元素的约束关系，即如何确定顺序表中的数据元素的相邻关系？
答：数组的每个元素在计算机的存储空间是依次连续的。
(6) 修改主函数main( )的代码，并按下图输出数据：
"listinarray.h"文件中修改线性表元素类型：
typedef int ElemType;
"content.cpp"文件中修改以下代码：
#include "listinarray.h"
int main()
{
SqList my_List2; //定义线性表SqList类型的变量
ElemType Array[] ={1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1};
for (int i = 1; i <= 20; i++)
ListInsert(my_List2, i, Array[i - 1]);
cout << "my_list2：";
TraverseList(my_List2);
return 0;
}
(7) 修改顺序表的元素类型，输入相应数据，并按下图输出数据：
"listinarray.h"文件中修改线性表元素类型：
typedef int ElemType;
"content.cpp"文件中修改以下代码：
#include "listinarray.h"
int main()
{
SqList my_List2; //定义线性表SqList类型的变量
ElemType Array[] = "student";
InitList(my_List2);
for (int i = 1; i <= 7; i++)
ListInsert(my_List2, i, Array[i - 1]);
cout << "my_list2：";
TraverseList(my_List2);
return 0;
}
2． 重新设计一个主程序完成如下功能：
(1) 初始化顺序表my_list；
(2) 在my_list的头部依次插入’a’, ‘b’, ‘c’, ‘d’, 'e’元素；
(3) 输出my_list的长度及my_list中的元素；
(4) 判断my_list是否为空；
(5) 在my_list第4个位置上插入元素 'f ’ 并输出my_list；
(6) 删除my_list的第3个元素并输出被删除元素和my_list；
(7) 输出my_list的第2个元素；
(8) 输出元素 ‘b’ 的位置。
#include "listinarray.h"
int main()
{
SqList my_list; //定义线性表SqList类型的变量
ElemType Array[] = {'a','b','c','d','e'};
ElemType b[1] = {};
//1初始化线性表
InitList(my_list);
//2在my_list的头部依次插入a, b, c, d, e元素
for (int i = 1; i <= 5; i++)
ListInsert(my_list, i, Array[i - 1]);
//3输出线性表元素
cout << "my_list长度为：" << ListLength(my_list) << endl;
cout << "my_list元素为：";
//4判断my_list是否为空
TraverseList(my_list);
cout << "my_list是否为空："<< ListEmpty(my_list) << endl;
//5在my_list第4个位置上插入元素f
ListInsert(my_list, 4, 'f');
cout << "my_list第四个位置上插入元素f：";
TraverseList(my_list);
//6删除my_list的第3个元素
ListDelete(my_list, 3, b[0]);
cout << "被删除的元素："<<b[0]<<endl;
cout << "删除元素后的my_list：";
TraverseList(my_list);
//7输出my_list的第二个元素
GetElem(my_list, 2, b[1]);
cout << "my_list的第2个元素：" << b[1] << endl;
//8输出元素’b’的位置
cout << "my_list的'b'的位置：" << Find(my_list,'b') << endl;
return 0;
}
3． 设计顺序表的接口函数void MergeList(SqList &L1 , SqList L2); 把顺序表L2中的数据全部合并到顺序表L1的尾部。如下所示：L1中有数据{1,2,3,4,5}，L2中有数据 {6,7,8,9,10}；合并的结果为L1中包含数据 {1,2,3,4,5, 6,7,8,9,10}。运行结果如下图所示。
// ①(ListInArray.h)文件中添加
//合并线性表L2到线性表L1尾部
void MergList(SqList &L1 ,SqList L2);
//修改线性表元素类型ElemType
typedef int ElemType;
// ②(ListInArray.cpp)文件中添加
//合并线性表L2到线性表L1尾部
void MergList(SqList &L1 ,SqList L2)
{
ElemType t;
for(int i=1;i<= ListLength(L2);i++)
{
GetElem(L2, i, t);
ListInsert(L1, ListLength(L1)+1, t);
}
}
// ③(content.cpp)文件中
#include "listInarray.h"
int main()
{
SqList my_List1,my_List2;
InitList(my_List1);
InitList(my_List2);
for(int i=1;i<=5;i++)
{
ListInsert(my_List1, i, i);
ListInsert(my_List2, i, i+5);
}
cout<<"线性表my_List1中有数据："<<endl;
TraverseList(my_List1);
cout<<"线性表my_List2中有数据："<<endl;
TraverseList(my_List2);
MergList(my_List1, my_List2);
cout<<"合并后的线性表my_List1中有数据："<<endl;
TraverseList(my_List1);
return 0;
}
思考题：
已知顺序表 La 、 Lb中的元素按非递减顺序排列。请思考并设计一个函数 void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) ，把La和Lb中的元素合并到一个顺序表Lc，使Lc中的元素也保持非递减顺序排列。
如： La={2,4,7,9} Lb={3,5,7,10,12}
合并后： Lc={2,3,4,5,7,7,9,10,12}
ListInArray.h:
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc);
ListInArray.cpp:
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
{
ElemType a,b;
int i=1,j=1;
while(i<= ListLength(La) && j<= ListLength(Lb))
{
GetElem(La, i, a);
GetElem(Lb, j, b);
if(a<=b)
{
ListInsert(Lc, ListLength(Lc)+1, a);
i++;
}
else
{
ListInsert(Lc, ListLength(Lc)+1, b);
j++;
}
}
while(i<= ListLength(La))
{
GetElem(La, i, a);
ListInsert(Lc, ListLength(Lc)+1, a);
i++;
}
while(j<= ListLength(Lb))
{
GetElem(Lb, j, b);
ListInsert(Lc, ListLength(Lc)+1, b);
j++;
}
}
content.cpp:
int main()
{
SqList La,Lb,Lc;//定义线标表SqList类型的变量
ElemType a[]={2,4,7,9};
ElemType b[]={3,5,7,10,12};
//初始化线性表
InitList(La);
InitList(Lb);
InitList(Lc);
//向线性表的指定位置插入数据
for(int i=1; i<=sizeof(a)/sizeof(a[0]); i++)
ListInsert(La, i, a[i-1]);
for(int j=1; j<=sizeof(b)/sizeof(b[0]); j++)
ListInsert(Lb, j, b[j-1]);
//输出线性表元素
cout<<"La：";
TraverseList(La);
cout<<"Lb：";
TraverseList(Lb);
cout<<"有序合并后："<<endl;
MergeList_Sq(La,Lb,Lc);
cout<<"Lc：";
TraverseList(Lc);
return 0;
}