元素内置顺序表
顺序表中存放的基本是数据类型相同的元素。因此存储每个元素所用的内存空间是相同。可以在顺序表里等间距的安排同样大小的内存空间。这样可以直接映射到计算机内存和单元，顺序表里的的元素位置计算会变得十分简单。
设有一个顺序表对象,元素存储在一片存储区域;第一个元素的存储地址为,逻辑地址对应为0; 每个元素占的存储空间为
,逻辑地址
对应的物理地址为
，如下图所示：
image.png
表尾插入数据
image.png
指定位置插入数据
指定位置插入数据在表中时，插入位置后面的数据要整体向后移动
image.png
删除数据
删除数据在表中间或表头时，删除位置后面的数据要整体向前移动
image.png
python代码实现元素内置顺序表
class BaseSeqList:
def __init__(self, *args, size=50):
"""顺序表初始化"""
self.__max = size # 定义最大元素存储数量
self.__length=0 # 当前元素存储数量
self.data = [None]*self.__max # 初始化内存空间
for index, data in enumerate(args): # 将初始化的数据放入顺序表的存储区域
self.data[index] = data
self.__length += 1
def is_empty(self):
"""判读顺序表是否为空"""
return self.__lenght == 0
def is_full(self):
"""判断顺序表是否存满"""
return self.__max == self.__length
def append(self, value):
"""顺序表末尾添加数据"""
def append(self, value):
"""
在顺序表末尾添加数据
:param value:
:return:
"""
if not self.is_empty(): # 判断顺序表是否为空
if self.is_full():
self.data += [None]
self.__max += 1
self.data[self.__length] = value
self.__length += 1
def insert(self, index, value):
"""
指定位置添加数据
:param index: 要添加的索引
:param value: 添加的值
:return:
"""
pos = self.__length
if not self.is_empty():
self.__get_new_space()
if index >= self.__length:
self.append(value)
else:
while pos > index:
self.data[pos] = self.data[pos - 1]
pos -= 1
self.data[index] = value
self.__length += 1
def update_value(self, value, new_value):
"""
指定元素修改第一个找到元素
:param value: 要修改的值
:param new_value: 修改为的值
:return:
"""
pos = self.__length
if not self.is_empty():
for i in range(pos):
if self.data[i] == value:
self.data[i] = new_value
break
else:
raise ValueError("指定value不存在")
def update_index(self, index, new_value):
"""
指定索引修改
:param index: 要修改索引
:param new_value: 修改为的值
:return:
"""
pos = self.__length
if not self.is_empty():
if index > pos-1:
raise IndexError("超出索引范围")
else:
self.data[index] = new_value
else:
raise IndexError("超出索引范围")
def search(self, value):
"""
查询顺序表中的元素的索引, 如果元素存在返回第一个元素索引，否则返回-1
:param value:
:return:
"""
pos = self.__length
if not self.is_empty():
for index in range(pos):
if self.data[index] == value:
return index
else:
return -1
def search_all(self, value):
"""
查询顺序表中所有的value的索引，如果存在以列表形式返回，否则报错
:param value:
:return:
"""
ind = []
pos = self.__length
if not self.is_empty():
for index in range(pos):
if self.data[index] == value:
ind.append(index)
if ind:
return ind
else:
raise ValueError("value不存在")
def delete(self, value):
"""
删除元素value
:param value: 要删除的元素
:return:
"""
pos = self.__length
if not self.is_empty():
ind = self.search(value)
while ind < pos:
self.data[ind] = self.data[ind+1]
ind += 1
self.__length -= 1
else:
raise ValueError("value不存在")
def __getitem__(self, index): # self[index]
return self.data[index]
def __setitem__(self, index, value): # self[index] = value
self.update_index(index, value)
def __delitem__(self, index): # del self[index]
pos = self.__length
if index > pos-1:
raise IndexError("超出索引范围")
else:
if not self.is_empty():
while index < pos-1:
self.data[index] = self.data[index+1]
index += 1
self.__length -= 1
def __len__(self): # len(self)
return self.__length
def __get_new_space(self):
"""
当顺序表存满时，重新申请额外内存空间
:return:
"""
if self.__length == self.__max: # 判断顺序表是否存满，如果存满，动态申请内存
self.data += [None]
self.__max += 1
def __repr__(self):
data = []
for i in range(self.__length):
data.append(str(self.data[i]))
return ",".join(data)
元素外置顺序表
当我们遇到顺序表中要存放数据类型不同的元素时，可以将元素的地址保存到顺序表中，通过地址寻找到元素。如下图所示：
image.png
采取方法：将数据保存到一个类中，将这个类放到顺序表中，实现元素外置
python实现元素外置顺序表
class Data:
"""
将数据保存到一个类中，将这个类放到顺序表中，实现元素外置
"""
def __init__(self, value):
self.value = value
元素外置顺序表实现，与元素内置顺序表的实现时一致的。只需要将承载元素的类放入顺序表中,具体实现如下。
self.data[index]=Data(value)
