数据结构的概念及定义_数据结构的定义_黑牛儿的博客-程序员秘密

技术标签：算法数据结构与算法数据结构

一、数据结构的概念及定义

1. 定义

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。“结构”就是指数据元素之间存在的关系，一般分为逻辑结构和存储结构

1. 数据逻辑结构

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

集合：数据结构中的元素之间除了“同属一个集合”的相互关系外，别无其它关系
线性结构:数据结构中的元素存在一对一的相对关系
树形结构:数据结构中的元素存在一对多的相互关系
图形结构：数据结构中的元素存在多对多的相互关系

2. 数据物理结构

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

数据元素的机内表示(映像方式):用二进制位的位串表示数据元素。通常这种位串称之为节点（node）。所以，节点是数据元素的机内表示(或机内映像)
关系的机内表示(映像方式):数据元素的关系的机内表示可以分为顺序映像和非顺序映像,常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针来表示数据元素之间的逻辑关系

3. 数据存储结构

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

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

2. 分类

数据结构一般分为多种，一般来说，按照数据逻辑结构对齐进行简单的分类，包括线性结构和非线性结构两类。

1. 线性结构

线性结构就是表中各个数据节点具有线性关系。线性结构应该包括一下几点：

线性结构是非空集。
线性结构有且仅有一个开始和一个结束节点。
线性结构的所有节点都最多只有一个直接前驱节点和一个直接后继节点

2. 非线性结构

非线性结构就是表中各个数据节点具有多个对应关系，非线性结构应该包括一下几点：

非线性结构是非空集。
非线性结构的一个节点可能有多个直接前驱节点或多个直接后继节点。

二、常用数据结构

1. 数组（Array）

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

2. 栈（Stack）

栈是一种特殊的线性表，它只能在一个表的固定端进行插入和删除操作。栈按照先进后出或后进先出的原则来存储数据，也就是说，先进的数据将压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言中，经常用户重要数据的先出保护。栈中没有数据时称为空栈。

3. 队列(Queue)

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

4. 链表(Linked List)

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

5. 树（Tree）

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

6. 图(Graph)

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

7. 堆（Heap）

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

8. 散列表(Hash)

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

本文链接：https://blog.csdn.net/chen501986411/article/details/128207688

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

一次ORA-3136的处理_chenqunan3231的博客-程序员秘密

最近收到一个告警，用户说数据库无法连接，但是从监控上看，oracle的后台进程已经侦听进程还是在的，没有任何的alert。登录数据库，已经恢复正常，但是在数据库的alertlog中发现大量的ora-3136的报错： Thu Feb 17 09:07:31 20...

golang中xorm的基本使用_xorm incr_yí無所冇的博客-程序员秘密

简单的用法package mainimport ( _ "github.com/go-sql-driver/mysql" "github.com/go-xorm/xorm" "log")//定义结构体(xorm支持双向映射)type User struct { User_id int64 `xorm:"pk autoincr"` //指定主键并自增...

省选专练 [AHOI2012]树屋阶梯_LauJiYeoung的博客-程序员秘密

额这个是卡特兰数为啥思考选左边一块上面放一块右边放一堆这个是卡特兰数递推式然后我恬不知耻的写的pyimport mathF=[0]*501F[1]=1n=int(raw_input())for i in range(2,n+1): F[i]=F[i-1]*(4*i-2)/(i+1)print(F[n]) ...

传奇源码分析-服务器端(LoginSvr服务器分析) _gudesheng的博客-程序员秘密

LoginSvr服务器g_gcSock Local 5500端口1．首先从LoginSvr.cpp WinMain分析： 1) CheckAvailableIOCP : 检查是不是NT，2000的系统（IOCP） 2) InitInstance: 初始化界面，加载WSAStartup GetDBManager()->Init( InsertLogMsg, "M

OpenWrt下基于OLSR的Ad-Hoc组网实现网络摄像头多节点访问_lippon的博客-程序员秘密

文章目录Ad-Hoc组网配置摄像头端口映射PC连接设置Ad-Hoc组网配置参照博客https://www.cnblogs.com/smbx-ztbz/p/4478862.html?tdsourcetag=s_pctim_aiomsg摄像头端口映射PC连接设置...

电源纹波测试的正确方法_恋天的风的博客-程序员秘密

某用户在用500MHz带宽的示波器对其开关电源输出5V信号的纹波进行测试时，发现纹波和噪声的峰峰值达到了900多mV（如下图所示），而其开关电源标称的纹波的峰峰值&lt;20mv。虽然用户电路板上后级还有LDO对开关电源的这个输出再进行稳压，但用户认为测得的这个结果过大，不太可信，希望找出问题所在。问题分析电源纹波测试过大的问题通常和使用的探头以及前端的连接方式有关。首先检查了用户探头...