网站设计 中高端,黄埔网站建设公司,大宗商品交易平台app,徐州seo顾问Evernote Export 线性结构#xff1a;python的列表操作列表是如何存储的#xff1a;顺序存储的#xff0c;是一块连续的内存#xff0c;内存是一堆格子#xff0c;列表是一串连续的编号32位机器上一个整数占4个字节数组和列表有2点不同#xff0c;1.数组的元素类型要求是…Evernote Export 线性结构 python的列表操作 列表是如何存储的顺序存储的是一块连续的内存内存是一堆格子列表是一串连续的编号 32位机器上一个整数占4个字节 数组和列表有2点不同1.数组的元素类型要求是相同的2.数组长度固定 列表1.python中列表的元素类型可以不同python列表中存储的不是数值而是地址2.python列表会根据输入的长度自动根据序列来递增列表 列表的append时间复杂度是O(1) 列表的插入和删除的时间复杂度是O(n) 栈的结构 栈是一个数据集合可以理解为只能在一端插入或进行删除操作的列表 栈的特点后进先出LIFO(last in first out) 栈的概念栈顶、栈底 栈的基本操作 进栈压栈push 出栈pop 取栈顶gettop 栈的应用 括号匹配问题给一个字符串其中包括小括号、中括号、大括号、求该字符串中的括号是否匹配 队列 队列是一个数据集合仅允许在列表的一端进行插入另一端进行删除 进行插入的一端称为队尾(rear)插入动作称为进队或入队 进行删除的一端称为队头(front),删除动作称为出队 队列的性质:先进先出(First-in, First-out) 迷宫的两种方式 栈-深度优先搜索 思路从一个节点开始任意找下一个能走的点当找不到能走的点退回上一个点寻找是否有其他方向的点 使用栈存储当前路径 队列-广度优先搜索 思路从一个节点开始寻找所有接下来能继续走的点继续寻找直到找到出口 使用队列存储当前正在考虑的节点 链表 链表是一种线性数据结构链表是由一系列节点组成的元素集合。 每个节点包含两个部分数据域item和指向下一个节点的指针next。通过节点之间的相互连接最终串联成一个链表。 创建链表 头插法 尾插法 复杂度分析 按元素值查找O(n) 按下标查找O(n) 在某一元素中插入O(1) 删除元素O(1) 链表在插入和删除的操作上明显快于顺序表 链表的内存快于灵活的分配:试利用链表重新实现栈和队列 链表这种链式存储的数据结构对树和图的结构有很大的启发性 哈希表(散列表) 哈希表通过哈希函数来计算数据存储位置的数据结构通常支持一下操作 insert(key,value):插入键值对(key,value) get(key):如果存在键为key的键值则返回其value否则返回空值 delete(key):删除key的键值对 直接寻址表 当关键字的全域U比较小时直接寻址是一种简单而有效的方法 直接寻址的技术缺点 当域U很大时需要消耗大量内存很不实际 如果域U很大而实际出现的key很少则大量空间被浪费 无法处理关键字不是数字的情况 哈希表是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成哈希函数h(k)将元素关键字k作为自变量返回元素的存储下标 假设有一个长度为7的哈希表哈希函数h(k) k%7元素集合{14,22,3,5}的存储方式如下图 哈希冲突 由于哈希的大小是有限的而要存储的值的总数量是无限的因此对于任何哈希函数都会出现两个不同的值但是映射到同个位置上的情况这种情况称为哈希冲突 解决哈希冲突方法 1.开放寻址法:如果哈希函数返回的位置已经有值则可以向后探查新的位置来存储这个值 线性查探如果位置被占用则探查i1i2... 二次查探如果位置i被占用则探查i1^2,i-1^2,i2^2,i-2^2 二度哈希有n个哈希函数当使用第一个哈希函数h1发生冲突时则尝试使用 h2h3... 2.拉链法哈希表每个位置都连接一个链表当冲突发生时冲突的元素将被加到该位置链表的最后 树与二叉树 树是一种结构比如目录结构 树是一种可以递归定义的数据结构 树是由n个节点组成的集合 如果n0那这是一颗空树 如果n0,那存在1个节点作为树的根节点其他节点可以分为m个集合每个集合本身又是一棵树 二叉搜索树 二叉搜索树是一颗二叉树且满足性质设x是二叉树的一个节点。如果y是x左子树的一个节点那么y.keyx.key 如果y是x右子树的一个节点那么y.keyx.key 二叉搜索树的操作查询、插入、删除 转载于:https://www.cnblogs.com/pandaboy1123/p/10098961.html
