开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> Python知识库 -> 算法和数据结构 -> 正文阅读

[Python知识库]算法和数据结构

算法和数据结构

程序 = 算法 + 数据结构

在刷题的时候遇到数据结构知识不够，特来补充学习。

前言

开始学习数据结构。

1 抽象数据类型和面向对象编程

什么是抽象数据类型 ADT

实际上 python 内置的 list 就可以看成一种抽象数据类型。
ADT: Abstract Data Type，抽象数据类型，我们在组合已有的数据结构来实现一种新的数据类型， ADT 定义了类型的数据和操作。
我们以抽象一个背包(Bag) 数据类型来说明，背包是一种容器类型，我们可以给它添加东西，也可以移除东西，并且我们想知道背包里有多少东西。于是我们可以定义一个新的数据类型叫做 Bag.

例如：

class Bag:
    """ 背包类型 """
    pass

数据结构与算法–ADT
http://www.atjiang.com/data-structures-using-python-ADT/

2 数组和列表

2.1 数组 array

推荐你用 numpy.array

2.2 列表 list

1、列表操作平均时间复杂度
list[index] O(1)
list.append O(1)
list.insert O(n)
list.pop(index), default last element O(1)
list.remove O(n)

3 线性查找

3.1 实现线性表顺序存储的插入操作

def insertlist(L, i, item):
    n = len(L)
    if i < 0 or i > n:
        return False
    else:
        tempt_list = list(range(i - 1, n))
        # 采用从最后一位进行平移
        for j in tempt_list[::-1]:
            L[j + 1:j + 2] = [L[j]]
            # print(L)
        L[i - 1] = item
    return L


# 方法2：
def insert_list(L, i, item):
    n = len(L)
    if i < 0 or i > n:
        return False
    else:
        L.insert(i, item)
        return L


if __name__ == '__main__':
    L = [2, 6, 7, 8, 0]
    i = 2
    item = 99
    res = insertlist(L, i, item)
    print(res)

Python中list赋值时， L1=L 与 L1=L[:] 有什么区别？
严格的说，python没有赋值，只有名字到对象的绑定。所以L1=L是把L所指的对象绑定到名字L1上，而L2=L[:]则是把L通过切片运算取得的新列表对象绑定到L2上。前者两个名字指向同一个对象，后者两个名字指向不同对象。换句话说，L1和L是指的同一个东西，那么修改L1也就修改了L；L2则是不同的东西，修改L2不会改变L。注意这个引用的概念对于所有的东西都成立，例如容器内部存储的都是引用……
在这里插入图片描述
很容易理解了吧,

L1=L 意思是将L1也指向L的内存地址,

L1=L[:] 意思是, 复制L的内容并指向新的内存地址.

3.2 实现线性表顺序存储的删除操作

def delete_list(L, i):
    n = len(L)
    if i < 0 or i > n:
        return False
    else:
        # del L[i]
        for k in range(i-1, n - 1)[::1]:
            L[k] = L[k + 1]
            # print(L)
        L.pop()
    return L


if __name__ == '__main__':
    L = [2, 6, 7, 8, 1]
    i = 1
    res = delete_list(L, i)
    print(res)

# 4 排序基础 ## 4.1 冒泡排序冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

# -*- coding:utf-8 -*-
"""
冒泡算法：多次遍历列表，将不合顺序的进行交换，一轮遍历将最大值放在列表最后面，

"""
def sortBubble(alist):
    al=len(alist)-1
    while al>0:
        for i in range(al):
            if alist[i]>alist[i+1]:
                alist[i],alist[i+1]= alist[i+1],alist[i]
        al-=1
    return alist

if __name__ == "__main__":
    res= sortBubble([2,5,3,8,2,6,4])
    print(res)

针对有的列表有部分数据已经有序，不需要在进行判断，则对冒泡排序进行改进。

def optsortBubble(alist):
    al=len(alist)-1
    exchange=True
    while al>0 and exchange:
        exchange=False
        for i in range(al):
            if alist[i]>alist[i+1]:
                exchange = True
                alist[i],alist[i+1]= alist[i+1],alist[i]
        al-=1
    return alist

if __name__ == "__main__":
    res= optsortBubble([2,3,5,8,2,6,4])
    print(res)

4.2 选择排序

