第七讲：数据结构31.ppt

数据结构 寿光现代中学 王桐林 程序 数据结构＋算法 主要学习内容 第一章、 数据结构概述 1、基本概念 2、逻辑结构与物理结构 3、顺序存储与链式存储 第二章、线性结构 线性表、栈、队列、数组 第三章、非线性结构 树与二叉树 第一章 数据结构概述 一、数据结构的基本概念和术语 1.数据：对客观事物的符号表示，在计算机中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包括文字、符号、数字、图像、声音等。 2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项：数据元素的组成部分。 4.数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构（从具体问题抽象出来的数学模型）、存储结构（逻辑结构在计算机存储器里的实现）、数据运算（检索、插入、删除、更新、排序等）。 二、数据的逻辑结构和存储结构（物理结构） 1.数据的逻辑结构：数据元素之间原本存在的逻辑关系，称为数据的逻辑结构。它只是抽象地反映数据元素之间的关系。 2.四种基本的数据结构（集合、线性结构、树形结构、图状结构）。 3.数据的存储结构：数据的逻辑结构在计算机中的表示称为数据的存储结构，又称物理结构。为将逻辑结构全面正确地在计算机中表示出来，存储结构应包括数据元素自身的值和数据元素之间的关系两个方面。通常将数据元素在计算机中的表示称为结点，而将组成数据元素的数据项在计算机中的表示称为数据域。 4.两种基本的存储方法 （1）顺序存储方法（数组）。 顺序存储结构是把数据元素存储在一段连续的存储单元里，结点之间的关系由存储单元的邻接关系来直接或间接地反映。 顺序存储结构的主要特点是：结点中只有自身信息域，没有连接信息域，因此存储密度大，存储空间利用率高；存储空间是连续的，因而可以通过计算机直接确定数据结构中任意一个节点的存储地址。 （2）链式存储方法（指针）。 链式存储结构就是借助指针来指示逻辑上相邻的数据元素在存储器中的物理位置。因此，可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。 链式存储结构的主要特点是：结构中除自身信息外，还有表示连接信息的指针域，因此比顺序结构的存储密度小，存储空间利用率低。存储空间可以是不连续的，因而更适合动态数据的管理。 5.两种结构之间的关系： 一般地，程序算法的设计取决于逻辑结构的设计，而算法的实现依赖于采用的存储结构。 三、数据的运算 1.概念：数据的运算是指对所定义的数据结构进行访问或操作。数据的运算是定义在数据的逻辑结构上的，但是运算的实现要在存储结构上进行。 2.几种基本运算： 插入：在数据结构的指定位置上增添新的数据元素； 删除：删除数据结构中某个指定的数据元素； 更新：改变数据结构中某个数据元素的值； 查找：在数据结构中寻找满足某个特定要求的数据元素； 排序：重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或 由大到小的次序排列。 从运算的性质来分，所有的运算可以分为两类：一类是加工型运算，其运算改变了数据结构的值；另一类是引用型运算，其运算不改变数据结构，只对数据进行访问。 3.数据类型：一组具有相同特点的数据及这组数据上的运算，用数据类型来刻划。所谓数据类型是指一组值的集合及这个集合上的一组运算的总称。 第二章、线性结构 第一节 线性表 一、线性表的基本概念 1.定义：线性结构是n(n=0)个结点的有穷序列。当n=0时线性结构记为()或φ，称为空表。设n(n0)个结点的线性结构表示成：(a1,a2,...,an)，其中每个ai代表一个结点。a1称为起始结点，an称为终端结点。i称为ai在线性表中的序号或位置。对任意一对相邻结点ai,ai+1(1=in)，ai称为ai+1的直接前趋，ai+1称为ai的直接后继。线性表的逻辑结构是线性结构。所含结点的个数称为表长。没有结点的表称为空表。 2.基本特征： 均匀性：同一结构的结点具有相同的特性(数据项的个数相同，对应项的类型也相同)。 有序性：除起始结点没有直接前趋外，其他结点有且只有一个直接前趋；除终端结点没有直接后继外，其他结点有且只有一个直接后继。 3.基本运算：设L=(a1,a2,..,ai,...,an) （1）初始化INI(L)，结果是一个空表 L=φ。 （2）求表长LEN(L)，结果是L的长度。 （3）读表元(按位查找)GET(L,i)，结果是L的第i个结点。 （4）定位(按值查