基本的数据结构和算法

算法

常用的数据结构

队列

class Queue(object):
    def __init__(self):
        self.queue = []

    def push(self, item):
        self.queue.append(item)

    def pull(self):
        self.queue.pop(0)

    def size(self):
        return len(self.queue)

    def first(self):
        return self.queue[-1]

    def end(self):
        return self.queue[0]

栈

class Stack(object):

    def __init__(self):
        self.stack = []

    def top(self):
        return self.stack[-1]

    def push(self, item):
        self.stack.append(item)

    def pull(self):
        """出栈"""
        return self.stack.pop()

    def size(self):
        return len(self.stack)


if __name__ == '__main__':
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    print(s.stack)

    s.pull()
    print(s.stack)

链表

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None

class chain:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return not self.head

    def length(self):
        count = 0
        cur = self.head
        while cur != None:
            count += 1
            cur = cur.next

        return count

    def add(self,data):
        node = Node(data)
        node.next = self.head
        self.head = node

    def append(self,data):
        cur = self.head
        while cur.next != None:
            cur = cur.next
        node = Node(data)
        cur.next = node

    def traverse(self):
        cur = self.head
        while cur != None:
            print(cur.data, end='-***-')
            cur = cur.next
        print()

    def insert(self,index,data):

        if index < 0:
            self.add(data)
        elif index > self.length() -1:
            self.append(data)
        else:
            cur = self.head
            for i in range(index - 1):
                cur = cur.next

            node = Node(data)
            node.next = cur.next
            cur.next = node

    def remove(self, data):
        cur = self.head
        pre = None
        while cur != None:
            if cur.data == data:
                if cur == self.head:
                    self.head = self.head.next
                    return
                pre.next = cur.next #前节点等于后节点
                return
            pre = cur
            cur = cur.next

    def search(self, data):
        cur = self.head
        while cur != None:
            if cur.data == data:
                print("数据%f存在于链表中" % cur.data)
                return True
            cur = cur.next
        print("数据不存在于链表中")
        return False

递归

递归就是不断调用函数本身

阶乘 1 * 2 * 3....*N

def rescuvie(n):
    if n == 1:
        return 1
    return n * rescuvie(n-1)

递归使用了运算符，每次重复的调用都使得运算的链条不断加长，系统不得不使用栈进行数据保存和恢复
如果每次递归都要对越来越长的链条进行运算，那速度极慢，并且可能栈溢出，导致程序崩溃

尾递归

尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算，效率将会极大的提高。

def rescurieTail(n, a):
    if n == 1:
        return a
    return rescurieTail(n-1, a*n)

排序算法

https://blog.csdn.net/weixin_42702038/article/details/106744386

选择排序

首先在未排序的序列中找到最小（大）元素，存放在排序序列的起始位置，然后在剩余的列表中查找，依次放入到新列表中。

# 找出最小元素
def find_smallest_item(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index


# 选择排序
def select_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        smallest_index = find_smallest_item(arr)
        new_arr.append(arr.pop(smallest_index))

    return new_arr


if __name__ == '__main__':
    print(select_sort([4, 324, 42, 45, 2435, 2, 2]))

快速排序

分而治之的思想

# 快速排序

def quick_sort(arr):
    # 基准的选择
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]

        less_arr = [i for i in arr[1:] if i <= pivot]
        greater_arr = [i for i in arr[1:] if i > pivot]

        return quick_sort(less_arr) + [pivot] + quick_sort(greater_arr)


if __name__ == '__main__':
    print(quick_sort([2, 3, 49, 10, 24, 3]))

冒泡排序

冒泡排序思想：遍历整个数据列表，在一组数据中，每遍历比较一次数据，最大的数便会”冒泡”到数据列表右端

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

二分查找

def binaray_search(li, item):
    low = 0
    high = len(li) - 1

    while low <= high:  # 确定范围
        mid = (low + high) // 2
        guess = li[mid]
        if guess == item:
            return mid
        elif guess > item:
            high = mid - 1
        else:
            low = mid + 1


if __name__ == '__main__':
    print(binaray_search([1, 2, 3, 4, 5, 6], 6))