数据结构课程论文

“数据结构与算法”课程学习总结报告

本书主要讲述了线性结构、树结构和图结构中数据表示及数据处理的方法，书中对各类数据结构的分析按照“算法思想——算法实现过程分析——算法实现程序——性能分析”的顺序进行讲述，算法采用C语言描述。本书我们学习了10章，每章分析如下：

第一章“数据结构和算法”作为全书的引导，主要包括有关数据、数据类型、数据结构、算法、算法实现、C语言使用中相关问题和算法分析等基本概念和相关知识。其中重点式数据、数据类型、数据结构、算法等概念；C语言中则介绍了指针、结构变量、函数、递归、动态存储分配、文件操作、程序测试与调试问题等内容。由于本章主要是复习以前C语言的内容，所以本章不太难，能基本掌握。但关系全书的时间性能分析有些未能全部掌握。

第二章“顺序表及其应用”主要介绍的是线性逻辑结构的数据在顺序存储方法下的数据结构顺序表（包括顺序串）的概念、数据类型、数据结构、基本运算及其相关应用。其中重点一是顺序表的定义、数据类型、数据结构、基本运算和性能分析等概念和相关知识。二是顺序表的应用、包括查找问题（简单顺序查找、二分查找、分块查找）、排序问题（直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、归并排序）、字符处理问题（模式匹配）等内容。本章重点和难点在查找和排序问题的算法思想上，6种排序方法的性能比较。本章未掌握的为希尔排序、快速排序、归并排序的时间复杂度分析。

第三章“链表及其应用”主要介绍的是线性逻辑结构的数据在链接存储方法下数据结构链表的相关知识。主要是单链表、循环链表的数据类型结构、数据结构、基本运算及其实现以及链表的相关应用问题，在此基础上介绍了链串的相关知识。在应用方面有多项式的相加问题、归并问题、箱子排序问题和链表在字符处理方面的应用问题等。本章未完全掌握的是循环链表的算法问题和C的描述。链表的应用中归并和箱子排序较难。

第四章“堆栈及其应用”介绍在两种不同的存储结构下设计的堆栈，即顺序栈和链栈的相关知识，了解堆栈的相关应用，掌握应用堆栈来解决实际问题的思想及方法。本章主要内容是顺序栈和链栈的概念、数据类型、数据结构定义和基本运算算法及其性能分析。本章堆栈算法思想较为简单，所以能较好掌握，但表达式计算问题未掌握好的

第五章“队列及其应用”主要介绍顺序存储和链接存储方法下的两种队列、顺序（循环）队列和链队列的数据结构、基本运算及其性能分析以及应用。顺序队列(重视是循环队列）和链队列的概念、数据类型描述、数据结构和基本运算算法及其性能分析等。本章同堆栈有点类似，算法思想较为简单，所以能较好掌握；但难点重在循环队列对空、堆满的判断条件问题。基数排序有些难度。

第六章“特殊矩阵、广义表及其应用”将学习数组、稀疏矩阵和广义表的基本概念，几种特殊矩阵的存储结构及其基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。本章的重点是相关数据结构的存储结构及其基本运算算法。掌握了特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解了稀疏矩阵的计算和广义表的存储结构及其基本运算。

第七章“二叉树及其应用”的知识结构主要是：非线性结构数据二叉树的定义、性质、逻辑结构、存储结构及其各种基本运算算法，包括二叉树的建立、遍历、线索化和表达式求值等算法。在此基础上，介绍二叉树的一些应用问题，包括哈夫曼编码问题、（平衡）二叉排序树问题和堆排序问题等。本章二叉树节点的插入和删除，平衡二叉排序树较为复杂，未

能掌握好。

第八章“树和森林及其应用”介绍树和森林的数据结构、基本算法及其性能分析，树和森林与二叉树之间的转换算法等，在此基础上介绍树的应用---B树，应用B树来实现数据元素的动态查找。本章基本掌握树和森林的概念和性质、数据结构、树的基本算法及性能分析，树和二叉树间的转换及其算法，并用应用B树来实现数据元素的动态查找未能掌握好。

第九章“散列结构及其应用”是逻辑结构“集合型”的数据元素在散列存储方法下的数据结构及其应用知识内容。主要介绍散列结构的概念、散列结构的概念、散列存储结构的概念---散列表、散列函数和散列表中解决冲突的处理方法---开放定址法、链地址法以及散列表的基本算法及其性能分析，在散列结构的应用方面介绍散列结构的查找问题。LZW压缩/解压缩问题和直接存取文件问题。本章概念较为多，所以掌握不太好。

第十章“图及其应用”是逻辑结构为“图形”的数据结构及其应用知识内容，主要介绍图的定义和基础知识，图的4种存储结构。图的基本算法以及图的典型应用问题（最小生成树、最短路径、拓扑排序和关键路径等）。通过本章学习，我掌握了图的概念和基本性质，图的存储结构（邻接矩阵和邻接表）及其基本算法、图的遍历及算法。了解了图的逆邻接表、十字链表、邻接多重表存储结构及其基本算法，关键路径求解算法未能掌握好，不能灵活运用图的不同数据结构和遍历算法解决复杂的应用问题。 学习了本书我对数据结构与算法有了更深的理解，数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。包括4类基本的结构：集合、线形结构、树形结构、图状或网状结构。通俗点就是数据的逻辑结构，比方说这些数据在内存中以什么样的结构存放。算法实际是编程过程中完成一件事采用的方法，比方说现实生活中做数学题时两个人都将题完成但是他们之间有一个用的时间很短就是因为采用了简便的方法。同样在编程过程中采用好的算法可以降低程序的时间和空间复杂度。 学习本书为以后操作系统、编译原理、数据库管理系统、软件工程、人工智能等的学习都是十分有益的，而且所有的计算机系统软件和应用软件都要用到各种类型的数据结构。

建议老师以后课堂多和学生进行互动，多提一些课堂问题让大家回答和积极思考，可以思考除了课本以外的数据结构，多尝试一些新的算法思想。