数据结构顺序表实验报告
引言
数据结构是计算机科学中最为基础的课程之一，也是理论与实践相结合的课程。顺序表（Sequence List）是一种存储数据元素的线性表结构，它是采用一组连续的存储单元来存储数据的，具有结构简单，利于在存储空间上进行分配和利用等特点。在本次实验中，我将对顺序表的构建、插入、删除等操作进行详细研究和分析。
实验目的
本次实验的主要目的是熟悉顺序表的定义和基本操作，并能在程序中加以实现。在实验过程中，通过编写相关程序，掌握数据结构中顺序表操作和设计方式，并加深对算法设计的理解。
实验原理
顺序表是一种典型的线性表结构，其特点是数据元素存储在一块连续的存储区内，可以直接进行随机访问。数据元素之间的关系是一对一的关系，即线性关系。顺序表图形化表示如下：
顺序表实际上是一个一维的数组，在使用前需要定义数组的长度，以便于在程序中开辟一块合适的内存块存储数据。
主要操作
（1）顺序表的构建
顺序表的构建是首先需要完成的任务。通常情况下，我们需要事先给出顺序表的长度，才能依据此长度创建一块连续的内存空间。常用的代码如下：
```
#定义顺序表的长度
MAXSIZE = 100
#顺序表的构建
def InitList(lst):
lst = [0] * MAXSIZE
length = 0
return lst, length
#主函数
if __name__ == '__main__':
lst, length = InitList(lst)
```
（2）顺序表的插入
顺序表的插入操作是指在表的任意位置上加入一个新的元素。这里我将分为两种情况进行详述：
①在第i个位置前插入元素
假设当前表长度为n，需要在第i个位置前插入元素，即需要将第i个位置及其后的所有元素都往后移动一位，并将待插入元素存放至第i个位置上。常用的代码如下：
```
#在第i个位置前插入元素
def ListInsert(lst, i, new_elem):
#判断i是否合法
if i < 1 or i > MAXSIZE:
print("该位置不合法")
return False
#判断是否表满
if len(lst) == MAXSIZE:
print("表满")
return False
#移动元素，为新元素腾出位置
for j in range(length, i-1, -1):
lst[j] = lst[j-1]
#插入新元素
lst[i-1] = new_elem
#长度+1
length += 1
return True
#主函数
if __name__ == '__main__':
lst, length = InitList(lst)
#在第2个位置前插入元素30
res = ListInsert(lst, 2, 30)
```
（3）顺序表的删除
顺序表的删除操作是指删除表中任意位置的元素。假设当前表长度为n，需要在第i个位置删除元素，即需要将第i+1个位置及其后的所有元素都往前移动一位。常用的代码如下：
```
#删除表中第i个元素
def ListDelete(lst, i):
if i < 1 or i > length:
print("该位置不合法")
return False
#将第i+1个位置及后面的元素前移
for j in range(i, length):
lst[j-1] = lst[j]
#长度-1
length -= 1
return True
#主函数
if __name__ == '__main__':
lst, length = InitList(lst)
#删除第2个位置的元素
res = ListDelete(lst, 2)
```
实验结果与分析
经过以上操作，我们已经成功地实现了顺序表的构建、插入和删除操作。可以得出以下结论：
①通过本次实验，我掌握了数据结构中顺序表的设计和实现方法，增强了对数据结构的理解。
②顺序表经常用于程序编写，是数据结构常用的基础。
③顺序表对于按下标存取元素的操作，时间复杂度较低，仅为O(1)，效率较高。
