作者:少年吉
来源:微信公众号: 数据科学CLUB
出处:https://mp.weixin.qq.com/s?__biz=MzUzODg0NDI4Mw==&mid=2247485723&idx=1&sn=75dd6e6cb8ca25f2fb5c3bf83c93a31c
- 顺序表
- Python顺序表中基本操作的实现
- list其他操作
- list内置操作的时间复杂度
- 单链表
- python单链表基本操作的实现
- 单个节点实现
- 单链表的实现
- 顺序表与单链表的对比
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示 也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（Sequent ial List其特点是, 逻辑上相邻的数据元素，其物理次序也是相邻的。假设线性表的每个元素需占用个存储单元，并以所占的第一个单元的存储地址作为数据元 素的存储起始位置。则线性表中第个数据元素的存储位置和第个数据元素的存 储位置 LOC之间满足下列关系：
一般来说，线性表的第个数据元素的存储位置为：
a = [1,2,3,4,4,5]
id(a[1])-id(a[0])
id(a[2])-id(a[1])
id(a[0]) 32*3 == id(a[3])
True
Python顺序表中基本操作的实现
Python的 list 和 tuple采用了顺序表的实现技术,具有顺序表的所有性质
- 初始化
顺序表的初始化操作就是构造一个空的顺序表。
alist = []
- 取值
取值操作是根据指定的位置序号i，获取顺序表中第i个数据元素的值。由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到,elem[i-1]单元存储第i个数据元素。
- 时间复杂度为
a[2]
- 查找
查找操作是根据指定的元素值e，查找顺序表中第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号;若查找失败，则返回0。
- 平均时间复杂度为
a.index(4)
- 插入
线性表的插入操作是指在表的第个位置插人一个新的数据元素, 使长度为的线性表
变成长度为的线性表
一般情况下，在第个位置插入一个 元素时，需从最后一个元素即第个元素开始，依次向后移动一个位置，直至第个元素（共个元素 )。
顺序表插入算法的平均时间复杂度为
Python中有多种方法向表中插入某一元素
a
[1, 2, 3, 4, 4, 5]
# 在列表尾部添加一个对象
# 官方：same as s[len(s):len(s)] = [x]
a.append(0)
a
[1, 2, 3, 4, 4, 5, 0]
# 在列表尾部添加一个序列
# 官方：same as s[len(s):len(s)] = t
a.extend([9])
a
[1, 2, 3, 4, 4, 5, 0, 9]
# 在指定位置插入元素
a.insert(2,8)
a
[1, 2, 8, 3, 4, 4, 5, 0, 9]
a.pop(2)
- 删除
线性表的删除操作是指将表的第个元素删去，将长度为的线性表
变成长度为的线性表
一般情况下, 删除第个元素时需将第个至第个元素（共个元素 ) 依次向前移动一个位置
- 顺序表删除算法的平均时间复杂度为
# 从a中删除a[i]等于x的第一项
a.remove(4)
a
[1, 2, 8, 3, 4, 5, 0, 9]
# 返回i处的元素值，并将其从a中删除
a.pop(-1)
a
[1, 2, 8, 3, 4, 5, 0]
list其他操作
b = [1,2,3,4,4]
len(b)
min(b)
max(b)
b.count(4)
5 in b
False
2 in b
True
# 反转
b.reverse()
b
[4, 4, 3, 2, 1]
# 删除某几项
del b[1:3]
b
[4, 2, 1]
# 清空
b.clear()
b
[]
list内置操作的时间复杂度
线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单 元可以是连续的，也可以是不连续的因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直 接后继的信息（即直接后继的存储位置这两部分信息组成数据元素的存储映像，称为结点( node )。它包括两个域：其中存储数据元素信息的域称为数据域; 存储直接后继存储位置的域称 为指针域。指针域中存储的信息称作指针或链。个结点（的存储映像 ) 链结成一 个链表，即为线性表
示意图
python单链表基本操作的实现单个节点实现class LNode(object):
def __init__(self,elem,next = None):
self.elem = elem
self.next = next
单链表的实现
- 单链表的初始化
class SingleLinkList(object):
def __init__(self):
self.__head = None
# 头结点的指针域置空
- 判断链表是否为空
def is_empty(self):
return self.__head == None
- 链表长度
def length(self):
# p初始时指向头节点
p = self.__head
count = 0
# 尾节点指向None，当未到达尾部时
while p != None:
count = 1
# 将cur后移一个节点
p = p.next
return count
- 取值
和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样 ，根据给定的 结点位置序号i'在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结 点出发，顺着链域 next 逐个结点向下访问。
- 单链表取值算法的平均时间复杂度为
def get_elem(self,i):
# p为扫描指针
p = self.__head
while p != None and 0<i<self.length():
i -= 1
p = p.next
return p.elem
- 查找
链表中按值查找的过程和顺序表类似，从链表的首元结点出发， 依次将结点值和给定值e进 行比较， 返回查找结果。
- 其平均时间复杂度也为
def loc_elem(self,elem):
p = self.__head
while p != None:
if p.elem == elem:
return True
else:
p = p.next
return False
- 插入
假设要在单链表的两个数据元素a和b之间插入一个数据元素x, 已知p为其单链表存储结 构中指向结点a的指针
