数据结构课程总结和思考.docx
《数据结构课程总结和思考.docx》由会员分享，可在线阅读，更多相关《数据结构课程总结和思考.docx（23页珍藏版）》请在冰点文库上搜索。
数据结构课程总结和思考
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）
然后把这个树加入到集合F
5代表这棵树的权值
然后继续上述步骤
选择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
#include
#include
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<<"输入"<";
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<<"字符数量：
"<cout<<"字符编号：
";
for（inti=1;i<=num;i++）
cout<cout<cout<<"字符频率：
";
for（inti=1;i<=num;i++）
cout<cout<ucnum=Unchange（num）;//得到定码长所需的码数总和
Hsort（p,n,1,num）;
//根据频率值排序并循环添加和，再排序得到最终的序列
Renew（p,n）;
//把最终序列里的和结点与加数结点对应便于向后找和结点
cnum=PHf（p,n,copy）;
//输出哈弗曼编码后各编号的前缀码，得到哈弗曼编码所需总码数
cout<<"压缩率为"<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].valuewhile（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（pintq=Partition（a,p,r）;
QuickSort（a,p,q-1）;
QuickSort（a,q+1,r）;
}
}
voidHsort（Huffman*a,intn,intnl,intnr）
{//根据类值中的频率值由小到大排序，取最小的两个数相加，
//和放在数组最后，移动指针继续排序
if（nrQuickSort（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=num
for（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<<"第"<";
CPHf（a,a[e],e）;//调用CPHf输出字符的前缀码
c[i][2]=mecou;//第i个字符前缀码的长度mecou，存放在c[i][2]里
ave+=mecou*c[i][1];//编号的前缀码长乘以频率的总和
cout<}
floatpp=（float）ave;//转换类型
cout<<"使用变长码编码需要"<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<<"使用定长码编码需要"<returnl;//返回定长码所需码数的总个数
}
☆对各类排序算法的总结
1、快速排序（QuickSort）
快速排序是一个就地排序，分而治之，大规模递归的算法。
从本质上来说，它是归并排序的就地版本。
快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。
（2） 一般选择序列最左边的值作为支点数据。
（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。
尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。
快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。
合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3堆排序（HeapSort）
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。
这对于数据量非常巨大的序列是合适的。
比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。
接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 Shell排序（ShellSort）
Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。
平均效率是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）
n小时较好
交换
O（n2）
O（n2）
不稳定
O
（1）
n小时较好
选择
O（n2）
O（n2）
不稳定
O
（1）
n小时较好
插入
O（n2）
O（n2）
稳定
O
（1）
大部分已排序时较好
基数
O（logrd）
O（logrd）
稳定
O（n）
d是关键字项数（0-9），
r是基数（个十百）
Shell
O（nlogn）
O（ns）1不稳定
O
（1）
s是所选分组
快速
O（nlogn）
O（n2）
不稳定
O（nlogn）
n大时较好
归并
O（nlogn）
O（nlogn）
稳定
O
（1）
n大时较好
堆
O（nlogn）
O（nlogn）
不稳定
O
（1）
n大时较好
☆学习心得
无论我们学习什么课程，概念永远是基础，所有的知识都是建立在基础概念之上的。
我们要将概念熟记于心，然后构建知识框架。
数据结构包括线性结构、树形结构、图状结构或网状结构。
线性结构包括线性表、栈、队列、串、数组、广义表等，栈和队列是操作受限的线性表，串的数据对象约束为字符集，数组和广义表是对线性表的扩展：
表中的数据元素本身也是一个数据结构。
除了线性表以外，栈是重点，因为栈和递归紧密相连，递归是程序设计中很重要的一种工具。
树状结构中的重点自然是二叉树和哈弗曼树了。
对于二叉树的很多操作都是基于对二叉树的遍历，掌握了如何遍历，很多问题也就迎刃而解了，比如对二叉树结点的查找访问、统计二叉树中叶子结点的数目、求二叉树的深度等。
哈弗曼编码也有着很广泛的应用。
对于图状结构，主要学习图的存储结构及图的遍历。
对算法的学习是学习数据结构的关键。
要注重对算法的掌握。
对于一个算法，如果我们不是很理解的话，可以手动将算法走一遍，慢慢理解该算法的思想。
学习这门课程的最终目的，还是要学会如何设计算法，这需要我们长期的练习和思考。
不得不说，在学习这门课的过程中，我还是暴露了一些问题的，数据结构是一门既重视理论，又重视实践的课程，而在我的学习中，理论占了绝大多数的时间，反而没有什么时间来研究具体的代码的实现，我觉得这一点是非常不好的，在更多时候，我过分注重基础知识的掌握，反而忘记了实践是检验真理的唯一标准，我想，在下学期对算法的学习过程中，我会注意这一点，将理论和实践紧密地结合在一起。
升级会员 