目录
1.1 数据结构的基本概念(定义)
1.2 数据结构的内容（研究范围）
1.3 算法设计
1.4 算法描述工具
1.5 对算法作性能评价
1.6 数据结构与C语言表示
1.1 数据结构的基本概念(定义)
数据结构的相关名词： 数据（Data） 数据元素（Data Element） 数据对象（Data Object） 数据结构（Data Structure） 数据类型(Data Type) 数据抽象与抽象数据类型
数据（Data）
定义：数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。
数据元素（Data Element）
定义：数据元素是组成数据的基本单位 ，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：
数据对象（Data Object）
定义： 数据对象是性质相同的数据元素的集合，是数据的一个子集。
整数集合：N={0，±1，±2，…} 无限集
字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ} 有限集
数据结构（Data Structure）
定义： 数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。
例如表结构：
数据类型(Data Type)
定义：数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
如在高级语言中，整型类型的取值范围为： -32768~+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。
高级语言中的数据类型分为两大类：
1.原子类型，其值不可分解。如C语言中的标准类型（整型、实型、字符型、）。
2.结构类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。
数据抽象与抽象数据类型
数据的抽象
抽象数据类型(Abstract Data Type)
抽象数据类型实现
ADT的表示与实现
面向对象的概念
结构化的开发方法与面向对象开发方法不同点
1.2 数据结构的内容（研究范围）
逻辑结构 存储结构 运算集合
逻辑结构
定义： 数据的逻辑结构是指数据元素之间逻辑关系描述
形式化描述：Data_Structure=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。
四类基本的结构 ：集合结构、线性结构、树型结构、图状结构。
集合结构：
定义：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
线性结构：
定义：结构中的数据元素之间存在着一对一的线性关系。
树型结构：
定义：结构中的数据元素之间存在着一对多的层次关系。
图状结构或网状结构：
定义：结构中的数据元素之间存在着多对多的任意关系。
综上所述，数据的逻辑结构可概括为：
存储结构：
定义：存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。
形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元映象S ，D→M，即对于每一个d， d∈D,都有唯一的z∈M使S（D）=Z, 同时这个映象必须明显或隐含地体现关系R。
逻辑结构与存储结构的关系为：
存储结构是逻辑关系的映象与元素本身映象，是数据结构的实现；逻辑结构是数据结构的抽象。
数据元素之间关系在计算机中的表示方法：
顺序映象 （顺序存储结构）
非顺序映象（非顺序存储结构）
运算集合
数据结构的内容：
综上所述，数据结构的内容可归纳为三个部分， 逻辑结构、存储结构和运算集合： 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。
1.3 算法设计
算法（Algorithm）定义
算法的特性
算法设计的要求
算法（Algorithm）定义：算法是规则的有限集合，是为解决特定问题而规定的一系列操作。
算法的特性：
1.有限性：有限步骤之内正常结束，不能形成无穷循环。
2. 确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。
3. 输 入： 有多个或0个输入。
4. 输 出： 至少有一个或多个输出。
5. 可行性：原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。
算法设计的要求：算法的正确性，可读性，健壮性，高效率和低存储量
1.4 算法描述工具
概述：
算法+数据结构=程序
算法、语言、程序的关系
1. 算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。
2. 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。
3.程序是算法在计算机中的实现。
设计实现算法过程步骤
1. 找出与求解有关的数据元素之间的关系
2. 确定在某一数据对象上所施加运算
3. 考虑数据元素的存储表示
4. 选择描述算法的语言
5.设计实现求解的算法，并用程序语言加以描述。
类描述算法的语言选择
类语言：
类语言是接近于高级语言而又不是严格的高级语言，具有高级语言的一般语句设施，撇掉语言中的细节，以便把注意力主要集中在算法处理步骤本身的描述上。
对C语言作以下描述：
循环语句：
1.5 对算法作性能评价
评价算法的标准：评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。
性能评价
定义：问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。
问题规模N—对不同的问题其含义不同：
对矩阵是阶数；
对多项式运算是多项式项数；
对图是顶点个数；
对集合运算是集合中元素个数。
有关数量关系计算
数量关系评价体现在时间——算法在机器中所耗费时间。
数量关系评价体现在空间——算法在机器中所占存储量。
关于算法执行时间
语句频度
算法的时间复杂度
数据结构中常用的时间复杂度频率计数
最坏时间复杂度
算法的空间复杂度
关于算法执行时间
定义：一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。
分析：不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。
语句频度
定义：语句频度是指该语句在一个算法中重复执行的次数。
算法的时间复杂度
算法的时间复杂度，即是算法的时间量度记做： T(n)=O(f(n))
常用的时间复杂度频率计数
数据结构中常用的时间复杂度频率计数有7个:
O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型
O(log2n)对数型 O(nlog2n)二维型
按时间复杂度由小到大排列的频率表：
最坏时间复杂度：
定义：讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。
例如冒泡排序算法
void bubble(int a[], int length)
{将a中整数数组重新排序，达到递增有序}
int i=0, j, temp;
int change ;
do{
change=false ;
for(j=1;ja[j+1])
{
temp= a[j];
a[j]=a[j+1];
a[j+1]=temp;
change=true;
}
i=i+1 ;
}
while(i
算法的空间复杂度
定义： 用空间复杂度作为算法所需存储空间的量度， 记做： S(n)=O(f (n)) 。
1.6 数据结构与C语言表示
数据结构与程序设计的关联性
问题描述：欲求1名学生10次C语言程序设计的测试成绩总分与平均分。其中10次测验的成绩分别为：80，85，77，56，68，83，90，92，80，98。
main()
{ int sum，verage；
int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10；
t1=80；t2=85；t3=77；t4=56； t5=68；
t6=83；t7=90；t8=92；t9=80；t10=98;
sum= t1+t2+t3+t4+t5+t6+t7+t8+t9+t10;
average=sum/10;
printf(“总分=%dn”,sum); printf(“平均分=%dn”, average);
}
根据测试次数与测试成绩的关系，采用数组结构存储测验成绩，提高了程序的适用范围。
main()
{ int sum，erage；int i;
int t[10] =80，85，77，56，68，83，90，92，80，98}
sum=0;
for (i=0; i<10; i++)
sum=sum+t[i];
average=sum/10;
printf(“总分=%dn”,sum); printf(“平均分=%dn”, average);
}
结构化程序设计与函数的模块化
结构化程序设计 ：是为使程序具有合理的结构，以保证程序正确性而规定的一套程序设计的方法
程序设计的实质：算法+数据结构=程序
即“程序是在数据的特定表示方式的基础上，对抽象算法的具体描述”
程序结构=控制结构+数据结构
① 结构化程序设计目的
通过设计结构良好的程序，以程序的静态良好结构保证程序动态执行的正确性，使程序易理解、易调试、易维护，以提高软件开发的效率，减少出错率。
②结构化程序设计的构成单元
任何程序都可由顺序、选择、重复三种基本控制结构来组成。
③结构化程序设计方法
其一：“自顶向下，逐步求精”的设计思想 ；
其二：“独立功能，一个入口，一个出口“的模块化结构；
其三：“仅用三种基本控制结构”的设计原则
面向对象与抽象数据类型
面向对象=对象+类+继承+通信
对象：指在应用问题中出现的各种实体、事件、规格说明等 。
类：具有相同属性和服务的对象。
继承：是面向对象方法的最有特色的方面。
（1）面向对象程序设计的特点是封装性、继承性和多态性。
（2）与数据结构密切相关的是定义在数据结构上的一组操作
基本操作主要有：
⑴插入：在数据结构中的指定位置上增添新的数据元素 ；
⑵删除：删去数据结构中某个指定数据元素 ；
⑶更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合 ；
⑷查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值）；
⑸排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。
结构化与面向对象开发方法的不同点
结构化的开发方法：是面向过程的开发方法，首先着眼于系统要实现的功能。
面向对象的开发方法： 首先着眼于应用问题所涉及的对象，包括对象、对象属性和要求的操作，从而建立对象结构和为解决问题需要执行的时间序列。
