python进阶-08-数据结构

1 概念

算法不关注处理何种数据,数据结构关注的是如何组织数据
比如可以使用列表嵌套元组保存学生信息,也可使用列表嵌套字典,或者字典嵌套字典(学号作为key,其他作为value)
如果使用列表保存,需要循环根据学号判断
如果使用字典保存,可以直接根据学号的key获取

2 顺序表

顺序表,存储空间连续

2.1 插入元素

尾部插入,保序插入(当前位置到末尾所有元素后移),非保序插入(当前元素移至末尾+1)
python中的list就是保序的线性表

2.2 测试insert和append的执行效率

timeit模块可以测试代码效率

# coding=utf-8
from timeit import Timer


def append_test():
    li = []
    for i in range(10000):
        li.append(i)


def insert_test():
    li = []
    for i in range(10000):
        li.insert(0,i)


append_timer = Timer('append_test()', 'from __main__ import append_test')
print('append插入执行时间', append_timer.timeit(1000))
insert_timer = Timer('insert_test()', 'from __main__ import insert_test')
print('insert插入执行时间', insert_timer.timeit(1000))

测试结果

append插入执行时间 1.1257968
insert插入执行时间 41.978182499999996

3 链表

链表存储空间非连续,可以充分利用计算机空间
每个节点保存下一元素的地址
链表插入元素更加灵活

3.1 单向链表

# coding=utf-8


# 节点类
class Node(object):
    def __init__(self, elem):
        # elem指数据元素
        self.elem = elem
        # 指向下一个节点
        self.next = None


# 单向链表类
class SingleLinkList(object):
    def __init__(self, node=None):
        # 判断node是否为空
        if node != None:
            headNode = Node(node)
            self.__head = headNode
        else:
            self.__head = node

    # 头部添加元素
    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
        else:
            curNode = self.__head
            # 遍历得到最后节点
            while curNode.next != None:
                curNode = curNode.next
            curNode.next = node

    # 指定位置添加元素
    def insert(self,pos,item):
        # 如果pos<0,默认插入头部
        if pos <= 0:
            self.add(item)
        # 如果pos值大于链表长度,默认插入尾部
        elif pos > self.length()-1:
            self.append(item)
        else:
            node = Node(item)
            count = 0
            preNode = self.__head
            while count<(pos-1):
                count += 1
                preNode = preNode.next
            # 修改指向
            node.next = preNode.next
            preNode.next = node



    # 删除元素
    def remove(self, item):
        preNode = None
        curNode = self.__head
        while curNode != None:
            if curNode.elem == item:
                # 判断是否是头节点
                if preNode == None:
                    # 删除头节点
                    self.__head = curNode.next
                else:
                    # 删除
                    preNode.next = curNode.next
                break
            else:
                preNode = curNode
                curNode = curNode.next


    # 查找节点是否存在
    def search(self, item):
        curNode = self.__head
        while curNode != None:
            if curNode.elem == item:
                return True
            curNode = curNode.next
        return False

    # 判断链表是否为空
    def is_empty(self):
        # 判断head是否为None
        return self.__head == None

    # 计算链表长度
    def length(self):
        count = 0
        # 当前节点
        curNode = self.__head
        while curNode != None:
            count += 1
            # 当前节点指向下一节点
            curNode = curNode.next
        return count

    # 遍历
    def travel(self):
        curNode = self.__head
        print('遍历:', end='\t')
        while curNode != None:
            print(curNode.elem, end='\t')
            curNode = curNode.next
        print()

# 测试
if __name__ == '__main__':
    # 初始化一个元素值为20的单向链表
    singleLinkList = SingleLinkList(20)
    # 初始化一个空的的单向链表
    singleLinkList2 = SingleLinkList()
    print('判断链表是否为空:', singleLinkList.is_empty())
    print('链表长度:', singleLinkList.length())
    singleLinkList.travel()
    print('查找:', singleLinkList.search(20))
    singleLinkList.add(1)
    singleLinkList.add(2)
    singleLinkList.add(3)
    singleLinkList.travel()
    singleLinkList.append(4)
    singleLinkList.travel()
    singleLinkList2.append(4)
    singleLinkList2.travel()
    singleLinkList.insert(2, 100)
    singleLinkList.travel()
    singleLinkList.insert(-1, 200)
    singleLinkList.travel()
    singleLinkList.insert(100, 300)
    singleLinkList.travel()
    singleLinkList.remove(200)
    singleLinkList.travel()
    singleLinkList.remove(300)
    singleLinkList.travel()

3.2 链表\顺序表对比

存储空间,不连续\连续
链表由于添加了指针域,空间开销比较大
链表便于修改,顺序表便于查询

3.3 双向链表

每个节点存储前驱和后继节点
双向链表初始化\查找\判断是否为空\计算长度\遍历方法与单向链表相同

# coding=utf-8


# 双向链表节点类
class Node:
    def __init__(self,elem):
        self.elem = elem
        # 后继
        self.next = None
        # 前驱
        self.prev = None


