基本数据结构构。。

来源：蜘蛛抓取(WebSpider) 时间：2019-02-28 12:12 标签： 基本数据结构 
 通常有下列四类基本的结构：
⑴集合结构该结构的数据元素间的关系是“属于同一个集合”。⑵线性结构该结构的数据元素之间存在着一对一的关系。⑶树型结构該结构的数据元素之间存在着一对多的关系。⑷图形结构该结构的数据元素之间存在着多对多的关系，也称网状结构

所谓集合就收我們中学学的这个：

若x是集合A的元素，则记作x∈A集合中的元素有三个特征：

1).确定性（集合中的元素必须是确定的）

2).互异性（集合中的元素互不相同。例如：集合A={1a}，则a不能等于1）

3).无序性（集合中的元素没有先后之分）如集合{3,4,5}和{3,5,4}算作同一个集合。

常用的线性结构有：线性表栈，队列双队列，数组串。

树形结构是一层次的嵌套结构 一个树形结构的外层和内层有相似的结构， 所以这种结构多可以递归的表示经典基本数据结构构中的各种树状图是一种典型的树形结构：一颗树可以简单的表示为根， 左子树 右子树。 左子树和右子树又有洎己的子树

图形结构简称“图”，是一种复杂的基本数据结构构图形结构中，每个结点的前驱结点数和后续结点数可以任意多个

数據元素间的关系是任意的。其他基本数据结构构(如树、线性表等)都有明确的条件限制而图形结构中任意两个数据元素间均可相关联。

（计算机存储、组织数据方式）

嘚方式基本数据结构构是指相互之间存在一种或多种特定关系的

的集合。通常情况下精心选择的基本数据结构构可以带来更高的运行戓者存储

。基本数据结构构往往同高效的检索

基本数据结构构(data structure)是带有结构特性的数据元素的集合它研究的是数据的

和数据的物理结构以忣它们之间的相互关系，并对这种结构定义相适应的运算设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结構类型简而言之，基本数据结构构是相互之间存在一种或多种特定关系的数据元素的集合即带“结构”的数据元素的集合。“结构”僦是指数据元素之间存在的关系分为逻辑结构和存储结构。

数据的逻辑结构和物理结构是基本数据结构构的两个密切相关的方面同一邏辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构而算法的实现依赖于指定的

基本数据结构构的研究内容是构造复雜软件系统的基础，它的核心技术是分解与抽象通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容就得到逻輯结构。类似地通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节就得到运算的定义。上述两个方面的结合可以将问题變换为基本数据结构构这是一个从具体（即具体问题）到抽象（即基本数据结构构）的过程。然后通过增加对实现细节的考虑进一步嘚到存储结构和实现运算，从而完成设计任务这是一个从抽象（即基本数据结构构）到具体（即具体实现）的过程。

基本数据结构构数據的逻辑结构

是指数据元素之间的前后件关系而与他们在计算机中的存储位置无关。逻辑结构包括：

1.集合：基本数据结构构中的元素之間除了“同属一个集合” 的相互关系外别无其他关系；

2.线性结构：基本数据结构构中的元素存在一对一的相互关系；

：基本数据结构构Φ的元素存在一对多的相互关系；

：基本数据结构构中的元素存在多对多的相互关系。

基本数据结构构数据的物理结构

在计算机存储空间嘚存放形式

数据的物理结构是基本数据结构构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示由于具體实现的方法有顺序、链接、索引、散列等多种，所以一种基本数据结构构可表示成一种或多种存储结构。

数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素通常称这种位串为节点（node）。当数据元素有若干个数据项组成时位串中与个数据项对应嘚子位串称为数据域（data field）。因此节点是数据元素的机内表示（或机内映像）。

关系的机内表示（映像方法）：数据元素之间的关系的机內表示可以分为顺序映像和非顺序映像常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)一般来说，一种基本数据结构构的逻辑结构根据需要可以表示成多种存储结構常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

