一、学习目的与要求
理解数据、数据元素和数据项的概念及其相互关系；
理解数据结构的含义；
理解逻辑结构、基本运算和存储结构的概念，意义和分类；
理解存储结构与逻辑结构的关系；
理解算法的概念；
理解衡量一个算法效率的两个标准：时间复杂度和空间复杂度。
二、课程内容 1.1 引言 计算机处理问题的一般步骤：
（1）从具体的问题抽象出一个适当的数学模型；
（2）设计一个求解该数学模型的算法；
（3）用某种计算机语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解答。
1.2 基本概念和术语 1.2.1 数据、数据元素和数据项 数据：所有被计算机存储、处理的对象。数值、布尔值等扩展到字符串、表格、图像甚至声音等。
数据元素（元素）：数据的基本单位，在程序中作为一个整体而加以考虑和处理。
数据项：一般情况下，数据元素由数据项组成。在数据库中数据项又称为字段或域。.它是数据的不可分割的最小标识单位。
结合表1-1，理解数据、数据元素、数据项三个概念及之间的联系
表1-1 学生档案信息表
学号 | 姓名 | 性别 | 年龄 | 入学成绩 |
1001 | 王韬 | 男 | 20 | 589 |
1002 | 潘小欣 | 女 | 21 | 580 |
1003 | 张艳 | 女 | 19 | 568 |
1004 | 赵李军 | 男 | 18 | 580 |
1005 | 刘勇 | 男 | 22 | 585 |
1.2.2 数据的逻辑结构
数据的逻辑结构是指数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联方式或“邻接关系”
四种基本的逻辑结构：
●集合：集合中任意两个结点之间都没有邻接关系，组织形式松散。
●线性结构：一对一
●树形结构：一对多
●图结构：多对多
a）集合 b）线性结构 C）树形结构 d）图结构
1.2.3 数据的存储结构
数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）。一般情况下，一个存储结构包括以下两个部分：
（1）存储数据元素；
（2）数据元素之间的关联方式。
主要的存储方式：顺序存储、链式存储。顺序存储方式是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储方式是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。
除了上述两种存储方式之外，还有索引存储方式和散列存储方式。
1.2.4 运算
运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。一般来说，在每个逻辑结构上，都定义了一组基本运算，这些运算包括：建立、查找、读取、插入和删除等。
1.3 算法及描述
一个算法给规定了求解给定问题所需的处理步骤及其执行顺序，使得给定问题能够在有限的时间内被求解。本书采用类C语言来描述算法
1）函数描述形式.
函数类型 函数名（函数参数表）//算法说明
{
语句序列
}
2）输入、输出语句
输入语句：scanf（格式串，变量1，...，变量n）；
输出语句：printf（格式串，变量1，变量n）；
3）赋值语句 变量名=表达式；
4）选择语句
1>条件语句：
if（表达式）语句；
或
if（表达式）语句；
else语句；
2>分支语句：
switch
｛case条件1：语句序列；break；
case条件2：语句序列；break；
case条件n：语句序列；break；
default：语句序列；｝
其中“default：语句序列；”可以省略。
5）循环语句
for（赋初值表达式序列；条件；修改表达式序列）语句；
while（条件）语句；
do{
语句；
}while（条件）；
6）结束语句
1>函数结束语句：return表达式；
2>case结束语句break；
3>异常结束语句：exit（异常代码）；
7）出错语句：error（"错误描述"）
8）注释
单行注释： //注释内容
多行注释： /*注释内容*/
1.4 算法分析
通常评价算法好坏的因素包括以下几个方面：
1）正确性：能正确地实现预定的功能，满足具体问题的需要。
2）易读性：易于阅读、理解和交流，便于调试、修改和扩充。
3）健壮性：即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。
4）时空性：一个算法的时空性是指该算法的时间性能（或时间效率）和空间性能（或空间效率），前者是算法包含的计算量，后者是算法需要的存储量。
1.4.1 时间复杂度
【例1-4】编制函数求1!+2!+...+n!。
【分析】对于这个问题，可以写出两个算法，如图所示。
两个算法的计算量不同，如何估算算法的计算量?可在算法中合理地选择一种或几种操作作为“基本操作”，对给定的输入，确定算法共执行了多少次基本操作，可将基本操作次数作为该算法的时间度量。
假如问题的输入规模为n，—般情况下，一个算法的计算量是问题规模n的函数。设函数fact1中乘法、加法和赋值的次数记为T（n），则
T（n）=n（n+1）/2+n+n（n+1）/2+2n+1=2（n2+n）/2+3n+1=n2+4n+1
当n充分大时，n2这一项对T（n）的值起着支配作用，采用数学记号Ｏ（n2）表示T（n）的近似值，写为T（n）=Ｏ（n2），这种表示法称为大Ｏ表示法，它的含义是：当n充分大时，算法的执行时间与n2成正比。大Ｏ表示法的具体提法是：当且仅当存在正常数c和n0，使得：T（n）<=cf（n）。
对所有n>n0成立。其中，f（n）为问题的规模n的某个函数，大Ｏ表示法也称为渐进表示法，它不考虑具体的运行时间，只给出算法在问题规模n下执行时间的上界。
T（n）=Ｏ（f（n））称为算法的渐进时间复杂度，简称时间复杂度。
常见的时间复杂度有：常数阶Ｏ（1），对数阶Ｏ（log2n），线性阶Ｏ（n），多项式阶Ｏ（n2）、Ｏ（n3），指数阶Ｏ（2n）
最坏时间复杂度、平均时间复杂度、最好时间复杂度
1.4.2 空间复杂度
一个算法的空间复杂度定义为该算法所耗费的存储空间，它也是问题规模n的函数。通常可记为：S（n）=0（g（n））其中，g（n）为问题规模n的某个函数。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
一个算法在执行期间所需要的存储空间量应包括以下三个部分：
（1）程序代码所占用的空间
（2）输入数据所占用的空间
（3）辅助变量所占用的空间
