《数据结构》课件第一章

数据结构（c语言版）程序设计犹如写英语作文，每个人都知道语法句型，但作文质量确有好有坏！如何写出好程序？找出解决问题适合的方法来设计程序的流程采用最简洁的数据的结构来表示程序中的数据和变量问题举例如何设计程序的存储结构和算法才能以最快的速度查询出学校内某个学生的成绩单？学习要求及时复习和预习，及时理解知识活跃的思维能力和严格的推理过程注重数据结构和算法的实现方法或流程，掌握部分程序的代码实现过程大量的手工绘图——流程图良好的C++语言基础

C++语言+数据结构=问题的解决数组、结构指针控制语句——循环、条件判断、顺序最基本的输入输出操作良好的抽象思维能力能够针对算法流程图逐一阐述出算法的完整实现流程关于流程图的介绍每个流程图都有一个开始标记每个流程图至少有一个结束标记程序模块的确定——顺序语句条件分支的画法如何用“条件分支”来实现“循环”的逻辑推荐画图工具——VISIO第一章绪论内容概述数据结构的相关概念算法及算法复杂度分析什么是数据结构计算机加工处理的对象由纯粹的数值发展到字符、图表、图象等各种具有一定结构的数据。用计算机解决一个具体问题的时候一般有几个步骤：从具体问题抽象出一个数学模型设计解决这个模型的算法（找到处理的对象的特性和对象之间的关系）编程、测试、得到最终解基本概念和术语（一）数据：对客观事物的符号表示，是所有被计算机程序处理的符号总称（数字、图象、声音、字符串）。数据元素

：数据的基本单位。由多个数据项组成，数据项是数据的不可分割的最小单位。数据元素可以是单一数据，也可以是一条记录数据对象：性质相同的数据元素的集合，是数据的一个子集。（整数数据集合、学籍表）基本概念和术语（二）数据结构：结构是指数据间的关系。数据结构是指是相互之间存在某种特定关系的数据元素的集合。（模型）数据结构包括三个方面的内容数据的逻辑结构数据的存储结构数据的运算一个算法的设计取决于选定的逻辑结构，算法的实现依赖于采用的存储结构图书馆查询系统线性关系(一对一)人机对羿树状关系(一对多)交通灯问题图状（网状）关系(多对多)数据结构就是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科。是计算机专业或相关专业的一门基础学科。001高等数学樊映川S01…002理论力学罗远祥L01…003高等数学华罗庚S01…004线性代数栾汝书S02………………高等数学001,003…理论力学002…线性代数004………樊映川001,…华罗庚003…栾汝书004………L002…S001,003………XXXXXXXXXXXXXXXXX如何对博弈问题进行抽象？1234512354BACDE如何对交通线路图进行抽象？数据结构的形式化定义：数据结构是一个二元组:Data_Structure＝（D，R）

其中，D是数据元素的有限集，R是D上关系的有限集。

D={学校，系，处，研究机构，教研室，实验室}R={<学校，系〉，<学校,处>,<学校，研究机构>,<系,教研室>,<系,实验室>}数据类型的表示和实现数据类型：一个值的集合和定义在这个值集上的一组操作的总称。一个高级程序语言的数据类型可分为：原子型：不可分解结构类型：由若干分量组成抽象数据类型（ADT）:是指一个数学模型以及定义在该模型上的一组操作。（与逻辑特性有关，与存储、实现无关）算法和算法分析（一）算法的5个重要特性：程序=算法+数据结构评价一个算法的原则：正确性：要求P14可读性健壮性：当输入非法时，能适当做出反映或进行处理效率与低存储量需求算法的描述算法的描述可以是自然语言、伪语言、框图、类语言完成条列式：以文字形式来描述步骤流程图：以图形符号来描述解决问题的方法（仅适合于小问题）伪码：夹杂程序语法和自然语言的形式描述解决问题的方法。程序语句：程序语法形式描述解决问题的方法算法的时间复杂度分析算法执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。语句频度：该语句在一个算法中重复执行的次数

最佳状况（下限）、最坏状况（上限）算法的时间复杂度：指程序运行从开始到结束所需要的时间。也是算法中语句总的执行次数T(n)。随n的变化确定数量级，用“O”来表示数量级，记作：T(n)=O(f(n))x=x+1；其时间复杂度为O(1)，算法的时间复杂性与输入规模n无关我们称之为常量阶；

for(i=1;i<=n;i++)x=x+1;其时间复杂度为O(n)，我们称之为线性阶；for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;

其时间复杂度为O(n2),我们称之为平方阶。for(i=1;i<=n;i*2)for(j=1;j<=n;j++)x=x+1;

其时间复杂度为O(n*logn),我们称之为线性对数阶。2一般地，随n的增大，T(n)的增长较慢的算法为最优的算法。对于足够大的n，常用的时间复杂性存在以下顺序：O(1)<O(logn)<O(n)<O(n*logn)<O(n2)<

O(n3)…<O(2n)<O(3n)<…<O(n!)22程序步确定方法关于复杂度数量级的表示方法O(n)C+O(n)O(n)C*O(n)O(n)O(n)*O(n)顺序语句C一重循环n多重循环m*n、m*n*l、m*n*l*t

……条件判断Max(u,v)（u和v也可能是常数）例：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]+=a[i][k]*b[k][j];}n次n次n次整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，记作T(n)=O(n3)对于一个多项式的时间复杂度，只记它最高的幂次。算法平均时间复杂度：所有可能的输入实例都以等概率的情况出现时，算法的预期运行时间。算法最坏时间复杂度：算法在任何输入实例上运行时间的上界。

算法的时间复杂度不仅仅依赖于问题的规模，还取决于输入实例的初始状态

e.g折半查找法最好情况：1（x=n/2）最坏情况：logn

一般来说，在普通应用场合中使用折半查找法时，以最坏情况时的复杂度作为该算法的复杂度2算法的空间复杂度分析空间复杂度是指程序运行从开始到结束时所需的最大存储量。(自身运行所需的内存单元、辅助内存单元）记为S(n)=O(f(n))思考：某程序的时间复杂度为(14n+n*lgn+n2+37），其数量级表示为O（？）有一个程序片段：……X=1000;While(x!=5)X=x/10;……时间复杂度为O（n）对不对？

O（lg(n)）呢？数据的逻辑结构可以看作是从具体问题抽象出来的模型，描述操作对象之间的关系，它与数据的存储方式、位置无关。研究表明：元素之间必是下列四种关系之一：集合线性结构(表、栈、队列）树图或网状数据的存储结构：数据元素及其关系在计算机存储器内的