选择排序是在冒泡排序的基础上进行改进。每次遍历列表只进行一次交换。要实现这一点，选择排序每次遍历寻找最大值，并在遍历完成后将它放在正确的位置上。

.算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

# -*- coding:utf-8 -*-
"""
选择排序算法：多次遍历列表，一轮遍历将最大值放在列表最后面。并且每次缩小遍历的列表的大小。

"""
def optselectBubble(alist):
    al=len(alist)
    tempt=0
    while al>1:
        for i in range(0,al):
            if alist[i]>alist[tempt]:
                tempt=i
        alist[i],alist[tempt]= alist[tempt],alist[i]
        print(alist)
        al=al-1
        tempt=0
    return alist

if __name__ == "__main__":
    res= optselectBubble([2,5,1,3,8,2,6,4])
    print("最终结果：")
    print(res)```

通过每次记录最小值：

```python
#通过每次记录最小数值的索引
def select_sort(L):
    n=len(L)
    if n==0:
        return None
    for i in range(n-1):
        minindex=i
        for j in range(i+1,n):
            if L[j]<L[minindex]:
                minindex=j
        L[minindex],L[i]= L[i],L[minindex]
    return L



if __name__ == '__main__':
    L = [3,2, 6]
    res = select_sort(L)
    print(res)```

## 插入排序
![在这里插入图片描述](https://img-blog.csdnimg.cn/c21f16b150af4e4db274bbb2513b7d41.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAc2VhX2Jp,size_20,color_FFFFFF,t_70,g_se,x_16)

```python
#每次取一个数据与列表排序，保证前几个数据保证前面的数据已经排序好

