数据结构之线性表 Python实现

Python实现线性表

525小白菜

2242人浏览 · 2021-07-12 11:00:44

525小白菜 · 2021-07-12 11:00:44 发布

1. 线性表的定义

线性表是具有相同特性数据元素的一个有限序列。该序列中所含元素的个数叫作线性表的长度，用n（n≥0）表示。注意，n可以等于零，表示线性表是一个空表。

线性表的几个特性：

元素个数有限
所有元素数据类型相同
可以有序也可以无序

线性表的逻辑特性：

只有一个表头元素，只有一个表尾元素，表头元素没有前驱，表尾元素没有后继，除表头和表尾元素外，其他元素只有一个直接前驱，也只有一个直接后继。

线性表的存储结构：

线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表，后者称为链表。下面通过对比来介绍这两种存储结构。

（1）顺序表

顺序表就是把线性表中的所有元素按照其逻辑顺序，依次存储到从指定的存储位置开始的it续的存储空间中。这样，线性表中第一个元素的存储位置就是指定的存储位置，第 i+1个元素的存储位置紧接在第 i 个元素的存储位置的后面。顺序表支持使用索引随机访问，而且顺序表要求占用连续的存储空间。在顺序表中插入元素要移动多个元素。

（2）链表

在链表存储中，每个结点不仅包含所存元素的信息，还包含元素之间逻辑关系的信息，如单链表中前驱结点包含后继结点的地址信息，这样就可以通过前驱结点中的地址信息找到后继结点的位置。链表不支持随机访问，只能按顺序依次访问。且链表由于要存储“指针”，所以空间利用率低。但链表的存储空间支持动态分配。在链表中插入元素，无需移动元素。

2. 顺序表的实现

Python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有元素的顺序（即保序）。

在Python的官方实现中，list实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。

顺序表的定义：

Sqlist = list()
#或者
Sqlist = []

元素插入

def insertElem(Sqlist,i,x): #在列表的第i位置插入元素x
    Sqlist.insert(i,x)

元素删除

def deleteElem(Sqlist,i): #删除列表第i个元素
    Sqlist.pop(i)

元素查找

#按位置查找,返回元素值
def findElemP(Sqlist,i):
    if i<len(Sqlist):
        return Sqlist[i]
#按元素值查找，返回元素位置，若有相同的多个元素，则返回第一个出现的位置
def findElemV(Sqlist,x):
    if Sqlist.count(x) > 0:
        return Sqlist.index(x)

3. 单链表的实现

链表判空条件：

	带头结点	不带头结点
单链表	self.head.next is None	self.head is None
双链表	self.head.next is None	self.head is None
循环单链表	self.head.next == self.head	self.head is None
循环双链表	self.head.next == self.head and self.head.pre == self.head	self.head is None

3.1 不带头结点的单链表

python中，任何变量都可以引用任何内容，包括None值，此处它表示空链接。通过定义包含两个字段(数据项和对下一节点的引用)的对象，从而定义了单向链表。下图所示为一个具有头指针的单链表。

在这里插入图片描述
下面是对带头指针的单链表的代码实现，代码在pycharm上运行过，没有什么问题：

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


