首页 > 其他分享 >数据结构

数据结构

时间：2023-10-30 20:46:18浏览次数：31  
标签：__ 结点 return self 数据结构 stack def

数据结构

定义

数据结构就是设计数据以何种方式组织并存放在计算机中

eg：列表，字典，元组，堆，栈，队列

程序 = 数据结构（静态的数据） + 算法（动态的操作）

分类

  • 逻辑结构
    • 线性（一对一）
    • 非线性
      • 树结构（一对多）
      • 图结构（多对多）
      • 集合结构（除属于同一集合，别无其它关系）
  • 存储结构（物理结构）
    • 顺序存储结构（列表）
    • 链式存储结构

注：逻辑上为非线性结构，存储结构可以以线性结构存储，eg：堆（在逻辑上试属于非线性结构中的树，但可以以线性存储结构中的列表存储）

c语言数组与python中列表的区别

  1. c语言需设置存储空间大小
  2. 两者空间存储内容范围不同
    image

c语言数组只能存储同一类型元素，python可存储不同类型元素，由于python不同类型元素所占的字节不同，无法定义数组容量，因此，python数组存储元素的地址，占用一片连续的空间。

插入删除的时间复杂度为：O（n）

栈

特点

后进先出（last in first out：LIFO）

基本操作

  • 进栈：push
  • 出栈：pop
  • 取栈顶（不拿走）：gettop

image

栈的实现

  • 进栈：li.append
  • 出栈：li.pop
  • 取栈顶：li[len(li)-1]
# 栈
# 访问该类属性格式：self+.+属性
class Stack:        # 定义一个栈类            
    def __init__(self):     # 初始化栈
        self.stack = []
    def push(self,element):     # 进栈方法
        self.stack.append(element)
    def pop(self):              # 出栈方法
        if len(self.stack) > 0:     # 判断栈类是否有元素
            return self.stack.pop()
        else:
            return None
    def get_top(self):      # 获取栈顶元素方法
        if len(self.stack) > 0:     # 判断是否存在栈顶元素
            return self.stack[-1]
        else:
            return None
stack = Stack()
stack.push(9)
stack.push(6)
stack.push(6)
print(stack.pop())
print(stack.pop())
print(stack.get_top())

栈的应用

# 栈的括号匹配问题
class Stack:
    def __init__(self):
        self.stack = []
    def push(self,element):
        self.stack.append(element)
    def pop(self):
        if len(self.stack) > 0:
            return self.stack.pop()
        else:
            return None
    def get_top(self):
        if len(self.stack) > 0:
            return self.stack[-1]
        else:
            return None
    def is_empty(self):
        return len(self.stack) == 0
def brace_match(s):
    stack = Stack()
    catch = {"]":"[","}":"{",")":"("}
    for i in s:
        if i in "([{":
            stack.push(i)
        else:
            if stack.is_empty():
                stack.push(i)
            elif catch[i] == stack.get_top():
                stack.pop()
            else:
                stack.push(i)
    if stack.is_empty():
        print("匹配")
    else:
        print("不匹配")
str = str(input())
brace_match(str)

队列

特点

先进先出（first in first out：FIFO）
image

队列的实现——环形队列

原理

image

队首指针往下一格：(front+1)%MaxSize

队尾指针往下一格：（rear+1）%MaxSize

队满条件：（rear+1）%MaxSize == front

队空条件：font == rear

实现

# 堆的底层实现
class Queue:
    def __init__(self,size):     # 指定列表空间大小
        self.size = size
        self.queue = [0 for _ in range(size)]
        self.rear = 0       # rear表示队尾元素
        self.front = 0          # front表示队头元素
    def push(self,element):
        if not self.is_filled():
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = element
        else:
            raise Exception("队满了！")
    def pop(self):
        if not self.is_empty():
            self.front = (self.front + 1) % self.size
            return self.queue[self.front]
        else:
            raise Exception("队空了！")
    # 队空情况
    def is_empty(self):
        return self.rear == self.front
    # 队满情况
    def is_filled(self):
        return (self.rear + 1) % self.size == self.front
queue = Queue(7)
for i in range(6):
    queue.push(i)
