数据结构课程总结和思考

.....XX大学数据结构总结姓名：专业班级：学号：任课教师：完成时间：.....目录☆学习总结………3☆对赫夫曼树的研究……………5•赫夫曼树的基本定义………5•赫夫曼树的构造……………5•动态赫夫曼编码的实现…………………11☆对各类排序方法的总结………16☆学习感悟………18☆学习总结学习数据结构之前、一直以为数据结构是一门新的语言、后来才知道学习数据结构是为了更加高效的的组织数据、设计出良好的算法,而算法则是一个程序的灵魂。经过了一学期的数据结构了,在期末之际对其进行总结。首先,学完数据结构我们应该知道数据结构讲的是什么,数据结构课程主要是研究非数值计算的研究的程序设计问题中所出现的计算机处理对象以及它们之间关系和操作的学科。第一章主要介绍了相关概念,如数据、数据元素、数据类型以及数据结构的定义。其中,数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构,数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。最后着重介绍算法性能分析,包括算法的时间性能分析以及算法的空间性能分析。第二章具体地介绍了顺序表的定义、特点及其主要操作,如查找、插入和删除的实现。需要掌握对它们的性能估计。包括查找算法的平均查找长度,插入与删除算法中的对象平均移动次数。链表中数据元素的存储不一定是连续的,还可以占用任意的、不连续的物理存储区域。与顺序表相比,链表的插入、删除不需要移动元素,给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算〔如求表长、插入、查找、删除等、单链表的建立〔头插法和尾插法以及双向循环链表的定义、结构、功能和基本算法。第三章介绍了堆栈与队列这两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同,不同的是堆栈须遵循"先进后出"的规则,对堆栈的操作只能在栈顶进行；而队列要遵循"先进先出"的规则,教材中列出了两种结构的相应算法,如入栈、出栈、入队、出队等。在介绍队列时,提出了循环队列的概念,以避免"假溢出"的现象。算法上要求掌握进栈、退栈、取栈顶元素、判栈空盒置空栈等五种操作及掌握使用元素个数计数器及少用一个元素空间来区分队列空、队列满的方法。第四章串和数组中,我们知道串是一种特殊的线性表,是由零个或多个任意字符组成的字符序列。串的储存结构分为紧缩模式和非紧缩模式。基本运算需掌握求串长、串赋值、连接操作、求子串、串比较、串定位、串插入、串删除、串替换等。第六章二叉树的知识是重点内容。在介绍有关概念时,提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法〔递归算法、先序、中序和后序遍历非递归算法和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序。树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构,还有树、森林和二叉树的相互关系,树或森林怎样转化成二叉树,二叉树又如何转换为树和森林等算法。第七章介绍了图的概念及其应用,图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。最后两章集体说明了查找和排序算法,查找教材上介绍了静态查找表和哈希查找表,静态查找表中介绍了顺序查找、折半查找以及分块查找。哈希法中,学习要点包括哈希函数的比较；解决地址冲突的线性探查法的运用,平均探查次数；解决地址冲突的二次哈希法的运用。排序是使用最频繁的一类算法,可分为内部排序和外部排序。主要需要理解排序的基本概念,在算法上、需要掌握插入排序〔包括直接插入排序算法、折半插入排序算法,交换排序〔包括冒泡排序算法、快速排序递归算法,选择排序〔包括直接选择排序算法、堆排序算法等。由于平时上机练习的少,对于教材中很多算法都掌握的不是很熟悉、不过这些都是可以弥补的,我会在剩下的时间中不断练习书上给出的算法和练习,正如教材上说的,学习数据结构,仅从书本上学习是不够的,必须经过大量的程序设计实践,在实践中体会构造性思维方法,掌握数据组织与程序设计技术。以上就是我这学期对数据结构学习的总结。☆对赫夫曼树的研究•赫夫曼树的基本定义赫夫曼树〔Huffman又称最优二叉树,是一类带权路径长度最短的树,有着广泛的应用。首先需要弄清楚关于路径和路径长度的概念。树中两个结点之间的路径由一个结点到另一结点的分支构成。两结点之间的路径长度是路径上分支的数目。树的路径长度是从根结点到每一个结点的路径长度之和。

