数据结构教程

1、概要模块1 :线性表模块2 :树结构模块3 :地图结构模块4 :其他1 .数据结构的定义、数据要素数据项目、数据结构指的是与数据的相互关系(或关系)。 (1)包括数据的逻辑结构。 (2)数据的存储结构(物理结构)。 (3)与该数据相关的运算。 概要、数据的逻辑结构从逻辑关系中记述数据，与数据的存储无关，与计算机独立。 数据的容纳结构是逻辑结构用计算机语言的实现(也称为对象)，依赖于计算机语言。 数据的运算被定义在数据的逻辑结构中，每个逻辑结构都有对应的一组运算。 但是，运算的实现与数据的存储结构有关。 程序数据结构算法、概要、(1)线性结构(2)树结构(3)图形结构、概要、逻辑结构主要分为三类

2、： (1)顺序存储方法(2)链接存储方法(3)索引存储方法、概要，2 摘要，算法的五个重要特性： (1)有贫困性；(2)有确定性；(3)有可行性；(4)有输入；(5)有输出；概况；算法的时间复杂性：其基本运算在算法中反复执行的次数。 算法中的基本运算次数T(n )是具有问题规模n的函数f(n )，标记为T(n)=O(f(n ) )的符号“o”读出为“大o”，表示伴随问题规模n的增大的算法执行时间的增加率和f(n )的增加率相同。 概要，示例分析了以下段的时间复杂性： i=1； while (i=n) i=i*2； 解：在上述算法中，基本的操作是语句i=i*2，设其频度为T(n )，则T(n)l

3、og2n=O(log2n )。 因此，该段的时间复杂度为O(log2n )。 算法空间的复杂性：测量一个算法在运行时暂时消耗的存储空间的大小。 空间复杂度为O(1)的算法被称为当场工作或当场工作的算法。 概要、递归定义、3 .算法设计方法：在定义递归、算法时出现了调用本算法的要素，称为递归。 概要、递归模型、递归输出和递归体构成，例如，对二叉树的所有节点数： f (b )=0b=null ff (b )=f (B- lchild ) f (B- rcild ) 1b null、概要、递归算法设计、元问题f(s )进行分析，并进行合理的“。 即，通过确定赋予f(s )和f(s )关系的特定状况(

4、例如f(1)和f(0) )的解，递归输出.概要、b、b-rchild， 假设合理的“小问题”作为b-lchild :假设左右子树的节点数，可以求出f(s )和f(s )的关系：确定f(b)=f(b-lchild) f(b-rchild) 1递归出口： f(NULL)=0 如果求解算法：概述，例子设计要求f(n)=1.n的递归算法解： f(n )是前n项的和，则求f(n-1)=1(n-1)f(n-1 ) 当n=1 f(n)=f(n-1) n时，对应于n-1的递归算法如下： else返回(f (n-1 ) n )； 1 .一般线性表线性表：具有相同特性的数据元素的有限阵列。 不是集合。 要素之间是