print(queue.pop())

双端队列

同时具有队列和栈的特点：元素可以从两端进行删除和插入操作

image

python队列内置模块的实现

from collections import deque
# 单向队列
queue = deque()
for j in range(10):
    queue.append(j)  # 在队尾插入元素
print(queue.popleft())  # 在队首移除元素

# 多向队列
for i in range(20,30):
    queue.appendleft(i)  # 在队首插入元素
print(queue.pop())   # 在队尾移除元素

队列的应用

# 队列的应用（从文件中读取后n行）
from collections import deque
def tail(n):
    with open(r"C:\Users\hby\Desktop\1.txt","r") as f:
        queue = deque(f,n)          
        # f表示初始化一个队列，n表示队列所能存放的最大空间，若超过，dequeue会将前面的元素移除，最后保留后加入的n给元素
        return queue
for i in tail(5):
    print(i,end="")

栈和队列的应用

背景

迷宫问题：给一个二维列表，表示迷宫（0表示通道，1表示围墙）。给出算法，求一条走出迷宫的路径。

栈（深度优先搜索：一条路走到黑）

回溯法

  1. 原理：通过一定法则，进行搜索，并将路径保存在栈内存中，当元素走到头时，将该元素出栈，找到栈内还有可走路径的元素为止，停止出栈，最后到终点，则该栈中的元素则为到达终点的一条路径（并不一定是最短路径）

image

  1. 实现
# 迷宫
maze = [
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,0,0,1,1,0,0,1],
    [1,0,1,1,1,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,0,1,0,0,0,1,0,0,1],
    [1,0,1,1,1,0,1,1,0,1],
    [1,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]
direction = [                   # 用于存储给出参数为（x，y）的上下左右坐标位置
    lambda x,y:(x+1,y),
    lambda x,y:(x,y+1),
    lambda x,y:(x-1,y),
    lambda x,y:(x,y-1)
]
def path(x1,y1,x2,y2):          # x1,y1表示起始点;x2,y2表示终点
    stuck = []                  # 将路径点存放在列表（可进行增加和删除操作）stuck中
    stuck.append((x1,y1))
    while(len(stuck)>0):        # 当列表还存在元素时(表示可能还有通路)
        curNode = stuck[-1]     # 记录已走到最末的当前点位置
        if curNode == (x2,y2):      # 当走到终点时，输出终点
            for i in stuck:
                print(i)
            return True
        for i in direction:
            newNode = i(curNode[0],curNode[1])      # 找到末点的后面的点位置，得到一个坐标(x,y)
            if maze[newNode[0]][newNode[1]] == 0:       # 判断该点是否是通路
                stuck.append(newNode)                  # 是通路则存放列表中
                maze[newNode[0]][newNode[1]] = 2        # 改变该点的标志为2，说明该点已走过
                break                               # 以新的点进行重新while循环，进行深度优先搜索
        else:
            # 若当前点都没有下一个可走位置，则去除该点，找到前一个点，如此循环，直到找到有可走路径的点为止
            stuck.pop()
            maze[newNode[0]][newNode[1]] = 2        # 并设该点为已走过的点
    else:           # 若列表内元素为空，则表明无通路
        print("无通路！")
        return False
path(1,1,8,8)

队列（广度优先搜索）

  1. 原理：考虑一个位置所有可走的位置，分叉多条路，最后得到的路径一定是最短路径,需要一个额外的数组来存储当前位置的源头下标。

image

  1. 实现
# 迷宫
maze = [
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,0,0,1,1,0,0,1],
    [1,0,1,1,1,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,0,1,0,0,0,1,0,0,1],
    [1,0,1,1,1,0,1,1,0,1],
    [1,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]
# 方向
directions = [
    lambda x,y:(x+1,y),
    lambda x,y:(x,y+1),
    lambda x,y:(x-1,y),
    lambda x,y:(x,y-1)
]
# 寻回队列前的元素
def maze_back(path):
    Node = path[-1]                     # 从终点开始往回找
    realPath = []                       # 存放正确的路径
    while Node[2] != -1:                # 等于-1时即为起始点
        realPath.append(Node[0:2])
        Node = path[Node[2]]
    path.append(Node[0:2])
    realPath.reverse()                  # reverse能够使得列表本身发生颠倒
    for i in realPath:
        print(i)
