1、 数据结构（数据结构（c c语言版）语言版）程序设计犹如写英语作文，每个人都知道语法程序设计犹如写英语作文，每个人都知道语法句型，但作文质量确有好有坏！句型，但作文质量确有好有坏！如何写出好程序如何写出好程序？u找出解决问题适合的方法来设计程序的流程找出解决问题适合的方法来设计程序的流程u采用最简洁的数据的结构来表示程序中的数采用最简洁的数据的结构来表示程序中的数据和变量据和变量问题举例问题举例n如何设计程序的存储结构和算法才能如何设计程序的存储结构和算法才能以最快的速度查询出学校内某个学生以最快的速度查询出学校内某个学生的成绩单？的成绩单？学习要求学习要求n及时复习和预习，及时理解知识及时复
2、习和预习，及时理解知识n活跃的思维能力和严格的推理过程活跃的思维能力和严格的推理过程n注重数据结构和算法的注重数据结构和算法的实现方法或流实现方法或流程程，掌握部分程序的代码实现过程，掌握部分程序的代码实现过程n大量的手工绘图大量的手工绘图流程图流程图良好的良好的C+语言基础语言基础nC+语言语言+数据结构数据结构=问题的解决问题的解决n数组、结构数组、结构n指针指针n控制语句控制语句循环、条件判断、顺序循环、条件判断、顺序n最基本的输入输出操作最基本的输入输出操作良好的抽象思维能力良好的抽象思维能力n能够针对算法流程图逐一阐述出算法的能够针对算法流程图逐一阐述出算法的完整实现流程完整实现流程
3、关于流程图的介绍关于流程图的介绍n每个流程图都有一个开始标记每个流程图都有一个开始标记n每个流程图至少有一个结束标记每个流程图至少有一个结束标记n程序模块的确定程序模块的确定顺序语句顺序语句n条件分支的画法条件分支的画法n如何用如何用“条件分支条件分支”来实现来实现“循环循环”的的逻辑逻辑n推荐画图工具推荐画图工具VISIO第一章 绪论内容概述n数据结构的相关概念n算法及算法复杂度分析什么是数据结构n计算机加工处理的对象由纯粹的数值发展计算机加工处理的对象由纯粹的数值发展到字符、图表、图象等各种具有一定结构到字符、图表、图象等各种具有一定结构的数据。的数据。n用计算机解决一个具体问题的时候一般
4、有用计算机解决一个具体问题的时候一般有几个步骤几个步骤：v从具体问题抽象出一个数学模型从具体问题抽象出一个数学模型v设计解决这个模型的算法（找到处理的对象设计解决这个模型的算法（找到处理的对象的特性和对象之间的关系）的特性和对象之间的关系）v编程、测试、得到最终解编程、测试、得到最终解 基本概念和术语（一）数据：数据：对客观事物的符号表示，是所有被计算对客观事物的符号表示，是所有被计算机程序处理的符号总称（数字、图象、声音、机程序处理的符号总称（数字、图象、声音、字符串）。字符串）。数据元素数据元素 ：数据的基本单位。由多个数据项数据的基本单位。由多个数据项组成，数据项是数据的不可分割的最小单
5、位。组成，数据项是数据的不可分割的最小单位。数据元素可以是单一数据，也可以是一条记录数据元素可以是单一数据，也可以是一条记录数据对象：数据对象：性质相同的数据元素的集合，是性质相同的数据元素的集合，是数据的一个子集。（整数数据集合、学籍表）数据的一个子集。（整数数据集合、学籍表）基本概念和术语（二）数据结构：数据结构：结构是指数据间的关系。结构是指数据间的关系。数据结构是指是相互之间存在数据结构是指是相互之间存在某种特定关系某种特定关系的的数据元素的集合。（模型）数据元素的集合。（模型）数据结构包括三个方面的内容数据结构包括三个方面的内容数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构
6、数据的运算数据的运算一个算法的设计取决于选定的逻辑结构，一个算法的设计取决于选定的逻辑结构，算法的实现依赖于采用的存储结构算法的实现依赖于采用的存储结构图书馆查询系统线性关系(一对一)人机对羿树状关系(一对多)交通灯问题图状（网状）关系(多对多)数据结构就是一门研究数据结构就是一门研究非数值非数值计算的程序设计计算的程序设计问题中计算机的问题中计算机的操作对象以及他们之间的关系操作对象以及他们之间的关系和操作和操作的学科。是计算机专业或相关专业的一的学科。是计算机专业或相关专业的一门基础学科门基础学科。001001高等数学高等数学樊映川樊映川S01S01002002 理论力学理论力学罗远祥罗远
7、祥L01L01 003003 高等数学高等数学华罗庚华罗庚S01S01004004 线性代数线性代数栾汝书栾汝书S02S02 高等数学高等数学 001,003001,003理论力学理论力学 002002线性代数线性代数 004004樊映川樊映川001,001,华罗庚华罗庚003003栾汝书栾汝书004004L L002002S S001,00001,003 3 XXXXXXXXXXXXXXXXX如何对博弈问题进行抽象？如何对博弈问题进行抽象？12 34512354BACDE如何对交通线路图进行抽象？如何对交通线路图进行抽象？数据结构的形式化定义：数据结构的形式化定义：数据结构是一个二元组数据结
8、构是一个二元组:Data_Structure Data_Structure（D D，R R）其中，其中，D D是数据元素的有限集，是数据元素的有限集，R R是是D D上上关系的有限集关系的有限集。学学校校系系处处研研究究机机构构教教研研室室实实验验室室D=D=学校，系，处，研究机学校，系，处，研究机构，教研室，实验室构，教研室，实验室 R=R=学校，系，学校，系，,数据类型的表示和实现数据类型：数据类型：一个值的集合和定义在这个一个值的集合和定义在这个值集上的一组操作的总称。一个高级程值集上的一组操作的总称。一个高级程序语言的数据类型可分为：序语言的数据类型可分为：原子型：不可分解原子型：不可
9、分解结构类型：由若干分量组成结构类型：由若干分量组成抽象数据类型（抽象数据类型（ADT）:是指一个数学模是指一个数学模型以及定义在该模型上的一组操作。型以及定义在该模型上的一组操作。（与逻辑特性有关，与存储、实现无关）（与逻辑特性有关，与存储、实现无关）算法和算法分析（一）算法的算法的5 5个重要特性：个重要特性：程序程序=算法算法+数据结构数据结构评价一个算法的原则：评价一个算法的原则：正确性：要求正确性：要求P14可读性可读性健壮性：当输入非法时，能适当做出反映或进健壮性：当输入非法时，能适当做出反映或进行处理行处理效率与低存储量需求效率与低存储量需求算法的描述n算法的描述可以是自然语言、
10、伪语言、算法的描述可以是自然语言、伪语言、框图、类语言完成框图、类语言完成条列式：以文字形式来描述步骤条列式：以文字形式来描述步骤流程图：以图形符号来描述解决问题的方法流程图：以图形符号来描述解决问题的方法（仅适合于小问题）（仅适合于小问题）伪码：夹杂程序语法和自然语言的形式描述解伪码：夹杂程序语法和自然语言的形式描述解决问题的方法。决问题的方法。程序语句：程序语法形式描述解决问题的方法程序语句：程序语法形式描述解决问题的方法算法的时间复杂度分析算法执行时间大致上等于其所有语句执行时间算法执行时间大致上等于其所有语句执行时间的总和，的总和，对于语句的执行时间是指该条语句对于语句的执行时间是指该
11、条语句的执行次数和执行一次所需时间的乘积。的执行次数和执行一次所需时间的乘积。语句频度：语句频度：该语句在一个算法中重复执行的次该语句在一个算法中重复执行的次数数 最佳状况（下限）、最坏状况（上限）最佳状况（下限）、最坏状况（上限）算法的时间复杂度：算法的时间复杂度：指程序运行从开始到结束指程序运行从开始到结束所需要的时间。也是算法中语句总的执行次数所需要的时间。也是算法中语句总的执行次数T(n)T(n)。随随n n的变化确定数量级，用的变化确定数量级，用“OO”来表示来表示数量级，记作：数量级，记作：T(n)=O(f(n)T(n)=O(f(n)x=x+1 x=x+1；其时间复杂度为其时间复杂
12、度为O(1)O(1)，算法的时间复杂性与输算法的时间复杂性与输入规模入规模n n无关我们称之为无关我们称之为常量阶常量阶；for(i=1;i=n;i+)for(i=1;i=n;i+)x=x+1;x=x+1;其时间复杂度为其时间复杂度为O(n)O(n)，我们称之为我们称之为线性阶线性阶；for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=n;j+)for(j=1;j=n;j+)x=x+1;x=x+1;其时间复杂度为其时间复杂度为O(nO(n2 2),),我们称之为我们称之为平方阶平方阶。for(i=1;i=n;for(i=1;i=n;i i*2 2)for(j=1;j
13、=n;j+)for(j=1;j=n;j+)x=x+1;x=x+1;其时间复杂度为其时间复杂度为O(nO(n*log n),log n),我们称之为我们称之为线性对数阶线性对数阶。2一般地，随一般地，随n n的增大，的增大，T(n)T(n)的增长较慢的算法为的增长较慢的算法为最优的算法。最优的算法。对于足够大的对于足够大的n n，常用的时间复杂性存在以下顺常用的时间复杂性存在以下顺序：序：O(1)O(log n)O(n)O(n*log n)O(n2)O(n3)O(2n)O(3n)O(n!)22程序步确定方法程序步确定方法关于复杂度数量级的表示方法关于复杂度数量级的表示方法nO(n)C+O(n)n
14、O(n)C*O(n)nO(n)O(n)*O(n)n顺序语句顺序语句 Cn一重循环一重循环 nn多重循环多重循环 m*n、m*n*l、m*n*l*t n条件判断条件判断 Max(u,v)（u和和v也可能是常数）也可能是常数）例：例：For(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;n次n次n次整个算法的执行时间与该基本操作（乘法）重整个算法的执行时间与该基本操作（乘法）重复执行的次数复执行的次数n3成正比，记作成正比，记作T(n)=O(n3)对于一个多项式的时间复杂度，只记它最高的幂次。对于一个多项式的时间复杂度，只记
15、它最高的幂次。算法平均时间复杂度：算法平均时间复杂度：所有可能的输入所有可能的输入实例都以等概率的情况出现时，算法的实例都以等概率的情况出现时，算法的预期运行时间。预期运行时间。算法最坏时间复杂度：算法最坏时间复杂度：算法在任何输入算法在任何输入实例上运行时间的上界。实例上运行时间的上界。n算法的时间复杂度不仅仅依赖于问题的算法的时间复杂度不仅仅依赖于问题的规模，还取决于输入实例的初始状态规模，还取决于输入实例的初始状态 e.g 折半查找法折半查找法 最好情况：最好情况：1（x=n/2）最坏情况：最坏情况：log n 一般来说，在普通应用场合中使用折半查找法一般来说，在普通应用场合中使用折半查
16、找法时，以最坏情况时的复杂度作为该算法的复时，以最坏情况时的复杂度作为该算法的复杂度杂度2算法的空间复杂度分析空间复杂度是指程序运行从开始到结空间复杂度是指程序运行从开始到结束时所需的束时所需的最大最大存储量。存储量。(自身运行所需自身运行所需的内存单元、辅助内存单元）的内存单元、辅助内存单元）记为记为S(n)=O(f(n)思考：思考：v某程序的时间复杂度为某程序的时间复杂度为(14n+n*lgn+n2+37），其数量级表示为其数量级表示为O（？）（？）v有一个程序片段：有一个程序片段：X=1000;While(x!=5)X=x/10;时间复杂度为时间复杂度为O（n）对不对？）对不对？O（lg
17、(n)）呢？）呢？数据的逻辑结构可以看作是从具体问题抽象出数据的逻辑结构可以看作是从具体问题抽象出来的模型，描述操作对象之间的关系，它与数来的模型，描述操作对象之间的关系，它与数据的存储方式、位置无关。据的存储方式、位置无关。研究表明：元素之间必是下列四种关系之一：研究表明：元素之间必是下列四种关系之一：集合集合线性结构线性结构(表、栈、队列）表、栈、队列）树树图或网状图或网状数据的存储结构：数据元素及其关系在计数据的存储结构：数据元素及其关系在计算机存储器内的表示。算机存储器内的表示。顺序存储：顺序存储：借助存储器中的位置来表示数借助存储器中的位置来表示数据元素之间的关系。据元素之间的关系。链式存储：链式存储：对逻辑上相邻的元素不要求其对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示。设的指针字段来表示。索引存储：索引存储：建立附加索引表来标识结点地建立附加索引表来标识结点地址址。逻辑结构与存储结构的关系：逻辑结构与存储结构的关系：v存储结构是逻辑关系的映象与元素本身存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象。的映象。逻辑结构是数据结构的抽象。v存储结构是逻辑结构的实现，两者综合存储结构是逻辑结构的实现，两者综合起来建立了数据元素之间的结构关系。起来建立了数据元素之间的结构关系。
