数据结构顺序表实验报告

引言

数据结构是计算机科学中最为基础的课程之一，也是理论与实践相结合的课程。顺序表（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)，效率较高。