第1章 简介与算法时间复杂性

《第1章 简介与算法时间复杂性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构刘士军Lsj@sdu.edu.cn山东大学计算机学院学习本课的目的？用数字计算机解决任何应用问题都离不开数据表示和数据处理。而数据表示和数据处理的核心问题之一就是数据结构及其操作的实现。算法设计提供了使用计算机解决问题的基本思维方式。算法分析是关于算法评价的科学方法。2讲述内容数据结构与算法分析概论11线性结构11栈和队列11数组和广义表1树结构22图结构23搜索24排序253第一章绪论1.1数据结构讨论的范畴NiklausWirthAlgorithm+DataStructures=Progr

2、ams程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型例如:数值计算的程序设计问题结构静力分析计算─━线性代数方程组全球天气预报─━环流模式方程非数值计算的程序设计问题5例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表6例2人机对奕问题树……..……..…...…...…...…...7例3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图8数据结构定义

3、:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科9数据—所有能被输入到计算机中，且被计算机处理的符号的集合是计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式数据元素—数据的基本单位，也称节点或记录数据项—有独立含义的数据最小单位数据结构—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构集合——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多

4、个对多个，如图1.2基本概念和术语10数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计逻辑结构算法实现存储结构存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系1.2基本概念和术语11元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=

5、Lo+（i-1)*m顺序存储1.2基本概念和术语121536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h1.2基本概念和术语13数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用

6、typedef自己定义数据类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;1.2基本概念和术语14抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型数据结构+定义在此数据结构上的一组操作=抽象数据类型抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作

7、集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名15数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构研究的三个方面16算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性—1.3算法的描述和算法分析简介17算法的五个特性1．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每

8、个步骤都能在有限时间内完成；2．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5．有输出它是一组与“输入”与确定关系