资源描述：
《软件技术-----数据结构概述课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章数据结构概述本章基本内容与要求基本内容基本概念、常用术语、抽象数据类型、算法的特征以及算法分析与评价本节重点：基本概念、常用术语，抽象数据类型第一节数据、数据元素、数据类型、抽象数据类型数据结构研究什么？数据结构是一门研究数据组织、存储和运算的一般方法的学科。能输入到计算机中并能被计算机程序处理的符号的集合。整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。A数据结构研究什么？数据结构是一门研究数据组织、存储和运算的一般方法的学科。计算机管理图书问题在图书馆里有各种卡片：有按书名编排的、有按作者编
2、排的、有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间数据结构研究什么？数据结构是一门研究数据组织、存储和运算的一般方法的学科。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如数据结构研究什么？数据结构是一门研究数据组织、存储和运算的一般方法的学科。数据元素在计算机中的表示数据结构研究什么？数据结构是一门研究数据组织、存储和运算的一般方法的学科。对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序)数据是能输入到计算机中并被计算机程序处理的符号的总称。数据元素（DataEl
3、ement）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理，有时也称作元素、结点、顶点、记录等。数据对象（DataObject）是具有相同性质的数据元素的集合，是数据的一个子集。数据类型（DataType）是对在计算机中表示的同一数据对象及在该数据对象上的一组操作的总称。抽象数据类型（AbstractDataType简记为ADT）是一个数据结构以及定义在该结构上一组操作的总称。数据及其概念数据（Data）信息的载体，是对客观事物的符号表示。能输入到计算机中并被计算机程序处理的符号的总称。计算机程序加工的原料。含义广泛
4、：如数、字符、符号、图像、声音等。数据元素（DataElement）是数据的基本单位在计算机中通常作为一个整体进行考虑和处理可能是若干数据项的组合数据元素亦称为结点（node）或记录（record）{1,2,3,4,5,6,7,8,9,10}名词解释数据对象（DataObject）具有相同性质的数据元素的集合是数据的一个子集如：字母字符数据对象为集合C={‘A’，‘B’，···，‘Z’}整数数据对象为集合N={0，±1，±2，···}{1,2,3,4,5,6,7,8,9,10}名词解释数据类型（DataType）是对在计算机中表
5、示的同一数据对象及其在该数据对象上的一组操作的总称即程序设计语言中允许的变量类型。分为：简单数据类型（其值是不可再分的），如整型、实型、布尔型等。结构数据类型（其值是可以再分的），如数组、结构体等。名词解释抽象数据类型ADT（AbstractDataType）是一个数据结构以及定义在该结构上一组操作的总称。名词解释ADT抽象数据类型名{DataObjects:D={…}//定义数据对象DataRelation:R={…}//定义数据关系ElementaryOperation:/*…定义基本操作…*/};//ADT定义结束第二节数
6、据结构的基本概念一、什么是数据结构数据结构（DataStructure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构通常包含以下三个方面的内容：数据的逻辑结构数据的存储结构数据的运算及实现。数据结构数据结构（DataStructure）形式定义：S=（D，R）D：一个数据元素的非空有限集合R：定义在D上的关系的有限集例设有一个数据结构的抽象结构为，S=(D,R)D={1,2,3,4}R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}它的逻辑结构图为：1234例设有一个数据结构的抽
7、象结构为，S=(D,R)D={a1,a2,a3,a4,a5}R={,,,}它的逻辑结构图为：a1a2a3a4a5例设有一个数据结构的抽象结构为，S=(D,R)D={a,b,c,d,e,f,g,h}R={,,,,,,}它的逻辑结构图为：abcdefgh1.数据的逻辑结构是指数据元素之间的逻辑关系研究数据元素及其关系的数学特性,独立于计算机，是数据本身所固有的a集合:元素间为松散的关系。b线性结构:元素间为严
8、格的一对一关系。c树形结构:元素间为严格的一对多关系。d图状结构（或网状结构）:元素间为多对多关系。数据结构是指数据及数据元素之间的关系在计算机内存中的表示。即逻辑结构在计算机中的映像,也就是具体实现。顺序存储方式是在计算机内存储器中开辟一片地址连续的存储单元顺
