数据结构与算法2

第一章数据结构与算法主要内容1.1算法与数据结构概念

1.2线性表1.3栈和队列1.4树和二叉树

1.5查找1.6内部排序1.1.1算法的根本概念定义：解题方案的准确而完整描述。特点(四个)：(一般填空题或选择题)有穷性：包含有限个操作步骤，每个步骤都能在有限时间内完成。确定性：每一条指令无二义性。〔相同输入只能得到相同输出〕可行性：指定操作都可以实现。拥有足够的情报：有输入有输出。〔涵盖面广〕算法：是一组严谨地定义运算顺序的规那么，并且每个规那么都是有效的、明确的，此顺序在有限的次数下终止。2.算法根本要素及描述根本要素：算法中对数据的运算和操作(算术运算、逻辑运算、关系运算、数据传输)算法的控制结构算法的控制结构：顺序、选择、循环。3.算法的设计方法(1)列举法：列举出所有可能情况，用给定条件检验哪些是需要的，哪些是不需要的。例：百钱百鸡问题。(2)归纳法：列举少量简单而又特殊的情况，分析归纳出一般结论。(3)递推法：从初始条件出发，逐步推出各种中间结果和最后结果。例：猴子摘桃子问题。(5)回溯法：尝试。分析找出解决线索，逐步试探成功：求得解失败：逐步回推，换线索再试探。(4)递归法：解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决了最后简单问题后，再沿原来的逆过程逐步综合。例：求3！。(6)减半递推技术：减少：问题规模减半，而性质不变递推：重复减半的过程例：二分查找〔游戏猜数字〕1.1.2算法复杂度评价算法标准：时间复杂度和空间复杂度。

1算法的时间复杂度：定义：算法运行从开始到结束所需要的计算工作量。计算工作量：算法执行过程中所需要的根本运算的执行次数。算法的时间复杂度不仅依赖于问题的规模，也取决于输入实例的初始状态。

平均时间复杂度：所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。最坏时间复杂度：最坏情况下算法的时间复杂度。最优算法：随n的增大，T(n)增长较慢的算法。2算法的空间复杂度：定义：算法运行从开始到结束所需的存储空间量。一个算法在执行时所占的空间包括算法程序所占的空间、输入数据所占的存储空间以及算法执行过程中所需要的额外空间。用While语句求计算：s=1+2+3+…+100，代码如下。main(){inti=1,s=0;while(i<=100){s=s+ii=i+1}}printf(“%d〞,s);此算法的时间复杂度为：1+2*100+1=202空间复杂度为：2假设100改为n,那么时间复杂度为:o(2n+2)1.2数据结构根本概念1.2.1数据结构的定义(1)数据：信息载体，能够被计算机识别、存储和加工处理。可以是数值数据(整数、实数)，也可以是非数值数据(声音、图像等)。(2)数据元素：数据的根本单位，在计算机程序中通常作为一个整体进行考虑和处理(又称结点、记录)。数据模型包括数据结构、数据操作和数据约束。数据项：一个数据元素由假设干数据项组成，数据的不可分割的最小单位。关键码：其值能唯一确定一个数据元素的数据项。举例：图书管理系统数据元素数据项关键码书目信息中的一本书书目信息的每一项书号VisualBasic6.0作者(或出版社或定价)978-7(3)数据结构：定义：相互之间存在着一种或多种关系的数据元素的集合。研究内容:(记住两种结构)如:(2-1空)①数据的逻辑结构：各数据元素之间的逻辑关系；②数据的存储结构：各数据元素在计算机中的存储关系；③对各种数据结构进行的运算：添加，删除，排序等。1.数据的逻辑结构四类根本逻辑结构：(1)集合结构：数据元素间的关系是“属于同一个集合〞。(2)线性结构：数据元素之间存在一个对一个的关系。(3)树形结构：数据元素之间存在一个对多个的关系。(4)图形结构：数据元素之间存在多个对多个的关系。学号姓名系别住址电话…...981111李洪机械六舍5371111982111王刚电子四舍5372111983211王将计算机五舍5373211983212张强机械六舎5372221…………………………线性结构树型结构学校教研室部、处实验室医学院计算机…线性结构与非线性结构概念结点：组成数据结构的数据元素称为一个结点。前后件关系：数据元素之间的固有关系可以用前后件关系(前驱与后继关系)描述。举例：家庭成员辈分关系(父亲、儿子、女儿)，“父亲〞是“儿子〞和“女儿〞的前件，“儿子〞和“女儿〞是“父亲〞后件。线性结构有且只有一个根结点每个结点最多有一个前件，也最多有一个后件非线性结构一个数据结构如果不是线性结构，那么称之为非线性结构。数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件。树型、图形结构属于非线性结构。2.数据的存储结构定义：数据的逻辑结构在计算机存储空间中的存放形式。

