《数据结构》知识点总结1

数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体数据元素是数据的基本单位，可以由若干个数据项组成数据项是具有独立含义的最小标识单位数据结构的定义■逻辑结构从逻辑结构上描述数据，独立于计算机•线性结构一对一关系•线性结构多对多关系•存储结构是逻辑结构用计算机语言的实现•顺序存储结构如数组•链式存储结构如链表•索引存储结构•稠密索引每个结点都有索引项•稀疏索引每组结点都有索引项•散列存储结构如散列表•数据运算•对数据的操作定义在逻辑结构上，每种逻辑结构都有一个运算集合•常用的有检索、插入、删除、更新、排序数据类型是一个值的集合以及在这些值上定义的一组操作的总称•结构类型由用户借助于描述机制定义，是导出类型抽象数据类型•是抽象数据的组织和与之的操作相当于在概念层上描述问题ADT:•优点是将数据和操作封装在一起实现了信息隐藏程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法算法取决于数据结构算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出评价算法的好坏的因素•算法是正确的；•执行算法的时间；■执行算法的存储空间主要是辅助存储空间；•算法易于理解、编码、调试时间复杂度是某个算法的时间耗费，它是该算法所求解问题规模的函数n渐近时间复杂度是指当问题规模趋向无穷大时，该算法时间复杂度的数量级评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关时间复杂度按数量级递增排列依次为常数阶、对数阶、线性阶、线性对数阶、平方阶01Olog2n0n Onlog2n、立方阶、次方阶、指数阶八0M20M3……k02k02n空间复杂度是某个算法的空间耗费，它是该算法所求解问题规模的函数n算法的时间复杂度和空间复杂度合称算法复杂度第二章线性表线性表是由个数据元素组成的有限序列n20是空表；非空表，只能有一个开始结点，有且只能有一个终端结点n=0线性表上定义的基本运算•构造空表Initlist L•求表长Listlength L•取结点GetNode L,i•查找:LocateNode L,x•插入InsertList L,x,i•删除:Delete L,i顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的地址计算:LOCa i=LOCa1+i-1*d；首地址为1在顺序表中实现的基本运算.其基本思想1每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可即从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置的数据元素集合中选取关键字最小的数据元素并将它与原始数据集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止.优缺点2优点实现简单缺点每趟只能确定一个元素，表长为时需要趟n n-1例关键字序列，请给出直接选择排序的具体实现过程3:T=21,25,49,25*,16,08原始序列21,25,49,25*,16,08第趟108,25,49,25*,16,21第趟208,16,49,25*,25,21第趟308,16,21,25*,25,49第趟408,16,21,25*,25,49第趟508,16,21,25*,25,49public static void selectSortint[]a{int i,j,small;int temp;int n=a.Length;fori=0;in-I;i++{〃设第个数据元素最小small=i;i〃寻找最小的数据元素forj=i+I;jn;j++//记住最小元素的下标ifa[j]a[small]small=j;〃当最小元素的下标不为时交换位置ifsmall!=i{itemp=a[i];a[i]=a[small];a[small]=temp;}.算法分析3时间效率On2——虽移动次数较少，但比较次数仍多空间效率OI没有附加单元仅用至I个temp算法的稳定性不稳定.稳定的直接选择排序算法4例关键字序列T=21,25,49,25*,16,08请给出稳定的直接选择排序的具体实现过程原始序列21,25,49,25*,16,08第趟108,21,25,49,25*,16第趟208,16,21,25,49,25*第趟308,16,21,25,49,25*第趟408,16,21,25,49,25*第趟508,16,21,25,25*,49public staticvoid selectSort2int[]a{int ij,small;int temp;int n=a.Length;fori=0;in-1;i++{small=i;〃寻找最小的数据元素forj=i+1;jn;j++{ifa[j]a[small]small=j;//记住最小元素的下标ifsmall!=i{temp=a|small];〃把该区段尚未排序元素依次后移forj=small;ji;j-a[j]=a[j-l];〃插入找出的最小元素a[i]=temp;堆排序.什么是堆..怎样建堆怎样堆排序？堆的定义设有个数据元素的序列当且

12.3n kO,kl,…,kn-l,仅当满足下述关系之一时，称之为堆解释如果让满足以上条件的元素序列顺次排成一棵完全二叉树，kO,kl,…,kn—1则此树的特点是树中所有结点的值均大于或小于其左右孩子，此树的根结点即堆顶必最大或最小例有序列和序列二，判断它们是否“堆”？.怎样建堆？步骤4:Tl=08,25,49,46,58,67T291,85,76,66,58,67,552从第一个非终端结点开始往前逐步调整，让每个双亲大于或小于子女，直到根结点为止终端结点即叶子没有任何子女，无需单独调整例关键字序列请建最大堆T=21,25,49,25*,16,08,解为便于理解，先将原始序列画成完全二叉树的形式这样可以很清晰地从开始调整n-l-l/2public staticvoid createHeapint[]a,int n,int h{int ij,flag;int temp;i=h;j=2*i+1;〃j为i结点的左孩子结点的下标temp=a[i];flag=0;whilejnflag!=1{//寻找左右孩子结点中的较大者,为其下标jifjn-1a[j]a[j+l]j++;if temp=a[j]//a[i]=a[j]//标记结束筛选条件〃否则把上移flag=1;else{a[i]=a[j];♦*l=j;j=2*i+1;a[i]=temp;利用上述函数，初始化创建最大堆的过程就是从第一个非叶子结点开始，到根结点为createHeap a,n,h a[i]a

[0]止,循环调用的过程初始化创建最大堆算法如下createHeap a,n,h public staticvoidinitCreateHeapint[]a{int n=a.Length;forint i=n-1-1/2;i=0;i—createHeapa,n,i;.怎样进行整个序列的堆排序？3*基于初始堆进行堆排序的算法步骤堆的第一个对象具有最大的关键码，将与对调，把具有最大关键码的对象交换到最后；a

[0]a

[0]a[n-l]再对前面的个对象，使用堆的调整算法，重新建立堆调整根结点使之满足最大堆的定义结果具有次最大关n-l键码的对象又上浮到堆顶，即位置；a

[0]再对调和然后对前个对象重新调整，…如止匕反复，最后得到全部排序好的对象序列a

[0]a[n-2],n-2例对刚才建好的最大堆进行排序5:public staticvoid heapSortint|]a{int temp;int n=a.Length;〃初始化创建最大堆initCreateHeapa;〃当前最大堆个数每次递减forint i=n-1;i0;i-{1〃把堆顶元素和当前最大堆的最后一个元素交换a

[0]temp=a

[0];a

[0]=a[i];a[i]=temp;〃调整根结点满足最大堆createHeapa,i,0;}.堆排序算法分析4时间效率:Onlog2no空间效率01稳定性不稳定练习以下序列是堆的是1:{75,65,30,15,25,45,20,

10..…B.{75,65,4510,30,25,20,15}C.{75,45,65,30/5,25,20/0……D.{75,45,65/0,25,30,20,

15.练习2有一组数据{15,9,7,8,20,1,7*,4},建成的最小堆为A.{1,4,8,9,20,7/5,7*}B.{1,7/5,7*,4,8,20,9}以上都不对C.{1,4,7,8,20/5,7*,9}D.练习已知序列写出采用堆排序对该序列作非递减排列时的排序过程3:{503,87,512,61,908,170,897,275,653,462},排序好的序列为:61,87,170,275,462,503,512,653,897,908交换排序

10.4交换排序的基本思想是利用交换数据元素的位置进行排序的方法交换排序的主要算法有冒泡排序1快速排序2冒泡排序

10.

4.

1.基本思路每趟不断将记录两两比较，并按“前小后大”或“前大后小”规则交换

1.优点每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生,还2可以提前结束排序例关键字序列请按从小到大的顺序，写出冒泡排序的具体实现过程T=21,25,49,25M6,08,初态21,25,49,25*,16,08第趟121,25,25*,16,08,49第趟221,25,16,08,25*,49第趟321,16,08,25,25*,49第趟416,08,21,25,25*,49第趟508,16,21,25,25*,

49.冒泡排序算法3public staticvoid bubbleSortint[]a{int i,j,flag=l;int temp;二int na.Length;fori=1;inflag==1;i++{flag=0;forj=0;j n-i;j++{ifa[j]a[j4-l]{flag=1;temp=a[j];a[j]=a[j+l];a[j+l]=temp;.冒泡排序的算法分析4时间效率—因为要考虑最坏情况数据元素全部逆序，当然最好情况是数据元素已全部排好序，此时循环O n2n-l次，时间复杂度为O n空间效率一只在交换时用到一个缓冲单元01稳定性稳定一和在排序前后的次序未改变2525*练习关键字序列请按从小到大的顺序，写出冒泡排序的具体实现过程T=31,15,9,25,16,28,初态:31,15,9,25,16,28第趟115,9,25,16,28,31第趟2915,16,25,28,31第趟39,15,16,25,28,

31.基本思想设数组中存放了个数据元素为数组的低端下标,为数组的高端下标，从数组中任取一个元1a now higha素通常取做为标准元素，以该标准元素调整数组中其他各个元素的位置，使排在标准元素前面的元素均小于aflow]a标准元素，排在标准元素后面的均大于或等于标准元素这样一次排序过程结束后，一方面将标准元素放在了未来排好序的数组中该标准元素应位于的位置上，另一方面将数组中的元素以标准元素为中心分成了两个子数组,位于标准元素左边子数组中的元素均小于标准元素，位于标准元素右边子数组中的元素均大于等于或标准元素对这两个子数组中的元素分别再进行方法类同的递归快速排序算法的递归出口条件是low^higho例、关键字序列，请按从小到大的顺序,写出快速排序的具体实现过程快速排序算法各T=60,55,48,37,10,90,84,36次快速排序过程.快速排序算法3public staticvoid quickSortint[]a,int low,int high{int i,j;int temp;1=low;j=high;〃取第一个元素为标准数据元素temp=a[low];whileij{〃在数组的右端扫描whileijtemp=a[j]j—;ifij{a[i]=a[j];i++；〃在数组的左端扫描whileija[i]temp i++;ifij{a|j|=a[i];j-；a[i]=temp;〃对左端子集合递归iflowi quickSorta,low,i-1;〃对右端子集合递归ifihigh quickSorta,j+1,high;.快速排序算法分析4时间效率一般情况下时间复杂度为最坏情况是数据元素已全部正序或反序有序，此时每次标准元素都0nkg2n,把当前数组分成一个大小比当前数组小的子数组，此时时间复杂度为1On2空间效率O log2n—因为递归要用栈稳定性不稳定一因为有跳跃式交换第一趟:

[4628727561170]503【897908653512第二趟:[17087275503

[512653]897

[908]61]462第三趟:

[6187]170462503512

[653]897908【】275第四趟:61

[87]170503512653897908275462最后排序结果:6187170275462503512653897908练习已知序列给出采用快速排序对该序列作非递减排序时每趟的结果{503,87,512,61,908,170,897,275,653,462},插入排序是稳定的，选择排序是不稳定的L.堆排序所需要附加空间数与待排序的记录个数无关

5.对有个记录的集合进行快速排序，所需时间确定于初始记录的排列情况，在初始记录无序的情况下最好6n,直接插入排序在最好情况下的时间复杂度为4A A.On...B.Onlog2n...C.Olog2n....D.On

2..数据序歹只能是算法的两趟排序后的结果5iJ{8,9/045,6,201,2}C直接选择排序冒泡排序直接插入排序堆排序A.B.C D..用直接插入排序对下面个序列进行递增排序，元素比较次数最少的是64C A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,

40..以下排序算法中，不能保证每趟排序至少能将一个元素放到其最终位置上.7OA.快速排・.B.希尔排•.C堆排….D.冒泡排..对关键字序列进行快速排序，第一趟从小到大一次划分结果为8{28,16,32,12,60,2,5,72}BA.2,5,12,162660,32,72B.5,l6,2,122860,32,72C.2,l6,12,52860,32,72D.5,l6,2,122832,60,

72.若用冒泡排序对关键字序列进行从小到大的排序，所需进行的关键字比较总次数是9{18,16,14,12,10,8}B A.10B.15C.21D.34一组记录的关键字为则利用堆排序的方法建立的初始堆为…

10.{45,80,55,40,42,85},A・{85,80,45,40,42,55}B.{85,80,55,40,42,45}C・{85,80,55,45,42,40D.{85,55,80,42,45,40}第十章文件文件是性质相同的记录的集合记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性文件•逻辑结构是一种线性结构操作有检索和维护并有实时和批量处理两种处理方式•文件•存储结构是指文件在外存上的组织方式基本的组织方式有顺序组织、索引组织、散列组织和链组织•常用的文件组织方式顺序文件、索引文件、散列文件和多关键字文件•评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件主关键字有序称顺序有序文件，否则称顺序无序文件一切存储在顺序存储器（如磁带）上的文件都只能顺序文件，只能按顺序查找法存取顺序文件的插入、删除和修改只能通过复制整个文件实现索引文件的组织方式通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件索引非顺序文件中的索引表为稠密索引索引顺序文件中的索引表为稀疏索引若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表是一种静态索引索引顺序文件常用的有两种索引顺序存取方法是专为磁盘存取文件设计的，采用静态索引结构•ISAM虚拟存储存取方法采用树作为动态索引结构，由索引集、顺序集、数据集组成■VSAM B+散列文件是利用散列存储方式组织的文件，亦称为直接存取文件散列文件•优点是文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间•缺点是不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件多重表文件对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项倒排表次关键字索引表称倒排表，主文件和倒排表构成倒排文件•插入平均移动结点次数为n/2；平均时间复杂度均为O no■删除平均移动结点次数为n-1/2；平均时间复杂度均为O no线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息即指针或链这两部分信息组成链表中的结点结构一个单链表由头指针的名字来命名单链表运算・建立单链表•头插法:s-next=head；head=s；生成的顺序与输入顺序相反平均时间复杂度均为O n•尾插法head=rear=null；if head=null head=s；else r-next=s；r=s；平均时间复杂度均为O n•加头结点的算法对开始结点的操作无需特殊处理，统一了空表和非空表•查找•按序号与查找位置有关，平均时间复杂度均为O no•按值与输入实例有关，平均时间复杂度均为Ono•插入运算:p=GetNode L,i-1；s-next=p-next；p-next=s；平均时间复杂度均为O n•删除运算:p=GetNode L,i-1；r=p-next；p-next=r-next；free r；平均时间复杂度均为O n单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点链表终止条件是以指针等于头指针或尾指针采用单循环链表在实用中多采用尾指针表示单循环链表优点是查找头指针和尾指针的时间都是不用遍历整O1,个链表双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域形成两条不同方向的prior,链由头指针惟一确定head双链表也可以头尾相链接构成双向循环链表双链表上的插入和删除时间复杂度均为O Do顺序表和链表的比较•基于空间•顺序表的存储空间是静态分配，存储密度为适于线性表事先确定其大小时采用1;•链表的存储空间是动态分配，存储密度适于线性表长度变化大时采用1;•基于时间•顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用•以插入和删除操作为主的线性表宜采用链表做存储结构•若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表第三章栈和队列栈是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底表中Stack无元素时为空栈栈的修改是按后进先出的原则进行的，我们又称栈为表通常栈有顺序栈和链LIFO LastIn First Out栈两种存储结构栈的基本运算有六种•构造空栈:InitStack S判栈空•StackEmpty S判栈满•StackFull S进栈•Push S,x退栈•Pop S取栈顶元素•StackTop S在顺序栈中有“上溢”和“下溢”的现象•“上溢”是栈顶指针指出栈的外面是出错状态“下溢”可以表示栈为空栈，因此用来作为控制转移的条件•顺序栈中的基本操作有六种•构造空栈•判栈空•判栈满•进栈•退栈•取栈顶元素链栈则没有上溢的限制，因此进栈不要判栈满链栈不需要在头部附加头结点，只要有链表的头指针就可以了链栈中的基本操作有五种•构造空栈•判栈空・进栈•退栈•取栈顶元素队列是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头Queue front,允许插入的一端称为队尾,队列的操作原则是先进先出的，又称作表.队列也有顺序存储和链rear FIFOFirst InFirstOut式存储两种存储结构队列的基本运算有六种•置空队InitQueue Q•判队空QueueEmpty Q•判队满:QueueFull Q•入队EnQueue Q,x•出队DeQueue Q•取队头元素QueueFront Q顺序队列的“假上溢”现象由于头尾指针不断前移，超出向量空间这时整个向量空间及队列是空的却产生了“上溢”现象为了克服“假上溢”现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列判定循环队列是空还是满，方法有三种•一种是另设一个布尔变量来判断；・第二种是少用一个元素空间，入队时先测试rear+1%m=front满空；•第三种就是用一个计数器记录队列中的元素的总数队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表为了便于在表尾进行插入入队的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定链队列不存在队满和上溢的问题在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空第四章串串是零个或多个字符组成的有限序列•空串是指长度为零的串，也就是串中不包含任何字符结点•空白串指串中包含一个或多个空格字符的串•在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串•子串在主串中的序号就是指子串在主串中首次出现的位置•空串是任意串的子串，任意串是自身的子串串分为两种•串常量在程序中只能引用不能改变；串变量的值可以改变串的基本运算有•求串长stHen charts•串复制strcpy char*to,char*from•串联接strcat char*to,char*from•串比较charcmp chads1,char*s2•字符定位strchr charts,chare串是特殊的线性表结点是字符，所以串的存储结构与线性表的存储结构类似串的顺序存储结构简称为顺序串顺序串又可按存储分配的不同分为■静态存储分配直接用定长的字符数组来定义优点是涉及串长的操作速度快，但不适合插入、链接操作・动态存储分配是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串链串与单链表的差异只是它的结点数据域为单个字符为了解决“存储密度”低的状况，可以让一个结点存储多个字符，即结点的大小顺序串上子串定位的运算又称串的“模式匹配”或“串匹配”，是在主串中查找出子串出现的位置在串匹配中，将主串称为目标串，子串称为模式串这是比较容易理解的，串匹配问题就是找出给定模式串在给定目标P串中首次出现的有效位移或者是全部有效位移最坏的情况下时间复杂度是，假如与同阶T0n-m+1m mn的话则它是八链串上的子串定位运算位移是结点地址而不是整数0n2第五章多维数组数组一般用顺序存储的方式表示存储的方式有行优先顺序，也就是把数组逐行依次排列♦PASCAL.C•列优先顺序，就是把数组逐列依次排列FORTRAN地址的计算方法•按行优先顺序排列的数组:LOCa ij=LOCa11+i-1*n+j-D*d.■按列优先顺序排列的数组:LOCa ij=LOCa11+j-1*n+i-D*d.矩阵的压缩存储为多个相同的非零元素分配一个存储空间；对零元素不分配空间特殊矩阵的概念所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵稀疏矩阵的概念一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵特殊矩阵的类型•对称矩阵满足元素总数a ij=a jion n+1/

2.1=max i,j,J=min i,j,LOCa ij=LOCsa

[0]+I*1+1/2+J*d.•三角矩阵•上三角阵k=i*2n-i+l/2+j-i,LOCa ij=LOC sa

[0]+k*d.•下三角阵k=i*i+l/2+j,LOCa ij=LOC sa

[0]+k*d.•对角矩阵k=2i+j,LOCa ij=LOC sa

[0]+k*d.稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表来表示但这种压缩存储方式将失去随机存储功能加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的三元组表第六章树树是个结点的有限集合，非空时必须满足只有一个称为根的结点；其余结点形成个不相交的子集，并称根n m的子树根是开始结点；结点的子树数称度；度为的结点称叶子终端结点；度不为的结点称分支结点非终端结0点；除根外的分支结点称内部结点；有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是个互不相交的树的集合；m树的四种不同表示方法•树形表示法；•嵌套集合表示法；•凹入表示法•广义表表示法二叉树的定义是个结点的有限集，它是空集或由一个根结点及两棵互不相交的分别称作这个根的n=0左子树和右子树的二叉树组成二叉树不是树的特殊情形，与度数为的有序树不同2二叉树的4个重要性质•二叉树上第i层上的结点数目最多为2八i-1i^lo；•深度为k的二叉树至多有2”-1个结点k2l；•在任意一棵二叉树中，若终端结点的个数为nO,度为2的结点数为n2,则n0=n2+l；•具有个结点的完全二叉树的深度为n intlog2n+

1.满二叉树是一棵深度为结点数为八的二叉树；完全二叉树是满二叉树在最下层自右向左去处部分结点;二叉k,2k-l树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中存储前先将其画成完全二叉树树的存储结构多用的是链式存储的结构为把所有类型的结点，加上一个指向BinTNode lchild|data|rchild,BinTNode根结点的型头指针就构成了二叉树的链式存储结构，称为二叉链表它就是由根指针唯一确定的共有BinTree root个指针域,个空指针2n n-f-l根据访问结点的次序不同可得三种遍历先序遍历前序遍历或先根遍历，中序遍历或中根遍历、后序遍历或后根遍历时间复杂度为0no利用二叉链表中的个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针;这些附加的指针就称为n+1“线索”，加上线索的二叉链表就称为线索链表线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用树和森林及二叉树的转换是唯一对应的转换方法•树变二叉树兄弟相连，保留长子的连线•二叉树变树结点的右孩子与其双亲连•森林变二叉树树变二叉树，各个树的根相连树的存储结构•有双亲链表表示法结点对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的data|parent,孩子及后代•孩子链表表示法为树中每个结点设置一个孩子链表并将存放在一个向量中data|next firstchild,data|firstchild・双亲孩子链表表示法将双亲链表和孩子链表结合•孩子兄弟链表表示法结点结构附加两个分别指向该结点的最左孩子和右邻兄弟的leftmostchild|data|rightsibing,指针域树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致树的带权路径长度是树中所有叶结点的带权路径长度之和树的带权路径长度最小的二叉树就称为最优二叉树即哈夫曼树在叶子的权值相同的二叉树中，完全二叉树的路径长度最短哈夫曼树有个叶结点，共有个结点，没有度为的结点，这类树又称为严格二叉树n2n-l1变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性如、00这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这

01.0001种码称为前缀码其实是非前缀码哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码右路径上写代码然后从上到下到叶结0,1,点的相应路径上的代码的序列就是该结点的最优前缀码第七章图图的逻辑结构特征就是其结点顶点的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关图是顶点的有穷非空集合,是顶点偶对的有穷集GraphG=V,E,V E有向图每条边有方向；无向图每条边没有方向Digraph:Undigraph:有向完全图具有条边的有向图；无向完全图具有条边的无向图；n*n-1n*n-1/2有根图有一个顶点有路径到达其它顶点的有向图；简单路径是经过顶点不同的路径；简单回路是开始和终端重的简单路径；网络是带权的图图的存储结构•邻接矩阵表示法用一个阶方阵来表示图的结构是唯一的，适合稠密图n无向图邻接矩阵是对称的•有向图行是出度，列是入度建立邻接矩阵算法的时间是八其时间复杂度为0n+n2+e,0M2•邻接表表示法用顶点表和邻接表构成不是唯一的，适合稀疏图•顶点表结构指针域存放邻接表头指针vertex|firstedge,•邻接表用头指针确定•无向图称边表；•有向图又分出边表和逆邻接表；•邻接表结点结构为adj vex|next,时间复杂度为，空间复杂度为0n+e On+eoo图的遍历•深度优先遍历借助于邻接矩阵的列使用栈保存已访问结点•广度优先遍历借助于邻接矩阵的行使用队列保存已访问结点生成树的定义若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点构成的子图称作该图的生成树最小生成树图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树MSTo构造最小生成树的算法算法的时间复杂度为与边数无关适于稠密图•Prim O22算法的时间复杂度为主要取决于边数，较适合于稀疏图•Kruskal OIge,最短路径的算法算法，时间复杂度为•类似于算法•Dijkstra O22prim拓扑排序是将有向无环图中所有顶点排成一个线性序列，若则在线性序列在之前，这种线性G u,v£E G,u v序列称为拓扑序列拓扑排序也有两种方法•无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列•无后继的结点优先每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列第八章排序记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字排序是使文件中的记录按关键字递增或递减次序排列起来•基本操作比较关键字大小；改变指向记录的指针或移动记录•存储结构顺序结构、链表结构、索引结构经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的排序过程中不涉及数据的内、外存交换则称之为“内部排序”内排序，反之，若存在数据的内外存交换，则称之为外排序内部排序方法可分五类插入排序、选择排序、交换排序、归并排序和分配排序评价排序算法好坏的标准主要有两条执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素插入排序•直接插入排序•逐个向前插入到合适位置•哨兵监视哨有两个作用•作为临变量存放R[i]•是在查找循环中用来监视下标变量是否越界j•直接插入排序是就地的稳定排序时间复杂度为0a2，比较次数为n+2n-1/2；移动次数为n+4n-1/2；•希尔排序•等间隔的数据比较并按要求顺序排列，最后间隔为

1.•希尔排序是就地的不稳定排序时间复杂度为OML25，比较次数为nN.25；移动次数为L6n八

1.25；交换排序•冒泡排序•自下向上确定最轻的一个•自上向下确定最重的一个•自下向上确定最轻的一个，后自上向下确定最重的一个•冒泡排序是就地的稳定排序时间复杂度为0a2，比较次数为n n-1/2；移动次数为3n n-1/2；•快速排序•以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合重复直到排序完成•快速排序是非就地的不稳定排序时间复杂度为O nlog2n，比较次数为n n-1/2；选择排序•直接选择排序•选择最小的放在比较区前•直接选择排序就地的不稳定排序时间复杂度为022比较次数为n n-1/2；•堆排序•建堆按层次将数据填入完全二叉树，从处向前逐个调整位置int n/2•然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开•堆排序是就地不稳定的排序，时间复杂度为不适宜于记录数较少的文件O nlog2n,归并排序•先两个一组排序，形成组，再将两组并一组，直到剩下一组为止n+1/2归并排序是非就地稳定排序，时间复杂度是O nlog2n,分配排序•箱排序•按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱•箱排序的平均时间复杂度是线性的O no•基数排序•从低位到高位依次对关键字进行箱排序•基数排序是非就稳定的排序，时间复杂度是O d*n+d*rd各种排序方法的比较和选择•待排序的记录数目n；n较大的要用时间复杂度为O nlog2n的排序方法；•记录的大小规模；记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现；•关键字的结构及其初始状态；•对稳定性的要求；•语言工具的条件；•存储结构；•时间和辅助空间复杂度第九章查找查找的同时对表做修改操作如插入或删除则相应的表称之为动态查找表，否则称之为静态查找表衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数即平均查找长度ASLo线性表查找的方法•顺序查找逐个查找,ASL=n+1/2；•二分查找取中点比较，若小就比左区间，大就比右区间用二叉判定树表示每层结点数*int n/2ASL=£层数/N.•分块查找要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序索引表二叉排序树定义是二叉排序树是空树或者满足如下性质的二叉树•若它的左子树非空，则左子树上所有BST结点的值均小于根结点的值；•若它的右子树非空，则右子树上所有结点的值均大于根结点的值；•左、右子树本身又是一棵二叉排序树二叉排序树的插入、建立、删除的算法平均时间性能是O nlog2n二叉排序树的删除操作可分三种情况进行处理是叶子，则直接删除*即将*的双亲*中指向的指针域•*P P,P parent*P置空即可只有一个孩子*此时只需将*和*的双亲直接连接就可删去*•*p child,child p p.有两个孩子，则先将*结点的中序后继结点的数据到*删除中序后继结点•*ppp,关于树多路平衡查找树它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法建立的方式B-是从下向上拱起散列技术将结点按其关键字的散列地址存储到散列表的过程称为散列散列函数的选择有两条标准简单和均匀常见的散列函数构的造方法•平方取中法八hash=int x2%100•除余法表长为m,hash=x%m•相乘取整法hash=int m*x*A-int x*A；A=

0.618•随机数法:hash=random x处理冲突的方法•开放定址法•一般形式为开放定址法要求散列表的装填hi=h key+di因子a WL•开放定址法类型•线性探查法address=hash x+i%m；•二次探查法address=hash x+iA2%m；•双重散列法address二hash x+i*hash y%m；・拉链法•是将所有关键字为同义词的结点链接在同一个单链表中•拉链法的优点•拉链法处理冲突简单，且无堆积现象；链表上的结点空间是动态申请的适于无法确定表长的情况；•拉链法中可以大于结点较大时其指针域可忽略，因此节省空间；a1,•拉链法构造的散列表删除结点易实现•拉链法也有缺点当结点规模较小时;用拉链法中的指针域也要占用额外空间，还是开放定址法省空间第十章排序排序的基本概念

10.1插入排序

10.2选择排序

10.3交换排序

10.4本章主要知识点排序的基本概念和衡量排序算法优劣的标准，其中衡量标准有算法的时间复杂度、空间复杂度和稳定性直接插入排序，希尔排序直接选择排序，堆排序冒泡排序，快速排序排序的基本概念

10.

1.排序是对数据元素序列建立某种有序排列的过程

1.排序的目的便于查找

2.关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的3关键字分主关键字和次关键字两种对要排序的数据元素集合来说，如果关键字满足数据元素值不同时该关键字的值也一定不同，这样的关键字称为主关键字不满足主关键字定义的关键字称为次关键字,排序的种类分为内部排序和外部排序两大类4若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序注外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多.排序算法好坏的衡量标准5⑴时间复杂度——它主要是分析记录关键字的比较次数和记录的移动次数⑵空间复杂度——算法中使用的内存辅助空间的多少⑶稳定性一一若两个记录和的关键字值相等，但排序后的先后次序保持不变，则称这种排序算法是稳定的A BA.B插入排序

10.2插入排序的基本思想是每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止简言之，边插入边排序，保证子序列中随时都是排好序的常用的插入排序有直接插入排序和希尔排序两种直接插入排序

10.

2.

1.其基本思想是1顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置例关键字序列1:T=13,6,3,31,9,27,5,11,请写出直接插入排序的中间过程序列初始关键字序列[1始，6,3,序，9,27,5,11第一次排序【，6,13]3,31,9,27,5,11第二次排序[3,6,13]，31,9,27,5,11第三次排序[3,6,13,31]，9,27,5,11第四次排序[3,6,9,13,31],27,5,11第五次排序[3,6,9,13,27,31]，5,11第六次排序[3,5,6,9,13,27,31]，11第七次排序[3,5,6,9,11,13,27,31]注方括号[]中为已排序记录的关键字，下划横线的关键字表示它对应的记录后移一个位置.直接插入排序算法2public staticvoid insertSortint[]a{int i,j,temp;int n=a.Length;fori=0;in-1;i++{temp=a[i+1];j=i；whilej-1tempa[j]{a[j+1]=a[j];一；ja[j+1]=temp;}初始关键字序列初始，6,3,31,9,27,5,11第一次排序【，6,13]3,31,9,27,5,11第二次排序[3,6,13]，31,9,27,5,

11.直接插入排序算法分析31时间效率当数据有序时，执行效率最好，此时的时间复杂度为On；当数据基本反序时，执行效率最差，止匕时的时间复杂度为所以当数据越接近有序，直接插入排序算法的性能越好On2⑵空间效率仅占用个缓冲单元一一1O1⑶算法的稳定性稳定希尔排序又称缩小增量排序shell.基本思想把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次1缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束,技巧小组的构成不是2简单地“逐段分割”，而是将相隔某个增量的记录组成一个小组，让增量逐趟缩短例如依次取』，直到d d5,3d=1为止、优点让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多3例2设待排序的序列中有12个记录,它们的关键字序列T=65,34,25,87,12,38,56,46,14,77,92,23,请写出希尔排序的具体实现过程publicstaticvoid shellSortint[|a,int|]d,int numOflD{int i,j,k,m,span;int temp;int n=a.Length;〃共次循环form=0;mnumOfD;m++{numOfD//取本次的增量值span=d[m];〃共个小组fork=0;kspan;k++{spanfori=k;in-span;i=i+span{temp=a[i+span];j=i；whilej-1tempa[j]{a[j+span]=afj];j=j-span;a[j+span]=temp;算法分析开始时的值较大，子序列中的对象较少，排序速度较快；随着排序进展,值逐渐变小，子序列中对象个d d数逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快时间效率:Onlog2n2空间效率:因为仅占用个缓冲单元O1——1算法的稳定性不稳定练习欲将序列中的关键码按字母升序重排，则初始为的希尔排序一趟的结果是？

1.Q.H.C.Y.P.A.M.S.R.DEX d4答原始序列Q,H,C,Y,P,A,M,S,R,D,F,X一趟后shell P,A,C,S,Q,D,F,X,R,H,M,Y.以关键字序列为例，写出执行希尔排序取算法的各趟排序结2256,301,751,129,937,863,742,694,076,438d=5,3,l束时，关键字序列的状态解:原始序列256,301,751,129,937,863,742,694,076,438希尔排序第一趟d=5256301694076438863742751129937第二趟d=3076301129256438694742751863937第三趟d=l076129256301438694742751863937选择排序

10.3选择排序的基本思想是每次从待排序的数据元素集合中选取关键字最小或最大的数据元素放到数据元素集合的最前或最后，数据元素集合不断缩小，当数据元素集合为空时选择排序结束常用的选择排序算法直接选择排序1堆排序2直接选择排序

10.

3.1。