ch2-1数据结构_概述

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

1、计算机软件技术基础computerSoftwareTechnique言凯成（askcyen@Gmail.com）中南大学交通运输工程学院1第二章常用数据结构及其运算常用数据结构及其运算第二章2第二章常用数据结构及其运算内容2．1概述2．2线性表2．3栈与队2．5树与二叉树2．6图2．7查找2．8排序3第二章常用数据结构及其运算2.1概述2.1.1数据结构的概念数值型与非数值型数据数值型：整型、实型、布尔型等非数值型：文献检索、金融管理、商业系统等数据处理数据结构研究非数值运算的程序设计问题。数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。如线性关系、层次关系、网状关系等。

2、4第二章常用数据结构及其运算2.1概述数据(data)——是信息的载体，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数值型和非数值型数据两类。数据元素(dataelement)——是数据的基本单位。如数据集合N={1，2，3，4，5}中整数1至5均为数据元素。数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。数据元素有时也称结点或记录。3.基本概念和术语5第二章常用数据结构及其运算2.1概述数据类型——程序设计语言中允许的变量类型基本数据类型（原子类型）：变量值不可分，如整型、实型、字符型等结构类型：变量值可分，

3、如数组、结构体等数据对象(dataobject)——性质相同的数据元素的集合。如大写字母字符的数据对象是集合：C={‘A’，’B’，...，’Z’}。6第二章常用数据结构及其运算2.1概述数据结构(datastructure)——是指同一数据对象中各数据元素间存在的关系。数据结构与算法——程序＝算法＋数据结构算法指解决特定问题的有限运算序列7第二章常用数据结构及其运算2.1概述1.逻辑结构：研究数据元素及其关系的数学特性，即数据元素间的逻辑关系。二元组S=（D，R）D－－数据元素的非空有限集合R－－D上关系的非空有限集合。2.1.2数据的逻辑结构和物理结构8第二章常用数据结构及其运

4、算2.1概述四类基本结构：线性结构（一对一）树形结构（一对多）图形结构（多对多）举例2.1.2数据的逻辑结构和物理结构集合9第二章常用数据结构及其运算例1：linearity=(D,R)，其中D＝{1,2,3,4,5,6,7,8,9,10}R={r}r={<7,2>,<2,1>,<1,6>,<6,10>,<10,8>,<8,4>,<4,5>,<5,3>,<3,9>}例2：Tree=(D,R)，其中D＝{1,2,3,4,5,6,7,8,9,10}R={r}r={<1,2>,<2,3>,<2,4>,<1,5>,<5,6>,<1,7>,<7,8>,<7,9>,<7,10>}10第二章常用数

5、据结构及其运算例4：S=(D,R)，其中D＝{1,2,3,4,5,6}R={r1,r2}r1={<3,2>,<3,5>,<2,1>,<5,4>,<5,6>}r2={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}例3：Graph=(D,R)，其中D＝{1,2,3,4,5};R={r}r={<1,2>,<1,4>,<1,3>,<3,5>,<2,3>}11第二章常用数据结构及其运算2.1概述2.物理结构(存储结构)：是逻辑结构在计算机中的映象，即具体实现。四种基本存储结构：顺序存储结构链式存储结构索引存储结构散列存储结构3.逻辑结构与存储结构的关系－算法的设计取决于选定的逻辑

6、结构，而算法的实现依赖于采用的存储结构。－同一种逻辑结构可采用不同的存储结构。2.1.2数据的逻辑结构和物理结构12第二章常用数据结构及其运算2.1概述2.1.3算法与算法分析一、什么是算法算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。算法的五个特征：有穷性、确定性、可行性、输入、输出算法描述：采用类C语言的形式，有时也用自然语言。注释部分用//或/*...*/表示。13第二章常用数据结构及其运算2.1概述2.1.3算法与算法分析二、算法设计的要求：正确性、健壮性、效率与低存储三、算法评价标准：时间复杂度、空间复杂度一般时间复杂度考虑的较

7、多。一个可执行的算法不一定是一个好算法，算法的分析通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准。度量一个程序的执行时间通常有两种方法：事后统计和事前分析估算着重介绍第二种方法。（算法、问题规模、语言、机器代码质量、机器执行指令的速度）14第二章常用数据结构及其运算2.1概述一、时间复杂度1.频度：指一条语句重复执行的次数。记作：F(n)2.算法的时间度量：T(n)=O(F(n))是问题规模n的某个函数F(n),称为算法的渐进时