前言

数据结构笔记第一章

一、基本概念

1.数据

1、数据元素——组成数据的基本单位
2、数据——是能输入计算机且能被计算机处理的各种符号集合
3、数据项——构成数据元素不可分割的最小单位
4、数据对象——性质相同的数据元素的集合

2.数据结构

指元素之间不是独立存在的，他们之间存在着某种关系，数据元素相互之间的关系称之为结构，或者说是数据结构是带带结构的数据元素的集合。

3.逻辑结构

数据元素之间的逻辑关系称之为逻辑结构
数据结构有两种划分方法
（1）线性机构与非线性结构
线性结构：有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个前趋和一个直接后继。例如线性表、栈、队列。
（2）四类基本逻辑结构
集合逻辑：结构中的数据元素之间同属以一个集合的关系外，无任何其他关系。
线性结构：结构中的数据元素之间存在着一对一的线性关系。
树形结构：结构中的数据元素中存在着一对多的关系
图状结构：结构中的数据元素之间存在着多对多的关系

4.存储结构

1、顺序存储结构：用一种连续的存储单元依次存储数据元素。数据元素之间的逻辑关系由元素的存储位置来表示。
2、链接存储结构：用一组任意的存储单元存储数据，数据元素之间的逻辑关系用指针来表示。
3、索引存储结构：在存储信息的同时还建立附加的索引表。
4、散列存储结构：根据结点的关键字直接结算出该节点的存储地址。

5.数据类型

1、数据类型
在使用高级程序设计语言编写程序时，必须对程序中的每一个变量、常量或表达式，明确说明他们所属的数据类型，数据类型的作用是1、约束变量或常量的取值范围。2、约束变量或常量的操作。
2、抽象数据类型（Abstract Data Type）
ADT是指一个数学模型以及定义在此数学模型上的一组操作
定义格式如下

ADT 抽象数据类型名{
	数据对象：<数据对象的定义>
	数据关系:<数据关系的定义>
	基本操作：<基本操作的定义>
}ADT 抽象数据类型名

用c语言具体实现抽象数据
具体例子如下：
“复数”的实现

typedef struct{
	float realpart;
	float imaqpart;
}Complex
void add(Complex *a,float real,float imag){
	//此处据情况而定
}

二、算法

1.算法定义

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

2.算法与程序

算法是解决一个问题的一种方法或者一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
程序是用某种程序设计语言对算法的具体实现。

3.算法特性

（1）又穷性：一个算法必须是在执行又穷步之后结束，且每一步都在有穷的时间内完成
（2）确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入得到相同的输出。
（3）可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
（4）输入：一个算法有零个或者多个输入。
（5）输出：一个算法有零个或者多个输出。

3.算法设计要求

（1）正确性：算法中不含语法错误，对于一切合法输入都能得出满足要求的结果
（2）可读性：易于人的理解
（3）健壮性：当输入非法数据时，算法能作出恰当的处理
（4）高效性：尽量降低所用的时间和存储需求

4.时间复杂度

1、一个好的算法主要要考虑它的算法效率
算法效率主要通过以下两个方面考虑
（1）时间效率：指的是算法所消耗的时间
（2）空间效率：指的是算法执行过程中所消耗的存储空间。
时间效率和空间效率有时候是矛盾的。
算法时间效率可以通过程序在执行过程中所消耗的时间来度量
事后统计：将算法实现，测量其时间和空间的开销
事前分析：对算法资源消耗的一种估算方法
事后统计的结果会因为计算机软硬件环境而产生影响，因此不太适宜。
事前分析的方法是通过一条简单的操作执行所需要的时间乘以执行次数即可。
2.时间复杂度
若有某个辅助函数f(n)，当n趋近于无穷大时，T(n)/f(n)是不等于0的常数时，则称f(n)是T(n)的同数量级函数
称O(f(n))为算法的时间复杂度
3、分析时间复杂度的方法
（1）找出语句频率最大的基本语句
（2）计算基本语句的频度
（3）计算取得时间复杂度