数据结构下

mac2024-01-26  35

数据结构与算法(增加)

队列 定义:、队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 特点:FIFO(先进先出),front头,rear尾(初始值都等于-1,但front是在第一个数据的前一个位置,rear在正末尾数据位置) 数组实现栈声明如下 MAXSIZE = 10 queue = [0]*MAXSIZE front = rear = -1 具体范例

MAXSIZE = 10 queue = [0]*MAXSIZE front = rear = -1 def enqueue(data): #进队 global queue global front global rear if rear == 4: print('满队') else: rear += 1 queue[rear] = data def dequeue(data): #出队 global queue global front global rear if front == rear: print('队空') else: front +=1 data=queue[front]

(环形队列还不太熟悉,下个博客再探讨)

单链表: 分两部分,结点和表身 结点 class node: def init(self,name,score): self.name = name self.score = score self.next = None 链表 class Link:

# 构造函数 def __init__(self): self.head = Student(None,None,None) # 头节点为空 self.tail = self.head self.size = 1 具体范例 class Node(object): # 结点类 def __init__(self, item): self.item = item self.next = None class SingleLinklist(object): # 单链表 def __init__(self, node=None): self.__head = node def is_empty(self): # 链表是否为空,如果为空,则返回真 return self.__head is None # def length(self): # 链表长度 cur = self.__head # 设置一个辅助变量游标cur count = 0 while cur is not None: count += 1 cur = cur.next return count def trave(self): # 遍历整个列表 cur = self.__head # 设置一个辅助变量游标cur while cur is not None: print(cur.item, end=" ") cur = cur.next print("") # 输出换行 def add(self, item): # 链表头部添加元素,item为要保存的具体数据 node = Node(item) node.next = self.__head self.__head = node def append(self, item): # 链表尾部添加元素 node = Node(item) # 如果链表为空,需要特殊处理 if self.is_empty(): self.__head = node else: cur = self.__head while cur.next is not None: cur = cur.next # 退出循环时,cur指向的是尾接点 def insert(self, pos, item): # 链表指定位置插入元素 # 在头部添加元素 if pos <= 0: self.add(item) elif pos >= self.length(): self.append(item) else: cur = self.__head count = 0 while count < (pos - 1): count += 1 cur = cur.next # 退出循环时,cur指向pos的前一个位置 node = Node(item) node.next = cur.next cur.next = node def remove(self, item): # 删除节点 cur = self.__head pre = None while cur is not None: # 找到要删除的元素 if cur.item == item: # 在头部找到了元素 if cur == self.__head: self.__head = cur.next else: pre.next = cur.next return # 不是要找的元素, 移动游标 pre = cur cur = cur.next def search(self, item): # 查找节点是否存在 cur = self.__head while cur is not None: if cur.item == item: return True cur = cur.next return False if __name__ == '__main__': ``
最新回复(0)