廊坊网络推广建站市场调研报告ppt
用Python链表实现有序表与无序表
《数据结构与算法》MOOC（北大地空）课堂笔记
2020.4
by dlnb526
啥是链表
链表,顾名思义，顾名思义，链表像锁链一样，由一节节节点连在一起，组成一条数据链。
为什么要使用链表？
在之前用了python中的列表（list）来实现各种数据结构，然而有的语言可能并没有提供像python的列表一样强大的功能，我们必须要自己实现列表。
无序列表
概述
列表可以看作是一个无序的列表。
无序，也就是说它里面的元素没有一定的顺序，比如这样一个列表：
a = [1,2,'ads',54,32]
这里面的每个元素没有按照一定的规则排序，所以就叫无序。
无序列表应该有以下的方法
list() 创建一个新的空列表。它不需要参数，而返回一个空列表。
add(item) 将新项添加到列表，没有返回值。假设元素不在列表中。
remove(item) 从列表中删除元素。需要一个参数，并会修改列表。此处假设元素在列表中。
search(item) 搜索列表中的元素。需要一个参数，并返回一个布尔值。
isEmpty() 判断列表是否为空。不需要参数，并返回一个布尔值。
size() 返回列表的元素数。不需要参数，并返回一个整数。
append(item) 在列表末端添加一个新的元素。它需要一个参数，没有返回值。假设该项目不在列表中。
index(item) 返回元素在列表中的位置。它需要一个参数，并返回位置索引值。
此处假设该元素原本在列表中。
insert(pos,item) 在指定的位置添加一个新元素。它需要两个参数，没有返回值。假设该元素在列表中并不存在，并且列表有足够的长度满足参数提供的索引需要。
pop() 从列表末端移除一个元素并返回它。它不需要参数，返回一个元素。假设列表至少有一个元素。
pop(pos) 从指定的位置移除列表元素并返回它。它需要一个位置参数，并返回一个元素。假设该元素在列表中。
节点
为了实现无序列表，我们采用链表的方式。
链表最基本的元素是节点。
每个节点对象必须持有至少两条信息。
首先，节点必须包含列表元素本身。我们将这称为该节点的“数据区”（data field）。
此外，每个节点必须保持到下个节点的引用。
如果没有下一个节点，那我们就记录为None
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. 添加数据项add
通过之前的方式建立了一个节点，如果初始化它我们知道他是一个在开头的节点，后面是None.由于无序表是从表头开始逐个向后查找，新数据所以插入到表头是我们的最佳选择。
def add(self,item):
temp = Node(item) #新的要插入的数据初始化为一个节点
temp.setNext(self.head)#但当前节点的下一个指向为之前链表的头部
self.head = temp#把插入的节点设为新链表的头部
2. size()的实现 和 search()的实现
def size(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
没什么可说的，设置一个计数器，然后遍历元素。
3. remove(item)实现
我们需要先用类似search的方法找到元素，然后它指向的后一个元素和前一个元素怎么连在一起呢？
这时就需要维护前一个节点的引用。
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())
好了那下面我们来看无序表的完整实现
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))
有序链表
概述
之前无序链表时我们就能推测出有序的意思，也就是排列过大小的呗~
有序表依据数据项的可比性质（如整数大小，字母表前后）来决定数据项在列表中的位置。
比如下面我们要实现越小的越靠近列表头的操作。
有序表中的操作：
OrderedList()：创建一个新的空有序列表。它返回一个空有序列表并且不需要传递任何参数。
add(item):在保持原有顺序的情况下向列表中添加一个新的元素，新的元素作为参数传递进函数而函数无返回值。假设列表中原先并不存在这个元素。
remove(item):从列表中删除某个元素。欲删除的元素作为参数，并且会修改原列表。假设原列表
中存在欲删除的元素。
search(item)：在列表中搜索某个元素，被搜索元素作为参数，返回一个布尔值。
isEmpty()：测试列表是否为空，不需要输入参数并且其返回一个布尔值。
size()：返回列表中元素的数量。不需要参数，返回一个整数。
index(item)：返回元素在列表中的位置。需要被搜索的元素作为参数输入，返回此元素的索引值。假设这个元素在列表中。
pop()：删除并返回列表中的最后一项。不需要参数，返回删除的元素。假设列表中至少有一个元素。
pop(pos)：删除并返回索引 pos 指定项。需要被删除元素的索引值作为参数，并且返回这个元素。假设该元素在列表中。
有序链表的实现
其实大部分操作都和无序表相同
search()方法
在无序表中如果不存在，搜索的时候会遍历整个表。
但是在有序表中，因为有顺序，一旦当前节点大于要查找的数据，就直接宣判死刑可以返回False了。
def search(self,item):
current = self.head
found = False
stop = False# 加入了一个stop可以直接停住
while current != None and not found and not stop:#这里有三个条件
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
add()方法
和无序表相比，改动最大的方法是 add。回想一下在无序列表中的 add 方法，只需要在原列表头加一个新的节点。然而在有序表里我们要找到大小合适的位置才行。
所以我们还是要定位一个previous（前一个元素）。
def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
有序表的完整实现如下：
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 OrderedList:
def __init__(self):
self.head = None
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()
return found
def add(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()
temp = Node(item)
if previous == None:
temp.setNext(self.head)
self.head = temp
else:
temp.setNext(current)
previous.setNext(temp)
def isEmpty(self):
return self.head == None
def length(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def traverse(self):
current = self.head
while current != None:
print(current.getData())
current = current.getNext()
mylist = OrderedList()
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.traverse()
总结分析
当分析链表方法的复杂度时，我们应该考虑它们是否需要遍历链表。考虑一个有 n 个节点的链表，isEmpty 方法复杂度是 O（1），因为它只需要检查链表的头指针是否为 None。对于方法 size，则总需要 n 个步骤，因为除了遍历整个链表以外，没有办法知道链表的节点数。因此，size 方法的复杂度是 O（n）。无序列表的 add 方法的复杂度是 O（1），因为我们永远只需要在链表的头部简单地添加一个新的节点。但是，search、remove 和在有序列表中的 add 方法，需要遍历。尽管在平均情况下，它们可能只需要遍历一半的节点，但这些方法的复杂度都是 O(n)，因为在最糟糕的情况下需要遍历整个链表。
参考资料：MOOC配套教材及代码
《Python数据结构与算法分析》 第2版