数据结构

数据结构

第一章  绪论。

数据非为整型非整型

整型为实数和整数

数据：能输入到计算机中并被计算机处理的符号总称

数据元素：若干数据项组成的一个对象，通常做一个整体处理，是数据的基本单位

数据对象：性质相同的数据元素的集合。

数据结构：带有结构的元素的集合。

结构：元素间的相互关系称为结构。

根据元素间的关系通常有四类结构：集合、线性、树、图。

逻辑结构;描叙数据间的逻辑关系为逻辑结构。

存储结构：数据在计算机中的表示称为物理结构又叫储存结构。

数据域：元素数据项的子为串。

数据在电脑中主要有两种存储方法：顺序、非顺序，分别对应顺序存储和链式存储。

算法有五个重要特性：有穷性，输入、输出、确定性、可行性、

有四个要求：可读性、健壮性、正确性、效率性。

效率性常指空间复杂度和时间复杂度。

频度：语句执行的次数为频度。

第二章  线性表

线性表：可为空的线性序列。

除头结点外，每个节点都有唯一的前驱、除尾节点外，每个节点都有唯一的后继。

存在唯一一个被称作第一个数据元素或最后一个数据元素。

链式存储结构用一组任意的存储单元表示，存储单元可以是任意也可以是连续。

指针域：节点存储后继的位置。

数据域：节点保存数据的位置。

头节点：在链表的第一个节点之前辅设一个节点，节点的数据可以不存储任何信息。

链表必须从头指针开始。

静态链表;数据容器为数组，以序号表示元素、数组内容表示双亲节点、是链式结构。

顺序表的存储密度为1.线性表的存储密度小于1

数据元素称为记录、大量记录的线性表称为文件。

多项式的单链表存储结构

第三章：栈和队列

栈和队列是操作受限的线性表。

栈：仅限于在尾部插入和删除的线性表，表头为栈底、表尾为栈顶。

队列：它允许在表得而一端进行插入、另一端删除。

循环队列

链式循环队列解决判断空的方法为;增加一个空域。队尾的下一个为头为空

第四章：串

空串;包含0个字符。

长度：串中字符的长度。

位置：串中字符所在位置的序列号。

相等:两个串字符和相应字符顺序皆相等。

顺序串超过最大空间即后面的截留。

Kmp算法

第五章：数组与广义表：

数组：

计算存储位置以序号，计算起始地址以数号。

特殊矩阵和稀疏矩阵需要压缩存储。

特殊矩阵：上下三角矩阵、三对角矩阵、对称矩阵。用数组存储，有对应公式数组以0开始计数。

稀疏矩阵用三元组存储。

稀疏因子：有数据的位置除以总位置。

矩阵还有十字链表法存储。

广义表：

广义表：分为表结点和原子节点。

表结点：指示域、头指针域、尾指针域。

原子节点1：指示域、数据域。

原子节点2： 指示域、数据域、尾指针域。

最外层

表长：最外层括号包含的元素个数

表深度：以表节点为计、原子节点不算入。（括号中以最大括号数计）

第六章：数和二叉树

树：>=0个节点的有限集。

根：每棵树有且仅有一个称为根的节点

子数：每个节点所包含的是原树的子树。

节点的度：拥有子树的数目。

叶子节点（终端节点）：度为0的节点。

孩子节点：与节点直接相连的度。

双亲节点：产生该分支的节点。

兄弟节点：双亲节点的所有度互为兄弟节点。

祖先节点：从根节点到该节点的所有节点

子孙的节点：除该节点外的所有节点。

层次：根为第一次、叶子节点为最后一层、他们之差为深度。

森林：互不相交的树的集合。

二叉树：每个节点至多有两棵树且左右孩子区分。

1.第i层至多有2i-1个节点。

2.深度为k的二叉树最多有2k-1.

3.对于任意二叉树n2+1=n0

4.有n个节点的完全二叉树二叉树深度为log2n向下取+1.

二叉树可用顺序存储（数组） 链式存储。

二叉树的遍历：先根遍历、中跟遍历、后根遍历。

线索二叉树 ：无左右孩子的情况下，左孩子指向前驱、右孩子指向后继。

线索：前驱后继指针n-1.

线索链表：储结构存储。

树换成二叉树用子兄弟表示法、

森林换成树先对每个树弟表示法、在对处理后的二叉树用孩子兄弟表示法。

树与森林转换后同序遍历得到的结果并不相同。

对一个森林 F={T1, T2,⋯,Tn} 的遍历，实际上相当于对这个森林对应的二叉树的遍历而不是每个树的遍历

哈夫曼树（最优二叉树）:

路径长度：两个节点所经历的边的个数。

树的路径长度：从根节点到每个节点的路径之和。

树的带权路径长度：所有叶子节点的带权路径长度之和。记为WPL=所有终端节点的路径长度*权值

前缀编码：任意一个编码都不是另一个编码的前缀

第七章：图

b为弧头a为弧尾。

图按密度分有稠密图和稀疏图之分。

网：带权的图

图的存储结构：十字链表、邻接表、邻接多重表、

图的遍历：广度优先搜索、深度优先搜索。

最小生成树：普里姆、克鲁斯卡尔算法

拓扑排序：偏序 到全序，邻接表存储时间复杂度为O（n+e）

关键路径：最长路径为关键路径。

最短路径：迪杰斯特拉算法  弗洛伊德算法。

弗洛伊德：解决任意两点间的最短路径的一种算法

迪杰斯特拉算法：单源最短路径算法

第九章：查找

关键字：唯一标识

折半查找：中点查找法，条件有序表。

分块查找：局部最大元素在索引中

动态查找表：删除和增加操作。

静态查找表：查询操作。

第十章内部排序

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。