版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第一章概述一、概念一、数据结构的要紧研究内容:一般是研究数据的存储结构(物理结构)和逻辑 结构,以及它们之间的彼此联系;对每种结构概念相适应的各类运算,设计 出相应的算法,分析算法的效率。二、从逻辑上能够把数据结构分为线性结构、非线性结构两大类。即:数据逻辑 结构除集合之外,还包括线性结构、树形结构和图形结构。3、数据的逻辑结构与数据元素本身的内容和形式无关。4、数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。二、算法一、程序和算法原那么上是有区别的。二、算法分析的两个要紧方面是:时刻复杂度和空间复杂度第二章线性表一、顺序表一、顺序表中的地址计算公式:第一个元素的存储地址是LOC
2、(ai),每一个元素占用L个存储单元,并以所占的第一个单元的存储地址作为数据元素 的存储位置,那么第i个元素的存储地址为:LOC(ai)=LOC(ai)+(i-1)* L (1 i next=p-next; p-next=q;二、删除结点P后的结点q的语句:p-next=q-next; free(q);3、链式存储的存储结构所占存储空间:分两部份,一部份寄存结点值,另一 部份寄存表示结点间关系的指针4、在线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并非必 然紧邻。三、双向链表一、在双向链表存储结构中,删除 p所指的结点时可修改指针:p-next-prior=p-prior; p-p
3、rior-next=p-next;二、双向链表指针p的结点前插入一个指针q的结点操作是:q- next =p;q- prior =p- prior ;p- prior - next =q;p- prior =q;四、各类存储结构综合一、顺序表结构适宜于进行随机存取,而链表适宜于进行顺序存取。二、单链表的每一个结点包括一个指针域,双向链表的每一个结点包括两个指 针域。五、例题和算法设计例1:顺序表中第一个元素的存储地址是50,每一个元素的长度为4,那么第10 个元素的地址是:LOC(M =LOC(a)+(10-1)* 4 =86例2:在带头结点的单链表中删除一个最小值结点的算法。void del
4、ete (Linklist *L ) Linklist *p,*q;p=L;q= L-next ;while (q&q-next) if (q-next-datanext-data )p= q;q= q-next ;if(p-next) q=p-next ;p-next=q-next;free (q); /终止算法delete。例3:已知不带头结点的线性链表list ,链表中结点构造为(data、link ),其中data为数据域,link为指针域。请写一算法,将该链表按结点数据域的值 的大小从小到大从头链接。LinkedList LinkListSort(LinkedList list)/
5、list是不带头结点的线性链表,链表结点构造为 data和link两个域, data是数据域,link是指针域。本算法将该链表按结点数据域的值的大 小,从小到大从头链接。p=list-link;/p是工作指针,指向待排序的当前元素。list-link=null;/假定第一个元素有序,即链表中现只有一个结点。while(p!=null)r=p-link;/ r 是 p 的后继。q=list;if(q-datap-data、口处置待排序结点p比第一个元素结点小的情形p-link=list;list=p; /链表指针指向最小元素。else /查找元素值最小的结点。while(q-link!=null
6、&q-link-datadatA、q=q-link;p-link=q-link;/将当前排序结点链入有序链表中。q-link=p; p=r; / p指向下个待排序结点。例4:将一个带头结点、数据项递增有序的单向链表,从头排列链表,使数据 项递减有序。void invert(Linklist *la ) linklist *p,*q;p=la-next ;la-next= NULL ;while (p!= NULL)q= p-next ;p-next=la-next ;la-next=p ; p= q;)第3章栈和队列一、栈一、栈的特点:先进后出或称作后进先出二、入栈与出栈序列3、空栈:是不包括
7、任何元素的栈4、栈的应用(1)在判别表达式中左,右括号是不是配对显现的算法中,采纳栈作为数据 结构最正确。(2)在表达式求值、进制转换、函数或进程的挪用等算法中,都要用到栈。二、队列一、队列的特点:先进先出,在队列中,通常许诺删除的一端称为队头,许诺插入的一端称为队尾。二、队列的应用:解决运算机主机与打印机间速度不匹配问题,通常设一个打 印数据缓冲区,该缓冲区的逻辑结构确实是一个队列。3、循环队列中的元素个数计算公式。4、对顺序栈作操作运算时,进栈应先判别栈是不是满,出栈时应先判别栈是不 是空。且顺序队列和循环队列关于队满和队空的判定条件是不一样的。五、设循环队列寄存在向量M+1中,设:队头指
8、针为,队尾指针为,采用捐躯一个单元的方法来区分队满和队空。那么:出队操作时,队头指针转变可表示为:=(s.front+1)%(M+1);队满的条件为:(s.rear+1)%(M+1)=;三、栈与队列的存储栈和队列都是操作受限的线性结构,都能够用顺序存储和链式存储。四、例题分析例1:有六个元素6, 5, 4, 3, 2, 1的顺序进栈,那么:(5 4 3 6 1 2 )不是合法的出栈序列例2:设一个栈的输入序列是1 , 2, 3, 4, 5,以下序列中,(D )是栈的合 法输出序列。A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 1 5 4例3:数组Q n
9、用来表示一个循环队列,front为当前队列头元素的前一名 置,rear为队尾元素的位置,假定队列中元素的个数小于n ,计算队列中元 素个数的公式为:(n+rear-fron)%n例4:假设为循环队列分派的向量空间为Q25(下标从0开始),假设队列的长度和队头指针值别离为15和20,那么当前队尾指针的值为:10。例5:循环队列存储在数组 A0.m中,那么入队时的操作为(D )。A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)第4、5章串和数组一、用一、用的长度的概念:是指
10、用中所含字符的个数二、子用的概念,例如:“DTA不是“DATAA的子用。3、用的存储结构中,堆分派存储是一种动态存储结构。4、空审是任意用的字申。二、数组一、数组的地址计算公式:设二维数组是 Ac1.d1, c2.d2,那个地址c1,c2不必然是0。那么行优先存储时的地址公式为:LOC同 尸LOC(a1,c2)+(i-c 1)*(d 2-c2+1)+j-c 2*L二维数组列优先存储的通式为:LOC(a 尸LOC(a1,c2)+(j-c 2)*(d 1-C1+1)+i-c i*L二、特殊矩阵的紧缩存储及其地址映射公式三、例题分析例1:设有数组Ai,j,数组的每一个元素长度为4字节,i的值为1到7
11、, j的值为1到10,数组从内存首地址Loc开始顺序寄存,当用以行为主寄存 时,元素A4,6的存储首地址为(Loc+140 );当用以列为主寄存时, 元素A4,6的存储首地址为(Loc+152 )。例2:设有一个9阶的对称矩阵,采纳紧缩存储方式,以行序为主存储,a-为第一元素,其存储地址为1,每一个元素占2个地址空间,那么a 5的 地址为(51 ),则a5,7的地址为(51 )。例3:设A是n*n的对称矩阵,将A的对角线及对角线上方的元素以列为主的 顺序寄存在一维数组 B1.n(n+1)中,对上述任一元素aij (1 i ,j lchild=null & p-rchlid=null3、在二叉树
12、中,每一个结点的两棵子树是有序的。二、二叉树的性质、性质2:二叉的高与结点之间的关系、性质5:完全二叉树中双亲、左小孩与右小孩之间的关系及其应用3、完全二叉树和满二叉树的关系:满二叉树必然是完全二叉树,完全二叉树 不必然是满二叉树。4、在满二叉树中,只有度为0或度为2的结点,不存在度为1的结点。五、性质3:度为0、一、2三类结点间的关系三、二叉树的遍历一、由二叉树的先序序列和中序序列能够唯一确信一棵二叉树。由二叉树的后序序列和中序序列能够唯一确信一棵二叉树。但由二叉树的先序序列和后 序序列不能唯一确信一棵二叉树。二、在二叉树结点的先序序列、中序序列和后序序列中,所有叶子结点的前 后顺序完全相同
13、。四、树的存储结构、树的遍历、树与二叉树之间的转换一、把一棵树转换为二叉树后,这棵二叉树的形态是唯一的,且没有右子树。即:由树转化为二叉树,其根结点的右子树老是空的。二、树转换成二叉树3、树的存储形式有:双亲表示法、小孩链表表示法、小孩兄弟表示法等,但 没有顺序存储表示法。4、树的遍历五、丛林转换成二叉树:注意其左右子树上的结点个数。设丛林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结 点个数为n,丛林F中第一棵树的结点个数是 m-n。若是丛林F中有三棵树, 第一,第二,第三棵树的结点个数别离为 M1, M2和M3那么与丛林F对应 的二叉树根结点的右子树上的结点个数是 M2+M 3
14、五、哈夫曼树一、特点二、组成和应用六、例题分析一、二叉树性质应用例1: 一个具有1000个结点的二叉树的高h介于10至1000之间,一个具有 1000个结点的完全二叉树的高h等于10。例2:具有256个结点的完全二叉树的深度为 9 (注意:不能是8)。例3:如某二叉树有30个叶子结点,有40个结点仅有一个小孩,那么该叉树的总结点数为:99例4: 一棵完全二叉树上有1000个结点,其中叶子结点的个数是 500个,若是有1000个结点,那么其叶子结点的个数是 501个。、已知中序序列和后序序列确信一棵树,已知中序序列和先序序列确信一棵树例1:已知一棵二叉树的先序序列是DBFEACG H青画出这棵二
15、叉树,并给出后序序列。答:该二叉树如右图后序序歹h DFEBHGCAABDEFCG也序序歹U是例2:已知一棵二叉树的中序序列是DFEBHGC A青画出这棵二叉树,并给出先序序列答:该二叉树如右图DBEFAGH Ct序序列J是0ACGHF先序序歹h DFEBHGCA3、树和二叉之间的转换例:请按小孩兄弟表示法将以下树结构转换为对应的二叉树,并给出该树的一种先序遍历序列和后序遍历序列答:对应的二叉树:树的一种先序遍历序列:ABEFGCDHI树的一种后序遍历序列:EFGBCHIDA4、哈夫曼树生成及哈夫曼编码例:假设用于通信的电文仅由 7个字母组成,字母在电文中显现的次数别离为这8个字母设计哈夫曼编
16、码016:011 8:10010 : 101 24 : 11答:哈夫曼树如下(形状不唯一)5,30,8 , 10,7,16,24 。请依照各个字符的显现概率构造一棵哈夫曼树,并为哈夫曼编码(编码不唯一)30:00 5: 0100 7 : 0101一、图的概念和存储结构一、图能够没有边,但不能没有极点。二、邻接表和邻接矩阵都可用于存储有向图和无向图。3、在有向图中,丫1、2与丫2田 是两条不同的边。4、在无向图G的邻接矩阵A中,假设Aij 等于1,那么Aji 等于1五、完全图中,极点数和边数的关系二、图的遍历一、图的遍历方式:深度优先遍历、广度优先遍历二、假设从无向图的任意一个极点动身进行一次深
17、度优先搜索能够访问图中 所有的极点,那么该图必然是连通图。3、用邻接表表示图进行广度优先遍历时,通常借助队列来实现算法。4、深度优先遍历算通常采纳递归或借助栈来实现。三、最小生成树一、带权图最小生成树不必然是唯一的,能够有一棵或多棵,但其最小生成树的代价是唯一的二、最小生成树的两种生成算法四、AOM与 AOEW一、拓扑排序方式能够判定出一个有向图是不是有环。五、例题分析例1:具有9个极点的有向完全图有72条弧。具有9个极点的无向图,边的总数最多为 36。例2:图的邻接矩阵如右图所示,那么从极点 V0动身按10 0 1 。I 0 0 0 110 10 10110 10 0 10例3:已知一个图的
18、采纳二维数组表示的邻接矩阵如下图所示,请回答以深度优先遍历的结果是(0,3,6,1,5,4,2)下问题:(1)画出该邻接矩阵对应的图。(2)请画出自极点v1动身进行遍历所得的深度优先遍历生成树例4:已知一个图的采纳二维数组表示的邻接表如下图所示,请回答以下问题:(1)画出该邻接表对应的图(2)请画出自极点v1动身进行遍历所得的广度优先遍历生成树广度优先遍历生成树如下图第9章查找一、顺序查找和索引(分块)查找的算法思想一、索引查找中,数据的组织特点是:块内可无序,块间要有序。二、假设查找表的长度为n,那么顺序查找法的平均查找长度为(n+1) /23、顺序查找算法能够适用于有序表、无序表,能够采纳
19、顺序存储和链式存储。 二、折半查找一、适用于折半查找的表的存储方式及元素排列要求:顺序方式存储,元素有序二、折半查找中,元素的比较次数3、对有序表而言,采纳折半查找并非是总比采纳顺序查找法速度快。三、二叉排序树、概念:二叉排序树的左子树不为空,那么左子树上所有结点的值均小于 它的根结点值,右子树不为空,则右子树上所有结点的值均大于它的根 结点的值。二、关于一个二叉排序树,按二叉树层次进行遍历能够取得一个有序序列。3、关于两棵具有相同关键字但形状不同的二叉排序树,按中序遍历它们取得 的序列的顺序是一样的。4、平稳二叉树中某一结点左子树的深度减去右子树的深度称为该结点的平稳 因子。四、哈希查找一、
20、散列法是一种将关键字转换为存储地址的存储方式。二、哈希函数的选择要视情形而定,不存在专门好与坏的哈希函数。3、哈希表的生成五、例题分析一、折半查找例一、在有序表A1.25中,按二分查找方式进行查找,查找长度为5的元 素个数是10个例2:在有序表(3, 5, 8, 15, 25, 34, 55, 78, 90, 100)中采纳折半查 找方式,查找表中元素 58,那么它将依次与表中(25 , 78, 340, 55 ) 比较大小,查找结果是失败。二、二叉排序树构造例1:别离以以下序列构造二叉排序树,与用其它三个序列所构造的结果不 同的是(B )。(105, 85, 95 , 60 , 125, 1
21、10, 140)(105, 60, 85 , 95 , 125, 110, 140)(105, 125, 110, 140, 85, 60 , 95)(105, 85, 60 , 95 , 125, 140, 110)例2:给定关键字序列21, 88, 20, 10, 13, 12, 24, 31,若采纳二叉排序 树查找,请回答以下问题:(1)画出二叉排序树查找的二叉排序树。(2)假定每一个元素的查找概率相等,那么查找成功时的平均查找长度是多少?答:(1)二叉排序树(关键字顺序已确信,该二叉排序树唯一)如以下图所示:(2)从上图能够取得二叉排序树查找的成功平均查找长度为:ASL=(1+2*2+
22、3*2+4*2+5*1)/8=33、哈希表构造例1:设哈希表长为15,哈希函数是H(key)=key%11,表中已有数据的关键 字为26, 38, 72, 84共四个,现要将关键字为49的元素加到表中,用 线性探测再散列法解决冲突,那么放入的位置是:8;用二次探测法解决冲突,那么放入的位置是:9。例2:设哈希(Hash)表的地址范围为017,哈希函数为:H(K)=K MOD 16。K为关键字,用线性探测法再散列法处置冲突,输入关键字序列:(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)造出Hash表,试回答以下问题:(1)按关键字的输入顺序构造哈希表,画
23、出所构造哈希表的示用意。(2)求所构造哈希表查找成功时的平均查找长度 ASL答:(1)最后取得的哈希表示用意如下表所示:012345678910111213141516173217634924401030314647(2) ASL=1/11 (6+ 2+3X3) = 17/11=1.5454545454例3、设关键字的输入序列为:(47, 7, 29, 11, 16, 92, 22, 8, 3),哈希表 的地址范围为010,哈希函数为:H (K) =K MOD 11 K为关键字值,采纳 线性探测法处置冲突,请回答下面两个问题:(1)按关键字的输入顺序构造哈希表,画出所构造哈希表的示用意。(2)
24、求所构造哈希表查找成功时的平均查找长度 ASL答:(1)最后取得的哈希表示用意如下表所示:地址编号012345678910关键字值112247921637298(2) AS上(1+2+1+1+1+4+1+2+2 19=5/3=第10章排序一、各类排序的算法思想一、内部排序的概念:内部排序确实是整个排序进程完全在内存中进行的排 序。二、算法稳固性的概念。二、插入排序一、直接插入排序时,关键字的比较次数与记录的初始排列有关,初始序列顺 序时比较次数最少,初始序列倒序时比较次数最多。二、直接插入排序的思想。3、希尔排序的算法思想,能写出每一趟排序的结果序列。4、希尔排序是不是是稳固的排序方式,并能说
25、明缘故。三、选择排序一、概念:从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方式,称为选择排序二、堆排序:关于一个堆,按二叉树层次进行遍历不能取得一个有序序列。四、互换排序一、对n个不同的关键字由小到大进行冒泡排序,在从大到小排列好(倒序) 的情形下比较的次数最多,属于最坏的情形,其需要的时刻是O (n2)在从小到大排列好(顺序)的情形下比较的次数最少。二、快速排序算法思想及其应用,能写出每一趟排序的结果序列。3、快速排序是不是是稳固的排序方式,并能说明缘故。五、归并排序一、对n个记录的集合进行归并排序,所需要的时刻是 O(nlog2n)。六、例题分析与算法描述一、插入
26、排序例 1:给定一组关键字序列15, 25, 10, 40, 25*, 35, 12, 30, 20, 24, 5),其中20和20*表示值相同的两个关键字,采纳希尔排序方式由小到 大排序,dk依次取5, 3, 1。(1)请写出排序进程(每趟排序的结果序列)。(2)希尔排序是不是稳固的排序?什么缘故?答:(1)每趟排序的结果序列为: TOC o 1-5 h z 初态:15 , 25,10,40,25*, 35,12,30,20,24, 5第一趟(Dk=5): 5 ,12,10,20, 25*,15,25,30,40, 24,35第二趟(Dk=3):5, 12,10,20,25*, 15, 25
27、,30,40,24,35第三趟(Dk=1):5, 10,12,20,15, 25*, 25,24,30,35,40最后取得的排序序列为:5, 10, 12, 20, 15, 25*, 25, 24, 30, 35, 40(2)希尔排序不是稳固的排序,因为值相同的两个关键字25和25*在排序前后位置发生了改变。例2:对序列16, 10, 7, 8, 22, 1 , 5进行排序,进行一趟排序后,取得的排列为10, 16, 7, 8, 22, 1 , 5),那么采纳的是(C )排序算法。A.简单选择B, 希尔 C.直接插入D. 归并二、堆排序例1:假设一组记录的排序码为(50, 79, 56, 38
28、, 40, 90),那么利用堆排 序的方式成立的初始堆为(90, 79, 50, 38, 40, 46)。例2:以下关键字序列中,(D )是堆。A . 16, 72, 31,23, 94, 53 B. 94, 23, 31, 72, 16, 53C. 16, 53, 23, 94, 31, 72 D . 16, 23, 53, 31, 94, 723、快速排序和冒泡排序例1:假设一组记录的排序码为(50, 79 , 56, 38, 40, 85),那么利用快速 排序的方式,以第一个记录为基准取得的一次划分结果为:40 38 50 56 79 85例2:设有一个整型数组中寄存了一个无序的序列k
29、一、k二、kn。现要求将kn放在将元素排序后的正确位置上,要求比较关键字的次数不超过n0那么可用快速排序算法例3:设有一个整型数组中寄存了一个序列 k、k二、kn。实现该序列的升序排列。要求:该算法在最好情形下(原始序列为升序时)一趟排序能够终止,时刻复杂度为 O(n)。那么可用冒泡排序算法。例 4:关键字序列为20, 14, 20*, 33, 87, 22, 2, 10, 72,其中,18和* .一 一一 . . . .18表示两个值相等的关键字,采纳快速排序算法由小到大进行排序, 请 回答下面两个问题:(1)写出排序进程(每趟排序后的关键字序列)(2)快速排序是不是稳固的排序算法?什么缘故?答:(1)每趟排序结果初始序列:20, 14, 第一趟:10 14 20
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 重大医患纠纷事件应急预案
- 脑小血管病的诊断和治疗
- 耳穴贴压治疗高血压及其并发症的研究进展
- 幼儿卫生保健专家讲座
- 宴会厅形象设计
- 牙科牙齿冷光美白的护理技术
- 舒心病房护理流程优化的研究
- 社区居家医养结合养老模式
- 2027年安徽省高考二模英语真题卷及答案
- 八年级生物模拟卷(2026-2027学年上学期第二次月考)
- 拔罐疗法适应症与禁忌专家共识(2025版)
- 慢性阻塞性肺疾病科普
- 2024儿童口腔分龄护理和科学防龋专家共识解读
- NBT 10209-2019《风电场工程道路设计规范》
- 2026春季学期国家开放大学专科《统计与数据分析基础》一平台在线形考形成性考核一至五试题及答案
- 中班安全:《玩火真危险-我们不玩火》课件
- 卫生部病历书写基本规范2025年版
- 2025年宜都社区专职工作人员招聘真题
- 超星尔雅学习通《人工智能与创业智慧(北京林业大学)》章节测试含答案
- PC塑料培训课件
- 2024年辽宁机电职业技术学院招聘笔试真题
评论
0/150
提交评论