浅析数据结构之绪论
数据结构和算法
- 数据： 是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
- 数据元素：组成数据的，有一定意义的基本单位，在计算机中通常作为整体进行考虑和处理，也被称为记录。
- 数据元素组成数据。
- 数据项：数据项是数据不可分割的最小单元，一个数据元素可以由若干个数据项组成。数据项是对客观事物某一方面特性的数据描述。
- 数据对象：性质相同的数据元素的集合，是数据的子集
数据结构概述
数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本逻辑类型：
逻辑结构：
- 1、集合结构：
1.集合结构中数据元素同属于一个集合。
2.数据元素相互之间没有关系。 - 2、线性结构： 数据元素之间是一对一的关系。
- 3、树形结构： 数据元素之间一种一对多的层次关系。
- 4、图状结构（网状结构）： 数据元素之间是多对多的关系。
物理结构：又叫存储结构，是指数据的逻辑结构在计算机中的存储形式。
- 1、线性：索引存储，数据元素的存储
数组、链表
具体应用：栈和队列（特殊的线性结构） - 2、非线性：散列存储，元素之间的关系的表示
树、图
元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。
顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。
链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构
数据结构的三个组成部分：
- 逻辑结构： 数据元素之间逻辑关系的描述
D_S=（D，S） - 存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。
- 数据操作： 对数据要进行的运算。
算法
算法的五大特性：
- 有穷性：有穷步 有穷时间
- 确定性：每一条指令都有明确的含义
- 可行性：算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现
- 输入: 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合
- 输出: 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量
算法的设计要求
- 正确性：算法应当满足具体问题的需求
- 可读性：算法主要是为了人的阅读与交流，其次才是机器执行
- 健壮性：输入的数据非法时，算法应当作出反应或者进行
- 通用性： 算法应具有一般性 ，即算法的处理结果对于一般的数据集合都成立。相应的处理，而不是产生莫名其妙的输出结果
- 高效率与低存储量需求： 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关
算法效率的质量
算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：
- 事后统计：计算机内部进行执行时间和实际占用空间的统计。
问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。 - 事前分析：求出该算法的一个时间界限函数。
与此相关的因素有：- 依据算法选用何种策略；
- 问题的规模；
- 程序设计的语言；[注]：严书上是有这一条的，如果你的目标院校推荐书目不是这本，那么这一条可以省略。
- 编译程序所产生的机器代码的质量；
- 机器执行指令的速度；
衡量算法的标准：
- 1.时间复杂度，程序大概的执行次数，而非执行的时间。
- 2.空间复杂度，算法执行过程中大概所占的最大内存。
- 3.难易程度，即是否容易被人理解。
- 4.健壮性，即是否容易崩溃
复杂度： O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)
数据结构的地位
数据结构上软件中最核心的课程
算法
1.狭义的算法与数据的存储密切相关
2.广义的算法与数据的存储无关，广义的算法就是泛型
泛型：利用某种方式达到的效果，不同的存数方式，执行的操作是一样的。