- 1、本文档共90页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[工学]07-计算机软件系统-算法与数据结构
数据结构 数据结构 数据处理,是指对数据集合中的各元素以各种方式进行操作,包括插入、删除、查找、更改等,也包括对数据元素进行分析。 数据的组织方式不同,通常对它进行处理时的效率也不同。如:对两个存放相同元素的表进行查找时,一个表中的所有数据元素是没有规律的,而另外一个表中的元素是经过排序的,则对于前者用顺序查询法进行查找,后者采用折半查询法进行查询,可见后者效率较高。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。 数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象成数据元素。数据元素一般简称为元素。作为某种处理,其中的数据元素一般具有某种共同特征。 1.数据的逻辑结构 所谓数据的逻辑结构,是指描述数据元素之间逻辑关系的数据结构。数据的逻辑结构由某一数据对象及该对象中所有数据成员之间的关系(前后件关系)组成。即一个数据结构可以表示成: Data_Structure =(D,R) D是数据元素的集合, R是D上的关系,它反映了D中各数据元素之间的前后件关系。 例如: 设a、b、c 是D中的数据,则 D={a,b,c} R={(a, b),(b,c) } 表示a是b的前件,b是a的后件。 例如:一年四季的数据逻辑结构可以表示为: B = (D, R) D ={春,夏,秋,冬} R ={(春,夏),(夏,秋),(秋, 冬)} 2.数据的物理结构 数据的物理结构:数据的逻辑结构在计算机中的存储方式称为数据的物理结构。它包括数据元素的存储方式和关系的存储方式。 一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构,其数据处理的效率是不同的 。 5.1.4 线性结构与非线性结构 空的数据结构:如果在一个数据结构中一个数据元素都没有,则称该数据结构为空的数据结构。 在一个空的数据结构中插入一个新的元素后就变为非空的数据结构。 根据数据元素之间关系的不同特性,一般将数据结构分为两大类型:线性结构与非线性结构。 线性结构 : 如果一个非空的数据结构满足下列两个条件: (1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。 如一年四季这个数据结构就属于线性结构,如图所示。 在一个线性结构中插入或删除任何一个结点后还应是线性结构。 非线性结构: 如果一个数据结构不是线性结构,则称之为非线性结构。如家庭成员间辈分关系的数据结构就属于非线性结构,如图所示。 显然,在非线性结构中,各数据元素之间的前后件关系要比线性结构复杂,因此,对非线性结构的存储与处理比线性结构要复杂得多。 5.2 线性表与线性链表 5.2.1 线性表 1.线性表的基本概念 线性表是最简单且最常用的一种数据结构。一个线性表是n个数据元素的有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。 线性表或是一个空表,或可以表示为(a1,a2, …,ai, …,an),其中ai (i=1,2, …,n)是属于数据对象的元素,通常也称其为线性表中的一个结点。 如26个英文字母的字母表(A, B, C, …, Z)是一个长度为26的线性表,其中的数据元素是单个字母字符。 在稍微复杂的线性表中,一个数据元素还可以由若干个数据项组成。例如,某班的学生情况登记表是一个复杂的线性表,表中每一个学生的情况就组成了线性表中的每一个元素,每一个数据元素包括姓名、学号、性别、年龄和健康状况5个数据项,如表所示。 2. 线性表的顺序存储结构 线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个基本特点: (1)线性表中所有元素所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 在线性表的顺序存储结构中,如果线性表中各数据元素所占的存储空间(字节数)相等,则要在该线性表中查找某一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为LOC(b1),每一个数据元素占m个字节,则线性表中第i个元素bi在计算机存储空间中的存储地址为: LOC (bi) = LOC (b1) + (i-1)m 在计算机中的顺序存储结构如图所示。 3. 顺序表的插入操作 在一般情况下,要在第i(1≤i≤n)个元素之前插入一个新元素时,首先要从最后一个(即第n个)元素开始,直到第i个元素之间共n – i + 1元素依次向后移动一个位置,移动结束后,第i个位置就被空出,然后将新元素插
文档评论(0)