《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第1章 绪论
19页1、第1章 绪论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据类型和抽象数据类型 1.4 算法描述与算法评价,本章将介绍数据结构研究的对象、基本概念和术语、算法的概念及其描述方法(C语言描述)、数据类型以及抽象数据类型,并概述数据结构的发展概况及其在计算机科学中的地位。,第1章 绪 论,随着计算机应用领域的不断扩大,计算机处理的对象更多的是非数值计算问题,它们的数学模型无法用数学方程来进行描述,此时就必须建立相应的数据结构来进行描述,分析问题中所用到的数据是如何组织的,研究数据之间的关系如何,进而为解决这些问题设计出合适的数据结构。,1.1 什么是数据结构,例1 职工信息管理,图1.1 职工花名册表,将每位职工的信息组织成如图1.1所示的花名册。花名册中每个职工的信息由编号、姓名、性别、年龄、月收入等项目组成,占表的一行,表中的结点和结点之间是一种简单的线性关系,这就是上述花名册表的线性逻辑结构。当用计算机对上述花名册表中的数据进行运算时,就要考虑那些结点在计算机中的存储表示,即存储结构。另外,还必须考虑如何进行结点的插入、删除、修改、检索或查找,这就涉及到数据的运算,例2
2、 旅游交通网络图 如图1.2所示,为一个旅游交通网络咨询系统,可采用一种称之为图的结构来表示实际的交通网络, 此时,这个交通网络图就表示一个数据结构。在这个数据结构中,结点之间的关系可以是任意的,图中任意两个结点之间都可以相关。同样,必须考虑构造后将这张图存放入计算机中,这就要涉及到图的存储结构问题,以及图的运算。 从以上例子可见,要描述诸如此类的非数值计算问题的数学模型,涉及到一些诸如表、图还有树之类的数据结构。 数据结构课程实际上是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机科学中,数据结构不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。,数据是指信息的载体,是对客观事物的符号表示,是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。 数据元素是数据的基本单位,数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成,如上面职工花名册中的每个人的信息就是一个数据
3、元素,而每个人的信息包括编号、姓名、性别、年龄、月收入等,这每一个项目就属于数据项。,1.2 基本概念和术语,数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据类型(数据类型)是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 数据类型有时还分为原子数据类型和结构数据类型。 数据结构指的是数据及数据之间的相互关系。一般地,数据结构包括以下三个方面的内容: (1)数据元素之间的逻辑关系,有时也称为数据的逻辑结构。 (2)数据元素及其关系在计算机内存中的表示(又称为映象),称之为数据的物理结构,又称为数据的存储结构,它包括数据元素的表示和数据元素之间关系的表示。 (3)数据的运算及实现,即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。,数据的逻辑结构是从逻辑关系上描述数据,可以看作是从具体问题抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的不同特性,通常有下列四类基本逻辑结构: (1)线性结构:结构中的数据元素存在一个对一个的关系,即所谓的线性关系。 (2)树型结构:结构中的数据元素之间存在一个对多个的关系,是结点之间有分支、并具有
4、层次关系的结构,它非常类似于自然界中的树。 (3)图或网状结构:该结构中的数据元素之间的关系存在多个对多个的关系,如交通网络图就是一个图状结构。 (4)集合:结构中的数据元素之间除了“同属于一个集合”的相互关系外,别无其它关系。 有时将树形结构、集合和图或网状结构称为非线性结构,此时数据逻辑结构就可分为线性结构和非线性结构两类。,数据的存储结构是指逻辑结构用计算机语言的实现,就是数据元素及其关系如何存放入计算机内存的问题。一般地,数据的存储结构可按以下四种基本存储方法而得到: (1)顺序存储方法:是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中,结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构,通常可借助计算机语言的数组来描述。 (2)链状存储方式:不要求逻辑上相邻的结点在物理位置上也相邻,数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储,必须通过一些附加的手段来存储这种相互关系,由此得到的存储表示称为链状存储结构。一般可以用指针来实现,通常可借助计算机程序语言的指针类型或者游标来来描述。,(3)索引存储方法:该方法通常是在存储结点信息的
《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第1章 绪论》由会员E****分享,可在线阅读,更多相关《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第1章 绪论》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页