def insertsortBubble(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        for i in range(index):
            if alist[i] > currentvalue:
                alist[i], alist[index] = alist[index], alist[i]

    return alist


if __name__ == "__main__":
    res = insertsortBubble([1, 2, 5, 1, 3, 8, 2, 6, 4])
    print(res)

4.2 插入排序

在这里插入图片描述

#每次取一个数据与列表排序，保证前几个数据保证前面的数据已经排序好

def insertsortBubble(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        for i in range(index):
            if alist[i] > currentvalue:
                alist[i], alist[index] = alist[index], alist[i]

    return alist


if __name__ == "__main__":
    res = insertsortBubble([1, 2, 5, 1, 3, 8, 2, 6, 4])
    print(res)

Java实现：

在这里插入图片描述

4.3 希尔排序

在这里插入图片描述
希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序的核心是对步长的理解，步长是进行相对比较的两个元素之间的距离，随着步长的减小，相对元素的大小会逐步区分出来并向两端聚拢，当步长为1的时候，就完成最后一次比较，那么序列顺序就出来了。
在这里插入图片描述

def shell_sort(items):
    """
    希尔排序
    :param items:
    :return:
    """
    n = len(items)
    step = n // 3
    print("++++1++++")
    print("step:" + str(step))
    while step > 0:
        for cur in range(step, n):
            i = cur
            while i >= step and items[i-step] > items[i]:
                print(i,i-step)
                items[i - step], items[i] = items[i], items[i-step]
                i -= step
        step = step // 3
        print("++++2++++")
        print("step:"+str(step))



if __name__ == "__main__":
    arr = [2, 5, 8, 0, 1, 4, 2, 7, 10, 67, 34]
    shell_sort(arr)
    n=len(arr)
    print("\n排序后:")
    for i in range(n):
        print(arr[i], end=",")

python代码演示，是从step到n,然后从后面跟前面比较

def shell_sort(items):
    """
    希尔排序
    :param items:
    :return:
    """
    n = len(items)
    step = n // 3
    print("++++1++++")
    print("step:" + str(step))
    while step > 0:
        for cur in range(step, n):
            i = cur
            print("i:"+str(i))
            while i >= step and items[i-step] > items[i]:
                print(i,i-step)
                items[i - step], items[i] = items[i], items[i-step]
                i -= step
        step = step // 3
        print("++++2++++")
        print("step:"+str(step))



if __name__ == "__main__":
    arr = [2, 5, 8, 0, 1, 4, 2, 7, 10, 67, 34,66,334,12,213,32,454,67,23,12,345]
    shell_sort(arr)
    n=len(arr)
    print("\n排序后:")
    print("n:"+str(n))
    for i in range(n):
        print(arr[i], end=",")

4.4 快速排序

快速排序采用分治策略。

快速排序是一种交换排序。

基本思想：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

详细的图解往往比大堆的文字更有说明力，所以直接上图：
在这里插入图片描述

public int division(int[] list, int left, int right) {
    // 以最左边的数(left)为基准
    int base = list[left];
    while (left < right) {
        // 从序列右端开始，向左遍历，直到找到小于base的数
        while (left < right && list[right] >= base)
            right--;
        // 找到了比base小的元素，将这个元素放到最左边的位置
        list[left] = list[right];

        // 从序列左端开始，向右遍历，直到找到大于base的数
        while (left < right && list[left] <= base)
            left++;
        // 找到了比base大的元素，将这个元素放到最右边的位置
        list[right] = list[left];
    }

    // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
    // 而left位置的右侧数值应该都比left大。
    list[left] = base;
    return left;
}

private void quickSort(int[] list, int left, int right){

    // 左下标一定小于右下标，否则就越界了
    if (left < right) {
        // 对数组进行分割，取出下次分割的基准标号
        int base = division(list, left, right);

        System.out.format("base = %d:\t", list[base]);
        printPart(list, left, right);

        // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        quickSort(list, left, base - 1);

        // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        quickSort(list, base + 1, right);
    }
}

python实现

def partition(arr,low,high): 
    i = ( low-1 )         # 最小元素索引
    pivot = arr[high]      #最末尾的数
  
    for j in range(low , high): 
  
        # 当前元素小于或等于 pivot 
        if   arr[j] <= pivot: 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 
  
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return i+1
  

def quickSort(arr,low,high): 
    if low < high: 
  
        pi = partition(arr,low,high) 
  
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 
  
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 
print ("排序后的数组:") 
for i in range(n): 
    print ("%d" %arr[i],end=",")

下面以数列a={30,40,60,10,20,50}为例，演示它的快速排序过程(如下图)。
在这里插入图片描述
上图只是给出了第1趟快速排序的流程。在第1趟中，设置x=a[i]，即x=30。

(01) 从"右 --> 左"查找小于x的数：找到满足条件的数a[j]=20，此时j=4；然后将a[j]赋值a[i]，此时i=0；接着从左往右遍历。

(02) 从"左 --> 右"查找大于x的数：找到满足条件的数a[i]=40，此时i=1；然后将a[i]赋值a[j]，此时j=4；接着从右往左遍历。

(03) 从"右 --> 左"查找小于x的数：找到满足条件的数a[j]=10，此时j=3；然后将a[j]赋值a[i]，此时i=1；接着从左往右遍历。

(04) 从"左 --> 右"查找大于x的数：找到满足条件的数a[i]=60，此时i=2；然后将a[i]赋值a[j]，此时j=3；接着从右往左遍历。

(05) 从"右 --> 左"查找小于x的数：没有找到满足条件的数。当i>=j时，停止查找；然后将x赋值给a[i]。此趟遍历结束！

按照同样的方法，对子数列进行递归遍历。最后得到有序数组！

def quick_sort(lists,i,j):
    if i >= j:
        return list
    pivot = lists[i]
    low = i
    high = j
    while i < j:
        while i < j and lists[j] >= pivot:
            j -= 1
        lists[i]=lists[j]
        while i < j and lists[i] <=pivot:
            i += 1
        lists[j]=lists[i]
    lists[j] = pivot
    quick_sort(lists,low,i-1)
    quick_sort(lists,i+1,high)
    return lists

if __name__=="__main__":
    lists=[30,24,5,58,18,36,12,42,39]
    print("排序前的序列为：")
    for i in lists:
        print(i,end =" ")
    print("\n排序后的序列为：")
    for i in quick_sort(lists,0,len(lists)-1):
        print(i,end=" ")

好了今天就学到这里。

4 链表(LinkList)

链表(LinkList)
数据存储在“节点(Node)”中，
节点包含的内容：数据和下一个节点的指针
链表额增删改查的时间复杂度全部是O(n)级别，但是在链表头的操作的时间复杂度是O(1)的
优点：真正的动态，不需要考虑容量的问题
缺点：丧失了随机访问的能力，因为每一个节点通过next指针穿插起来，不是连续存储的

和数组对比
数组最好用于索引有语意的情况。例如scores[2]
是线性结构
数组最大的优点：支持快速查询

链表不适合用于索引有语意的情况
不是线性结构
链表最大的优点：真正的动态，不浪费存储空间
在这里插入图片描述
定义节点：

class Node(object):
    """单链表的结点"""

    def __init__(self, item):
        # item存放数据元素
        self.item = item
        # next是下一个节点的标识
        self.next = None

定义链表：

#2. 定义链表
class SingleLinkList(object):
    """单链表"""

    def __init__(self):
        self._head = None

创建链表：

#创建链表
if __name__=="__main__":
    link_list=SingleLinkList()
    #创建节点
    node1=Node(1)
    node2=Node(2)
    
     # 将结点添加到链表
    link_list._head = node1
    # 将第一个结点的next指针指向下一结点
    node1.next = node2

    # 访问链表
    print(link_list._head.item)  # 访问第一个结点数据
    print(link_list._head.next.item)  # 访问第二个结点数据

在这里插入图片描述

class Node(object):
    """单链表的结点"""

    def __init__(self, item):
        # item存放数据元素
        self.item = item
        # next是下一个节点的标识
        self.next = None


class SingleLinkList(object):
    """单链表"""

    def __init__(self):
        self._head = None

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

    def length(self):
        """链表长度"""
        # 初始指针指向head
        cur = self._head
        count = 0
        # 指针指向None 表示到达尾部
        while cur is not None:
            count += 1
            # 指针下移
            cur = cur.next
        return count

    def items(self):
        """遍历链表"""
        # 获取head指针
        cur = self._head
        # 循环遍历
        while cur is not None:
            # 返回生成器
            yield cur.item
            # 指针下移
            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():
            # 空链表，_head 指向新结点
            self._head = node
        else:
            # 不是空链表，则找到尾部，将尾部next结点指向新结点
            cur = self._head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def insert(self, index, item):
        """指定位置插入元素"""
        # 指定位置在第一个元素之前，在头部插入
        if index <= 0:
            self.add(item)
        # 指定位置超过尾部，在尾部插入
        elif index > (self.length() - 1):
            self.append(item)
        else:
            # 创建元素结点
            node = Node(item)
            cur = self._head
            # 循环到需要插入的位置
            for i in range(index - 1):
                cur = cur.next

            node.next = cur.next
            cur.next = node

    def remove(self, item):
        """删除节点"""
        cur = self._head
        pre = None
        while cur is not None:
            # 找到指定元素
            if cur.item == item:
                # 如果第一个就是删除的节点
                if not pre:
                    # 将头指针指向头节点的后一个节点
                    self._head = cur.next
                else:
                    # 将删除位置前一个节点的next指向删除位置的后一个节点
                    pre.next = cur.next
                return True
            else:
                # 继续按链表后移节点
                pre = cur
                cur = cur.next

    def find(self, item):
        """查找元素是否存在"""
        return item in self.items()

    def getIndex(self, data):
        if self.is_empty():
            print("error : out of index")
            return None
        cur = self._head
        index = 0
        while cur is not None:
            # 返回生成器
            if cur.item == data:
                return index
            # 指针下移
            index += 1
            cur = cur.next
        return None

    def show(self):
        if self.is_empty():
            print("空链表")
            return None
        cur = self._head
        while cur is not None:
            print(cur.item, end="-->")
            cur = cur.next

    def deleteIdex(self, index):
        if index == 0:
            self._head = self._head.next
            return
        elif index > (self.length() - 1):
            return
        j = 0
        node = self._head
        pre = self._head
        while node.next and j < index:
            pre = node
            node = node.next
            j += 1
        if j == index:
            pre.next = node.next


if __name__ == '__main__':
    link_list = SingleLinkList()
    # 向链表尾部添加数据
    for i in range(5):
        link_list.append(i)
    # 向头部添加数据
    link_list.add(6)
    # 遍历链表数据
    for i in link_list.items():
        print(i, end='\t')
    # 链表数据插入数据
    link_list.insert(3, 9)
    print('\n', list(link_list.items()))
    # 删除链表数据
    link_list.remove(0)
    # 查找链表数据
    print(link_list.find(4))
    print('\n', list(link_list.items()))
    link_list.show()

参看imooc上liuyubobobo老师java数据结构的python改写：

# -*- coding: utf-8 -*-
# Author:           Annihilation7
# Data:             2018-09-27
# Python version:   3.6

class Node:
    def __init__(self, elem_=None, next_=None):
        """
        节点类构造函数
        :param elem_: 节点所带的元素，默认为None
        :param next_: 指向下一个节点的标签（在python中叫做标签）
        """
        self.elem = elem_
        self.next = next_  # 都是共有的

    def printNode(self):
        """打印Node"""
        print(self.elem, end='  ')  # 就打印一下元素的值


class LinkedList:
    def __init__(self):
        """
        链表构造函数
        """
        self._dummyhead = Node()        # 虚拟头结点，作用巨大，把他当成不属于链表的哨兵节点就好
        # 如果没有dummyhead，在链表头部插入与删除操作将要特殊对待，因为找不到待操作节点的前一个节点
        # 而有了虚拟头结点后，就不存在这种情况了
        self._size = 0       # 容量

    def getSize(self):
        """
        获得链表中节点的个数
        :return: 节点个数
        """
        return self._size

    def isEmpty(self):
        """
        判断链表是否为空
        :return: bool值，空为True
        """
        return self.getSize() == 0

    def add(self, index, elem):
        """
        普适性的插入功能
        时间复杂度：O(n)
        :param index: 要插入的位置（注意index对于用户来说也是从零开始的，这里我没做更改）
        :param elem: 待插入的元素
        """
        if index < 0 or index > self._size:     # 有效性检查
            raise Exception('Add failed. Illegal index')
        prev = self._dummyhead      # 从虚拟头结点开始，注意虚拟头结点不属于链表内的节点，当做哨兵节点来看就好了
        for i in range(index):      # 往后撸，直到待操作节点的前一个节点
            prev = prev.next
        prev.next = Node(elem, prev.next)
        # 先看等式右边，创建了一个节点对象，携带的元素是elem，指向的元素就是index处的节点，即
        # 现在有一个新的节点指向了index处的节点
        # 并将它赋给index节点处的前一个节点的next，是的prev的下一个节点就是这个新节点，完成拼接操作
        # 可以分解成三句话：  temp = Node(elem); temp.next = prev.next; prev.next = temp
        # 画个图就很好理解啦
        self._size += 1 # 维护self._size

    def addFirst(self, elem):
        """
        将elem插入到链表头部
        时间复杂度：O(1)
        :param elem: 要插入的元素
        """
        self.add(0, elem)       # 直接点用self.add

    def addLast(self, elem):
        """
        链表尾部插入元素elem
        时间复杂度：O(n)
        :param elem: 待插入的元素
        """
        self.add(self._size, elem)      # 调用self.add

    def remove(self, index):
        """
        删除第index位置的节点
        时间复杂度：O(n)
        :param index: 相应的位置，注意从零开始
        :return: 被删除节点的elem成员变量
        """
        if index < 0 or index >= self.getSize():    # index合法性检查
            raise Exception('Remove falied. Illegal index')
        pre = self._dummyhead       # 同样的，要找到待删除的前一个节点，所以从dummyhead开始
        for i in range(index):      # 往后撸index个节点
            pre = pre.next
        retNode = pre.next          # 此时到达待删除节点的前一个节点，并用retNode对待删除节点进行标记，方便返回elem
        pre.next = retNode.next     # pre的next直接跨过待删除节点直接指向待删除节点的next，画个图就很好理解了
        retNode.next = None         # 待删除节点的next设为None，让它完全从链表中脱离，使得其被自动回收
        self._size -= 1             # 维护self._size
        return retNode.elem         # 返回被删除节点的elem成员变量

    def removeFirst(self):
        """
        删除第一个节点(index=0)
        时间复杂度：O(1)
        :return: 第一个节点的elem成员变量
        """
        return self.remove(0)   # 直接调用self.add方法

    def removeLast(self):
        """
        删除最后一个节点(index=self._size-1)
        时间复杂度：O(n)
        :return: 最后一个节点的elem成员变量
        """
        return self.remove(self.getSize() - 1)

    def removeElement(self, elem):
        """
        删除链表的指定元素elem，这个方法实现的是将链表中为elem的Node全部删除哦，与数组只删除最左边的第一个是不一样的！如果elem不存在我们什么也不做
        :param elem: 待删除的元素elem
        时间复杂度：O(n)
        """
        pre = self._dummyhead             # 老方法，被删除元素的前一个记为pre
        while pre.next:                   # 只要pre的next不为空
            if pre.next.elem == elem:     # pre的next的elem和elem相等
                delNode = pre.next        # 记下pre的next的节点，准备略过它
                pre.next = delNode.next   # 略过pre.next直接将pre.next置为pre.next.next
                delNode.next = None       # delNode的next置为空，被当成垃圾回收
                self._size -= 1           # 维护self._size
                # 注意此时不要pre = pre.next，因为这时候pre的next又是一个新的元素！也需要进行判断的，所以删除的是所有携带值为elem的节点
            else:
                pre = pre.next            # 不相等就往后撸就完事了


    def get(self, index):
        """
        获得链表第index位置的值
        时间复杂度：O(n)
        :param index: 可以理解成索引，但并不是索引！
        :return: 第index位置的值
        """
        if index < 0 or index >= self.getSize():    # 合法性检查
            raise Exception('Get failed.index is Valid, index require 0<=index<=self._size-1')
        cur = self._dummyhead.next      # 初始化为第一个有效节点
        for i in range(index):          # 执行index次
            cur = cur.next              # 往后撸，一直到第index位置
        return cur.elem

    def getFirst(self):
        """
        获取链表第一个节点的值
        时间复杂度：O(1)
        :return: 第一个节点的elem
        """
        return self.get(0)      # 调用self.add方法

    def getLast(self):
        """
        获取链表最后一个节点的值
        时间复杂度：O(n)
        :return: 最后一个节点的elem
        """
        return self.get(self.getSize() - 1)

    def set(self, index, e):
        """
        把链表中第index位置的节点的elem设置成e
        时间复杂度：O(n)
        :param index: 链表中要操作的节点的位置
        :param e:  将要设为的值
        """
        if index < 0 or index >= self.getSize():        # 合法性检查
            raise Exception('Set failed.index is Valid, index require 0<=index<=self._size-1')
        cur = self._dummyhead.next  # 从第一个元素开始，也就是dummyhead的下一个节点
        for i in range(index):      # 往后撸，直到要操作的节点的位置
            cur = cur.next
        cur.elem = e        # 设置成e即可

    def contains(self, e):
        """
        判断链表的节点的elem中是否存在e
        时间复杂度：O(n)
        由于并不存在索引，所以只能从头开始找，一直找。。。如果到尾还没找到就是不存在
        :param e: 要判断的值
        :return: bool值，存在为True
        """
        cur = self._dummyhead.next  # 将cur设置成第一个节点
        while cur != None:      # 只要cur有效，注意这个链表的最后一个节点一定是None，因为dummyhead初始化时next就是None，这个
            # 通过链表的这些方法只会往后移动，一直处于最末尾
            if cur.elem == e:   # 如果相等就返回True
                return True
            cur = cur.next      # 否则就往后撸
        return False            # 到头了还没找到就返回False

    def printLinkedList(self):
        """对链表进行打印操作"""
        cur = self._dummyhead.next
        print('表头：', end=' ')
        while cur != None:
            cur.printNode()
            cur = cur.next
        print('\nSize:  %d' % self.getSize())

+++++++++++++++++==+++++++++++++++++=+=++++++++++++++++++++
import linkedlist       # Linkedlist写在这个py文件中
import numpy as np
np.random.seed(7)

test = linkedlist.LinkedList()
print(test.getSize())
print(test.isEmpty())
test.addFirst(6)
for i in range(13):
    test.addLast(np.random.randint(11))
test.printLinkedList()
test.add(10, 'annihilation7')
test.printLinkedList()
print(test.getSize())
print(test.get(2))
print(test.getLast())
print(test.getFirst())
test.set(0, 30)
test.printLinkedList()
print(test.contains(13))
print(test.remove(8))
test.printLinkedList()
print(test.removeFirst())
test.printLinkedList()
print(test.removeLast())
test.printLinkedList()

print('删除全部为7的元素：')
test.removeElement(7)
test.printLinkedList()
print(test.getSize())