数据结构面向对象

现代程序设计——C 与数据结构面向对象的方法与是非常不错的，比较基础内容简介本书在系统地介绍C++的封装性、继承性和多态性的基础之上,采用面向对象的思想和抽象数据类型的概念,用C艹语言有效地组织和描述了各种常用数据结构(线性表、数组、串、堆栈、队列、树、图)的抽象类及其实现,并注意每一种数据结构的不同存储方法、有关算法及其应用。再者,本书还将数据结构与算法设计技术有效地结合起来,列举了一些典型实例,如迷宫问题、图的着色问题和货郎担问题的算法描述和实现。全书共分三部分:第一部分介绍C++语法;第二部分介绍各种数据结构的C++抽象类及其实现;第三部分介绍面向对象的程序设计方法,并进行综合实例分析全书体系完整、概念清楚、内容充实、取材适当,实用性强,是积多年教学经验写成的。可以作为大学本科电子类、信息类及相关专业的教材或参考书,也可供学习过C语言的非计算机专业的大学生或专科生自学或参考使用前言计算机与网络技术的高速发展,特别是面向对象技术的出现,使得C++的软件开发得到了迅速普及。这种面向对象的技术,不仅符合人们思维习惯,而且用它开发出来的软件可靠性很强。数据结构又是计算机学科中的一门核心课程,就软件产品而言,关键是建立合理的软件体系结构和程序结构。如果脱离薮据结构,只是进行纯粹的C艹+语法功能介绍,就不能形成体系的结构和思路,不符合现代程序设计的要求。作为非计算机专业的大学生,要提高程序设计和软件开发能力,就必须在学习了《C程序设计》的基础上,进一步学习、掌握面向对象的C艹+程序设计和有效组织各种数据在计算机中的存储、传递和转换的方法。因此,用不多的学时开设一门既介绍面向对象的程序设计方法,又将系统的数据结构思路融合到面向对象的方法上来的课程,对于非计算机专业的大学生来说,是很有必要的,符合形势发展的需要本教材《现代程序设计》就是通过系统地介绍面向对象的C艹程序设计方法和数据结构的C艹描述,并通过具体的实例分析,使学生真正掌握数据结构应用于面向对象程序设计的方法,从而更好地从事软件开发和工程应用。本教程在北京理工大学电子工程系作为教学改革项目开设已经3年,深受学生欢迎;书中所有例题,也是教师们在多年的教学过程中,精心挑选、编写和调试过的,具有一定的代表性。本书可以作为电子专业、通信专业和其他非计算机专业的高校本科生、成人教育学院的本科生以及计算机专业的大专生选用的教材,也可供程序设计工程人员和爱好者自学或参考使用。全书内容分三部分,共十八章。第一部分是面向对象的程序设计基础,包括第一章到第六章。第一章引入面向对象的思想、概念和基本特征,并讨论了一些从C过渡到C++的语法变化。第二章主要介绍C艹+类的定义及其封装性的体现,并重点介绍了构造函数和析构函数的作用和定义方式。第三章主要介绍C++中的几种常用语法和一些特殊用途,包括函数和运算符的重载、友员和引用的定义和使用。第四章主要介绍继承及派生类的定义和使用,包括单继承和多继承、继承方式及基类数据在派生类中访问权限的变化情况的介绍和应用。引入了虚基类的概念并介绍了它的用途。第五章主要介绍多态性在C++中的体现,并重点介绍了运行时的多态性一一虚函数的引入、定义和使用,以及纯虚函数和抽象类的概念。第六章主要介绍了引入模板的意乂、定义和使用模板函数和模板类的方法及模板函数重载和模板类派生的方式。第二部分是数据结构的抽象类及其实现,包括第七章到第十五章第七章主要引入了数据结构的定义及抽象数据类型的概念,而且讨论了数据结构所研究的三个方面(逻辑结构、存储结构和算法)的内容,还简要介绍了数据结构的分类及其抽象层次。第八章到第十二章依次介绍了线性表、数组、串、堆栈和队列的概念、抽象类描述及不同存储表示的各种类的具体定义、实现和应用。第十三章和第十四章依次介绍了树和图的基本概念和多种存储表示,并给出了典型表示的抽象类定义、实现和应用。第十五章主要介绍了索引与散列表的概念、散列函数的设计方法及解决冲突的多种策略第三部分是面向对象程序设计实例,包括第十六章到第十八章。第十六章主要概述C++面向对象程序设计的一般规范,并介绍了一些常用算法的设计思想及面向对象程序设计的一般过程。第十七章和第十八章是两个综合实例,分别介绍图的着色问题和货郎担问题的描述、模型的建立、算法分析及其程序实现。本书的第二章到第六章由苏京霞老师编写,第七章~第十二章由聂青老师编写,第一章和第十三章~第十八章由沈晴霓老师编写。特別感谢罗森林副教授的帮助和指导,他为我们的初稿提出了许多宝贵的意见。在整个教材的编写过程中还得到了苏广川教授的大力支持和细心指导,在此也表示我们的衷心谢意。由于时间仓促和水平有限,难免有一些错误和不足之处,恳请读者批评指正作者2002年4月23日目录第一部分面向对象的C++程序设计基础第一章面向对象的概述1.1面向对象的思想11面向对象程序设计·+··p·“····、.(1)112面向对象的语言(112面向对象的基本概念(212对象(2)122消息类(3)13面向对象的基本特性131封装性(3)132继承性带鲁4133多态性(4)14从C过渡到C++D··,■(4141函数原型說明142变量的说明(5)143输入和输出(5)144 const说明竽(6145void类型习题(6)第二章类及其对象的封装性…(72.1类的定义(722类的成员函数…(8)221成员函数的定义(8222内置成员函数(8)23对象的定义鲁鲁923类与对象(9)232定义对象…。,着924构造函数和析构函数…241构造函数…(11242析构函数…243动态存储(21)25C++中的封装性………(24)习题(27)第三章友员、重载和引用(28友员(2831友员的定义曹鲁“(29)32友员函数(29)33友员成员…·香(30)34友员类(3132重载…(33)32函数重载……(33)322运算符重载·普··普··(3633引用(46)331引用的概念……(46332引用的应用(47)333引用传递参数(48334引用返回值…(49)335常引用D鲁(52)习题(53第四章继承与派生(544.1继承与派生…(5442派生类…(5442派生类生成过程(55)422派生类定义(55)423访问权限…(56)424派生类的构造函数和析构函数(6143多继承(63)43.1多继承的概念(63432多继承的定义…433多继承的构造函数与析构函数……………(6544虚基类…(71)441问题的提出………………(71442虚基类的概念(72)443虚堪类的初始化(74习题77第五章虚函数与多态性(78)5:1多态性……(7851多态性概述(78)52编译吋的多态性(79)53运行时的多态性(80)2虚函数…曹鲁“(80521对象指针(80)522虚函数的定义及使用·香(82)53抽象类(87)531纯虚函数与抽象类(87532纯虚函数多态性的体现(89)习题···普··普··92)第六章模板(94)6.1模板的概念·(9462函数模板(95)621函数模板和模板函数(95)622重载模板函数(9763类模板(9863类模板与模板类的概念……(98)632类模板的派生(101习题(104第二部分数据结构的C++抽象类及其实现第七章绪论(1057.1数据结构的基本概念(105)72抽象数据类型的面向对象概念(107数据类型(107)722数据抽象与抽象数据类型……………………(10773算法和算法分析(108)731算法(108732算法设计的要求(108)733算法效率的度量……………………(10974数据结构的抽象层次(111)习题鲁香·D·看鲁·e。D(112)第八章线性表(113)8:1线性表的定义(113)8.11线性表的逻辑结构13812线性表的顺序存储表示(113)8.13线性表的链式存储表示(114)2抽象链表类(115)821抽象链表类的定义115822抽象链表中典刑成员函数的实现(116)83单链表···……(118)831单链表的定义(118832单链表的常用操作(120)833单链表类的定义(120)834单链表的常用成员函数的实现………(122)835一元多项式加法(127)84循环链表(131841循环链表的定义(131842循环链表类的定义…(131)843循环链表常用函数的实现…(132844约瑟夫( Josepha)问题(139)85双向链表(139851双向链表的定义(139)852双向链表类的定义·(140)853双向链表的常用成员函数的实现141习题(147第九章数组149)9.1数组的定义(149)9.1数组的逻辑结构(149)92数组的存储结构(149)913数组的常用操作(150)92抽象数组类(150)921抽象数组类的定义鲁鲁(150)922抽象数组类常用函数的实现(151)93数组类鲁番,。着·。着15493数组类的定义(154)932数组类常用函数的实现…………(155)94一元多项式加法····.··.;··.········.···“·······(160习题(164)第十章串···;····165101串的概念(165)10.1.1串的定义(165)1012串的基本术语(165)10.13串的存储表示和实现1661014串的木运算(166)102字符串类···……(1671021字符串类定义(167)1022字符串类中常用成员函数的实现l68习题(179)第十一章堆栈…(18111堆栈的概念及其运算(181)1.11堆栈的定义(18111.12堆栈的有关运算(181)12抽象栈类带鲁(182)113顺序栈(18313顺序栈的定义………(183)1132顺序栈类的定义…(1831133顺序栈类中典型成员函数的实现(1841134多栈共享空间问题(187)14链式栈…(189)1141链式栈的定义189142式栈类的定义(190)1143链式栈中典型成员函数的实现…(191)15堆栈的应用举例(195)1151数制转换……(195)152一个趣味游戏——迷宫问题…………(196)习题(201)第十二章队列鲁鲁(202)121队列的定义及其运算(202)1211队列的定义………………………(202)12.12队列的有关运算(202)122抽象队列类………………………(202)6