[数据结构与算法] 【算法与数据结构】2.抽象数据类型及实现（链表2及栈、集合实现）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【算法与数据结构】2.抽象数据类型及实现（链表2及栈、集合实现） -> 正文阅读

[数据结构与算法]【算法与数据结构】2.抽象数据类型及实现（链表2及栈、集合实现）

空链表


class IntNode():
	def __init__(self,i,n):
		self.item = i
		self.next = n

class SllList():
	def __init__(self,x=None):
		if x is None:
			self.__first = None
			self.__size = 0
		else:
			self.__first = IntNode(x,None)
			self.__size = 1

	def add_first(self,x):
		self.__first = IntNode(x,self.__first)
		self.__size+=1

	def get_first(self):
		return self.__first.item

	def add_last(self,x):
		p = self.__first
		while p.next is not None:
			p = p.next
		p.next = IntNode(x,None)
		self.__size+=1

	def size(self):
		return self.__size

l = SllList()
l.add_last(1)  #报错！！！！！ 此时add last（）出问题

#改进方法1
class IntNode():
	def __init__(self,i,n):
		self.item = i
		self.next = n

class SllList():
	def __init__(self,x=None):
		if x is None:
			self.__first = None
			self.__size = 0
		else:
			self.__first = IntNode(x,None)
			self.__size = 1

	def add_first(self,x):
		self.__first = IntNode(x,self.__first)
		self.__size+=1

	def get_first(self):
		return self.__first.item

	def add_last(self,x):
		p = self.__first

		'''if p is None:              #不够优雅
			self.__first = IntNode(x,None)
			self.__size += 1
			return'''

		while p.next is not None:
			p = p.next
		p.next = IntNode(x,None)
		self.__size+=1

	def size(self):
		return self.__size

l = SllList()
l.add_last(1)

哨兵机制

其本质问题出现在空链表与非空链表的第一个元素（类型）不一样，故需要一样的数据类型，即加一个哨兵在最前面。


class IntNode():
	def __init__(self,i,n):
		self.item = i
		self.next = n

class SllList():
	def __init__(self,x=None):
		self.__sentinel = IntNode(49,None)
		if x is None:
			self.__size = 0
		else:
			self.__sentinel.next = IntNode(x,None)
			self.__size = 1

	#def add_first(self,x):
		#self.__first = IntNode(x,self.__first)
		#self.__size+=1

	#def get_first(self):
		#return self.__first.item

	#def add_last(self,x):
		#p = self.__sentinel

		'''if p is None:              #不够优雅
			self.__first = IntNode(x,None)
			self.__size += 1
			return'''

		while p.next is not None:
			p = p.next
		p.next = IntNode(x,None)
		self.__size+=1

	def size(self):
		return self.__size

l = SllList(10)
l.add_last(1)

在这里插入图片描述
add_first(）get_first 的修改

	def add_first(self,x):
		original_first = self.__sentinel.next
		self.__sentinel.next = IntNode(x,original_first)
		self.__size+=1
		
	def get_first(self):
		return self.__sentinel.next.item

小问题：把所有元素循环一遍才能向最后添加一个元素，利用缓存机制
在这里插入图片描述

双向链表

如果用缓存的方式，以下哪种或哪几种方法会很慢？:
add_last()
get_last()
remove_last()

remove_last()*最慢，因为remove_last()后需要找到倒数第二个值，而我们并不知道倒数第二个值，需要从头到尾再遍历一遍。
在这里插入图片描述
如果删除了5，10，15 还会遇到类型差异的问题，故可以加入一个后哨兵来规避这个情况。

但是其还是不够简洁优雅，可以考虑循环结构。

在这里插入图片描述

#初始化
class IntNode():
	def __init__(self,i,n,p):
		self.item = i
		self.next = n
		self.prev = p

class SllList():
	def __init__(self,x=None):
		self.__sentinel = IntNode(49,None,None)
		self.__sentinel.next = self.__sentinel
		self.__sentinel.prev = self.__sentinel
		self.__last = self.__sentinel.prev
		if x is None:
			self.__size = 0
		else:
			self.__sentinel.next = IntNode(x,self.__sentinel,self.__sentinel)
			self.__sentinel.prev = self.__sentinel.next
			self.__size = 1
l = SllList(10)

增加一个数据
在这里插入图片描述
两个理解角度，编程思路

		self.__sentinel.next = IntNode(x,self.__sentinel.next,self.__sentinel)

		'''original_first = self.__sentinel.next
		news_first = IntNode(None,None,None)
		news_first.next = original_first
		news_first.prev = self.__sentinel
		self.__sentinel.next = news_first'''

这行代码改了三条线
在这里插入图片描述
完整代码（四根线为）

	def add_first(self,x):
		self.__sentinel.next = IntNode(x,self.__sentinel.next,self.__sentinel)
		self.__sentinel.next.next = self.__sentinel.next

		'''original_first = self.__sentinel.next
		news_first = IntNode(None,None,None)
		news_first.next = original_first
		news_first.prev = self.__sentinel
		self.__sentinel.next = news_first
		
		original_first.prev = new_first

		'''
		self.__size+=1

抽象数据类型

在这里插入图片描述

栈结构实现

class Stack():
	def __init__(self):
		self.__data = []

	def push(self,x):
		self.__data.append(x)

	def pop(self):
		return self.__data.pop()

b = Stack()
b.push(1)
b.push(2)
b.push(3)
print(b.pop())
print(b.pop())
print(b.pop())

-->
3
2
1

集合结构实现

class Set():
	def __init__(self,data=[]):
		self.__data = []
		for item in data:
			if item not in self.__data:
				self.__data.append(item)

	def add(self,x):
		if x not in self.__data:
			self.__data.append(x)

	def get_all(self):
		return self.__data

c = Set()
c.add(1)
c.add(1)
c.add(2)
c.add(2)
c.add(3)
print(c.get_all())
-->
[1, 2, 3]

但是做如下操作

d = c.get_all()
d.append(15)
d.append(15)
d.append(15)
d.append(15)
d.append(15)
d.append(1)
print(c.get_all())
-->
[1, 2, 3, 15, 15, 15, 15, 15, 1]

我们可以看到集合里的值被更改了，其本质原因“ return self.__data”返回了我们的内部数据，
在这里插入图片描述
我们可以做如下的改进，并不是返回我们的变量表，而是返回一个他的复制品，即“return list(self.__data)”，这样就规避了用户更改的风险。但是因为需要创建列表，也同时也会让算法的复杂度上升。
在以后的问题中，应该做到综合考量算法复杂度和完整性的问题。

class Set():
	def __init__(self,data=[]):
		self.__data = []
		for item in data:
			if item not in self.__data:
				self.__data.append(item)

	def add(self,x):
		if x not in self.__data:
			self.__data.append(x)

	def get_all(self):
		return list(self.__data)

c = Set()
c.add(1)
c.add(1)
c.add(2)
c.add(2)
c.add(3)
print(c.get_all())

d = c.get_all()
d.append(15)
d.append(15)
d.append(15)
d.append(15)
d.append(15)
d.append(1)
print(c.get_all())