数据结构总结

一、绪论。

1、数据结构：数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示和实现”的学科。具有相同特征的数据元素的集合，如果在这些数据元素之间存在一种或多种特定的关系，则称为一种数据结构。

2、建立模型：

3、数据：客观对象的符号表示；

数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑和处理，通常具有完整确定的实际意义。（节点、顶点、记录）

数据项：数据不可分割的最小标识单位。一个数据元素可由若干数据项组成，通常不具有完整确定的实际意义。

4、数据的逻辑结构：数据之间的逻辑关系，是抽象的数学模型。

5、数据元素之间存在四种基本结构：

集合（无关系），线性结构（一对一）：除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，如表、栈。

树形结构（一对多）：每一个元素只有一个直接前趋，有0个或多个直接后继。如树。

图状结构（多对多）：每一个元素可以有0个或多个直接前趋，有0个或多个直接后继。如图。

7、数据的存储结构：顺序存储结构，链式存储结构，散列结构和索引结构。

8、一个算法必须满足以下五个重要特性：有穷性、确定性、可行性、有输入和有输出。

9、评价算法的标准：正确性，可读性，可维护性，健壮性，效率。

10、算法效率的度量：计算复杂度、渐进复杂度。

11、老师的课后题：

数据结构定义：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

数据结构：数据元素和数据元素关系的集合。

数据的逻辑结构：只抽象反映数据元素的逻辑关系。

数据的存储（物理）结构：数据的逻辑结构在计算机存储器中的实现。

存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。

链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。

数据的逻辑结构与存储结构密切相关：算法设计 → 逻辑结构；算法实现 → 存储结构。

数据的运算：检索、排序、插入、删除、修改等

第二章、线性表的基本概念。

1、线性表特点：在数据元素的非空有限集中。

存在唯一的一个被称作“第一个”的数据元素。

存在唯一的一个被称作“最后一个”的数据元素。

除第一个外，集合中的每个数据元素均只有一个前驱。

除最后一个外，集合中的每个数据元素均只有一个后继。

2、线性表的元素。

1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；

2）在表中 ai-1 领先于 ai ，ai 领先于 ai+1，称 ai-1 是 ai 的直接前趋， ai+1 是ai 的直接后继；

3）**性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。线性表是一种线性数据结构；

4）元素的个数 n 称为表的长度，n=0时称为空表；

5） ai 是表的第 i 个元素，称 i 为数据元素 ai 的序号，每个元素**性表中的位置，仅取决于它的序号。

6）可在表的任意位置进行插入和删除操作。

3、顺序表的特点：用连续的存储单元存放线性表的元素，元素存储顺序与元素的逻辑顺序一致。

4、线性表的链式存储结构特点：

1）用一组任意的存储单元存储线性表的数据元素。

2）利用指针实现了用不相邻的存储单元存放逻辑上相邻的一组元素。

3）每个数据元素 ai ，除存储本身信息外，还需存储其直接后继的信息（指针）。

5、结点。数据域：数据元素本身的信息

指针域：指示直接后继的存储位置

6、几个概念：

头指针：存放线性链表中第一个结点的存储地址；

空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针；

头结点：线性链表的第一数据元素结点前面的一个附加结点，称为头结点。头结点不保存数据。

带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；

6、链表中没有数据结点称为：空表。

7、结点的形式定义：

typedef struct lnode lnode，* linklist；

linklist l；

/ l 为单链表的头指针，是 linklist 类型的变量。

8、单链表操作的特点：单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。因此，查找第 i 个数据元素的基本操作为：

移动指针，比较 j 和 i 。

9、静态链表：用数组实现的链式结构，称为静态链表。

10、线性链表的特点：

1. 用一组任意的存储单元存储线性表中数据元素；

2. 通过指针保存直接后继元素的存储地址来表示数据元素之间的逻辑关系；

3. 通过头指针（或首结点）给出线性链表；

4. 链表中结点空间是动态分配的；

5. 插入、删除操作通过修改结点的指针实现；

6. 只能顺序存取元素，不能直接存取元素。

11、循环链表（带有头结点的单向环表）

最后一个结点的指针域的指针又指回第一个结点（头结点）的链表。判断为是否空表的条件：h->next ==h

