《数据结构概述》PPT课件

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

1、数据结构谢陆宁xieluning@shift.edu.cn67703850成绩如何评定？平时成绩：40%考勤：10%作业：30%期末考试：60%教材和参考书黄国瑜，数据结构（C语言版），清华大学出版社严蔚敏，数据结构，清华大学出版社张瑞军，数据结构（C语言描述），清华大学出版社数据结构基础（C语言版)，[美]EllisHorowitz，清华大学出版社第一章数据结构的基本概念1.1何谓数据结构1.2算法1.3程序结构化设计风格1.4程序分析的方法1.5时间复杂度分析1.6渐进式表示法1.1数据结构计算机解决问题的步骤：分析问题，建立数学模

2、型：界定问题的输入输出边界，抽取问题的实质，对问题进行抽象，形成相应的数学模型。确定数据结构：设计合适的数据结构对解决问题所需的数据及数据之间的关系进行存储，描述出其相应的逻辑结构及存储结构。算法设计：根据问题要求和数据结构的特点来选择和设计算法，同时要考虑算法的效率和占用内存空间。编程实现1.1数据结构例子：新生入学注册学号的编码规则。采用入学年份+学院编号+专业编号+流水号的编码方式学号姓名学院编号专业编号性别出生年月200805165001赵飞霞5165女1988.5………………学院编号学院名称5管理学院……专业编号专业名称165

3、财务管理……1.1数据结构确定数据结构。设计适当的数据格式来存储和表达这些信息算法设计。主要涉及学生信息的增加、删除、修改、查询等操作程序设计1.1数据结构数据结构这门学科主要完成以下工作：数据集合中个数据元素之间的逻辑关系，即数据的逻辑结构在对数据集合进行访问和处理时，个数据元素在计算机物理介质中的实际存储，即数据的物理结构对数据集合中个数据元素的各种运算1.1数据结构数据：对客观事物的符号表示，它描述客观事物的数值、字符等所有输入到计算机中并能被计算机所接受和处理的符号的集合数据类型：程序语言中变量所能表示并存储的数据种类在C语言中

4、数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义1.1数据结构数据对象（数据实体）：是性质相同的数据元素的集合。是数据的一个子集。整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}数据结构：数据实体中元素之间的关系，包括数据的表示法（逻辑结构和存储结构）和运算数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。1.1数据结构数据的逻辑结构和物理结构数据之间的

5、相互关系称为逻辑结构。通常分为四类基本结构：一、集合：结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构：结构中的数据元素之间存在一对一的关系。三、树状结构：结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构：结构中的数据元素之间存在多对多的关系。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。1.2算法数据结构与算法是有紧密联系的。对于某一问题，如果使用计算机求解，其本质上是对某一种或几种数据结构施加一些运算。程序=数据结构+算法算法是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指

6、令表示一个或多个操作。1.2算法算法是指为了完成某项特定工作所设计出的一连串用来说明工作是如何被完成的步骤。算法必须满足下列几个条件：输入：有零个或多个输入数据输出：具有一个以上的结果输出定义明确：每一个步骤的语句必须很明确，不允许有二义性有限性：对所有情形都能在执行有限步之后结束有效性：每一个步骤必须是基本的、可执行的（feasible）指令（即使是用纸和笔也可以完成计算）1.2算法用来写算法的方式：条列式的步骤流程图：以图形符号来描述解决问题的方法。伪码：以夹杂程序语法和自然语言的形式来描述解决问题的方法。程序语句1.2算法算法设计

7、的要求正确性：算法应满足具体问题的需求，对任何合法的输入，算法都能给出正确的输出。可读性：算法应该好读。以有利于阅读者对程序的理解。健状性：算法应具有容错处理。当输入非法数据时，算法能适当的作出反应，并做相应的异常处理，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.3程序结构化与设计风格程序设计是设计和编制程序的全过程。程序，设计发展的历史,可以分为三个不同的时期：20世纪50年代，程序都是用指令代码或汇编语言来编写的。评论程序

8、好坏的标准是能否做到指令条数少，存储单元省，执行速度快。20世纪60年代，高级语言蓬勃发展，出现了一系列不同风格、为不同对象服务的程序设计语言。但程序设计方法并无实质性进展。20世纪70年代，程序设计观念发