【数据结构】

一:算法分析

1:时间复杂度计算

T(n)=函数执行的最大次数。执行次数与输入规模有关。

原则:

1)去除常系数

2)同等数量级并且并列的则用 + 连接,并列的但数量级不同的取大者

3)嵌套的相乘

所以,我们先用  T(n)=K*t(f1(n))+M*t(f2(n))... 计算出算法执行的最大次数,然后运行化简法则化简:去常系数,和式取大,嵌套相乘,即可得到复杂度

2:空间代价

如果需要用到容器存放处理过程中的数据,那么我们可以根据输入规模n计算出空间开销代价与n的关系式。

二:树

1:遍历二叉树

前序:根左右

中序:左根右

后序:左右根

2:链表建立二叉树

每个结点一个node,有左右指针指向儿子

3:数组实现完全二叉树

n为结点总数,r为当前结点下标,则:

父节点为:floor[(r-1)/2]

左兄弟:r-1(r为偶数)

右兄弟:r+1(r为奇数)

左儿子:2r+1

右儿子:2r+2

4:遍历二叉树

5:由中序+前/后序遍历重建二叉树

6:BST的建立与使用

7:最大/最小堆的建立

8:哈夫曼编码树的建立及使用

9:计算树的高度

10:统计叶子数目

三:排序

1:

四:检索

五:索引

六:图

时间: 03-01

【数据结构】的相关文章

【数据结构】之散列链表(Java语言描述)

散列链表,在JDK中的API实现是 HashMap 类. 为什么HashMap被称为"散列链表"?这与HashMap的内部存储结构有关.下面将根据源码进行分析. 首先要说的是,HashMap中维护着的是一个数组: transient Node<K,V>[] table; ,数组中的每个元素都是一个 Node 对象.这里的Node是HashMap的一个内部类,代码如下: static class Node<K,V> implements Map.Entry<

旧题新做:从idy的视角看数据结构

“今天你不写总结……!!!” 额…… 还是讲我的吧.这些考试都是idy出的题. 20170121:DFS序. ST表.线段树练习 这是第一次考数据结构. Problem 1. setsum 1 second 给你一个长度为N 的整数序列,支持两种操作: • modity l r val 将区间[l,r] 中的所有数修改为val • query l r 询问区间[l,r] 所有数的和 分析:最简单的线段树,区间更改区间求和.但注意是更改,不是添改,sum与flag需同时覆盖. Problem 2.

数据结构Set和Map

一.数据结构 Set 集合的基本概念:集合是由一组无序且唯一(即不能重复)的项组成的.这个数据结构使用了与有限集合相同的数学概念,应用在计算机的数据结构中.  特点:key 和 value 相同,没有重复的 value.ES6 提供了数据结构 Set.它类似于数组,但是成员的值都是唯一的,没有重复的值. 1. 如何创建一个 Set const s = new Set([1, 2, 3]); 2.属性 console.log(s.size); // 3 3.Set 类的方法 --set.add(v

数据结构基本概念

什么是数据结构 "数据结构是数据对象,以及存在于该对象的实例和组成实例的数据元素之间的各种联系.这些联系可以通过定义相关的函数来给出"--Sartaj Sahni,<数据结构.算法与应用> "数据结构是ADT(抽象数据类型Abstract Data Type)的物理实现."--Clifford A.Shaffer,<数据结构与算法分析> "数据结构(data structture)是计算机中存储.组织数据的方式.通常情况下,经i想你

分布式缓存技术redis学习系列(二)——详细讲解redis数据结构(内存模型)以及常用命令

Redis数据类型 与Memcached仅支持简单的key-value结构的数据记录不同,Redis支持的数据类型要丰富得多,常用的数据类型主要有五种:String.List.Hash.Set和Sorted Set. Redis数据类型内存结构分析 Redis内部使用一个redisObject对象来表示所有的key和value.redisObject主要的信息包括数据类型(type).编码方式(encoding).数据指针(ptr).虚拟内存(vm)等.type代表一个value对象具体是何种数

【Python&amp;数据结构】 抽象数据类型 Python类机制和异常

这篇是<数据结构与算法Python语言描述>的笔记,但是大头在Python类机制和面向对象编程的说明上面.我也不知道该放什么分类了..总之之前也没怎么认真接触过基于类而不是独立函数的Python编程,借着本次机会仔细学习一下. 抽象数据类型 最开始的计算机语言,关注的都是如何更加有效率地计算,可以说其目的是计算层面的抽象.然而随着这个行业的不断发展,计算机不仅仅用于计算,开发也不仅只关注计算过程了,数据层面的抽象也变得同样重要.虽然计算机语言一开始就有对数据的抽象,但是那些都只是对一些最基本的

深入浅出分析MySQL索引设计背后的数据结构

在我们公司的DB规范中,明确规定: 1.建表语句必须明确指定主键 2.无特殊情况,主键必须单调递增 对于这项规定,很多研发小伙伴不理解.本文就来深入简出地分析MySQL索引设计背后的数据结构和算法,从而可以帮你释疑如下问题: 1.为什么innodb表需要主键? 2.为什么建议innodb表主键是单调递增? 3.为什么不建议innodb表主键设置过长? B-tree(多路搜索树,并不是二叉的)是一种常见的数据结构.使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度.B通常

数据类型和常用数据结构

1.数据类型 几乎是所有的程序设计语言都会讲到数据类型的概念.简单的说,数据类型就是一个值的集合及在这些值上定义的一系列操作的总称.例如:对于C语言的整数类型,其有一定的取值范围,对于整数类型还定义了加法.减法.乘法.除法和取模运算等操作. 按照数据类型的值是否可以分解,数据类型可以分为基本数据类型和聚合数据类型. *基本数据类型:其值不能进一步分解,一般是程序设计语言自身定义的一些数据类型,例如C语言中.字符型.浮点型等. *聚合数据类型:其值可以进一步分解为若干分量,一般是用户自定义的数据类

第3章 文件I/O(3)_内核数据结构、原子操作

3. 文件I/O的内核数据结构 (1) 内核数据结构表 数据结构 主要成员 文件描述符表 ①文件描述符标志 ②文件表项指针 文件表项 ①文件状态标志(读.写.追加.同步和非阻塞等状态标志) ②当前文件偏移量 ③i节点表项指针 ④引用计数器 i节点 ①文件类型和对该文件的操作函数指针 ②当前文件长度 ③文件所有者 ④文件所在设备.文件访问权限 ⑤指向文件数据在磁盘块上所在位置的指针等. (2)3张表的关系 4. 文件的原子操作 (1)文件追加 ①打开文件时使用O_APPEND标志,进程对文件偏移量

数据结构与算法C++描述学习笔记1、辗转相除——欧几里得算法

前面学了一个星期的C++,以前阅读C++代码有些困难,现在好一些了.做了一些NOI的题目,这也是一个长期的目标中的一环.做到动态规划的相关题目时发现很多问题思考不通透,所以开始系统学习.学习的第一本是<数据结构与算法C++描述>第三版,边学边做一些笔记.所以这些笔记中的代码有很多将会非常简单,甚至可能只有一个记录或者结论. 辗转相除法用来求两个整数的最大公约数,即能同时整除两个数的最大整数.程序如下: int gdc(int m,int n){ int rem; while(n!=0){ //