# 广度优先搜索
from collections import deque           # python内置队列
def maze_path_queue(x1,y1,x2,y2):
    queue = deque()
    path = []           # 存放移除队列的元素
    queue.append((x1,y1,-1))            # -1表示该元素在path里源头的下标
    while len(queue) > 0:               # 判断找到终点元素前队列是否为空
        curNode = queue.pop()
        path.append(curNode)            # 保存元素，以便后面从终点找起点
        if curNode[0] == x2 and curNode[1] == y2:
            maze_back(path)
            return True
        for i in directions:
            newNode = i(curNode[0],curNode[1])
            if maze[newNode[0]][newNode[1]] == 0:
                queue.append((newNode[0],newNode[1],len(path)-1))
                maze[newNode[0]][newNode[1]] = 2
    else:
        print("无通路！")
        return False
maze_path_queue(1,1,8,8)

链表

定义

由一系列结点组成的元素集合

包含两部分：数据域（item）＆ 指针域（next）

数据域：存放数据

指针域：存放下一个结点的地址，指向下一个结点的位置

结点与结点之间不是顺序存放，结点内部之间则是顺序存放

链表的创建和遍历

  1. 链表的创建
    • 头插法：需要指向头节点的指针
    • 尾插法：需要指向头节点和尾节点的指针

image

# 链表的创建
class Node:
    def __init__(self,element):        # 初始化结点（包括数据域和指针域）
        self.element = element
        self.next = None
# 头插法
def head_insert(li):
    head = Node(li[0])
    for i in li[1:]:
        node = Node(i)        # 创建新的结点
        node.next = head
        head = node
    return head
head = head_insert([1,2,3,4,5,6])
print(head.element)
# 尾插法
def tail_insert(li):
    head = Node(li[0])
    tail = head
    for i in li[1:]:
        node = Node(i)
        tail.next = node
        tail = node
    return head,tail
head,tail = tail_insert([1,2,3,4,5,6])
print(head.next.element,tail.element)

链表的插入和删除

链表的插入和删除操作的效率要高于列表

  1. 链表的插入：

image

p.next = curNode.next
curNode.next = p
  1. 链表的删除：
    image
p=curNode.next
curNode.next = curNode.next.next
del p

双链表

双链表有两个指针（指向前一个结点的指针prior和指向后一个结点的指针next）

双链表的插入和删除

  1. 插入
    image
curNode.next.prior = p
p.next = curNode.next
curNode.next = p
p.prior = curNode
  1. 删除

image

p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p

复杂度分析

顺序表（数组/列表）与链表

  • 链表在插入和删除操作的时间效率要高于顺序表，顺序表在按下标查找元素的时间效率要高于链表
  • 链表的内存可以更灵活的分配（不需要连续的且既定大小的空间）

哈希表（散列表）

通过哈希函数计算数据存储位置的数据结构，属于线性存储结构，通常支持如下操作：

  • insert（key,value）：插入键值对
  • get（key）：如果存在键为key的键值对则返回其value，否则返回空值
  • delete（key）：删除键为key的键值对

构成

①直接寻址表 ②哈希函数

哈希冲突

当有两个值通过哈希函数计算到了同一个位置上

python中的字典和集合以哈希表的形式实现的

哈希冲突解决方法

开放寻址法

通过哈希函数找到原本该存放的位置，当位置已有元素，接着通过以下方式进行空位的查找与存放；查找元素方法与存放元素方法必须一样。

  • 线性探查法：如果位置i被占用，则探查i+1，i+2，……
  • 二次探查法：如果位置i被占用，则探查i+12,i-12,i+22,i-22，……
  • 二度哈希法：有n个哈希函数，当使用第一个哈希函数h1发生冲突时，则尝试使用h2，h3，……

拉链法

image

通过链表，将存放在同一位置的元素进行串联起来

直接寻址表（k的key为k）

  1. 原理

将可能的关键字范围建成一个长度为该范围的列表，关键字存放位置的下标即为该关键字的值（eg：2存放在下标为2的列表中）

