【Python】数据结构——线性表（顺序表、单链表、循环单链表、双链表、循环双链表）

目录

线性表

线性表定义

线性表类型

线性表特性

线性表用处

顺序表

顺序表定义

顺序表的 *** 作

链表

链表的定义

链表与顺序表的区别

链表的构成

链表的类型

单链表的 *** 作

 循环单链表的 *** 作

双向链表的 *** 作

循环双链表的 *** 作

---

线性表 线性表定义

线性表是由若干个具有相同特性的数据元素组成的有限序列
空表就是线性表中不包含任何元素，长度为零。当线性表非空时，线性表长度即线性表内数据元素的个数。
直接前驱：线性表某一个元素的前一个元素
直接后继：线性表某一个元素的后一个元素
在线性表中有且仅有一个表头和一个表尾。表头无直接前驱，表尾无直接后继。

线性表类型

有序线性表（有序表）：表内元素按照递增或递减的方式排列。
无序线性表（无序表）：表内元素排列无序，无递增关系也无递减关系。

线性表特性

• 线性表内元素个数有限
• 线性表中所有元素具有相同的数据特性
• 线性表中除了表头外，其余元素都具有唯一的直接前驱
• 线性表中除了表尾外，其余元素都具有唯一的直接后继

线性表用处

用于解决数据的排序、约瑟夫环、n级法雷数列

顺序表 顺序表定义

顺序表是指采用顺序存储的方式来存储数据元素的线性表。在线性表中我们通常将结点依次存放在一组地址连续的存储空间中。

顺序表的 *** 作

class SequenceList(object):
    def __init__(self):
        # 初始化顺序表
        self.SeqList = []

    def CreateSequenceList(self):
        print("请输入顺序表元素按回车确认，输入#号结束")
        Element = input("请输入元素：")
        while Element != '#':
            self.SeqList.append(int(Element))
            Element = input("请输入元素：")

    def FindElement(self):
        key = int(input("请输入需要查找的元素值："))
        if key in self.SeqList:
            ind = self.SeqList.index(key)
            print(f"查找成功！元素下标为:{ind} 元素值为{self.SeqList[ind]}")
        else:
            print(f"查找失败！当前顺序表中不存在值为{key}的元素")

    def InsertElemnt(self):
        ind = int(input("请输入待插入元素的下标："))
        Element = int(input("请输入待插入元素的值："))
        self.SeqList.insert(ind, Element)
        print(f"插入当前元素后的顺序表：{self.SeqList}")

    def DeleteElementById(self):
        ind = int(input("请输入要删除元素的下标："))
        print(f"正在删除下标为{ind}的元素")
        self.SeqList.remove(self.SeqList[ind])
        print("删除后的顺序表为：", self.SeqList)

    def DeleteElementByKey(self):
        key = int(input("请输入要删除元素的值："))
        print(f"正在删除值为{key}的元素")
        if key in self.SeqList:
            ind = self.SeqList.index(key)
            print(f"删除成功！已成功删除元素值为{self.SeqList[ind]}的元素")
            print("删除后的顺序表为：", self.SeqList)
        else:
            print(f"删除失败！当前顺序表中不存在值为{key}的元素")

    def TraverseElement(self):
        SeqListLen = len(self.SeqList)
        for i in range(0, SeqListLen):
            print(f"下标为{i}的元素的值为{self.SeqList[i]}")

    def IsEmpty(self):
        if len(SeqList) == 0:
            return True
        else:
            return False


if __name__ == '__main__':
    SeqList = SequenceList()
    SeqList.CreateSequenceList()
    SeqList.TraverseElement()
    SeqList.FindElement()
    SeqList.InsertElemnt()
    SeqList.DeleteElementById()
    SeqList.DeleteElementByKey()

链表 链表的定义

链表是指采用链式结构存储数据元素的线性表。

链表与顺序表的区别

1.链表只能顺序存取，线性表可以随机存取。

顺序表是系统提前分配好一组连续的存储空间，并采用顺序存储的方式存储数据元素的，链表是在每个结点创建的时候主动向系统申请存储空间，并通过指针来链接各个包含数据元素的结点。
链表中元素的逻辑顺序是由指针的链接次序决定的，和存储单元的物理位置无关。
链表在使用时只能顺序存取，但是顺序表中的元素的逻辑地址是和物理地址直接关联的，可以实现随机存取。

2.链表实现存储空间的动态管理
3.链表在插入和删除时，不需要移动其余元素，只需要修改指针指向。

