数据结构.ppt

2020/7/20数据结构1数据结构2020/7/20数据结构2讲课安排：•串讲全书内容•典型习题分析•前年、去年考题分析2020/7/20数据结构3第一章概论•数据结构及其概念•如何评价一个算法2020/7/20数据结构4第一章概论1.1数据结构的概念一、术语1.数据(Data):是信息的载体，能被计算机识别、存储、加工处理。2.数据元素(DataElement):数据的基本单位,即数据集合中的一个个体。也称元素、结点、顶点、记录数据项:是具有独立含义的最小标识单位关键字（key)：唯一能识别一个数据元素的数据项。数据元素由数据项(dataitem)组成2020/7/20数据结构53、数据类型(DataType):是具有相同性质的计算机数据的集合及在这个集合上的一组操作。原子数据类型(atomicdatatype)结构数据类型(aggregatedatatype)4、数据结构•数据的逻辑结构•数据的存储结构•数据的运算：既对数据施加的操作2020/7/20数据结构6逻辑结构：(有时直接称为数据结构）•线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继)•非线性结构：树、图、多维数组、广义表说明：1、逻辑结构与数据元素本身的形式、内容无关2、逻辑结构与数据元素的相对位置无关3、逻辑结构与所含结点个数无关2020/7/20数据结构7存储结构：•顺序存储方法：数据元素在内存中按序连续存储，结点间的逻辑关系由存储单元的邻接关系来体现•链接存储方法：用指针指出其直接后继结点的存储位置，结点间的逻辑关系由存储单元的邻接关系来体现•索引存储方法：数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成分为稠密索引和稀疏索引•散列存储方法：确定散列函数后，根据结点的关键字直接计算出该结点的存储地址。2020/7/20数据结构8关系：•逻辑结构是从逻辑关系上描述数据，与存储无关，是独立于计算机的。•逻辑结构是从具体问题抽象出来的数学模型•存储结构是逻辑结构用计算机语言的实现（亦称映象）•数据的运算是定义在数据的逻辑结构上的一个运算的集合•运算的实现与存储结构密切相关•逻辑结构与存储结构是多对多的关系2020/7/20数据结构9例：一个学生成绩表：•是一个数据结构•每行是一个结点（或记录），由学号、姓名、各科成绩及平均成绩等数据项组成。•逻辑关系：线性结构•存储结构：•表的运算：2020/7/20数据结构10逻辑结构上定义的基本运算在存储结构上的实现是通过算法来描述的。一、算法定义算法是对特定问题求解步骤的一种描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作。第一章概论1.3算法描述2020/7/20数据结构11二、算法应具有的五个特性：（1）输入一个算法有零个或多个的输入，它们是算法开始前给出的最初量（2）输出一个算法至少有一个输出，它们是同输入有某种关系的量（3）有穷性每一条指令的执行次数必须是有限的（4）确定性每一条指令必须有确切的含义，无二义性（5）可行性每条指令的执行时间都是有限的。2020/7/20数据结构12第一章概论一、算法评价五要素（1）正确性（2）执行算法所耗费的时间（3）执行算法所耗费的空间（4）可读性（5）健壮性1.4算法分析2020/7/20数据结构13第一章概论二、算法的时间复杂度•一个算法所耗费的时间:该算法中每条语句的执行时间之和。•每条语句的执行时间：该语句的执行次数乘以该语句执行一次所需时间。•频度：语句重复执行的次数•算法的时间耗费T(n)=每条语句的执行的时间=（语句频度×语句执行一次所需时间）=语句频度•算法的时间复杂度：就是算法的时间耗费T(n)2020/7/20数据结构14第一章概论三、（渐进）时间复杂度(O(f(n))当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度，简称时间复杂度四、最坏时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度称为最坏时间复杂度。五、平均时间复杂度在假设数据集的分布是等概率的条件下，估算出的时间复杂度称为平均时间复杂度。例：顺序查找2020/7/20数据结构15五、空间复杂度S(n)：算法所耗费的存储空间，仍是问题规模n的函数。第一章概论2020/7/20数据结构16第一章概论本章要求:1、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。3、学会算法分析的基本方法。2020/7/20数据结构17第二章线性表本章要学习的主要内容1、线性表的逻辑结构及基本运算2、线性表的顺序存储结构3、线性表的链式存储结构：单链表、循环链表、双链表、静态链表4、顺序表和链表的比较2020/7/20数据结构182.1线性表的概念及运算1.描述:线性表是由n(n=0)个数据元素(点)a1,a2,….,ai,….,an组成的有限序列。其中，数据元素的个数n定义为表长。当n=0时称为空表，非空的线性表(n0)记为：(a1,a2,….,ai,…..,an)一、逻辑结构注意:1.数据元素ai是一个抽象的符号2.ai可取各种数据类型3.一般情况下,同一线性表中的元素具有相同的数据类型4.i是元素的序号(1=i=n)2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继2020/7/20数据结构19线性表的常见基本运算包括：（1）置空表SETNULL(L)（2）建表CREATLIST(L)二、线性表的运算（4）取结点GET(L,i)（5）定位LOCATE(L,x)（6）插入INSERT(L,x,i)（7）删除DELETE(L,i)（3）求表长LENGTH(L)复杂的运算可以由这些基本运算组合来实现2020/7/20数据结构202.2线性表的顺序存储1、顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。3、存储地址的计算：LOC(ai)=LOC(a1)+(i-1)*c1=i=n这里：LOC(a1)为结点a1的存储起址(基地址），c为每个结点所占存储单元数。一、顺序表2、顺序表：采用顺序存储方法存储的线性表称顺序表。顺序表是一种随机存取结构2020/7/20数据结构21typedefintdatetype;#definemaxsize1024typedefstruct{datatypedata[maxsize];intlast;}sequenlist;4、顺序表的描述：说明:(1).datatype是表中的数据类型,依具体情况而定(2).向量下标可以看作表中结点的相对地址(3).顺序表的长度为last+1(4).结点的引用:定义一个顺序表：sequenlist*L;(*L).data[0]a1(*L).data[1]a2....(*L).data[(*L).last]ana1a2...anMaxsize-1(*L).last01last2020/7/20数据结构22二、顺序表上的基本运算（实现）2.2线性表的顺序存储SETNULL（L）：(*L).last=-1LENGTH(L):(*L).last+1GET(L,i):(*L).data[i-1]LOCATE(L,x)INSERT(L,x,i)DELETE(L,i)2020/7/20数据结构23顺序表的特点：用物理位置上的邻接关系表示结点间的逻辑关系顺序表的优点：（1）无须增加额外的存储空间表示结点间的逻辑关系。（2）可以方便地随机存取表中任一结点。顺序表的缺点：（1）插入和删除运算不方便，通常须移动大量结点，效率较低。（2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。2020/7/20数据结构242.3线性表的链式存储一、链表1、链式存储：用一组任意的存储单元存储线性表,逻辑上相邻的结点在物理位置上不一定相邻，结点间的逻辑关系由存储结点时附加的指针字段表示2、链表：采用链式存储方法的线性表称为链表。2020/7/20数据结构252.3.1单链表1、单链表的特点：每个结点只有一个链域，指向其直接后继（尾结点除外）。4、单链表的存储结构描述如下：typedefintdataype;typedefstructnode{datatypedata;structnode*next;}linklist;linklist*head,*p;2、结点结构：datanext3、图示法表示单链表a1a2an.....^head因为单链表由头指针唯一决定2020/7/20数据结构26说明：•区分指针变量和结点变量:p,*p•结点的动态分配和释放typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;linklist*head,*p;申请一个结点p=(linklist*)malloc(sizeof(linklist));释放一个结点free(p);2020/7/20数据结构272.3.2单链表上的基本运算（实现）1.建立单链表（1）头插法建表（2）尾插法建表方法:从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域,然后将新结点插入当前链表中,直到结束。头插法建表：将新结点插入到当前链表的表头ds优点：算法简单缺点：链表中结点次序和输入次序相反cbaHead^122020/7/20数据结构28Linklist*CREATLIST(){charch;linklist*head,*s;head=NULL;ch=getchar();dscbaHead^12while(ch!=‘$’){s=malloc(sizeof(linklist));s-data=ch;s-next=head;head=s;ch=getchar();}returnhead;}2020/7/20数据结构292.3.2单链表上的基本运算（实现）尾插法建表：将新结点插入到当前链表的表尾（需引入r）dsrabcHeadr^^•不带头结点的尾插法：插入时，第一个结点的处理与其它结点的处理有区别。结束时，空表和非空表的处理有区别。2020/7/20数据结构30Linklist*CREATLISTR(){charch;linklist*head,*s,*r;head=NULL;r=NULL;ch=getchar();while(ch!=‘$’){s=malloc(sizeof(linklist));s-data=ch;if(head=NULL)head=selser-next=s;r=s;ch=getchar();}if(r!=NULL)r-next=NULL;returnhead;}2020/7/20数据结构312.3.2单链表上的基本运算（实现）尾插法建表：将新结点插入到当前链表的表尾（需引入r）dsrabcHeadr^^•不带头结点的尾插法：插入时，第一个结点的处理与其它结点的处理有区别。结束时，空表和非空表的处理有区别。•带头结点的尾插法：1）链表第一个位置上的操作与其它位置上的操作相一致。2）空表和非空表的处理相一致。2020/7/20数据结构322.3.2单链表上的基本运算（实现）Linklist*CREATLISTR1(){charch;linklist*head,*s,*r;head=malloc(sizeof(linklist));r=head;ch=getchar();while(ch!=“$”){s=malloc(sizeof(linklist));s-data=ch;r-next=s;r=s;ch=getchar();}r-next=NULL;returnhead;}dsrcHeadr^^2020/7/20数据结构332.3.2单链表上的基本运算（实现）二、查找运算（1）按序号查找GET（L，i）给定一个序号，在单链表中查找该序号对应的结点，若结点存在，则返回该结点的指针，否则返回空指针。方法：非随机存储结构的链表，决定了上述查找运算