基本线性数据结构的Python实现
本篇主要实现四种数据结构,分别是数组、堆栈、队列、链表。我不知道我为什么要用Python来干C干的事情,总之Python就是可以干。
所有概念性内容可以在参考资料中找到出处
数组
数组的设计
数组设计之初是在形式上依赖内存分配而成的,所以必须在使用前预先请求空间。这使得数组有以下特性:
- 请求空间以后大小固定,不能再改变(数据溢出问题);
- 在内存中有空间连续性的表现,中间不会存在其他程序需要调用的数据,为此数组的专用内存空间;
- 在旧式编程语言中(如有中阶语言之称的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;
还有一篇文章讲List
实现,感兴趣的朋友可以去看看。中文版。
当然,在Python里它就是数组。
后面的一些结构也将用List
来实现。
堆栈
什么是堆栈
堆栈(英语:stack),也可直接称栈,在计算机科学中,是一种特殊的串列形式的数据结构,它的特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语:top)进行加入资料(英语:push)和输出资料(英语:pop)的运算。另外堆叠也可以用一维阵列或连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列。
由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。
特点
- 先入后出,后入先出。
- 除头尾节点之外,每个元素有一个前驱,一个后继。
操作
从原理可知,对堆栈(栈)可以进行的操作有:
- top():获取堆栈顶端对象
- push():向栈里添加一个对象
- 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: