基本线性数据结构的Python实现

2017年10月

Python

本篇主要实现四种数据结构，分别是数组、堆栈、队列、链表。我不知道我为什么要用 Python 来干 C 干的事情，总之 Python 就是可以干。

所有概念性内容可以在参考资料中找到出处

数组

数组的设计

数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先请求空间。这使得数组有以下特性：

请求空间以后大小固定，不能再改变（数据溢出问题）；
在内存中有空间连续性的表现，中间不会存在其他程序需要调用的数据，为此数组的专用内存空间；
在旧式编程语言中（如有中阶语言之称的 C），程序不会对数组的操作做下界判断，也就有潜在的越界操作的风险（比如会把数据写在运行中程序需要调用的核心部分的内存上）。

因为简单数组强烈倚赖电脑硬件之内存，所以不适用于现代的程序设计。欲使用可变大小、硬件无关性的数据类型，Java 等程序设计语言均提供了更高级的数据结构：ArrayList、Vector 等动态数组。

Python 的数组

从严格意义上来说:Python 里没有严格意义上的数组。 List可以说是 Python 里的数组，下面这段代码是 CPython 的实现List的结构体:

1typedef struct {
2    PyObject_VAR_HEAD
3    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
4    PyObject **ob_item;
5
6    /* ob_item contains space for 'allocated' elements.  The number
7     * currently in use is ob_size.
8     * Invariants:
9     *     0 <= ob_size <= allocated
10     *     len(list) == ob_size
11     *     ob_item == NULL implies ob_size == allocated == 0
12     * list.sort() temporarily sets allocated to -1 to detect mutations.
13     *
14     * Items must normally not be NULL, except during construction when
15     * the list is not yet visible outside the function that builds it.
16     */
17    Py_ssize_t allocated;
18} PyListObject;

1typedef struct {
2    PyObject_VAR_HEAD
3    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
4    PyObject **ob_item;
5
6    /* ob_item contains space for 'allocated' elements.  The number
7     * currently in use is ob_size.
8     * Invariants:
9     *     0 <= ob_size <= allocated
10     *     len(list) == ob_size
11     *     ob_item == NULL implies ob_size == allocated == 0
12     * list.sort() temporarily sets allocated to -1 to detect mutations.
13     *
14     * Items must normally not be NULL, except during construction when
15     * the list is not yet visible outside the function that builds it.
16     */
17    Py_ssize_t allocated;
18} PyListObject;

取自CPython-Github

还有一篇文章讲List实现,感兴趣的朋友可以去看看。中文版。

当然，在 Python 里它就是数组。后面的一些结构也将用List来实现。

堆栈

什么是堆栈

堆栈（英语：stack），也可直接称栈，在计算机科学中，是一种特殊的串列形式的数据结构，它的特殊之处在于只能允许在链接串列或阵列的一端（称为堆叠顶端指标，英语：top）进行加入资料（英语：push）和输出资料（英语：pop）的运算。另外堆叠也可以用一维阵列或连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列。

由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

特点

先入后出，后入先出。
除头尾节点之外，每个元素有一个前驱，一个后继。

操作

从原理可知，对堆栈(栈)可以进行的操作有:

top():获取堆栈顶端对象
push():向栈里添加一个对象
pop():从栈里推出一个对象

实现

1class my_stack(object):
2    def __init__(self, value):
3        self.value = value
4        # 前驱
5        self.before = None
6        # 后继
7        self.behind = None
8
9    def __str__(self):
10        return str(self.value)
11
12
13def top(stack):
14    if isinstance(stack, my_stack):
15        if stack.behind is not None:
16            return top(stack.behind)
17        else:
18            return stack
19
20
21def push(stack, ele):
22    push_ele = my_stack(ele)
23    if isinstance(stack, my_stack):
24      stack_top = top(stack)
25      push_ele.before = stack_top
26      push_ele.before.behind = push_ele
27    else:
28      raise Exception('不要乱扔东西进来好么')
29
30
31def pop(stack):
32    if isinstance(stack, my_stack):
33        stack_top = top(stack)
34        if stack_top.before is not None:
35            stack_top.before.behind = None
36            stack_top.behind = None
37            return stack_top
38        else:
39            print('已经是栈顶了')

