当前位置:   article > 正文

【数据结构与算法python】无序链表的python实现_python 无序链表

python 无序链表

1、无序链表的介绍
列表List是一种数据项按照相对位置存放的数据集,作为一种简单强大的数据集结构,提供了丰富的操作接口,但并不是所有的编程语言都提供了List数据类型,有时候需要我们自己实现。为了实现无序表数据结构,可以采用链接表的方案。

2、无序链表的性质
虽然列表数据结构要求保持数据项的前后相对位置,但这种前后位置的保持,并不要求数据项依次存放在连续的存储空间。
数据项存放位置并没有规则,但如果在数据项之间建立链接指向,就可以保持其前后相对位置。
第一个和最后一个数据项需要显式标记出来,一个是队首,一个是队尾,后面再无数据了。
在这里插入图片描述
链表实现的最基本元素是节点Node,每个节点至少要包含2个信息:数据项本身,以及指向下一个节点的引用信息,next为None的意义是没有下一个节点了。
在这里插入图片描述

3、无序链表的基本操作
(1)节点Node

class Node:
	# 链表初始化
    def __init__(self,initdata):
        self.data = initdata
        self.next = None
	# 获取节点的值
    def getData(self):
        return self.data
	# 获取节点的下一个节点
    def getNext(self):
        return self.next
	# 设置节点的值
    def setData(self,newdata):
        self.data = newdata
	# 设置节点的后续节点
    def setNext(self,newnext):
        self.next = newnext
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

(2)无序链表初始化
无序表必须要有对第一个节点的引用信息,设立一个属性head,保存对第一个节点的引用
空表的head为None,随着数据项的加入,无序表的head始终指向链条中的第一个节点

def __init__(self):
	self.head = None
  • 1
  • 2

(3)判断无序表是否为空
包含的head只是对首个节点Node的引用,判断空表的isEmpty()很容易实现,实现方式如下所示

def isEmpty(self):
	return self.head == None
  • 1
  • 2

(4)添加元素
由于无序表并没有限定数据项之间的顺序,新数据项可以加入到原表的任何位置,按照实现的性能考虑,应添加到最容易加入的位置上,也就是添加到表头head处

def add(self,item):
    temp = Node(item)
    temp.setNext(self.head)
    self.head = temp
  • 1
  • 2
  • 3
  • 4

(5)链表大小
从链条头head开始遍历到表尾同时用变量累加经过的节点个数

def length(self):
    current = self.head
    count = 0
    while current != None:
        count = count + 1
        current = current.getNext()

    return count
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

(6)元素搜索
从链表头head开始遍历到表尾,同时判断当前节点的数据项是否目标

def search(self,item):
    current = self.head
    found = False
    while current != None and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()

    return found
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

(7)元素删除
首先要找到item,这个过程跟search一 样,但在删除节点时,需要特别的技巧current指向的是当前匹配数据项的节点,而删除需要把前一个节点的next指向current的下一个节点,所以我们在search current的同时,还要维护前一个(previous)节点的引用

def remove(self,item):
    current = self.head
    previous = None
    found = False
    while not found:
        if current.getData() == item:
            found = True
        else:
            previous = current
            current = current.getNext()

    if previous == None:
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

4、例子

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

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext


class UnorderedList:

    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None
            
    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
        
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()

        return count
        
    def search(self,item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()

        return found
                
    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())
            
mylist = UnorderedList()

mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.add(93)
mylist.add(26)
mylist.add(54)

print(mylist.length())
print(mylist.search(93))
print(mylist.search(100))

mylist.add(100)
print(mylist.search(100))
print(mylist.length())

mylist.remove(54)
print(mylist.length())
mylist.remove(93)
print(mylist.length())
mylist.remove(31)
print(mylist.length())
print(mylist.search(93))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/858828
推荐阅读
相关标签
  

闽ICP备14008679号