# 定义一个单链表类
class linkedList(object):
    def __init__(self):
        # 初始化head指针和链表的长度length
        self.head = None
        self.length = 0

    # 头插法
    def insertatHead(self, newitem):
        self.head = Node(newitem, self.head)
        self.length += 1

    # 尾插法
    def insertatEnd(self, newitem):
        if self.head is None:
            self.head = Node(newitem, None)
        else:
            temp = self.head
            while temp.next != None:
                temp = temp.next
            temp.next = Node(newitem, None)
        self.length += 1

    # 任意位置插入,在第index位置插入，原该位置及之后的元素依次后移，index范围（0，length）
    def insertatAnyposition(self, index, newitem):
        if index > self.length or index <0:
            print("the index is incorrect")
            return None
        elif self.head is None or index == 0:
            self.head = Node(newitem, self.head)
        else:
            temp = self.head
            while temp.next != None and index > 1:
                temp = temp.next
                index -= 1
            temp.next = Node(newitem, temp.next)
        self.length += 1

    # 在任意位置删除元素,删除第index位置的元素，index范围（0，length-1）
    def deleteatAnyposition(self, index):
        if self.head is None:
            print("the Linkedlist is None")
            return None
        elif index > (self.length-1) or index <0:
            print("the index is incorrect")
            return None
        elif self.head.next is None or index == 0:
            removeitem = self.head.data
            self.head = None
        else:
            temp = self.head
            while temp.next != None and index > 1:
                temp = temp.next
                index -= 1
            removeitem = temp.next.data
            temp.next = temp.next.next
        self.length -= 1
        return removeitem

    # 查找元素,按数值,返回其索引值
    def searchTargetV(self, targetitem):
        if self.head is None:
            print("the Linkedlist is None")
            return None
        else:
            temp = self.head
            index = 0
            while temp.next != None and temp.data != targetitem:
                temp = temp.next
                index += 1
            if temp.data == targetitem:
                print(targetitem,"has been found")
                return index
            else:
                print(targetitem,"is not in linkedlist")
                return None

    # 查找元素,按位置,返回元素值
    def searchTargetP(self, index):
        if self.head is None:
            print("the Linkedlist is None")
            return None
        elif index > (self.length-1) or index < 0:
            print("the index is incorrect")
            return None
        else:
            temp = self.head
            while index > 0:
                temp = temp.next
                index -= 1
            return temp.data

    # 从头打印列表
    def printLinkedlist(self):
        if self.head == None:
            print("the Linkedlist is None")
        else:
            temp = self.head
            while temp != None:
                print(temp.data)
                temp = temp.next
        print("length is ",self.length)

操作核心代码：

# 头插法（head是头指针）
	self.head = Node(newitem, self.head)
# 尾插法（temp指向插入位置前一个元素）
	temp.next = Node(newitem, temp.next)
# 删除元素（temp指向被删元素前一个元素）
	temp.next = temp.next.next
# 遍历
	temp = self.head
	while temp.next != None:  
        temp = temp.next

3.2 带头结点的单链表

注意头节点与头指针的区别。与不带头结点的单链表相比，带头结点的单链表多了一个不存储数据的空节点，该节点指向链表的第一个数据节点。头指针指向的是头节点。加入头结点的好处是，对第一个数据节点的处理可以和其余节点一致。
在这里插入图片描述
下面是对带头指针的单链表的代码实现

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


# 定义一个单链表类
class linkedList(object):
    def __init__(self):
        # 初始化head指针和链表的长度length
        self.head = Node(None,None)
        self.length = 0

    # 头插法
    def insertatHead(self, newitem):
        self.head.next = Node(newitem, self.head.next)
        self.length += 1

    # 尾插法
    def insertatEnd(self, newitem):
        temp = self.head
        while temp.next != None:
            temp = temp.next
        temp.next = Node(newitem, None)
        self.length += 1

    # 任意位置插入,在第index位置插入，原该位置及之后的元素依次后移，index范围（0，length）
    def insertatAnyposition(self, index, newitem):
        if index > self.length or index <0:
            print("the index is incorrect")
            return None
        else:
            temp = self.head
            while temp.next != None and index > 0:
                temp = temp.next
                index -= 1
            temp.next = Node(newitem, temp.next)
        self.length += 1

    # 在任意位置删除元素,删除第index位置的元素，index范围（0，length-1）
    def deleteatAnyposition(self, index):
        if self.head.next is None:
            print("the Linkedlist is None")
            return None
        elif index > (self.length-1) or index <0:
            print("the index is incorrect")
            return None
        else:
            temp = self.head
            while temp.next != None and index > 0:
                temp = temp.next
                index -= 1
            removeitem = temp.next.data
            temp.next = temp.next.next
        self.length -= 1
        return removeitem

    # 查找元素,按数值,返回其索引值
    def searchTargetV(self, targetitem):
        if self.head.next is None:
            print("the Linkedlist is None")
            return None
        else:
            temp = self.head.next
            index = 0
            while temp.next != None and temp.data != targetitem:
                temp = temp.next
                index += 1
            if temp.data == targetitem:
                print(targetitem,"has been found")
                return index
            else:
                print(targetitem,"is not in linkedlist")
                return None

    # 查找元素,按位置,返回元素值
    def searchTargetP(self, index):
        if self.head.next is None:
            print("the Linkedlist is None")
            return None
        elif index > (self.length-1) or index < 0:
            print("the index is incorrect")
            return None
        else:
            temp = self.head.next
            while index > 0:
                temp = temp.next
                index -= 1
            return temp.data

    # 从头打印列表
    def printLinkedlist(self):
        if self.head.next == None:
            print("the Linkedlist is None")
        else:
            temp = self.head.next
            while temp != None:
                print(temp.data)
                temp = temp.next
        print("length is ",self.length)

