第一章 线性表

数据结构可视化：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
https://visualgo.net/en
Python可视化
https://pythontutor.com/

程序, 等于数据结构与算法. 在本标签下, 会讲述有关于数据结构 (逻辑结构, 存储结构和运算) 的基本知识. 逻辑结构分为线性结构 (线性表) 和非线性结构 (树, 与图) 的讲述. 存储结构包括 (顺序存储, 链式存储, 索引存储与散列存储) . 而有关于处理这些数据的基本技术即运算则 (如查找于排序) 在算法标签下讲述.

1. 线性表

线性表是指由有限个同类元素组成的, 且相邻元素之间有序偶关系.

2. 线性表的存储

线性表的存储有顺序存储和链表存储两种方式.
顺序存储按顺序依次存储, 列表和元组可以实现顺序表.
链表存储除了原有的数据外, 还有存放后继元素地址的指针域.
顺序表的操作会引起大量数据移动, 效率很低, 根本原因是数据的逻辑关系是通过物理关系来表示的; 链式存储不要求物理上相邻 (毕竟指针也不是吃干饭的) , 这就使链表相比顺序表效率更高.

3. 线性表的操作

1) 顺序表操作

参阅列表与元组的操作即可.

3. 单链表操作

点击显/隐线性表的操作

class Node:
    """节点类, 有一个参数"""

    def __init__(self, node):
        self.node = node  # 参数 1: 用于接收节点
        self.next = None  # 指针域, 初始化为空, 该指针域代表后继元素的地址信息


class SingleLinkList:
    def __init__(self, node=None):
        self.__head = node  # 将接收到的节点传入头节点, 若未指定, 默认为空

    def is_empty(self):
        """判断是否为空"""
        return self.__head == None  # 若头节点为空, 返回 True, 反之则反

    def length(self):
        """获取链表长度"""
        cur, count = self.__head, 0  # cur 游标, 用来遍历节点, count 计数器
        while cur != None:  # 当节点不为空, 即遍历未完时
            count, cur = count + 1, cur.next  # 计数器 +1, 游标移向下一个节点
        return count  # 返回计数结果

    """
    得: 下代码是遍历全局所需代码
    cur = self.__head    # cur 游标, 用来遍历节点
        while cur != None:    # 当节点不为空, 即遍历未完时
            cur = cur.next    # 游标移向下一个节点
    """

    def add(self, node):
        """增 - 头插法"""
        new_node = Node(node)  # 将新元素传递到节点里, 用 new_node 接收
        # 将原本的头节点赋给该节点的指针域, 将新节点赋给已经空下来的头节点
        new_node.next, self.__head = self.__head, new_node

    def append(self, node):
        """增 - 尾增法 1.0"""
        cur, new_node = self.__head, Node(node)  # cur 游标, 用来遍历节点, 将新元素传递到节点里, 用 new_node 接收
        while cur != None:  # 当节点不为空, 即遍历未完时
            cur = cur.next  # 游标移向下一个节点
        cur.next = new_node  # 最后一个节点的指针域存放该新增节点

    def append(self, node):
        """增 - 尾增法 2.0, 在原有基础上添加了判定列表为空的情况"""
        cur, new_node = self.__head, Node(node)  # cur 游标, 用来遍历节点, 将新元素传递到节点里, 用 new_node 接收
        if self.__head == None:  # 如果节点为空
            self.__head = new_node  # 将该节点添加到头节点里
        else:
            while cur.next != None:  # 当节点指针域不为空, 即遍历未完时
                cur = cur.next  # 游标移向下一个节点
            cur.next = new_node  # 最后一个节点的指针域存放该新增节点

    def insert(self, index, node):
        """增 - 指定下标位置插入"""
        if index <= 0:  # 若下标小于 0, 按头插法插入
            self.add(node)
        elif index > self.length() - 1:  # 若下标大于长度减一, 按尾增法插入
            self.append(node)
        else:
            cur, count, new_node = self.__head, 0, Node(node)  # cur 游标, count 计数器, new_node 新节点
            while count != index - 1:  # 当计数的下标不为所指定下标减一, 即所需要插入的下标前一个数据时, 进行循环
                count, cur = count + 1, cur.next  # 计数加一, 游标移向下一个节点
            new_node.next, cur.next = cur.next, new_node  # 将新节点赋给游标的下一个节点, 原游标的指针域赋给新节点的指针域

    def remove(self, node):
        """删除节点 1.0"""
        # 遍历, 若遍历的某个节点与需要删除的节点相同, 将需要删除的节点的指针域赋给需要删除的节点的上一个节点的指针域
        cur, prior = self.__head, None  #
        while cur.node != node:  # 当遍历的逐个元素不等于需要删除的节点的话
            prior, cur = cur, cur.next  # 将原有的 cur 移至 prior, cur.next 移至 cur, 等于全体向前挪动一格
        else:  # 但若遍历的这个元素恰好等于需要删除的这个节点的话
            prior.next = cur.next  # 本来 prior应该指向 cur, 但现在应该将这一节点跳过去, 所以直接指向 cur.next

    def remove(self, node):
        """删除节点 2.0, 增加了考虑删除的节点是否为头节点, 并在第四行改变了代码使得"""
        cur, prior = self.__head, None  #
        while cur != None:  # 全局遍历
            if cur.node != node:  # 当遍历的逐个元素不等于需要删除的节点的话
                prior, cur = cur, cur.next  # 将原有的 cur 移至 prior, cur.next 移至 cur, 等于全体向前挪动一格
            else:  # 但若遍历的这个元素恰好等于需要删除的这个节点的话
                if cur == self.__head:  # 如果一开始扫描到的就是头节点
                    self.__head = cur.next  # 本来头节点应该对等 cur, 但现在应该将这一节点跳过去, 所以直接指向 cur.next
                else:
                    prior.next = cur.next  # 本来 prior 应该指向 cur, 但现在应该将这一节点跳过去, 所以直接指向 cur.next
                break

    def search(self, node):
        """查询节点是否存在"""
        cur = self.__head  # 游标, 遍历全局
        while cur != None:  #
            if cur.node == node:  # 如果此刻游标的节点与需要查找的节点相同, 那么返回 True
                return True
            else:
                cur = cur.next  # 否则游标移向下一个节点
        return False  # 直到遍历结束若无则返回 False

    def travel(self):
        """遍历节点"""
        cur = self.__head
        while cur != None:
            print(cur.node, end=" ")
            cur = cur.next
        print()


