1.单向循环列表
单项循环列表是一种数据结构，它是由一组节点组成的，每个节点包含一个数据元素和一个指向下一个节点的指针。与普通的单向链表不同的是，最后一个节点的指针指向第一个节点，形成一个环。
单项循环列表具有以下特点：
- 可以像普通的单向链表一样遍历整个列表，但无需处理最后一个节点的特殊情况。
- 可以通过任何一个节点遍历整个列表，因为最后一个节点指向第一个节点。
- 可以动态地添加、删除节点，而不需要考虑头结点或尾节点的特殊情况。因为最后一个节点指向第一个节点，所以添加或删除节点时只需要修改指针即可。
单项循环列表源代码及理解：
class Node: def __init__(self, elem): self.elem = elem self.next = None class SingleCycleList: #构建单向循环列表 def __init__(self, node = None): self._head = node if node: #不写也可以？ node.nex = node #不写也可以？ def is_empty(self): #不变 return self._head == None def append(self, item): node = Node(item) if self._head == None: self._head = node node.next = node else: cur = self._head while cur.next != self._head: #在节点中的next不为空的情况下(不是最后一个节点) cur = cur.next #遍历列表，把下一节点地址赋给此几点 # print(cur) cur.next = node #类的实例化，cur.next也是Node类！cur.next存入node的地址，同时self._head.next 也被赋值！！！ node.next = self._head def length(self): if self._head == None: return 0 cur = self._head count = 1 #count 从1开始 while cur.next != self._head: count += 1 cur = cur.next #遍历 return count def travel(self): cur = self._head # 遍历开始 while cur.next != self._head: print(cur.elem,end=",") cur = cur.next # 遍历 print(cur.elem) #补上最后一个节点 def headadd(self, item): node = Node(item) if self.is_empty(): self._head = node self._head.next = self._head else: cur = self._head while cur.next != self._head: cur = cur.next cur.next = node node.next = self._head self._head = node def addatpos(self, pos, item): node = Node(item) count = 1 cur = self._head while count != pos: count += 1 cur = cur.next node.next = cur.next cur.next = node def search(self, item): if self.is_empty(): return "empty" cur = self._head while cur.next != self._head: #遍历 if cur.elem == item: return "Bingo" else: cur = cur.next print(cur.elem) if cur.elem == item: return "Bingo" return "Nogo" def deletatpos(self, pos): count = 1 cur = self._head if self.length() == pos: self._head = self._head.next while count != pos: count += 1 cur = cur.next cur.next = cur.next.next scl = SingleCycleList() scl.headadd(1) scl.headadd(2) scl.headadd(3) scl.append(22) scl.append(33) scl.append(44) scl.addatpos(3,888888) print(scl.travel()) scl.deletatpos(7) print(scl.travel())
2. 栈与队列
栈与队列都是是一种容器，用于存入数据元素。
栈是一种后进先出（LIFO）的数据结构，它只允许在栈顶进行插入和删除操作，所以也被称为“压栈”和“弹栈”。栈的应用场景比较广泛，如函数调用栈、表达式求值、回溯算法等。
队列是一种先进先出（FIFO）的数据结构，它允许在队尾进行插入操作，在队首进行删除操作，也被称为“入队”和“出队”。队列的应用场景也比较多，如任务调度、消息队列等。
因此，栈和队列的主要区别在于它们的插入和删除操作的位置不同。在栈中，只有最近插入的元素才能被访问到，而在队列中，先插入的元素先被访问到。此外，栈和队列的复杂度也不相同，具体取决于具体实现。
2.1 栈（stack）：
- 栈的特性： last in first out
- 栈的建立：入栈，出栈
源代码：
class Stack: #用顺序表实现方法 def __init__(self): self.__list = [] def push(self,item): self.__list.append(item) #为什么在尾部加item？**因为对于顺序表来说，在尾部添加时间复杂度为O(1);对于链表来说，正好相反 def pop(self): self.__list.pop() def peek(self): if self.__list: return self.__list[-1] else: return None def size(self): return len(self.__list) def is_empty(self): if len(self.__list): return "Not empty" return "empty" st = Stack() st.push(1) st.push(2) st.push(3) st.pop() st.pop() print(st.is_empty()) print(st.peek())
2.2 队列（queue）：只能从一段添加，从另外一段获取
- 队列的特性：first in first out
源代码:
class queue: #取的一端为队头，压的一段为队尾 def __init__(self): self.__list = [] def enqueue(self, item): self.__list.append(item) def dequeue(self): self.__list.pop(0) def is_empty(self): if self.__list: return "Not empty" else: return "empty" def size(self): return len(self.__list) def pr(self): #测试用 return self.__list qu = queue() qu.enqueue(1) qu.enqueue(2) qu.enqueue(3) qu.enqueue(4) qu.enqueue(88) qu.dequeue() qu.dequeue() a = qu.pr() print(a)