链表的构成

链表由一系列结点通过指针链接而成，每个结点都具有数据域和指针域。数据域用来存储数据元素，指针域用来存储下一个结点的地址。

链表的类型

单向链表、双向链表、循环链表

单向链表中，每个结点只包含一个指针域，用来指向其直接后继结点，通常将单向链表简称为单链表。单链表的最后一个结点指针域默认为空None。

双向链表中，每个结点有两个指针域，其中一个指向其前驱结点，称之为先驱指针，后一个结点用于指向后继结点，称之为后继指针。通常将双向链表简称为双链表。

循环链表的特点是无论从哪一个结点出发都可以找到链表中的其他结点。

循环单链表：表中的最后一个结点的指针域不为空，而是指向表中的第一个结点。

若循环单链表中存在头结点，则第一个结点为头结点，否则第一个结点为循环单链表第一个元素所在的结点。

循环双链表：表中最后一个结点的后继指针指向该表的第一个结点，并且表中的第一个结点的先驱指针指向该表的最后一个结点。

若循环双链表存在头结点，那么第一个结点即为头结点，否则第一个结点为循环双链表的第一个元素所在的结点。

单链表的 *** 作

# 循环单链表：表中的最后一个结点的指针域不为空，而是指向表中的第一个结点。
# 若循环单链表中存在头结点，则第一个结点为头结点，否则第一个结点为循环单链表第一个元素所在的结点。
class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None


class SingleLinkedList(object):

    def __init__(self):
        self.head = Node(None)

    def CreateSingleLinkedList(self):
        print("请输入数据后按回车确认，按#号结束")
        cNode = self.head
        Element = input("请输入当前结点的值：")
        while Element != '#':
            nNode = Node(int(Element))
            cNode.next = nNode
            cNode = cNode.next
            Element = input("请输入当前结点的值：")

    def InsertElementInTail(self):
        Element = input("请输入要插入结点的值（尾插）")
        if Element == "#":
            return
        cNode = self.head
        nNode = Node(int(Element))
        while cNode.next != None:
            cNode = cNode.next
        cNode.next = nNode

    def InsertElementInHead(self):
        Element = input("请输入要插入结点的值（头插）：")
        if Element == "#":
            return
        cNode = self.head
        nNode = Node(int(Element))
        nNode.next = cNode.next
        cNode.next = nNode

    def GetLength(self):
        cNode = self.head
        length = 0
        while cNode.next != None:
            length = length + 1
            cNode = cNode.next
        return length

    def IsEmpty(self):
        if self.GetLength() == 0:
            return True
        else:
            return False

    def FindElement(self):
        Posi = 0
        cNode = self.head
        key = int(input("请输入想查找的元素值："))
        if self.IsEmpty():
            print("当前链表为空，不存在该元素")
            return
        while cNode.next != None and cNode.data != key:
            cNode = cNode.next
            Posi = Posi + 1
        if cNode.data == key:
            print(f"查找成功！元素值为{key}的结点位于该单链表的第{Posi}位")
        else:
            print(f"查找失败！当前单链表中不存在{key}元素")

    def DeleteElement(self):
        dElement = int(input("请输入要删除结点的值："))
        cNode = self.head
        pNode = self.head
        if self.IsEmpty():
            print("当前链表为空！")
            return
        while cNode.next != Node and cNode.data != dElement:
            pNode = cNode
            cNode = cNode.next
        if cNode.data == dElement:
            pNode.next = cNode.next
            del cNode
            print(f"成功删除值为{dElement}的结点")
        else:
            print(f"删除失败！当前单链表中不含有值{dElement}的结点")

    def VisitElement(self, tNode):
        if tNode != None:
            print(tNode.data, "->", end="")
        else:
            print("None")

    def TraverseElement(self):
        cNode = self.head
        if cNode.next == None:
            print("当前单链表为空！")
            return
        print("您当前的单链表为：")
        while cNode != None:
            cNode = cNode.next
            self.VisitElement(cNode)


if __name__ == '__main__':
    LinkList = SingleLinkedList()
    LinkList.CreateSingleLinkedList()
    LinkList.TraverseElement()
    LinkList.InsertElementInTail()
    LinkList.TraverseElement()
    LinkList.InsertElementInHead()
    LinkList.TraverseElement()
    LinkList.FindElement()
    LinkList.DeleteElement()
    LinkList.TraverseElement()

 循环单链表的 *** 作

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


