学生做爰网站,网站建行接口,主流电商网站开发框架,珠海网站建设招聘数据结构与算法是计算机科学中的核心概念#xff0c;也与现实生活如算法岗息息相关。鉴于全网数据结构文章良莠不齐且集成度不高#xff0c;故开设本专栏#xff0c;为初学者提供指引。 目录 基本概念数据结构为何面世算法基本数据类型抽象数据类型使用抽象数据类型的好处 数… 数据结构与算法是计算机科学中的核心概念也与现实生活如算法岗息息相关。鉴于全网数据结构文章良莠不齐且集成度不高故开设本专栏为初学者提供指引。 目录 基本概念数据结构为何面世算法基本数据类型抽象数据类型使用抽象数据类型的好处 数据结构常见的数据结构常用算法 基本概念
数据结构data structure是一种具有一定逻辑关系在计算机中应用某种存储结构并且封装了相应操作的数据元素集合。它包含三方面的内容逻辑关系、存储关系及操作。
不同种类的数据结构适合于不同种类的应用而部分甚至专门用于特定的作业任务。例如计算机网络依赖于路由表运作B 树高度适用于数据库的封装。
数据结构为何面世
随着应用程序变得越来越复杂和数据越来越丰富几百万、几十亿甚至几百亿的数据就会出现而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢数据结构就是用来解决这些问题的。
算法
算法是在一类特定的数据模型上定义所有运算并以解决一类特定问题为目标的一个有限的运算序列它与数据结构是息息相关的。
算法实现的三要素数据算法需要处理的数据是算法的输入也是算法的输出。数据包括各种数据类型如整数、浮点数、字符串、数组、链表、树等以及数据结构如栈、队列、堆、图等。运算算法的核心是运算包括各种基本运算如加、减、乘、除、取模等、比较运算如大于、小于、等于等、逻辑运算如与、或、非等等。此外算法还可以包括一些高级运算如快速幂、快速排序、动态规划等以及各种库函数的调用。控制算法的执行流程需要通过控制来实现。控制包括顺序结构、选择结构、循环结构和函数调用等。顺序结构表示按照代码的书写顺序依次执行各个语句选择结构包括if语句和switch语句用于根据条件选择不同的分支循环结构包括for循环、while循环和do-while循环用于重复执行某个代码块函数调用用于将代码分解成多个可重用的模块提高代码的可读性和可维护性。算法的描述载体自然语言、数据流图、程序语言或者伪代码
算法的五大特征
输入具有零个或多个输入这些输入取自特定的数据对象集合
输出至少具有一个或多个输出这些输出同输入之间存在某种特定的关系
确定性双重含义组成算法的每条指令是清晰的、无歧义的无二义性对应相同的输入仅有唯一的一条算法执行路径
有限性序列项数有限且每一项运算时间有限
可行性∀合法输入 ∃正确输出
注意程序可以不满足有限性即程序可以无限循环执行而算法必须是有限的
基本数据类型
数据类型是指高级程序设计语言中用以刻划程序中操作对象的特性。类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围以及在这些值上允许进行的操作。
抽象数据类型
抽象数据类型是基本数据类型概念的引伸和发展指操作对象的一个数据模型以及定义在该模型上的一组操作。 也就是说对于抽象数据类型的描述除了必须描述它的数据结构外还必须描述定义在它上面的运算(过程或函数)。
抽象数据类型的定义取决于它的一组逻辑特性而与其在计算机内部如何表示和实现无关。
抽象数据类型的内容需要约定抽象数据类型的名字 、约定在该类型上定义的一组运算的各个运算的名字 、明确各个运算分别有多少个参数、这些参数的含义和顺序以及运算的功能
抽象数据类型的目标
把数据类型的表示和数据类型上运算的实现与其在程序中的应用分开相互独立 顶层和底层都与抽象数据类型的定义打交道算法底层的设计就是数据结构的设计和函数的设计
使用抽象数据类型的好处
顶层设计和底层实现分离、算法设计和数据结构设计分离 、数据模型和运算的内在统一于抽象数据类型之中、局部化、模块化、编出来的程序结构清晰层次分明便于程序正确性的证明和复杂性的分析
数据结构
数据结构的结构指的是数据之间的逻辑关系以及数据在计算机中的存储方式。数据的逻辑结构是从具体问题抽象出来的数学模型反映成分数据之间的逻辑关系它与数据的存储无关。数据的物理结构是在计算机中的存储和实现方法包括数据结构中元素的表示及元素间关系的表示。
常见的数据结构
栈Stack 栈是一种特殊的线性表它只能在一个表的一个固定端进行数据结点的插入和删除操作。
队列Queue 队列和栈类似也是一种特殊的线性表。和栈不同的是队列只允许在表的一端进行插入操作而在另一端进行删除操作。
数组Array 数组是一种聚合数据类型它是将具有相同类型的若干变量有序地组织在一起的集合。
链表Linked List 链表是一种数据元素按照链式存储结构进行存储的数据结构这种存储结构具有在物理上存在非连续的特点。
树Tree 树是典型的非线性结构它是包括 2 个结点的有穷集合 K。
图Graph 图是另一种非线性数据结构。在图结构中数据结点一般称为顶点而边是顶点的有序偶对。
堆Heap 堆是一种特殊的树形数据结构一般讨论的堆都是二叉堆。
散列表Hash table 散列表源自于散列函数(Hash function)其思想是如果在结构中存在关键字和T相等的记录那么必定在F(T)的存储位置可以找到该记录这样就可以不用进行比较操作而直接取得所查记录。
常用算法
数据结构研究的内容就是如何按一定的逻辑结构把数据组织起来并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据提高数据运算效率。数据的运算是定义在数据的逻辑结构上但运算的具体实现要在存储结构上进行。一般有以下几种常用运算
检索 检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值找具有该字段值的节点。插入 往数据结构中增加新的节点。删除 把指定的结点从数据结构中去掉。更新 改变指定节点的一个或多个字段的值。排序 把节点按某种指定的顺序重新排列。例如递增或递减。
基础性概念介绍完毕不同数据结构的实现会在后面的文章中阐发。
