《数据结构——C++实现 教学课件 ppt 作者 缪淮扣 顾训穰 沈俊 数据结构-第一章》由会员分享，可在线阅读，更多相关《数据结构——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（int i=0; i=5; i+） printf（“i=%d”,i） 在for结构中把变量i声明为一个整数并把它初始化为0。,作用域,函数中声明的变量只能在函数内部使用；在类中定义的变量，只能在该类内部使用。这些变量都称为
