《数据结构介绍》PPT课件

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

1、数据结构(DataStructure)任课教师：赵少卡E-MAIL:zska@cernet.edu.cn数计系2012级计算机科学与技术、网络工程专业1课程性质：专业核心基础课教材:严蔚敏、吴伟民.数据结构(C语言版).北京:清华大学出版社,2011.——1981年初稿，使用面最广周学时：4（理论授课）+2（上机实践）考核：平时成绩（作业、考勤）20%+期中成绩20%+期末成绩60%数据结构数据库人工智能软件工程操作系统编译原理算法设计与分析离散数学语言程序设计高等数学2保持课堂安静，头脑清醒，思维

2、活跃课后及时复习巩固认真、独立、按时完成并提交作业多思考多动手，重视上机实践课程要求3数据结构基础数据结构应用数据结构非线性结构线性结构线性表栈队列串数组广义表树二叉树图查找内部排序外部排序文件动态存储管理本课程的内容框架4讲授篇章第1章绪论第7章图第2章线性表第9章查找第3章栈和队列第6章树和二叉树第10章内部排序5证明正确性分析算法程序设计理解问题选择数据结构、算法设计策略问题数学化设计算法第1章绪论问题求解(ProblemSolving)：6计算机求解问题的分类数值计算(科学运算):解方程(组

3、)、函数求值、概率统计等。应用：天气预报(环流模式方程)、结构静力分析（线性代数方程组）、水库大坝的应力计算、预报人口增长等。非数值计算：字符、表格、图像、声音等。7基本概念和术语数据：计算机程序处理的符号的总称，包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。数据元素：数据的基本单位（数据中的一个“个体”），通常作为一个整体进行处理。数据项：数据的具有意义的不可分割的最小单位。一个数据元素可以由若干个数据项构成。数据元素数据项..................福州19

4、93.11福建男张三12101住址出生年月籍贯性别姓名学号8数据对象：性质相同的数据元素的集合。如：整数数据对象N={0,1,2,…}（无限集）字母字符数据对象C={'A','B','C',…'Z'}（有限集）因此：数据元素是数据的一个个体；数据对象是数据的一个子集。9例：{a1,a2,a3,a4,a5,a6}存在次序为：（1）{

5、i=1，2，3，4，5}（2）Row={,,}Col={,,

6、3,a6>}所谓结构就是数据元素之间的关系，即描述数据元素之间的运算与运算规则。数据结构：相互间存在一种或多种特定关系的数据元素的集合。10数据的逻辑结构数据的存储结构（物理结构、映像）数据的运算：查找、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队列树形结构图形结构数据结构的三个方面：集合结构串索引存储散列存储11主要逻辑结构举例集合：其中的数据元素之间除了“属于同一个集合”的关系以外，别无其他关系。线性结构：其中的数据元素之间存在一对一的关系。树型结构：其中的数据元素之间存

7、在一对多的关系。图状结构（网状结构）：其中的数据元素之间存在多对多的关系。12例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表13例2人机对弈问题树……..……..…...…...…...…...14例3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图有连线的节点用不同的颜色标记,表示不能同时通行。要求使用的颜色数尽可能少,以使减少等待时间。15逻辑结构与存储结构逻辑结构:数据元素间的

8、逻辑关系，与数据元素的相对位置无关。存储结构:逻辑结构在计算机存储器中的表示，如：数据的逻辑结构与存储结构密切相关：算法设计逻辑结构算法实现存储结构顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系16元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储结构171536元素21400元素11346元素3∧元素413

9、45h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储结构h18数据类型与抽象数据类型数据类型（DataType）：值的集合以及定义在这个集合上的一组操作。数据类型分类：（1）原子类型：每个数据都无法再分割。（整型、实型、字符型等）（2）结构类型：结构类型中的数据可以分解为若干原子类型或结构类型数据。（数组、记录、结构体、联合体、串、文件等）19抽象数据类型(Abst