1、第1章 绪论 1.1 数据结构 1.2 基本概念和术语 1.3 抽象数据类型 1.4 算法和算法分析引引 论论 对于一个课题，在计算机领域，一般遵循下面的解决原则： 需求分析 总体设计 模块分割 建立数学模型 解数学模型的算法 程序编制 调试 结果 数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法。 数据结构的地位：数学、硬件、软件之间。核心专业基础课.1.1数据结构的基本概念和术语1. 基本术语（1）数据：描述客观事物的数字、字符以及所有能 输入到计算机中并被计算机程序处理的符号的 集合。（数字、字符、声音、图形、图像等等）（2）数据元素：数据的基本单位，在计算机程序中 常常作为
2、一个整体进行考虑和处理，如纪录/结 构。（3）数据项：数据的不可分割的最小单位，如结构 中的域。（4）数据对象：性质相同的数据元素的集合，是数 据的一个子集。2. 数据结构（1）定义：是相互之间存在一种或多种特定关系的 数据元素的集合。 数据之间不是相互独立的，他们之间有某种特定的关系，这种数据元素之间的关系，称为“结构” 结构=关系+实体 另一种定义：按照逻辑关系组织起来的一批数据, 按一定的存储方法把它存储在计算机中, 并在这些数据上定义了一个运算的集合。 形式定义：二元组 (D,S) 其中D是数据元素的有限集，S是D上关系的有限集（2）四种基本结构（逻辑结构） p5 集合：元素仅属于同一
3、个集体，没有其他关系。 线性结构：存在一对一 关系，序列相邻，次序关系。 树型结构：存在一对多关系，层次关系。 图状结构（网状结构） ：存在多对多关系，任意性v存储器模型：一个存储器M是一系列固定大小的存储单元，每个单元U有一个唯一的地址A(U)，该地址被连续地编码。每个单元U有一个唯一的后继单元U=succ(U) v物理结构就是逻辑结构到存储器的一个映射。v四种存储结构：顺序存储、链接存储、索引存储、散列存储（3）实例：P1-P3 例1-1 例1-3表：计算机系人事表工号姓名性别职务教研室工作时间发表论文01系主任软件1981.1A,B02教研室主任软件1985.1B,C,E,F03教师软件
4、1990.8C,D04教师应用1987.8A,G05教师应用1975.9E,I06教师应用1992.2F,J07教师软件1983.8D,L08教研室主任应用1986.7G,H09教师应用1995.8H,I,J,K10教师软件1989.2L,K3. 数据结构的划分（1）按数据结构的性质划分 数据的逻辑结构数据元素之间的逻辑关系 （设计算法 数学模型） 数据的物理结构数据结构在计算机中的 映像 （存储结构，算法的实现）3. 数据结构的划分（2）按数据结构在计算机内的存储方式来划分 顺序存储结构借助元素在存储器的相 对位置来表示数据元素之间的逻辑关系。 链式存储结构借助指示元素存储地址 的指针表示数
5、据元素之间的逻辑关系。3. 数据结构的划分（2）按数据结构在计算机内的存储方式来划分 索引存储方法：在存储结点的同时，还建立附加 的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。 散列存储方法：根据结点的关键字直接计算出该结点的存储地址。说明：四种存储方法可结合起来对数据结构进 行存储映像。3. 数据结构的划分（3）按数据结构的操作来划分 静态结构经过操作后，数据的结构特征保持不变（如数组）。 半静态结构经过操作后，数据的结构特性只允许很小变迁（如栈、队列）。 动态结构经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）。1.2 抽象数据类型 ADT 定义：是指基
6、于一个逻辑类型的数据模型以及定义在该模型上的一组操作。每一个操作由它的输入和输出定义。 抽象的与具体的相对应 示例： int a,b; 则 a和b可以进行+、-、*、/的运算 2和6则是具体的int数据1.3 算法和算法分析1. 算法 p13 定义：指一系列确定的而且是在有限步骤内 能完成的操作。算法的重要特性 P13(1) 有穷性 ：能执行结束(2) 确定性 ：对于相同的输入执行相同的路径(3) 0至多个输入(4) 1至多个输出(5) 有效性(可行性) （用于描述算法的操作都是 足够基本的） 问题：程序是不是算法？ 如操作系统，只要系统不遭破坏，它就永远不会停止，即使没有作业要处理，仍处于一
7、个等待循环中，等待新作业的进入。因此操作系统程序不是一个算法。2. 算法与数据结构的关系 计算机科学家沃斯（N.Wirth）提出的:“算法算法+数据结构数据结构=程序程序” 揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。 一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据。 p6图1.6上面2行算法与数据结构关系举例例1：编写程序查询某城市某人的电话号码 建立一张登记表，存放2个数据项：姓名+Tel 好的算法取决于这张表的结构及存储方式：v将表中结点按
8、照姓名顺序地存储在计算机中，依次查找，可能遍历整个表都找不到。v建立一张姓氏索引表：姓+表中的起始地址 则不需查找其他姓氏，查找效率得到提高。算法与数据结构关系举例 例2: 设计一个考试日程安排表，使在尽可能短的时间内安排完考试，要求同一个学生选修的几门课程不能安排在同一个时间内。姓名选修1选修2选修3ABECDCEFDFABF算法与数据结构关系举例 解决该问题，首先选择一个合适的数据结构。用无向图表示，图中的顶点表示课程，不能同时考试的课程之间连上一条边。则该问题就抽象成对该无向图进行“着色”操作，即用尽可能少的颜色去给图中每个顶点着色，使得任意两个相邻的顶点着不同的颜色。同一种颜色表示一个
9、考试 时间。 答案：1：A,C 2:B,D 3:E 4: F 解决问题的关键步骤是先选取合适的数据结构表示问题，才能写出有效的算法。3. 算法设计的要求 p13p14（1）正确性 四层含义 p14 a,b,c,d（2）可读性 首先是给人读，然后才是机器执行（3）健壮性 容错性（4）效率与低存储量需求算法的效率效率 定义：一个算法如果能在所要求的资源限制资源限制内将问题解决好，则称这个算法是有效率的有效率的。 例如，一个资源限制是：可用来存储数据的全部空间可能是分离的内存空间限制和磁盘空间限制以及允许执行每一个子任务所需要的时间。4 . 算法的分析 算法性能的评价 评价标准： 1）算法所需的计算
10、时间 2）算法所需的存储空间 3）算法的简单性 度量算法执行时间的两种方法 p14 1）事后统计法 此方法有两个缺陷 p14 2）事前分析估算法 此方法取决于多个因素：a,b,c,d,e p145 . 时间复杂度（1）引例 （a） +x; s=0； +x 的频度为1 （b） for (i=1; i=n; +i) +x; s+=x; +x的频度为n （c） for (j=1;j=n;+j) for (k=1;k=n;+k) +x; s+=x; +x的频度为n2 5 . 时间复杂度（2）定义： 一般情况下，算法中基本操作重复执行的时间是问题规模n的某个函数f(n)，算法的时间量度记作 T(n) =
11、 O(f(n) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度时间复杂度。 语句的频度频度：该语句重复执行的次数。频度统计法 表：时间复杂度和算法运行时间的关系T(n)nO(logn) O(n)O(nlogn)O(n2 )O(n3 )O(n5 )O(2n )O(n!)204.3us20us86.4us400us8ms3.2s1.05s771世纪405.340213160064ms1.7min12.7天2.59*1032世纪605.9603543600216ms13min366世纪2.64*1066世纪结论（1）当f(n)为对数函数
12、、幂函数、或它们的乘积时，算法的运行时间是可以接受的，称这些算法是有效算法；当f(n)为指数函数或阶乘函数时，算法的运行时间是不可接受的，称这些算法是无效的算法。（2）随着n值的增大，增长速度各不相同，n足够大时，存在下列关系： 对数函数幂函数指数函数常见函数的增长率 O(1) 常量阶，与n无关 O(log n) log n阶 O(n) n阶 O(n log n) n log n阶 O(n2) 平方阶 O(n3) 立方阶 O(2n) 指数阶 增长率由慢到快 图示见p16图1-7 尽量少用指数阶的算法 说明：教材p17第2行 除特别指明外，均指最坏情况下的时间复杂度6. 空间复杂度（1）存储算法本身所占用的空间（2）算法的输入/输出数据占用的空间（3）算法在运行过程中临时占用的辅助空间 原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。 若所占空间量依赖于特定的输入，按最坏情况来分析。
