Python数据结构与算法

发表于 | 更新于 | 分类于 | 阅读次数：

介绍

数据结构与算法对于Python而言是他的核心,但对于Python而言内置了基础的数据结构与算法,弱化了数据结构与算法的使用

数据结构主要涉及，顺序表，链表，堆栈（栈存储的为局部变量，而栈内存存储的为局部变量），队列，树，二叉树，平衡二叉树，红黑树

算法主要涉及排序算法（冒泡排序，选择排序，插入排序，快速排序，希尔排序，归并排序）和查找算法（顺序查找，二分法查找，二叉树查找，哈希查找）

顺序表
1
2
Python中的list和tuple都是顺序表结构,list是动态顺序表,支持内部结构变化如增加或者减少元素,而tuple并不支持结构的改变,其他性能和list一致
list结构中,append的时间复杂度为O(1),而insert插入函数是在插入位置之后的元素依次向下挪动一个位置,复杂度为O(n),同理pop()删除最后一个位置时,时间复杂度为O(1),当删除指定元素时,则该元素其后的元素依次挪动一个位置,时间复杂度为O(n)
单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
链表是由一个个节点连接而成,节点由两部分构成:元素域、链接域；链接域链接下一个节点
    节点对象
Class node：
	def __init__(self,item):
		self.item = item
         self.next = None
     链表对象
class SinglyLinkedList:
    """链表对象"""
    def __init__(self):
        self._head = None

    def add(self, item):
        """
        头部添加节点
        :param item: 节点值
        :return:
        """
        node = Node(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        """
        尾部添加节点
        :param items:
        :return:
        """
        cur = self._head
        if not cur:  # 判断是否为空链表
            self.add(item)
        else:
            node = Node(item)
            while cur.next:
                cur = cur.next
            cur.next = node