数据结构四川理工.ppt

《数据结构四川理工.ppt》由会员分享，可在线阅读，更多相关《数据结构四川理工.ppt（58页珍藏版）》请在三一办公上搜索。

1、 DCS of SUSE,第1章绪论,复习要点：1.数据结构基本概念 2.数据元素、数据项、逻辑结构、物理结构 3.时间复杂度、空间复杂度、语句频度等计算,DCS of SUSE,基本概念,(1)数据：所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。(2)数据元素:是数据的基本单位，具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。(3)数据项:构成数据元素的项目。它是数据不可分割的最小单位。(4)数据类型：指一个类型和定义在这个类型上的操作集合。例：C语言（基本类型：整型、浮点型、字符型等构造类型：数组、结

2、构、联合、指针、枚举等）(5)抽象数据元素：抽象定义的、没有实际含义的数据元素。(6)抽象数据类型：用户自己定义的数据类型。,DCS of SUSE,数据结构,DCS of SUSE,集合结构：仅同属一个集合线性结构:一对一（1:1)树 结 构:一对多（1:n)图 结 构:多对多(m:n),线 性,逻辑结构可细分为4类：,数据的逻辑结构,指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,DCS of SUSE,（1）R=(D,S)D=a,b,c,d,e,f S=,解：上述表达式可用图形表示为：,b c a e f d,此结构为线性的。,例：用图形表示下列

3、数据结构，并指出它们是属于线性结构还是非线性结构。,DCS of SUSE,物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,存储结构可分为4大类：,例：复数3.02.3i 的两种存储方式：,顺序、链式、索引、散列,法1：地址 内容,法2：地址 内容,2字节,数据的物理结构,DCS of SUSE,时间复杂度和空间复杂度如何表示？,DCS of SUSE,特别说明：如果无论算法规模怎样变化，其执行时间为一常数，则该算法的时间复杂度为O(1).,DCS of SUSE,DCS of SUSE,第2章 线性表,复习要点：1.基本概念 线性结构、线性表、位序、

4、长度、空表等2.线性表的基本操作 主要掌握插入、删除等运算及特性3.顺序存储、链式存储特点，组织方式 顺序表、单链表、双链表的查找、插入和删除等操作,DCS of SUSE,一、线性表（linear_list）线性表是n个数据元素的有限序列，记为：L=（a1,a2,an）,数据元素之间的关系是：ai-1领先于ai，ai领先于ai+1。称ai-1是ai的直接前驱 元素；ai+1是ai的直接后继 元素。除a1外，每个元素有且仅有一个直接前驱元素，除an外，每个元素有且仅有一个直接后继元素。线性表中数据元素的个数n(n=0)称为线性表的长度，当n=0时，称为空表。,DCS of SUSE,线性表的顺

5、序存储结构,一、顺序存储结构 用一组地址连续的存储单元依次存储线性表的元素。设线性表的每个元素占用k个存储单元，则第i个元素ai 的存储位置为：Loc(ai)=Loc(a1)+(i-1)*k 其中，Loc(ai)为线性表的起址。,特点：存储单元地址连续（需要一段连续空间）逻辑上相邻的数据元素其物理位置也相邻存储密度大（100%）随机存取元素序号与存储位置存在如下关系：,Loc(ai)=Loc(a1)+(i-1)*d(1in),线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。,DCS of SUSE,二.插入和删除操作1.插入运算 INSERT（L,i,b）插入

6、前：L=（a1,.,ai-1,ai,.,an）插入后：L=（a1,.,ai-1,b,ai,.,an）,算法思想：进行合法性检查，1=i=n+1；判断线性表是否已满；将第n个至第i个元素逐一后移一个单元；在第i个位置处插入新元素；将表的长度加1。,DCS of SUSE,线性表上的基本运算插入运算含义：将元素e插入到线性表：(a1,a2,ai-1,ai,an)中，构成新的线性表(a1,a2,ai-1,e,ai,an)，满足ai-1 e ai,(其中为比较关系),即不破坏原线性关系。表的长度为n+1将元素e插入到元素ai-1之后，ai-1的直接后继和ai 的直接前驱就改变了，需要在顺序表的存储结构

