数据结构的基本概念
10页1、数据结构的基本概念数据结构是讨论计算机系统中数据的组织形式及其相互关系的一门学科,它是计算机专业的重要基础课,也是其他从事计算机软件开发工作的人需要掌握的必备知识。1、 数据结构的主要内容数据结构实际上就是研究:(1) 数据元素间的逻辑关系是什么?(2) 适宜采用什么样的存储结构(3) 有那些基本运算?怎样实现? 也就是数据结构的三个层次:数据的逻辑结构、数据的存储结构、数据操作相关算法集合。下面举例说明:职工档案表如表7-1所示。 表7-1 职工档案表姓名性别出生年月部门职称工资婚否奖惩胡一民李 静张冬梅李清明王文明刘明伦男女女男女男01/10/6703/12/7804/12/6411/25/7201/12/5412/03/76.技术科生产科生产科技术科生产科生产科.工程师助工高工工程师助工高工.165013001550165012001800.T.F.T.T.F.T.MemoMemoMemoMemoMemoMemo.这张档案表可称为一个数据结构,它是一个线性表结构,表中的每一行为一个数据元素(它是数据结构的基本单位)。(1) 表中书元素的逻辑关系是:对表中任一元素,与它相邻且在它前
2、面的数据元素(也称为直接前驱)最多只有一个,与表中任一数据元素相邻且在它后面的数据元素(也称直接后继)也最多只有一个。表中第一个元素没有直接前驱,故称为开始 数据元素,最后一个数据元素没有直接后继,故称为终点元素(例:表中李静所在元素的直接前驱为胡一民所在的数据元素;直接后继为张冬梅所在的数据元素)(2) 该表的存储方式:表中的数据元素是顺序地邻接在一片连续的单元中,而不是用指针将这些元素连接在一起。(3) 对表元素怎样进行查找、删除、插入等操作方能提高数据操作效率。2、 有关概念(1) 数据:能被计算机识别、存储和加工的客观事物的描述,称为数据。(2) 结构:是指事物间的相互关系和约束。(3) 数据元素:数据的基本单位,也称数据结点(4) 算法:是指为解决某一问题而需进行的有限操作的过程描述。3、 数据结构的具体内容(1) 数据元素逻辑关系(逻辑结构),分为两大类:A 线性结构:其逻辑特征为:有且仅有一个开始元素和一个终点元素,所有数据元素最多只有一个直接前驱和 一个直接后继,线性表就是一个典型的线性结构。B 非线性结构: 其逻辑特征为:该结构中一个数据元素可能有多个直接前驱或直接后
3、继。除最一般的图结构外, 还有树结构。图结构:对数据元素的直接前驱和直接后继的个数不作限制。 树结构:有且仅有一个根元素无直接前驱,其他元素有且仅有一个直接前驱;每个元素都可 能有多个直接后继;除根元素外, 所有的数据元素都存在一条从根元素到该元素的路径。(2) 数据元素在计算机中的存储方法(即数据的存储结构,也称物理结构),分四类:A 顺序存储方法把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里,元素间的逻辑关系由存储单元的邻接关系体现,其存储表示我们称为顺序存储结构。顺序存储方法主要应用于线性的数据结构,如线性表、数组等,但非线性数据结构也可以通过某种线性化方法来实现顺序存储。B 连接存储方法并不要求逻辑上相邻的元素在物理位置上也相邻,元素的逻辑关系是由附加的指针字段表示。它要借助于程序语言的指针类型来描述元素的存储地址,每个数据元素所占存储单元分成两部分:元素数据项和指针项。C 索引存储方法在存储元素信息的同时,还建立附加的索引表。索引表的每一项成为索引项,而地址则指示存储位置。D 散列存储方法(地址转移法)根据元素的关键字,通过某一散列函数直接计算出该元素的存储地址。同一
4、种逻辑结构采用不同的存储方法,可得到不同的存储结构,采用何种存储方法来表示相应的逻辑结构,主要是根据算法具体确定。例如:线性表是一种逻辑结构,采用顺序方法的存储表示,该结构为顺序表;若采用链接方法的存储表示,该结构为链表;若采用散列方法的存储表示,该结构为散列表。(3) 数据处理与运算对一个数据结构,一般有如下的一些基本运算:A 遍历:在数据结构里的各元素间移动,或查看所有的数据元素。B 插入:往数据结构中添加新元素。C 更新:修改数据元素的数据项(又称为字段)的值D 删除:把指定的数据元素从数据结构中去掉。E 查找:在数据接中查找满足一定条件的数据元素F 排序:在保持数据元素个数不变的前提下,将数据元素按指定顺序重新排列(一般针对线性逻辑结构)由于数据运算是数据结构不可分割的部分,对于同一个数据结构,同一个基本运算,当选择的存储结构不同时,其运算的实现也会完全不同。例如,对一个线性表结构,同样进行插入操作,采用顺序存储时的算法就与采用链式存储时迥然不同。同样地,已给定了数据的逻辑结构和存储结构,若定义的运算不同,也可能导致完全不同的数据结构。例如,对线性表上的插入、删除运算仅在表的一
《数据结构的基本概念》由会员人***分享,可在线阅读,更多相关《数据结构的基本概念》请在金锄头文库上搜索。
基于加速度传感器的人体运动信息采集系统设计说明
9年级物理第一学期期中考试.docx
安全生产“三项行动”.docx
冷轧窄钢带项目可行性研究报告
工程划分与质量目标分解.doc
儿科学课程期末试卷A卷(试卷及答案详解).doc
宜兴市实验中学.doc
优秀早教活动教案.docx
印制线路板(pcb)电镀镍工艺介绍.doc
急诊会诊制度范文(九篇)
新出试用期个人工作总结.docx
污水处理厂工程总承包合同书
光纤Bragg光栅(FBG)设计.doc
2023年沪教版五年级下册品德当好“地球村”的小公民 教学设计说明.doc
10拜踌拜﹀.doc
资助贫困大学生仪式上的讲话在挂牌仪式上的讲话
室内空气中可吸入颗粒物的测定方法
九年级英语听力
白居易个人作品集
质量保证课程Key#03设 计、制造和安装.do.doc
2023-12-09 25页
2023-02-01 10页
2023-02-08 135页
2023-01-24 98页
2023-09-12 23页
2023-04-09 8页
2023-05-21 4页
2023-10-11 9页
2023-01-27 8页
2023-04-14 186页