【数据结构】--绪论

 •数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树 •算法： 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。 1.1数据结构研究 无法用数学公式或者方程来描述，是一些”非数值计算”的程序设计问题，描述非数值计算问题的数学模型不是数学方程，而是诸如表、树和图之类的具有逻辑关系的数据。 数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科 1.2基本概念和术语1 1.2.1 数据、数据元素、数据项和数据对象 1.数据：是能输入计算机且能被计算机处理的各种符号的集合 •信息的载体； •是对客观事物符号化的表示； •能够被计算机识别、存储和加工； 包括： •数值型的数据：整数、实数等 •非数值型的数据：文字、图像、图形、声音等。 2.数据元素：是数据的基本单位，也简称为元素、记录、节点或顶点。 3.数据项：数据项是构成数据元素的不可分割的最小单位。

数据、数据元素、数据项三者之间的关系：
数据>数据元素>数据项
eg：学生表>个人记录>学号、姓名…
4.数据对象：是性质相同的数据元素的集合，是数据的一个子集。

补充：数据元素与数据对象的区别：
•数据元素——组成数据的基本单位。
与数据的关系：是集合的个体
•数据对象——性质相同的数据元素的集合。
与数据的关系是：集合的子集
数据、数据对象、数据元素、数据项四者之间的关系：
数据>=数据对象>=数据元素>数据项

1.2.2数据结构（Data Structure）
数据结构
•数据元素相互之间的关系称为结构
•是指相互之间存在一种或多种特定关系的数据元素集合
•数据结构是带结构的数据元素的集合
数据结构包括以下三个方面的内容：
•数据元素之间的逻辑关系，也称为 逻辑结构；
•数据元素及其关系在计算机内存中的表示(又称为映像)，称为数据的物理结构或数据的存储结构；

•数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。
逻辑结构的种类：
划分方法一：
•线性结构

•非线性结构

划分方式二：
•集合结构：结构中的元素之间除了同属于一个集合的关系外，无任何其它关系。
•线性结构：结构中的数据元素之间存在着一对一的线性关系。
•树形结构：结构中的数据元素之间存在着一对多的层次关系。
•图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

存储结构的种类：
四种基本的存储结构：顺序、链式、索引、散列
1.顺序存储结构：
•用一组连续的的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示；
•c语言中用数组来实现顺序存储结构；
1.链式存储结构：（看下图中的例子）
•用一组任意的的存储单元依次存储数据元素，数据元素之间的逻辑关系用指针来表示；
•c语言中用指针（地址）来实现链式存储结构

1.索引存储结构（目录）

1.散列存储结构：
根据结点的关键字直接计算出该结点的存储地址。

1.2.3数据类型和抽象数据类型

1. 数据类型简介：
   •定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
   •数据类型=值的集合+值集合上的一组操作
   •在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。

•一些最基本数据结构可以用数据类型来实现，如数组、字符串等；
•而另一些常用的数据结构，如栈、队列、树、画等，不能直接用数据类型来表示。
2. 数据类型的作用：
•约束变量或常量的取值范围；
•约束变量或常量的操作；
3. 抽象数据类型（Abstract Data Type,ADT）：
3.1 概念：是指一个数学模型以及定义在此数学模型上的一组操作。
•由用户定义，从问题抽象出数据模型（逻辑结构）
•包括定义在数据模型上的一组抽象运算（相关操作）
•不考虑计算机内的具体存储结构与运算的具体实现算法。
3.2 一个抽象数据类型的定义格式如下：
ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义>}ADT 抽象数据类型名
•其中：数据对象、数据关系的定义用伪代码描述
•基本操作的定义格式为：
–基本操作名（参数表）
–初始条件：<初始条件描述>
–操作结果：<操作结果描述>
3.3基本操作定义格式说明：
参数表：赋值参数 只为操作提供输入值。
引用参数 以&打头，除可提供输入值外，还将返回操作结果

初始条件：

操作结果：
说明操作正常完成之后，数据结构的变化状况和应返回的结果。

抽象数据类型（ADT）定义举例：Circle的定义：
ADT Circle{ 数据对象：D={r,x,y|r,x,y均为实数} 数据关系：R={<r,x,y>|r是半径，<x，y>是圆心} 基本操作： Circle(&C,r,x,y) 操作结果：构造一个圆。 double Area© 初始条件：圆已存在。 操作结果：计算面积。 double Circumference© 初始条件：圆已存在。 操作结果：计算周长。 …}ADT Circle
抽象数据类型（ADT）定义举例：复数的定义：

1.3抽象数据类型的表示与实现：

抽象数据类型的实现：

•抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。
•在本门课程的学习过程中，我们使用的类C语言（介于伪代码和C语言之间）作为描述工具。
其中，用C语言真正实现抽象数据类型的定义
•例如：抽象数据类型“复数”的实现
typedef struct{ float realpart; float imagpart;}Complex

用C语言实现抽象数据类型:

抽象类型数据举例：

1.4算法和算法分析

1. 算法的定义
   对特殊问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。吧
   算法的描述
   •自然语言：英语、中文
   •流程图：传统流程图、NS流程图
   •伪代码：类语言
   •程序代码：C语言程序、JAVA语言程序…
2. 算法与程序

3.算法特性：一个算法必须具备以下五个重要特性
有穷性、确定性、可行性、输入、输出

4.算法设计的要求
•正确性

•可读性

•健壮性（鲁棒性）

•高效性

算法效率以下两个方面来考虑：

5.算法时间效率的度量
可以根据该算法编制的程序在计算机上执行所消耗的时间来度量
两种度量方法：
•事后统计
将算法实现，测算其时间和空间开销。
•事前分析
对算法所消耗资源的一种估算方法
事前分析方法

6.算法时间复杂度定义
算法中基本语句重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作： T（n）=O（f（n））
它表示随着n的增大，算法执行的时间的增长率和f（n）的增长率相同，称 渐进时间复杂度（最高幂次数）。

分析算法时间复杂度的基本方法
1.找出语句频度最大的那条语句作为基本语句；
2.计算基本语句的频度得到问题规模n的某个函数f（n）；
3.取其数量级用符号”O”表示。

时间复杂度是由嵌套最深层语句的频度决定的
例题：

算法时间复杂度
•最坏时间复杂度
•平均时间复杂度
•最好时间复杂度

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
•对于复杂的算法，可以将它分成几个容易估算的部分，然后利用加法法则和乘法法则，计算算法的时间复杂度：

7.渐进空间复杂度
•空间复杂度：算法所需存储空间的度量，
记作：S（n）=O（f（n））
其中n为问题的规模（或大小）
•算法要占据的空间
–算法本身要占据的空间，输入/输出，指令，常数，变量等
–算法要使用的辅助空间
算法空间复杂度分析例题

8.总结：设计好算法的过程

注：本文章为个人观看青岛大学王卓老师数据结构课程课堂笔记