数据结构-1(顺序表)

一、数据结构的初步思维导图

二、 顺序表的创建

class Sequence_list():def __init__(self, capacity=10):# 用列表申请一片连续的空间用于存储数据self.data = [None] * capacity  # 序列乘法,用于规定列表的长度为capacityself.size = 0  # 已存储的个数self.capacity = capacitydef add_tail(self, value):"""功能:顺序表的增加,尾插思路:将要增加的元素放入顺序表中下标为size的位置中(因为列表从0开始,size从1开始，size和将要放入的位置恰好相同)注意事项:1、判满 ; 2、增加成功后顺序表的长度自增:param value: 要插入的元素:return:None"""if self.is_full():print("顺序表已满，插入失败")returnelse:self.data[self.size] = valueself.size += 1def is_full(self):"""功能：顺序表长度是否与线性表的最大容量相等思路：判断顺序表长度是否等于顺序表最大长度:return:bool(Ture为满,False为未满)"""return self.size == self.capacitydef show(self):"""功能：打印顺序表所有元素注意事项：1、判空:return:None"""if self.is_empty():returnelse:i = 0while i < self.size:print(self.data[i], end=' ')  # end=' ' 指定 print 语句行尾不再默认换行，而是输出一个空格i += 1print()  # 用于换行# for data in self.data: #此版本不如上面,因为会打印整个列表,即使后面的位置为空,浪费空间#     print(data)def is_empty(self):"""功能：判断顺序表是否为空思路：顺序表长度是否为0:return:bool"""return self.size == 0def insert_index(self, index, value):"""功能：在函数的任意位置插入思路：注意事项：1、判满 2、插入成功,长度自增 3、判断要插入的位置是否合理:param value:要插入的元素:param index:要插入的位置:return:None"""if self.is_full() or index < 0 or index > self.size:  # 判满并判断插入位置是否合理print("插入失败")returnelse:# 首先决定操作次数i = 0  # 初始化i,i表示腾位时后移操作的次数,while i < self.size - index:  # 根据次数进行循环,必须要引入index,因为插入的位置不同腾位的次数也不同,需要先确定次数# [self.size - i]从列表最后一位的再后一位开始,self.size - i - 1从最后一位开始self.data[self.size - i] = self.data[self.size - i - 1]  # 从后往前依次腾位i += 1self.data[index] = valueself.size += 1print("插入成功")def remove(self, index):"""功能：在函数的任意位置删除思路：注意事项：1、判空 2、删除成功,长度自减 3、判断要插入的位置是否合理:param index: 要删除的位置:return: None"""if self.is_empty() or index < 0 or index >= self.size:  # 判空并判断删除位置是否合理,index可以为0但不能为-1及以下print("删除失败")returnelse:i = indexwhile i < self.size - 1:  # 删除的次数是固定的self.data[i] = self.data[i + 1]  # 从前往后依次腾位i += 1self.size -= 1# [1,2,3]def change_index(self, index, value):"""按位置修改:param index: 需要修改的位置:param value: 需要修改为的值:return: None"""if self.is_empty() or index < 0 or index >= self.size:  # 判空并判断修改位置是否合理self.data[index] = valuedef change_value(self, old_value, new_value):"""按值修改:param old_value: 需要被修改的值:param new_value: 需要修改为的值:return: None"""if self.is_empty():  # 判空并判断修改位置是否合理returnelse:i = 0flag = 0while i < self.size:if self.data[i] == old_value:self.data[i] = new_valueflag = 1i += 1if flag == 0:print("未找到数据")def find_value_index(self, value):"""按值查找并返回索引:param value: 需要查找的值:return: 查找到的值的索引 or -1"""if self.is_empty():print("查找失败")returnelse:i = 0while i < self.size:if self.data[i] == value:return ii += 1return -1  # 和change_value的flag方法类似,两者都可以使用，用于判断查找是否成功def remove_repeat(self):lasr_unique=0 # 初始化已确定最后一个不重复元素的位置for i in range(self.size):  # 遍历所有元素for j in range(self.size-1,lasr_unique,-1):  # 除了已去重过的元素索引外,继续进行遍历并与i比对，若相同则删除,需要反向遍历，因为如果不在表尾进行删除会导致索引变化,用j-1进行回退也可以。if self.data[j] == self.data[i]:self.remove(j)lasr_unique+=1def get_capacity(self):return self.capacitypass
# 1 3 5
# 2 8 10
#
# 1 2 8 10 3 5
if __name__ == '__main__':seq_list = Sequence_list()seq_list.add_tail("张飞")seq_list.add_tail("吕布")seq_list.show()

三、额外功能实现

1、自动扩容

    def add_tail(self, value):"""功能:顺序表的增加,尾插增加功能:表满时自动扩容思路:将要增加的元素放入顺序表中下标为size的位置中(因为列表从0开始,size从1开始，size和将要放入的位置恰好相同)注意事项:1、判满 ; 2、增加成功后顺序表的长度自增:param value: 要插入的元素:return:None"""if self.is_full():print("扩容")self.capacity = int(self.capacity) * 1.5  # 定义扩容量print(f"新容量为：{int(self.capacity)}")self.backup_data = self.dataself.data = [None] * int(self.capacity)  # 充值并扩容for i in range(self.size):  # 将备份好的列表逐步加入回重置并扩容后的列表self.data[i] = self.backup_data[i]self.add_tail(value)  # 扩容后重新addelse:self.data[self.size] = valueself.size += 1

2、自动缩容

    def remove(self, index):"""功能：在函数的任意位置删除增加功能：元素少于最大容量1/4时自动缩容思路：注意事项：1、判空 2、删除成功,长度自减 3、判断要插入的位置是否合理:param index: 要删除的位置:return: None"""if self.is_empty() or index < 0 or index >= self.size:  # 判空并判断删除位置是否合理,index可以为0但不能为-1及以下print("删除失败")returnelif self.size < self.capacity // 4:print("缩容")self.capacity = self.capacity // 4  # 定义缩容量print(f"新容量为：{int(self.capacity)}")self.backup_data = self.dataself.data = [None] * int(self.capacity)  # 重置并缩容for i in range(self.size):  # 将备份好的列表逐步加入回重置并扩容后的列表self.data[i] = self.backup_data[i]self.remove(index)  # 重新执行remove函数else:i = indexwhile i < self.size - 1:  # 删除的次数是固定的self.data[i] = self.data[i + 1]  # 从前往后依次腾位i += 1self.size -= 1

3、返回实际容量

    def get_capacity(self):return self.capacity

4、合并两个升序列表

def merge_sorted(list1, list2):"""合并两个升序顺序表，需要list1保留足够两个列表合并的容量:param list1::param list2::return:"""# 创建i、j两个指针分别指向list1和list2的末端i = len([x for x in list1 if x is not None]) - 1  # 不能直接用len，因为list有很多Nonej = len([x for x in list2 if x is not None]) - 1# 创建k指针指向list1预留的合并后列表的最后一位k = i + j + 1  # 合并后的最终一位if len(list1) < i+j+2:print("list预留空间不足")returnwhile i >= 0 and j >= 0:# 比较，大的元素指针向前走一步,直到ij其中一个指针走到-1if list1[i] >= list2[j]:list1[k] = list1[i]k -= 1i -= 1else:list1[k] = list2[j]k -= 1j -= 1# 若i先到-1，j还剩一位，直接赋值到第一位，之所以不需要对i进行同样的处理是因为第一位一直都是i的最小值list1[0]，就算没轮到list1[0]也没必要赋值。while j >= 0:list1[k] = list2[j]j -= 1k -= 1# list1 = list1[len1:]return list1