image

  1. 评价

优点：能够快速进行插入和删除操作

缺点：当关键字的域很大时，浪费空间；当域很多，而关键字较集中时（实际出现的key很少），浪费空间；无法处理关键字不为数字的情况

改进直接寻指标（哈希）（k的key为h（k））

  1. 思想
  • 构建一个大小为m的列表
  • 设置哈希函数h（k）使得关键域U映射在范围为[0，m-1]的列表中

哈希表的内部实现

#  链表功能的定义
class LinkList:
    # 定义结点(包括数据域和指针域)
    class Node:
        def __init__(self,element=None):
            self.element = element
            self.next = None
    # 迭代器的定义(必须有iter和next)
    class LinkListIterator:
        def __init__(self,head):
            self.head = head
        def __iter__(self):
            return self
        def __next__(self):
            if self.head:
                cur_node = self.head
                self.head = cur_node.next
                return cur_node.element
            else:
                raise StopIteration
    # 链表的元素添加
    def __init__(self,iterable=None):
        self.head = None
        self.tail = None
        if iterable:
            self.extend(iterable)
    # 将元素进行拆分成单个元素
    def extend(self,iterable):
        for obj in iterable:
            self.append(obj)
    # 对单个元素进行添加
    def append(self,obj):
        s = LinkList.Node(obj)
        if self.head:
            self.tail.next = s
            self.tail = s
        else:
            self.head = s
            self.tail = s
    # 对单个元素进行寻找
    def find(self,obj):
        for i in self:
            if i == obj:
                return True
        else:
            return False
    # 设置链表迭代器
    def __iter__(self):
        return self.LinkListIterator(self.head)
    # 输出
    def __repr__(self):
        return "<<"+",".join(map(str,self))+">>"
# 哈希数组的定义
class HashTable:
    # 哈希数组
    def __init__(self,size=101):
        self.size = size
        self.T = [LinkList() for i in range(self.size)]
    # 哈希函数
    def h(self,k):
        return k % self.size
    # 元素的插入
    def insert(self,k):
        key = self.h(k)
        if self.T[key].find(k):
            print("Duplicated Insert.")
        else:
            self.T[key].append(k)
hash = HashTable()
hash.insert(0)
hash.insert(1)
hash.insert(3)
hash.insert(102)
print(hash.T)

哈希表的应用

  • 字典和集合都是通过哈希表来实现的

  • 安全性上（将数据映射到128位的哈希值）

    • md5算法

    • SHA2算法（无法反推）

树

定义

树是一种非线性（一对多）且可以递归定义的数据结构

概念

  • 根结点、叶子结点

    • 根结点：第一个结点（无父结点）
    • 叶子结点：无孩子的结点（无度的结点）

  • 树的深度（高度）

  • 树的度

    整个结点中有最大度结点的度（结点的度：一个结点的分叉数）

树的实例

# 模拟文件系统(linus)
# 定义结点
class Node:
    def __init__(self,name):
        self.name = name
        self.type = "dir"
        self.childen = []     # 存放该结点的孩子结点
        self.parent = None      # 存放该结点的父结点
    def __repr__(self):
        return self.name
# 树结构
class FileSystemTree:
    def __init__(self):				# 初始化根目录
        self.root = Node("/")
        self.now = self.root
    def mkdir(self,name):			# 文件的创建
        if name[-1] != "/":
            name += "/"
        newNode = Node(name)
        self.now.childen.append(newNode)
        newNode.parent = self.now
    def ls(self):					# 对当前文件的字文件进行查询
        return self.now.childen
    def cd(self,name):				# 跳转文件
        if name[-1] != "/":
            name += "/"
        for Name in self.now.childen:
            if Name.name == name:
                self.now = Name
                return
        raise ValueError("invalid dir")
file = FileSystemTree()
file.mkdir("bin")
file.mkdir("user")
file.cd("user")
file.mkdir("python")
print(file.ls())

二叉树

定义

  • 每个结点的度都大于大于等于2
  • 有左右结点孩子区分

存储形式

  • 若为完全二叉树可采用顺序存储方式（如排序算法中的堆排序）
  • 若不为完全二叉树可采用链式存储方式

