C|图表说数组结构 c++数组表示

数据结构包括数据本身和结构（一个数据集合中各数据之间的关系）。数据结构的关键在于如何存储数据关系（用数据描述关系并存储）。数据关系包括一对一的线性关系，一对多的树形层次关系，多对多的图形网络关系。当然，数学上的函数也是一种关系，直接用公式的表达式来表示。

算法是一组数据上的一组操作。

数据类型显示或隐式地规定了数据的取值范围、存储方式以及允许进行的操作。如整数类型（signed int），它的集合是-32768~32767，在这个值集上能进行加、减、乘、除和取余等操作，而实数类型（float）就不能进行取余操作，这两种类型属于不可分割的原子类型，而数组、结构体、共用体属于可以分割的结构类型。

数据结构主要研究三个方面的问题：数据的逻辑结构、数据的存储结构以及定义在数据结构上的一组操作。即研究按照某种逻辑关系组织起来的一批数据，并按一定的映像方式把它们存放在计算机的存储器中，最后分析在这些数据上定义的一组操作。

主要数据结构类型：

① int parent用一个整数存放该节点的父节点的位置；

② int child为节点在表头数组中的下标；

③ 以上指针都是指向自身的结构体或另外的结构体；

④ 顺序存储：即用一组连续的内存单元依次存放线性表中的数据元素（元素在内存的物理存储次序与它们在线性表中的逻辑次序相同）。在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。

⑤ 链式存储，即用指针将存储线性表中数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。

单链表

双向链表

二叉链表、三叉链表

双亲存储法

设T 是一棵树，表示 T 的一种最简单的方法是用一个一维数组存储每个结点，数组的下标就是结点的位置指针，每个结点中有一个指向各自的父亲结点的数组下标的域。由于树中每个结点的父亲是唯一的，所以上述的父亲数组表示法可以唯一地表示任何一棵树。下图说明了这种存储结构。

孩子存储法

用一个线性表来存储树的所有结点信息，称为结点表。对每个结点建立一个孩子表。孩子表中只存储孩子结点的地址信息，可以是指针，数组下标甚至内存地址。由于每个结点的孩子数目不定，因此孩子表常用单链表来实现，因此这种表示法称为孩子链表表示法。

双亲孩子存储法

将双亲存储法和孩子链表存储法相结合：

孩子兄弟存储法

树的孩子兄弟表示法又称为二叉树表示法。每个结点除了data 域外，还含有两个域，分别指向该结点的第一个孩子和右邻兄弟。

邻接矩阵

图没有顺序映像的存储结构，但可以借助数组来表示数据元素之间的关系。

邻接表

邻接矩阵的空间效率之所以低，是因为其中大量的单元所对应的边有可能并未在图中出现，这是静态数组结构不可避免的问题。既然如此，则可以将静态的存储结构改为动态的链式存储结构。按照这一思路可以得到图的另一种表示形式，它其实是对邻接矩阵法的一种改进，即邻接表。

十字链表

是有向图的另一种链式结构。将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。

十字链表存稀疏矩阵的基本思想是：将每个非零存储为一个节点，节点由5个域组成：

栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说，它们也是线性结构，与线性表不同的是它们所支持的基本操作是受到限制的，它们是操作受限的线性表，是一种限定性的数据结构。

队列（queue）简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾（rear），删除数据元素的一端称为队首（front）。向队尾插入元素称为进队或入队，新元素入队后成为新的队尾元素；从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队首元素。由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队，也就是说先进队的元素必然先离队，所以称队列为先进先出表（First In First Out,简称FIFO）。队列结构与日常生活中排队等候服务的模型是一致的，最早进入队列的人，最早得到服务并从队首离开；最后到来的人只能排在队列的最后，最后得到服务并最后离开。

栈（stack）又称堆栈，它是运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为栈顶（top），栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈（bottom）当栈中没有数据元素时称为空栈；向一个栈插入元素又称为进栈或入栈；从一个栈中删除元素又称为出栈或退栈。由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈称为后进先出表（LastIn First Out，简称LIFO）。

堆（heap）结构是一种数组对象，它可以被视为一棵完全二叉树。

广义表（(Lists）是线性表的推广,广义表中元素既可以是原子类型,也可以是列表;当每个元素都为原子且类型相同时,就是线性表?广义表一般记为LS=(a1,a2,…,an),其中LS是广义表(a1,a2,…,an)的名称,n是它的长度?在线性表中ai只限于单个元素,而在广义表的定义中,ai可以是单个元素,也可以是广义表,分别称为广义表LS的原子和子表?

数组（array）是有序的元素序列。 若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按无序的形式组织起来的一种形式。 这些无序排列的同类数据元素的集合称为数组。

串（string）是字符串的简称，是零个或多个字符组成的有限序列。是一种特殊的线性表，要求组成线性表的所有数据元素都是字符。字符数组是指用来存放字符数据的数组。其定义的一般形式为： char 数组名[数据长度] 。字符数组用于存放字符或字符串，字符数组中的一个元素存放一个字符，它在内存中占用一个字节。C语言中没有字符串类型，字符串是存放在字符型数组中的。串也可采用链式方式存储串值。

矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合 ，最早来自于方程组的系数及常数所构成的方阵。通常用二维数组来存储矩阵元素

参考：

树的双亲表示法 树的存储结构：https://www.server110.com/jiaocheng/201703/2071832.html

数据结构---->树：http://www.cnblogs.com/xiaoqiangzhaitai/archive/2012/11/25/5637458.html

数据结构---->图的存储结构：http://www.cnblogs.com/xiaoqiangzhaitai/archive/2012/12/27/5429414.html

稀疏矩阵的十字链表存储：http://www.cnblogs.com/zhuyf87/archive/2012/10/22/2733628.html

数据结构之树和二叉树：https://www.2cto.com/kf/201709/679291.html

－End－