7、上反映出来。,DCS of SUSE,2.删除运算DELETE（L,i）删除前：L=（a1,.,ai-1,ai,ai+1,.,an）删除后：L=（a1,.,ai-1,ai+1,.,an）,算法思想：进行合法性检查，i是否满足1=i=n；判线性表是否已空，L.length=0；将第i+1至第n个元素逐一向前移一个位置；将表的长度减1。,思考：如果要删除指定位置开始的m个元素，如何实现？,DCS of SUSE,线性表顺序存储结构的特点(1).逻辑上相邻的元素，其物理位置也相邻；(2).可随机存取表中任一元素；(3).必须按最大可能长度预分存储空间，存储空间利用率低，表的容量难以扩充，是一种静态存

8、储结构；(4).插入删除时，需移动大量元素，平均移动元素为n/2。顺序表的基本运算的复杂度插入T(n)=O(n)，S(n)=O(1)删除T(n)=O(n)，S(n)=O(1),DCS of SUSE,线性表的链式表示和实现,链表-线性表的链式存储内涵：线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其直接前驱和（或）直接后继之间的关系用指针来存储。这称为链表。术语结点：数据元素及与其有直接关系的元素的地址构成的存储单位。,数据域,指针域,DCS of SUSE,单链表的表示和实现,单链表上的查找运算在单链表中，必须从头指针出发进行查找：查找第i个元素查找指定的元素是否在表中.若

9、找到，则返回该元素的值，否则返回ERROR。在单链表上查找第i个元素的示意图,k=1,找到，返回P指向的结点的数据。,问题：i n呢？,特别说明：指针的移动，不会删除结点。,DCS of SUSE,单链表上的插入运算(第i个位置上插入新的结点)逻辑运算(a1,a2,ai-1,ai,ai+1,an),(a1,a2,ai-1,e,ai,ai+1,an),单链表上的实现示意图,基本步骤：找到第i-1个元素所在结点；,申请一个新结点s并填入e值；,修改s的指针域指向p的下一结点；,思考：第步是否可交换？,DCS of SUSE,链表的优缺点优点：插入、删除时无须移动元素，只需修改指针根据需要申请存储空

10、间，且不要求连续的存储空间缺点：对表中的元素只能进行顺序访问用指针指示元素之间的逻辑关系（直接前驱、后继），存储空间利用率低,DCS of SUSE,双向链表,双向链表上的插入操作(将元素e插入到链表的第i个结点前),基本步骤：(1)定位指针p指向结点ai-1;,(2)建立新结点s并赋e;,(3)修改s的next指针域指向p下一结点：s-next=p-next;,(5)修改p的next指针域指向s结点：p-next=s;,(6)修改s下一结点的prior指针域指向s：s-next-prior=s;,(4)修改s的prior指针域指向p结点：s-prior=p;,问题：修改指针的步骤是否可随意？

11、不带头结点？,DCS of SUSE,双向链表上的删除操作(删除第i个结点),基本步骤：(1)定位指针p指向结点ai;,(2)修改p的前一结点的next指针域指向p下一结点：p-prior-next=p-next;,(3)修改p的下一结点的prior指针域指向p前一结点：p-next-prior=p-prior;,(4)释放结点p。,DCS of SUSE,第3章 栈和队列,一、栈的概念 栈（stack）是插入和删除操作限定在表尾进行的线性表。栈的逻辑表示为：S=（a1,a2,an）表尾元素an称为栈顶(top)表头元素a1称为栈底(bottom)不含元素的空表称为空栈栈的运算特性是后进先出(

12、Last In First Out-LIFO)或先进后出(First In Last Out-FILO),DCS of SUSE,二、队列的概念队列（Queue）是限定仅在一端插入,另一端删除的线性表。允许插入的一端叫队尾(rear),允许删除的一端叫队头(front),不含元素的空表称为空队列队列的运算特性是先进先出(First In First Out-FIFO),DCS of SUSE,插入、删除操作,栈：Push(&S,x)Pop(&S,&e)GetTop(S,&e)StackEmpty(S)队列：Que ueEmpty(Q)EnQueue(&Q，e)DeQueue(&Q,&e)Get

