搜索
1第12章数据结构2第12章数据结构►12.1数据结构基本概念►12.2线性表►12.3栈和队列►12.4树和二叉树312.1数据结构基本概念►随着求解问题的规模和应用领域的不断扩大，简单的数据类型已经远远不能满足需要，各数据元素之间的复杂联系已经不是传统数学方程式所能表达的，无论设计系统软件或应用软件都会用到各种复杂的数据结构。►本质上，设计优秀的程序无非是选择合理的数据结构和好的算法，而好的算法的选择在很大程度上也取决于描述实际问题所采用的数据结构。因此，数据结构是设计应用程序的重要基础。412.1.1什么是数据结构►数据（data）是对客观事物的符号表示。从计算机的角度看，数据是所有能输入到计算机中并能被计算机处理的符号的集合。它是计算机操作对象的总称，也是计算机处理信息的某种特定的符号表示形式。512.1.1什么是数据结构►数据元素（dataelement）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数据项（dataitem）组成，如图书信息为一个数据项。数据项是数据不可分割的最小单位，也称为字段或域。►数据对象（dataobject）是性质相同的数据元素的集合，是数据的一个子集，如整数数据对象是自然数的集合。612.1.1什么是数据结构►数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（structure）。712.1.1什么是数据结构►数据结构包括以下几个方面：►①数据元素之间的逻辑关系，称为数据的逻辑结构；►②数据元素及其关系在计算机中的表示（又称映像），称为数据的存储结构；►③对该数据的操作，即数据的运算。812.1.2逻辑结构与存储结构►根据数据元素之间关系的不同特性，通常有下列4类基本逻辑结构：►①集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系；►②线性结构：结构中的数据元素之间存在一个对一个的关系；►③树形结构：结构中的数据元素之间存在一个对多个的关系;►④图形结构或网状结构：结构中的数据元素之间存在多个对多个的关系。912.1.2逻辑结构与存储结构►数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。1012.1.2逻辑结构与存储结构►（1）顺序存储结构►顺序存储结构把逻辑上相邻的元素存储在物理位置上相邻的存储单元中，元素之间的逻辑关系由存储空间的邻接关系直接体现。通常，顺序存储结构借助程序语言的数组来描述。其优点是节省存储空间，缺点是不便于对元素进行插入、删除运算。1112.1.2逻辑结构与存储结构►（2）链式存储结构►链式存储结构逻辑上相邻的元素在物理上并不要求相邻，元素之间的逻辑关系由附加的指针域表示。通常，链式存储结构借助程序语言的指针来描述。其主要优点是便于插入、删除运算，缺点是需要额外的指针空间，且不能对元素进行随机访问（如按下标访问）。1212.1.2逻辑结构与存储结构►（3）索引存储结构►索引存储结构在存储元素信息的同时还建立附加的索引表，索引表由关键字和指向元素的指针组成。这种结构大大提高了数据查找的速度，可以对元素进行随机访问，在进行插入、删除运算时速度也佷快。缺点是需要额外的空间来存储索引表。1312.1.2逻辑结构与存储结构►（4）哈希存储结构►哈希存储结构是根据关键字通过哈希函数计算出元素的位置，其优点是查找速度快，适合快速查找和插入元素的场合。与前三种存储结构不同，哈希存储结构只存储元素的数据，不存储元素之间的逻辑关系。1412.1.3数据结构与数据类型►数据结构是计算机处理数据元素的组织形式和相互关系，数据类型则是程序语言（如C/C++）中已实现的数据结构，是数据结构和该结构所允许的运算集合，两者的概念不能混淆。►在程序语言的数据类型支持下，根据从求解问题中抽象出来的各种数据模型，构造出描述这些数据模型的各种数据结构。1512.1.3数据结构与数据类型►抽象数据类型ADT（abstractdatatype）是指一个数学模型以及定义在该模型上的一组操作。►抽象数据类型的定义仅取决于它的一组逻辑特性，而与计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。1612.1.3数据结构与数据类型►抽象数据类型不局限于计算机中已定义并实现的数据类型，还包括在设计软件时自定义的数据类型。►为了提高软件的复用率，在现代程序设计方法学中指出，一个软件系统的框架应建立在数据之上，而不是建立在操作之上（后者是传统的软件设计方法所为）。1712.1.3数据结构与数据类型►即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作的细节，而在模块外部使用的只是抽象的数据和抽象的操作。►显然，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也就越高。1812.1.3数据结构与数据类型►抽象数据类型的基本格式如下：►其中基本运算的定义格式为ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本运算：基本运算的定义}ADT抽象数据类型名基本运算名（参数表）初始条件：描述初始条件操作结果：描述运算功能和操作结果1912.2线性表►1．线性表的定义►线性表（linearlist）是最常用且最简单的一种数据结构，是一个具有相同特性的数据元素的有限序列。序列中所含元素的个数n(n≥0)称为线性表的长度。当n=0时，表示线性表是一个空表，即表中不包含任何元素。2012.2.1线性表的基本概念►设序列中第i个元素为ai(1≤i≤n)，则线性表L的一般表示为L=(a1,a2,...,ai-1,ai,ai+1,...,an)，其中a1为第一个元素，又称表头元素；an为最后一个元素，又称表尾元素；称i为数据元素ai在线性表中的位序。表中ai-1领先与ai，ai领先与ai+1，称ai-1是ai的直接前趋元素，称ai+1是ai的直接后继元素。当i=1,2,...,n-1时，ai有且仅有一个直接后继，当i=2,3,...,n时，ai有且仅有一个直接前趋。2112.2.1线性表的基本概念►线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可方便地进行插人和删除等。2212.2.1线性表的基本概念►线性表的数据元素可以是一个数或一个符号，也可以是由若干数据项组成的信息，记为ElemType类型。如typedefstructtagElemType{//复杂的数据元素类型......//任意数目、任意组合、任意类型的数据成员}ElemType;2312.2.1线性表的基本概念►抽象数据类型线性表的定义如下：ADTList{数据对象：数据关系：基本运算：CreateList(*L,n,input())操作结果：创建一个线性表L。InitList(*L)操作结果：构造一个空的线性表L。DestroyList(*L)初始条件：线性表L已存在。操作结果：销毁线性表L。24DestroyList(*L)初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(*L)初始条件：线性表L已存在。操作结果：将L置为空表。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表返回真，否则返回假。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素的个数，L的长度。GetElem(L,i,*e)初始条件：线性表L已存在，。操作结果：用*e返回L中第个数据元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是关系判定函数。12.2.1线性表的基本概念25操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回0。PriorElem(L,cur_e,*pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用*pre_e返回它的前驱，否则操作失败，*pre_e无定义。NextElem(L,cur_e,*next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用*next_e返回它的后继，否则操作失败，*next_e无定义。12.2.1线性表的基本概念26ListInsert(*L,i,e)初始条件：线性表*L已存在。操作结果：在*L中第i个位置之前插入新的数据元素e，*L的长度加1。ListDelete(*L,i,*e)初始条件：线性表*L已存在且非空。操作结果：删除*L的第i个数据元素，并用*e返回其值，*L的长度减1。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit()，一旦visit()失败则操作失败。}ADTList12.2.1线性表的基本概念2712.2.1线性表的基本概念►【例12.1】有一个线性表L=(‘h’,‘e’,‘l’,‘l’,‘o’}，求ListLength(L)、ListEmpty(L)、GetElem(L,1,&e)、LocateElem(L,‘e’,compare)、ListInsert(&L,3,‘-’)、ListDelete(&L,6,&e)等基本运算执行结果。►ListLength(L)5►ListEmpty(L)假（0）►GetElem(L,1,&e)e='h'►LocateElem(L,'e',compare)2►ListInsert(&L,3,'-')执行后L=('h','e','-','l','l','o'}►ListDelete(&L,6,&e)执行后L=('h','e','-','l','l'}2812.2.1线性表的基本概念►【例12.2】假设有两个线性表La和Lb分表表示两个集合A和B，编写一个算法求新集合A=A∪B，即将两个集合的并集放到线性表La中。►解扩大线性表La，遍历线性表Lb，将存在于Lb中但不存在于La中的数据元素插入到La中。►由于LocateElem(La,e)运算的时间复杂度为O(ListLength(La))，所以算法的时间复杂度为O(ListLength(La)*ListLength(Lb))。2912.2.1线性表的基本概念voidunionlist(List*LA,List*LB){//将所有在线性表*LB中但不在*LA中的数据元素插入到*LAintLA_len,LB_len,i;ElemTypee;LA_len=ListLength(*LA),LB_len=ListLength(*LB);for(i=1;i=LB_len;i++){//遍历线性表*LBGetElem(*LB,i,&e);//取*LB中第i个数据元素eif(LocateElem(*LA,e,compare))ListInsert(LA,++LA_len,e);}}3012.2.1线性表的基本概念►【例12.3】已知两个线性表La和Lb中的数据元素升序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素也是升序排列。►解先置Lc为空表，然后将La或Lb中的元素逐个插入到Lc中。为使Lc中的数据元素也升序排列，可以用i和j分别表示La和Lb当前的位序。设La当前数据元素为a，Lb当前数据元素为b，则插入到Lc中的元素是a和b的最小值。3112.2.1线性表的基本概念voidMergeList(ListLa,ListLb,List*Lc){//顺序线性表La和Lb升序排列。归并得到Lc且升序排列inti=1,j=1,k=0,la_len,lb_len;ElemTypea,b;InitList(Lc);//先置Lc为空表la_len=ListLength(La),lb_l