class DoubleLinkList:
    # 初始化方法
    def __init__(self, node=None):
        # 判断node是否为空
        if node != None:
            headNode = Node(node)
            self.__head = headNode
        else:
            self.__head = node

    # 头部添加元素
    def add(self, item):
        node = Node(item)
        # 判断是否为空链表
        if self.is_empty():
            self.__head = node
        else:
            node.next = self.__head
            self.__head.prev = node
            self.__head = node

    # 尾部追加元素
    def append(self, item):
        node = Node(item)
        # 如果是空链表
        if self.is_empty():
            self.__head = node
        else:
            curNode = self.__head
            # 遍历得到最后节点
            while curNode.next != None:
                curNode = curNode.next
            node.prev = curNode
            curNode.next = node

    # 指定位置添加元素
    def insert(self,pos,item):
        # 如果pos<0,默认插入头部
        if pos <= 0:
            self.add(item)
        # 如果pos值大于链表长度,默认插入尾部
        elif pos > self.length()-1:
            self.append(item)
        else:
            node = Node(item)
            count = 0
            curNode = self.__head
            while count<(pos-1):
                count += 1
                curNode = curNode.next
            # node的前驱指向当前节点
            node.prev = curNode
            # node的后继指向当前节点的下一节点
            node.next = curNode.next
            # 当前节点下一节点的前驱指向node节点
            node.next.prev = node
            # 当前节点后继指向node节点
            curNode.next = node



    # 删除元素
    def remove(self, item):
        curNode = self.__head
        while curNode != None:
            if curNode.elem == item:
                # 判断是否是头节点
                if curNode == self.__head:
                    # 删除头节点
                    self.__head = curNode.next
                    # 判断当前节点是否只有一个节点
                    if curNode.next:
                        curNode.next.prev = None
                else:
                    # 删除
                    curNode.prev.next = curNode.next
                    # 如果当前节点是最后节点,则下一节点没有前驱
                    if curNode.next:
                        curNode.next.prev = curNode.prev
                break
            else:
                curNode = curNode.next


    # 查找节点是否存在
    def search(self, item):
        curNode = self.__head
        while curNode != None:
            if curNode.elem == item:
                return True
            curNode = curNode.next
        return False

    # 判断链表是否为空
    def is_empty(self):
        # 判断head是否为None
        return self.__head == None

    # 计算链表长度
    def length(self):
        count = 0
        # 当前节点
        curNode = self.__head
        while curNode != None:
            count += 1
            # 当前节点指向下一节点
            curNode = curNode.next
        return count

    # 遍历
    def travel(self):
        curNode = self.__head
        print('遍历:', end='\t')
        while curNode != None:
            print(curNode.elem, end='\t')
            curNode = curNode.next
        print()


# 测试
if __name__ == '__main__':
    doubleLinkList = DoubleLinkList()
    doubleLinkList.add(20)
    doubleLinkList.add(21)
    doubleLinkList.travel()
    doubleLinkList.append(22)
    doubleLinkList.travel()
    doubleLinkList.insert(1, 19)
    doubleLinkList.travel()
    doubleLinkList.remove(21)
    doubleLinkList.travel()
    doubleLinkList.remove(20)
    doubleLinkList.travel()
    doubleLinkList.remove(22)
    doubleLinkList.travel()
    print('链表长度:', doubleLinkList.length())
    print('查找元素:', doubleLinkList.search(19))
    print('查找元素:', doubleLinkList.search(20))

4 栈

栈由链表或顺序表实现
栈只关心操作的实现->后进先出

# coding=utf-8


class Stack():
    def __init__(self):
        self.__list = []

    # 压栈
    def push(self, item):
        self.__list.append(item)

    # 弹出元素
    def pop(self):
        return self.__list.pop()

    # 返回栈顶元素
    def peek(self):
        return self.__list[len(self.__list)-1]

    # 判断栈是否为空
    def is_empty(self):
        return self.__list == []

    # 计算栈的大小
    def size(self):
        return len(self.__list)


if __name__ == '__main__':
    stack = Stack()
    print('是否空栈:', stack.is_empty())
    # 压栈
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print('栈长度:', stack.size())
    # 弹出
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

5 队列

先进先出

# coding=utf-8


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

    # 进队
    def enqueue(self, item):
        # 进队频繁用append,出队频繁用insert
        self.__list.insert(0, item)

    # 出队
    def dequeue(self):
        return self.__list.pop()

    # 判断队列是否为空
    def is_empty(self):
        return self.__list == []

    # 计算队列大小
    def size(self):
        return len(self.__list)


if __name__ == '__main__':
    queue = Queue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    print(queue.is_empty())
    print(queue.size())
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())

6 树

每个节点由0或多个子节点
没有父节点的为根节点
非根节点只有一个父节点
每个字节点可以分为多个不相交的子树

6.1 概念及应用场景

度

节点的子节点的数目

树的度

最大节点的度

有序树

任意节点间有顺序关系

二叉树

每个节点最多有两个子树

完全二叉树

除最后一层外其他节点数目达到最大

满二叉树

最后一曾节点数达到最大

平衡二叉树

任意节点两颗子树高度差不大于1

排序二叉树

每个节点左侧小于该节点,右侧大于该节点

应用场景:

html\xml\mysql索引\路由协议\文件系统目录,以及一些AI算法如决策树

6.2 二叉树

第n层至多2^(n-1)个节点