13、Head(Q,&e),DCS of SUSE,第4章 串,要点：基本概念和朴素模式匹配算法,模式匹配算法朴素的串匹配算法int Index(sstring S,sstring T,int pos)/返回子串T在主串S中从第pos个字符开始的位置/要求T非空，1pos Strlength(S)i=pos;j=1;while(i Strlength(T)return(iStrlength(T);return 0;/Index,算法时间复杂度?,O(n*m)，其中n、m分别为主串和子串长度,DCS of SUSE,第5章 数组和广义表,要点：数组基本概念和特殊矩阵的压缩存贮,LOC(aij)=LOC

14、(a11)+(i-1)*n+j-1*d,对称矩阵,数组B,ai,j,an,n,k,m,下标,k=?m=?,DCS of SUSE,第6章 树与二叉树,要点：（1）二叉树的性质、推论及应用 性质1、性质2、性质3、性质4、性质5（2）完全二叉树的概念及特点（3）二叉树的遍历（4）线索二叉树的基本概念和数据结构（5）树、森林与二叉树的转换，及相关特点（6）Huffman 树及Huffman编码,DCS of SUSE,树的基本术语1.树的结点:包含一个DE和指向其子树的所有分支;2.结点的度:一个结点拥有的子树的个数,度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I)含义

15、:树中最大分支数为树的度;4.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度5.森林:是m(m=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换.,结论：一棵树的各结点的度之和，等于该树的分支数目。,DCS of SUSE,二叉树性质(扩展要求掌握各性质的推论)性质1.在二叉树的第i层上至多有2i-1个结点(i1)。性质2.深度为k的二叉树至多有2k-1个结点(k1)。（深度一定，二叉树的最大结点数也确定）性质3.二叉树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+1性质4.结点数为n的完全

16、二叉树，其深度为 log2n+1,DCS of SUSE,性质5.在按层序编号的n个结点的完全二叉树中，任意一结点i(1in)有：i=1时，结点i是树的根；否则(i1)，结点i的双亲为结点i/2。2in时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。2i+1n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。性质6.含有n个结点的二叉链表中，有n+1个空链域。,重点说明：对于前4个性质，要求能推广到多叉树。,DCS of SUSE,二叉树的遍历,遍历顺序：DLR，LDR，LRD，层序遍历,D,L,R,根结点,根的左子树,根的右子树,DCS of SUSE,线索二叉树：结点结

17、构在二叉链表中增加 ltag 和 rtag 两个标志域,若结点有左子树，则左链域lchild指示其左孩子（ltag=0）；否则，令左链域指示其前驱（ltag=1）；若结点有右子树，则右链域rchild指示其右孩子（rtag=0）；否则，令右链域指示其后继（rtag=1）；,DCS of SUSE,树与二叉树的转换,借助于“孩子兄弟表示法”实现树与二叉树之间的转化,DCS of SUSE,森林转化为二叉树,B,结论：从根开始，沿右指针前进，结点个数对应原森林中树的数目。,DCS of SUSE,赫夫曼编码,已知某系统在通信联络中只可能出现8种字符，其概率如下表所示:,a,g,c,d,h,e,f,

18、b,最优二叉树,0,1,0,0,0,0,0,0,1,1,1,1,1,1,a:0010,b:11,c:1010,d:1011,e:100,f:01,g:0011,h:000,a,b,c,d,e,f,g,h,DCS of SUSE,第7章 图,要点：（1）图的邻接矩阵和邻接表表示 特点及关系（2）最小生成树及算法（3）完全图基本概念、拓扑排序的基本概念和特点、,DCS of SUSE,一、数组表示法（邻接矩阵）,设图G=（V，E）有n个顶点，则G的邻接矩阵定义为n阶方阵A。其中：Ai，j=1 若（vi，vj）或 E，ij 0 其它,无向图的邻接矩阵为对称矩阵,DCS of SUSE,特点：判定两个

19、顶点Vi与Vj是否关联,只需判Ai,j是否为1 顶点的度容易求得:,DCS of SUSE,二、邻接表（adjacency list）,如图G2的邻接表为：,特点：设无向图中顶点数为n，边数为e，则它的邻接表需要n个头结点和2e个表结点。顶点Vi的度 TD（Vi）=链表i中的表结点数。,DCS of SUSE,二、邻接表（adjacency list）,2.有向图邻接表,与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为弧尾的各个弧头顶点,特点：1.n个顶点，e条弧的有向图，需n个表头结点，e 个表结点 2.第i条链表上的结点数，为Vi的出度（求顶点的出度易，求入度难）,如图G1的邻

20、接表为：,DCS of SUSE,图的遍历,一、深度优先搜索（depth-first-search),如图G4：,二、广度优先搜索（breadth-first-search),首先访问指定顶点v0，将v0作为当前顶点;访问当前顶点的所有未访问过的邻接点，并依次将访问的这些邻接点作为当前顶点;重复2，直到所有顶点被访问为止。,DCS of SUSE,最小生成树概念1.设无向连通图G=（V，E），其子图G=（V，T）满足：V(G)=V(G)n个顶点 G是连通的 G中无回路则G是G的生成树,DCS of SUSE,普里姆（Prim）最小生成树算法,1.TE=,U=u02.当UV，重复下列步骤：(1)

