概念
数据结构的概念
数据结构 是 存储、组织数据 的方式 ,指相互之间存在一种或多种特定关系的 数据元素的集合。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储 效率 , 数据结构往往影响着 算法的效率
举个例子： 我们希望存贮一个 班级的学员信息
结论：相同 的数据采用 不同 的方式也就不同的 数据结构 存储，带来的运行或者存储 效率
是不同的
什么是数据结构、和算法关系
数据结构 只是 静态 的描述了数据元素之间的 关系， 是存储和组织数据的方式。
高效的程序 需要在数据结构的基础上设计和选择 算法
算法 是为了 解决实际问题 而设计的， 数据结构 是算法需要处理问题的 载体
最常用的数据运算有五种：
插入，删除，修改，查找，排序等
内存的存储结构
内存是以 字节 为基本 存储单位 的, 每个基本 存储空间 都有自己的 地址（注意：一个内存地址代表一个字节（8bit）的存储空间）。
整形(int) : 4个字节
字符(char): 1个字节 . 单个字符“a”占1个字节, 字符串“abc”占3个字节
数据结构的分类
根据数据结构中数据之间的关系，将数据结构分类为:
- 线性结构
- 非线性结构
线性结构
线性结构就是数据结构中各个结点具有 线性关系
线性结构的特点:
① 线性结构是非空集
② 线性结构所有结点都最多只有一个直接前驱结点和一个直接后继结点
非线性结构
非线性结构就是数据结构中各个结点之间具有 多个对应关系
非线性结构的特点:
① 非线性结构是非空集
② 非线性结构的一个结点可能有多个直接前驱结点和多个直接后继结点
线性结构存储方式
线性结构的实际存储方式，分为两种：
①顺序表 : 将元素顺序地存放在一块 连续的存储区里 ，元素间的顺序关系由它们的存储顺序自然表示
②链表 : 将元素存放在通过链接构造起来的一系列存储块中 , 存储区是非连续的
顺序表的储方式
顺序表 元素顺序地存放在一块 连续的存储区里， 具体的存储方式的两种情况:
- 一体式结构
- 分离式结构
一体式存储方式
分离式存储
num 会记录列表的 首元素 地址0x11
由于列表中数据 大小不固定 , 偏移量也不确定 , 无法通过偏移的方式查找
无论 一体式结构 还是 分离式结构， 顺序表在获取数据的时候直接通过下标偏移就可以找到数据所在空间的地址 , 而无需遍历后才可以获取地址 . 所以顺序表在 获取地址操作 时的时间复杂度 : O(1)
顺序表的实现和扩充
顺序表的完整信息包括两部分:
①数据区
②信息区，即元素存储区的 容量 和当前表中已有的 元素个数
（ 信息区对数据进行描述、信息显示 ）
数据区更换为存储空间更大的区域时
扩充的两种策略
①每次扩充 增加固定数目的存储位置 ，如每次扩充增加10个元素位置，这种策略可称为线性增长
特点：节省空间，但是扩充操作频繁，操作次数多。
②每次扩充 容量加倍 ，如每次扩充增加一倍存储空间。
特点：减少了扩充操作的执行次数，但可能会浪费空间资源 , 以空间换时间，推荐的方式
顺序表增加与删除元素
增加元素
顺序表增加新元素 111 的三种方式
a. 尾端加入元素，时间复杂度为O(1)
b. 非保序的加入元素（不常见），时间复杂度为O(1) eg：在指定位置1号位置加入111元素（三号元素去队尾，插队元素占三号的位置）
c. 保序的元素加入，时间复杂度为O(n)（插队元素插到三号后面，其他元素挨个往后挪一位）
删除元素
a. 删除表尾元素，时间复杂度为O(1)
b. 非保序的元素删除（不常见），时间复杂度为O(1)，比如：在指定位置删除（1号位置）删除111，153填进来
c. 保序的元素删除，时间复杂度为O(n)
链表
顺序表的不足
顺序表存储时需要 连续的内存空间 ，当要扩充顺序表时会出现以下两种情况：
链表 不需要 连续的存储空间
链表结构
单链表(单向链表) 是链表的一种形式，每个结点包含两个域： 元素域 和 链接域 .
这个 链接 指向链表中的 下一个结点 , 而最后一个结点的链接域则指向 一个空值None
① 表元素域item 用来存放具体的 数据
② 链接域next 用来存放 下一个结点的位置
③ 变量head 指向链表的 头结点（首结点） 的位置，从 head 出发能找到表中的任意结点
结点代码实现
从面向对象的角度思考链表：应该有 2个对象 ： 结点对象 SingleNode 、链表对象 SingLinkList
如果 node 是一个结点:
获取结点元素 : node.item
获取下一个结点 : node.next 0
单链表代码的实现
- is_empty(self) 链表是否为空
- length(self) 链表长度
- travel(self) 遍历整个链表
- add(self, item) 链表头部添加元素
- append(self, item) 链表尾部添加元素
- insert(self, pos, item) 指定位置添加元素
- remove(self, item) 删除节点
- search(self, item) 查找节点是否存在
通过 append(node) 方法不断添加元素 , 最终实现单链表
链表判空 , 长度 , 遍历
链表的判空
链表的长度测量
链表的遍历
链表增加结点
add(item) 链表头部添加结点
append(item) 链表尾部添加结点
Insert(pos,item)在指定位置添加结点
链表删除和查找节点
remove(item) 删除节点
search(item) 查找节点是否存在
完整代码
class SingleNode:def __init__(self, item: str):self.item = itemself.next: SingleNode = Noneclass SingleLinkList:def __init__(self, item: str = None):self.head = SingleNode(str(item))def is_empty(self):"""链表是否为空:return: True:为空,False:不为空"""if not self.head:return Trueelse:return Falsedef length(self):"""链表长度:return: 链表的长度"""cur = self.headcount = 0while cur is not None:cur = cur.nextcount += 1return countdef travel(self):"""遍历整个链表"""cur = self.headwhile cur is not None:print(cur.item)cur = cur.nextdef add(self, item: str):"""链表头部添加元素"""node = SingleNode(item)node.next = self.headself.head = nodedef append(self, item: str):"""链表尾部添加元素"""node = SingleNode(item)if self.is_empty():self.head = nodeelse:cur = self.headwhile cur.next is not None:cur = cur.nextcur.next = nodedef insert(self, pos: int, item: str):"""指定位置添加元素"""if pos <= 0:self.add(item)elif pos >= self.length():self.append(item)else:cur = self.headcount = 0node = SingleNode(item)while count < pos - 1:cur = cur.nextcount += 1node.next = cur.nextcur.next = nodedef remove(self, item):"""删除节点"""# 游标cur = self.head# 辅助游标（指向前一个节点的游标）pre: SingleNode = Nonewhile cur is not None:# 找到要删除的节点if cur.item == item:# 若删除的是头结点if cur == self.head:self.head = cur.nextelse:pre.next = cur.nextreturnelse:pre = curcur = cur.nextdef search(self, item):"""查找节点是否存在"""cur = self.headwhile cur is not None:if cur.item == item:return Truecur = cur.nextreturn Falseif __name__ == "__main__":linkList = SingleLinkList(0)for i in range(1, 5):linkList.append(str(i))linkList.add("head")linkList.insert(1, "B")linkList.remove("head")linkList.remove("3")linkList.travel()print(f"链表长度：{linkList.length()}, 判断2是否存在 {linkList.search("2")}")
链表失去了顺序表随机读取的优点，链表由于增加了结点的连接域，空间开销比
较大，但对存储空间的使用要相对灵活 。
