【算法导论】基本数据结构

1.栈和队列

栈和队列都是动态集合，栈实现的是一种后进先出的策略，队列实现的是先进先出的策略。

栈

栈的insert操作称为压入（push），delete操作称为弹出（pop）。

出入栈以及判断空栈操作：

class Stack():
    def __init__(self):
        self.stack = []
        self.top = -1
        pass

    def push(self, i):
        self.stack.append(i)
        self.top += 1

    def pop(self):
        assert self.top != -1, 'stack empty'
        num = self.stack.pop()
        self.top -= 1
        return num

    def is_empty(self):
        """
        判断是否为空
        :return:
        """
        if self.top == -1:
            return True
        else:
            return False
        pass

    def print(self):
        """
        打印栈
        :return:
        """
        print(self.stack)

队列

队列上的insert称为入队（enqueue），delete操作称为出队（dequeue）。

队列有对头和队尾。

入队、出队、以及判断为空的操作：

class Queue():
    def __init__(self):
        self.queue = [0 for _ in range(10)]
        self.head = 0
        self.tail = -1
        pass

    def enqueue(self, i):
        """
        入队
        :param i:
        :return:
        """
        self.tail += 1
        self.queue[self.tail] = i

    def dequeue(self):
        """
        出队
        :return:
        """
        self.head += 1
        return self.queue[self.head - 1]

    def is_empty(self):
        """
        判断空
        :return:
        """
        if self.head == self.tail + 1:
            return True
        else:
            return False

2.链表

链表即各元素之间通过一条链（地址）相连。如下图（下图是双向链表）

同时为了方便对第一个链和后面的链的操作，我们引入哨兵机制（sentinel），如图为带哨兵的双向循环链表。

下面是双循环链表的查询、插入和删除代码：

class LinklistMine():
    def __init__(self):
        self.first = Point()
        self.first.prev = self.first
        self.first.next = self.first
        pass

    def list_search(self, k):
        """
        抄找链表中的k元素
        :param k:
        :return:
        """
        p = self.first.next
        while p.value != k:
            if p is not self.first:
                p = p.next
            else:
                return 'Null'
        return k

    def list_insert(self, value):
        """
        插入value
        :param value:
        :return:
        """
        # 设置新节点
        p = Point()
        p.set_value(value=value)
        # 连接到链表中
        point = self.first.prev
        p.prev = point
        point.next = p
        self.first.prev = p
        p.next = self.first
        pass

    def list_delete(self, k):
        """
        删除k
        :param k:
        :return:
        """
        p = self.first.next
        while p.value != k:
            if p is not self.first:
                p = p.next
        # 删除p
        p.prev.next = p.next
        p.next.prev = p.prev
        pass

    def print(self):
        """
        打印
        :return:
        """
        if self.first.next is self.first:
            print('linklist empty')
            return
        print('linklist:', end='')
        point = self.first.next
        while point is not self.first:
            print(point.value, ' ', end='')
            point = point.next
        print()


class Point():
    def __init__(self):
        self.prev = None
        self.value = None
        self.next = None

    def link_prev(self, point):
        """
        连接prev
        :param point:
        :return:
        """
        self.prev = point

    def link_next(self, point):
        """
        连接next
        :param point:
        :return:
        """
        self.next = point

    def set_value(self, value):
        """
        设置值
        :param value:
        :return:
        """
        self.value = value

3.有根树的表示

二叉树

如下图，分为左右子树（left与right指针）和根（value）

分支无限制的有根数

我们采用左孩子右兄弟表示法，即left指针连接的是孩子，right指针连接的是兄弟。如下图：