1class my_stack(object):
2    def __init__(self, value):
3        self.value = value
4        # 前驱
5        self.before = None
6        # 后继
7        self.behind = None
8
9    def __str__(self):
10        return str(self.value)
11
12
13def top(stack):
14    if isinstance(stack, my_stack):
15        if stack.behind is not None:
16            return top(stack.behind)
17        else:
18            return stack
19
20
21def push(stack, ele):
22    push_ele = my_stack(ele)
23    if isinstance(stack, my_stack):
24      stack_top = top(stack)
25      push_ele.before = stack_top
26      push_ele.before.behind = push_ele
27    else:
28      raise Exception('不要乱扔东西进来好么')
29
30
31def pop(stack):
32    if isinstance(stack, my_stack):
33        stack_top = top(stack)
34        if stack_top.before is not None:
35            stack_top.before.behind = None
36            stack_top.behind = None
37            return stack_top
38        else:
39            print('已经是栈顶了')

队列

什么是队列

和堆栈类似，唯一的区别是队列只能在队头进行出队操作，所以队列是是先进先出（FIFO, First-In-First-Out）的线性表

特点

先入先出,后入后出
除尾节点外,每个节点有一个后继
（可选）除头节点外,每个节点有一个前驱

操作

push（）:入队
pop（）：出队

实现

普通队列

1class MyQueue():
2    def __init__(self, value=None):
3        self.value = value
4        # 前驱
5        # self.before = None
6        # 后继
7        self.behind = None
8
9    def __str__(self):
10        if self.value is not None:
11            return str(self.value)
12        else:
13            return 'None'
14
15
16def create_queue():
17    """仅有队头"""
18    return MyQueue()
19
20
21def last(queue):
22    if isinstance(queue, MyQueue):
23        if queue.behind is not None:
24            return last(queue.behind)
25        else:
26            return queue
27
28
29def push(queue, ele):
30    if isinstance(queue, MyQueue):
31        last_queue = last(queue)
32        new_queue = MyQueue(ele)
33        last_queue.behind = new_queue
34
35
36def pop(queue):
37    if queue.behind is not None:
38        get_queue = queue.behind
39        queue.behind = queue.behind.behind
40        return get_queue
41    else:
42        print('队列里已经没有元素了')
43
44def print_queue(queue):
45    print(queue)
46    if queue.behind is not None:
47        print_queue(queue.behind)

1class MyQueue():
2    def __init__(self, value=None):
3        self.value = value
4        # 前驱
5        # self.before = None
6        # 后继
7        self.behind = None
8
9    def __str__(self):
10        if self.value is not None:
11            return str(self.value)
12        else:
13            return 'None'
14
15
16def create_queue():
17    """仅有队头"""
18    return MyQueue()
19
20
21def last(queue):
22    if isinstance(queue, MyQueue):
23        if queue.behind is not None:
24            return last(queue.behind)
25        else:
26            return queue
27
28
29def push(queue, ele):
30    if isinstance(queue, MyQueue):
31        last_queue = last(queue)
32        new_queue = MyQueue(ele)
33        last_queue.behind = new_queue
34
35
36def pop(queue):
37    if queue.behind is not None:
38        get_queue = queue.behind
39        queue.behind = queue.behind.behind
40        return get_queue
41    else:
42        print('队列里已经没有元素了')
43
44def print_queue(queue):
45    print(queue)
46    if queue.behind is not None:
47        print_queue(queue.behind)

链表

什么是链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间，而顺序表相应的时间复杂度分别是 O(logn)和 O(1)。

特点

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

操作

init():初始化
insert(): 插入
trave(): 遍历
delete(): 删除
find(): 查找

实现

此处仅实现双向列表

