数据结构基础讲义学习教案.pptx

《数据结构基础讲义学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构基础讲义学习教案.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)基础讲义基础讲义第一页，共45页。n n1 1 概要概要n n2 2 线性表线性表n n3 3 栈和队列栈和队列n n4 4 树和二叉树树和二叉树 n n5 5 查找查找(ch zho)(ch zho)和排序和排序主要主要(zhyo)内容内容第1页/共45页第二页，共45页。1.1 1.1 讨论讨论讨论讨论(t(t oln)oln)的范畴的范畴的范畴的范畴算法+数据结构(sh j ji u)=程序设计 处理问题的策略给出问题的数学模型编制出的指令集处理问题用计算机问题问题(wnt)(wnt)构建数学模型构建数学模型程序实现程序实现第2页/共45页第

2、三页，共45页。1.1 1.1 讨论讨论讨论讨论(t(t oln)oln)的范畴的范畴的范畴的范畴n n例例1 1 求小红求小红C C语言和数据结构两门语言的考试的平均成绩语言和数据结构两门语言的考试的平均成绩成绩和总成绩。全省的呢？成绩和总成绩。全省的呢？n n例例2 2 酒店管理中的客房分配问题。酒店管理中的客房分配问题。n n例例3 3 煤气管道的铺设问题。煤气管道的铺设问题。n n等等等等(dn(dn dn dn)n n 例子中的数学模型正是数据结构要讨论的问题。例子中的数学模型正是数据结构要讨论的问题。第3页/共45页第四页，共45页。1.2 1.2 定义定义定义定义(dngy)(d

3、ngy)n n数据结构是一门讨论数据结构是一门讨论 描述现实世界实体的数学模型描述现实世界实体的数学模型及其上的操作在计算机中如何表示和实现及其上的操作在计算机中如何表示和实现 的学科。的学科。n n n na.a.在解决问题时可能遇到的典型的逻辑结构（数据结在解决问题时可能遇到的典型的逻辑结构（数据结构）构）n nb.b.逻辑结构的存储映象（存储实现）逻辑结构的存储映象（存储实现）n nc.c.数据结构的相关操作及其实现。数据结构的相关操作及其实现。(算法算法(sun f(sun f)n n通俗点讲，数据结构研究的是数据的存储和操作。通俗点讲，数据结构研究的是数据的存储和操作。第4页/共45

4、页第五页，共45页。1.3 1.3 三个方面三个方面三个方面三个方面(fngmin)(fngmin)数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：查找、排序、插入、删除、修改等数据的运算：查找、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构第5页/共45页第六页，共45页。1.3 逻辑和物理逻辑和物理(wl)结构结构逻辑逻辑(lu j)(lu j)结构结构物理(wl)结构第6页/共45页第七页，共45页。n n数学模型数学模型n n集合集合(jh)(jh)和

5、关系和关系n n数据和信息数据和信息n n数据元素数据元素n n数据项数据项n n关键码关键码n n抽象数据类型抽象数据类型1.4 1.4 相关相关相关相关(xinggun)(xinggun)概念概念概念概念第7页/共45页第八页，共45页。n n算法是特定问题求解步骤的描述，在计算机中表算法是特定问题求解步骤的描述，在计算机中表现为指令的有限序列，算法是独立现为指令的有限序列，算法是独立(dl)(dl)存在的存在的一种解决问题的方法和思想。对于算法而言，语一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。言并不重要，重要的是思想。n n数据结构和算法的关系：数据结构是专门研

6、究数数据结构和算法的关系：数据结构是专门研究数据的存储问题，而对存储后的数据进行相应的操据的存储问题，而对存储后的数据进行相应的操作就是算法。作就是算法。1.5 算法算法(sun f)的定义的定义第8页/共45页第九页，共45页。1.5 1.5 算法效率算法效率算法效率算法效率(xio l(xio l)的度量的度量的度量的度量n n我们通过大我们通过大OO表示法来表示算法的效率表示法来表示算法的效率(xio l(xio l)：时间复杂度、空间复杂度。规则如下：时间复杂度、空间复杂度。规则如下：n n（1 1）只关注最高次项，常数项和次要项忽略；）只关注最高次项，常数项和次要项忽略；n n（2

7、2）时间复杂度是指最坏时间复杂度；）时间复杂度是指最坏时间复杂度；n n（3 3）只有常数项记做）只有常数项记做1 1。执行次数函数执行次数函数阶阶非正式术语非正式术语12O(1)常数阶2n+3O(n)线性阶3n2+2n+1O(n2)平方阶5log2n+20O(logn)对数阶2n+3nlog2n+19O(nlogn)nlogn阶6n3+2n2+3n+4O(n3)立方阶2nO(2n)指数阶第9页/共45页第十页，共45页。1.6 1.6 时间时间时间时间(shjin)(shjin)复杂度举例复杂度举例复杂度举例复杂度举例n n线性阶：线性阶：O(n)O(n)平方(pngfng)阶:O(n2)第

8、10页/共45页第十一页，共45页。1.6 1.6 空间空间空间空间(kngjin)(kngjin)复杂度举例复杂度举例复杂度举例复杂度举例n n空间空间(kngjin)(kngjin)复杂度：复杂度：O(n)O(n)第11页/共45页第十二页，共45页。2.1 2.1 线性表概念线性表概念线性表概念线性表概念(ginin)(ginin)n n线性结构的基本特点是节点之间满足线性关系。数组、链表、栈、线性结构的基本特点是节点之间满足线性关系。数组、链表、栈、队列都属于线性结构。他们的共同之处，是节点中有且只有一个队列都属于线性结构。他们的共同之处，是节点中有且只有一个(y(y )开始节点和终端

9、节点。他们分别属于几种不同的抽象数据类开始节点和终端节点。他们分别属于几种不同的抽象数据类型实现，它们之间的区别，主要就是操作的不同。型实现，它们之间的区别，主要就是操作的不同。n n线性表是零个或者多个数据元素的有限序列，数据元素之间是有顺线性表是零个或者多个数据元素的有限序列，数据元素之间是有顺序的，数据元素个数是有限的，数据元素的类型必须相同序的，数据元素个数是有限的，数据元素的类型必须相同第12页/共45页第十三页，共45页。2.1 2.1 编程实战编程实战编程实战编程实战(shzhn)(shzhn)n n动态数组动态数组n n数组到底应该有多大才合适，通常不得而知数组到底应该有多大才

10、合适，通常不得而知(b d r zh)(b d r zh)。所以希望能够在运行时具有。所以希望能够在运行时具有改变数组大小的能力。（基本操作：创建、改变数组大小的能力。（基本操作：创建、销毁、插入、删除、遍历打印）销毁、插入、删除、遍历打印）n n单向链表单向链表 第13页/共45页第十四页，共45页。2.3 2.3 编程实战编程实战编程实战编程实战(shzhn)(shzhn)n n经典双向链表经典双向链表n n主要操作：初始化头结点、添加、删除、获取元素主要操作：初始化头结点、添加、删除、获取元素(yun s)(yun s)、遍历、遍历第14页/共45页第十五页，共45页。n nQ1.Q1.

11、创建两循环单向链表并将它们合为一各链表？创建两循环单向链表并将它们合为一各链表？n nQ2.Q2.头指针和头节点有什么区别？头结点头指针和头节点有什么区别？头结点(ji din)(ji din)和其他节点有什么区和其他节点有什么区别？别？第第第第1 1天天天天 习题习题习题习题(xt)(xt)第15页/共45页第十六页，共45页。3.1 3.1 栈的特点栈的特点栈的特点栈的特点(tdi(tdi n)n)n n栈为一种可以实现栈为一种可以实现“先进后出先进后出”的存储结构，的存储结构，凡是对数据的处理具有凡是对数据的处理具有“后进先出后进先出(LIFO)”(LIFO)”的的特点，都可以用栈这种数

12、据结构来操作。特点，都可以用栈这种数据结构来操作。n n栈的特殊之处在于限制栈的特殊之处在于限制(xinzh)(xinzh)了这个线性表了这个线性表的插入和删除的位置，它始终只在栈顶进行。的插入和删除的位置，它始终只在栈顶进行。第16页/共45页第十七页，共45页。3.2 3.2 编程实战编程实战编程实战编程实战(shzhn)(shzhn)n n栈的顺序存储栈的顺序存储n n利用一组地址连续的的存储单元利用一组地址连续的的存储单元(cn(cn chch dn yun)dn yun)依次存放自栈底到栈顶的依次存放自栈底到栈顶的数据元素，同时附设指针数据元素，同时附设指针toptop只是栈顶只是栈

13、顶元素在顺序表中的位置。元素在顺序表中的位置。n n栈的链式存储栈的链式存储第17页/共45页第十八页，共45页。3.4 3.4 队列队列队列队列(duli)(duli)的特点的特点的特点的特点n n队列队列(duli)(duli)为一种可以实现为一种可以实现“先进先出先进先出”(FIFO)”(FIFO)的存储结构。的存储结构。n n队列队列(duli)(duli)是一种特殊的受限制的线性表，只允是一种特殊的受限制的线性表，只允许在一端进行插入操作，而在另一端进行删除操作许在一端进行插入操作，而在另一端进行删除操作的线性表，队列的线性表，队列(duli)(duli)不允许在中间部位进行操不允许

14、在中间部位进行操作。作。第18页/共45页第十九页，共45页。3.5 3.5 编程实战编程实战编程实战编程实战(shzhn)(shzhn)队列(duli)的顺序存储第19页/共45页第二十页，共45页。3.6 3.6 编程实战编程实战编程实战编程实战(shzhn)(shzhn)队列(duli)的链式存储第20页/共45页第二十一页，共45页。n nQ1.Q1.假设假设(jish)(jish)以带头结点的循环链表表示队列，并又只设一个指针指向队以带头结点的循环链表表示队列，并又只设一个指针指向队尾元音结点尾元音结点(注意不设头指针注意不设头指针)，试编写相应的队列初始化、入队列和出队列的，试编写

15、相应的队列初始化、入队列和出队列的算法。算法。n nQ2.Q2.假设假设(jish)(jish)称正读和反读都相同的字符序列为称正读和反读都相同的字符序列为“回文回文”，例如，例如，”aba”aba”和和”abcba”abcba”是回文，是回文，”abcde”abcde”和和”ababab”ababab”则不是回文。试则不是回文。试写一个算法判别读入的一个以写一个算法判别读入的一个以“”“”为结束符的字符序列是否是为结束符的字符序列是否是“回文回文”。第第第第2 2天天天天 习题习题习题习题(xt)(xt)第21页/共45页第二十二页，共45页。4.1 4.1 树的定义树的定义树的定义树的定义

16、(dngy)(dngy)n n定义：定义：n n-由一个由一个(y)(y)或多个结点组成的有限集合或多个结点组成的有限集合T T，有且，有且仅有一个仅有一个(y)(y)结点称为根，其余的结点分为结点称为根，其余的结点分为m m个互不个互不相交的有限集合相交的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵。每个集合本身又是棵树，被称作这个根的子树。树，被称作这个根的子树。n n树的特点：树的特点：n n非线性结构，有一个非线性结构，有一个(y)(y)直接前驱，但可能有多个直接前驱，但可能有多个直接后继（直接后继（1:n1:n）n n树的定义具有递归性，树中还有树树的定义具有递归性，树

17、中还有树n n树可以为空，即节点个数为树可以为空，即节点个数为0 0第22页/共45页第二十三页，共45页。4.2 4.2 树的术语树的术语树的术语树的术语(shy(shy)专业术语专业术语含义含义根也叫根结点(没有前驱)叶子也叫终端结点(没有后继)森林指m棵不相交的树的集合(例如删除A后的子树个数)有序树结点各子树从左至右有序，不能互换（左为第一）无序树结点各子树可互换位置双亲 即上层的那个结点(直接前驱)parent孩子即下层结点的子树(直接后继)child兄弟同一双亲下的同层结点（孩子之间互称兄弟）sibling堂兄弟即双亲位于同一层的结点（但并非同一双亲）cousin祖先即从根到该结点

18、所经分支的所有结点子孙即该结点下层子树中的任一结点结点也叫节点，即树的数据元素结点的度、树的度结点挂接的子树数、所有结点度中的最大值结点的层次从根到该结点的层数（根结点算第一层）终端结点即度为0的结点，即叶子 分支结点除树根以外的结点（也称为内部结点）树的深度(或高度)指所有结点中最大的层数(从根节点到最低层的结点层数)第23页/共45页第二十四页，共45页。4.3 4.3 树的表示法树的表示法树的表示法树的表示法第24页/共45页第二十五页，共45页。4.4 4.4 树的表示法树的表示法第25页/共45页第二十六页，共45页。4.5 4.5 二叉树的概念二叉树的概念二叉树的概念二叉树的概念(

19、ginin)(ginin)n n二叉树由一个根结点加上两棵分别称为二叉树由一个根结点加上两棵分别称为(chn wi)(chn wi)左左子树和右子树的互不相交的树组成：子树和右子树的互不相交的树组成：n n每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）的结点）n n左子树和右子树次序不能颠倒（有序树）左子树和右子树次序不能颠倒（有序树）第26页/共45页第二十七页，共45页。4.6 4.6 树转化树转化树转化树转化(zhu(zhu nhu)nhu)为二叉树为二叉树为二叉树为二叉树n n左孩子右兄弟左孩子右兄弟(xingd)(xingd)表示法可以将一

20、颗多叉树转化表示法可以将一颗多叉树转化为一颗二叉树。为一颗二叉树。第27页/共45页第二十八页，共45页。4.7 4.7 满二叉树和完全满二叉树和完全满二叉树和完全满二叉树和完全(wnqun)(wnqun)二叉树二叉树二叉树二叉树第28页/共45页第二十九页，共45页。4.7 4.7 树的顺序存储树的顺序存储树的顺序存储树的顺序存储n n多叉树顺序存储的缺陷多叉树顺序存储的缺陷(quxin)(quxin)第29页/共45页第三十页，共45页。4.7 完全完全(wnqun)二叉树的顺序存储二叉树的顺序存储非完全二叉树存储缺点：非完全二叉树存储缺点：浪费空间；浪费空间；插入插入(ch(ch r)r

21、)、删除不便、删除不便完全(wnqun)二叉树存储第30页/共45页第三十一页，共45页。4.7 4.7 二叉树的链式存储二叉树的链式存储二叉树的链式存储二叉树的链式存储(cn ch(cn ch)二叉链存储(cn ch)第31页/共45页第三十二页，共45页。4.7 二叉树的链式存储二叉树的链式存储(cn ch)三叉链存储(cn ch)第32页/共45页第三十三页，共45页。4.8 4.8 二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历(bin l)(bin l)遍历是指按某条搜索路线遍访每个结点且不重复（又称周游），遍历是树结构插入、删除、修改、查找和排序运算(yn sun)的前提，是二叉

22、树一切运算(yn sun)的基础和核心。牢记一种约定，对每个结点的查看都是“先左后右”。遍历方式遍历方式特点特点先序遍历(先根遍历，DLR)根-左子树-右子树中序遍历(中根遍历，LDR)左子树-根-右子树后序遍历(后根遍历，LRD)左子树-右子树-根第33页/共45页第三十四页，共45页。4.8 4.8 二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历(bin l)(bin l)第34页/共45页第三十五页，共45页。4.8 4.8 编程实战编程实战编程实战编程实战(shzhn)(shzhn)二叉树的动态创建和释放二叉树的递归遍历计算二叉树叶子节点数目(shm)计算二叉树高度第35页/共45页

23、第三十六页，共45页。第第第第3 3天天天天 习题习题习题习题(xt)(xt)n nQ1 Q1 编写递归算法，在二叉树中求位于先序序列中第编写递归算法，在二叉树中求位于先序序列中第A A个位置的结点的个位置的结点的值。值。n nQ2 Q2 编写递归算法，计算编写递归算法，计算(j sun)(j sun)二又树中叶子结点的数目。二又树中叶子结点的数目。n nQ3 Q3 编写递归算法，将二叉树中所有结点的左、右子树相互交换。编写递归算法，将二叉树中所有结点的左、右子树相互交换。第36页/共45页第三十七页，共45页。5.1 5.1 查找查找查找查找(ch zh(ch zh o)o)的概念的概念的概

24、念的概念n n根据给定的某个值，在查找根据给定的某个值，在查找(ch zho)(ch zho)表中确定一个其关键表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的一个记字等于给定值的记录或数据元素，若表中存在这样的一个记录，则称查找录，则称查找(ch zho)(ch zho)是成功的。是成功的。第37页/共45页第三十八页，共45页。5.2 5.2 编程实战编程实战编程实战编程实战(shzhn)(shzhn)顺序查找(ch zho)二分查找(ch zho)第38页/共45页第三十九页，共45页。5.3 5.3 排序排序排序排序(pi x)(pi x)的概念的概念的概念的概念n n

25、排序是计算机内经常进行的一种排序是计算机内经常进行的一种(y zhn)(y zhn)操作，其操作，其目的是将一组目的是将一组“无序无序”的数据元素调整为的数据元素调整为“有序有序”的数的数据元素。排序是高效查询的前提。据元素。排序是高效查询的前提。第39页/共45页第四十页，共45页。5.4 编程实战编程实战(shzhn)冒泡选择(xunz)插入排序第40页/共45页第四十一页，共45页。5.5 排序算法排序算法(sun f)比较比较第41页/共45页第四十二页，共45页。第第4天天 习题习题(xt)n nQ1 Q1 编写一个双向起泡的排序算法，即相邻两遍分别向相反方向起泡。编写一个双向起泡的

26、排序算法，即相邻两遍分别向相反方向起泡。n nQ2 Q2 当记录序列基本有序时，用哪种排序才法效率较高当记录序列基本有序时，用哪种排序才法效率较高?简单选择排序简单选择排序与起泡排序两者在什么与起泡排序两者在什么(shn me)(shn me)情况下的执行效率差别较大情况下的执行效率差别较大?n nQ3 Q3 画出对长度为画出对长度为1010的有序表进行折半查找的判定树，并求其等概率时的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。查找成功的平均查找长度。第42页/共45页第四十三页，共45页。谢谢(xi xie)大家！第43页/共45页第四十四页，共45页。6 学习学习(xux)拓展拓展n n图和广义图和广义(gu(gu ngy)ngy)表表n n文件文件实战吧，实践(shjin)出真知！肖兴贵第44页/共45页第四十五页，共45页。