C|图表说数组结构 c++数组表示
yuyutoo 2024-10-12 00:46 3 浏览 0 评论
数据结构包括数据本身和结构(一个数据集合中各数据之间的关系)。数据结构的关键在于如何存储数据关系(用数据描述关系并存储)。数据关系包括一对一的线性关系,一对多的树形层次关系,多对多的图形网络关系。当然,数学上的函数也是一种关系,直接用公式的表达式来表示。
算法是一组数据上的一组操作。
数据类型显示或隐式地规定了数据的取值范围、存储方式以及允许进行的操作。如整数类型(signed int),它的集合是-32768~32767,在这个值集上能进行加、减、乘、除和取余等操作,而实数类型(float)就不能进行取余操作,这两种类型属于不可分割的原子类型,而数组、结构体、共用体属于可以分割的结构类型。
数据结构主要研究三个方面的问题:数据的逻辑结构、数据的存储结构以及定义在数据结构上的一组操作。即研究按照某种逻辑关系组织起来的一批数据,并按一定的映像方式把它们存放在计算机的存储器中,最后分析在这些数据上定义的一组操作。
主要数据结构类型:
线性表 | 顺序存储 | 数组,数组元素只是数据本身 | |
单链表 | data,*next | 数组元素是一个结构体 | |
双向链表 | *prior,data,*next | ||
二叉树 | 顺序存储 | 数组 | |
二叉链表 | *lchild,data,*rchild | ||
三叉链表 | *lchild,data,*rchild,*parent | ||
树 | 双亲存储法 | data,int parent① | |
孩子存储法 | data,*firstchild | int child,*next② | |
双亲孩子存储法 | data,int parent,*firstchild | int child,*next | |
树和森林 | 孩子兄弟存储法 | data,*firstchild,*nextsibling | |
图 | 邻接矩阵 | 用一个一维数组存储图中顶点信息 | 又称数组存储法 |
用一个二维数组(矩阵)存储顶点之间的相邻 | |||
邻接表 | vex,*firstarc | int adjvex,*nextarc,data | |
十字链表 | vex,*firstin,*firstout | int tailvex,headvex,data,*hlink,*tlink |
① 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-
相关推荐
- jQuery VS AngularJS 你更钟爱哪个?
-
在这一次的Web开发教程中,我会尽力解答有关于jQuery和AngularJS的两个非常常见的问题,即jQuery和AngularJS之间的区别是什么?也就是说jQueryVSAngularJS?...
- Jquery实时校验,指定长度的「负小数」,小数位未满末尾补0
-
在可以输入【负小数】的输入框获取到焦点时,移除千位分隔符,在输入数据时,实时校验输入内容是否正确,失去焦点后,添加千位分隔符格式化数字。同时小数位未满时末尾补0。HTML代码...
- 如何在pbootCMS前台调用自定义表单?pbootCMS自定义调用代码示例
-
要在pbootCMS前台调用自定义表单,您需要在后台创建表单并为其添加字段,然后在前台模板文件中添加相关代码,如提交按钮和表单验证代码。您还可以自定义表单数据的存储位置、添加文件上传字段、日期选择器、...
- 编程技巧:Jquery实时验证,指定长度的「负小数」
-
为了保障【负小数】的正确性,做成了通过Jquery,在用户端,实时验证指定长度的【负小数】的方法。HTML代码<inputtype="text"class="forc...
- 一篇文章带你用jquery mobile设计颜色拾取器
-
【一、项目背景】现实生活中,我们经常会遇到配色的问题,这个时候去百度一下RGB表。而RGB表只提供相对于的颜色的RGB值而没有可以验证的模块。我们可以通过jquerymobile去设计颜色的拾取器...
- 编程技巧:Jquery实时验证,指定长度的「正小数」
-
为了保障【正小数】的正确性,做成了通过Jquery,在用户端,实时验证指定长度的【正小数】的方法。HTML做成方法<inputtype="text"class="fo...
- jquery.validate检查数组全部验证
-
问题:html中有多个name[],每个参数都要进行验证是否为空,这个时候直接用required:true话,不能全部验证,只要这个数组中有一个有值就可以通过的。解决方法使用addmethod...
- Vue进阶(幺叁肆):npm查看包版本信息
-
第一种方式npmviewjqueryversions这种方式可以查看npm服务器上所有的...
- layui中使用lay-verify进行条件校验
-
一、layui的校验很简单,主要有以下步骤:1.在form表单内加上class="layui-form"2.在提交按钮上加上lay-submit3.在想要校验的标签,加上lay-...
- jQuery是什么?如何使用? jquery是什么功能组件
-
jQuery于2006年1月由JohnResig在BarCampNYC首次发布。它目前由TimmyWilson领导,并由一组开发人员维护。jQuery是一个JavaScript库,它简化了客户...
- django框架的表单form的理解和用法-9
-
表单呈现...
- jquery对上传文件的检测判断 jquery实现文件上传
-
总体思路:在前端使用jquery对上传文件做部分初步的判断,验证通过的文件利用ajaxFileUpload上传到服务器端,并将文件的存储路径保存到数据库。<asp:FileUploadI...
- Nodejs之MEAN栈开发(四)-- form验证及图片上传
-
这一节增加推荐图书的提交和删除功能,来学习node的form提交以及node的图片上传功能。开始之前需要源码同学可以先在git上fork:https://github.com/stoneniqiu/R...
- 大数据开发基础之JAVA jquery 大数据java实战
-
上一篇我们讲解了JAVAscript的基础知识、特点及基本语法以及组成及基本用途,本期就给大家带来了JAVAweb的第二个知识点jquery,大数据开发基础之JAVAjquery,这是本篇文章的主要...
- 推荐四个开源的jQuery可视化表单设计器
-
jquery开源在线表单拖拉设计器formBuilder(推荐)jQueryformBuilder是一个开源的WEB在线html表单设计器,开发人员可以通过拖拉实现一个可视化的表单。支持表单常用控件...
你 发表评论:
欢迎- 一周热门
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)