提示信息

Python实现的顺序表手动构建

冷暖 已关注

在 Python 中,顺序表通常可以用列表(list)来实现,因为 Python 的列表在内部实现上就是动态数组。不过,如果你想手动构建一个类似于顺序表的数据结构,可以从底层使用数组的思想来实现。这里是一个简单的例子,展示了如何手动构建一个顺序表类:

  1. class MyArrayList:
  2. def __init__(self, capacity=10):
  3. # 初始化数组容量和内部存储
  4. self.capacity = capacity # 初始容量
  5. self.size = 0 # 当前元素个数
  6. self.array = [None] * self.capacity # 内部存储
  7. def is_empty(self):
  8. return self.size == 0
  9. def get_size(self):
  10. return self.size
  11. def get(self, index):
  12. if 0 <= index < self.size:
  13. return self.array[index]
  14. else:
  15. raise IndexError("Index out of bounds")
  16. def add(self, element):
  17. # 如果数组已满,扩充容量
  18. if self.size == self.capacity:
  19. self._resize(2 * self.capacity)
  20. self.array[self.size] = element
  21. self.size += 1
  22. def insert(self, index, element):
  23. if index < 0 or index > self.size:
  24. raise IndexError("Index out of bounds")
  25. if self.size == self.capacity:
  26. self._resize(2 * self.capacity)
  27. for i in range(self.size, index, -1):
  28. self.array[i] = self.array[i - 1]
  29. self.array[index] = element
  30. self.size += 1
  31. def remove(self, index):
  32. if index < 0 or index >= self.size:
  33. raise IndexError("Index out of bounds")
  34. removed_element = self.array[index]
  35. for i in range(index, self.size - 1):
  36. self.array[i] = self.array[i + 1]
  37. self.array[self.size - 1] = None
  38. self.size -= 1
  39. return removed_element
  40. def _resize(self, new_capacity):
  41. new_array = [None] * new_capacity
  42. for i in range(self.size):
  43. new_array[i] = self.array[i]
  44. self.array = new_array
  45. self.capacity = new_capacity
  46. # 使用示例
  47. my_list = MyArrayList()
  48. my_list.add(10)
  49. my_list.add(20)
  50. my_list.insert(1, 15)
  51. print(my_list.get(1)) # 输出 15
  52. my_list.remove(1)
  53. print(my_list.get(1)) # 输出 20

关键点说明:

  1. 容量管理:当数组达到其容量上限时,通过 _resize 方法增加容量。通常将容量加倍,以减少频繁扩容所带来的开销。

  2. 数据移动:在插入和删除操作中,需要移动数组中的元素以保持顺序。

  3. 基本操作:提供了一些基本操作如 add(尾部添加)、insert(插入)和 remove(删除)等。

这个实现基本上涵盖了顺序表的一些常见操作,你可以根据需要进行扩展或优化。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
冷暖 关注 已关注

最近一次登录:2024-11-20 21:09:51   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图