数据结构基础讲义

1、数据结构,-肖兴贵,传智播客,1概要2线性表3栈和队列4树和二叉树5查找和排序,主要内容,1.1讨论的范畴,算法+数据结构=程序设计,处理问题的策略,给出问题的数学模型,编制出的指令集处理问题用计算机,问题,构建数学模型,程序实现,1.1讨论的范畴,例1求小红C语言和数据结构两门语言的考试的平均成绩成绩和总成绩。全省的呢？例2酒店管理中的客房分配问题。例3煤气管道的铺设问题。等等例子中的数学模型正是数据结构要讨论的问题。,1.2定义,数据结构是一门讨论描述现实世界实体的数学模型及其上的操作在计算机中如何表示和实现的学科。a.在解决问题时可能遇到的典型的逻辑结构（数据结构）b.逻辑结构的存储映象

2、（存储实现）c.数据结构的相关操作及其实现。(算法)通俗点讲，数据结构研究的是数据的存储和操作。,1.3三个方面,1.3逻辑和物理结构,逻辑结构,物理结构,数学模型集合和关系数据和信息数据元素数据项关键码抽象数据类型,1.4相关概念,算法是特定问题求解步骤的描述，在计算机中表现为指令的有限序列，算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。数据结构和算法的关系：数据结构是专门研究数据的存储问题，而对存储后的数据进行相应的操作就是算法。,1.5算法的定义,1.5算法效率的度量,我们通过大O表示法来表示算法的效率：时间复杂度、空间复杂度。规则如下：（1）只关注

3、最高次项，常数项和次要项忽略；（2）时间复杂度是指最坏时间复杂度；（3）只有常数项记做1。,1.6时间复杂度举例,线性阶：O(n),平方阶:O(n2),1.6空间复杂度举例,空间复杂度：O(n),2.1线性表概念,线性结构的基本特点是节点之间满足线性关系。数组、链表、栈、队列都属于线性结构。他们的共同之处，是节点中有且只有一个开始节点和终端节点。他们分别属于几种不同的抽象数据类型实现，它们之间的区别，主要就是操作的不同。线性表是零个或者多个数据元素的有限序列，数据元素之间是有顺序的，数据元素个数是有限的，数据元素的类型必须相同,2.1编程实战,动态数组数组到底应该有多大才合适，通常不得而知。所

4、以希望能够在运行时具有改变数组大小的能力。（基本操作：创建、销毁、插入、删除、遍历打印）单向链表,2.3编程实战,经典双向链表主要操作：初始化头结点、添加、删除、获取元素、遍历,Q1.创建两循环单向链表并将它们合为一各链表？Q2.头指针和头节点有什么区别？头结点和其他节点有什么区别？,第1天习题,3.1栈的特点,栈为一种可以实现“先进后出”的存储结构，凡是对数据的处理具有“后进先出(LIFO)”的特点，都可以用栈这种数据结构来操作。栈的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。,3.2编程实战,栈的顺序存储利用一组地址连续的的存储单元依次存放自栈底到栈顶的数据元素，同

5、时附设指针top只是栈顶元素在顺序表中的位置。栈的链式存储,3.4队列的特点,队列为一种可以实现“先进先出”(FIFO)的存储结构。队列是一种特殊的受限制的线性表，只允许在一端进行插入操作，而在另一端进行删除操作的线性表，队列不允许在中间部位进行操作。,3.5编程实战,队列的顺序存储,3.6编程实战,队列的链式存储,Q1.假设以带头结点的循环链表表示队列，并又只设一个指针指向队尾元音结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。Q2.假设称正读和反读都相同的字符序列为“回文”，例如，”aba”和”abcba”是回文，”abcde”和”ababab”则不是回文。试写一个算

6、法判别读入的一个以“”为结束符的字符序列是否是“回文”。,第2天习题,4.1树的定义,定义：-由一个或多个结点组成的有限集合T，有且仅有一个结点称为根，其余的结点分为m个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。树的特点：非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）树的定义具有递归性，树中还有树树可以为空，即节点个数为0,4.2树的术语,4.3树的表示法,4.4树的表示法,4.5二叉树的概念,二叉树由一个根结点加上两棵分别称为左子树和右子树的互不相交的树组成：每个结点最多只有两棵子树（不存在度大于2的结点）左子树和右子树次序不能颠倒（有序树）,

7、4.6树转化为二叉树,左孩子右兄弟表示法可以将一颗多叉树转化为一颗二叉树。,4.7满二叉树和完全二叉树,4.7树的顺序存储,多叉树顺序存储的缺陷,4.7完全二叉树的顺序存储,非完全二叉树存储缺点：浪费空间；插入、删除不便,完全二叉树存储,4.7二叉树的链式存储,二叉链存储,4.7二叉树的链式存储,三叉链存储,4.8二叉树的遍历,遍历是指按某条搜索路线遍访每个结点且不重复（又称周游），遍历是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。牢记一种约定，对每个结点的查看都是“先左后右”。,4.8二叉树的遍历,4.8编程实战,二叉树的动态创建和释放二叉树的递归遍历计算二叉

8、树叶子节点数目计算二叉树高度,第3天习题,Q1编写递归算法，在二叉树中求位于先序序列中第A个位置的结点的值。Q2编写递归算法，计算二又树中叶子结点的数目。Q3编写递归算法，将二叉树中所有结点的左、右子树相互交换。,5.1查找的概念,根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的一个记录，则称查找是成功的。,5.2编程实战,顺序查找二分查找,5.3排序的概念,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。排序是高效查询的前提。,5.4编程实战,冒泡选择插入排序,5.5排序算法比较,第4天习题,Q1编写一个双向起泡的排序算法，即相邻两遍分别向相反方向起泡。Q2当记录序列基本有序时，用哪种排