表，分为无序表和有序表。
无序表
无序表概念：数据项按照相对位置存在的数据列表，跟数据的大小无关。
例如：[21, 44, 5, 65, 32]
在Python中，无序表的数据结构完全可以用Python本身的List表示。list的方法和功能如下：
| 方法 | 功能 |
|---|---|
| .append(item) | 将item插入到列表最后 |
| .index(item) | 返回item在列表中的位置 |
| .insert(pos, item) | 在列表中pos的位置插入item |
| .pop() | 移除列表中的最后一个元素 |
| .pop(pos) | 移除列表中位置为pos的元素 |
这对于c/c++来说，几乎是作弊。为了学习表的精髓和灵魂，我们同样采用链表实现无序表和有序表。
最基本元素：节点Node。上图中一个蓝色和黄色部分组成一个节点。其至少包含两个基本信息：（1）数据项本身；（2）指向下一节点的引用信息。
# 链表实现：节点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
测试代码：
temp = Node(93)
temp.getData()
输出结果：
93
无序表的实现：
# 无序表
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
# add方法实现
def add(self, item):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
# size实现
def size(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
# search 实现
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
# remove(item)
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())
| 方法 | 注意事项 |
|---|---|
| add(item) | 链表中最容易添加元素的位置是“表头”， |
| size() | 没有方法可以直接读取列表长度，所以需要从头遍历整个链表得到size |
| search(item) | 寻找元素同样需要遍历整个链表 |
| remove(item) | 移除之前，需要先找到元素。但是移除的时候，要将该移除节点的指向信息传递给前一个节点，然后删除该节点 |
有序表
有序表中的数据按照某种可比性质放入列表，例如数字大小、字母的先后顺序，这些性质决定了数据在列表中的位置。
有序表中方法和无序表基本类似，在添加元素add(item)和寻找元素search(item)有细微区别。
# 有序表OrderList实现
class OrderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
# size实现
def size(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
# remove(item)
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())
# search 方法 当前节点的数据大于找的数据，就False
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
# add 方法实现
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)