数据结构与算法

引入

算法的概念

算法的五大特性：输入，输出，有穷性，确定性，可行性

时间复杂度

大O表示法

最坏时间复杂的

计算时间复杂度

数据结构

概念

算法与数据结构

算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

数据结构只是静态的描述了数据元素之间的关系，高效的程序需要在数据结构的基础上设计和选择算法。

程序 = 数据结构 + 算法

抽象数据类型

抽象数据类型是指一个数学模型以及在此数学模型上的一组操作。引入数据模型的目的是把数据类型的表示和数据类型上的运算的实现与这些数据类型和运算在程序中的引用隔开，使他们相互独立。

最常用的数据运算：插入，删除，修改，查找，排序

顺序表

顺序表的基本形式

顺序表的结构与实现

顺序表的结构

顺序表的实现

元素存储区

替换，扩充

扩充的两种策略：

• 每次增加固定数量的存储位置（节省空间，但操作频繁）
• 每次扩容加倍（减少操作次数，但存在空间浪费）

顺序表的操作

增加

删除

python中的顺序表

python中list和tuple两种数据类型采用了顺序表结构。tuple是不可变类型，不支持改变状态，其它与list性质类似，这里只说list。

链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，扩充时也很繁琐，所以使用起来不灵活，而链表可以充分利用内存空间，实现灵活的内存动态管理

单向链表

单向链表是链表中最简单的一种形式，它的每个节点包含两个域，信息域和链接域。这个链接域指向下一个节点，最后一个节点为空。

单链表的实现

# 实现单链表

class Node(object):
    """节点"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    """ 单链表"""
    def __init__(self, node=None):
        self._head = node


    def is_empty(self):
        """ 判断链表是否为空"""
        return self._head == None

    def length(self):
        """ 链表长度"""
        # cur游标
        cur = self._head
        # 计数
        count = 0

        while cur != None:
            count += 1
            cur = cur.next
        
        return count


    def travel(self):
        """ 遍历整个链表"""
        cur = self._head
        while cur != None:
            print(cur.elem)
            cur = cur.next


    def add(self, item):
        """ 链表头部添加元素"""
        node = Node(item) 
        node.next = self._head
        self._head = node

    def append(self, item):
        """ 链表尾部添加元素"""
        node = Node(item)

        if self.is_empty():
            self._head = node
            
            return

        cur = self._head
        while cur.next != None:
            cur = cur.next
        cur.next = node

    def insert(self, pos, item):
        """ 在指定位置添加元素"""

        if pos <= 0:
            self.add(item)
        if pos > self.length()-1:
            self.append(item)

        node = Node(item)

        pre = self._head
        count = 0
        while count < (pos-1):
            count += 1
            pre = pre.next
        node.next = pre.next    
        pre.next = node

    def remove(self, item):
        """ 删除节点"""
        cur = self._head
        pre = None

        while cur != None:
            if cur.elem == item:
                if cur == self._head:
                    self._head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
        

    def search(self, item):
        """ 查找节点是否存在"""

        cur = self._head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

单链表与顺序表对比

单向循环链表

实现原理同单链表，但需要注意尾节点与头节点之间的一些细节。

双向链表

栈

栈结构的实现

队列

双端队列

排序与搜索

稳定性：不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但稳定排序算法不会

冒泡排序

实现

def bubbleSort(alist):
    """冒泡排序"""
    n = len(alist)
    for j in range(n-1):
        for i in range(n-j-1):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]

if __name__ == "__main__":
    li = [54, 26, 77, 31, 44, 55, 20]
    bubbleSort(li)
    print(li)

选择排序

实现

def selectSort(alist):
    """ 选择排序"""
    n = len(alist)

    for i in range(n):
        for j in range(i, n):
            if alist[j] < alist[i]:
                alist[i], alist[j] = alist[j], alist[i]

if __name__ == "__main__":
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    selectSort(li)
    print(li)

插入排序

实现

def insertSort(alist):
    """ 插入排序"""
    n = len(alist)
    for j in range(1, n):
        i = j
        
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break

快速排序

实现

def quick_sort(alist, first, last):
    """ 快速排序"""
    if first >= last:
        return

    # n = len(alist)
    mid_value = alist[0]
    low = first
    high = last

    while low < high:
    
        while low < high and alist[high] > mid_value:
            high -= 1
        alist[low] = alist[high]

        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
    alist[low] = mid_value
    
    quick_sort(alist, first, low-1)
    quick_sort(alist, low+1, last)

希尔排序

def shellSort(alist):
    """ 希尔排序"""
    n = len(alist)
    gap = n//2

    while gap > 0:
        for j in range(gap, n):
            i = j
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                else:
                    break
        gap //= 2

归并排序

def mergeSort(alist):
    """ 归并排序"""
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2

    left_li = mergeSort(alist[:mid])
    right_li = mergeSort(alist[mid:])

    left_pointer, right_pointer = 0, 0
    result = []

    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result

常见排序算法比较

搜索

二分法查找

实现

• 递归版本

def binary_search(alist, item):
    """ 二分查找"""
    n = len(alist)
    if n > 0:
        mid = n//2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            return binary_search(alist[:mid], item)
        else:
            return binary_search(alist[mid+1], item)
        return False

• 非递归版本

def binary_search(alist, item):
    """ 二分查找"""
    n = len(alist)
    first = 0
    last = n-1
    while first <= last:
        mid = (first + last)//2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            last = mid -1
        else:
            first = mid + 1
    return False

时间复杂度

最优时间复杂度：O(1)

最坏时间复杂度：O(logn)

树

树的存储与表示

二叉树

二叉树性质

完全二叉树

若二叉树高度为h，除第h层外，其它各层节点数均为最大，h层有叶子节点，且节点从左到右一次排布，这就是完全二叉树。

二叉树遍历

由遍历确定一棵树

必须有两个序列，且其中一个为中序序列，便可通过通过这两个序列还原二叉树

树的实现

class Node(object):
    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.rchild = None

class Tree(object):
    """二叉树"""
    def __init__(self):
        self.root = None

    def add(self, item):
        """ 添加节点"""
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    # 广度优先遍历
    def breadth_travel(self):
        """ 广度优先遍历"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem)
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    # 深度优先遍历
    def preorder(self, node):
        """ 先序遍历"""
        if node is None:
            return
        print(node.elem, end=" ")
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        """ 中序遍历"""
        if node is None:
            return
        self.preorder(node.lchild)
        print(node.elem, end=" ")
        self.preorder(node.rchild)

    def postorder(self, node):
        """ 后序遍历"""
        if node is None:
            return
        self.preorder(node.lchild)
        self.preorder(node.rchild)
        print(node.elem, end=" ")

打赏