数据结构的栈,队列,双端队列,顺序表,链表,二叉树
程序员文章站
2022-03-26 20:10:04
基础数据结构 栈(stack) 队列 (queue) 双端队列 ( deque ) 顺序表 与 内存 简单了解一下内存 顺序表 顺序表的弊端:顺序表的结构需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁。 链表 (Linked list) 二叉树 二叉树 根节点 叶子节点 ......
基础数据结构
栈(stack)
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。 这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈, 它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈, 它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。 栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据, 先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。 栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。 - 特性:先进后出的数据结构 # 应用:每个 web 浏览器都有一个返回按钮。当你浏览网页时,这些网页被放置在一个栈中(实际是网页的网址)。 你现在查看的网页在顶部,你第一个查看的网页在底部。如果按‘返回’按钮,将按相反的顺序浏览刚才的页面。
# 使用python代码实现一个栈 - stack() 创建一个空的新栈。 它不需要参数,并返回一个空栈。 - push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。 - pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。 - peek() 从栈返回顶部项,但不会删除它。不需要参数。 不修改栈。 - isempty() 测试栈是否为空。不需要参数,并返回布尔值。 - size() 返回栈中的 item 数量。不需要参数,并返回一个整数。 class stack(): def __init__(self): self.items = [] def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return len(self.items) - 1 def isempty(self): return self.items == [] def size(self): return len(self.items) stack = stack() stack.push(1) stack.push(2) stack.push(3) print('栈顶元素下标:',stack.peek()) print(stack.isempty()) print('元素个数:',stack.size()) print(stack.pop()) print(stack.pop()) print(stack.pop())
队列 (queue)
- 队列:先进先出 - 应用场景: - 我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时, 他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。 如果你是最后一个,你必须等待你前面的所有其他任务打印。
# 使用python代码实现一个队列 - queue() 创建一个空的新队列。 它不需要参数,并返回一个空队列。 - enqueue(item) 将新项添加到队尾。 它需要 item 作为参数,并不返回任何内容。 - dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。 - isempty() 查看队列是否为空。它不需要参数,并返回布尔值。 - size() 返回队列中的项数。它不需要参数,并返回一个整数。 class queue(): def __init__(self): self.items = [] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def isempty(self): return self.items == [] def size(self): return len(self.items) q = queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print(q.dequeue()) print(q.dequeue()) print(q.dequeue())
# 面试题 - 烫手的山芋 - 烫手山芋游戏介绍:6个孩子围城一个圈,排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋, 需要在计时器计时1秒后将山芋传递给下一个孩子,依次类推。规则是,在计时器每计时7秒时,手里有山芋的孩子退出游戏。 该游戏直到剩下一个孩子时结束,最后剩下的孩子获胜。请使用队列实现该游戏策略,排在第几个位置最终会获胜。 # 解题思路 - 让手里有山芋的孩子永远排在队列的头部 class queue(): def __init__(self): self.items = [] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def isempty(self): return self.items == [] def size(self): return len(self.items) kids = ['a','b','c','d','e','f'] queue = queue() for kid in kids: queue.enqueue(kid) #a对头f队尾 while queue.size() > 1: for i in range(6): #每循环一次,山芋传递一次,手里有山芋的孩子永远在对头位置 kid = queue.dequeue() queue.enqueue(kid) queue.dequeue() print('获胜的选手是:',queue.dequeue()) for a in range(len(kids)): if kids[a] == kid: print('排在第:%d会获胜'%a) # 执行结果 获胜的选手是: e 排在第:4会获胜
# 面试题 使用两个队列实现一个栈 class queue(): def __init__(self): self.items = [] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items) alist = [1,2,3,4,5] q1 = queue() for i in alist: q1.enqueue(i) q2 = queue() while q1.size() > 0: #将q1中的n-1个值取出放入到q2中 while q1.size() > 1: item = q1.dequeue() q2.enqueue(item) print(q1.dequeue()) q1,q2 = q2,q1
双端队列 ( deque )
同队列相比,有两个头部和尾部。可以在双端进行数据的插入和删除,提供了单数据结构中栈和队列的特性. # 用python代码实现一个双端队列 - deque() 创建一个空的新 deque。它不需要参数,并返回空的 deque。 - addfront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。 - addrear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。 - removefront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。 - removerear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。 - isempty() 测试 deque 是否为空。它不需要参数,并返回布尔值。 - size() 返回 deque 中的项数。它不需要参数,并返回一个整数。 class deque(): def __init__(self): self.items = [] def addfront(self,item): self.items.insert(0,item) def addrear(self,item): self.items.append(item) def removefront(self): return self.items.pop() def removerear(self): return self.items.pop(0) def isempty(self): return self.items == [] def size(self): return len(self.items) q = deque() q.addfront(1) q.addfront(2) q.addfront(3) print(q.removerear()) print(q.removerear()) print(q.removerear())
- 双端队列应用案例:回文检查 - 回文是一个字符串,读取首尾相同的字符,例如,radar toot madam。 class deque(): def __init__(self): self.items = [] def addfront(self,item): self.items.insert(0,item) def addrear(self,item): self.items.append(item) def removefront(self): return self.items.pop() def removerear(self): return self.items.pop(0) def isempty(self): return self.items == [] def size(self): return len(self.items) def ishuiwen(s): ex = true q = deque() for ch in s: q.addfront(ch) while q.size() > 1: if q.removefront() != q.removerear(): ex = false break return ex print(ishuiwen('上海自来水来自海上')) # 执行结果 true
顺序表 与 内存
-
简单了解一下内存
- 内存在计算机的作用 - 用来存储和运算二进制的数据 - 问题:计算机如何计算1+2? - 将1和2的二进制类型的数据加载到计算机的内存中,然后使用寄存器进行数值的预算。 - 变量的概念 - 变量可以理解为某一块内存(实际是引用的某一块内存的地址) - 内存空间是有两个默认的属性: - 内存空间的大小 - bit(位):一个bit大小的内存空间只能存放一位二进制的数 - byte(字节):8bit - kb:1024byte - 内存空间的地址 - 使用一个十六进制的数值表示 - 作用:让cup寻址 - 理解a=10的内存图(引用,指向) - 引用:变量==》内存空间的地址 - a = 10:a变量/引用/内存空间的地址 - 指向:如果变量或者引用表示的是某一块内存空间地址的话,则该变量或者该引用指向了该块内存
-
顺序表
- 集合中存储的元素是有顺序的,顺序表的结构可以分为两种形式:单数据类型(np.array数组)和多数据类型(列表,元组)。 - python中的列表和元组就属于多数据类型的顺序表 - 单数据类型顺序表的内存图 (内存连续开辟,每个内存空间大小一致)
- 多数据类型顺序表的内存图(内存非连续开辟)
-
顺序表的弊端:顺序表的结构需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁。
链表 (linked list)
- 链表(linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据, 而是每一个结点(数据存储单元)里存放下一个结点的信息(即地址) - 相对于顺序表,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理且进行扩充时不需要进行数据搬迁。
- 使用python实现单向链表 . is_empty():链表是否为空 . length():链表长度 . travel():遍历整个链表 . add(item):链表头部添加元素 . append(item):链表尾部添加元素 . insert(pos, item):指定位置添加元素 . remove(item):删除节点 . search(item):查找节点是否存在 # 代码 class node(): def __init__(self,item): self.item = item self.next = none class link(): def __init__(self): #构造出一个空链表 #_head存储的只能是空或者第一个节点的地址 self._head = none #向链表的头部插入一个节点 def add(self,item): #创建一个新的节点 node = node(item) node.next = self._head self._head = node def travel(self): #_head在链表创建好之后一定是不可变 cur = self._head while cur: print(cur.item) cur = cur.next def isempty(self): return self._head == none def size(self): cur = self._head count = 0 while cur: count += 1 cur = cur.next return count def append(self,item): node = node(item) #特殊情况 if self._head == none: self._head = node return cur = self._head pre = none#pre指向的是cur前一个节点 while cur: pre = cur cur = cur.next pre.next = node def search(self,item): find = false cur = self._head while cur: if cur.item == item: find = true break cur = cur.next return find def insert(self,pos,item): node = node(item) pre = none cur = self._head for i in range(pos): pre = cur cur = cur.next pre.next = node node.next = cur def remove(self,item): cur = self._head pre = none #删除的是第一个节点 if cur.item == item: self._head = cur.next return while cur: pre = cur cur = cur.next if cur.next == none: return if cur.item == item: pre.next = cur.next return
- 如何实现将单链表倒置 # 单链表(插入,删除,遍历) class node(): def __init__(self,item): self.item = item self.next = none class link(): def __init__(self): self._head = none def append(self,item): node = node(item) if self._head == none: self._head = node return cur = self._head pre = none while cur: pre = cur cur = cur.next pre.next = node def travel(self): cur = self._head while cur: print(cur.item) cur = cur.next def remove(self,item): cur = self._head pre = none #删除的是第一个节点 if cur.item == item: self._head = cur.next return while cur: pre = cur cur = cur.next if item == cur.item: pre.next = cur.next return def reverse(self): cur = self._head pre = none next_node = cur.next while cur: cur.next = pre pre = cur cur = next_node if cur: next_node = cur.next self._head = pre # 双向链表就是连续开辟三个内存空间,分别存放 数据 上个节点内存地址 下个节点内存地址
二叉树
-
二叉树
- 根节点
-
叶子节点:
- 左叶子节点
- 右叶子节点
- 树的层级/树的高度
-
二叉树的遍历
-
广度优先遍历
- 一层一层对节点进行遍历
-
深度优先遍历
- 前序:根左右
- 中序:左根右
- 后序:左右根
-
广度优先遍历
# 使用python代码实现二叉树 class node(): def __init__(self,item): self.item = item self.left = none self.right = none class tree(): def __init__(self): self.root = none def addnode(self,item): node = node(item) #如果插入第一个节点的情况 if self.root == none: self.root = node return cur = self.root q = [cur] #列表元素是我们进行遍历判断的节点 while q: nd = q.pop(0) if nd.left == none: nd.left = node return else: q.append(nd.left) if nd.right == none: nd.right = node return else: q.append(nd.right) def travel(self): #广度优先遍历 cur = self.root q = [cur] while q: nd = q.pop(0) print(nd.item) if nd.left: q.append(nd.left) if nd.right: q.append(nd.right) def forwoar(self,root): #深度优先 前序:根左右 if root == none: return print(root.item) self.forwoar(root.left) self.forwoar(root.right) def middle(self,root): #深度优先 前序:左根右 if root == none: return self.middle(root.left) print(root.item) self.middle(root.right) def back(self,root): #深度优先 前序:左右根 if root == none: return self.back(root.left) self.back(root.right) print(root.item)
郭楷丰
出 处:https://www.cnblogs.com/guokaifeng/
出 处:https://www.cnblogs.com/guokaifeng/
下一篇: Airtest常见的元素定位不到