21、选取（u0,v0)=mincost(u,v)|uU,vV-U，保证不形成回路(2)TE=TE+（u0,v0),边（u0,v0)并入TE(3)U=U+V0，顶点V0 并入U,特点:以连通为主选代价最小的邻接边,顶点加入序列：V1，V3，V6，V4，V2，V5,顶点逐个加入,DCS of SUSE,克鲁斯卡尔（Kruskal）最小生成树算法,步骤(v,u)E T,1(1,3),0,1,3(2,5),2(4,6),5(1,4),4(3,6),6(2,3),边数=n-1=5代价=(1+2+3+4+5)=15,DCS of SUSE,拓扑排序(topological sort)拓扑排序是一种对非线性结构

22、的有向图进行线性化的重要手段,AOV网可解决如下两个问题：（1）判定工程的可行性。显然，有回路，整个工程就无法结束（2）确定各项活动在整个工程执行中的先后顺序。称这种先后顺序为拓扑有序序列。,如图有如下拓扑有序序列：a1 a2 a3a4 a6 a5 a7 a8 a9 a2 a6 a1 a3 a4 a5 a7 a9 a8,DCS of SUSE,第9章 查找,要点：（1）基本概念（2）有序表查找(二分查找，或折半查找)思想、算法（3）哈希查找基本概念及冲突解决方法(链地址法，公共溢出区法)(4)二叉排序树的特点,DCS of SUSE,查找:在查找表中确定与给定值相等的DE的过程.查找结果:查找

23、成功(table 中存在给定值的记录)查找不成功(table 中不存在给定值的记录),查找表分为:静态查找表(对查找表中的数据元素不进行插入和删除操作)动态查找表(对查找表中的数据元素可进行插入和删除操作),DCS of SUSE,有序表的查找有序表:查找表中记录按关键字有序排列的表.即:ST.elemi.key=ST.elemi+1.key i=1,2,n-1折半查找:要求:查找表为有序表;查找过程:先确定待查记录范围;然后逐步缩小范围;直到:查找成功或不成功.,DCS of SUSE,折半查找算法 int Search_Bin(SSTable ST,KeyType key);low=1;h

24、igh=ST.length;while(low=high)mid=(low+high)/2;if(EQ(key,ST.elemmid.key)return mid;else if(LT(key,ST.elemmid.key)high=mid-1;else low=mid+1;return 0;/Search_Bin,折半查找算法（递归实现）int Search_Bin(SSTable ST,int low,int high,KeyType key);if(low=high)mid=(low+high)/2;if(EQ(key,ST.elemmid.key)return mid;else if(

25、LT(key,ST.elemmid.key)return Search_Bin(ST,low,mid-1,key);else return Search_Bin(ST,mid+1,high,key);else return 0;/Search_Bin,DCS of SUSE,链地址法 将关键字发生冲突的记录存储在同一个线性链表中。例：H（key）=key mod 13 对关键字19，14，23，01，68，20，84，27，55，11，10，79 处理的结果为：,DCS of SUSE,公共溢出区法将同哈希表中关键字发生冲突的所有记录填入一个溢出表中.例如上例的结果为：,DCS of SUSE

26、,第10章 内部排序,要点：（1）快速排序操作（2）堆排序（基本概念，排序过程）,排序(Sorting):将数据元素(或记录)的一个任意序列,重新排列成一个按关键字有序的序列。排序方法的稳定性：对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称该排序方法是稳定的。反之，称该排序方法是不稳定的。,DCS of SUSE,快速排序-对冒泡排序的一种改进,基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分记录继续分别进行排序，以达到整个序列有序。,DCS of SUSE,快速排序举例,初始关键字：49，38，65，97，76，

27、13，27，49,一趟完成后：27，38，13，49，76，97，65，49,DCS of SUSE,堆排序,堆的定义：n个元素的序列k1,k2,.,kn当且仅当满足下列条件时，称之为堆。,堆举例：96,83,27,38,11,09)12,36,24,85,47,30,53,91,完全二叉树,且所有非叶结点的值均不大于(不小于)其左、右孩子结点的值,小顶堆,大顶堆,DCS of SUSE,无序序列建成一个堆（从第n/2到1个元素）49，38，65，97，76，13，27，49,DCS of SUSE,试卷题型,一、单项选择题（20分）二、填空题（20分）三、判断题（10分）四、算法阅读及分析（10分）五、综合应用题（30分）六、算法设计（10分）,