一.什么是线性表

线性表是最基本、最简单、也是最常用的一种数据结构，它的定义是:由零个或多个数据元素组成的有限序列，线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的(注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储)，但是把最后一个数据元素的尾指针指向了首位结点)。

线性表的两种物理结构:顺序存储结构和链式存储结构

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 = nextNodeclass 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 = Noneclass 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 Falseif __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 = Noneclass 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.headif __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))