Python实现基本线性数据结构
数组的设计
数组设计之初是在形式上依赖内存分配而成的,所以必须在使用前预先请求空间。这使得数组有以下特性:
1、请求空间以后大小固定,不能再改变(数据溢出问题);
2、在内存中有空间连续性的表现,中间不会存在其他程序需要调用的数据,为此数组的专用内存空间;
3、在旧式编程语言中(如有中阶语言之称的C),程序不会对数组的操作做下界判断,也就有潜在的越界操作的风险(比如会把数据写在运行中程序需要调用的核心部分的内存上)。
因为简单数组强烈倚赖电脑硬件之内存,所以不适用于现代的程序设计。欲使用可变大小、硬件无关性的数据类型,Java等程序设计语言均提供了更高级的数据结构:ArrayList、Vector等动态数组。
Python的数组
从严格意义上来说:Python里没有严格意义上的数组。
List可以说是Python里的数组,下面这段代码是CPython的实现List的结构体:
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;
当然,在Python里它就是数组。
后面的一些结构也将用List来实现。
堆栈
什么是堆栈
堆栈(英语:stack),也可直接称栈,在计算机科学中,是一种特殊的串列形式的数据结构,它的特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语:top)进行加入资料(英语:push)和输出资料(英语:pop)的运算。另外堆叠也可以用一维阵列或连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列。
由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。
特点
1、先入后出,后入先出。
2、除头尾节点之外,每个元素有一个前驱,一个后继。
操作
从原理可知,对堆栈(栈)可以进行的操作有:
1、top() :获取堆栈顶端对象
2、push() :向栈里添加一个对象
3、pop() :从栈里推出一个对象
实现
class my_stack(object):
def __init__(self, value):
self.value = value
# 前驱
self.before = None
# 后继
self.behind = None
def __str__(self):
return str(self.value)
def top(stack):
if isinstance(stack, my_stack):
if stack.behind is not None:
return top(stack.behind)
else:
return stack
def push(stack, ele):
push_ele = my_stack(ele)
if isinstance(stack, my_stack):
stack_top = top(stack)
push_ele.before = stack_top
push_ele.before.behind = push_ele
else:
raise Exception('不要乱扔东西进来好么')
def pop(stack):
if isinstance(stack, my_stack):
stack_top = top(stack)
if stack_top.before is not None:
stack_top.before.behind = None
stack_top.behind = None
return stack_top
else:
print('已经是栈顶了')
队列
什么是队列
和堆栈类似,唯一的区别是队列只能在队头进行出队操作,所以队列是是先进先出(FIFO, First-In-First-Out)的线性表
特点
1、先入先出,后入后出
2、除尾节点外,每个节点有一个后继
3、(可选)除头节点外,每个节点有一个前驱
操作
1、push() :入队
2、pop() :出队
实现
普通队列
class MyQueue():
def __init__(self, value=None):
self.value = value
# 前驱
# self.before = None
# 后继
self.behind = None
def __str__(self):
if self.value is not None:
return str(self.value)
else:
return 'None'
def create_queue():
"""仅有队头"""
return MyQueue()
def last(queue):
if isinstance(queue, MyQueue):
if queue.behind is not None:
return last(queue.behind)
else:
return queue
def push(queue, ele):
if isinstance(queue, MyQueue):
last_queue = last(queue)
new_queue = MyQueue(ele)
last_queue.behind = new_queue
def pop(queue):
if queue.behind is not None:
get_queue = queue.behind
queue.behind = queue.behind.behind
return get_queue
else:
print('队列里已经没有元素了')
def print_queue(queue):
print(queue)
if queue.behind is not None:
print_queue(queue.behind)
链表
什么是链表
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。
特点
使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
操作
1、init() :初始化
2、insert() : 插入
3、trave() : 遍历
4、delete() : 删除
5、find() : 查找
实现
此处仅实现双向列表
class LinkedList():
def __init__(self, value=None):
self.value = value
# 前驱
self.before = None
# 后继
self.behind = None
def __str__(self):
if self.value is not None:
return str(self.value)
else:
return 'None'
def init():
return LinkedList('HEAD')
def delete(linked_list):
if isinstance(linked_list, LinkedList):
if linked_list.behind is not None:
delete(linked_list.behind)
linked_list.behind = None
linked_list.before = None
linked_list.value = None
总结
以上就是利用Python实现基本线性数据结构的全部内容
数据分析咨询请扫描二维码
CDA数据分析师在中国航信高科技产业园进行了面向测试度量的数据分析培训课程,培训人数近2 ...
2024-05-01CDA数据分析师走进深圳迈瑞生物医疗电子股份有限公司,在迈瑞总部展开了为期两天的培训,本次课程参训人员线上及线下近百人, ...
2024-05-01CDA数据分析师在合肥市对合肥阳光新能源科技有限公司开展了为期8天的企业内训。 合肥阳光新能源科技 ...
2024-05-01CDA数据分析师走进海尔大学,进行了《数据治理与数据中台建设的道与术》专题培训,培训现场爆满,近百人参加了此次培训。 ...
2024-05-01在中国银行苏州分行培训中心开始数据分析师培训,此次培训课程共10天内容,包括Excel、MySQL、概率论与数理统计、SPSS等内容, ...
2024-05-01从实际的业务需求出发,结合行业的典型应用特点,围绕实际的商业问题,探讨数据挖掘、机器学习模型在金融领域的应用,包括获客、信用评分、细分画像、交叉销售、反欺诈、违规识别、时序预测、运筹优化、流程挖掘九个方面,形成 ...
2024-05-01本次培训课程为线上+线下的模式,由于学员编程能力不一、部分学员没有编程基础,故提供统计学、python基 ...
2024-05-01华夏银行信用卡中心-机器学习培训 1、课程亮点 取材于业界一流企业和顶级咨询公司的行业实践;已经被证明是人人 ...
2024-05-01主 题:数据中台建设及数据分析应用主题分享 1. 数据中台市场洞察 2. 主流数据中台产品比较 3. 某企业数据中 ...
2024-05-01围绕“数据驱动”战略,全力打造我行 300 人数字化人才梯队,着力培养数字化管理人才、大数据专业团队 ...
2024-05-01在当今数据驱动的商业环境中,数据分析成为了企业决策的重要依据。通过对大量数据的收集、处理和分析,企业能够更好地理解市场 ...
2024-04-29在人工智能(AI)的世界里,提示词(Prompt)是一种强大的工具,它能够引导AI按照用户的需求产生特定的输出。本文将深入探讨AI ...
2024-04-29CDA立足未来职场,拓展前沿视野——对外经贸大学保险学院举办“三全育人大讲堂”分享行业最新动态。 ...
2024-04-294月2日,CDA数据分析师创始发起人兼协会理事长赵坚毅博士受邀在浙江万里学院举办了一场以“数字化能力在职场中的作用” ...
2024-04-29随机森林(Random Forests)现在机器学习中比较火的一个算法,是一种基于Bagging的集成学习方法,能够很好地处理分类和回归的问 ...
2022-12-23方差分析是数据分析中常用的一种统计分析方法,接下来让我们简单了解一下方差分析的基本思想和原理吧。 方差分析(Analysis ...
2022-12-23来源:关于数据分析与可视化 关于streamlit-aggrid 数据排序 表格样式的调整 数据 ...
2022-08-03作者:麦叔 定义 「把上面晦涩的概念汇成一句话就是:」 ❝ 回调函数就是一个被作为参 ...
2022-08-03现今,高学历人群日益增多,物以稀为贵的高学历光环淡去。无论本科生还是研究生,甚至博士生,求职竞争力都大不如前,就业压力越来越大。
2022-06-01某家企业10个人面试,有9个本科生……如何脱颖而出,除得体的举止和良好的沟通力外,证书成重要筹码,这也是很多人考证的关键所在。
2022-04-14