查找算法总结
静态查找
顺序表的查找-顺序查找:查找成功时的平均查找长度ASL==,查找不成功时的比较次数为n+1,故查找成功与不成功等概率时的平均查找长度为+=,时间复杂度为O(n);
有序表的查找-折半查找:具有n个节点的判定树深度为+1,平均查找长度为log2-1,时间复杂度为O。
索引顺序表的查找:块的查找用顺序查找或折半查找(其他也可),块内只能用顺序查找。
动态查找
二叉排序树:掌握插入、删除过程,时间复杂度为O(随机情况下)
平衡二叉树(AVL树):掌握插入、删除过程,含有n个结点的平衡二叉树的最大深度为
logφ-2(其中φ=),时间复杂度为O。
B-树:掌握概念,插入和删除过程。在含有n个关键字的B-树上进行查找时,从根节点到关键字所在结点的路径上涉及的结点数不超过log+1,时间复杂度为O(log)。
B+树:叶子结点本身依关键字的大小自小而大顺序链接,每次查找都是走了一条从根到叶子节点的路径。
哈希表的查找:常用的构造哈希函数的方法:
1、 直接定址法 H(key)=key 或 H(key)=a·key+b
2、 数字分析法
3、 平方取中法
4、 折叠法
5、 除留余数法 H(key)=key MOD p,p≤m
处理冲突的方法
1、 开放定址法 Hi=(H(key)+di) MOD m,i=1,2,…,k(k≤m-1)
di有三种取法:⑴线性探测再散列
⑵二次探测再散列
⑶伪随机探测再散列
2、 再哈希法 Hi= RHi(key)
3、 链地址法
平均查找长度与冲突的处理方法和装填因子有关。
排序算法总结与比较
①n比较小的时候,适合插入排序和选择排序;
②基本有序的时候,适合直接插入排序和冒泡排序;
③n很大但是关键字的位数较少时,适合链式基数排序;
④n很大的时候,适合快速排序、堆排序 、归并排序;
⑤无序的时候,适合快速排序;
⑥稳定的排序:冒泡排序、插入排序、归并排序、基数排序;
⑦复杂度是O(nlogn):快速排序、堆排序、归并排序;
⑧辅助空间(大 次大):归并排序、快速排序;
⑨好坏情况一样:简单选择排序(n^2),堆排序(nlogn),归并排序(nlogn);
⑩最好是O(n)的:插入排序、冒泡排序。
《数据结构与算法》课程学习总结报告
0704013015 07计本(3)班 张浩
本学期开设的《数据结构与算法》课程已经告一段落,现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。
一、《数据结构与算法》知识点
在课本的第一章便交代了该学科的相关概念,如数据、数据元素、数据类型以及数据结构的定义。其中,数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类:集合型、线性、树形和图形结构,数据元素的存储结构分为:顺序存储、链接存储、索引存储和散列存储四类。紧接着介绍了一些常用的数据运算。最后着重介绍算法性能分析,包括算法的时间性能分析以及算法的空间性能分析。
第二章具体地介绍了顺序表的概念、基本运算及其应用。基本运算有:初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有:简单顺序查找、二分查找和分块查找。排序方法有:直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等。最后介绍了顺序串的概念,重点在于串的模式匹配。
链表中数据元素的存储不一定是连续的,还可以占用任意的、不连续的物理存储区域。与顺序表相比,链表的插入、删除不需要移动元素,给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算(如求表长、插入、查找、删除等)、单链表的建立(头插法和尾插法)以及双向循环链表的定义、结构、功能和基本算法。
堆栈与队列是两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同,不同的是堆栈须遵循“先进后出”的规则,对堆栈的操作只能在栈顶进行;而队列要遵循“先进先出”的规则,教材中列出了两种结构的相应算法,如入栈、出栈、入队、出队等。在介绍队列时,提出了循环队列的概念,以避免“假溢出”的现象。
第六章介绍了特殊矩阵和广义表的概念与应用。其中,特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵,书中分别详细介绍了它们的存储结构。稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构,关于它的应用,课本中举了m元多项式的表示问题。
第七章二叉树的知识是重点内容。在介绍有关概念时,提到了二叉树的性质以及两种特殊的二叉树:完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法(递归算法、先序、中序和后序遍历非递归算法)和线索二叉树。二叉树的应用:基本算法、哈弗曼树、二叉排序树和堆排序。
树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构,还有树、森林和二叉树的相互关系,树或森林怎样转化成二叉树,二叉树又如何转换为树和森林等算法。 散列结构是一种查找效率很高的一种数据结构。本章的主要知识点有:散列结构的概念及其存储结构、散列函数、两种冲突处理方法、线性探测散列和链地址散列的基本算法以及散列结构的查找性能分析。
最后一章介绍了图的概念及其应用,是本书的难点。图的存储结构的知识点有:邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有:有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。
二、对各知识点的掌握情况
总体来看,对教材中的知识点理解较为完善,但各个章节均出现有个别知识点较为陌生
的现象。现将各个章节出现的知识点理解情况列举如下。
第一章中我对数据和数据结构的概念理解较为透彻,熟悉数据结构的逻辑结构和存储结构。而对算法的时间、空间性能分析较为模糊,尤其是空间性能分析需要加强。
第二章,顺序表的概念、生成算法理解较为清晰,并且熟悉简单顺序查找和二分查找,对分块查找较为含糊;排序问题中,由于冒泡排序在大一C语言课上已经学习过,再来学习感觉很轻松。对插入排序和选择排序理解良好,但是,在实际运用中仍然出现明显不熟练的现象。由于在归并排序学习中感觉较吃力,现在对这种排序方法仍然非常模糊,所以需要花较多的时间来补习。此外串的模式匹配也是较难理解的一个地方。
链表这一章中,除对双向循环链表这一知识点理解困难之外,其他的知识点像单链表的建立和基本算法等都较为熟悉。
接下来的有关堆栈以及队列的知识点比较少,除有关算法较为特殊以外,其余算法都是先前学过的顺序表和链表的知识,加上思想上较为重视,因此这部分内容是我对全书掌握最好的一部分。不足之处仍然表现在算法的性能分析上。
在学习第六章时感觉较为吃力的部分在于矩阵的应用上,尤其对矩阵转置算法的C语言描述不太理解。稀疏矩阵相加算法中,用三元组表实现比较容易理解,对十字链表进行矩阵相加的方法较为陌生。
第七章是全书的重点,却也有一些内容没有完全理解。在第一节基本概念中,二叉树的性质容易懂却很难记忆。对二叉树的存储结构和遍历算法这部分内容掌握较好,能够熟练运用,而对于二叉树应用中的哈弗曼树却比较陌生。
第八章内容较少,牵涉到所学的队列的有关内容,总体来说理解上没有什么困难,问题依旧出现在算法的性能分析上。
散列结构这一章理解比较完善的知识点有:基本概念和存储结构。散列函数中直接定址法和除留余数法学得比较扎实,对数字分析法等方法则感觉较为陌生。对两种冲突处理的算法思想的理解良好,问题在于用C语言描述上。
最后一章,图及其应用中,图的定义、基本运算如图的生成等起初理解有困难,但随着学习深入,对它的概念也逐步明朗起来。邻接矩阵、邻接表和逆邻接表掌握较好,而对十字链表和邻接多重表则较为陌生。感觉理解较为吃力的内容还有图的遍历(包括深度和广度优先遍历),最小生成树问题也是比较陌生的知识点。最短路径和AOV网学习起来感觉比较轻松,而对于C语言描述却又不大明白。
三、学习体会
接触这门课程以前,我对该课程所学的内容有许多疑点,例如:这门课是否是在介绍一种新的计算机语言?如果不是,那么学习这门课程的用途是什么?为什么市面上各种介绍数据结构的资料采用了不同的计算机语言,如C、C++还有Java?我的C语言学得不好,对学习这门课是否有影响??
在学习伊始,老师就明确提出它不是一种计算机语言,不会介绍新的关键词,而是通过学习可以设计出良好的算法,高效地组织数据。一个程序无论采用何种语言,其基本算法思想不会改变。联系到在大一和大二上学期学习的C和C++语言,我深刻认识到了这一点。“软件开发好比写作文,计算机语言提供了许多华丽的辞藻,而数据结构则考虑如何将这些辞藻组织成一篇优秀的文章来。”在学习这门课中,要熟悉对算法思想的一些描述手段,包括文字描述、图形描述和计算机语言描述等。因此,计算机语言基础是必须的,因为它提供了一种重要的算法思想描述手段——机器可识别的描述。
这门课结束之后,我总结了学习中遇到的一些问题,最为突出的,书本上的知识与老师的讲解都比较容易理解,但是当自己采用刚学的知识点编写程序时却感到十分棘手,有时表现在想不到适合题意的算法,有时表现在算法想出来后,只能将书本上原有的程序段誊写到
自己的程序中再加以必要的连接以完成程序的编写。针对这一情况,我会严格要求自己,熟练掌握算法思想,尽量独立完成程序的编写与修改工作,只有这样,才能够提高运用知识,解决问题的能力。
四、对《数据结构与算法》课程教学的建议
1、建议在上课过程中加大随堂练习的分量,以便学生能当堂消化课堂上学习的知识,也便于及时了解学生对知识点的掌握情况,同时有助于学生保持良好的精神状态。
2、建议在课时允许的情况下,增加习题课的分量,通过课堂的习题讲解,加深对知识点的掌握,同时对各知识点的运用有一个更为直观和具体的认识。
以上便是我对《数据结构与算法》这门课的学习总结,我会抓紧时间将没有吃透的知识点补齐。今后我仍然会继续学习,克服学习中遇到的难关,在打牢基础的前提下向更深入的层面迈进!
一插入排序InsertionSort1基本思想每次将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置使数列依然有序直到待…
数据结构各种排序算法总结计算机排序与人进行排序的不同计算机程序不能象人一样通览所有的数据只能根据计算机的quot比较quot原理在…
数据结构与算法总结姓名:**学号:**班级:12计本(2)班这个学期在老师的带领下我们学习了数据结构与算法这门课程。在本次数据结构…
排序总结排序方法平均时间最坏时间辅助存储简单排序O(n2)O(n2)O(1)快速排序O(nlogn)O(n2)O(logn)堆排序…
数据结构实验课程之手工执行一下排序算法写出每一趟排序结束时的关键码状态includeltstdiohgtincludeltstdl…
冒泡排序(BubbleSort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换…
排序算法总结选择法排序:for(i=0;i9;i++){max=i;for(j=i+1;j10;j++)if(a[max]a[j]…
一、顺序查找条件:无序或有序队列。原理:按顺序比较每个元素,直到找到关键字为止。时间复杂度:O(n)二、二分查找(折半查找)条件:…
算法学习报告学习总结:对于算法这门课,要善于给出算法的形式化表示,学会用一些算法分析的数学基础,原来的时间复杂度的分析,一般是采用…
一、进程(作业)调度算法l先来先服务调度算法(FCFS):每次调度是从就绪队列中,选择一个最先进入就绪队列的进程,把处理器分配给该…
镇康县人民医院“爱国卫生月”活动工作总结根据县爱委办的有关文件精神,镇康县人民医院高度重视清洁卫生工作,在全院开展了以“开展爱国卫…