001-数据结构与算法简介
本帖最后由 moc 于 2018-9-22 23:01 编辑1、数据结构的起源
计算机从解决数值计算问题发展到解决生活中的问题，现实生活中的问题涉及不同个体间的复杂联系，需要在计算机程序中描述生活中各个个体间的联系，于是产生了数据结构。
数据结构主要研究的是非数值计算程序中的操作对象以及他们之间的关系，不是研究复杂算法的。
2、数据结构中的基本概念
数据： 程序中的操作对象，用于描述客观事物。
数据的特点：
可以输入到计算机中；
可以被计算机程序处理。
数据是一个抽象的概念，将其分类后得到程序设计语言中的类型，如int，float，char等等。
int a;struct Teacher t1; a和t1就是具体的数据。
数据元素： 组成数据的基本单位。
数据项：一个数据元素由若干个数据项组成。
数据对象 => 性质相同的数据元素的集合（如：链表、数组等）。
3、数据结构中的逻辑结构和物理结构
逻辑结构：指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的；逻辑结构可细分为4类：
① 集合 ---- 数据元素间除了同属于一个集合外，无其他关系；
② 线性结构 ---- 数据间有着一个对着一个的关系，如线性表、栈、队列等
③ 树形结构 ---- 一个对多个， 如树；
④ 图形结构 ---- 多个对多个， 如图。
物理结构：也称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像），它依赖于计算机；物理结构也可细分为4类：
① 顺序存储结构 ---- 把数据元素存放在地址连续的存储单元里，数据间的逻辑关系和物理关系是一致的。
② 链式存储结构 ---- 把数据元素存放在任意的存储单元里，这些存储单元不一定是连续的，借助指针表示元素之间的关系。
③ 索引结构 ---- 即计算机文件目录的结构，类似于指针数组构建的二维内存空间。
④ 散列结构 ---- 散列即哈希（hash）每个数据元素与一个键相对配对，该键用于识别数据元素。
数据运算
在数据的逻辑结构上定义的操作，他在数据的存储（物理）结构上实现。
最常用的5种数据运算：插入、删除、修改、查找、排序。
4、算法基本概念
1. 算法的概念
算法是特定问题的求解步骤的描述，在计算机中表现为指令的有限序列。
算法是独立存在的一种解决问题的方法和思想，对算法而言，语言不重要，重要的是思想。
2. 算法和数据结构的区别
数据结构只是静态描述了数据元素之间的关系，高效的程序需要在数据结构的基础上设计和选择算法。
==>程序 = 数据结构 + 算法
即：算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体，数据结构和算法相辅相成。
3. 算法的特性
输入：具有0个或多个输入；
输出：至少有一个输出；
有穷性：有限步骤之后自动结束而不会无限循环；
确定性：每一步都有明确含义，不会出现二义性；
可行性： 算法的每一步都是可行的。
4. 算法的度量
①事后统计法： 比较不同算法对同一组输入数据的运行处理时间
缺陷： 必须依据算法事先编制好测试程序；
严重依赖硬件及运行时的环境；
测试数据的选取相当困难。
②事先分析法：据统计方法对算法进行估算。
5、时间复杂度和空间复杂度
大O表示法： 大写O()来体现算法时间和空间复杂度的记法。
关系：
算法最终都要编译成具体的计算机指令；
每一条指令 在具体计算机 CPU上的运行时间是固定的；
通过具体的步骤的多少就可以推导出算法的复杂度；
// 时间复杂度的度量
// 空间复杂度（32位机为例）
long sum1(int n)//时间复杂度 2n+3 ===> O(n) //空间复杂度 4n+8 ===>O(n)
{
long ret = 0;// 1 //4
int* array = (int*)malloc(n * sizeof(int));// 1 //4*n
int i = 0;// 1 //4
for (i = 0; i < n; i++)// n
{
array = i + 1;
}
for (i = 0; i < n; i++)// n
{
ret += array;
}
free(array);// 1
return ret;
}
long sum2(int n)//时间复杂度 n+2 ===> O(n) //空间复杂度 8 ===>O(1)
{
long ret = 0;// 1 //4
int i = 0;// 1 //4
for (i = 0; i < n; i++)// n
{
ret += i;
}
return ret;
}
long sum3(int n)//时间复杂度 2 ===> O(1) //空间复杂度 4 ===>O(n)
{
long ret = 0;// 1 //4
ret += (1 + n) * n / 2;// 1
return ret;
}
注意1：判断一个算法效率时，往往只需要关注操作数量的最高次项，其他次要项和常数项可以忽略。
注意2：在没有特殊说明的情况下，我们分析的都是算法的时间复杂度都是指最坏的时间复杂度。
6、时间和空间的策略
多数情况下，算法执行所用的时间更令人关注；如果有必要，可以通过增加空间复杂度来降低时间复杂度；同理也可以通过时间空间复杂度来降低复杂度增加。
即常说的：空间换时间；时间换空间。
空间换时间举例：
// 问题： 在一个自然数1-1000中某些数组所组成的数组中，每个数字可能出现0次或多次；
// 设计一个算法，找出出现次数最多的数字。
void search(int a[], int len)
{
int sp = { 0 };
int i = 0;
int max = 0;
for (i = 0; i < len; i++)// 遍历数组，求出每一个数字出现的次数，然后记录下来
{
int index = a - 1;
sp++;
}
for (i = 0; i < 1000; i++)// 扫描数组求出最大数
{
if (max < sp)
{
max = sp;
}
}
for (i = 0; i < 1000; i++)// 打印出现次数最多的数字
{
if (max == sp)
{
printf("%d\n", i + 1);
}
}
} 嗯
好
页:
[1]