1class LinkedList():
2    def __init__(self, value=None):
3        self.value = value
4        # 前驱
5        self.before = None
6        # 后继
7        self.behind = None
8
9    def __str__(self):
10        if self.value is not None:
11            return str(self.value)
12        else:
13            return 'None'
14
15
16def init():
17    return LinkedList('HEAD')
18
19
20def delete(linked_list):
21    if isinstance(linked_list, LinkedList):
22        if linked_list.behind is not None:
23            delete(linked_list.behind)
24            linked_list.behind = None
25            linked_list.before = None
26        linked_list.value = None
27
28
29def insert(linked_list, index, node):
30    node = LinkedList(node)
31    if isinstance(linked_list, LinkedList):
32        i = 0
33        while linked_list.behind is not None:
34            if i == index:
35                break
36            i += 1
37            linked_list = linked_list.behind
38        if linked_list.behind is not None:
39            node.behind = linked_list.behind
40            linked_list.behind.before = node
41        node.before, linked_list.behind = linked_list, node
42
43
44def remove(linked_list, index):
45    if isinstance(linked_list, LinkedList):
46        i = 0
47        while linked_list.behind is not None:
48            if i == index:
49                break
50            i += 1
51            linked_list = linked_list.behind
52        if linked_list.behind is not None:
53            linked_list.behind.before = linked_list.before
54        if linked_list.before is not None:
55            linked_list.before.behind = linked_list.behind
56        linked_list.behind = None
57        linked_list.before = None
58        linked_list.value = None
59
60
61def trave(linked_list):
62    if isinstance(linked_list, LinkedList):
63        print(linked_list)
64        if linked_list.behind is not None:
65            trave(linked_list.behind)
66
67
68def find(linked_list, index):
69    if isinstance(linked_list, LinkedList):
70        i = 0
71        while linked_list.behind is not None:
72            if i == index:
73                return linked_list
74            i += 1
75            linked_list = linked_list.behind
76        else:
77            if i < index:
78                raise Exception(404)
79            return linked_list

1class LinkedList():
2    def __init__(self, value=None):
3        self.value = value
4        # 前驱
5        self.before = None
6        # 后继
7        self.behind = None
8
9    def __str__(self):
10        if self.value is not None:
11            return str(self.value)
12        else:
13            return 'None'
14
15
16def init():
17    return LinkedList('HEAD')
18
19
20def delete(linked_list):
21    if isinstance(linked_list, LinkedList):
22        if linked_list.behind is not None:
23            delete(linked_list.behind)
24            linked_list.behind = None
25            linked_list.before = None
26        linked_list.value = None
27
28
29def insert(linked_list, index, node):
30    node = LinkedList(node)
31    if isinstance(linked_list, LinkedList):
32        i = 0
33        while linked_list.behind is not None:
34            if i == index:
35                break
36            i += 1
37            linked_list = linked_list.behind
38        if linked_list.behind is not None:
39            node.behind = linked_list.behind
40            linked_list.behind.before = node
41        node.before, linked_list.behind = linked_list, node
42
43
44def remove(linked_list, index):
45    if isinstance(linked_list, LinkedList):
46        i = 0
47        while linked_list.behind is not None:
48            if i == index:
49                break
50            i += 1
51            linked_list = linked_list.behind
52        if linked_list.behind is not None:
53            linked_list.behind.before = linked_list.before
54        if linked_list.before is not None:
55            linked_list.before.behind = linked_list.behind
56        linked_list.behind = None
57        linked_list.before = None
58        linked_list.value = None
59
60
61def trave(linked_list):
62    if isinstance(linked_list, LinkedList):
63        print(linked_list)
64        if linked_list.behind is not None:
65            trave(linked_list.behind)
66
67
68def find(linked_list, index):
69    if isinstance(linked_list, LinkedList):
70        i = 0
71        while linked_list.behind is not None:
72            if i == index:
73                return linked_list
74            i += 1
75            linked_list = linked_list.behind
76        else:
77            if i < index:
78                raise Exception(404)
79            return linked_list

以上所有源代码均在Github共享，欢迎提出 issue 或 PR，希望与大家共同进步!

参考资料

Wiki 百科: 数据结构、数组、队列、链表