结点的定义

class Node:
    def __init__(self,name):
        self.name = name
        self.lchild = None      # 左孩子
        self.rchild = None      # 右孩子
    def __repr__(self):         # 定义输出形式，默认输出地址
        return self.name
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
root = a
a.lchild = c
a.rchild = b
b.rchild = d
print(root.rchild.rchild)

二叉树的遍历

标签：__,结点,return,self,数据结构,stack,def
From： https://www.cnblogs.com/byyya/p/17798742.html

相关文章

  • 数据结构：栈与队列-详解循环队栈
    《详解循环队栈》目录：循环队列的定义及其特点循环队列的实现完整Demo运行截图小结参考文献一、循环队列的定义及其特点队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表......
  • 数据结构与算法 | 二分搜索（Binary Search）
    二分搜索（BinarySearch）文承上篇，搜索算法中除了深度优先搜索（DFS）和广度优先搜索（BFS），二分搜索（BinarySearch）也是最基础搜索算法之一。二分搜索也被称为折半搜索（Half-intervalSearch）也有说法为对数搜索算法（LogarithmicSearch），用于在已排序的数据集中查找特定元素。搜索过程从排序数......
  • 05数据结构(栈、队列、数组、链表)
    数据结构一、什么是数据结构计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。数据结构是为了更加方便的管理和使用数据，需要结合具体的业务场景来进行选择。一般情况下，精心选择的数据结构可以带来更高的运行或者存储效率。如何学习数据结构：每......
  • 数据结构之散列表与哈希函数初识
    一：概述一：为什么需要散列表*在我们的程序世界里，往往也需要在内存中存放这样一个“词典”，方便我们进行高效的查询和统计。*例如开发一个学生管理系统，需要有*通过输入学号快速查找对应学生的姓名的功能。*这里不必要每次都去查询数据库，而可以在内存中建立一个缓存表，这样做可以......
  • 数据结构与算法-cnblog
    数据结构与算法课程笔记树与二叉树树的深度与高度高度就可以理解为深度看层数：如果根结点第0，层数=深度=高度-1如果根结点第1，层数=深度=高度深度定义是从上往下的，高度定义是从下往上的......
  • Python数据结构——栈
    栈（Stack）是一种基本的数据结构，它遵循“后进先出”（Last-In-First-Out，LIFO）的原则，即最后放入栈的元素最先出栈。栈常用于管理函数调用、表达式求值、括号匹配等问题。本文将详细介绍Python中栈数据结构的使用，并提供示例代码来说明。什么是栈？栈是一种线性数据结构，它由一组元素组成，支持两......
  • 数据结构之树（二叉树）
    什么是二叉树（binarytree）？在树结构的基础上，要求其中每个节点最多有两个子节点（一个节点最多有2个边）。二叉树由根节点和若干个左子树和右子树构成，这些子树也都是二叉树。二叉树可以为空树，也可以只包含一个根节点。为什么树形结构常用二叉树呢？就是为了省空间。n叉树，n越大就需要更......
  • NOIP[区间数据结构类问题]
    平面最近点对经典的分治问题，把所有的点按照\(x\)排序，然后分治处理两个子区间，然后枚举离中心少于已知最小值的点，判断能否出现更小值。intn,temp[250000];structnode{ intx,y;}a[500500];boolcmp(nodel,noder){ if(l.x==r.x)returnl.y<r.y; returnl.x<r.x;}doub......
  • 【数据结构】- 并查集
    并查集简介并查集是可以维护元素集合的数据结构。并查集通过把一个集合作为一棵树的方式，维护一个森林（这暗含并查集可以维护连通块个数，如在kruskal中，通过并查集维护连通块个数就能快速判断循环退出条件），并使用树的根节点代表各集合。这样一棵树的节点就对应该集合中的元素......
  • C++---数据结构---队列（queue）
    queue容器queue基本概念概念：Queue是一种先进先出(FirstInFirstOut,FIFO)的数据结构，它有两个出口队列容器允许从一端新增元素，从另一端移除元素队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为队列中进数据称为—入队push队列中出数据称为—出队popque......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99