数据结构学习报告

数据结构学习报告第一章：绪论1 .数据：人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。2 .数据元素：表示一个事物的一组数据。3 .数据项：构成数据元素的数据。4 .数据结构：相互之间存在一种或多种特定关系的数据元素的集合。5 .抽象数据类型：是指一个逻辑概念上的类型和这个类型上的操作集合。6 .算法性质：输入性（2）输出性 有限性 确定性（5）可执行性7 .算法满足条件:(1)正确性(2)可读性(3)健壮性(4)高时间效率 (5)高空间效率8 .算法时间效率的度量：算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗的时间来度量。方法有两种：(1)事后统计方法(2)事前分析方法9 .算法的时间复杂度：算法的时间效率是算法所处理的数据个数n的函数，算法的时间效率也称作算法的时间复杂度。|作用：判断程序是否优化总结：在第一章中主要学习到了数据结构的基本术语，抽象数据类型，算法设计的要求(主要针对时间复杂度)第二章线性表2. 1线性表的类型定义线性表：n个数据元素的有限序列，每个数据元素的具体含义可不同。稍复杂的线性表中，一个数据元素可由若干个数据项组成； 此时，数据元素称为 记录，线性表称为文件。要点：同一线性表中的元素具有相同特征。线性表的长度：表中元素的个数 n (n=0 )； n=0时为空表。2. 2线性表的顺序表示和实现线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。假设线性表的每个元素需占用l个存储单元，则第i个数据元素ai的存储位置为：LOC (ai) =LOC (al ) + (i-1 ) *l;其中LOC (al )为线性表的起始位置或基 地址。线性表的顺序表示，称做线性表的顺序存储结构或顺序映像，叫做顺序表。顺序存储结构的特点： 逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素。一元素。顺序存储结构的弱点：在做插入或删除操作时需移动大量元素。顺序存储结构插入或删除元素时移动元素个数：插入： E=n/2删除：（ n-1 ）/22 3线性表的链式表示和实现2 31 线性链表线性表的链式存储结构： 用一组任意的存储单元存储线性表的数据元素； 因此不要求逻辑关系上相邻的元素在物理位置上也相邻，但不可随机存取。数据元素 AI 的存储映像，称为结点，由存储数据元素信息的数据域和存储直接后继存储位置的指针域（指针域中存储的信息为指针或域） 。静态链表：用数组描述的链表2 3 2 循环链表循环链表： 另一种形式的链式存储结构。特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。分为：单链的循环链表和多重链的循环链表。2 3 3 双向链表双向链表：结点中有两个指针域，其一指向直接后继，另一指向直接前趋。2 4 一元多项式的表示及相加如何用顺序存储结构和链式存储结构表示一元多项式及如何相加。总结：在此章节中对线性表有了一定的认识，学习了相关线性表的类型及定义，抽象数据类型线性表相关定义，线性表的顺序存储结构，链式存储（循环链表）线性表对数据的插入以及删除第二章 栈和队列1. 栈：栈是限定仅在表尾进行插入或删除操作的线性表。栈的修改是按后进先出原则进行，因此栈又称为后进先出的线性表。2. 栈的表示和实现：I:顺序栈：栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针TOP 指示栈顶元素在顺序栈中的位置。n：链式表示：与线性操作相类似。3. 栈的应用举例：括号匹配的检验(重点)4. 栈与递归的实现(例子： Hanio 塔问题：VOID HANOI (INT N,CHAR X,CHAR Y,CHAR Z)IF(N=1 )MOVE (X, 1, Z)；ELSEHANIO(N-1, X,Z,Y);MOVE(X,N,Z) ；HANOI(N-1,Y,X,Z)5. 队列：队列是种先进先出的线性表，它只允许在表的一端进行插入，而在另端删除元素。（注：栈只在头进行操作）总结：在第三章中学习了栈并对栈的表示有了一定的了解，对链栈的存储方式也有一定的了解。HANOI问题是栈与递归的应用，此问题使我对栈有了进一步的 认识并且对递归有了一定的认识。除了栈这类存储方式我还学习到了队列这种存 储方式，明白了两种存储方式的区别。第三章 串4.1 串类型的定义用：由零个或多个字符组成的有限序列，一般记为：S= A1A2 AN （N0）用的长度：用中字符的数目N空用：零个字符的用子申：用中任意个连续的字符组成的子序列；包含子用的用相应称为主用。用的位置：字符在序列中的序号（子用在主审中的位置则以子用的第一个字符在主审中的位置来表示）空格用：由一个或多个空格组成的申称为空格申。用线性表逻辑结构相似相似基本对象单个元素用的整体用的抽象数据结构类型的定义详见 71页用的最小操作子集：用赋值，用比较，求用长，串联接以及求子用4.2 用的表示和实现4.2.1 定长顺序存储表示概念：用一组地址连续的存储单元存储用值的字符序列。在用的定长顺序存储结构中，按照定义的大小，为每个定义的用变量分配一个固定长度的存储区。申长的表示方法：1.以下标为0的数组分量存放用的实际长度。2.在用值后加一个不计入用长的结束标记字符。存储结构中用的连接：1 .用连接 CONCAT (&T, S1,S2)用T是由S1联接用S2得到，根据定长顺序存储，对超长部分施行“截断”操作，此可分为3种情况：i：用T中有完整的S1和S2ii ：用T中有完整的S1和部分的S2iii：用T中只含有完整的S12.求子用 SUBSTRING(&sub, S, pos, len )求子用的过程即为复制字符序列的过程。本操作不会有截断的情况，但有可能产生用户给出的参数不符合操作的初始条件。具体算法见第75页。4.2.2堆分配存储表示此种分配方式仍以一组地址连续的存储单元存放用值字符序列，但它们的存储空问是在程序执行过程中动态分配而得。其表示的算法在75页。4.2.3用的块链存储表示ABCDHEAD f此为结点为4的链表4.3 用的模式匹配算法4.3.1 求子用位置的定位函数 INDEX （S,T, POS）子用的定位操作通常称为用的模式匹配。（算法4.5）基本思想：从主用S的第POS个字符起和模式的第一个字符相比较，若相等, 则继续逐个比较后续字符：否则从主审的下一个字符起再重新和模式符比较之。（图示见80页）总结：在第四章中着重学习了串的相关知识。串的概念，串的存储方 式有了一定的认识。第五章数组和广义表1.数组的定义：数据对象，数据关系，基本操作2. 数组的顺序表示和实现2.1 二维数组的两种存储方式：以序列为主序和以行序为主序3. 矩阵的压缩存储3.1 压缩存储 : 为多个值相同的元只分配一个存储空间， 对零元不分配空间3.2 假若值相同的元素或者零元素在矩阵中的分布有一定的规律，则称为特殊矩阵，反之，成为稀疏矩阵。3.3 若n阶矩阵A中的元满足下述性质：a。=&，1=i,j=n,则称为n阶对称矩阵.3.4 假设在 m*n 的矩阵中，有t 个元素不为零，令s=t/(m*n), 称 s 为矩阵的稀疏因子，通常认为 s=0）个结点的有限集。n=0时为空树，n0 时：（ 1） 有 且仅有一个特定的结点，称为树的根（2）其余结点可分为mi （m0个互不相交的有限集 T1, T2,。Tm其中每一个集合本身又是一棵树，并且称 为根的子树。T1, T2,。Tm称为森林。特点：（ 2） 非 空树中至少有一个结点根，只有根的树称为最小树（ 3） 树 中各子树是互不相交的集合。2 . 结点：一个数据元素及若干指向子树的分支结点的度：结点拥有的子树树的度：树中所有结点的度的最大值叶子（终端结点） ：度为零的结点分支结点：度大于零的结点树的深度：树中结点的最大层次孩子：结点子树的根称为该结点的孩子双亲：孩子的结点的上层结点叫该结点的双亲6.2 二叉树一二叉树的特点：每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其秩序不能颠覆。满二叉树：一颗深度为k且有2 -1个结点的二叉树。6.3 遍历二叉树和线索二叉树一、遍历二叉树（ 1）遍历定义：指按某条搜索路线遍访每个结点且不重复（又称周游） 。（ 2）遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。（ 3）遍历方法：牢记一种约定，对每个结点的查看都是“先左后右”4）遍历规则二叉树由根、左子树、右子树构成，定义为D、L 、 RD、 L 、 R 的组合定义了六种可能的遍历方案：LDR, LRD, DLR, DRL, RDL, RLD若限定先左后右，则有三种实现方案：DLR LDRLRD先 （ 根）序遍历中 （ 根）序遍历后（根）序遍历二、线索二叉树（ Threaded Binary Tree ）普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来， 则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。三，线索链表：用前页结点结构所构成的二叉链表线 索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树（图形式样）线索化： 对二叉树以某种次序遍历使其变为线索二叉树的过程6.6 赫夫曼树及其应用一最优二叉树路径长度： 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度：从树根到每一个结点的路径长度之和。树的带权路径长度：为树中所有叶子结点的带权路径长度之和，WPL最小的二叉树称做最优二叉树或赫夫曼树总结：此章节学习了树型结构的相关知识。 明白了相关树型结构的概 念，并对遍历二叉树有了清楚的认识。学会了树与二叉树之间的转换。 学会了一种有着实现应用的：赫夫曼树。第七章图7.1图的定义和术语图是一种数据结构，加上一组基本操作，就构成了抽象数据类型。图分为有向图和无向图。其表示方式也不相同。有向图用来表示，如左图，无向图用(v,w)来表示，如右图。在教学中，我们用n表示图中的顶点数目，用e来表示边或弧的数 目。在讨论中，也不考虑顶点与其自身的弧或边。由此，我们可以通 过公式，来求出e的取值范围。对于无向图，e的取值范围在0到 1/2*n*(n-1)。若有1/2*n*(n-1)条边的无向图称为完全图。对于有 向图，e的取值范围为0至口 n(n-1)。若有n(n-1)条边的无向图称为 有向完全图。出度和入度：以顶点v为头的弧的数目称为v的入度，几位ID (v);以v为尾的弧的数目称为v的出度，记为OD(V),顶点v的度为TD( v) =ID(v)+OD ( v) 。连通：在无向图中，如果ongoing 顶点 v 到顶点v 有路径，则称v和v是连通的。