admin 管理员组文章数量: 1086019
2024年4月21日发(作者：rounddown函数和round函数)
基本概念
数据
数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号
集合。
数据元素
数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据项
数据项是构成数据元素的不可分割的最小单位。
数据对象
数据对象是具有相同性质的数据元素的集合，是数据的子集。
注意：在不产生混淆的情况下，将数据对象简称为数据。
数据结构
数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = (D,
R)，其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结
构。
数据的逻辑结构
数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分
为四类：
⑴集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系；
⑵线性结构：数据元素之间存在着一对一的线性关系；
⑶树结构：数据元素之间存在着一对多的层次关系；
⑷图结构：数据元素之间存在着多对多的任意关系。
注意：数据结构分为两类：线性结构和非线性结构。
数据的存储结构
数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺
序存储结构和链接存储结构。
顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是
由元素的存储位置来表示的。
链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指
针来表示的。
注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。
抽象数据类型
抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实
现两个不同的视图，实现了封装和信息隐藏。
算法的定义
通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有
限序列。
算法的特性
⑴输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象
集合。
⑵输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的
关系。
⑶ 有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间
内完成。
⑷ 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同
的输入只能得到相同的输出。
⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
线性表的定义
线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长
度，长度等于零时称为空表。
线性表的逻辑关系
在一个非空表L＝(a
1
，a
2
，……，a
n
)中，任意一对相邻的数据元素a
i
-
1
和a
i
之间（1＜i≤n）存在序偶
关系（a
i
-
1
，a
i
），且a
i
-
1
称为a
i
的前驱，a
i
称为a
i
-
1
的后继。在这个序列中，a
1
无前驱，a
n
无后继，其它每
个元素有且仅有一个前驱和一个后继。
顺序表的存储结构定义
用MaxSize表示数组的长度，顺序表的存储结构定义如下：
#define MaxSize 100
typedef struct
{
ElemType data[MaxSize]; // ElemType表示不确定的数据类型
int length; //length表示线性表的长度
} SeqList;
顺序表是随机存取结构
设顺序表的每个元素占用c个存储单元，则第i个元素的存储地址为：
LOC(a
i
)= LOC(a
1
)＋(i－1)×c
顺序表的优缺点
顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系，这使得顺
序表具有下列优点：
⑴ 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
⑵ 可以快速地存取表中任一位置的元素（即随机存取）。
同时，顺序表也具有下列缺点：
⑴ 插入和删除操作需移动大量元素。在顺序表上做插入和删除操作，等概率情况下，平均要移动表中
一半的元素。
⑵ 表的容量难以确定。由于数组的长度必须事先确定，因此，当线性表的长度变化较大时，难以确定
合适的存储规模。
⑶ 造成存储空间的“碎片”。数组要求占用连续的存储空间，即使存储单元数超过所需的数目，如果
不连续也不能使用，造成存储空间的“碎片”现象。
单链表的存储结构定义
单链表的存储结构定义如下：
Struct Node
{ ElemType data; // ElemType表示不确定的数据类型
struct Node *next;
} *first; //first为单链表的头指针
双链表的存储结构定义
双链表存储结构定义如下：
版权声明：本文标题：数据结构基本概念归纳汇总 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1713689042a647094.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论