华南农大数据结构实验：顺序线性表操作详解及STL应用

本资源是一份华南农业大学数据结构实验的答案文档，专注于顺序线性表（SqList）的基础操作，包括结构定义、初始化、插入、删除和遍历功能的实现。顺序线性表是一种简单但基础的数据结构，它将数据元素按照一定的顺序存储，每个元素可以通过索引访问。 首先，我们来看结构定义： ```cpp typedef struct { int* elem; // 存储元素的指针数组 int length; // 当前列表的元素数量 int listsize; // 初始分配的数组大小 } SqList; ``` 在这个结构中，`elem` 是一个指向整型元素的指针数组，`length` 用于记录当前元素的实际数量，而 `listsize` 则是预先设定的存储空间大小。 接下来是关键的函数实现： 1. 初始化函数 InitList_Sq: 该函数用于构造一个空的顺序线性表，初始大小为 `LIST_INIT_SIZE`。代码可能如下： ```cpp int InitList_Sq(SqList& L) { L.elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int)); // 分配初始内存 if (L.elem == NULL) { return ERROR; // 内存分配失败 } L.length = 0; L.listsize = LIST_INIT_SIZE; return OK1; // 初始化成功 } ``` 2. 遍历与打印函数 Load_Sq: 这个函数用于输出顺序表中的所有元素。如果列表为空，会输出"TheListisEmpty!"。遍历过程应使用索引访问 `elem` 数组： ```cpp int Load_Sq(SqList& L) { if (L.length == 0) { // 判断列表是否为空 printf("TheListisEmpty!\n"); } else { printf("TheListis:\n"); for (int i = 0; i < L.length; i++) { // 遍历并打印元素 printf("%d ", L.elem[i]); } printf("\n"); } return OK; } ``` 3. 插入函数 ListInsert_Sq: 在指定位置 `i` 前插入元素 `e`，需要检查 `i` 的合法性并更新 `length` 和 `elem`。例如： ```cpp int ListInsert_Sq(SqList& L, int i, int e) { if (i > L.length + 1) { return ERROR; // 插入位置超出范围 } if (L.length == L.listsize) { // 列表满，需要扩展空间 L.elem = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int)); if (L.elem == NULL) { return ERROR; } L.listsize += LISTINCREMENT; } for (int j = L.length; j > i; j--) { // 移动元素 L.elem[j] = L.elem[j - 1]; } L.elem[i] = e; L.length++; return OK; } ``` 4. 删除函数 ListDelete_Sq: 删除指定位置的元素，并将值保存到 `e`，同时更新 `length` 和可能移动后续元素： ```cpp int ListDelete_Sq(SqList& L, int i, int& e) { if (i > L.length) { return ERROR; // 删除位置超出范围 } e = L.elem[i]; // 获取待删除元素 for (int j = i; j < L.length - 1; j++) { // 移动后续元素 L.elem[j] = L.elem[j + 1]; } L.length--; // 减少长度 if (L.length == L.listsize / 2 && L.listsize > LIST_INIT_SIZE) { // 如果超过一半空间未用，缩小数组 L.elem = (int*)realloc(L.elem, L.listsize / 2 * sizeof(int)); if (L.elem == NULL) { return ERROR; } L.listsize /= 2; } return OK; } ``` 最后，`main` 函数用于创建顺序线性表并进行基本操作的交互式执行。用户可以选择插入、删除或加载所有元素。 整个文档提供的代码片段展示了如何在C++中实现顺序线性表的基本操作，这对于理解数据结构和算法的应用具有实际意义，尤其是在解决编程题目的时候，能够帮助学生熟悉数据结构的实现细节和优化技巧。