赞
踩
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
(2)无序链表初始化
无序表必须要有对第一个节点的引用信息,设立一个属性head,保存对第一个节点的引用
空表的head为None,随着数据项的加入,无序表的head始终指向链条中的第一个节点
def __init__(self):
self.head = None
(3)判断无序表是否为空
包含的head只是对首个节点Node的引用,判断空表的isEmpty()很容易实现,实现方式如下所示
def isEmpty(self):
return self.head == None
(4)添加元素
由于无序表并没有限定数据项之间的顺序,新数据项可以加入到原表的任何位置,按照实现的性能考虑,应添加到最容易加入的位置上,也就是添加到表头head处
def add(self,item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
(5)链表大小
从链条头head开始遍历到表尾同时用变量累加经过的节点个数
def length(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
(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
(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())
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))
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。