408计算综合数据结构笔记
绪论
数据结构三要素：
逻辑结构：集合结构，线性结构，树形结构，图状结构；
数据的运算；物理结构（存储结构）
逻辑结构
集合：各个元素同属于一个集合，别无其它关系
线性结构：数据元素直接是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一的后继。（第二，三章）
树形结构：数据元素之间是一对多的关系。（第四章）
图结构：数据元素之间是多对多的关系。（第五章）
数据的运算
针对于某种逻辑结构，结合实际需求，定义基本运算。
运算的定义是针对逻辑结构的，需指出运算的功能；
运算的实现是针对物理结构的，需指出运算的步骤。
定义数据结构=确定逻辑结构+定义基本运算
物理结构（存储结构）
如何用计算机表示数据元素间的逻辑关系
存储结构：顺序存储，链式存储，索引存储，散列存储；
以线性结构为例：
顺序存储：
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体系。
链式存储：
逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
索引存储：
在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项（关键字，地址）。
散列存储：
根据元素的关键字直接计算出元素的存储地址，又称哈希（Hash）存储。（第六章散列表）
存储结构的影响：
1.若采用顺序存储，数据元素在物理上必须的连续的，若采用非顺序存储，数据元素在物理上可以是离散的
2.数据的存储结构会影响存储空间分配的方便程度
3.数据的存储结构会影响对数据运算的速度
数据类型，抽象数据类型
数据类型是一个值的集合和定义在此集合的操作的总称
1）原子类型其值不可再发的类型（bool,int,float。。。）
2）结构类型其值可以分解成若干成分（分量）的类型（struct）
抽象数据类型（Abstract Data Type,ADT）抽象数据组织及与之相关的操作
*定义了一个ADT，就定义了数据结构中的逻辑结构和数据的运算
算法
程序=数据结构+算法
算法（Algorithon）：对特定问题求解步骤的一种描述，他是指令的有限序列，其中的每条指令表示一个或多个操作。
算法的特性
1)有穷性：一个算法必须总在执行有穷步之后结束，且每一步必须可在有穷时间内完成
2）确定性：算法中每条指令必须有确定的含义，并且对相同的输入必须有相同的输出
3）可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4）输入：一个算法有零个或多个输入，这些输入取自某个特定对象（数据对象）的集合
5）输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量
“好”算法的特质
1）正确性：算法应能正确的解决求解问题
2）可读性：算法应该具备良好的可读性，帮助人们理解
3）**健壮性：**输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果
4）高效率与低存储量的需求：花的时间少，时间复杂度低；费内存少，空间复杂度低
算法效率的度量
算法的时间复杂度
事前预估算法时间开销T(n)与问题规模n的关系（T为“Time”）
计算方法示例
算法1逐步递增：
void add(int n)
{
int i; //执行1次
while(i<=n) //执行n+1次
{
i++; //执行n次
}
printf("over,add more than %d\n",n); //执行1次
}
因此上述算法的时间开销与问题规模n的关系应为：
T(n)=2n+3;
时间复杂度表达式的简化
有如下几种时间复杂度表达式：
T1(n)=2n+3;
T2(n)=n^2+3;
T3(n)=n^3+n^2+99999;
当n足够大的时候，真正决定T(n)大小的是其中的最高阶部分，也就是说上述的三个表达式可以写成下面的样子：
T1(n)=2n;
T2(n)=n^2;
T3(n)=n^3;
因此在描述时间复杂度的时候只需要考虑他们的数量级，对此采用“O”来表示：
T1(n)=O(n);
T2(n)=O(n^2);
T3(n)=O(n^3);
表达式加分乘法规则
1）加法规则：
T(n) = T1(n)+T2(n)=O(max(T1(n),T2(n)))
即多式相加只保留最高阶的项
2）乘法规则：
T(n) = T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
时间复杂度阶数大小关系：
多行代码时T(n)的确定
1）顺序执行的代码只会影响常数项，可以忽略
2）只需挑循环中的一个基本操作分析它的执行次数与n的关系即可
3）如果有多层循环结构，只需要关注最深层的循环次数
算法2嵌套循环
void add(int n)
{
int i=1;
while(i<=n)
{
i++; //外层循环执行n次
for(int j=1;j<=n;j++)
{
printf("一战成硕"); //内层循环执行n^2次
}
}
printf("over,add more than %d\n",n);
}
上述算法2的时间开销与问题规模n的关系应是：
T(n)=O(n)+O(n^2) = O(n^2)
小练习
算法3指数递增：
void add(int n)
{
int i=1;
while(i<=n)
{
i=i*2；
}
printf("over,add more than %d\n",n);
}
设循环次数为x
由循环条件可知当
2
x
>
n
2^x>n
2x>n时循环结束
即
x
=
log
2
n
+
1
x=\log_2n+1
x=log2n+1
所以
T
(
n
)
=
O
(
log
2
n
)
T(n)=O(\log_2n)
T(n)=O(log2n)
算法4搜索
int flag[n]={1...n}; //乱序放了n个数的数组flag
void find(int flag[],int n)
{
int i=1;
for(i=0;i<=n;i++)//从第一个元素开始找
if(flag[i]==n) //找到目标
{
printf("find flag\n");
break; //立刻跳出循环
}
}
由于“n”的位置是不确定的需要分多种情况去考虑
最好情况：即“n”在第一个位置，即
最好时间复杂度：
T
(
n
)
=
O
(
1
)
T(n)=O(1)
T(n)=O(1)
最坏情况：即“n”在最后一个位置，即
最坏时间复杂度：
T
(
n
)
=
O
(
n
)
T(n)=O(n)
T(n)=O(n)
平均情况：“n”在任意一个位置的概率均为
1
n
\frac{1}{n}
n1
循环次数
=
(
1
+
2
+
3
+
.
.
.
.
.
+
n
)
1
n
=
(
n
(
1
+
n
)
n
)
1
n
=
1
+
n
2
=(1+2+3+.....+n)\frac{1}{n}=(\frac{n(1+n)}{n})\frac{1}{n}=\frac{1+n}{2}
=(1+2+3+.....+n)n1=(nn(1+n))n1=21+n
即
平均时间复杂度：
T
(
n
)
=
O
(
n
)
T(n)=O(n)
T(n)=O(n)
算法的空间复杂度
空间开销（内存开销）与问题规模n之间的关系S(n),S表示Space.
计算示例
示例1
以上述的算法1来看，程序存储在内存空间的分为两部分
| 内存 |
|---|
| 程序代码（大小固定与问题规模无关） |
| 数据 （局部变量i，参数n） |
这种情况无论问题怎么变，算法所需要的内存空间都是一个常量，所以算法的空间复杂度为：
S
(
n
)
=
O
(
n
)
S(n)=O(n)
S(n)=O(n)
示例2
void test(int n)
{
int flag[n];
int i;
.....
}
| 内存 |
|---|
| 程序代码（大小固定与问题规模无关） |
| 数据 （局部变量i，数组flag[n],参数n） |
假设一个int变量占4B
则内存所需空间
=
4
+
4
n
+
4
=
4
n
+
8
=4+4n+4=4n+8
=4+4n+4=4n+8
此时空间复杂度：
S
(
n
)
=
O
(
n
)
S(n)=O(n)
S(n)=O(n)
示例3
void test(int n)
{
int flag[n];
int other[n];
int i;
.....
}
| 内存 |
|---|
| 程序代码（大小固定与问题规模无关） |
| 数据 （局部变量i，数组flag[n][n],other[n]参数n） |
时间复杂度的加法规则同样适用：
S
(
n
)
=
O
(
n
2
)
+
O
(
n
)
+
O
(
1
)
=
O
(
n
2
)
S(n)=O(n^2)+O(n)+O(1)=O(n^2)
S(n)=O(n2)+O(n)+O(1)=O(n2)
示例4递归调用带来的内存开销
void text(int n){
int a,b,c;
.....
if(n>1){
text(n-1);
}
printf("over");
}
| 内存 |
|---|
| 程序代码（大小固定与问题规模无关） |
| 数据 （局部变量a,b,c，参数n） |
| 数据（局部变量a,b,c，参数n-1） |
| 。。。。。。 |
| 数据（局部变量a,b,c，参数1） |
由于每次调用都会开辟一个新的内存空间，所以需要将每次占用的空间加起来，该算法中的flag每次占据空间都会少1，所以：
1
+
2
+
.
.
.
.
+
n
=
n
(
1
+
n
)
2
=
=
n
2
2
+
n
2
1+2+....+n=\frac{n(1+n)}{2}==\frac{n^2}{2}+\frac{n}{2}
1+2+....+n=2n(1+n)==2n2+2n
最终
S
(
n
)
=
O
(
n
2
)
S(n)=O(n^2)
S(n)=O(n2)