5、一对一的关系。 模块1 :线性结构、逻辑结构、(1)顺序表、typedefstructelemtypeelemmaxsize； /*存储顺序表要素*/int length的/*存储顺序表的长度*/SqList，存储结构之一，模块1 :线性结构，顺序表基本运算的实现，插入数据要素算法：要素移动的次数不仅仅是在插入表长度n时移动要素的平均次数n2。 平均时间复杂度是O(n )。 模块1 :线性结构，删除数据元素的算法：元素的移动次数也与表长度n有关。 删除元素时移动的元素的平均次数为(n-1)/2。 删除算法的平均时间复杂度是O(n )。模块1 :线性结构；(struct LNode *next，

6、用于定义链表和单链表的节点类型： typedefstructlnodeelemtypedata； /*到下一个节点*/LinkList；存储结构的第二部分，模块struct DNode *prior，用于定义线性结构和双链表节点类型： typedefstructdnodeelemtypedata； /*前驱节点*/struct DNode *next； /*指后续节点*/DLinkList，模块1 :线性结构，单链表基本运算的实现，重点： (1)插件表和插件表的算法，它是许多算法设计的基础；(2)检索、插入、删除操作。 模块1 :使用线性结构、插件方法创建表的方法是，从空表中读取字符数组a的字

7、符，生成新节点，将读取的数据存储在新节点的数据字段中，将新节点插入当前链表的报头中，直到最后。 使用插件法创建表的算法为：模块1 :线性结构，voidpristf(linklist* )，模块1 :线性结构，插件法创建表的方法很简单，但生成的链表的节点顺序与原始的数组元素的顺序相反。 在想使两者的顺序一致的情况下，可以使用尾插法制作。 这种方法将新节点插入到当前链表的末尾，因此必须始终添加末尾指针r以指向当前链表的末尾节点。 使用尾插法制作表的算法为：模块1 :线性结构，void CreateListR(LinkList */*结束节点next域为NULL*/，双重链表的基本运算的实现，重点：

8、插入删除节点的算法。 模块1 :线性结构，实现循环链表的基本运算，重点：判断最后的节点。 模块1 :线性结构，该示例设计了一种算法LocateElem(L，e )，用于在单链表中查找元素值e的节点号。 想法：在链接列表l中查找e等于倒数第一值区域的节点，如果存在这种节点，则返回到位置，否则返回到0。 链接列表* l，电子链接列表* p=l-next； PS=1； while (p！=NULL，2 .堆栈(1)堆栈的定义堆栈是先进的后表格。 插入删除受到限制的线性表。 堆栈的基本运算：进入堆栈，离开堆栈。 逻辑结构，模块1 :线性结构，(2)序列堆栈，typedefstructelemtypee

9、lemmaxsize； int top； /*堆栈指针*/SqStack； 存储结构之一，模块1 :线性结构，堆栈空间条件：s.top=-1堆栈完全条件：s.top=MaxSize-1堆栈：top； s.datas.top=e； 堆栈：e=s.datas.top； s.top，顺序堆栈4个元素：模块1 :线性结构，(3)链堆栈，typedefstructlinknodeelemtypedata； /*数据域*/struct linknode *next； /*指针域*/Li堆栈； 存储结构2、模块1 :线性结构、用开头节点的链表实现(也可以不是开头节点)、堆栈空条件：s-next=NULL堆栈

10、满足条件： 模块1 :线性结构，3 .队列，(1)队列定义队列是先进的先进先出表。 插入删除受到限制的线性表。矩阵的基本运算：加入矩阵，出矩阵，逻辑结构，模块1 :线性结构，(2)顺序矩阵，typedefstructelemtypeelemmaxsize； int front，rear； /*团队开头和末尾的指针*/SqQueue； 存储结构之一，模块1 :线性结构，队列空：q.front=q.rear队是： (q.rear1) % maxsize=q.front前进队：q.rear=(q.rear 1)MaxSize； q.dataq.rear=e； 出场：q.front=(q.front

11、1)MaxSize； e=q.dataq.front； 环矩阵的4个元素：模块1 :线性结构，(3)链，结构qnode/*数据节点*/elemtype数据； 结构qnode * next； QNode； 类型结构/*头节点*/qnode *前端； QNode *rear； 李队列； 记忆结构的2，模块1 :线性结构，(2)序列，(3)序列，(4)序列的模式匹配算法(不要求)，4 .序列(1)序列的定义列，部分序列，字符串相等，空列，空间序列，模块1 :线性结构，5 .序列和稀疏矩阵(1) 模块1 :线性结构，(2)阵列的存储结构行顺序主要是： LOC(ai，j)=LOC(ac1，c2) (i-

12、c1)*(d2-c2 1) (j-c2)*k，列顺序主要是LOC(ai，j)=LOC(ac1，C2 ) (j-C2 ) * (D1 - 以c2.d2为例，模块1 :线性结构(3)特殊矩阵的压缩存储称为n阶对称矩阵，其中当对称矩阵满足一个n阶正方阵Ann中的元素ai，j=aj，i(0i，jn-1 )时，该对称矩阵称为n阶对称矩阵。 A0.n-10.n-1 B0.n(n 1)/2、模块1 :线性结构、三角矩阵、采用类似的压缩方法，模块1 :线性结构、(4)疏散矩阵、存储结构：三元组表示交叉链接表示各种表示的基本构想。 的双曲馀弦值。 模块1 :线性结构，一个广义表中包含的元素的数量为其长度，6 .

13、广义表，GL=(a )、(a )、(b、c、d )、()的长度为4。 模块1 :线性结构，在一个广义表中嵌套括号的最大次数为其深度，GL=(a )、(a、b、c、d )、()深度为2。 模块1 :线性结构，表的第一个元素a1是广义表GL的页眉，其馀部分(a2，ai，ai 1，an )是GL的页脚，GL=(a )、(a，b，c，d )、() 标头是a，页脚是(a )、(b，c，d )、() ，模块树的定义递归定义适合于表示层次结构的数据，1 .树，(2)树的表现法(逻辑表现方法)，树的表现法文氏图表现法凹表法括号表现法，模块2 :树结构，(3)树的扫描，先扫描算法后扫描算法，模块2 :树结构，(

14、4)与树平分树二叉树二叉树模块2 :树结构，2 .二叉树，(1)二叉树的定义根，左子树，右子树的完全二叉树，满二叉树的定义，模块2 :树结构，性质1非空二叉树的上叶节点数在二分支节点数上加1。 即n0=n2 1 .性质2非空二叉树上的第I层最多有2i-1个节点(i1 )。 (2)二叉树的性质，模块2 :树结构，性质为3的高度为h的二叉树最多有2h-1个节点(h1 )。 性质4完全二叉树的性质。 具有性质5n个(n0 )节点的完全二叉树的高度为log2n 1或log2n 1。 (2)二叉树的性质，模块2 :树结构，从根层开始具有一根98个节点的完全二叉树，按各层从左到右的顺序对节点编号，将根节点

15、的编号设为1，编号49的节点右侧的孩子的编号为。 A.98 B.99 C.50 D .不存在，a:d，模块2 :树结构，示例深度为5的二叉树最多有节点。 A.16 B.32 C.31 D.10，a :在相同满意度下满二叉树的节点最多，h=5的满二叉树的节点数=25-1=31。 c模块2 :树结构：(3)二叉树的记忆结构，二叉树的顺序记忆结构，模块2 :树结构，a，b，c，d，e，f，I，2i，2i 1，左孩子，右孩子，二叉链记忆结构typedef struct node ElemType data； /*数据元素*/struct node *lchild； /*左边的孩子*/struct no

16、de *rchild； /*右边的孩子*/BTNode； (4)二叉树的循环，按第一循环的顺序之后的循环，模块2 :树结构，例如二叉树使用二叉链的存储结构进行存储，设计一个算法，输出一个给定二叉树的所有叶的节点。 解：输出一棵树的所有叶节点的递归模型f ()如下： f(b ) :什么都不做时b=NULL f(b ) :输出*b节点的data字段时*b是叶节点f(b):f(b-lchild )； 在f(b-rchild )其他情况下，模块2 :树结构，void DispLeaf(BTNode *b) if (b！=NULL) if (b-lchild=NULL，模块2 :树结构，首先扫描思想，2 .霍夫曼树，(1)霍夫曼树的定义，WPL最小，没有单枝节点的n1=0，模块2 :树结构，(2)霍夫曼树的结构过程，(3)霍夫曼树的结构过程顶点的度、入度和出度完全掌握了子图路径和路径长度连通，连通图和连通成分强连通图和强连通成分权和网，模块3 :图结构，(1)图的基本概念，(2)图的存储结构，邻接矩阵存储方法，两种存储方法的优点和缺点，实现在相同功能不同的存储结构上的算法。 邻接表的存储方法、模块3 :图形结构、(3)图的扫