997-数据结构 C++实现.ppt
《997-数据结构 C++实现.ppt》由会员分享,可在线阅读,更多相关《997-数据结构 C++实现.ppt(89页珍藏版)》请在三一文库上搜索。
1、数据结构 C+实现 第一章 缪淮扣 顾训穰 沈 俊 编著 科 学 出 版 社,新世纪计算机专业系列教材,内 容 简 介,数据结构是计算机专业教学计划中的一门核心课程,也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。从事与计算机科学与技术相关的工作, 尤其是计算机应用领域的开发和研制工作,必须具备坚实的数据结构的基础。 本书对C+语言作了简单介绍,叙述了抽象数据类型和面向对象的概念,介绍了线性表、栈、队列、数组、广义表、树、图等数据结构,并介绍了查找和排序的方法。全书用C+语言描述并实现了所有数据结构的类和程序,并附有习题,便于教学。 本书是为高等院校开设数据结构课程
2、编著的教材,可供计算机等专业,也可供从事计算机开发和应用的工程技术人员阅读参考。,为什么要学习数据结构?,作为计算机程序组成部分的数据结构和算法的研究,一直受到计算机领域工作者的高度重视。数据结构是计算机专业教学计划中的一门核心课程,也是信息管理、通信电子、自动控制等与计算机技术关系密切的专业的一门基础课程。 要从事与计算机科学与技术相关的工作,尤其是计算机应用领域的开发和研制工作,必须具备坚实的数据结构的基础。,数据结构课程的教学目的,数据结构课程的教学目的是使学生学会分析研究计算机所要加工处理的数据的特征,掌握组织数据、存储数据和处理数据的基本方法,并加强在实际应用中选择合适的数据结构和相
3、应算法的训练。,为什么用面向对象的观点来描述数据结构?,面向对象技术是软件工程领域中的重要技术,它不仅是一种程序设计方法,更重要的是一种对真实世界的抽象思维方式。 目前,面向对象的软件分析和设计技术已发展成为软件开发的主流方法。为了适应软件开发方法与技术的发展以及应用领域的要求,就有必要改进和充实数据结构的教学内容。 因此,用面向对象的观点来描述数据结构就成为一种既顺理成章又紧迫的选择。,采用C+描述数据结构,用面向对象的观点来描述数据结构,要涉及到面向对象程序设计语言的选用问题。 目前被广泛采用作为程序设计语言教学的是C语言,C+是以C语言为基础的、使用比较普遍的面向对象程序设计语言。因此本
4、书采用了C+作为数据结构的描述语言。,数据结构课程的特点,数据结构课程内容丰富,学习量大; 隐藏在各部分内容中的方法和技术多; 贯穿于全书的动态链表存储结构和递归技术令不少初学者望而生畏。 本书的编写者长期来从事数据结构课程的教学,对该课程的教学特点和难点有比较深切的体会。,作者的努力,作者在认真总结二十多年讲授数据结构课程的基础上参考了美国ACM/IEEE CS所颁布的计算2001教程,吸收了国内外各种数据结构教材的优点,对多年来形成的数据结构课程的教学内容进行了合理的剪裁,既强调了数据结构的原理和方法,又注重了其实践性,使之适应于现代大学生的学习特点和要求。,本书的一个重要特点,本书的一个
5、重要特点就是将程序设计的基础与数据结构的方法尽可能的结合起来。第一、二章介绍C+语言时尽可能给出比较完整的程序,使学生能对C+语言有比较全面和深入的了解,也便于上机实习,从而为数据结构课程的实验建立良好的基础。,本书的组织结构,全书共分九章,第一、二章介绍了数据结构、算法及其复杂度的基本概念,对C+作了简单介绍,并叙述了抽象数据类型和面向对象的概念。第三章至第五章介绍了线性结构线性表、栈、队列、数组、广义表;第六章和第七章介绍了非线性结构树和图;第八章和第九章分别介绍了查找和排序的方法。,1 绪论,1.1 (算法+数据结构)= 程序 计算机神通广大,聪明能干。 计算机的本领是人是用“程序”来“
6、教” 的。 让计算机解题实际上就是为计算机编程序。因而解题的过程就不仅仅是编程序,而是一个包括编程序在内的软件开发过程。,软件不仅仅指程序,而是包括程序以及开发程序的过程中所产生的各种文档。软件开发的目标是产生能让计算机有效工作的程序,因此程序是软件的核心。 程序到底是什么呢? N.Wirth给出的一个著名的公式: 算法+数据结构=程序 曾经产生了深远的影响。 现在受到了挑战。,20世纪90年代,面向对象的方法受到了很大的重视,并得到比较广泛的推广和应用。 在面向对象程序设计中,密切相关的数据与过程被定义为一个整体(即对象),而且一旦作为一个整体定义了之后,就可以使用它,而无需了解其内部的实现
7、细节,从而提高软件开发的效率。 封装和数据隐藏是面向对象问题解和面向对象程序设计的基本要素。 算法+数据结构=程序 (算法+数据结构)= 程序,本书以面向对象的观点来介绍各种数据结构以及与这些数据结构有关的算法的知识。 第一章将介绍数据结构以及算法的基本概念,并介绍用来描述数据结构和算法的语言C+。,1.2 数据结构的基本概念,计算机科学是一门研究信息表示和处理的科学,人们是用程序来处理信息的。 对程序设计方法进行系统的研究。这不仅涉及到研究程序结构和算法,同时也涉及到研究程序加工的对象。 用计算机解题: 具体问题 数学模型设计算法和编制程序 从对问题的分析中提取操作的对象,并找出这些操作对象
8、之间的关系,然后用数学的语言加以描述。,1.2.1 两个简单的数据结构实例,例 1-1 人事登记表 线性数据结构,例1-2 一个典型的学校行政机构,层次型数据结构,1.2.2 什么是数据结构,一个水平再高的厨师,尽管他可以把烹调某个菜肴的过程掌握得很好,但如果不给他原料,他是做不出色、香、味俱全的菜。 “巧妇难为无米之炊”。 对一个程序来讲,数据就是“原料”。 大千世界中有各种各样的信息,交通灯,交通卡,交易,思想。这些信息必须转换成数据才能在计算机中进行处理。,“什么是数据”以及与之相关的概念,数据(data):信息的载体, 数、字符、图形、图象、声音以及所有能输入到计算机中并被计算机程序识
9、别和处理的符号的集合。 数据元素(data element):数据的基本单位。 数据项(data item):数据的最小单位 数据对象:数据的子集。自然数集合 =0, 1, 2, 是“数”的数据对象;所有的字符是数据,字母集合AS=A, B, Z, a, b, , Z是该数据的数据对象。,数据结构(data structure) :数据以及数据元素之间的相互关系。 数据结构分为两大类:线性结构和非线性结构。这两类结构通常又可分为下列四类基本结构 集合,结构中的数据元素之间就是“同属于一个集合” ; 线性结构,结构中的数据元素之间存在的是一种线性关系,即一对一的关系; 树形结构,结构中的元素存在
10、着一对多的关系; 图形结构或网状结构,结构中的元素之间存在着多对多的关系。,四种不同结构的关系图,数据的逻辑结构属于用户视图,是用户所看到的数据结构,是面向问题的。它描述的是数据元素之间的逻辑关系。 数据的物理结构,又称存储结构,是数据的逻辑结构在计算机中的物理存储方式,它属于具体实现的视图,是面向计算机的。 数据的逻辑结构和物理结构是密切相关的两个方面。一般来说,算法设计是基于数据的逻辑结构,而算法实现则基于数据的物理结构。,1.3 C+语言基础,本书以面向对象的观点来介绍数据结构。 所涉及的程序设计的方法自然是面向对象的程序设计方法。 描述数据结构所采用的语言应该是面向对象的程序设计语言。
11、 选择了目前比较流行的C+语言来描述各种数据结构以及相应的算法。 实用和易学 C+与C具有许多相同的功能,C+对C有很多扩充的功能。假设读者已经熟悉C语言。,1.3.1 程序结构,一个C+程序可由若干个文件组成。C+的文件分为头文件和源文件两类。 头文件以.h为后缀,用于存放函数声明,它给出了函数的参数类型,个数以及函数的返回类型,称为原型。有一些头文件是系统定义的,如,而另一些头文件是用户定义的;而源文件是用来存放C+的源代码。用于源文件的后缀为.CPP。可通过预处理指令#include,将头文件包含在适当的文件中。,一个典型的C+程序,/* 头文件hello.h */ # ifndef F
12、ILENAME_H # define FILENAME_H char *hello(char *); # endif,/* 源代码文件hello.cpp */ # include /含有sprint( )的原型 # include / 含有求字符串长度函数strlen( )的原型 # include /含有hello( )的原型 char * hello(char* world) char *result = new char9+strlen(world); /* Return the string “Hello, world”. */ sprintf(result,”Hello,%s.”,w
13、orld); return result; /* 源代码文件main.cpp */ # include # include“hello.h” main( ) cout hello(“Hello, shanghai”); ,头文件hello.h 是hello函数的原型。 源文件hello.cpp定义了hello 函数,该函数有一个形式参数,其类型为string,返回函数的类型为string。 main.cpp 是打印“hello, Shanghai”的主程序,它构造并打印一个欢迎词字符串。 sprintf( )是系统内定义的打印函数。 main.cpp中调用的hello函数,其参数的类型、个数以
14、及函数的返回类型必须与预处理指令“include”所定向的头文件“hello.h”所给出的原型中的函数的参数类型、个数、函数的返回类型相匹配。,C+中有两种注释方法,多行注释:包含在定界符“/*”和“*/”之间的所有文本,如: /* This book is designed to present the fundamentals of data structures from an object-oriented perspective. */ 单行注释:在符号/之后至本行末的所有文本内容。 例如,C注释 /* This is a C+ program.*/ 可写为C+的单行注释 /This
15、 is a C+ program.,1.3.2 数据声明和作用域,数据声明的作用 C+的基本数据类型:char、int、float和double,这些数据类型中的某些又可以用short、long、signed和unsigned进行修饰 数据声明的主要形式: 常数值 变量:数据类型的实例,可被修改。 常量:在其生命期中不可被赋值的变量。如 const int pi=3.1415926。,(4) 枚举:声明一个整型常数序列的方式。用关键字enum声明的。例如声明: enum month=Jan=1, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov
16、, Dec,(5) 引用:引用类型用于为一个对象提供一个可替换的名字。对于某一个类型的对象的引用,所采用的声明方式就是在该类型后面添上一个符号。例如,int x=9; int y=x; x=13 printf(“x=%d,y=%d”,x,y,);,在C中,程序块的所有声明都必须出现在所有可执行语句之前。在C+中,声明可放在使用所声明的内容之前的任何地方。例如 printf(“Enter two integers:” ); int x,y; printf(“x=%d, y=%d”, x, y,) 变量也可以在for结构的初始化部分予以声明,其作用域仍然是在定义for结构的程序块内。例如 for(
17、int i=0; i=5; i+) printf(“i=%d”,i) 在for结构中把变量i声明为一个整数并把它初始化为0。,作用域,函数中声明的变量只能在函数内部使用;在类中定义的变量,只能在该类内部使用。这些变量都称为局部变量。 C+的局部变量的作用域从其声明开始到结束程序块的右花括号终止。因此,变量声明之前的语句即使在同一个程序块内也不能引用该变量。变量声明不能放在while 、do/while、for 和 if 结构的条件中。 把变量声明放在靠近首次引用的位置,即用到时再声明后写上使用,可提高程序的可读性。,在整个程序中都能引用的变量叫全局变量。如果一个全局变量在文件1中声明,而在文件
18、2中使用,则在文件2中必须使用关键字extern对该变量进行声明。 在构成一个程序的两个文件中,如果分别声明了具有相同名字的一个全局变量,它们分别代表不同的实体,此时就要在两个文件中分别使用关键字static对变量进行声明,以保证不发生混淆。 如果一个程序块中某个局部变量与某个全局变量同名,但又要在该程序块中引用该全局变量,则可以使用域操作符:来引用全局变量。,1.3.3 输入/输出,执行输入输出操作,必须用#include预处理指令包括一个头文件。 关键字cin用于C+中的输入,操作符用于分开输入的变量。空白(即teb键、回车或空格键)用于在标准输入设备上将不同变量的值分开。 关键字cout
19、用于输出到一个标准输出设备。cout和将被输出的每一内容之间用操作符 分开。 此外,定向到错误文件的命令由cerr定义。,例1-3 程序:C+中的输入输出,# include void main( ) int x,y; cin x y; cout “x=” x endl; cout “y=” y endl; ,执行上述程序时,按照输入格式 5 10 回车 或 5 回车 10 回车 均使变量X和Y分别得到输入值5和10,并输出如下结果: x=5 y=10,C+中的输入输出, “自由格式”。程序员不必使用格式化符号来指明输入输出项的类型和顺序。 输入输出操作符能够被重载。 如有对文件的输入输出,则
20、必须在程序中包含头文件 fstream.h,它定义了类 ifstream 、ofstream 和 fstream。 要创建一个输入流,必须声明它为类ifstream。要创建一个输出流,必须声明它为类ofstream。而执行输入输出的流必须声明为类fstream。,例1-4 含有文件输入输出的程序 # include # include void main ( ) ofstream outFile(“my.out”, ios:out); if(!outFile) cerr “can not open my .out” endl; /standard error device return; in
21、t n=70;float f =30.2; outFile “n:”n endl; outFile “f:” f endl; ,1.3.4 函数,C+中有两种函数:常规函数和成员函数。成员函数用于类方法的定义,完成一个特定的功能。 无论是常规函数还是成员函数,其定义都包括四个部分: 函数名 形式参数表 返回类型 函数体。 函数的使用者通过函数名来调用函数,调用过程把实际参数传送给相应的形式参数作为数据的输入;然后通过执行函数体中的语句实现该函数的功能;最终得到的返回值由函数名带回给函数的调用者。,函数如果有返回值,则该值的类型就是该函数的返回类型。函数的返回值是通过函数体中的return语句返
22、回的。return 语句的作用是返回一个其类型与返回类型相同的值,并终止函数的执行。,例1-5 一个函数 int min (int a, int b) if a b return a; else return b; ,对于不返回值的函数,其返回类型要声明为 void。 在C+中,指定空参数列表的方法是在圆括号中写入void,或什么也不写。,下面的程序例子,演示了声明和使用不带参数的函数的方法。,例1-6 使用不带参数的函数 # include void f1( ); void f2 (void); main( ) f1( ); f2( ); return 0; ,void f1 ( ) cou
23、t “Function f1 takes no arguments n”; void f2(void) cout “Function f2 also takes no argumentsn”; ,输出结果为: Function f1 takes no arguments Function f2 also takes no arguments,1.3.5 参数传递,函数调用时传送给形参表的实参与形参在类型、个数以及顺序上必须保持一致。 C+中函数的参数传递有四种方式: 值参数传递 引用参数传递 常值参数传递 常值引用参数传递 值参数传递是缺省的参数传递方式。 若采用这种传递方式,程序在运行时,对
24、应的实际参数的值传送给形式参数所对应的局部工作区中的单元。,当函数的执行终止时,函数修改的是形式参数所对应的工作单元的值,而该值不传回给实际参数。 因此值参数的传递方式不会改变对应形式参数的实际参数的值。 使用引用参数传递方式时,需要在函数的形参表中将形参声明为引用类型,即在参数名前加上一个“”。 当一个实参与一个引用类型形参结合时,被传递的不是实参的值,而是实参的地址,函数通过地址存取被引用的实参。 当函数执行时,任何对形式参数的改变也就是对实际参数的改变。,当要求一个函数调用返回多于一个参数时,也应采用参数传递方式。此时,将参数中的一个由return语句返回,而其它参数由引用返回。 常值引
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 997-数据结构 C+实现 997 数据结构 C+ 实现
链接地址:https://www.31doc.com/p-3026218.html