排名好的网站开发,网页制作网页设计,wordpress 颜色插件,网站开发工程数据结构
概述
为什么要讲数据结构#xff1f; 任何一个有志于从事IT领域的人员来说#xff0c;数据结构#xff08;Data Structure#xff09;是一门和计算机硬件与软件都密切相关的学科#xff0c;它的研究重点是在计算机的程序设计领域中探讨如何在计算机中组织和存储…数据结构
概述
为什么要讲数据结构 任何一个有志于从事IT领域的人员来说数据结构Data Structure是一门和计算机硬件与软件都密切相关的学科它的研究重点是在计算机的程序设计领域中探讨如何在计算机中组织和存储数据并进行高效率的运用涉及的内容包含数据的逻辑关系、数据的存储结构、排序算法Algorithm、查找或搜索等。
我们举一个形象的例子来理解数据结构的作用 战场程序运行所需的软件、硬件环境 敌人项目或模块的功能需求 指挥官编写程序的程序员 士兵和装备一行一行的代码 战术和策略数据结构 没有战术打仗事倍功半 有战术打仗事半功倍 总结简单来说数据结构就是一种程序设计优化的方法论研究数据的逻辑结构和物理结构以及它们之间相互关系并对这种结构定义相应的运算目的是加快程序的执行速度、减少内存占用的空间。 因此数据结构和算法是一名程序开发人员的必备基本功不是一朝一夕就能练成绝世高手的。冰冻三尺非一日之寒需要我们平时不断的主动去学习积累。
数据结构的应用 计算机的主要工作就是把数据Data经过某种运算处理转换为实用的信息Information 。具体介绍一些数据结构的应用
1树形结构 树形结构是一种相当重要的非线性数据结构广泛运用在人类社会的族谱、机关的组织结构、计算机的操作系统结构、平面绘图应用、游戏设计等方面。 上图四叉树示意图 上图地形与四叉树的对应关系
2最短路径 最短路径是指在众多不同的路径中距离最短或者所花费成本最少的路径。寻找最短路径最常见的应用是公共交通运输系统的规划或网络的架设如都市公交系统、铁路运输系统、通信网络系统等。 现在很多汽车和手机都安装了GPS导航用于定位和路况查询。其中路程的计算就是以最短路径的理论作为程序设计的依据为旅行者提供不同的路径作为选择方案。
3搜索理论 所谓“搜索引擎”是一种自动从因特网的众多网站中查找信息再经过一定的整理后提供给用户进行查询的系统例如百度、谷歌、搜狗等。 注意Search这个单词在网络上习惯上翻译为“搜索”如搜索引擎。而在数据结构的算法描述中习惯翻译成“查找”。在计算机科学中“搜索”和“查找”大部分情况下可以互相转换。 Pascal之父Nicklaus Wirth“AlgorithmsData StructuresPrograms” 上面我们提到的数据结构和算法是程序设计实践中最基本的内涵。程序能否快速而高效地完成预定的任务取决于是否选对了数据结构而程序是否能清楚而正确地把问题解决则取决于算法。算法是计算机处理信息的本质因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。 所以大家认为“Algorithms Data Structures Programs”出自Pascal之父Nicklaus Wirth 数据结构只是静态的描述了数据元素之间的关系。 高效的程序需要在数据结构的基础上设计和选择算法。
总结算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体。
数据结构的研究对象
数据间的逻辑结构
集合 数据元素之间只有“同属于一个集合”的关系
线性关系 数据元素之间存在一个对一个的关系对应Java中的线性表顺序表、链表、栈、队列
树形结构 数据元素之间存在一个对多个的关系对应Java中的树。比如二叉树
网状结构(或图状结构) 数据元素之间存在多个对多个的关系对应Java中的图
数据的存储结构(或物理结构) 参考书籍数据结构与算法分析Java语言描述第2版[美] 卡拉罗Carrano,F.M. 著 金名等 译 大话数据结构 作 者程杰 著
真实结构 在内存中真实存在的, 用来存放多个数据的内存结构。
线性表之顺序表或静态数据结构数组(Array)、ArrayList 特点① 使用连续分配的内存空间②一次申请一大段连续的空间, 需要事先声明最大可能要占用的固定内存空间 优点设计简单读取与修改表中任意一个元素的时间都是固定的 缺点① 容易造成内存的浪费② 删除或插入数据需要移动大量的数据 存储思路 所有数据存储在这个连续的空间中数组中的每一个元素都是一个具体的数据所有数据都紧密排布不能有间隔 操作 读内存 查:每个元素都有一个数值下标, 可以通过下标瞬间定位到某个元素 写内存 增 从头部插入 在中间插入 从尾部插入 注意插入元素引起部分元素后移代价非常高 删 注意去掉元素引起部分元素前移代价非常高 改 注意只需要修改对应位置的元素的内容不需要申请或者删除空间 适用范围 查询操作远多于插入/删除操作的场景 简单抽象数据结构的基石
线性表之链表或动态数据结构Linked List 特点① 使用不连续的内存空间② 不需要提前声明好指定大小的内存空间。一次申请一小块内存按需申请 优点① 充分节省内存空间② 数据的插入和删除方便不需要移动大量数据 缺点① 设计此数据结构较为麻烦② 查找数据必须按顺序找到该数据为止麻烦 存储思路 每一个小数据单独存在一小块内存中这个单元被称作结点(Node) 每一小块内存知道下一小块的地址 比如地下党只知道自己的下线单线联系 多个不连续的小内存空间组成, 通过内存地址引用形成一个链的结构 表头程序员获得表头就可以找到链表中所有的元素 表尾有的链表有有的没有
实现结构链表 单向链表 环形链表 双向链表
读写操作 读 查:节点是没有下标的, 只能从链表的表头开始查找某个节点 写 增 申请一小块内存--结点 插入到链中 从头部插入 从尾部插入 从中间插入 删 从链中剥离结点 释放这个结点的内存 改 改变这个结点中所存储的值 适用范围 插入/删除操作远多于查询操作的场景 复杂抽象数据结构的基石
抽象结构(ADT) 在内存中并不存在此结构, 由程序员利用数组/链表封装成的结构
栈(Stack) 栈Stack是限制仅在表的一端进行插入和删除运算的线性表。 栈的修改原则 栈的修改是按后进先出的原则进行。每次删除退栈的总是当前栈中最新的元素即最后插入进栈的元素而最先插入的是被放在栈的底部要到最后才能删除。
超市货架上的商品一叠书 名词
栈顶 插入、删除的这一端为栈顶
栈底 相对于栈顶的另一端
空栈 当表中没有元素时称为空栈
特点 继承于java.util.Vector后进先出
实现结构
顺序表实现栈 用数组实现 优点算法简单 缺点数组大小只能事先规划声明好太大了浪费空间太小了不够用
链表实现栈 优点随时可动态改变链表长度有效利用内存空间 缺点算法设计复杂
基本运算 进栈(压栈、入栈): push(ele) 出栈: pop() 查看栈顶元素: peek() 清栈: clear() 大小: size() 判断是否是空:empty() 查找元素出现位置search(Object obj)
使用场景
二叉树和森林的遍历
CPU的中断处理
图形的深度优先查找法(DFS)
递归调用 斐波那契数列 汉诺塔问题
子程序的调用
队列(Queue) 队列Queue是只允许在一端进行插入而在另一端进行删除的运算受限的线性表。
队列的修改原则 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾即不允许加塞每次离开的成员总是队列头上的不允许中途离队即当前最老的成员离队。 名词 队头(front)允许删除的一端称为队头Front 队尾(rear)允许添加的一端称为队尾Rear 空队列当队列中没有元素时称为空队列
特点 先进先出典型实现PriorityQueue
实现结构 顺序表实现队列 用数组实现 优点算法简单 缺点数组大小固定无法根据队列实际需要动态申请 链表实现队列 优点随时可动态改变链表长度有效利用内存空间 缺点算法设计复杂
操作 加入元素到队列尾部: add(Object obj)/offer(Object obj) 获取队列头部元素不删除该元素:element()/peek() 获取队列头部元素并删除该元素remove()/poll() 清理队列: clear() 得到队列的大小: size() 判断队列是否是空的: isEmpty()
使用场景 图形的广度优先查找法BFS) 可用于计算机各种事件处理的模拟 如: 事件队列, 消息队列 CPU的作业调度
变形的队列 环形队列 双向队列 优先队列 树(Tree) 树 对大量的输入数据链表的线性访问时间太慢不宜使用。这里是另外一种重要的数据结构----树其大部分时间可以保证操作的运行平均时间复杂度为O(logN)。 例如公司组织架构家族族谱Linux系统的文件和目录结构
计算机世界的树
专有名词
结点树中的数据元素都称之为结点
根节点最上面的结点称之为根一颗树只有一个根且由根发展而来从另外一个角度来说每个结点都可以认为是其子树的根
父节点结点的上层结点如图中结点K的父节点是E、结点L的父节点是G
子节点节点的下层结点如图中节点E的子节点是K节点、节点G的子节点是L节点
兄弟节点具有相同父节点的结点称为兄弟节点图中F、G、H互为兄弟节点
结点的度数每个结点所拥有的子树的个数称之为结点的度如结点B的度为3
树叶度数为0的结点也叫作终端结点图中D、K、F、L、H、I、J都是树叶
非终端节点或分支节点树叶以外的节点或度数不为0的节点。图中根、A、B、C、E、G都是
树的深度或高度树中结点的最大层次数图中树的深度为4
结点的层数从根节点到树中某结点所经路径上的分支树称为该结点的层数根节点的层数规定为1其余结点的层数等于其父亲结点的层数1
同代在同一棵树中具有相同层数的节点
二叉树(Binary Tree)
二叉树
在普通树的基础上让一棵树中每个节点最多只能包含两个子节点且严格区分左子节点和右子节点位置不能换。 分类 功能 增删改查 搜索 广度优先搜索 深度优先搜索 前序遍历树根-左子树-右子树 中序遍历左子树-树根-右子树 后序遍历左子树-右子树-树根
特例
排序二叉树
满足一些条件的二叉树才被称为排序二叉树。比如若它的左子树不为空左子树上的所有节点值均小于根节点值若右子树不为空右子树上的所有节点值均大于根节点值。
特点可以非常方便地对树中的所有节点进行排序和检索。
红黑树
红黑树顾名思义就是结点是红色或者黑色的平衡二叉树它通过颜色的约束来维持着二叉树的平衡。下图为一颗典型的二叉树 对于一棵有效的红黑树而言我们必须增加如下规则
1、每个结点都只能是红色或者黑色
2、根节点是黑色
3、每片叶子都是黑色的
4、如果一个结点是红色的则它的两个子节点都是黑色的也就是说在一条路径上不能出现相邻的两个红色结点
5、从任意一个结点到其每个叶子的所有路径都包含着相同数目的黑色结点 这些约束强制了红黑树的关键性质从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果就是这棵树大致上是平衡的因为插入、删除和查找某个值得最坏情况时间都要求与树的高度成比例这个高度理论上限允许红黑树只在最坏情况下都是高效的。 再具体就不说了可以参看http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html对红黑树的讲解写得非常好。 TreeMap和TreeSet就是红黑树的典型实现。
使用场景
哈夫曼树 一种带权路径最短的二叉树在信息检索中很常用
哈夫曼编码 假设需要对一个字符串如“abcdabcaba”进行编码将它转换为唯一的二进制码同时要求转换出来的二进制码的长度最小。我们采用哈夫曼树来解决报文编码问题。 1. 哈夫曼编码在数据通信中需要将传送的文字转换成二进制的字符串现要求为这些字母设计编码。在实际应用中各个字符的出现频度或使用次数是不相同的如A、B、C的使用频率远远高于X、Y、Z自然会想到设计编码时让使用频率高的用短码使用频率低的用长码以优化整个报文编码。为了获得传送报文的最短长度可将每个字符的出现频率作为字符结点的权值赋予该结点上显然字使用频率越小权值越小权值越小叶子就越靠下于是频率小编码长频率高编码短这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。利用哈夫曼树来设计二进制的前缀编码既满足前缀编码的条件又保证报文编码总长最短。 2. 哈夫曼译码在通信中若将字符用哈夫曼编码形式发送出去对方接收到编码后将编码还原成字符的过程称为哈夫曼译码。
B树
图 定义由“顶点”和“边”所组成的集合 分类 无向图 有向图 图的表示法 邻接矩阵法 邻接表法 邻接复合链表法 索引表格法 图的遍历 深度优先遍历 广度优先遍历 应用场景最短路径搜索、拓扑排序
其它 散列表(Hash),堆(Heap) 数组 数组是相同数据类型的数据按顺序组成的一种引用数据类型。 声明数组仅仅给出了元素的数据类型和数组名字要使用数组就必须为它分配内存空间即实例化数组。当实例化一个数组时就申请了一段连续的内存空间存储数组中的元素。 数组中的数据是通过数组名和数组下标来操作数据的下标从0开始下标的专业叫法索引
用于存储同一类型数据的一个容器。
数组的常见概念 数组本身是引用数据类型而数组中的元素可以是任何数据类型包括 基本数据类型和引用。
创建数组对象会在内存中开辟一整块连续的空间 而数组名中引用的是这块连续空间的首地址 。数组长度一旦确定 就不能修改 。我们可以直接通过下标 (或索引 )的方式调用指定位置元素 速度很快 。数组的分类 按照维度一维数组、二维数组、三维数组、… 按照元素的数据类型分基本引用数据类型元素的组 (即对 象数组 )
好处 可以对该容器中的数据进行编号从0开始。数组用于封装数据就是一个具体的实体。 穷举法只能用于初始化数组即必须和声明数组代码放在一条语句中完成。
核心思想就是对角标的操作 如何在java中表现一个数组呢两种表现形式。 元素类型[] 变量名 new 元素类型[元素的个数] 元素类型[] 变量名 {元素1元素2...} 元素类型[] 变量名 new 元素类型[]{元素1元素2...}
格式数组名[索引] 数组的长度属性 每个数组都具有长度而且是固定的Java中赋予了数组的一个属性可以获取到数组的长度语句为 数组名.length 属性length的执行结果是数组的长度int类型结果。由次可以推断出数组的最大索引值为 数组名.length-1 。
public static void main(String[] args) {int[] arr new int[]{1,2,3,4,5};//打印数组的属性输出结果是5System.out.println(arr.length);}
数组的访问 索引 每一个存储到数组的元素都会自动的拥有一个编号从0开始这个自动编号称为数组索引(index)可以通过数组的索引访问到数组中的元素。
索引访问数组中的元素
数组名[索引]数值为数组中的元素赋值
变量数组名[索引]获取出数组中的元素
public static void main(String[] args) {//定义存储int类型数组赋值元素12345int[] arr {1,2,3,4,5};//为0索引元素赋值为6arr[0] 6;//获取数组0索引上的元素int i arr[0];System.out.println(i);//直接输出数组0索引元素System.out.println(arr[0]);
}
一维数组
一维数组的声明方式
type var [] 或 type[] var
例如
int inta[] ;
int int[] a1;
double b[];
String [] c;// 引用类型变量数组
Java 语言中声明数组时不能指定其长度(数组中元素的)例如 int inta[5 ]; // 非法
动态初始化 数组声明且为元素分配空间与赋值的操作 分开进行
int[] arr new int[3];
arr[0] 3;
arr[1] 9;
arr[2] 8;
静态初始化 在定义数组的同时就为元素分配空间并赋值。 int arr[] new int[]{ 3, 9, 8}; 或 int[] arr {3,9,8};
一维数组的使用
数组元素的引用 定义并用运算符new为之分配空间后才可以引用数组中的每个元素数组元素的引用方式数组名[数组元素下标]
数组元素下标可以是整型常量或整型表达式。如a[3] , b[i] , c[6*i];数组元素下标从0开始长度为n的数组合法下标取值范围: 0 —n-1如inta[]new int[3]; 可引用的数组元素为a[0]、a[1]、a[2]
每个数组都有一个属性length指明它的长度例如a.length指明数组a的长度(元素个数)
数组一旦初始化其长度是不可变的
数组元素的默认初始化值 数组是引用类型它的元素相当于类的成员变量因此数组一经分配空间其中的每个元素也被按照成员变量同样的方式被隐式初始化。例如
Public class Test{Public static void main(String argv []){Int a[]new int[5];System.out.println(a[3]);//a[3]的默认值为0}
}
对于基本数据类型而言默认初始化值各有不同
对于引用数据类型而言默认初始化值为null(注意与0不同) 数组元素类型 元素默认初始值 byte 0 short 0 int 0 long 0L float 0.0F double 0.0 char 0 或写为:’\u0000’(表现为空) boolean false 引用类型 null
多维数组的使用
Java 语言里提供了支持多维数组的语法。如果说可以把一维数组当成几何中的线性图形那么二维数组就相当于是一个表格像右图Excel中的表格一样。对于二维数组的理解我们可以看成是一维数组array1又作为另一个一维数组array2的元素而存在。其实从数组底层的运行机制来看其实没有多维数组。 二维数组[ ][ ]数组中的数组 格式1动态初始化int[ ][ ] arr new int[3][2]; 定义了名称为arr的二维数组 二维数组中有3个一维数组 每一个一维数组中有2个元素 一维数组的名称分别为arr[0], arr[1], arr[2] 给第一个一维数组1脚标位赋值为78写法是arr[0][1] 78; 格式2动态初始化int[ ][ ] arr new int[3][ ]; 二维数组中有3个一维数组。 每个一维数组都是默认初始化值null (注意区别于格式1 可以对这个三个一维数组分别进行初始化 arr[0] new int[3]; arr[1] new int[1]; arr[2] new int[2]; 注 int[ ][ ]arr new int[ ][3]; //非法 格式3静态初始化int[][]arrnew int[][]{{3,8,2},{2,7},{9,0,1,6}}; 定义一个名称为arr的二维数组二维数组中有三个一维数组 每一个一维数组中具体元素也都已初始化 第一个一维数组arr[0] {3,8,2}; 第二个一维数组arr[1] {2,7}; 第三个一维数组arr[2] {9,0,1,6}; 第三个一维数组的长度表示方式arr[2].length; 注意特殊写法情况int[] x,y[]; x是一维数组y是二维数组。 Java中多维数组不必都是规则矩阵形式 数组原理内存图
内存概述 内存是计算机中的重要原件临时存储区域作用是运行程序。我们编写的程序是存放在硬盘中的在硬盘中的程序是不会运行的必须放进内存中才能运行运行完毕后会清空内存。Java虚拟机要运行程序必须要对内存进行空间的分配和管理
Java虚拟机的内存划分 为了提高运算效率就对空间进行了不同区域的划分因为每一片区域都有特定的处理数据方式和内存管理方式。垃圾回收机制。 区域名称 作用 寄存器 给CPU使用和我们开发无关。 本地方法栈 JVM在使用操作系统功能的时候使用和我们开发无关。 方法区 存储可以运行的class文件。 堆内存 存储对象或者数组new来创建的都存储在堆内存。用于存储数组和对象也就是实体。啥是实体啊就是用于封装多个数据的。 1每一个实体都有内存首地址值。 2堆内存中的变量都有默认初始化值。因为数据类型不同值也不一样。 方法栈 方法运行时使用的内存比如main方法运行进入方法栈中执行。存储的都是局部变量 ( 方法中定义的变量方法上的参数语句中的变量 )只要数据运算完成所在的区域结束该数据就会被释放
数组在内存中的存储
一个数组内存图
public static void main(String[] args) {int[] arr new int[3];System.out.println(arr);//[I5f150435
} 以上方法执行输出的结果是[I5f150435这个是什么呢是数组在内存中的地址。new出来的内容都是在堆内存中存储的而方法中的变量arr保存的是数组的地址arr[0]就会输出arr保存的内存地址中数组中0索引上的元素 两个数组内存图
public static void main(String[] args) {int[] arr new int[3];int[] arr2 new int[2];System.out.println(arr);System.out.println(arr2);
} 两个变量指向一个数组
public static void main(String[] args) {// 定义数组存储3个元素int[] arr new int[3];//数组索引进行赋值arr[0] 5;arr[1] 6;arr[2] 7;//输出3个索引上的元素值System.out.println(arr[0]);System.out.println(arr[1]);System.out.println(arr[2]);//定义数组变量arr2将arr的地址赋值给arr2int[] arr2 arr;arr2[1] 9;System.out.println(arr[1]);
} 数组中常见的两个异常
ArrayIndexOutOfBoundsException://当访问到数组中不存在的角标时就会发生该异常。
NullPointerException//当引用型变量没有任何实体指向时还在用其操作实体。就会发生该异常
//二分查找法。必须有前提数组中的元素要有序。 public static int halfSeach_2(int[] arr,int key){int min, max, mid;min 0;max arr.length-1;mid (maxmin)1; //(maxmin)/2;while(arr[mid]!key){if( key arr[mid] ){min mid 1;} else if ( key arr[mid] ){max mid - 1;}if( max min ){return -1;}mid (maxmin)1;}return mid;}
Arrays工具类的使用 1 Boolean equals(int[] a,int[] b) 判断两个数组是否相等。 2 String toString(int[] a) 输出数组信息。 3 Void fill(int[] a,int val) 将指定值填充到数组之中。 4 Void sort(int[] a) 对数组进行排序。 5 Int binarySearch(int[] a,int key) 对排序后的数组进行二分法检索指定的值。 数组中涉及的常见算法 1. 数组元素的赋值(杨辉三角、回形数等) 2. 求数值型数组中元素的最大值、最小值、平均数、总和等 3. 数组的复制、反转、查找(线性查找、二分法查找) 4. 数组元素的排序算法
插入排序 冒泡排序 快速排序
