数据结构

前言

数据结构对于计算机专业来说，算是基础课；可惜在学的时候，并没有学好它；一是重视不够，二呢就是练习的少；好在现在我开始重视这门课了，决定补习一下，好好把知识再过一轮，再多加练习；我参考的专业书是【大话数据结构】和严蔚敏的【数据结构(c)】，都是口碑很好的书；参考的项目地址Mzzopublic/C；不记得那本书上写了 –“了解细节是理解概念的先决条件”；今天开始开这一栏，每天大概花一个小时来整理，不求速度，重在理解

对比

刚开始整理，把两书对比下

严蔚敏的【数据结构(c)】	【大话数据结构】
第1章 绪论	第1章 数据结构绪论 第2章 算法
第2章 线性表	第3章 线性表
第3章 栈和队列	第4章 栈与队列
第4章 串	第5章 串
第5章 数组和广义表
第6章 树和二叉树	第6章 树
第7章 图	第7章 图
第8章 动态存储管理
第9章 查找	第8章 查找
第10章 内部排序	第9章 排序
第11章 外部排序
第12章 文件

严书分了十二章，大话分了九章(你那个目录里面写一大堆话是什么骚操作，我截目录时翻了半天···)；严书的动态存储管理和文件这两张章是大话没有的，这两张涉及了部分操作系统的知识；整体看上去，两本书可以很好的对应；

数据结构绪论

1946年2月14日，世界上第一台电脑ENIAC诞生，美军方将他用于导弹轨道计算；计算机一路发展，给人们的生活带来翻天覆地的变化；数据结构就在此不断发展

基本概念

数据：是客观事物的符号表示，是能被输入到计算机并能被计算机处理的符号总称

数据元素：数据的基本单位

数据项：一个数据元素可以由若干项数据项表示

数据对象：性质相同的数据元素集合，是数据的一个子集

整理了一下，看这个图，就感觉在看关系数据库，这里的一个数据对象就是一张表啊，存储不同的数据元素，而每个数据元素单独又是一张张独立的表，表里有不同的属性（数据项）；若干项数据项组成了数据的基本单位——数据元素，若干数据元素组成一个数据对象，数据是实体的抽象；这里要补充一下数据库的观点，并不是所有的实体（理解成事物）都可以抽象成数据的；这个数据是相对应的概念，取决于你需要解决的问题；比如我们需要知道班级中年龄最大的那个人，我们只需要得到每个人的年龄抽象的数值数据；而这个人的身高信息，从数据关系上说，是这个人（数据元素）的一个数据项；但对于解决谁年龄大这个问题，身高是无关的，所以身高不必抽象成数据

数据结构

数据结构：存在一种或多种特定关系的元素的集合

从不同方面看会有不同的分类：

逻辑结构解决了不同元素之间的关系问题，让解决问题的方案在逻辑上无误；存储结构则解决了怎么让计算机理解处理的问题；理解上，前者是人思考的问题，后者是计算机的过程；辅以相应的操作配合（插入，删除，优化算法提高效率···），这些操作沟通了人和计算机；最终，这三类相互配合，达到处理问题的目的

逻辑结构

集合——数据元素之间除了同属于一个集合外，没有其他关系
线性——数据元素之间是一对一的关系
树形——数据元素之间存在一对多的层次关系
图形——数据元素之间存在多对多的关系

存储结构（物理结构）

数据类型
一组性质相同的值的集合及定义在此集合上的一些操作的总称

类型，指明了变量或表达式的取值范围和所能进行的操作；有的语言是强类型语言（如c），有的是弱类型语言（如JavaScript），强弱之分就是是否严格规定了类型；

C语言中，按照取值的不同，分为

原子类型——不可再分的基本类型，如int，float，long

结构类型——由若干类型组合而成，struct，union

抽象数据类型：通常由用户定义，用以表示应用问题的数据模型以及定义在该模型上的一组操作，ADT=（D，S，P） （D是数据对象，s是D的关系，P是D的操作）

实际上，结构体可以看作是对基本类型的补充，对于你要解决的特定问题，你可以自定义结构体得到一种类型；结构类型和抽象数据类型的区别就是：结构只包含数据和关系，抽象数据增加了操作；对于抽象数据类型，就好像看到了java的类的样子，类包含属性和方法，属性对应抽象数据类型的不同类型，方法对应不同的操作，有异曲同工之妙；但它们实际不同，前者是过程式语言，自底向上；后者是面向对象的语言，自顶而下，其中的思想是不同的

存储方式

顺序存储——把数据元素放在地址连续的存储单元里，数据间的逻辑关系与物理关系一致
链式存储——把数据结构存放在任意的存储单元里，可以是连续的，也可以是不连续的

顺序存储最简单的例子就是数组了，数组是一段连续的内存，顺序存储；链式存储的一个例子单链表，可以存在不连续的内存上

算法

特征：

有穷：执行有限步骤后，自动结束而不会出现无限循环

确定：每一步骤都具有确定含义，不存在二义性

可行：每一步都在有限次数内完成

有输入和输出

要求：

正确性——输入、输出、加工处理无歧义性，能正常反映问题的需求、能得到问题的正确答案

可读性——便于阅读、理解、交流和维护

健壮性——当输入数据非法数据能抛出异常而不至于输出莫名其妙的值

时间效率高和存储量低

算法衡量

方法有事前分析法和事后统计法

衡量标准有时间复杂度和空间复杂度