12、循环链表的特点：

1. 从一个结点可找到链表中的任意一个结点；

2. 判断是否为表尾结点的条件：p->next ==l。

3. 有时，用表尾指针表示循环链表。

第三章栈。1、栈是限定仅能在表尾一端进行插入、删除操作的线性表。表尾端称为栈顶，表头端称为栈底。

2、能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。

3、第一个进栈的元素在栈底；最后一个进栈的元素在栈顶；第一个出栈的元素为栈顶元素；

最后一个出栈的元素为栈底元素。栈的特点：后进先出。

4、空栈 top = base ；栈满 top-base = stacksize (无可分配空间)

7、栈的链式存储结构，也称链栈。

8、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针

9、队列是限定仅能在表头进行删除，表尾进行插入的线性表。

10、能进行插入的一端称为队尾，能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。

11、第一个入队的元素在队头；最后一个入队的元素在队尾；第一个出队的元素为队头元素；

最后一个出队的元素为队尾元素，队列的特点：先进先出。

13、存在问题：

设数组大小为m，则：当front=0，rear= m 时，再入队发生溢出——真溢出，当front0，rear= m 时，再入队发生溢出——假溢出。

14、队列的应用：

1）解决计算机主机与外设不匹配的问题；

2）解决由于多用户引起的资源竞争问题；

3）离散事件的模拟——模拟实际应用中的各种排队现象；

4）用于处理程序中具有先进先出特征的过程。

第五章数组和广义表。

1、数量固定，数据类型相同的（变量）元素组合在一起。使用一个名称代表它。这个名称就是数组名。

如果要访问其中某个元素(变量)，可以使用元素的索引值(下标)来访问它。在c语言中，数组元素的索引值从0开始。

2、二维数组是数据元素为线性表的线性表。

3、数组的逻辑结构：二维数组中的每个元素都受两个线性关系的约束——行关系、列关系。

4、数组的基本操作：1）读：给定一组下标，读出对应的数组元素；2）写：

给定一组下标，存储或修改与其相对应的数组元素。读/写操作本质上只对应一种操作——寻址。确定指定元素在内存中的物理地址。

5、数组的存储：两种形式，既可以是顺序存储，也可以采用链式结构。

6、数组的存储结构与寻址——一维数组。

设具有m个元素的一维数组的下标范围为闭区间 [0, m-1]，每个数组元素占用 l 个存储单元。 ai 的存储地址： loc( ai )＝loc(a0)＋i×l

7、数组的存储结构与寻址——二维数组

常用的映射方法有两种：

按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。

按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。

8、值相同元素或者非零元素的分布有一定规律的矩阵，称为特殊矩阵。（对称矩阵、上（下）三角矩阵。）

9、含有较多值相同或较多零元素，且值相同或者零元素分布没有一定规律的矩阵称为稀疏矩阵。

10、稀疏矩阵采用三元组存储：(行，列，值)

11、广义表是一种不同构的线性结构，12、广义表的基本性质。

1. 广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；

2. **性表中数据元素是单个元素，而在广义表中，元素可以是单个元素称为原子(atom)，也可以是广义表，称为广义表的子表(sublist)；

3. 当每个元素均为原子且类型相同时，就是线性表。

13、广义表的术语。

表头：ls的第一个元素称为表头

表尾：其余元素组成的表称为ls的表尾。

表长：为最外层包含元素个数。

深度：所含括弧的重数。原子的深度为 0，“空表”的深度为 1

例： a空表表长：0；深度：1

b = b, c, d表长：3，深度：1

c = a, b ) a, (b,c,d表长：2，深度：2

d = a, b, cb,c,d), a,(b,c,d表长：3，深度：3

14任何一个非空广义表 ls = 1, 2, …n) 均可分解为：表头head(ls) =1和表尾tail(ls) =2, …n ) 两部分。

例如：d = e, fa, (b, c ) f ) head( d ) e，tail( d ) f)；head( e ) a tail( e ) b，c))；head( (b, c)) b， c)，tail( (b, chead( (b, c) )b, tail( (b, c) )c) ；head( (c ) c tail( (c )

数据结构总结

数据结构总结

数据结构总结

数据结构总结

其他用户还读了