操作核心代码：

# 头插法（head是头指针）
	self.head.next = Node(newitem, self.head.next)
# 尾插法（temp指向插入位置前一个元素）
	temp.next = Node(newitem, temp.next)
# 删除元素（temp指向被删元素前一个元素）
	temp.next = temp.next.next
# 遍历
	temp = self.head.next
	while temp.next != None:  
        temp = temp.next

4. 双链表

双链表的操作要特别注意，在链表末尾插入和删除时的操作与在链表当中插入和删除不同，因为最后一个节点的next是None，而None不需要修改 pre 指针。但在链表当中被操作元素的下一个节点是存在的，需要修改其pre指针的值。

双链表的节点插入操作：
在这里插入图片描述
双链表的节点删除操作：

# 定义链表节点
class Node(object):
    def __init__(self, data, pre=None ,next=None):
        self.data = data
        self.pre = pre
        self.next = next


# 定义一个双链表类
class DlinkedList(object):
    def __init__(self):
        # 初始化head指针和链表的长度length
        self.head = Node(None,None,None)
        self.length = 0

    # 任意位置插入,在第index位置插入，原该位置及之后的元素依次后移，index范围（0，length）
    def insertatAnyposition(self, index, newitem):
        if index > self.length or index <0:
            print("the index is incorrect")
            return None
        elif index == self.length :
            temp = self.head
            while temp.next != None:
                temp = temp.next
            temp.next = Node(newitem, temp, temp.next)
        else:
            temp = self.head
            while temp.next != None and index > 0:
                temp = temp.next
                index -= 1
            temp.next = Node(newitem, temp, temp.next)
            temp = temp.next
            temp.next.pre = temp
        self.length += 1


    # 在任意位置删除元素,删除第index位置的元素，index范围（0，length-1）
    def deleteatAnyposition(self, index):
        if self.head.next is None:
            print("the Linkedlist is None")
            return None
        elif index > (self.length-1) or index <0:
            print("the index is incorrect")
            return None
        elif index == self.length-1 :
            temp = self.head
            while temp.next.next != None:
                temp = temp.next
            removeitem = temp.next.data
            p = temp.next
            temp.next = p.next
        else:
            temp = self.head
            while temp.next != None and index > 0:
                temp = temp.next
                index -= 1
            removeitem = temp.next.data
            p = temp.next
            temp.next = p.next
            p.next.pre = temp
        self.length -= 1
        return removeitem

    # 查找元素,按数值,返回其索引值
    def searchTargetV(self, targetitem):
        if self.head.next is None:
            print("the Linkedlist is None")
            return None
        else:
            temp = self.head.next
            index = 0
            while temp.next != None and temp.data != targetitem:
                temp = temp.next
                index += 1
            if temp.data == targetitem:
                print(targetitem,"has been found")
                return index
            else:
                print(targetitem,"is not in linkedlist")
                return None

    # 查找元素,按位置,返回元素值
    def searchTargetP(self, index):
        if self.head.next is None:
            print("the Linkedlist is None")
            return None
        elif index > (self.length-1) or index < 0:
            print("the index is incorrect")
            return None
        else:
            temp = self.head.next
            while index > 0:
                temp = temp.next
                index -= 1
            return temp.data

    # 从头打印列表
    def printLinkedlist(self):
        if self.head.next == None:
            print("the Linkedlist is None")
        else:
            temp = self.head.next
            while temp != None:
                print(temp.data)
                temp = temp.next
        print("length is ",self.length)

5. 循环链表

循环单链表和循环双链表是由对应的单链表和双链表改造而来的，只需在终端结点和头结点间建立联系即可。循环单链表终端结点的next指针指向表头结点；循环双链表终端结点的next指针指向表头结点，头结点的pre指针指向表尾结总。要注意的是，如果p指针沿着循环链表行走，则判断p走到表尾结点的条件是：p.next == head。循环链表的各种操作均与非循环链表类似，这里不再介绍。

参考链接：