python

无序表的实现Python

2020-10-23 11:39发布

站内文章 / Python核心编程
1025 0 0

无序表的实现

  • 无序表是一种线性结构，对比有序表（元素的位置是根据其值的大小而设定的），无序表的元素位置不是因为其值的大小而改变。类似于Python中的List。Python中的List是以顺序存储的方式实现的，本文以链式存储的形式实现无序表，所以元素互称为前驱元素，后继元素。

无序表的方法主要有增加元素、删除元素、查找元素、无序表大小、是否非空等等。简单实现了几个方法（和c语言实现的方法类似）。

以链表的形式实现，就需要有节点node，节点中有两个变量，一个存储当前节点的值，另一个存储下一个节点的对象（对比c语言中的指针地址）。节点类的方法有，给节点赋值，取节点值，给节点赋下一个节点的对象，取节点下一个节点的对象。定义类如下：

class Node(object):
    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 = newnext12345678910111213141516

接下来看无序表如何实现，首先考虑一下无序表是空时（没有元素，没有节点），内部是什么形式的。这个其实不容易想，那就考虑一下如果无序表有元素（多于一个）时，内部是什么形式的？其实是利用节点的第二个变量将一个节点连接另一个节点。无序表的结尾就是最后一个节点，因为没有下一个节点，所以该节点的另一个变量就是None。应该可以想象到，只要我们往无序表里增加一个元素，就是链接一个节点，那么反过来，删除一个元素，就是断开某处连接。**那么无序表为空时，增加第一个元素如何链接呢？**参考其他位置的节点，是因为有上一个节点的第二个变量，为其赋值一个节点对象就是链接了。所以无序表最开始时也应该有一个类似于节点第二个变量的变量，用于给第一个元素进行连接。当无序表为空时，就类似于普通节点没有后继节点，即赋值为None（也就是初始化为None）。这样可以定义一个无序表类，初始化时，赋值给变量为None（因为初始化时为空表）。

    def __init__(self):
        self.head = None12

接下来看无序表的增加元素方法。因为是无序的，所以不用比较元素大小，因此只需要把元素增加上去就好。一般来说增加元素方法比较常用，所以需要把它设计的比较简单，复杂度要低。因为链表是一个一个连接的，没有下标，所以遍历时需要从头开始遍历，时间开销较大（但是空间利用率较高），这也是时间和空间的一个博弈体现。所以最简单的增加元素方法就是在头部开始增加（这里把离head变量近的位置称为头部）。

    def add(self, item):
         
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp12345

接下来看删除元素方法。既然要删除元素，就必要找到该元素。前面已经提到，需要从头开始遍历。那么来看一下如何删除呢？（因为Python不涉及内存，所以就不需要想c那样free掉内存了，只需要断开连接就行了）当找到一个元素后，一定要明确，因为有前驱和后继，断开连接指的是断开该元素两端的连接，既要和前驱断开，也要和后继断开。那么断开后，后该元素的后继怎么办？不要了吗，肯定不是的，还要把前驱和后继连接起来。怎么连接呢？其实和正常增加元素一样，把前驱的其二个变量赋值成后继的对象即可。因此在找到要删除的元素时，还要找到删除元素的前驱元素。所以需要两个变量同时遍历，一个找该元素，另一个找前驱元素。

    def remove(self, item):
        preTemp = None
        temp = self.head
        result = False
        # 遍历找到元素以及前驱
        while temp != None:
            if temp.getData() == item:
            	result = True
                break
            else:
                preTemp = temp
                temp = temp.getNext()
		# 删除元素
		if result == False:
			print('没有该元素，删除失败')
		else:
	        if preTemp == None:
	        	if temp == None:
	        		self.head = None
	        	else:
	            	self.head = temp.getNext()
	        else:
	            preTemp.setNext(temp.getNext())
	        print('删除成功')123456789101112131415161718192021222324

接下来看一下打印方法，遍历无序表并打印

    def pt(self):
        strs = ''
        temp = self.head
        if self.isEmpty() == True:
            print('无序表为空')
        else:
            while temp != None:
                strs = strs + str(temp.getData()) + '->'
                temp = temp.getNext()
            print(strs[:-2])12345678910

接下来看查找元素方法，这个不用多说，就是遍历就行。

    def search(self, item):
        temp = self.head
        result = False
        while temp != None:
            if temp.getData() == item:
                result = True
                break
            else:
                temp = temp.getNext()
        return result12345678910

最后看一下非空判断。

def isEmpty(self):
	return self.head == None12

然后还有以下其他的方法，比如修改，这个方法其实和查找类似，找到后再赋值就行了。这是全部代码。

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

    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def size(self):
        temp = self.head
        num = 0
        while temp != None:
            num += 1
            temp = temp.getNext()

        return num

    def search(self, item):
        temp = self.head
        result = False
        while temp != None:
            if temp.getData() == item:
                result = True
                break
            else:
                temp = temp.getNext()
        return result

    def remove(self, item):
        preTemp = None
        temp = self.head
        result = False
        while temp != None:
            if temp.getData() == item:
                result = True
                break
            else:
                preTemp = temp
                temp = temp.getNext()

        if result == False:
            print('没有该元素，删除失败')
        else:
            if preTemp == None:
                self.head = temp.getNext()
            else:
                preTemp.setNext(temp.getNext())

            print('删除成功')

    def isEmpty(self):
        return self.head == None
            
    def pt(self):
        strs = ''
        temp = self.head
        if self.isEmpty() == True:
            print('无序表为空')
        else:
            while temp != None:
                strs = strs + str(temp.getData()) + '->'
                temp = temp.getNext()
            print(strs[:-2])12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364

这是测试代码，简单测试了一下，还是要多进行边缘测试，提高鲁棒性。

mylist = UnorderedList()

mylist.pt()
print(mylist.search(3))
mylist.remove(3)

print('-'*20)

for i in range(8):
    mylist.add(i)
mylist.pt()
print(mylist.search(3))
mylist.remove(3)

print('-'*20)
mylist.pt()
print(mylist.search(3))



作者：qq_42907161

链接：https://blog.csdn.net/qq_42907161/article/details/108091952

来源：CSDN
著作权归作者所有，转载请联系作者获得授权，切勿私自转载。