一、实验目的
掌握线性表的顺序存储结构的存储特点与操作特点。
掌握顺序表的存储表示与基本操作的实现方法。
熟悉顺序表的基本应用。
了解抽象数据类型的定义、表示与实现的含义。
二、预备知识
阅读课程教材P18~21页内容，熟悉抽象数据类型线性表的定义，了解各基本操作的功能含义。学习范例2-1，体会如何使用线性表提供的基本操作解决更复杂问题的方法。
阅读课程教材P21~26页内容，熟悉线性表的顺序存储结构的存储特点，了解顺序表的随机存取的操作特点。理解顺序表的存储表示方法，掌握顺序表各种基本操作
（InitList_Sq，GetElem_Sq，ListInsert_Sq，ListDelete_Sq，LocatElem_Sq等）的实现方法。
三、实验内容(不要直接复制有防抄袭代码23333)
按如下要求编写程序，进行调试，写出调试正确的源代码，给出测试结果。
实现线性表在顺序存储结构下的存储表示和基本操作，并应用抽象数据类型线性表完成如下操作：
#include<iostream> #include<cstdlib> using namespace std; #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int *elem; int length;//当前长度 int listsize;//初始容量 }SqList; class my_SqList { private: SqList l; public: int*get_elem() { return l.elem; } int get_length() { return l.length; } int get_listsize() { return l.listsize; } void InitList_Sq() {//创建一个空的顺序表 l.elem = (int *)malloc(sizeof(int)*LIST_INIT_SIZE);//创建100个单位。 if (!l.elem) { printf("创建失败，退出程序\n"); return; } l.length = 0; l.listsize = LIST_INIT_SIZE; printf("创建成功\n"); } void ListInsert(int e) {//把e插入顺序表中默认插入最后 if (l.length >= l.listsize) { int *newelem; printf("空间已满，扩容\n"); newelem = (int *)realloc(l.elem, (l.listsize + LISTINCREMENT) * sizeof(int));//realloc(首地址，长度) if (!newelem) { printf("扩容失败，退出程序\n"); return; } l.elem = newelem; l.listsize += LISTINCREMENT; } l.elem[l.length++] = e; printf("%d插入表尾成功\n", e); } void OutpotList() {//输出类容 int i; for (i = 0; i < l.length; i++) { printf("%d\t", l.elem[i]); } printf("\n"); } void Hebing(my_SqList &L2) {//吧L2合并到L1中 while (L2.get_length() > l.listsize - l.length - 1) {//L1不能装下L2 printf("L1不能装下L2，扩容中....\n"); int *newelem = (int *)realloc(l.elem, (l.listsize + LISTINCREMENT) * sizeof(int));//realloc(首地址，长度) if (!newelem) { printf("扩容失败，退出程序\n"); return; } l.elem = newelem; l.listsize += LISTINCREMENT; } int i = 0; while (i < L2.get_length()) { l.elem[l.length++] = L2.get_elem()[i++]; } }; void Sub_L1_L2(my_SqList &L2) {//L1=L1-L2 int i, j, k; for (i = 0; i < L2.get_length(); i++) {//L2的遍历 for (j = 0; j < l.length; j++) { if (L2.get_elem()[i] == l.elem[j]) { for (k = j; k < l.length; k++) { l.elem[k] = l.elem[k + 1]; l.length--; } j--; } } } } }; int main() { my_SqList L1, L2; /************分别创建两个空的线性表L1、L2；*****************/ L1.InitList_Sq(); L2.InitList_Sq(); L1.OutpotList(); L2.OutpotList(); /**************分别将若干元素插入到L1、L2中，输出操作后表L1和L2的内容************/ //向L1中插入数据 int n, e; cout << "请输入插入L1数据的个数:"; cin >> n; cout << "请输入数据用空格隔开\n"; for (int i = 0; i < n; i++) { scanf("%d", &e); L1.ListInsert(e); } cout << "请输入插入L1数据的个数:"; cin >> n; cout << "请输入数据用空格隔开\n"; for (int i = 0; i < n; i++) { scanf("%d", &e); L2.ListInsert(e); } //输出L1,输出L2 cout << "L1的内容:"; L1.OutpotList(); cout << "L2的内容:"; L2.OutpotList(); /**实现两表的合并操作：L1=L1∪L2，输出合并后表L1的内容。**************************************/ L1.Hebing(L2); cout << "插入后L1的内容:"; L1.OutpotList(); /******* 实现两表的求差操作：L1=L1-L2，输出求差后表L1的内容。**********************************************/ L1.Sub_L1_L2(L2); cout << "求差后L1的内容:"; L1.OutpotList(); system("pause"); return 0; }
