华中科技大学计算机学院数据结构实验报告
1.2.3 运算算法思想与设计
线性表运算算法思想与设计如下：
1. 初始化线性表思想：将线性表初始化过程写成函数，其中传入函数的参数是主函数中定义的结构型变量L的引用，在函数中，首先使用malloc函数分配LISTSIZE大小的连续内存空间，并将首地址返回赋值给L.elem，由于线性表的长度为0，将L.length初始化为0，即完成了线性表的初始化。经分析，算法的时间复杂度为O(1)。
2. 销毁线性表思想：将销毁线性表的过程写成函数，其中传入函数是主函数中定义的结构性变量L。在函数中，首先使用free函数释放掉以L.elem为首地址的连续内存空间，再将L.length,L.listsize重新赋值为0。 经分析，该算法的时间复杂度为O(1)。
3. 清空线性表的思想：将清空表的过程写成函数，其中将主函数中定义的结构性变量L的引用作为函数参数，在函数中，由于清空操作并不释放内存空间，故只需将线性表的长度置为0即可。经分许，该算法的时间复杂度为O(1)。
4. 求线性表表长的思想：将求表长过程写成函数，其中主函数中定义的结构性变量L的引用作为函数的参数，在函数中，直接返回L.length即为所求线性表的表长。经分析，该算法的时间复杂度为O（1）。
5. 获得元素的算法思想：将获得线性表元素写成函数，其中函数的参数是结构型变量L以及数据元素的序号i，由于采取的是线性存储结构，故直接通过访问数组的方式即L.elem[i-1]来获取元素，当然，在这之前需要
4
华中科技大学计算机学院数据结构实验报告
判断合法性。经分析，该算法的时间复杂度为O（1）。
6. 查找元素的算法思想：将查找线性表特定值的数据元素写成函数，其中函数的参数是主函数中定义的结构类型变量L以及查找的数据元素的值，通过循环对线性表中的每一个元素与给定值比较看是否相等，如果相等就返回该元素的次序。经分析，该算法的时间复杂度为O（n）。查找算法的流程图如图1-2所示。
图1-2线性表查找算法流程图
7. 获得前驱算法思想：将获得前驱过程写成函数，函数的参数是结构体类型变量以及特定数据元素的值，接受前驱的变量作为另一个参数，首先调用获得元素的函数判断该线性表中特定数据元素的位序，首先判断不为1，否则的话返回FALSE，然后直接返回其前一个元素即L.elem[j-2]。经分析，该算法的时间复杂度为O（n）。
8. 获得后继算法思想：将获得后继写成函数，函数的参数是结构体类型变量以及特定数据元素的值。首先判断是否为最后一个元素，如果不是则直接返回其后一个元素，否则的话返回FALSE，同样该算法需要调用获得元素的函数来确定该特定元素在线性表中的次序。经分析，该算法的时间复杂度为O（n）。
9. 插入元素算法思想：将插入函数写成函数，函数的参数是结构型变量以及插入元素的值大小以及插入位置。在函数中，首先判断插入位置的合
5
华中科技大学计算机学院数据结构实验报告
法性，即是否在线性表中合适的位置，其次还要判断当前存储空间是否已满，如果满了的话要malloc函数重新分配空间，插入元素时从该位置起到最后一个元素从后开始以此往后移一个单元。经分析，该算法的时间复杂度为O（n）。该算法的程序流程图如图1-3所示。
图1-3线性表中插入元素算法流程图
10. 删除元素算法思想：将删除线性表中元素写成函数，函数的参数是结构类型变量，首先判断位序的合法性，在之后直接将删除元素位置后一个元素直到最后一个元素以此从前往后向前移动一个单元。经分析，该算法的时间复杂度为O（n）。
11. 遍历线性表算法思想：将遍历线性表写成一个函数，函数的参数是结构
6
华中科技大学计算机学院数据结构实验报告
类型变量，直接用一个循环来对线性表中的每一个元素进行操作。经分析，该算法的时间复杂度为O(n)。
1.3系统实现
1.3.1 编程环境、运行环境、项目工程描述
本次实验采用Microsoft Visual Studio 2015编程软件编写，并用VS2015进行编译运行，项目名称是linear datastructer。 1.3.2 头文件及预定义常量说明 1.头文件
#include
2.预定义常量 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0
#define INFEASTABLE -1 #define OVERFLOW -2
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10
3.类型表达式 typedef int status; typedef int ElemType;
1.3.3系统演示操作
1.系统一开始会显示菜单提示用户输入选择对1-99号线性表哪一个进行操作。如图1-4所示。
7
华中科技大学计算机学院数据结构实验报告
图1-4系统演示1
2.选择对线性表1进行操作，进入菜单演示界面，如图1-5所示。
图1-5系统演示2
3.选择退出0，此时会退出当前演示界面，即退出对当前线性表的操作，并显示要求用户选择对哪一个线性表进行操作。如图1-6所示。
8