数据结构学习笔记（一）----绪论
目录
为什么要学习数据结构
数据结构的研究内容
基本概念和术语
数据结构（Data Structure）
数据结构的两个层次：
数据的运算
数据类型
抽象数据类型(ADTs:Abstract Data Types)
算法和算法分析
算法效率的度量
事前分析估计
事后统计
时间复杂度的渐进表示法
分析算法时间复杂度的基本方法：
渐进空间复杂度
算法要占据的空间
结语：本章学习流程图如下：
为什么要学习数据结构
编程基础
计算机及相关专业考研博课程
计算机等级考试课程
程序员考试课程
数据结构的研究内容
N.沃思（Niklaus Wirth)教授提出：
程序=算法+数据结构
电子计算机的主要用途：
早期：主要用于数值计算
后来：处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据
数据结构的研究内容为：
研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作
基本概念和术语
数据结构（Data Structure）
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的两个层次：
逻辑结构：用数据元素间的相互关系
- 线性结构：线性表、栈、队列、串；
- 非线性结构：树、图；
存储结构（物理结构）：数据元素及其关系在计算机存储器中的存储方式
- 顺序存储：用元素在储存器的相对位置来表示数据元素间的逻辑关系 ；
- 链式存储：用元素存储地址的指针来表示数据元素间的逻辑关系；
数据的运算
常见的运算：插入、删除、修改、查找、排序
数据类型
基本数据类型：char、int、float、double、void
构造数据类型：数组、结构体、共用体、文件
抽象数据类型(ADTs:Abstract Data Types)
- 预定义常量及类型
- 内存的动态分配与释放
算法和算法分析
算法定义：解决问题的有限个步骤；
算法效率的度量
算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量
- 事前分析估计
- 事后统计
事前分析估计
一个高级语言程序在计算机上运行所消耗的时间取决于：
- 依据的算法选用何种策略
- 问题的规模
- 程序语言
- 编译程序产生
- 机器代码质量
- 机器执行指令速度
同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———使用绝
对时间单位衡量算法效率不合适。
事后统计
利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分
缺点：
- 必须先运行依据算法编制的程序
- 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣
时间复杂度的渐进表示法
算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：
T(n)=O(f(n))
算法中重复执行次数和算法的执行时间成正比的语句对算法运行时间的贡献最大
n越大算法的执行时间越长
- 排序：n为记录数
- 矩阵：n为矩阵的阶数
- 多项式：n为多项式的项数
- 集合：n为元素个数
- 树：n为树的结点个数
- 图：n为图的顶点数或边数
n * n阶矩阵加法：
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
c[i][j] = a[i][j] + b[i][j];
语句的频度（Frequency Count ):
重复执行的次数：n*n;T( n ) = O ( n2)即：矩阵加法的运算量和问题的规模n的平方是同一个量级
分析算法时间复杂度的基本方法：
- 找出语句频度最大的那条语句作为基本语句
- 计算基本语句的频度得到问题规模n的某个函数f(n)
- 取其数量级用符号“O”表示
时间复杂度是由嵌套最深层语句的频度决定的
例1：N×N矩阵相乘
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{c[i][j]=0;
for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
} 
例3：
i=1;
while(i<=n)
i=i*2;
渐进空间复杂度
空间复杂度:
算法所需存储空间的度量，记作:
S(n)=O(f(n))其中n为问题的规模(或大小)
算法要占据的空间
- 算法本身要占据的空间，输入/输出，指令，常数，变量等
- 算法要使用的辅助空间
结语：本章学习流程图如下：
