列表的实现与应用

抽象数据结构list

• python内置实现了list;但list是一种通用数据结构，类似于c++中的vector
• 下面使用链表来实现list;python内置list使用数组（array.Array模块）来实现

list的数据结构和操作方法如下：

一、实现（基于链表）

由于实现方式不同，该实现方式的各种操作时间复杂度不同于内置list

• 方法1：内置list(基于数组实现)
• 方法2：基于链表

1.1 无序list

class Node():"""链表中的节点，包括数据域和指针域；使用单链表实现"""def __init__(self, data):self.data = dataself.next = Nonedef get_data(self):return self.datadef set_next(self, next_node):#python内变量为引用类型，可视作指针self.next = next_nodedef get_next(self):return self.nextclass UnOrderedList():"""无序列表的实现"""def __init__(self):"""构造函数创建一个空list空的单链表等价于头部为空；根据头部可以遍历出所有所有链表信息故list只存储头部节点即可"""#头部节点初始为Noneself.head = Nonedef add(self, item):"""在链表head添加元素"""temp_node = Node(item)temp_node.set_next(self.head)self.head = temp_nodedef isEmpty(self):return self.head == Nonedef size(self):#排除特殊情况count = 0node = self.headwhile node != None:count += 1node = node.get_next()return countdef search(self, item):found = Falsecurrent = self.headwhile current != None and not found:if current.get_data() == item:#found相当于指示器，相当于breakfound = Trueelse:current = current.get_next()return founddef remove(self, item):"""1、找到则删除，未找到不做任何操作2、删除节点关键是定位相邻节点；左节点可以用previous表示，右节点用current.get_next()表示3、所以两个变量previous与current至关重要4、删除头结点要分类讨论"""found = Falsecurrent = self.headprevious = Nonewhile current != None and not found:if current.get_data() == item:#found相当于指示器，相当于breakfound = True#previous为None:删除头结点if previous == None:self.head = current.get_next()else:previous.set_next(current.get_next())else:previous = currentcurrent = current.get_next()def append(self, item):"""追加操作，链表首都append需要分类讨论"""current = self.headif current == None:self.head = Node(item)else:current = self.head#寻找链表最后一个元素while current.get_next() is not None:current = current.get_next() current.set_next(Node(item))def insert(self, pos, item):"""插入操作，链表首都append需要分类讨论"""if pos == 0:inserted_node = Node(item)inserted_node.set_next(self.head)self.head = inserted_nodeelif 0 < pos <=self.size() :#找到pos位置对应的当前元素current与前置元素previouscurrent = self.headprevious = Nonecount = 0while count < pos:previous = currentcurrent = current.get_next()count += 1inserted_node = Node(item)inserted_node.set_next(current)previous.set_next(inserted_node)def index(self, item):myindex = 0current = self.headif self.size():#非空执行操作，空list不做任何操作count = 0while current.get_data() != item:count += 1current = current.get_next()return countdef pop(self, pos=None):"""pop操作，链表首都pop需要分类讨论"""#对于缺省值的处理if pos is None:pos = self.size() - 1 if pos == 0:self.head = self.head.get_next()return self.headelif 0 < pos < self.size():current = self.headprevious = Nonecount = 0while count != pos:previous = currentcurrent = current.get_next()count += 1previous.set_next(current.get_next())return currentif __name__ == '__main__':mylist = UnOrderedList()mylist.add(31)mylist.add(77)mylist.add(17)mylist.add(93)mylist.add(26)mylist.add(54)print(mylist.size())print(mylist.search(93))print(mylist.search(100))mylist.add(100)print(mylist.search(100))print(mylist.size())print('*'*50)mylist.remove(54)print(mylist.size())mylist.remove(93)print(mylist.size())mylist.remove(31)print(mylist.size())mylist.remove(11)print(mylist.size())print(mylist.search(93))print(mylist.append(66))print(mylist.size())print(mylist.pop(0))print(mylist.pop())print(mylist.index(17))print(mylist.insert(0, 333))print(mylist.insert(1, 444))print(mylist.index(333))print(mylist.index(444))

用单向链表实现的list各操作复杂度为：

• append O(n)
• pop O(n)
• pop(k) O(k)
• add O(1)
• isEmpty O(1)
• size O(n)
• index O(n)
• insert(k) O(k)
• remove O(n)

对比使用数组实现的内置list,有一定性能差距

1.2 有序list

数据结构相同，部分操作方法要做对应修改

class Node():"""链表中的节点，包括数据域和指针域；使用单链表实现"""def __init__(self, data):self.data = dataself.next = Nonedef get_data(self):return self.datadef set_next(self, next_node):#python内变量为引用类型，可视作指针self.next = next_nodedef get_next(self):return self.nextclass OrderedList():"""有序列表"""def __init__(self):self.head = Nonedef isEmpty(self):return self.head == Nonedef size(self):#排除特殊情况count = 0node = self.headwhile node != None:count += 1node = node.get_next()return countdef remove(self, item):"""1、找到则删除，未找到不做任何操作2、删除节点关键是定位相邻节点；左节点可以用previous表示，右节点用current.get_next()表示3、所以两个变量previous与current至关重要4、删除头结点要分类讨论"""found = Falsecurrent = self.headprevious = Nonewhile current != None and not found:if current.get_data() == item:#found相当于指示器，相当于breakfound = True#previous为None:删除头结点if previous == None:self.head = current.get_next()else:previous.set_next(current.get_next())else:previous = currentcurrent = current.get_next()def search(self, item):current = self.head#trigger1found = False #trigger2stop = False#current is not None既表示当前列表非空，也是判断条件：遍历到了list末尾；双关while current is not None and not found and not stop:if item == current.get_data():#找到目标值，触发trigger1,退出循环found = Trueelse:if item < current.get_data():#由于list顺序排列，一旦当前考察值大于目标值，触发trigger2,退出循环stop = Falseelse: #自增项;只有当前值小于目标值才自增current = current.get_next()return founddef add(self, item):#1、找到合适位置，记录在current、previous中current = self.headprevious = Nonestop = Falsewhile current is not None and not stop:if current.get_data() > item:stop = Trueelse:#只有trigger:stop未触发情况下才自增previous = currentcurrent = current.get_next()temp_node = Node(item)if current == self.head:temp_node.set_next(current)self.head = temp_nodeelse:temp_node.set_next(current)previous.set_next(temp_node)if __name__ == '__main__':mylist = OrderedList()mylist.add(31)mylist.add(77)mylist.add(17)mylist.add(93)mylist.add(26)mylist.add(54)print(mylist.size())print(mylist.search(93))print(mylist.search(100))

二、参考链接

http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganOrderedList.html

总结

以上是生活随笔为你收集整理的列表的实现与应用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。