数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。实现方式：

(1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组来实现。(2)链式存储方式：对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现。(3)索引存储方法和散列存储方法〔为了查找方便〕。1.3线性表

线性表的根本概念定义：具有相同数据类型的n(n≥0)个数据元素组成的有限序列。最简单、最常用的数据结构。

结构特点：(1)有且只有一个根结点，无前驱

。(2)有且只有一个终端结点

，无后继。(3)其他结点有且只有一个直接前驱和一个直接后继。1.3.2线性表的顺序存储结构

顺序表：采用顺序存储结构的线性表称为顺序表(一维数组)。

顺序存储：用一组地址连续的存储空间依次存储线性表的各元素。特点(顺序存储结构)：表中的所有元素所占存储空间连续表中各元素在存储空间中按逻辑顺序存放

第i个元素地址：m：每个元素占m个存储单元Loc(a1)第一个元素地址(基址)

1.顺序表(线性表)根本概念顺序表的顺序存储结构存储地址内存状态元素在线性表中的位序bb+m...b+(i-1)m...b+(n-1)mb+nm...b+(maxlen-1)ma1a2......12...

i...n空闲aian2.顺序表根本运算根本运算：插入：在线性表指定位置插入一个新元素删除：删除线性表中指定的元素查找：在线性表中查找特定元素排序：线性表中元素按关键字升序或降序排序分解：将一个线性表分解为多个合并复制逆转

3插入运算：定义：是指在表的第i个位置上插入一个值为b的新元素原表长为n：(a1，a2，…ai-1，ai，ai+1，…

an)

新表长为n+1：(a1，a2，…ai-1，b，ai，ai+1，…，

an)

步骤：(1)将ai

~

an顺序向后移动,为新元素让出位置(2)将b置入空出的第i个位置举例：(在第4个和第5个元素之间插入元素91)67412621489160123456786741262148916012345678674126214891601234567891时间性能分析：插入运算，时间主要消耗在数据移动上。在长度为n的线性表中插入一个元素，那么平均移动元素次数：Pi：在第i个位置上作插入的概率。设Pi=1/(n+1)共需移动(n-i+1)个元素。4删除运算：定义：指将表中第i个元素从线性表中去掉。原表长为n：(a1，a2，…ai-1，ai

，ai+1，…

an)

新表长为n-1：(a1，a2，…ai-1，ai+1，…，

an)

步骤：(1)删除ai(2)将ai+1

~an

顺序向前移动举例：(删除第五个元素21)674126214891601234567867412648916012345678平均移动元素次数：5.顺序表优点和缺点优点：逻辑上相邻元素存储位置也相邻，无需增加额外存储空间；可方便随机存取表中任一元素。缺点：插入和删除运算不方便，必须移动大量结点，效率较低；不适合元素经常变动的大的线性表。链式存储结构的特点:每个结点由两局部组成：一局部存放数据，另一局部存储指向前件或后件结点的指针域。逻辑上相邻的结点物理上不必相连。数据运算〔插入和删除等〕灵活。1.3.3线性表的链式存储结构

结点组成：数据结构中每个数据结点对应一个存储单元，简称结点。

两局部：数据域：存放数据元素值指针域：存放指针，指向后继结点线性链表中用专门的HEAD指针指向第一个元素的结点，其最后一个元素没有后件，因此最后一个结点指针域为空〔用NULL或0表示〕。1线性链表定义：线性表的链式存储结构称为线性链表。

分类：单链表、循环单链表、双向链表2单链表定义：由n个结点链接，且每个结点中只包含一个指针域的链表。线性单链表(A,B,C,D,E,F)：逻辑状态：

ABCDEHF物理状态：E7FNULLB25A13C31D11713192531单链表存取：必须从头指针开始进行，依次顺着指针向链尾方向扫描。找到各个元素。(1)单链表插入：增加新结点,修改链接指针步骤：PBCXSA修改s指针域,s结点的后继是p结点的后继修改p指针域,使其指向新结点s(2)单链表删除：不需要移动元素,仅修改指针链接。步骤：先找到p的前驱结点q删除p结点，修改q结点指针域

q

next＝p

nextCPBA删除前P删除后qCBA1.4栈和队列

1.4.1栈

1.栈的定义〔用于子程序调用等〕只允许在线性表的一端进行插入和删除的线性表。

相关术语：(1)栈顶：允许插入与删除的一端称为栈顶。指针top指向栈顶位置。(2)栈底：不允许插入与删除的一端称为栈底。指针base指向栈底。(3)入栈：栈的插入操作(往栈中插入一个元素)(4)出栈：栈的删除操作(从栈中删除一个元素)(5)栈空：top=base(6)栈满：top=m(m为栈最大容量)栈示意图：原那么：先进后出或后进先出2顺序栈及其运算栈的两种存储结构：顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。链式存储结构：也称可利用栈。用于收集计算机存储器中所有空闲存储空间。顺序栈：顺序存储结构的栈称为顺序栈。链栈：链式存储结构栈称为链栈。根本运算：入栈、退栈与读栈顶元素(2)出栈步骤：栈顶元素赋给一个指定的变量。栈顶指针top减1。栈顶指针为0时，栈空，不能再退栈。称为栈“下溢〞错误。(1)入栈步骤：栈顶指针top加1。新元素插入到栈顶指针指向位置。栈顶指针指向存储空间最后一个位置时，栈已满，不能再入栈。称为栈“上溢〞错误。(3)读栈顶元素概念：将栈顶元素赋给一个指定变量。注意：不删除栈顶元素，栈顶指针不会改变。读栈顶元素和出栈区别？举例：topbottomABCDEF10987654321S(1:10)有6个元素的栈ABCDEFXYS(1:10)topbottom插入X和Y后的栈10987654321bottomABCDEFX10987654321S(1:10)top退出一个元素后的栈1.4.2队列

定义：指允许在一端插入，而在另一端进行删除的线性表。

相关术语(5个)：(1)队尾：允许插入的一端称为队尾。rear队尾指针，始终指向队尾元素的下一个位置。(2)队头：允许进行删除的一端称为队头。front队头指针，始终指向队头元素。(3)入队列：队列插入操作(进队列)(4)出队列：队列的删除操作(退队列)(5)空队列：队列中无数据元素原那么：先进先出或后进后出队头元素总是最先进队列的,也总是最先出队列队尾元素总是最后进队列,也是最后出队列队列结构示意图：队列Q=(a1，a2,…,an

)a1aia2an……队头队尾退队入队1顺序队列定义：队列的顺序存储结构称为顺序队列，利用一组地址连续的存储单元依次存放队列中的数据元素。约定：初始化队列：front=rear=0队尾插入新元素，rear加1队头元素出队列，front加1举例：顺序队列头尾指针变化情况：543210空队rearfront

a1

a2

a3543210frontrear

a3543210frontrear

a3

a4

a5

a6543210frontrear缺点：如上例,队列最大存储空间为6，队满时再继续插入元素就会上溢。队尾指针已到达数组上界，不能在增大。而当前队列可用空间并未占满，“假满〞现象。2循环队列定义：将队列存储空间的最后一个位置绕到第一个位置，相成逻辑上的环形空间。判定条件：队空：rear=front队满：方法1：rear=front，设一个标志变量S=0队空1队满约定循环数组中元素个数到达M-1队满头指针在尾指针下一位置上方法2：少一个元素空间循环队列示意图：02134567frontrear队空02134567一般情况a1a2frontrear02134567队满(少一个元素)a1a2frontreara3a4a5a6a7设循环队列中最多可容M个元素，那么循环队列中元素的个数为：=rear-front(当rear>front)=(rear+M-front)(当rear>front)如左图中元素个数:4+7-5=6设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，并且一个元素出栈后即进入队列Q，假设出队的顺序为b,d,c,f,e,a，那么栈S的容量至少应该为〔〕

〔A〕3〔B〕4〔C〕5〔D〕6一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，那么元素出栈的顺序是〔〕〔A〕12345ABCDE〔B〕EDCBA54321〔C〕ABCDE12345〔D〕54321EDCBA如果不是依次入栈，然后再依次出栈，那么ABD均有可能。类似题：(2-3)AB★树结构中结点之间有分支关系，层次关系，树中无环路树的一般表示：

ABCDEFGHIJK1.5树与二叉树1.5.1树的根本概念树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。根结点在第一层。1.5.2二叉树及其根本性质二叉树的特点：〔1〕非空二叉树只有一个根结点；〔2〕每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的五种根本形态(a)(b)(c)(d)(e)1什么是二叉树2二叉树的根本性质性质1二叉树第i(i≥1)层上至多有2i-1个结点。证明：根结点在二叉树的第一层上，这层结点数最多为1个，即20；第二层上最多有2个结点，即21个；…那么第i层上结点最多有2i-1个。性质2深度为k(k≥1)的二叉树至多有2k-1个结点。证明：由性质(1)可知各层结点最多数目之和为：20+21+22+…+2k-1；由二进制换算关系可得2k–1，因此二叉树树中结点的最大数目为2k-1。性质3：度为0的结点〔即叶子结点〕总是比度为2的结点多一个。证明：设n代表二叉树结点的总数，叶子结点(即度为零的结点)个数为n0，度为1的结点个数为n1，度为2的结点个数为n2。那么n=n0+n1+n2(1)有n个结点的二叉树总边数为n-1条：n-1=0*n0+1*n1+2*n2(2)将(1)式代入(2)式得：n0=n2+1满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，那么k层上有2k-1个结点,深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均到达最大值，在最后一层上只缺少右边的假设干结点。根据完全二叉树的定义可得出：度为1的结点的个数为0或1。设一棵完全二叉树共有700个结点，那么在该树中有多少个叶子结点？设该完全二叉树中有x个度为０的结点〔即叶子结点〕，y个度为１的结点，ｚ个度为２的结点，那么：x+y+z=700①z=x-1②将②代入①可得：x=(700+1-y)/2③又y只能取0或1，分别代入③可得：x=350.5④〔不合理舍去〕或350⑤所以叶子结点数x=350思考：将700改成739，那么结果为多少？370满二叉树和完全二叉树(a)满二叉树；(b)完全二叉树；(c)非完全二叉树FGDE1376542ABC(a)FDE136542ABC(b)FG13762ABC(c)性质4具有n个结点的完全二叉树树深为[log2n]+1。或者：具有n个结点的二叉树，其深度至少为[log2n]+1。其中[log2n]表示取[log2n]的整数局部。性质5设完全二叉树共有n个结点。如果从根结点开始，按层序〔每一层从左到右〕用自然数1，2，…n给结点进行编号〔k=1,2….n〕，有以下结论：①假设k=1，那么该结点为根结点，它没有父结点；假设k>1，那么该结点的父结点编号为INT(k/2)；②假设2k≤n，那么编号为k的结点的左子结点编号为2k；否那么该结点无左子结点〔也无右子结点〕；③假设2k+1≤n，那么编号为k的结点的右子结点编号为2k+1；否那么该结点无右子结点。1.5.3二叉树的遍历遍历二叉树是指以一定的