数组
数组:在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在python中没有数组，只能用列表模拟。
读入：
|
1 |
a = list(map(int, input().split())) |
注意：
$$
a 的下标 i \in [-n, n), n = len(a)
$$
栈
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO）的线性表。在栈中进行插入和删除操作的一端称为栈顶（top），相应地，另一端称为栈底（bottom）。不含数据元素的栈称为空栈。
code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# 在具体的题目中数据结构不一定需要封装成类 # 这里只是示范其基本操作 class Stack: a = [0 for i in range(N)] # N 为数组大小，此处数据结构都是用数组模拟 tt = -1 # 栈顶指针 # 向栈顶压入元素 def push(self, x): self.tt += 1 self.a[self.tt] = x # 将栈顶元素弹出 def pop(self): self.tt -= 1 # 询问栈是否空 def empty(self): return self.tt < 0 # 询问栈顶元素 def top(self): return self.a[self.tt] # 询问大小 def siz(self): return self.tt + 1 # 清空栈 def clear(self): self.tt = -1; # 打印栈 def Print(self): for i in range(self.tt + 1): print(self.a[i], end=' \n'[i == self.tt]) |
队列
队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入的一端称为队尾（rear），允许删除元素的一端称为队头（front）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Queue: a = [0 for i in range(N)] hh = 0 # 队头指针 tt = -1 # 队尾指针 # 向队尾插入一个元素 def push(self, x): self.tt += 1 self.a[self.tt] = x # 从队头弹出一个元素 def pop(self): self.hh += 1 # 询问队头元素 def front(self): return self.a[self.hh] # 询问队列是否空 def empty(self): return self.tt < self.hh # 询问队列大小 def siz(self): return self.hh - self.tt + 1 # 清空 def clear(self): self.hh = 0 self.tt = -1 # 打印队列 def Print(self): for i in range(self.hh, self.tt + 1): print(self.a[i], end=' \n'[i == self.tt]) |
链表
是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
# 注意：有些板子是用二维列表模拟链表 # 但是，用二维列表实现较为繁琐，这里就不做介绍 class Mylist: head = -1 # 头指针，-1表示空 e = [0 for i in range(N)] # 数据域 ne = [0 for i in range(N)] # 指针域 idx = 0 # 数组中分配位置 # 清空 def clear(self): self.head = -1 self.idx = 0 # 头插 def add_to_head(self, x): self.e[self.idx] = x self.ne[self.idx] = self.head self.head = self.idx self.idx += 1 # 插入k后 # 注意：这里的k指的是下标是k而非链表中的第k个元素 # 插入和删除链表中第k个元素的具体实现读者可以自行思考 def add(self, k, x): self.e[idx] = x self.ne[idx] = self.ne[k] self.ne[k] = self.idx self.idx += 1 # 删除k # 注意删除头节点与其不同 def remove(self, k): self.ne[k] = self.ne[self.ne[k]] # 头节点的删除 def remove_head(self): self.head = self.ne[self.head] # 打印链表 def Print(self): i = self.head while (~i): # 当i==-1时表示遍历完毕 j = self.e[i] print(j, end=' ') i = self.ne[i] print() |
发表回复