《数据结构动画版》PPT课件

《《数据结构动画版》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、什么是数据结构基本概念和术语算法的描述和算法分析简介下一章第一章绪言1946年，第一台电子计算机ENIACShownherearetwowomen“programming”ENIAC.U.S.ArmyPhoto.什么是数据结构系统功能分析建立数学模型抽象算法设计编码调试与测试系统输入/输出数据、功能需求设计合适的数据对象的表示结构解决特定问题的具体步骤的描述程序设计一般流程程序设计：为计算机处理问题编制的一组指令集数据结构：问题的数学模型算法：处理问题的策略什么是数据结构信息结构层次求解策略层次程序=数据结构+算法NiklausW

2、irth:语言层次从问题求解角度上，数据结构和高级程序设计语言（C语言）立足于不同的层面上针对问题时，C语言一般要想该用何种控制结构（分支还是循环）等细节问题；而数据结构主要考虑的问题的描述、信息的结构等宏观问题针对于问题的求解，算法立足于更高的层次:与数据结构相比，它更多地考虑整个问题该用何种策略（思想）求解，而不是其中涉及信息的组织与结构问题的一般求解过程为：分析求解策略＝>设计其中涉及信息的结构＝>用语言加以具体实现什么是数据结构系统功能分析建立数学模型抽象算法设计编码调试与测试程序设计一般流程非数值计算问题数学方程?数值计

3、算问题数值问题例已知：游泳池的长len和宽wide，求面积area◆建模型：问题涉及的对象：游泳池的长len宽wide，面积area；对象之间的关系：area=lenwide◆设计求解问题的方法◆编程main(){intlen,wide,area;scanf(“%d%d%”,&l,&w);area=len*wide;printf(“area=%d”,area);}什么是数据结构登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表例1书目自动检索系统线性表电话号码查询系统学生

4、成绩管理系统职工信息系统等文档管理的数学模型例2人机对奕问题……..……..…...…...…...…...例2人机对奕问题树CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题所有可能通行方向A→BA→CA→DB→AB→CB→DD→AD→BD→CE→AE→BE→CE→D用AB表示A→B，余类推交叉路口的模型图CEDABABACADBABCBDDADBDCEAEBECED算法设计：穷举法：逐一检查所有可能组合，记录最小分组数和对应分组贪心法：一类典型算法，其宗旨是根据当时掌握的信息，尽可能地向得

5、到解的方向推进例3多叉路口交通灯管理问题图CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题图CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题图CEDABABACADBABCBDDADBDCEAEBECED例3多叉路口交通灯管理问题图CEDABABACADBABCBDDADBDCEAEBECED图例3多叉路口交通灯管理问题是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科数据结构定义：数据结构学科的地位•综合性的专业基

6、础课•介于数学、计算机硬件和计算机软件之间的核心课程•不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础•本课程的先修课程：离散数学、C语言(或其他程序设计语言)•本课程后续课程：面向对象程序设计、操作系统、编译原理、数据库系统、人工智能等数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称结点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据对象

7、（dataobject)—性质相同数据元素的集合整数数据对象N={0,1,2,…}基本概念和术语数据元素集合元素间关系集合数据结构（datastructure)—数据元素和数据元素关系的集合Data_Structure={D,R}数据的逻辑结构—只抽象反映数据元素的逻辑关系从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型；与数据元素本身的形式、内容无关；与数据元素的相对位置无关。数据逻辑结构分为：（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个

8、对多个，如树图状结构——多个对多个，如图基本概念和术语数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现存储结构分为：顺序存储结构—借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构—借助指示元素存储地址的指针表示数据元素