数据结构概述.pptVIP

第二章 常用数据结构及其运算 问题 ？ 有A、B两段程序同时运行，在某时刻A的运行速度是B的2倍，因此，A的算法复杂度比B低（即效率高）。 * * 计算机软件技术基础 －－上海大学 通信与信息工程学院 安 平 计算机基础教学课件 学时数：40，其中习题课2学时。 讲授主要内容：第2、3、4章 自学内容：其余各章 课程的主要内容及安排 常用数据结构及其运算 第二章 内 容 2．1 概 述 2．2 线性表 2．3 栈与队 2．5 树与二叉树 2．6 图 2．7 查 找 2．8 排 序 2.1 概 述 2.1.1 数据结构的概念 数值型与非数值型数据 数值型：整型、实型、布尔型等 非数值型：文献检索、金融管理、商业系统 等数据处理 数据结构 研究非数值运算的程序设计问题。 数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。 如线性关系、层次关系、网状关系等。 2.1 概 述 数据(data)——是信息的载体，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数值型和非数值型数据两类。 数据元素(data element)——是数据的基本单位。如数据集合N={ 1，2，3，4，5 }中整数1至5均为数据元素。 ? 数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。 ? 数据元素有时也称结点或记录。 3. 基本概念和术语 2.1 概 述 数据类型——程序设计语言中允许的变量类型 ? 基本数据类型（原子类型）：变量值不可分， 如整型、实型、字符型等 ? 结构类型：变量值可分，如数组、结构体等 数据对象(data object)——性质相同的数据元素的集合。如大写字母字符的数据对象是集合：C={ ‘A’，’B’，...，’Z’ }。 2.1 概 述 数据结构(data structure)——是指同一数据对象中各数据元素间存在的关系。 数据结构与算法—— ? 程序＝算法＋数据结构 算法指解决特定问题的有限运算序列 2.1 概 述 1.逻辑结构：研究数据元素及其关系的数学特性， 即数据元素间的逻辑关系。 二元组 S =（D，R） D－－数据元素的非空有限集合 R－－D上关系的非空有限集合。 2.1.2 数据的逻辑结构和物理结构 2.1 概 述 四类基本结构： 线性结构（一对一） 树形结构（一对多） 图形结构（多对多） 举 例 2.1.2 数据的逻辑结构和物理结构 集合 例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} 例4：S = (D, R)，其中 D ＝ {1,2,3,4,5,6} R = {r1, r2} r 1= {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} 2.1 概 述 2.物理结构(存储结构)：是逻辑结构在计算 机中的映象，即具体实现。 四种基本存储结构：顺序存储结构 链式存储结构 索引存储结构 散列存储结构 3.逻辑结构与存储结构的关系 －算法的设计取决于选定的逻辑结构，而算 法的实现依赖于采用的存储结构。 －同一种逻辑结构可采用不同的存储结构。 2.1.2 数据的逻辑结构和物理结构 2.1 概 述 2.1.3 算法与算法分析 一、什么是算法 ? 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。 ? 算法的五个特征：有穷性、确定性、可行性、 输入、输出 ? 算法描述：采用类C语言的形式，有时也用自然语言。注释部分用//或/*...*/表示。 2.1 概 述 2.1.3 算法与算法分析 二、算法设计的要求：正确性、健壮性、效率与低存储 三、算法评价标准：时间复杂