数据结构与算法知识

概要：

什么是数据结构?数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或者多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效果。数据结构往往同高效的检索算法和索引技术有关。数据存储的结构和基本算法，最基本的三种基本结构：线性结构、树型结构和图形结构。常用的算法：查找、排序。

那为什么我们要学习数据结构呢?因为要学好编程，数据结构是必须学好的，不仅仅是结构，每一种结构里面会有几种算法，这些算法包涵了不同的思想。数据结构贯穿程序设计的始终。拥有数据结构与算法的功底，能使我们更快地编写出更高效率的程序。“算法+数据结构=程序”。

数据结构：

1.定义：数据结构是指相互之间存在着一种或者多种关系的数据元素的集合和该集合中数据元素之间的关系组成，分为逻辑数 据结构和存储(物理)数据结构两种。

2.数据包括：数据(原材料)、数据元素(基本单位)、数据项(最小单位)、数据对象(子集)、数据结构(数据的组织形式即集合)、 数据类型(按照数据值的不同进行划分的可操作性)

注意：

(1)数据元素之间不是独立的，而是存在特定的关系的，这下关系为结构。

(2)数据结构指数据对象中数据元素之间的关系。

3.数据的逻辑结构

定义：逻辑结构是指数据对象中数据元素之间的相互关系。

数据的逻辑结构可以分为两种：线性结构和非线性结构(集合、树、网)。

线性结构里的元素是一对一的关系，常见的线性结构是线性表，典型的线性表有：顺序表、链表、栈(知顺序栈、链栈)和队列(顺序队列、链队列)。

非线性结构里的元素是一对多或多对多的关系，常见的非线性结构包括：树(二叉树)、图(网)等。

也可以细分为以下四种基本类型：

集合结构：集合结构里面的元素关系是孤立的，仅同属于相同的集合。

线性结构：数据元素之间存在着一对一的线性关系。除第一个和最后一个元素外，每个元素只有一个前驱和一个后继数据元素。

树结构：数据元素之间存在这一对多的层次关系。除根结点外，每个数据元素只有一个前驱数据元素，可有0个或若干个后继数 据元素。

图结构：数据元素之间存在着多对多的任意关系。每个元素可有0个或若干个前驱数据元素和0个或若干个后继数据元素。

4.数据的存储(物理)结构

定义：物理结构是指数据的逻辑结构在计算机中的存储形式。存储结构有两种：

顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

算法：

1.定义：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

2.算法的五个重要特性：

(1)有穷性：一个算法包含有限个操作步骤。一个算法在执行若干个步骤之后应该能够结束，而且每一步骤都在有限时间内完成。

(2)确定性：算法中的每一步骤必须有确切的含义，不能产生二义性。

(3)可行性：算法中的每一步骤都应该是能有效地执行，并得到确定的结果。

(4)输入：一个算法可以有零个或多个输入。

(5)输出：一个算法有一个或多个输出。没有输出的算法是毫无意义的。

3.算法设计的要求：

算法设计的好坏关乎程序执行效率，算法的设计必须满足下列四个要求：

(1)正确性：正确性是指算法达到了测试要求。

(3)可读性：指人对算法的理解，可读性高便于交流，有利于算法的调试和修改

(3)健壮性：对于非法输入的数据，算法能给出相应的响应，阻止不可预料的后果的产生

(4)效率与低存储量需求：效率指算法的执行时间，执行时间短的算法效率高。存储量需求是指算法执行过程中所需的最大存储空间，存储量需求越小的算法效率越高。

4.算法的分析：

(1)算法效率的度量：算法执行时间是其对应的程序在计算机上运行所消耗的时间。程序在计算机上运行所需时间与下列因素有关：

1)算法本身选用的策略

2)书写程序的语言

3)编译产生的代码质量

4)机器执行指令的速度

5)问题的规模

其中算法本身选用的策略是算法好坏的根本，书写程序的语言和编译产生的代码质量要看具体的软件支持。

(2)算法的时间复杂度：

可以用算法中语句的执行次数来度量一个算法的效率。

(3)算法的空间复杂度：

数据结构与算法之间的关系：既有联系又有区别

1.两者之间的关系：

数据结构是底层，算法高层;

数据结构为算法提供服务;

算法围绕数据结构操作;

2.联系：

程序=算法+数据结构。算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。所以说，数据结构是算法实现的基础，算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。两者是相辅相成的存在，是不可分割的关系。

3.区别：

(1)两者的指代(即定义)不同

(2)目的不同：数据结构研究的是数据的逻辑结构、存储结构的一些基本操作，而算法更多的是研究如何在数据结构的基本上解决实际问题。算法是编程思想，数据结构则是这些思想的基础。

(3)特点不同：算法中执道行内的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成。数据结构核心技术是分解与抽象。通过分解可以划分出数据的3个层次;再通过抽象，舍弃数据元素的具体 内容，就得到逻辑结构。

编程语言中常见的数据结构：

以上就是星辉小编介绍的"数据结构与算法知识"，希望对大家有帮助，如有疑问，请在线咨询，有专业老师随时为您服务。