存储结构 实验报告

存储结构实验报告

一、实验目的

本次实验旨在深入理解不同存储结构的特点、操作方式以及它们在数据处理中的性能表现，通过实际操作对比数组、链表等存储结构，掌握其适用场景和优缺点，为后续数据结构和算法的学习与应用奠定基础。

二、实验环境

编程语言：Python 3.8

开发工具：PyCharm 2021.3

硬件环境：Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz，16GB 内存，512GB 固态硬盘

三、实验内容与步骤

（一）数组存储结构实验

1、创建数组

使用 Python 列表来模拟数组，初始化一个包含 10 个整数的数组arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。

2、数组元素访问

随机访问数组中的元素，例如访问第 5 个元素print(arr[4])，输出结果为 5，时间复杂度为 O(1)。

遍历数组元素，使用for 循环for i in range(len(arr)): print(arr[i])，依次输出数组中的每个元素，时间复杂度为 O(n)。

3、数组元素插入

在数组末尾插入元素，如arr.append(11)，此时数组变为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]，平均时间复杂度为 O(1)。

在数组中间插入元素，如在索引 3 处插入元素 99，arr.insert(3, 99)，数组变为[1, 2, 3, 99, 4, 5, 6, 7, 8, 9, 10, 11]，时间复杂度为 O(n)。

4、数组元素删除

删除数组末尾元素，arr.pop()，删除后数组为[1, 2, 3, 99, 4, 5, 6, 7, 8, 9, 10]，时间复杂度为 O(1)。

删除数组中间元素，如删除索引为 3 的元素，del arr[3]，数组变为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，时间复杂度为 O(n)。

（二）链表存储结构实验

1、定义链表节点类

创建一个名为Node 的类，包含数据域data 和指针域next，代码如下：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

2、创建链表及初始化

定义链表类LinkedList，包含头节点head，初始化为None。

编写方法append(data) 用于在链表末尾添加节点，代码如下：

class LinkedList:
    def __init__(self):
        self.head = None
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

3、链表元素访问

遍历链表输出元素，定义方法display()，代码如下：

def display(self):
    current = self.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")

调用display() 方法，按顺序输出链表中的元素，时间复杂度为 O(n)。

4、链表元素插入

在链表头部插入元素，修改append() 方法为insert_at_beginning(data)，代码如下：

def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

在链表指定位置插入元素，定义方法insert_after_node(prev_node, data)，代码如下：

def insert_after_node(self, prev_node, data):
    if not prev_node:
        print("Previous node does not exist.")
        return
    new_node = Node(data)
    new_node.next = prev_node.next
    prev_node.next = new_node

5、链表元素删除

删除链表头部元素，定义方法delete_head()，代码如下：

def delete_head(self):
    if self.head is None:
        return
    self.head = self.head.next

删除链表中指定元素，定义方法delete_node(key)，代码如下：

def delete_node(self, key):
    current = self.head
    if current and current.data == key:
        self.head = current.next
        current = None
        return
    prev = None
    while current and current.data != key:
        prev = current
        current = current.next
    if current is None:
        return
    prev.next = current.next
    current = None

四、实验结果分析

存储结构	元素访问平均时间复杂度	元素插入平均时间复杂度	元素删除平均时间复杂度	空间利用率	优点	缺点
数组	O(1)（随机访问） O(n)（遍历）	O(1)（末尾） O(n)（中间）	O(1)（末尾） O(n)（中间）	高（连续存储）	访问速度快（随机访问），支持随机访问	插入和删除元素时可能需要大量元素移动，空间大小固定
链表	O(n)	O(1)（头部） O(n)（中间/末尾）	O(1)（头部） O(n)（中间/末尾）	低（节点分散存储）	插入和删除操作方便灵活，无需大量元素移动	访问元素需要从头开始遍历，空间开销较大（存储指针）

五、实验归纳

通过本次实验，对数组和链表这两种常见的存储结构有了更深入的理解和实践操作经验，数组适合对数据进行快速随机访问的场景，但在插入和删除元素时效率较低；链表则在插入和删除元素方面具有优势，但访问元素相对较慢，在实际的数据结构和算法应用中，需要根据具体问题的需求和特点选择合适的存储结构，以达到最佳的性能和效率。

六、相关问答 FAQs

问题 1：为什么数组在插入和删除元素时可能需要大量元素移动？

答：数组在内存中是连续存储的，当在数组中间插入或删除元素时，为了保证数组元素的连续性，需要将插入点或删除点之后的所有元素都向前或向后移动一位，所以可能需要大量元素移动，而链表是通过指针连接各个节点，插入和删除节点时只需要修改相关节点的指针指向，不需要移动其他元素。

问题 2：链表的头指针和尾指针有什么区别和作用？

答：头指针指向链表的第一个节点，通过头指针可以方便地对链表进行遍历、插入和删除等操作，尤其是在头部插入和删除元素时操作较为简单高效，尾指针指向链表的最后一个节点，有了尾指针后，在进行尾部插入操作时可以直接通过尾指针完成，不需要遍历整个链表找到最后一个节点，提高了尾部插入的效率，在一些应用场景中，同时使用头指针和尾指针可以更方便地对链表进行操作和管理。

小编有话说

本次存储结构实验让我们清晰地看到不同存储结构的特性差异，就像不同的工具有不同的用途一样，数组和链表在数据处理的“工具箱”里各有其独特的地位，希望大家通过这次实验，不仅能掌握它们的操作方法，更能在面对实际问题时，迅速判断并选择最合适的存储结构，为数据世界的构建添砖加瓦。