class CircularSingleLinkedList(object):
    def __init__(self):

        self.head = Node(None)

    def CreateCircularSingleLinkedList(self):
        print("请输入数据按回车确认，按#号结束")
        data = input("请输入结点的值：")
        cNode = self.head
        while data != "#":
            nNode = Node(int(data))
            cNode.next = nNode
            nNode.next = self.head
            cNode = cNode.next
            data = input("请输入结点的值：")

    def InsertElementInTail(self):
        Element = input("请输入待插入结点的值（尾插）：")
        if Element == "#":
            return
        cNode = self.head
        nNode = Node(int(Element))
        while cNode.next != self.head:
            cNode = cNode.next
        cNode.next = nNode
        nNode.next = self.head

    def InsertElementInHead(self):
        Element = input("请输入待插入结点的值（头插）：")
        if Element == "#":
            return
        cNode = self.head
        nNode = Node(int(Element))
        nNode.next = cNode.next
        cNode.next = nNode

    def GetLength(self):
        cNode = self.head
        if self.head is None:
            return
        length = 1
        while cNode.next is not self.head:
            cNode = cNode.next
            length = length + 1
        return length

    def IsEmpty(self):
        return self.head is None

    def DeleteElement(self):
        dElement = int(input("请输入待删除结点的值："))
        cNode = self.head
        pNode = self.head
        if self.IsEmpty():
            print("当前循环单链表的为空！")
            return
        while cNode.next != self.head and cNode.data != dElement:
            pNode = cNode
            cNode = cNode.next
        if cNode.data == dElement:
            pNode.next = cNode.next
            del cNode
            print(f"成功删除含有元素{dElement}的结点")
        else:
            print(f"删除失败！循环双链表不存在含有元素{dElement}的结点")

    def FindElement(self):
        Posi = 0
        cNode = self.head
        key = int(input("请输入想查找的元素值："))
        if self.IsEmpty():
            print("当前链表为空，不存在该元素")
            return
        while cNode.next != self.head:
            if cNode.data == key:
                return True
            else:
                cNode = cNode.next
                Posi = Posi + 1
        if cNode.data == key:
            print(f"查找成功！元素值为{key}的结点位于该单链表的第{Posi}位")
        else:
            print(f"查找失败！当前单链表中不存在{key}元素")

    def TraverseElement(self):
        if self.IsEmpty():
            return
        cNode = self.head
        while cNode.next != self.head:
            print(f"当前结点为：{cNode.data}")
            cNode = cNode.next
        print(f"当前结点为：{cNode.data}")


if __name__ == '__main__':
    LinkList = CircularSingleLinkedList()
    LinkList.CreateCircularSingleLinkedList()
    LinkList.TraverseElement()
    LinkList.InsertElementInTail()
    LinkList.TraverseElement()
    LinkList.InsertElementInHead()
    LinkList.TraverseElement()
    LinkList.FindElement()
    LinkList.DeleteElement()
    LinkList.TraverseElement()

双向链表的 *** 作

# 带头结点的双链表
class DoubleLinkedNode(object):
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class DoubleLinkedList(object):
    def __init__(self):
        self.head = DoubleLinkedNode(None)

    def CreateDoubleLinkedList(self):
        print("输入数据按回车确认，按#号结束")
        data = input("请输入元素：")
        cNode = self.head
        while data != "#":
            nNode = DoubleLinkedNode(int(data))
            cNode.next = nNode
            nNode.prev = cNode
            cNode = cNode.next
            data = input("请输入元素：")

    def GetLength(self):
        cNode = self.head.next
        length = 0
        while cNode != None:
            length = length + 1
            cNode = cNode.next
        return length

    def IsEmpty(self):
        if self.head.next == None:
            return True
        else:
            return False

    def InsertElementInTail(self):
        Element = input("请输入待插入结点的值（尾插）：")
        if Element == "#":
            return
        nNode = DoubleLinkedNode(int(Element))
        cNode = self.head
        while cNode.next != None:
            cNode = cNode.next
        cNode.next = nNode
        nNode.prev = cNode

    def InsertElementInHead(self):
        Element = input("请输入待插入结点的值（头插）：")
        if Element == "#":
            return
        cNode = self.head.next
        pNode = self.head
        nNode = DoubleLinkedNode(int(Element))
        nNode.prev = pNode
        pNode.next = nNode
        nNode.next = cNode
        cNode.prev = nNode

    def DeleteElement(self):
        dElement = int(input("请输入待删除结点的值："))
        cNode = self.head
        pNode = self.head
        if self.IsEmpty():
            print("当前双链表为空：")
            return
        while cNode.next != None and cNode.data != dElement:
            pNode = cNode
            cNode = cNode.next
        if cNode.data == dElement:
            if cNode.next == None:
                pNode.next = None
                del cNode
                print(f"成功删除数据值为{dElement}的结点")
            else:
                qNode = cNode.next
                pNode.next = qNode
                qNode.prev = pNode
                del cNode
                print(f"成功删除数据值为{dElement}的结点")
        else:
            print(f"删除失败！当前双链表中不含有值为{dElement}的结点")

    def TraverseElement(self):
        cNode = self.head
        print("按照next域遍历带头结点的双链表：")
        if self.IsEmpty():
            print("当前双链表为空！")
            return
        while cNode.next != None:
            cNode = cNode.next
            print(cNode.data, "->", end="")
        print("None")


