搜索
课程学习总结班级学号姓名考核成绩一、学习内容总结（按章节进行）第一章：数据结构和算法本章主要是对数据、数据类型、数据结构、算法及算法分析等基本概念的掌握，而如何合理地组织数据、高效地处理数据正是扩大计算机领域、提高软件效率的关键，所以对这些概念的理解就显得十分重要。数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称，其基本单位是数据元素，而数据类型是一个同类值的集合和定义在这个值集上的一组操作的总称。在高级程序语言中定义一种数据类型时，编译程序编译系统就能获得如下信息：（1）、一组性质相同的值的集合；（2）、一个预订的存储体系；（3）、定义在这个值集合上的一组集合。数据结构是指数据元素之间的关系，它包括数据的逻辑结构、存储结构、一组运算集合；数据的逻辑结构（即数据结构）分为线性结构和非线性结构，数据的存储方法有：顺序存储方法、连接存储方法、索引存储方法和散列存储方法。接下来便是关于算法的有关概念，算法是为解决一个特定问题而采取的确定的有限步骤集合，它具有有穷性、确定性、可行性、输入和输出。关于算法的性能分析，分为时间性能分析和空间性能分析，在这里要记得常见的时间复杂度的比较：O（1）O（log2n）O（n）O（nlog2n）（n2）O（n3）O（nk）O（2n）。第二章：顺序表及其应用顺序表作为一种简单而又常用的数据结构，应用范围较为广泛，本章主要是对顺序表、顺序表的结构、数据类型、基本算法及相关应用的介绍。首先顺序表是一种简单而常用的数据结构，其应用范围较为广泛，它的基本运算包括初始化表、求表长、查找表中元素及删除元素等。在这其中，进行插入和删除操作时需要大量移动元素，算法的时间复杂度为O（n）。其次是关于查找运算，主要有简单顺序查找、二分查找及分块查找等查找方法。其中以分块查找的效率最优，但必须在有序表中完成查找运算。接下来是关于排序的算法，通常排序的方法有直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序，它们的算法时间复杂度如下：排序方法平均时间复杂度最坏时间复杂度辅助存储空间直接插入排序O（n2）O（n2）O（1）希尔排序O（n2/3）O（n2/3）O（1）冒泡排序O（n2）O（n2）O（1）快速排序O（nlog2n）O（n2）O（nlog2n）…………………………装………………………………订………………………………线………………………………直接选择排序O（n2）O（n2）O（1）归并排序O（nlog2n）O（nlog2n）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（aij）=Loc（a00）+[j*（m+1）+i]*d（2）、以列序为主存储，Loc（aij）=Loc（a00）+[i*（n+1）+j]*d，其中m为行数、n为列数、d为每个元素所占的存储单元的个数。2、对称矩阵：即将下三角存储在一个一维数组sa[k]中，其中0≤k(n+1)/2；当i≥j时，k=i*（i+1）/2+j，当ij时，k=j*（j+1）/2+i3、三角矩阵：和对称矩阵的存储思路一样用一维数组sa[k]存储，若是上三角矩阵（下三角中元素均为常数c），则当i≥j时，k=i*（i+1）/2+j，当ij时，k=n*（n+1）/2；若是下三角矩阵（上三角中元素均为常数c），则当i≤j时，k=i*（2n-i+1）/2+j-i，当ij时，k=n*（n+1）/24、对角矩阵：同样存储在一维数组sa[k]中，k=2i+j5、稀疏矩阵：即矩阵中非零元素个数远远小于矩阵元素个数，可用三元组表存储，将非零元素的值与其行号、列号存放在一起。其次是关于广义表的概念；广义表是n（n≥0）个元素a1、a2、a3、…、an的有限序列，而ai或是原子或是一个广义表，所以广义表是递归定义。第七章：二叉树及其应用首先关于二叉树的概念及其性质；二叉树是由n（n≥0）个结点组成的有限集合，其中：（1）、当n=0时，为空树（2）、当n0时，有且仅有一个特定的结点，成为二叉树的根。在这其中有两种特殊的二叉树，满二叉树和完全二叉树。满二叉树是满足如下条件的二叉树：（1）、任一非叶子结点均有两个孩子（2）、对于二叉树的任一层，若该层上有一个结点有孩子，则该层上所有结点均有孩子；而完全二叉树是在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。同时二叉树具有如下五个性质：（1）、在二叉树的第i层上至多有2（i-1）个结点（i0）（2）、深度为k的二叉树至多有2（k）-1个结点（k0）（3）、对任意一棵非空二叉树，若果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1（4）、有n个结点的完全二叉树（n0）的高度为∟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）=keymodp，其中p=m，m为散列表长度（3）、数字分析法：分析关键字集合中每个关键字中每一位数码的分布情况，找出数码分布均匀的若干位作为关键字的存储地址（4）、平方取中法：将关键字求平方后，取其中间的几位数字作为散列地址（5）、折叠法：将关键字分隔成位数相等的几部分，取这几部分的相加之和作为关键字的散列地址。其次是冲突处理；由于散列函数很可能将不同的关键字计算出相同的散列地址，所以就需要为发生冲突的关键字结点找到一个“空”的散列地址。冲突处理的方法有1、开放定址法：Hi=（H（key）+di）modm，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)、邻接表：图中每个结点对应一个单链表，第