《数据结构》PPT课件

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

1、数据结构数学科学学院朱松13901992420QQ:1651418549学科简介数据结构+算法=程序研究对象大量数据，特别是非数值数据的复杂结构及关系，如图像、声音、字符等研究内容数据的逻辑结构数据的存储结构数据的基本运算算法算法的特征算法的描述算法分析及评价课程内容数据结构线性表栈和队列串数组和广义表树和二叉树图基本算法查找排序课程内容树线索二叉树、哈夫曼树图最小生成树、最短路径查找静态查找、动态查找、哈希查找排序插入排序直接插入排序、希尔排序交换排序冒泡排序、快速排序选择排序直接选择排序、堆排序参考书目1.颜辉、付宏主编：实用数据结构教程，20112.殷人昆主编：数据结构，20073

2、.（美）SartajSahni著，汪诗林等译：数据结构、算法与应用，2010数据结构基本概念和术语数据指所有能输入到计算机中并能被计算机程序识别和处理的符号集合数据一般分数值型数据和非数值型数据数值数据：包括整数、实数或复数等。主要用于工程计算、科学计算等。非数值数据：包括字符、文字、图形、图像、语音等。用于情报检索、企业管理、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。数据元素数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以有一个或若干个数据项组成。数据元素也称为结点或记录。数据项数据的具有独立意义的不可分的最小单位，它是对数

3、据的数据元素属性的描述，又称为字段或域。数据结构基本概念和术语数据对象具有相同性质的数据元素的集合，是数据的子集。数据类型是具有相同性质的计算机数据的集合及定义在这个数据集合上的一组操作的总称。原子类型：如果一个数据元素由一个数据项构成，这个数据元素的类型就是这个数据项的数据类型，其值在逻辑上是不可分解的。结构类型：如果一个数据元素由多个不同类型的数据项组成，这个数据元素的类型就是由各数据项类型构成的结构类型。数据结构基本概念和术语抽象数据类型(AbstractDataType)简写为ADT，是一个数据结构以及定义在该结构上的一组操作的总称。数据结构+定义在此数据结构上的一组操作=抽象数

4、据类型抽象数据类型包括数据对象定义、数据关系定义和基本操作定义三部分。三元组表示为(D,S,P)D:数据对象；S：D上的关系集；P：对D的基本操作集。数据结构是相互之间存在一种或多种特定关系的数据元素及定义这些数据元素基本运算的集合。数据结构的研究内容数据的逻辑结构数据集合中各数据元素之间所固有的逻辑关系。对数据元素间逻辑关系的描述称为数据的逻辑结构，在形式上，可以定义为一个二元组：（D，S）D：数据元素的有限集，S：D上关系的有限集。集合结构集合结构中，元素间的次序是随意的线性结构线性结构是数据元素的有限序列，常用的线性结构有线性表、栈、队列和串。树形结构树形结构中，除一个特殊元素称为

5、根，它没有前趋只有后继外，其余元素都有仅有一个前趋，可以有多个后继，又称为层次结构。图形结构图是最一般的数据结构，图中每个元素的前趋和后继的数目都不限。基本结构又可分为线性结构和非线性结构。它独立于计算机。数据结构的研究内容数据的存储结构数据的存储结构是数据的逻辑结构在计算机内部的表示和实现，又称为数据的物理结构，它包括数据元素的表示和关系的表示，和计算机语言无关。顺序存储方法用一组地址连续的存储空间一次存放数据元素，是逻辑上相邻的数据元素存储时物理位置也相邻。特点：存储密度大，存储空间利用率高；是一种随机存储结构；插入和删除操作复杂。数据结构的研究内容数据的存储结构链式存储方法用一组地

6、址任意的存储空间依次存放数据元素，即不要求逻辑上相邻的数据元素在物理存储上也相邻，数据元素之间的相邻关系通过附加指针来体现，通过指针将数据元素串联起来。链式存储方法不仅存储数据元素的值，还存储数据元素之间的关系。特点除存储数据元素本身的信息外，还要存储数据元素之间关系信息，因此与顺序存储结构相比存储密度小，存储空间利用率低；逻辑上相邻的数据元素，物理位置上不一定相邻，是非随机的存储结构；插入和删除操作简单灵活，只需改变指针值即可。索引存储方法、散列存储方法数据结构的研究内容数据的基本运算每一种逻辑结构都有一个运算的集合。这些运算实际上实在数据元素上施加的一系列抽象操作，即指这些操作要求做

7、什么，但无需考虑如何做；以下为一些常见的基本运算。查找：就是在数据结构里查找满足一定条件的数据元素插入：向数据结构中添加新的数据元素删除：把指定的数据元素从数据结构中去掉修改：更改指定数据元素的一个或多个属性值排序：按指定的关键字将数据元素的次序字数据机构中重新排列。算法算法概念算法是解决问题方案准确而完整的描述。它是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。算法特征有穷性：一个算法必须在执行有