一.什么是线性表
线性表是最基本、最简单、也是最常用的一种数据结构，它的定义是:由零个或多个数据元素组成的有限序列，线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的(注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储)，但是把最后一个数据元素的尾指针指向了首位结点)。
线性表的两种物理结构:顺序存储结构和链式存储结构
1.顺序存储结构
定义:用一段地址连续的存储单元依次存储线性表的数据元素
顺序表的优点与缺点
优点:可以快速的存取访问表中的元素
缺点:插入和删除麻烦,需要移动大量的数据,容易造成存储空间碎片
顺序表的实现
#顺序表的实现
class SeqList(object):
def __init__(self,max=10):
self.max = max
self.num = 0
self.data = [None] * self.max
def isEmpty(self):
return self.num is 0
def isFull(self):
return self.num is self.max
def __getitem__(self,i):
if not isinstance(i,int):
raise TypeError
if 0 <= i < self.num:
return self.data[i]
else:
raise IndexError
def __setitem__(self,key,value):
if not isinstance(key,int):
raise TypeError
if 0 <= key < self.num:
self.data[key] = value
else:
raise IndexError
def getLoc(self,value):
n = 0
for j in range(self.num):
if self.data[j] == value:
return j
if j == self.num:
return -1
def count(self):
return self.num
def append(self,value):
if self.num > self.max:
print('The list is full')
else:
self.data[self.num] = value
self.num += 1
def insert(self,i,value):
if not isinstance(i,int):
raise TypeError
if i < 0 and i > self.num:
raise IndexError
for j in range(self.num,i,-1):
self.data[j] = self.data[j-1]
self.data[i] = value
self.num += 1
def remove(self,i):
if not isinstance(i,int):
raise TypeError
if i < 0 and i >= self.num:
raise IndexError
for j in range(i,self.num):
self.data[j] = self.data[j+1]
self.num -= 1
def printList(self):
for i in range(0,self.num):
print(self.data[i])
def destory(self):
self.__init__()
2.链式存储结构
定义:链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域，最后一个节点指针为空(Null)
链表的优点:插入和删除方便,不需要移动大量的数据,使用于插入和删除频繁的操作
链表的缺点:查找十分麻烦,每次查找都需要遍历链表
单链表(动态链表)的实现:
#链表的实现 class ListNode(object): def __init__(self,data): self.data = data self.next = None def getData(self): return self.data def setData(self,newData): self.data = newData def getNext(self): return self.next def setNext(self,nextNode): self.next = nextNode class UnorderedList(object): def __init__(self): self.head = None def getHead(self): return self.head def isEmpty(self): return self.head is None def add(self,item): node = ListNode(item) node.next = self.head self.head = node def size(self): current = self.head count = 0 while current is not None: count += 1 current = current.getNext return count def search(self,item): current = self.head found = False while current is not None and not found: if current.getData() == item: found = True else: current = current.getNext() return found def append(self,item): node = ListNode(item) if self.isEmpty(): self.head = node else: current = self.head while current.getNext() is not None: current = current.getNext() current.setNext(node) def remove(self,item): current = self.head privious = None found = False while not found: if current.getData() == item: found = True else: privious = current current = current.getNext() if privious is None: self.head = current.getNext() else: privious.setNext(current.getNext()) def getValue(self): current = self.head currarr = [] while current != None: currarr.append(current.getData()) current = current.getNext() return currarr
静态链表:用数组描述的链表
定义:对于线性链表，也可用一维数组来进行描述。第一个下标和最后一个下标不存放任何数据,第一个游标指向第一个没有数据的下标,最后一个游标指向第一个有数据的下标，最后一个有数据的游标指向0
优点:这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针(游标)，故仍具有链式存储结构的主要优点
缺点:表长难以确定,失去了顺序存储结构随机存储的特性
下图为静态链表的插入操作:
循环链表
定义:循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环
循环链表的特点:
1.循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针
2.在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现
循环链表的实现:
class Node(object):
def __init__(self,item):
self.item = item
self.next = None
class CycleSingleLinkList(object):
def __init__(self,node=None):
self.head = node
def isEmpty(self):
return self.head is None
def length(self):
if self.isEmpty():
return 0
current = self.head
count = 1
while current.next != self.head:
count += 1
current = current.next
return count
def travel(self):
if self.isEmpty():
print("")
return
current = self.head
while current.next != self.head:
print(current.item,end="")
current = current.next
print(current.item,end="")
print("")
def add(self,item):
node = Node(item)
if self.isEmpty():
node.next = node
self.head = node
else:
current = self.head
while current.next != self.head:
current = current.next
node.next = self.head
self.head = node
current.next = node
def append(self,item):
node = Node(item)
if self.isEmpty():
self.head = node
node.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = node
node.next = self.head
def insert(self,pos,item):
if pos <= 0:
self.add(item)
elif pos > (self.length() - 1):
self.append(item)
else:
node = Node(item)
current = self.head
count = 0
while count < (pos - 1):
count += 1
current = current.next
node.next = current.next
current.next = node
def remove(self,item):
if self.isEmpty():
return
current = self.head
pre = None
if current.item == item:
if current.next != self.head:
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
else:
self.head = None
else:
pre = self.head
while current.next != self.head:
if current.item == item:
pre.next = current.next
return
else:
pre = current
current = current.next
if current.item == item:
pre.next = current.next
def search(self,item):
if self.isEmpty():
return False
current = self.head
if current.item == item:
return true
while current.next != self.head:
current = current.next
if current.item == item:
return True
return False
if __name__ == '__main__':
l = CycleSingleLinkList()
l.append(1)
l.append(2)
l.append(3)
l.add(4)
l.insert(2,5)
l.remove(5)
print(l.search(5))
print(l.length())
l.travel()
双向链表
定义:双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表
双向链表实现:
#双向循环链表 class Node(object): def __init__(self,data=None): self.data = data self.next = None self.prev = None class dblLinkList(object): def __init__(self): head = Node() tail = Node() self.head = head self.tail = tail self.head.next = self.tail self.tail.pre = self.head def len(self): length = 0 node = self.head while node.next != self.tail: length += 1 node = node.next return length def append(self,data): node = Node(data) pre = self.tail.pre pre.next = node node.pre = pre self.tail.pre = node node.next = self.tail return node def get(self,index): length = self.len() index = index if index >= 0 else length + index if index >= length or index < 0:return None node = self.head.next while index: node = node.next index -= 1 return node.data def set(self,index,data): node = self.get(index) if node: node.data = data return node def insert(self,index,data): length = self.len() if abs(index + 1) > length: return False index = index if index >= 0 else index + 1 + length next_node = self.get(index) if next_node: node = Node(data) pre_node = next_node.pre pre_node.next = node node.pre = pre_node node.next = next_node next_node.pre = node return node def delete(self,index): node = self.get(index) if node: node.pre.next = node.next node.pre.pre = node.pre return True return False def clear(self): self.head.next = self.tail self.tail.pre = self.head if __name__ == '__main__': l = dblLinkList() l.append(111) l.append(222) l.append(333) print(l.get(0)) print(l.get(1)) print(l.get(2))