if __name__ == '__main__':
    DLL = DoubleLinkedList()
    DLL.CreateDoubleLinkedList()
    DLL.TraverseElement()
    DLL.InsertElementInHead()
    DLL.TraverseElement()
    DLL.InsertElementInTail()
    DLL.TraverseElement()
    DLL.DeleteElement()
    DLL.TraverseElement()

循环双链表的 *** 作

class DoubleLinkedNode(object):

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


class CircularDoubleLinkedList(object):

    def __init__(self):
        self.head = DoubleLinkedNode(None)

    def CreateCircularDoubleLinkedList(self):

        print("请输入数据按回车确认，按#号退出")

        data = input("请输入元素：")
        cNode = self.head
        while data != "#":
            nNode = DoubleLinkedNode(int(data))
            cNode.next = nNode
            nNode.prev = cNode
            nNode.next = self.head
            self.head.prev = nNode
            cNode = cNode.next
            data = input("请输入元素：")

    def GetLength(self):
        cNode = self.head
        length = 0
        while cNode.next != self.head:
            length = length + 1
            cNode = cNode.next
        return length

    def IsEmpty(self):
        if self.head.next == None:
            return True
        else:
            return False

    def InsertElementInTail(self):
        Element = input("请输入待插入结点的值（尾插）：")
        if Element == "#":
            return
        nNode = DoubleLinkedNode(int(Element))
        cNode = self.head
        while cNode.next != self.head:
            cNode = cNode.next
        cNode.next = nNode
        nNode.prev = cNode
        nNode.next = self.head
        self.head.prev = nNode

    def InsertElementInHead(self):
        Element = input("请输入待插入结点的值（头插）：")
        if Element == "#":
            return
        cNode = self.head.next
        pNode = self.head
        nNode = DoubleLinkedNode(int(Element))
        nNode.prev = pNode
        pNode.next = nNode
        nNode.next = cNode
        cNode.prev = nNode

    def DeleteElement(self):
        dElement = int(input('请输入待删除结点的值：'))
        cNode = self.head
        pNode = self.head
        if self.IsEmpty():
            print("当前双链表为空！")
            return
        while cNode.next != self.head and cNode.data != dElement:
            pNode = cNode
            cNode = cNode.next
        if cNode.data == dElement:
            qNode = cNode.next
            pNode.next = qNode
            qNode.prev = pNode
            del cNode
            print(f"成功删除含有元素{dElement}的结点")
        else:
            print(f"删除失败！双链表中不存在含有元素{dElement}的结点")

    def TraverseElement(self):
        if self.IsEmpty():
            return
        cNode = self.head.next
        print("按next域遍历带头结点双链表:")
        while cNode.next != self.head:
            print(cNode.data, "->", end="")
            cNode = cNode.next
        print(cNode.data)


if __name__ == "__main__":
    CDLL = CircularDoubleLinkedList()
    CDLL.CreateCircularDoubleLinkedList()
    CDLL.TraverseElement()
    CDLL.InsertElementInHead()
    CDLL.TraverseElement()
    CDLL.InsertElementInTail()
    CDLL.TraverseElement()
    CDLL.DeleteElement()
    CDLL.TraverseElement()

代码地址：Python/数据结构/线性表 at master · harbinailin/Python · GitHub

最近开始复习数据结构了，会一边复习一边刷题，预计5月10号左右复习算法。

可以订阅我的数据结构专栏哦~

喜欢的话，点赞、收藏+关注