《软件技术基础-数据结构.ppt》由会员分享，可在线阅读，更多相关《软件技术基础-数据结构.ppt（58页珍藏版）》请在三一办公上搜索。
1、计算机数据指计算机能够处理和保存的信息。数据包含数值、文字、字母、字符、声音、程序、图形、图像等信息。构成数据的基本单位是数据元素。数据元素之间存在一定的关系，并且按照一定的存储方式保存在计算机系统中。如何表达数据元素之间的关系将影响到计算机运算效率与使用存储空间的合理性。为此，一门讨论计算机系统中数据的组织形式及其相互关系的计算机学科-数据结构应运而生。,一.数据结构概念数据结构是数据存在的形式，反映了数据的内部构成，即一个数据由哪些成分构成，以什么方式构成，呈什么结构。其目的是提高算法的效率。数据结构分为逻辑结构和物理结构。数据的逻辑结构描述了数据之间的逻辑关系；数据的物理结构描述了数据在
2、计算机内部的存储关系。,几个有关概念数据：指能被计算机识别、存储和加工的客观事物。结构：指事物间的相互关系和相互约束。数据元素：是数据的基本单位(称数据结点)。数据结构：讨论计算机系统中数据的组织形式及相互关系。算法：指为解决某一问题而进行的有限操作的 过程描述。,数据结构的基本运算：遍历：在数据结构的各个元素中移动，或浏览所有数据元素。插入：在数据结构中添加新的数据元素。更新：修改或替换数据结构中指定元素的数据项(即字段值)。删除：把指定数据元素从数据结构中去掉。查找：在数据结构中查找满足条件的数据元素。排序：在保持数据结构中数据元素个数不变的前提下，把元素按指定的顺序重新排列(一般指线性逻
3、辑结构)。,研究数据结构主要有三个方面的内容：1.数据的逻辑结构。从逻辑上研究数据元素之间的关系；2.数据的存储结构：讨论数据元素之间的关系在计算机中的表示方法；3.数据的运算。通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。如检索、插入等。,例如：数据表是一个线性表结构，表中的每一行是一个数据元素(是数据结构的基本单位)，由“姓名”、“性别”、“单位”等字段组成。,表中数据元素的逻辑关系：表中任一元素，与它相邻且直接前趋的数据元素最多只有一个；与表中任一数据元素相邻且直接后继的数据元素也最多只有一个。表中第一个元素没有直接前趋，称为开始数据元素，最后一个数据元
4、素没有直接后继，称为终点元素。,表的存储方式：表中的数据元素顺序邻接在一片连续的存储单元中。表数据运算：对表元素进行查找、删除、插入等操作，提高数据操作效率。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。,数据结构分为两大类：线性结构和非线性结构。1.线性结构线性结构的逻辑特征：有并且只有有一个开始数据元素和一个终点数据元素，所有数据元素都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。,2.非线性结构非线性结构的逻辑特征：一个数据元素可能有多个直接前趋和多个直接后继。非线性结构中最一般的结构是图结构。在图结构中，任何数据元素的直接前趋和直接后继的
5、个数不作限制。,树结构是非线性结构中一类较特殊的结构。树的逻辑特征：有且仅有一个称为“根”的元素无直接前趋，其他元素有且仅有一个直接前趋，所有数据元素(除根元素)都存在一条从根元素到该元素的路径。,数据结构在计算机中的表示(映像)称为数据的物理(存储)结构。数据在储存器中的4种存储方法：顺序存储：把逻辑上相邻的数据元素按照某种顺序存储在物理位置上也相邻的(一块连续的)存储单元中。顺序存储方法主要用于线性数据结构。非线性的数据结构也可以通过某种线性化的方法来实现顺序存储。,链式存储：对在物理位置上不相邻的数据，通常采用链式存储结构。链式存储结构的特点是把存放数据元素的节点分为两部分，一部分存放数
6、据元素(称为数据域)；另一部分存放指示存储地址的指针(称为指针域)，指针域指出了其后继或前趋数据元素的存储地址(即数据元素之间的关系)，从而形成一个链。,索引存储：在存储元素信息的同时，建立附加的索引表，索引表中的每一项称为索引项。索引项的一般形式：(关键字、地址)若一组结点的每个结点在索引表中都有一个索引项，称为稠密索引。若一组结点在索引表中只对应一个索引项，称为稀疏索引。,散列存储：其基本思想是根据结点的关键字直接计算出该结点的存储地址。散列存储方法又称“关健字-地址转移法”同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择哪种存储结构来表示相应的逻辑结构，视具体要求而定，主要考
7、虑运算方便及算法要求。,二.线性结构线性结构是数据结构中最简单且最常用的一种数据结构。1.线性结构的特点：数据元素有序并有限。逻辑特征：有且仅有一个无直接前趋而仅有一个直接后继的数据元素为起始元素；有且仅有一个无直接后继而仅有一个直接前趋的数据元素为终点元素；其余为内部元素，各有一个直接前趋和直接后继。,线性结构的数据元素可排成一个线性的序列：其中，a1为起始元素，无直接前趋；an为终点元素，无直接后继；ai为索引号为i的数据元素，只有一个直接前趋和直接后继。,2.常见的线性结构 线性结构有各种类型，如线性表、堆栈、队列、数组、串等。,线性表线性表是由n(n0)个相同类型的元素 al，a2，.
8、，an所构成的有限线性序列。例如：1，12，123，1234，5321，221该整数序列是一个线性表，元素ai是一个整数，表长为6。,线性表有两种存储方式：顺序存储结构 在存储器中用一片地址连续的存储单元依次存放线性表中的数据元素，数据元素之间的逻辑关系通过数据元素的存储地址直接反映，使逻辑上相邻的两个数据元素在物理位置上也相邻。链式存储结构 用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以连续的，也可以不连续的，从而大大提高存储器的使用效率。,顺序表数据元素按其逻辑次序依次存放在一组地址连续的存储单元中。顺序表的逻辑关系蕴含在存储单元的邻接关系中。,线性链表线性链表是采用链式存
9、储结构方式进行存储的线性表，用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，可以是不连续的，可以大大提高存储器的使用效率。线性链表有单向链表和循环链表。,单向链表：单向链表是链式存储结构中最简单和最基本的结构。单向链表的每个数据元素由两部分组成：存储元素值的数据域(data)和存储直接后继元素存储地址的指针域(next)。,设有线性表a1，a2，.，an。在数据元素ai的结点之前插入一个数据元素为x的结点。首先应找到数据元素ai-1的结点，打开ai-1与ai两数据元素之间的链；申请一个新的结点空间，放上数据值x；再重新建立ai-1与x、x与ai 两两数据元素之间的链，构
10、成新的链表。,双向链表：双向链表的指针域包括指向该结点的直接前趋和直接后续的两个指针的存储结构。在单链表中，每个结点的指针指向该结点元素的直接后继元素的结点，每查找一个数据元素，都必须从头结点开始，从前向后单方向的搜寻。双链表实现线性链表从后向前的搜寻，即可双向查找。,循环链表：循环链表是一种首尾相接的链表。在单链表中，把最后一个结点的指针域指向头结点(带头结点的链表)或第一个元素结点(不带头结点的链表)，使整个链表形成一个环，构成单向循环链表。在双链表中，将双链表的最后一个结点与头结点(带头结点的双链表)或第一个元素结点(不带头结点的双链表)链接起来，构成双向循环链表。,栈 栈是一种特殊的线
11、性表，它的插入和删除运算限制在表的一端进行。通常称插入、删除的一端为“栈顶”，另一端称为“栈底”。当表中没有元素时称为“空栈”。栈中元素的插入和删除只能在栈顶进行，栈是一种后进先出表(LIF0)。,举例：进栈与出栈,队列 队列也是一种操作受限的线性表，允许在线性表的一端进行数据元素插入操作，而在另一端进行数据元素删除操作。允许插入的一端称为队尾，允许删除的另一端称为队头。根据队列的特点，队列有两个队列指针，一个是队头指针front,它总是指向队头元素的前一个位置；另一个是队尾指针 rear，它总是指向队尾元素所在的存储位置。,举例：入队和出队,举例：循环队列的入队和出队,数组顺序存储结构在计算
12、机内是用一组连续的内存单元来存储数组的。它分为行优先顺序存储和按列优先顺序存储两种。一维数组本身就是顺序表结构，多维数组是一种特殊的线性结构。基于二维数组应用最为广泛，像数学中的矩阵、生活中常见的报表都是二维数组。,串串是一种数据元素固定为字符的线性表。就数据结构而言，串归属于线性表数据结构。线性表上的操作是针对线性表中的某个数据元素进行，而串上的操作是针对串的整体或串的某一部分子串进行。串的基本操作包括：判串、求串长、连接串、替换子串等。,三.非线性结构非线性结构的逻辑特征：一个结点元素可能有多个直接前趋和多个直接后继。最主要的非线性结构有树结构、二叉树和图结构。1.树结构基本概念 树结构是
13、结点之间有分支、层次关系的结构，类似于自然界中的树，也有树根、树叶及联系它们的支干，它是一种倒生树。在树中，一个结点元素简称“结点”。,2.有关树结构的术语：叶子：没有后继的结点(或终端结点)。如图结点 D、E、F、G、H、J。分支结点：非叶子结点称为分支结点(或非终端结点)。如图结点 A、B、C、I。结点的度：一个结点的子树数目称为该结点的度。如图结点B的度为2；结点C的度为3；结点D、J的度为0。,树的度：树中各结点的度的最大值称为该树的度。如图所示树的度为3。子结点：某结点的子成为该结点的子结点。父结点：某结点的根，称该结点父结点。兄弟：具有同一父结点的子结点。如，结点C是结点G、H、I
14、 的父结点；结点G、h、I是结点C的子结点；结点G、H、I 互为兄弟。,结点的层次：根结点层次为1，其他任何层次为父结点的层次加1。树的深度：结点的最大层次值就是树的深度。图中树的深度为4。有序树和无序树：若树中结点的各子树从左到右是有序的，即交换某结点各子树的相对位置，构成不同的树，称这棵树为有序树，反之则为无序树。森林：森林是n棵树的集合(n0)。任何一棵树，删去根结点，树就变成丁森林。对树中的每个结点来说，其子树的集合就是一个森林。,3.二叉树结构 二叉树结构也是非线性结构中重要的一类，但二叉树结构不同于一般的树结构。二叉树是n个结点的有限集合(n0)：该集合可以是空(即n=0)，即“空
15、二叉树”；或者由一个根结点和两棵互不相交的被称为根的左子树和右子树组成。左子树和右子树分别又是一棵二叉树。二叉树可以有五种基本形态。注意一般树至少有一个结点，而二叉树可以空；二叉树的结点的子树区分为左子树和右子树，而一般树无此区分。,几个特殊二叉树的概念：满二叉树。在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的二叉树称做满二叉树。图中结点字符代表该结点本身的数据信息，数字为该结点的顺序编号。,完全二叉树。二叉树只有最下面的两层上结点的度数小于2，并且最下一层上的结点都集中在该层最左边的位置，则称为完全二叉树。二叉排序树。左子树上所有结点的关键字均小于根
16、结点的关键字；右子树上所有结点的关键字均大于根结点的关键字。左子树和右子树本身又各是一棵二叉排序树。,二叉树的遍历。树遍历是按一定规律走遍树的每一个结点，使每个结点被访问而且只被访问一次。一棵二叉树由三部分组成：根结点(记作D)、左子树(记作L)和右子树(记作R)。当限定对左右子树的访问次序为先左后右，则有三种访问：DLR(称为先序遍历)ABDGECFH LDR(称为中序遍历)DGBEAFHC LRD(称为后序遍历)GDEBHFCA,4.图图是一种复杂的非线性数据结构。图结点之间的联系可以是任意的。每个结点都可以与其他的点相联系。,有向图：如果图G的每条边都是有方向的，则称G为有向图。有向图的
17、一条有向边是由两个顶点组成的有序树，通常用尖括号表示。如表示一条有向边，Vi是边的顶点，Vj是边的终点。无向图：如果图G的每条边都是无方向的，则称G为无向图。无向图中的边都是顶点的无序树，用圆括号表示。,四.查找与排序1.查找算法查找是根据给定的关键字值，在一组数据元素中确定一个关键字值等于给定值的数据元素。若存在该数据元素，则查找成功；否则查找失败。查找算法取决于查找表中各数据元素在计算机存储系统中的组织方式与存储结构。,顺序查找顺序查找的基本思想：从第一个数据元素开始，逐个把数据元素的关键字值和给定值比较，若某个元素的关键字值与给定值相等，则查找成功；如果直至第n个元素都不相等，说明不存在
18、满足条件的数据元素，查找失败。顺序查找方法适用于顺序存储结构和链式存储结构的查找表。,顺序查找举例：在线性表中查找54和19。,找：54-查找成功，查找长度为5。找：19-查找失败，查找长度为9。在长度为n的线性表中顺序查找的平均查找长度ASL=(n+1)/2。,二分查找(折半查找)二分查找的算法思想：查找表中的数据元素按关键字有序(递增或递减)，先以有序数列的中点位置作为比较对象，如果元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分，将查找区间缩小一半。二分查找是一种高效率的查找方法，其先决条件是查找表中的数据元素必须有序。其缺点是对所有数据元素排序非常费时。,二分查找举例：
19、对有序数列3,5,11,17,21,23,28,30,32,50，折半查找关键字值为30的数据元素。,对于有1000个数据元素的查找表，顺序查找平均查找长度ASL=500，二分查找平均查找长度ASLlog2n=9。,分块查找(索引顺序查找)分块查找的算法思想：首先将所有数据元素分成若干块，块内元素可以无序，但块间按关键字有序；然后选取各块中的最大(或最小)关键字构成一个索引表。最后分两步查找：先确定待查数据元素可能在哪一块，然后在已确定的块中顺序查找。,分块查找举例：把待查序列22,12,13,9,8,33,42,44,38,24,48,60,58,75,47按“块间有序”分为3块(22,12
20、,13,9,8)；(33,42,44,38,24)；(48,6,58,74,47)。选取每块中最大的关键字组成索引表22,44,74,查找关键字值为60的元素。,2.排序算法 几个排序的基本概念排序：排序是将一组数据元素按排序码递增或递减排列的一种运算操作。排序码：排序的依据是排序码，排序码指数据元素中的一个或多个关键字。,内部排序和外部排序：内排序指在计算机内存中进行的排序；外排序指使用计算机外存进行的排序。排序算法的稳定性：如果待排序的序列中存在多个具有相同排序码的数据元素，经过排序后数据元素的相对次序保持不变，则称这种排序算法是稳定的；若经过排序后数据元素的相对次序发生改变，则称这种排序
21、算法是不稳定的。,内排序方法 插入排序：分为直接插入排序、折半插入排序、2-路插入排序、表插入排序和希尔(Shell)排序。选择排序：分为简单选择排序(或称选择排序)、树形选择排序和堆排序。交换排序：分为冒泡排序和快速排序。归并排序：归并排序分为2-路归并排序和k-路归并排序。,几种最常用、最简单的排序方法：插入排序基本思想：将待排序的记录插入到已排序的子文件中，使得插入之后得到的子文件仍然有序。插入一个记录，首先要对有序子文件进行查找，以确定这个记录的插入位置。按查找方式不同，插入排序又分为线性插入排序(顺序查找)和折半插入排序(折半查找)。插入排序举例：,选择排序基本思想：从待排序文件r1
22、.n中，确定最小关键字Rmin，与某个元素交换位置。第一趟：在n个记录中按排序码选出最小关键字Rmin，与r1元素交换位置；第二趟：在n-1个记录中选出最小的元素Rmin，与r2元素交换位置；第i趟：在r1.n中选出最小的元素Rmin，与ri元素交换位置；如此反复，使得r1.n有序。选择排序举例：,冒泡排序基本思想：设待排序文件r1.n。第一趟：从Rl开始两两比较Ri+1排序码大小，若RiRi+1则交换Ri和Ri+l的位置。第一趟排序后Rn为最大元素。第二趟：从Rl开始两两比较Ri排序码的大小，若RiRi+1则交换Ri和Ri+l的位置。第二趟排序后Rn-1为次大元素。如此反复经n-1趟排序后，
23、使得r1.n有序。冒泡排序举例：,快速排序基本思想：在r1.n中，确定一个ri。经过比较和移动，将ri放到“中间”某个位置上，使ri左边所有记录的关键字=ri.key。以ri为界,将文件r1.n划分为左、右两个子文件。再用同样的方法分别对这两个子文件进行划分，得到4个更小的子文件。如此继续，使每个子文件只有一个记录为止，使得r1.n有序。,归并排序归并排序是把两个或两个以上有序的序列合并为一个有序的序列，若是对两个有序序列进行归并，又称为2路归并。基本思想：将有n个元素的原始序列看作n个有序子序列，每个子序列的长度为1。从第一个子序列开始把相邻的子序列两两合并，得到n/2个，长度为2或1的子序列，这一过程称为一次归并排序。对第一次归并排序后的n/2个子序列采用上述方法，继续顺序成对归并，如此重复最后得到长度为n的有序序列。归并排序举例：,几种排序比较稳定性：插入排序、归并排序和冒泡排序稳定性好；选择排序不稳定。综合情况：归并排序速度较快，插入排序和冒泡排序速度较慢。各种排序法选用依据：数据规模n大，内存足够大，有稳定要求时，可使用归并排序。数据规模n较小，有稳定要求，可用插入排序。数据规模n较小，不要求稳定，可用选择排序。,
