…………………………装………………………………订………………………………线………………………………
课 程 学 习 总 结班级 | 学号 | 姓名 | 考核成绩 | ||||
一、学习内容总结（按章节进行） 第一章：数据结构和算法 本章主要是对数据、数据类型、数据结构、算法及算法分析等基本概念的掌握，而如何合理地组织数据、高效地处理数据正是扩大计算机领域、提高软件效率的关键，所以对这些概念的理解就显得十分重要。 数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称，其基本单位是数据元素，而数据类型是一个同类值的集合和定义在这个值集上的一组操作的总称。在高级程序语言中定义一种数据类型时，编译程序编译系统就能获得如下信息：（1）、一组性质相同的值的集合；（2）、一个预订的存储体系；（3）、定义在这个值集合上的一组集合。数据结构是指数据元素之间的关系，它包括数据的逻辑结构、存储结构、一组运算集合；数据的逻辑结构（即数据结构）分为线性结构和非线性结构，数据的存储方法有：顺序存储方法、连接存储方法、索引存储方法和散列存储方法。接下来便是关于算法的有关概念，算法是为解决一个特定问题而采取的确定的有限步骤集合，它具有有穷性、确定性、可行性、输入和输出。关于算法的性能分析，分为时间性能分析和空间性能分析，在这里要记得常见的时间复杂度的比较：O（1）< O（logn）< O（n）< O（nlogn）< （n）< O（n）< O（n）< O（2）。 第二章：顺序表及其应用 顺序表作为一种简单而又常用的数据结构，应用范围较为广泛，本章主要是对顺序表、顺序表的结构、数据类型、基本算法及相关应用的介绍。 首先顺序表是一种简单而常用的数据结构，其应用范围较为广泛，它的基本运算包括初始化表、求表长、查表中元素及删除元素等。在这其中，进行插入和删除操作时需要大量移动元素，算法的时间复杂度为O（n）。其次是关于查运算，主要有简单顺序查、二分查及分块查等查方法。其中以分块查的效率最优，但必须在有序表中完成查运算。接下来是关于排序的算法，通常排序的方法有直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序，它们的算法时间复杂度如下：
由上表可以看出： 完全二叉树算法 1、就时间性能而言，快速排序和归并排序较好，但快速排序在最坏的情况下的时间性能不如归并排序。 2、归并排序的时间性能虽然很好，但它所需要的辅助存储空间最多，空间性能较差。 3、从方法的稳定性来看，时间性能较好的内部排序方法如快速排序、希尔排序等都是不稳定的。 第三章：链表及其应用 链表是一种简单、常用的数据结构，与顺序表相比，具有插入、删除结点不需要移动元素，不必事先估计存储空间大小等优点，操作较为灵活。它有六种基本运算：（1）、置空表 （2）、求表长 （3)、按序号取元素 （4）、按值查 (5)、插入 （6）、删除。 单链表即链表的每个结点只有一个指针域，用来存储其直接后继的存储位置。但是这样就使得对结点前面的元素的操作很困难，所以就在每个结点增加一个指向其前驱结点的指针域，从而构成双向链表。同时由于每个结点的地址既存放在其前驱结点的后继指针中，又存放在其后继结点的前驱指针域中，所以双向链表的插入操作分为前插和后插。 第四章：堆栈及其应用 首先要明白栈是一种受限制的线性结构，遵守“先进后出”的规则，其插入与删除操作都在栈顶进行。 其次根据顺序存储和链接存储，栈分为顺序栈和链栈。其中顺序栈栈是用地址连续的存储空间依次存储栈中数据元素，并记录当前栈顶数据元素的位置；基本算法包括置空栈、判栈空、判栈满、取栈顶元素、入栈和出栈。而链栈则使用链式存储堆栈的数据元素，并记录当前栈顶数据元素的位置；每个结点包括data数据域：用来存放数据元素的值，next指针域：用来存放其直接后继结点的存储地址，其基本运算和顺序栈相同。 最后是关于堆栈的应用：（1）、数值转换问题；由于在将十进制数N转换为d进制数时，最先得到的余数是d进制数的最低位，在显示结果时需要最后输出；而最后求得的余数是d进制数的最高位，需要最先输出。这与栈的“先入后出”性质相吻合，所以可用栈来存放逐次求得的余数，然后输出。（2）、括号匹配问题；当读取一个表达式时，一旦读到括号就进栈，而读到下一个括号时就与栈中括号比较，若相匹配，则出栈，否则继续读取表达式。到最后，如果栈为空栈，则说明括号匹配，否则括号不匹配。 第五章：队列及其应用 首先和栈一样，要知道队列是一种受限制的线性结构，遵守“先进先出”的规则，其插入在队尾、删除在对头。 其次根据顺序存储和链式存储，队列也分为顺序队列和链队列。其中顺序队列是用地址连续的向量空间依次存储队列中的元素，同时记录当前对头元及队尾元素在向量中的位置。值得注意的是在顺序循环队列中存在“假溢出”的现象，即当rear=maxlen-1时，认为队满。但随着对头元素的不断出对，data数组会出现空单元，此时不一定是真的队满。同时队满的条件为：Q->front==(Q->rear+1)%maxlen，对空条件为：Q->front==Q->rear。然后是链队列，即在存储器中占用任意的、连续或不连续的物理存储区域，使用动态结点空间分配；在这其中，值得注意的是链队列不存在队满的情况。 第六章：特殊矩阵、广义表及其应用 首先是关于矩阵的概念即存储方法； 1、二维数组中元素aij的地址为：（1）、以行序为主存储，Loc（a）=Loc（a）+[j*（m+1）+i]*d （2）、以列序为主存储，Loc（a）=Loc（a）+[i*（n+1）+j]*d，其中m为行数、n为列数、d为每个元素所占的存储单元的个数。 2、对称矩阵：即将下三角存储在一个一维数组sa[k]中，其中0≤k<(n+1)/2；当i≥j时，k=i*（i+1）/2+j，当i<j时，k=j*（j+1）/2+i 3、三角矩阵：和对称矩阵的存储思路一样用一维数组sa[k]存储，若是上三角矩阵（下三角中元素均为常数c），则当i≥j时，k=i*（i+1）/2+j，当i<j时，k=n*（n+1）/2；若是下三角矩阵（上三角中元素均为常数c），则当i≤j时，k=i*（2n-i+1）/2+j-i，当i>j时，k=n*（n+1）/2 4、对角矩阵：同样存储在一维数组sa[k]中，k=2i+j 5、稀疏矩阵：即矩阵中非零元素个数远远小于矩阵元素个数，可用三元组表存储，将非零元素的值与其行号、列号存放在一起。 其次是关于广义表的概念；广义表是n（n≥0）个元素a、a、a、…、a的有限序列，而ai或是原子或是一个广义表，所以广义表是递归定义。 第七章：二叉树及其应用 首先关于二叉树的概念及其性质；二叉树是由n（n≥0）个结点组成的有限集合，其中：（1）、当n=0时，为空树 （2）、当n>0时，有且仅有一个特定的结点，成为二叉树的根。在这其中有两种特殊的二叉树，满二叉树和完全二叉树。满二叉树是满足如下条件的二叉树：（1）、任一非叶子结点均有两个孩子 （2）、对于二叉树的任一层，若该层上有一个结点有孩子，则该层上所有结点均有孩子；而完全二叉树是在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。同时二叉树具有如下五个性质：（1）、在二叉树的第i层上至多有2（i-1）个结点（i>0） （2）、深度为k的二叉树至多有2（k）-1个结点（k>0） （3）、对任意一棵非空二叉树，若果其叶子结点数为n，度为2的结点数为n，则n=n+1（4）、有n个结点的完全二叉树（n>0）的高度为∟log2n」+1 （5）、若对满二叉树或完全二叉树按照“从上到下，每层从左到右，根结点编号为1”的方式编号，则编号为i的结点，它的两个孩子结点编号分别为2i和2i+1，它的父节点编号为i/2。 其次是二叉树的存储结构；与线性结构相似，它也分为顺序存储和链接存储。顺序存储是按在完全二叉树中的编号顺序，依次存储在一维数组中。这样的存储方式可以很方便地到任一结点的父结点及左右孩子，但对于一般的二叉树会造成很大的空间浪费，且在插入或删除结点时需大量移动节点，不利于运算的实现。那么就引出了二叉树的链接存储，每个结点包括三个域，lchild指针域：记录该结点左孩子的地址、rchild指针域：记录该结点右孩子的地址、data域：存储该结点的信息。 接下来是二叉树的遍历及线索化，不仅要能对二叉树进行遍历、线索化操作，而且还要能够根据给出的遍历结果构造出二叉树。在线索化中，要知道每个结点的ltag=0表示lchild域指向该结点的左孩子、ltag=1表示lchild域指向该结点的前驱、rtag=0表示rchild域指向该结点的右孩子、rtag=1表示rchild域指向该结点的后继。 最后是二叉树的应用，例如哈夫曼树：为数据压缩提供了一种方法、二叉排序树：即中序遍历的结果是递增的有序序列。 第八章：树和森林及其应用 首先是关于树和森林的有关概念及存储结构；树或森林与二叉树之间有一个自然地一一对应关系，任何一个森林或一棵树可以唯一地对应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。在这里，要会如何将树或森林转换成二叉树、二叉树转换成树或森林。对于树的顺序存储结构：双亲表示法，链接存储结构：（1）、孩子表示法 （2）、孩子兄弟表示法，只需了解。 其次是树和森林的遍历，要知道树只有先序遍历和后序遍历、森林只有先序遍历和中序遍历，且（1）、树的先序遍历与二叉树的先序遍历相同 （2）、树的后序遍历与二叉树的中序遍历相同 （3）、森林的先序遍历和中序遍历分别与二叉树的先序遍历和中序遍历结果相同。 最后是树的一个典型应用——B树，它是一种平衡的多路查树，学习是根据实例走一遍算法，理解算法即可。 第九章：散列结构及其应用 散列结构是以存储结点中的关键字作为自变量，通过确定的函数H（即散列函数或哈希函数）进行计算，把所求的函数值作为该结点的存储地址，并将该结点或结点的关键字存储在这个地址中，在这里重点是要掌握散列和冲突处理这两个概念。 首先是散列，主要是散列函数的构造。（1）、直接定址法：H（key）=a*key+b （2）、除留余数法：H（key）=key mod p，其中p<=m，m为散列表长度 （3）、数字分析法：分析关键字集合中每个关键字中每一位数码的分布情况，出数码分布均匀的若干位作为关键字的存储地址 （4）、平方取中法：将关键字求平方后，取其中间的几位数字作为散列地址 （5）、折叠法：将关键字分隔成位数相等的几部分，取这几部分的相加之和作为关键字的散列地址。 其次是冲突处理；由于散列函数很可能将不同的关键字计算出相同的散列地址，所以就需要为发生冲突的关键字结点到一个“空”的散列地址。冲突处理的方法有1、开放定址法：Hi=（H（key）+di） mod m，i=1,2,3，…，K（K≤m-1） 例如（1）、线性探测再散列，取di=1,2,3，…，m-1 （2）、二次探测再散列，取di=1（2），-1（2），2（2），-2（2），… （3）、伪随机探测再散列，取di=伪随机数；2、链地址法：在散列表的每一个存储单元中增加一个指针域，把产生冲突的关键字以链表结构存放在指针指向的单元中。 第十章：图及其应用 首先是图的有关概念；图是一种数据结构，图可以用二元组表示，形式化定义为：Graph（V，VR），其中V={x|x∈dataobject}，R={VR}，VR={＜x，y＞ P（x，y）∧（x，y∈V）}。顶点的度、入度和出度，以顶点V为头的弧的数目称为V的入度，以顶点V为尾的弧的数目称为V的出度，而出度与入度之和即为顶点V的度。 其次是图的存储结构；（1）、邻接矩阵：若＜vi，vj＞或者（vi，vj）∈E（G），则A[i，j]=1；反之，A[i，j]=0 （2)、邻接表：图中每个结点对应一个单链表，第i个单链表中的结点依附于顶点vi的边，每个结点由三个域组成：adjvex邻接点域指示与顶点vi相邻接的顶点在图中的位置、nextarc链域指示依附于顶点vi的下一条边或弧的结点、info信息域存储与边或弧相关的信息。 最后的图遍历和图的典型应用；对于遍历图的深度优先算法或广度优先算法、最小生成树的普利姆算法或克鲁斯卡尔算法、最短路径的迪杰特斯拉算法和弗洛伊德算法以及有向无环图拓扑排序算法，都需要根据实例走一遍算法，从而掌握这些算法。 二、学习体会 在学习这门课程之前，脑海中认为只要根据问题用编程语言解决它就好了，谈什么数据结构，有什么意义？现在看来这是多么的幼稚、荒唐的想法，同时也对这门有了全新的认识。下面是我的一点学习体会： 首先要意识到这门课程的重要性及实践性；如何合理地组织数据、高效地处理数据是扩大计算机应用领域、提高软件效率的关键。正如我参加的“ACM程序设计大赛”一样，虽然你能把那个问题解决，但是当它给你规定一定的时间时，就解决不了，而其它的人却能实现，这是为什么呢？这里面就是在算法的时间性能上存在很大的差距，你不会选择合理的数据结构、有效地组织数据，当然是无法实现的。还有这门课程的实践性很强，如果只是“听”和“读”，那根本是不可能掌握它的。例如关于排序的那几种算法，只有用实例走算法才能体会到它们之间的异同、才能掌握它。 其次我认为要理解、“吃透”有关的概念；因为所有的知识框架都建立在这些基础概念之上，没有了它，何谈掌握？当然对这些概念绝不是那种死记硬背，那是没用的。在这里，王教授的从实际中例子的学习方法，我感觉就十分的好。比如队列的“先进先出”的原则，就和现实生活中排队买票、打饭等一样吗？通过与实际相结合方法，让我们就能很轻松的理解它。 接下来是关于算法的学习；对于一个算法，在上课时听老师讲过之后，可能感觉自己已经掌握了，但当自己再去看它时又似懂非懂的说不明白。这就是很显然的没有掌握嘛！记得王教授经常说，回来以后例子走一遍，只有付出努力，才能真正掌握它。这是绝对有效的，当多走几遍后，不仅能更加深入领会算法思想，而且还能发现算法的巧妙之处，从而对其产生兴趣。 最后是关于结合实际问题进一步掌握的问题；刚开始时上实验课时，感觉真的很烦，特别每句后面都要加注释。现在看来不然，一学期的锻炼就针对加注释而言，养成了我们很好的习惯。同时在《软件工程》中也了解到，曾经爆发的软件危机，就是因为轻视注视、文档造成的。增加注视增强了程序的可读性，便于以后的维护。还有就是根据每一章所学的内容，做相应算法设计，不仅是对相应知识点的巩固，也是对自己组织数据、分析问题、解决问题等能力的锻炼。 三、教学建议 首先我想说王教授，您的结合实际理解问题、用实例走算法、叫我们做很多习题等方法，都十分的有效，上课时对知识点的解析也很透彻，当我想给您提几点建议： 第一：我认为课堂是个很神圣的地方，作为学生的我们和作为教师的您都应该尊敬她。上课时，我们应该关闭手机或者是调成振动，把注意力全都集中在知识点上。 第二：在课时允许的情况下，我想应该在课堂上给我们更多的时间练习，这可以让我们更好的消化课堂上学习的知识点。 第三：如果可以的话，我想应该把更大精力转移到实际运用上，让我们更好的懂得知识的运用。 | ||||||||||||||||||||||||||||||||
共 页 第 页
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论