用c语言描述完整版课件全套ppt整本书电子讲义全书电子课件最全教学教程.ppt
《用c语言描述完整版课件全套ppt整本书电子讲义全书电子课件最全教学教程.ppt》由会员分享,可在线阅读,更多相关《用c语言描述完整版课件全套ppt整本书电子讲义全书电子课件最全教学教程.ppt(572页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第一一章章 绪论绪论第第1章章绪论绪论1.1什么是数据结构什么是数据结构1.2基本概念和术语基本概念和术语1.3数据类型和抽象数据类型数据类型和抽象数据类型1.4算法描述与算法评价算法描述与算法评价第第一一章章 绪论绪论 本本章章将将介介绍绍数数据据结结构构研研究究的的对对象象、基基本本概概念念和和术术语语、算算法法的的概概念念及及其其描描述述方方法法(C C语语言言描描述述)、数数据据类类型型以以及及抽抽象象数数据据类类型型,并并概概述述数数据据结结构的发展概况及其在计算机科学中的地位。构的发展概况及其在计算机科学中的地位。第第1 1章章 绪绪 论论第第一一章章 绪论绪论随随着着计计算算机
2、机应应用用领领域域的的不不断断扩扩大大,计计算算机机处处理理的的对对象象更更多多的的是是非非数数值值计计算算问问题题,它它们们的的数数学学模模型型无无法法用用数数学学方方程程来来进进行行描描述述,此此时时就就必必须须建建立立相相应应的的数数据据结结构构来来进进行行描描述述,分分析析问问题题中中所所用用到到的的数数据据是是如如何何组组织织的的,研研究究数数据据之之间间的的关关系系如如何何,进进而而为为解解决决这这些些问问题题设设计计出出合合适的数据结构。适的数据结构。1.1什么是数据结构什么是数据结构第第一一章章 绪论绪论例例1职工信息管理职工信息管理图图1.1职工花名册表职工花名册表编号编号姓
3、姓 名名性性 别别年年 龄龄月月 收收 入入1 1李李 泉泉男男51519809802 2王王 怡怡女女47479459453 3张张 三三男男35358708704 4马小丁马小丁男男2727840840.第第一一章章 绪论绪论将将每每位位职职工工的的信信息息组组织织成成如如图图1.1所所示示的的花花名名册册。花花名名册册中中每每个个职职工工的的信信息息由由编编号号、姓姓名名、性性别别、年年龄龄、月月收收入入等等项项目目组组成成,占占表表的的一一行行,表表中中的的结结点点和和结结点点之之间间是是一一种种简简单单的的线线性性关关系系,这这就就是是上上述述花花名名册册表表的的线线性性逻逻辑辑结结
4、构构。当当用用计计算算机机对对上上述述花花名名册册表表中中的的数数据据进进行行运运算算时时,就就要要考考虑虑那那些些结结点点在在计计算算机机中中的的存存储储表表示示,即即存存储储结结构构。另另外外,还还必必须须考考虑虑如如何进行结点的插入、删除、修改、检索或查找,这就涉及到数据的运算何进行结点的插入、删除、修改、检索或查找,这就涉及到数据的运算第第一一章章 绪论绪论例例2旅游交通网络图旅游交通网络图如图如图1.2所示,为一个旅游交通网络咨询系统,可采用一种称之为所示,为一个旅游交通网络咨询系统,可采用一种称之为图的结构来表示实际的交通网络,图的结构来表示实际的交通网络,此时,这个交通网络图就表
5、示一个此时,这个交通网络图就表示一个数据结构。在这个数据结构中,结点之间的关系可以是任意的,图中数据结构。在这个数据结构中,结点之间的关系可以是任意的,图中任意两个结点之间都可以相关。同样,必须考虑构造后将这张图存放任意两个结点之间都可以相关。同样,必须考虑构造后将这张图存放入计算机中,这就要涉及到图的存储结构问题,以及图的运算。入计算机中,这就要涉及到图的存储结构问题,以及图的运算。从以上例子可见,要描述诸如此类的非数值计算问题的数学模型,从以上例子可见,要描述诸如此类的非数值计算问题的数学模型,涉及到一些诸如表、图还有树之类的数据结构。涉及到一些诸如表、图还有树之类的数据结构。数据结构课程
6、实际上是一门研究非数值计算问题的程序设计中计数据结构课程实际上是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机科学中,数据结构不仅是一般程序设计(特别是非数值计算的程算机科学中,数据结构不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。统及其它系统程序和大型应用程序的重要基础。第第一一章章 绪论绪论第第一一章章 绪论绪论数据是指信息
7、的载体,是对客观事物的符号表示,是对有效地输入到数据是指信息的载体,是对客观事物的符号表示,是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。数据元素是数据的基本单位,数据项是数据的不可分割的最小单位。数据元素是数据的基本单位,数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成,如上面职工花名册中的每个人的信息就是一个数据元素,而每个项组成,如上面职工花名册中的每个人的信息就是一个数据元素
8、,而每个人的信息包括编号、姓名、性别、年龄、月收入等,这每一个项目就属于人的信息包括编号、姓名、性别、年龄、月收入等,这每一个项目就属于数据项。数据项。1.2基本概念和术语基本概念和术语第第一一章章 绪论绪论数据对象是性质相同的数据元素的集合,是数据的一个子集。数据对象是性质相同的数据元素的集合,是数据的一个子集。数据类型(数据类型)是对在计算机中表示的同一数据对象及其在该数据类型(数据类型)是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。数据对象上的一组操作的总称。数据类型有时还分为原子数据类型和结构数据类型有时还分为原子数据类型和结构数据类型。数据类型。数据结构指的是数
9、据及数据之间的相互关系。一般地,数据结构包括数据结构指的是数据及数据之间的相互关系。一般地,数据结构包括以下三个方面的内容:以下三个方面的内容:(1)数据元素之间的逻辑关系,有时也称为数据的逻辑结构。)数据元素之间的逻辑关系,有时也称为数据的逻辑结构。(2)数据元素及其关系在计算机内存中的表示(又称为映象),称之)数据元素及其关系在计算机内存中的表示(又称为映象),称之为数据的物理结构,又称为数据的存储结构,它包括数据元素的表示和数为数据的物理结构,又称为数据的存储结构,它包括数据元素的表示和数据元素之间关系的表示。据元素之间关系的表示。(3)数据的运算及实现,即对数据元素可以施加的操作及其这
10、些操作)数据的运算及实现,即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。在相应的存储结构上的实现。第第一一章章 绪论绪论数据的逻辑结构是从逻辑关系上描述数据,可以看作是从具体问题数据的逻辑结构是从逻辑关系上描述数据,可以看作是从具体问题抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的不同特性,通常有下列四类基本逻辑结构:不同特性,通常有下列四类基本逻辑结构:(1)线性结构:结构中的数据元素存在一个对一个的关系,即所谓)线性结构:结构中的数据元素存在一个对一个的关系,即所谓的线性关系。的线性关系。(2)
11、树型结构:结构中的数据元素之间存在一个对多个的关系,是)树型结构:结构中的数据元素之间存在一个对多个的关系,是结点之间有分支、并具有层次关系的结构,它非常类似于自然界中的树。结点之间有分支、并具有层次关系的结构,它非常类似于自然界中的树。(3)图或网状结构:该结构中的数据元素之间的关系存在多个对多)图或网状结构:该结构中的数据元素之间的关系存在多个对多个的关系,如交通网络图就是一个图状结构。个的关系,如交通网络图就是一个图状结构。(4)集合:结构中的数据元素之间除了)集合:结构中的数据元素之间除了“同属于一个集合同属于一个集合”的相互的相互关系外,别无其它关系。关系外,别无其它关系。有时将树形
12、结构、集合和图或网状结构称为非线性结构,此时数据有时将树形结构、集合和图或网状结构称为非线性结构,此时数据逻辑结构就可分为线性结构和非线性结构两类。逻辑结构就可分为线性结构和非线性结构两类。第第一一章章 绪论绪论数据的存储结构是指逻辑结构用计算机语言的实现,就是数据元素数据的存储结构是指逻辑结构用计算机语言的实现,就是数据元素及其关系如何存放入计算机内存的问题。一般地,数据的存储结构可按及其关系如何存放入计算机内存的问题。一般地,数据的存储结构可按以下四种基本存储方法而得到:以下四种基本存储方法而得到:(1)顺序存储方法:是把逻辑上相邻的结点存储在物理位置上相邻)顺序存储方法:是把逻辑上相邻的
13、结点存储在物理位置上相邻的存储单元中,结点间的逻辑关系由存储单元的相邻关系而体现。由此的存储单元中,结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构,通常可借助计算机语言的数组来描得到的存储表示称为顺序存储结构,通常可借助计算机语言的数组来描述。述。(2)链状存储方式:不要求逻辑上相邻的结点在物理位置上也相邻,)链状存储方式:不要求逻辑上相邻的结点在物理位置上也相邻,数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储,数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储,必须通过一些附加的手段来存储这种相互关系,由此得到的存储表示称必须通过一
14、些附加的手段来存储这种相互关系,由此得到的存储表示称为链状存储结构。一般可以用指针来实现,通常可借助计算机程序语言为链状存储结构。一般可以用指针来实现,通常可借助计算机程序语言的指针类型或者游标来来描述。的指针类型或者游标来来描述。第第一一章章 绪论绪论(3)索引存储方法:该方法通常是在存储结点信息的同时,建立)索引存储方法:该方法通常是在存储结点信息的同时,建立附加的索引表。索引表一般有稠密索引和稀疏索引两种。附加的索引表。索引表一般有稠密索引和稀疏索引两种。(4)散列存储方法:该方法是依据结点的关键字直接计算出该结)散列存储方法:该方法是依据结点的关键字直接计算出该结点的存储地址,而后将结
15、点按某种方式存入该地址的一种存储方法。点的存储地址,而后将结点按某种方式存入该地址的一种存储方法。数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例如,检索(查找)、插入、删除、定位、修改、排序等。要注意的是,如,检索(查找)、插入、删除、定位、修改、排序等。要注意的是,这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操作,运算的实现依赖于所选取的存储结构,是依赖于不同的计算机程作,运算的实现依赖于所选取的存储结构,是依赖于不同的计算机程序设计语言的。序设计语言的
16、。第第一一章章 绪论绪论数据类型是具有相同性质的计算机数据的集合及在这个数据集合上数据类型是具有相同性质的计算机数据的集合及在这个数据集合上的一组运算。的一组运算。在高级程序语言中,数据类型可以分为原子类型和结构类型。原子类在高级程序语言中,数据类型可以分为原子类型和结构类型。原子类型即值不可分解的类型,如型即值不可分解的类型,如C语言中的整型、字符型、实型、指针类型等;语言中的整型、字符型、实型、指针类型等;而结构类型则指的是其值可由若干成分按某种结构组成的类型,是可以分而结构类型则指的是其值可由若干成分按某种结构组成的类型,是可以分解的,如解的,如C语言中提供的结构体。语言中提供的结构体。
17、抽象数据类型(抽象数据类型(ADT)是指一个数学模型及定义在该数学模型上的一)是指一个数学模型及定义在该数学模型上的一组操作。抽象数据模型的定义取决于它的一组逻辑特性,与其在计算机内组操作。抽象数据模型的定义取决于它的一组逻辑特性,与其在计算机内部如何表示和实现无关。部如何表示和实现无关。1.3数据类型和抽象数据类型数据类型和抽象数据类型第第一一章章 绪论绪论算法是对特定问题求解方法和步骤的一种描述,它是指令的一组有限算法是对特定问题求解方法和步骤的一种描述,它是指令的一组有限序列。一个算法必须具备以下五个重要特性:序列。一个算法必须具备以下五个重要特性:(1)输入:一个算法必须具有零个或多个
18、的外界输入。)输入:一个算法必须具有零个或多个的外界输入。(2)输出:一个算法必须有一个或多个的输出。)输出:一个算法必须有一个或多个的输出。(3)有穷性:一个算法对任何合法的输入值必须总是在执行有穷步之后)有穷性:一个算法对任何合法的输入值必须总是在执行有穷步之后结束,并且每步都必须在有穷时间内完成。利用这一点,我们可以区别算结束,并且每步都必须在有穷时间内完成。利用这一点,我们可以区别算法与程序。法与程序。(4)确定性:算法中每一条指令必须有确切的含义,不会产生二义性。)确定性:算法中每一条指令必须有确切的含义,不会产生二义性。(5)可行性:算法中描述的操作都必须可以通过已经实现的基本运算
19、有)可行性:算法中描述的操作都必须可以通过已经实现的基本运算有限次执行来实现,而且算法必须在有限时间内完成。限次执行来实现,而且算法必须在有限时间内完成。一个算法可以用自然语言、数学语言或约定的符号来描述,也可用计一个算法可以用自然语言、数学语言或约定的符号来描述,也可用计算机高级程序语言来描述,如算机高级程序语言来描述,如PASCAl语言、语言、C语言、语言、C、Java或伪代或伪代码等。本书选用码等。本书选用C语言作为描述算法的工具。语言作为描述算法的工具。1.4.1算法描述算法描述1.4算法描述与算法评价算法描述与算法评价第第一一章章 绪论绪论1.4.2算法的设计要求算法的设计要求设计一
20、个好的算法可以从以下几个方面考虑:设计一个好的算法可以从以下几个方面考虑:(1)正确性。算法是为了针对解决具体问题而提出的,算法的正确与)正确性。算法是为了针对解决具体问题而提出的,算法的正确与否必须满足解决实际问题的需要,要经得起一切可能的输入数据的考验。否必须满足解决实际问题的需要,要经得起一切可能的输入数据的考验。(2)可读性。算法要让人阅读得懂,程序要尽可能地简单通俗,当然)可读性。算法要让人阅读得懂,程序要尽可能地简单通俗,当然也必须有效。也必须有效。(3)健壮性。当输入数据非法时,算法应能适当地作出反应或进行处)健壮性。当输入数据非法时,算法应能适当地作出反应或进行处理。理。(4)
21、高效率。要求算法的执行时间要尽可能地短,对于存储空间要尽)高效率。要求算法的执行时间要尽可能地短,对于存储空间要尽可能地少,即做到既省时又节省空间。可能地少,即做到既省时又节省空间。要设计一个好的算法,必须对这几个方面综合考虑,才可以设计出较要设计一个好的算法,必须对这几个方面综合考虑,才可以设计出较好较优的算法。好较优的算法。第第一一章章 绪论绪论考虑算法的效率应从下几个方面考虑:考虑算法的效率应从下几个方面考虑:(1)时间效率。考虑算法所耗费的运行时间。)时间效率。考虑算法所耗费的运行时间。(2)空间效率。考虑运行算法需要耗费的存储空间,其中主要考虑算)空间效率。考虑运行算法需要耗费的存储
22、空间,其中主要考虑算法所需的辅助存储空间。法所需的辅助存储空间。(3)算法应尽可能地简单,易于理解,易于编码和调试并能得出正确)算法应尽可能地简单,易于理解,易于编码和调试并能得出正确结果。结果。一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它可以认为是算法中每条语句的执行时间之和。可以认为是算法中每条语句的执行时间之和。1.4.3算法的评价算法的评价第第一一章章 绪论绪论例如,两个例如,两个nn矩阵相乘的算法:矩阵相乘的算法:for(i=1;i=n;i+)/*n+1次次*/for(j=1;j=n;j+)/*n(n+1)次
23、)次*/cij=0;/*nn次次*/for(k=1;k0时的线性表记为:(时的线性表记为:(a1,a2,ai,an)其中,其中,a1是第一个数据元素,又称为起始结点,是第一个数据元素,又称为起始结点,an是最后一个数据是最后一个数据元素,又称为终端结点。当元素,又称为终端结点。当i=1,2,n1时,时,ai有且仅有一个直接后有且仅有一个直接后继继ai+1;当;当i=2,3,n时,时,ai有且仅有一个直接前趋有且仅有一个直接前趋ai1。注意这里的。注意这里的ai(1in)仅仅是一个抽象的符号,其具体含义,在不同的情况下各)仅仅是一个抽象的符号,其具体含义,在不同的情况下各不相同,它可以是一个数,
24、一条记录或一个符号,甚至是更复杂的信息。不相同,它可以是一个数,一条记录或一个符号,甚至是更复杂的信息。例如,英文字母表例如,英文字母表(A,B,Z)是一个线性表,职工工资表等。是一个线性表,职工工资表等。线性表的结点之间的逻辑关系符合线性结构的逻辑特征,是一种线线性表的结点之间的逻辑关系符合线性结构的逻辑特征,是一种线性结构。性结构。2.1.1线性表的逻辑结构线性表的逻辑结构2.1线性表的基本概念线性表的基本概念第二章第二章 线性表线性表常见的线性表的基本运算:常见的线性表的基本运算:(1)置空表)置空表SETNULL(L):将线性表:将线性表L置成空表。置成空表。(2)求长度)求长度LEN
25、GTH(L):求给定线性表:求给定线性表L中数据元素的个数。中数据元素的个数。(3)取元素)取元素GET(L,i):结果是线性表:结果是线性表L中的第中的第i个数据元素。个数据元素。(4)定位函数)定位函数LOCATE(L,x):当线性表中存在一个值为:当线性表中存在一个值为x的数据元的数据元素,则结果是该数据元素在表中的位序,否则,表示值为素,则结果是该数据元素在表中的位序,否则,表示值为x的数据元素的数据元素不存在。不存在。(5)前趋函数)前趋函数PRIOR(L,x):若:若x为线性表中的一个数据元素,且为线性表中的一个数据元素,且其位序大于其位序大于1,则结果为,则结果为L的直接前趋,否
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 描述 完整版 课件 全套 ppt 电子 讲义 全书 教学 教程
限制150内