•赫夫曼树的构造〔1构成初始集合对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。〔为方便在计算机上实现算法,一般还要求以Ti的权值Wi的升序排列。〔2选取左右子树在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。〔3删除左右子树从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。〔4重复左右两步重复二和三两步,直到集合F中只有一棵二叉树为止。◎举个例子有个序列是<7,9,2,6,32,3,21,10>,求赫夫曼树步骤一：把这些点都看成是一个只有根结点的树的集合F步骤二：选2个值最小的树步骤三：在这些树的集合F中删除这2棵树然后把2,3构成一颗二叉树变成了〔5=2+3然后把这个树加入到集合F5代表这棵树的权值然后继续上述步骤选择5和6,把这2个构成二叉树。如下图：在F中删除5、6,并加入11这棵树,变成了：继续上述步骤选7和9在F中删除7和9,并加入16这棵树,则数变成了：继续上述步骤选10和11在F中删除10和11加入21这棵树继续上述步骤选16和21,构成二叉树在F中删除这16和21这两棵树,加入37这棵树继续上述步骤选21和32,构成二叉树在F中删除21和32这2两棵树,加入53这棵树还是继续上面步骤把F中的两棵树合并成一棵树赫夫曼树就构造完成了。•动态赫夫曼编码的实现所谓动态赫夫曼编码,指的就是每一个结点的权是不定的,那么在实现时,就以从键盘输入结点个数及权的值作为参考,实现动态赫夫曼编码。其主要思想及其过程都在下面的程序中体现。#include<iostream>#include<stdlib.h>#include<math.h>usingnamespacestd;intmecou;//定义全局变量计码长classHuffman{//构造Huffman类public:intparent;//和的位置 intvalue;//频率值intprenum;//该数的初始位置 intleft;//和的左加数位置 intright;//和的右加数位置};intmain<>{voidswap<Huffman&a,Huffman&b>;intPartition<Huffman*a,intp,intr>;voidQuickSort<Huffman*a,intp,intr>;voidHsort<Huffman*a,intn,intnl,intnr>;floatPHf<Huffman*a,intn,int<*c>[3]>;voidCPHf<Huffman*a,Huffman&b,inti>;voidRenew<Huffman*a,intn>;floatUnchange<intn,Huffman*a>;Huffmanp[50];//定义类数组 intcopy[50][3];//定义copy三维数组便于查询 intnum,n;//编码长num,最后数组长为n floatcnum,ucnum;//定义定长码所需码数总和,哈弗曼编码所需码数的总和 charf1,f2;//用于输入[,]两个符号 printf"输入字符数量：";//输入所需参数 cin>>num; n=2*num-1; cout<<"输入"<<num<<"个字符出现的频率："; cin>>f1; for<inti=1;i<=num;i++>{//对类的各项赋值 cin>>p[i].value; p[i].parent=0; p[i].prenum=i; p[i].left=0; p[i].right=0; } cin>>f2; cout<<"字符数量："<<num<<endl; cout<<"字符编号："; for<inti=1;i<=num;i++> cout<<i<<""; cout<<endl; cout<<"字符频率："; for<inti=1;i<=num;i++> cout<<p[i].value<<""; cout<<endl;ucnum=Unchange<num>;//得到定码长所需的码数总和 Hsort<p,n,1,num>;//根据频率值排序并循环添加和,再排序得到最终的序列 Renew<p,n>;//把最终序列里的和结点与加数结点对应便于向后找和结点 cnum=PHf<p,n,copy>;//输出哈弗曼编码后各编号的前缀码,得到哈弗曼编码所需总码数 cout<<"压缩率为"<<cnum/ucnum<<endl;//输出压缩率 system<"pause">;}voidRenew<Huffman*a,intn>{//找到该值的左右加数将其的位置写入加数的和 for<inti=3;i<=n;i++>{//对排完序的数组进行搜索 if<a[i].left!=0&&a[a[i].left].parent==0>//找到没有完成对应的和结点和它的加数结点 { a[a[i].left].parent=i;//在其左加数结点的和位置写入其现在的位置 a[a[i].right].parent=i;//在其右加数结点的和位置写入其现在的位置 } }}voidswap<Huffman&a,Huffman&b>{//交换a,b的类值 intl; l=a.value; a.value=b.value; b.value=l; l=a.prenum; a.prenum=b.prenum; b.prenum=l; l=a.left; a.left=b.left; b.left=l; l=a.right; a.right=b.right; b.right=l;}intPartition<Huffman*a,intp,intr>{//根据类值中的频率值由小到大排序 inti=p; intj=r+1; intx=a[p].value; while<true>{ while<a[++i].value<x&&i<r>; while<a[--j].value>x>; if<i>=j>break; swap<a[i],a[j]>; } swap<a[p],a[j]>; returnj;}voidQuickSort<Huffman*a,intp,intr>{//根据类值中的频率值由小到大排序 if<p<r>{intq=Partition<a,p,r>; QuickSort<a,p,q-1>;QuickSort<a,q+1,r>; }}voidHsort<Huffman*a,intn,intnl,intnr>{//根据类值中的频率值由小到大排序,取最小的两个数相加,//和放在数组最后,移动指针继续排序if<nr<n>{QuickSort<a,nl,nr>;a[++nr].value=a[nl].value+a[nl+1].value;a[nr].left=nl;a[nr].right=nl+1;a[nr].parent=0;a[nr].prenum=nr;nl=nl+2;Hsort<a,n,nl,nr>;}}voidCPHf<Huffman*a,Huffman&b,inti>{//输出字符的前缀码,得到码数的长度值 if<b.parent!=0>//当该数的和位置上的数不为0时 { CPHf<a,a[b.parent],b.parent>;//找到它的和继续递归 mecou++;//编号i的前缀码长度加1 cout<<<i+1>%2;//输出编号i前缀码中的一个码1或0 }}floatPHf<Huffman*a,intn,int<*c>[3]>{ intave=0; intw=<n+1>/2;//得到编码数,w=numfor<inti=1;i<=n-1;i++> { if<a[i].prenum<=<n+1>/2>//通过类值的最初位置搜索需要编码的数,排除他们的和 {c[a[i].prenum][0]=i;//将编码值按其最初位置存放在三维数组C中,第一维放它在a的编号 c[a[i].prenum][1]=a[i].value;//第二维存放其频率 } }//c[1:w][0],c[1:w][[1]里存放1---w编号在a中的编号值和频率值 for<inti=1;i<=w;i++>{ inte=c[i][0];//e等于第i个编码在a上的位置c[i][0] mecou=0;//清空mecou的值 cout<<"第"<<i<<"个字符的前缀码为："; CPHf<a,a[e],e>;//调用CPHf输出字符的前缀码 c[i][2]=mecou;//第i个字符前缀码的长度mecou,存放在c[i][2]里ave+=mecou*c[i][1];//编号的前缀码长乘以频率的总和cout<<endl; }floatpp=<float>ave;//转换类型cout<<"使用变长码编码需要"<<pp<<"位"<<endl; returnpp;//返回总码数}floatUnchange<intn,Huffman*a>{//得到定长编码的总码数 floatall=0; for<inti=1;i<=n;i++> all+=a[i].value;//计算频率和all floatl=<<int><log<<float>n>/log<2.0>>+1>*all;//利用方程式计算定长码所需编码位数cout<<"使用定长码编码需要"<<l<<"位"<<endl; returnl;//返回定长码所需码数的总个数}☆对各类排序算法的总结1、快速排序〔QuickSort快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。〔1

如果不多于1个数据,直接返回。〔2

一般选择序列最左边的值作为支点数据。〔3

将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。〔4

对两边利用递归排序数列。快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。2归并排序〔MergeSort归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。3堆排序〔HeapSort堆排序适合于数据量非常大的场合〔百万数据。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。4

Shell排序〔ShellSortShell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O<nlogn>。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。5

插入排序〔InsertSort插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。6

冒泡排序〔BubbleSort冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。它是O<n^2>的算法。7交换排序〔ExchangeSort和选择排序〔SelectSort这两种排序方法都是交换方法的排序算法,效率都是

O<n2>。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段,在实际中使用较少。8基数排序〔RadixSort基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法,但是它只能用于整数的排序,如果我们要把同样的办法运用到浮点数上,我们必须了解浮点数的存储格式,并通过特殊的方式将浮点数映射到整数上,然后再映射回去,这是非常麻烦的事情,因此,它的使用同样也不多。而且,最重要的是,这样算法也需要较多的存储空间。9

总结排序法

平均时间最差情形稳定度额外空间备注冒泡

O<n2>

O<n2>

稳定O<1>