第1章 绪论 1.1什么是数据结构
1.1.1数据结构的定义 数据：描述客观事物的数和字符的集合。 数据项：具有独立含义的数据最小单位，也成字段或域。 数据对象:数据的一个子集。 数据结构:数据+结构。存在某种特定关系的数据元素的集合。
数据结构包括: 逻辑结构logical structure（数据和元素逻辑关系） 存储结构storage structure（数据的物理结构，存储表示） 运算operation（施加在数据上的操作）
1.1.2逻辑结构 1.逻辑结构的表示 图表表示（图形表示时，一个结点对应一个数据元素，两结点之间带箭头连线表示相邻关系） 二元组表示（B=(D,R)。R中序偶集合r中任意序偶〈x,y〉表示相邻关系，x为y的前驱元素，y为x的后继元素。若某个元素没有前驱元素，则称该元素为开始元素，若无后继元素，则称为终端元素。 对称序偶在用图形表示逻辑关系时，用不带箭头连线表示） 2.逻辑结构的类型 集合（除了同属于一个集合，别无其他关系） 线性结构（数据元素存在一对一的关系。开始元素和终端元素都是唯一的。其余元素有且仅有一个前驱元素和后继元素。线性表） 树形结构（每个元素仅有一个前驱元素。除了终端元素，每个元素有一个或多个后继元素。二叉树） 图形结构（数据元素之间多对多关系。可能无开始元素和终端元素也可能有多个）
1.1.3存储结构 1.顺序存储结构:将数据的逻辑结构直接映射到存储结构。 优点:存储效率高，可实现随机存取，由序号直接计算元素的存储地址。 缺点:不便于数据修改，插入或删除需要移动一系列元素。 Stud用于唯一标识顺序存储结构，作为数组的起始地址。Stud［i］放在Stud[i+1]之前。 2.链式存储结构:给每个结点附加指针域用于存放相邻结点的存储地址，也就是通过指针域将所有结点链接起来。 优点：便于数据修改，对元素插入删除仅需修改相应结点指针域，不必移动结点。 缺点:存储空间利用率较低，不可随机存取。 首结点指针为head，尾结点指针域为空.一个结点的next指向后继结点。每个结点采用StudType类型单独存储。 3.索引存储结构:存储数据元素信息的同时还建立附加的索引表。 优点：查找效率高 缺点：需要建立索引表，增加空间开销。 4.哈希存储结构：根据元素的关键字通过哈希函数直接计算一个值，并将这个值作为元素的存储地址。（只适合要求对数据能够快速查找和插入的场合） 有点：查找速度快，根据关键字计算存储地址。
1.1.4数据运算 检索、插入、删除、更新、排序 运算定义<——>逻辑结构——>存储结构<——>运算实现
1.1.5数据类型和抽象数据类型 一、数据类型 1.C/C++常用数据类型 （1）基本数据类型：int、bool、float、double、char。 int取值范围-32768~32767，可用±*/运算符
（2）C/C++指针类型 int i,*p ;
int i=2,*p=&i ;
（3）C/C++数组类型 int a[10]包含a[0]~a[9]
(4)C/C++结构体类型 Teacher结构类型： struct Teacher {int no ; char name[8]; int age;};
定义Teacher的一个结构体变量t并赋值： struct Teacher; t.no=85; strcpy(t.name,“张敏”)； t.age=42; 引用no 成员t.no,引用name成员t.name,引用age成员t.age. t变量所分配的内存空间大小为所有成员占用的内存空间之和。 （5）C/C++共用体类型 一个共用体类型Tag： union Tag { short int n; char ch[2]; };
一个共用体变量u赋值： union Tag u； u.n=0x4142; 引用n成员u.n，引用ch成员ch[0]为u.ch[0] u变量所分配的内存空间大小为所有成员占用空间的最大值。 （6）C语言中自定义类型 typedef char ElemType;
2.存储空间的分配 （1）静态存储空间的分配 int a[10]; (2)动态存储空间的分配 char *p; p=(char * )malloc(10 * sizeof(char));//动态分配10个连续字符的空间 strcpy(p,“China”)；//将“China”存放到p所指的空间中 printf("%c\n",*p);//输出首字符C printf("%s\n",p);//输出字符串“China” free§;//释放p所指的空间
二、抽象数据类型 ATD抽象数据类型名 { 数据对象：数据对象的声明 数据关系：数据关系的声明 基本运算：基本运算的声明 } 基本运算声明格式为： 基本运算名（参数表）：运算功能描述
一个复数抽象数据类型Complex定义如下： ATD complex { 数据对象： D={e1,e2|e1,e2均为实数} 数据关系： R={<e1,e2>|e1是复数的实数部分，e2是复数的虚数部分} 基本运算：
}
1.2算法及其描述 1.2.1什么是算法 五个重要特性：有穷性、确定性、可行性、有输入、有输出
1.2.2算法设计的目标 正确性、可使用性、可读性、健壮性、高效率与低存储量需求
1.2.3算法描述 1.算法描述的一般格式与计算步骤 （1）分析算法功能 （2）确定输入输出 （3）设计函数体 2.输出型参数的设计 将输出型形参设计为引用型形参： void swap（int &x,int &y） { int tmp=x; x=y;y=tmp; }
1.3算法分析 1.3.1算法分析CPU时间和内存空间 时间性能分析和空间性能分析
1.3.2算法时间性能分析 1.两种分析方法：事后统计法、事前估算法 2.算法时间复杂度分析： （1）计算算法的频度T（n） 算法时间分析就是求出所有原操作的执行次数（也称频度），它是问题规模的函数，用T（n）表示。 算法执行时间=原操作所需时间*T(n).因此T(n)与算法执行时间成正比。 （2）T（n）用“O”表示 时间复杂度O（f(n)）为T（n）数量级。记作T（n）=O(f(n))
(3)简化的算法时间复杂度的分析 基本操作所需时间*运算次数 （4）时间复杂度的求和、求积定理 3.算法最好、最坏、和平均时间复杂度 4.递归算法时间复杂度分析
1.3.3算法空间性能分析 1.算法空间复杂度分析（存储空间大小的量度） S（n）=O(g(n)) 只考虑临时空间，不考虑形参。 占用存储空间大小与问题规模n无关。 2.递归算法空间复杂度分析