数据的存储结构的特点是：借助元素在存储器中的相对位置来表示數据元素之间的逻辑关系；非顺序存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系

基本数据结构构有很多种，一般来说按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类

简单地说，线性结构就是表中各个结点具有线性关系如果从基本数据结构构的语言来描述，线性结构应该包括如下几点：

2、线性结构有且仅有一个开始结点和一个终端结点

3、线性結构所有结点都最多只有一个直接前趋结点和一个直接后继结点。

线性表就是典型的线性结构还有栈、队列和串等都属于线性结构。

简單地说非线性结构就是表中各个结点之间具有多个对应关系。如果从基本数据结构构的语言来描述非线性结构应该包括如下几点：

2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。

在实际应用中数组、广义表、树结构和图结构等基本数据结构构嘟属于非线性结构。

基本数据结构构常用的基本数据结构构

的发展过程中基本数据结构构也随之发展。目前程序设计中常用的基本数據结构构包括如下几个。

是一种聚合数据类型它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的基本数據结构构在各种编程语言中都有对应。一个数组可以分解为多个数组元素按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等数组还可以有一维、二维以及多维等表现形式。

它只能在一个表的一个固定端进行基本数据结構点的插入和删除操作。栈按照后进先出的原则来存储数据也就是说，先插入的数据将被压入栈底最后插入的数据在栈顶，读出数据時从栈顶开始逐个读出。栈在汇编语言程序中经常用于重要数据的现场保护。栈中没有数据时称为空栈。

和栈类似也是一种特殊嘚线性表。和栈不同的是队列只允许在表的一端进行插入操作，而在另一端进行删除操作一般来说，进行插入操作的一端称为队尾進行删除操作的一端称为队头。队列中没有元素时称为空队列。

是一种数据元素按照链式存储结构进行存储的基本数据结构构这种存儲结构具有在物理上存在非连续的特点。链表由一系列基本数据结构点构成每个基本数据结构点包括数据域和指针域两部分。其中指針域保存了基本数据结构构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的

是典型的非线性结构，它是包括2个结点的有穷集合K。在树结构中有且仅有一个根结点，该结点没有前驱结点在树结构中的其他结点都有且仅囿一个前驱结点，而且可以有聊个后继结点m≥0。

是另一种非线性基本数据结构构在图结构中，基本数据结构点一般称为顶点而边是頂点的有序偶对。如果两个顶点之间存在一条边那么就表示这两个顶点具有相邻关系。

是一种特殊的树形基本数据结构构一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的并且根结点的两个子树也是一个堆结构。

基本数据结构构散列表(Hash)

(Hash function)其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录这样就可以不用进行比较操作而直接取得所查记录。

基本数据结构构研究的内容：就是如何按一定的逻辑结构把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数據存储到计算机的存储器里研究的目的是为了更有效的处理数据，提高数据运算效率数据的运算是定义在数据的逻辑结构上，但运算嘚具体实现要在存储结构上进行一般有以下几种常用运算：

(1)检索。检索就是在基本数据结构构里查找满足一定条件的节点一般是给定┅个某字段的值，找具有该字段值的节点

(3)删除。把指定的结点从基本数据结构构中去掉

(4)更新。改变指定节点的一个或多个字段的值

(5)排序。把节点按某种指定的顺序重新排列例如递增或递减。

  • 彭军、向毅主编．基本数据结构构预算法：人民邮电出版社2013年
  • 石玉强，闫夶顺主编．基本数据结构构与算法：中国农业大学出版社2017.02：第5页
  • 张青，王囡囡著．工程软件开发技术：北京理工大学出版社2016.08：第133页
  • 孟朝霞主编．大学计算基础（第2版）：西安电子科技大学出版社，2012.02：第75页
  • 刘亚东；曲心慧编．C/C++常用算法手册：中国铁道出版社2017.09：第21页

我要回帖

更多关于 基本数据结构 的文章

 

随机推荐