软件技术基础课件-第3章 算法与数据结构(一).ppt

《软件技术基础课件-第3章 算法与数据结构(一).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、软件技术基础电子教案第3章算法与数据结构1第3章内容摘要3.1数据结构概述3.2算法的描述和分析3.3线性表3.4树和二叉树3.5图3.6查找与排序《软件技术基础》电子教案23.1数据结构概述计算机=软件+硬件软件=程序+文档（软件工程的观点）程序=算法+数据结构（NiklausWirth，图灵奖获得者)程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型《软件技术基础》电子教案3‘数据结构’=‘计算机程序设计技巧'(Kunth，图灵奖获得者)熟悉C语言≠写出‘好’的程序学习数据结

2、构=编写高水平的程序《数据结构》：计算机类专业8大核心课程之一注：教育部计算机教指委认定的8大核心课程：计算机语言、数据结构、离散数学、计算机网络、计算机组成原理、操作系统、数据库、软件工程图灵奖：1966年设置，每年奖励1-2名杰出的计算机科学家，被誉为计算机领域的诺贝尔奖《软件技术基础》电子教案43.1.1什么是数据结构早期的计算机主要用于数值计算现在的计算机更多地是用于非数值数据处理（字符、表格、图像）对非数值数据的处理：分析数据的逻辑特征→抽象出合适的数学模型→合理地存储到计算机→设计出算法→编写出程序《

3、软件技术基础》电子教案5首先要构造学生信息表，表3-1表达出学生数据的逻辑关系，它就是一个数学模型，这张表如何构造、在计算机内如何存储将直接影响查找算法的设计以及算法的效率表3-1例1学生信息查询系统《软件技术基础》电子教案6学生信息表的特点每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构，现实中这类关系的数据有很多。通常的操作插入某个学生的信息删除某个学生的信息更新某个学生的信息按条件查找某个学生的信息《软件技术基础

4、》电子教案7中国象棋、国际象棋的人机大战，核心技术是人编写的对弈程序。对弈步骤和过程可以用树型结构表达出来（数学模型）例2人机对弈图3-1井子棋对弈树树形应用《软件技术基础》电子教案8树型结构的特点所处理的数据之间具有层次关系，这是我们所说的树形结构,还有如：基因遗传关系等，它是一种非线性结构。对它的操作有：建立树形结构、存储树、访问树中的每个结点《软件技术基础》电子教案9例3哥尼斯堡七桥问题问题：怎样才能够从某块陆地出发，经过每座桥一次且仅一次最后回到出发点。BADC《软件技术基础》电子教案10图结构的特点计算

5、机处理的对象是图元素间的关系是复杂的图形或网状关系施加于对象上的操作有查询、插入、删除等现实中，这类关系的数据非常多。如：网络规划、交通、通讯规划等，这里典型的非线性关系。《软件技术基础》电子教案11数据结构研究的内容由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构

6、的内容包括三个层次的五个“要素”，如下图所示：《软件技术基础》电子教案12数据结构课程内容体系方面层次数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价不同结构的比较及算法分析《软件技术基础》电子教案133.1.2基本概念和术语数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位（记录、结构体）数据项组成数据元素的有特定意义的最小的不可分割的单位。《软件技术基础》电子教案143.1.2基本概念和

7、术语数据结构中讨论的最小单位是数据项;数据元素是数据项的集合例如：运动员（数据元素）其中出生日期中年　月　日是组合项单位。姓名俱乐部名称出生日期参加日期职务《软件技术基础》电子教案15数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的形式定义数据结构是一个二元组:Data_Structures=(D,R)其中:D是数据元素的有限集，R是D上关系的有限集。数据结构分为四大类:表:元素是线性关系(连接)图:元素间是非线性关系(连接)树:元素间是非线性关系，连接不得有回路文件:记录的序列数据结构的定义

8、《软件技术基础》电子教案16数据结构的三要素数据的逻辑结构数据的存储结构对数据的操作（运算算法）数据结构的定义《软件技术基础》电子教案17数据结构的定义逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构，可以分为：线性结构和非线性结构存储结构（物理结构）是指数据结构在存储器中的具体实现，包括顺序存储结构，链式存储结构，索引存储结构，散列存储