哈工大-数据结构课件-严蔚敏《数据结构》(C语言版).ppt

《哈工大-数据结构课件-严蔚敏《数据结构》(C语言版).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论本章重点难点重点:①数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系；②抽象数据类型(ADT)的概念和实现方法，算法的时间复杂性和空间复杂性分析。难点:①抽象数据类型(ADT)的概念和实现方法；②算法的时间复杂性和空间复杂性分析。1.1数据结构及其讨论范畴1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析第1章绪论第1章绪论1.1数据结构及其讨论范畴算法+数据结构=程序设计处理问题的策略给

2、出问题的数学模型编制出用计算机处理问题的指令问题构建数学模型算法实现①在解决问题时可能遇到的典型的逻辑结构（数据结构）②逻辑结构的存储映象（存储实现）③数据结构的相关操作及其实现。数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现"的学科。第1章绪论1.1数据结构及其讨论范畴例1求n个整数中的最大值。例2交叉路口的红绿灯管理。例3煤气管道的铺设问题。……说明：例子中的数学模型正是数据结构要讨论的问题。第1章绪论1.1数据结构及其讨论范畴例计算机的发展数据处理的种类数据数值数据

3、非数值数据数(整数,实数)字符字符串文字图形图象声音对客观对象的符号表示程序原始数据结果数据第1章绪论1.1数据结构及其讨论范畴软件硬件应用领域数值问题与非数值问题①数值问题例1已知：游泳池的长len和宽wide，求面积area设计求解问题的方法编程建模型：问题涉及的对象：游泳池的长len宽wide，面积area；对象之间的关系：area=lenwide第1章绪论1.1数据结构及其讨论范畴学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82/06/01广州56100计算机200102石磊男83/12/21

4、汕头51200计算机100202李梅女83/02/23阳江53200计算机200301马耀先男82/07/12广州50900计算机3②非数值问题已知某级学生情况,要求分班按入学成绩排列顺序。说明：在此类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,该数学模型称为线性模型。第1章绪论1.1数据结构及其讨论范畴例②非数值问题第1章绪论1.1数据结构及其讨论范畴下棋程序--国际象棋：每次需要考虑的合乎规则的着法平均只有35步回合，计算机预先分析7至8个回合的着法。若设为7个回合，则有超过1亿亿亿个

5、不同的变化，经简化后，仍有500亿至600亿个变化。多分析一步，增加18亿个变化。根据计算机“深蓝”的速度，平均5分钟走一步。算法：对弈的规则和策略棋盘及棋盘的格局模型：根据计算机“深蓝”的速度例迷宫问题：在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树”。入口出口第1章绪论1.1数据结构及其讨论范畴例第1章绪论1.1数据结构及其讨论范畴对每种数据结构，主要讨论如下三方面的问题：①数据的逻辑结构数据元素之间的逻辑关

6、系，是具体关系的抽象。②数据的存储结构(物理结构)：数据元素及其关系在计算机内存中的表示；③数据的运算即对数据施加的操作。定义在数据的逻辑结构上的抽象的操作。1.1数据结构及其讨论范畴1.2基本概念和术语1.3数据结构的分类及表示1.4抽象数据类型的表示与实现1.5算法和算法分析第一章绪论数据：是信息的载体，能够被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。数据元素：数据的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。数据项:相当于记录的“域”或字段,是数据不可分割的最小

7、单位。如学号。数据对象：性质相同的数据元素的集合。如所有班名相同的记录集合。第1章绪论1.2基本概念和术语数据结构类型树图第1章绪论1.2基本概念和术语数据结构是数据之间的相互关系，即数据的组织形式。线性表栈队列串数组广义表数据结构线性结构非线性结构①线性结构：除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继；②非线性结构：其逻辑特征是一个结点可能有多个直接前驱和直接后继；第1章绪论1.2基本概念和术语数据的逻辑结构学号姓名专业政治面藐001王洪计算机党员002孙文计算机团员003谢军

8、计算机团员004李辉计算机团员005沈祥福计算机党员006余斌计算机团员007巩力计算机团员008孔令辉计算机团员001003002004006005008007学生间学号顺序关系是一种线性结构关系第1章绪论学生基本情况登记表，记录了每个学生的学号、姓名、专业、政治、面貌，表中的记录是按学生的学号顺序排列的。1.2基