if __name__ == "__main__":
    node = Node(5)
    list = SingleLinkList(node)
    print(list.is_empty())
    print(list.length())
    list.append(3)
    list.add(999)
    list.insert(-3, 110)
    list.insert(99, 111)
    print(list.is_empty())
    print(list.length())
    list.travel()
    list.remove(110)
    list.travel()

2. 栈

栈是一种增删操作都在表尾 (称栈顶) 操作的线性表. 具有先进后出的特性.

点击显/隐栈的操作

class Stack(object):
    """栈类, 由函数 push() 与 pop() 可知栈的元素为后进先出"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        """判断是否为空"""
        return self.items == []    # 当空列表时返回 True, 反之则反

    def length(self):
        """获取栈长度"""
        return len(self.items)    # len() 函数获取列表长度

    def push(self, item):
        """入栈"""
        self.items.append(item)    # 尾部追加

    def pop(self):
        """出栈"""
        return self.items.pop()    # 尾部弹出

    def peek(self):
        """获取栈顶元素"""
        return self.items[len(self.items) - 1]    # 栈顶元素为列表最后一个元素


if __name__ == "__main__":
    stack = Stack()
    print(stack.is_empty()); print(stack.length())    # 无元素, 列表为空, 返回 True, 长度为 0
    stack.push(1); print(stack.peek())    # 1 入栈, 此刻栈顶元素为 1
    stack.push(2); print(stack.peek())    # 2 入栈, 此刻栈顶元素为 2
    stack.push(3); print(stack.peek())    # 3 入栈, 此刻栈顶元素为 3
    print(stack.items)    # 获取此刻栈所有元素: [1, 2, 3]
    print(stack.is_empty()); print(stack.length())  # 3 元素, 列表不为空, 返回 False, 长度为 3
    stack.pop(); print(stack.peek())    # 3 出栈, 此刻栈顶元素为 2
    stack.pop(); print(stack.peek())    # 2 出栈, 此刻栈顶元素为 1
    stack.pop()    # 全部出栈
    print(stack.is_empty()); print(stack.length())    # 列表为空, 返回 True, 长度为 0

3. 队列

队列经典例子是 “排队” , 但刚好与其相反. 队列的插入采用头插法, 删除采用尾删法.

点击显/隐队列的操作

class Queue:
    """队列类, 由函数 en() 与 de() 可知队列为先进先出"""
    def __init__(self):
        self.items = []

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

    def length(self):    # 获取队列长度
        return len(self.items)

    def en(self, items):
        """入队"""
        self.items.insert(0, items)    # 头插法

    def de(self):
        """出队"""
        return self.items.pop()    # 尾部删除


if __name__ == "__main__":
    queue = Queue()
    print(queue.is_empty()); print(queue.length())    # 无元素, 列表为空, 返回 True, 长度为 0
    queue.en(1)    # 1 入队, 此刻队列元素为 [1]
    queue.en(2)    # 2 入队, 此刻队列元素为 [2, 1]
    queue.en(3)    # 3 入队, 此刻队列元素为 [3, 2, 1]
    print(queue.de())    # 1 出队, 此刻队列元素为 [3, 2]
    print(queue.de())    # 2 出队, 此刻队列元素为 [3]
    print(queue.de())    # 3 出队, 此刻队列无元素
    print(queue.is_empty()); print(queue.length())    # 全部出队, 列表为空, 返回 True, 长度为 0

4. 字符串

字符串是由 n 多字符组成的有限序列.

点击显/隐字符串的操作

class String:
    def __init__(self):
        self.items = ""
    def is_empty(self):
        return self.items == ""
    def length(self):
        return len(self.items)
    def CreatString(self):
        """创造字符串"""
        str = input('please input string: ')
        self.items = str
    def ConcatString(self, need_concat_str):
        """连接字符串"""
        self.items = self.items + need_concat_str
    def SubString(self, index, length):
        """获取字串"""
        print(self.items[index:index + length])
if __name__ == "__main__":
    string = String()
    print(string.is_empty())
    print(string.length())
    string.CreatString()
    string.ConcatString("123")
    print(string.length())
    print(string.items)
    string.SubString(1, 4)

5. 综合案例

1. 模式匹配

给定一个子串, 要求在字符串中找到与子串相同的所有子串, 如在 “BBC ABCDAB ABCDABCDABDE” 中找到 “ABCDABD” .

a. 点击显/隐 BF 算法的代码

# BF (Brute Force) 算法,
def BF(String, SubString, begin_index = 0):
    """
    Brute Force 算法, 我称它为暴力算法.
    将子串的第一个字符与目标串进行匹配, 若不一样则跳过, 若一样则继续比较第二个, 第三...直至完全匹配
    :param String: 需要被匹配的字符串
    :param SubString: 需要进行匹配的子串
    :param begin_index: 需要匹配的起始长度, 默认为 0
    :return: 返回匹配成功的起始下标, 若匹配不成功, 返回 😶
    """
    i, j = begin_index, 0    # 默认i = 0, j = 0
    while i < len(String) - 1 and j <= len(SubString) - 1:    # 仅当字符串及其子串的下标 i 不大于其本身的下标时, 进行循环
        if String[i] == SubString[j]:    # 如果字符相同
            i, j = i + 1, j + 1    # 两者均往后一格, 继续判断下一个字符
        else:    # 如果字符不相同
            i, j = i - j + 1, 0    # i 应该回滚 i - j , 再往后一格重新进行匹配, j 重新初始化
    if j > len(SubString) - 1:    # 如果 j (子串的下标) 大于子串的下标长度,
        return i - len(SubString)    # 返回匹配成功的起始下标
    else:
        return "😶‍"
if __name__ == "__main__":
    s1 = "BBC ABCDAB ABCDABCDABDE"
    s2 = "ABCDABD"
    print(BF(s1,s2))

b. 点击显/隐 KMP 算法的代码 [未完成]

def get_next(String):
    """部分匹配函数"""
    next, i, j = [-1] * len(String), 0, -1  # 要返回的 next 数组和分别指向主串和一开始指向模式串的指针
    while i < len(String) - 1:  # next[0] = -1, 只需求后面的 m-1 个值即可
        if j == -1 or String[i] == String[j]:
            i, j = i + 1, j + 1    # 当匹配成功时, 往下继续匹配
            # next[i] = j    # 将该行加个判断条件, 改为下面四行
            if String[i] == String[j]:    # 如果字符重复则跳过, 这样若 AAAAB, 直接可从第四个 A 开始判断
                next[i] = next[j]
            else:
                next[i] = j
        else:  # 匹配不成功则在前面的子串中继续寻找, 直至找不到
            j = next[j]
    return next


def kmp(String, SubString, begin_index=0):
    """
    KMP 算法则在上述的基础上做了些许改进. 具体体现在本函数的第 27 行与第 30 行.
    :param String: 需要被匹配的字符串
    :param SubString: 需要进行匹配的子串
    :param begin_index: 需要匹配的起始长度, 默认为 0
    :return: 返回匹配成功的起始下标, 若匹配不成功, 返回 😶
    """
    i, j = begin_index, 0  # 默认i = 0, j = 0
    while i < len(String) and j < len(SubString):  # 仅当字符串及其子串的下标 i 不大于其本身的下标时, 进行循环
        if String[i] == SubString[j] or j == -1:  # KMP 算法补充: 如果字符相同或 j == -1
            i, j = i + 1, j + 1  # 两者均往后一格, 继续判断下一个字符
        else:  # 如果字符不相同
            j = get_next(SubString)[j]  # KMP 算法补充: i 不需要回溯, j 获取跳跃点
    if j == len(SubString):  # 如果 j (子串的下标) 大于子串的下标长度,
        return i - j  # 返回匹配成功的起始下标
    else:
        return "😶‍"


if __name__ == '__main__':
    s1 = "BBC ABCDAB ABCDABCDABDE"
    s2 = "ABCDABDAFRDAHN"
    s3 = "AW ADCBASD AD ADSAABCDABD"
    s4 = "ABCDABD"
    print(get_next(s2))
    print(kmp(s1, s4))
    print(kmp(s2, s4))
    print(kmp(s3, s4))

2. 小猫钓鱼.

甲和乙在玩一个扑克游戏——小猫钓鱼。游戏规则：将一副扑克牌平均分成两份，每人拿一分。甲先拿出手中第一张扑克牌放在桌上，然后乙也拿出手中第一张扑克牌，并放在甲刚才打出的扑克牌的上面，两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，可将两张相同的牌及其中间所夹的牌全部拿走，并依次放到自己手中牌的末尾。当任意一人手中当牌出完时，游戏结束，对方获胜。

点击显/隐小猫钓鱼的代码

q1 = [1, 2, 3]  # 小猫钓鱼主程序，初始化，以各自三张牌为例分牌：甲方（q1）牌为1,2,3 乙方（q2）牌为2,5,1
q2 = [2, 5, 1]
s = []
"""
先分析一波: 玩家手牌为队列, 桌子为栈. 因此流程为 甲出队列 - 牌入栈 - 乙出队列 - 牌入栈
胜利结果为: 一人手牌为空
有个特殊情况: 若有相同牌, 需全部出栈并加入队列, 反之仅仅牌入栈
"""
i = 0  # 计数器, 用来记录是当前是谁出了牌


def pai_ru_zhan(n):
    global q1, q2, s, i
    i += 1
    if n in s:  # 若有相同牌
        s.append(n)  # 牌需先入栈
        if i % 2 == 1:  # 根据出牌计数器来判断是谁出的牌
            q1 = s[s.index(n):] + q1  # 将两数及其中间的牌全部出栈并加入队列
        else:
            q2 = s[s.index(n):] + q2  # 将两数及其中间的牌全部出栈并加入队列
        s = s[:s.index(n)]  # 牌被拿走后所剩下的牌
    else:  # 反之仅仅牌入栈
        s.append(n)


while True:
    pai_ru_zhan(q1.pop())  # 甲出队列后调用牌入栈函数
    pai_ru_zhan(q2.pop())  # 甲出队列后调用牌入栈函数
    if len(q1) == 0 or len(q2) == 0:  # 胜利结果为: 一人手牌为空
        if len(q1) > len(q2):
            print(f'胜利结果为: 甲胜利, 此刻甲手牌为{q1}, 乙手牌为{q2}, 桌上牌为{s}')
            break
        else:
            print(f'胜利结果为: 乙胜利, 此刻乙手牌为{q2}, 甲手牌为{q1}, 桌上牌为{s}')
            break