C-C++数据结构与算法速学速用大辞典(txt+pdf+epub+mobi电子书下载)

作者:陈锐 华庆一等

出版社:中国铁道出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

C-C++数据结构与算法速学速用大辞典

C-C++数据结构与算法速学速用大辞典试读:

前言

Foreword

终于完成本书,稍微可以放松下了。

每次写书实际花费的时间远远超过计划的时间,虽然花费很多时间去修改、完善,但对于书中文字的表述、例子的选取、讲解及算法的实现总感觉还不够满意,也许这不是一次能达到的,只能期待下一次改版再做修订。

在编写本书的过程中,也是我重新学习的过程,特别是在调试程序上花费了不少时间,但是我感觉每一次都有很大收获,因为我在调试程序的过程中发现了一些错误,这些错误之前我并没有遇到过,并且对算法有了更深一步的理解。

在写完《最新C/C++函数与算法速查速用大辞典》(书号为978-7-113-20740-3)之后,觉得似乎还不够一个体系,应该有一个数据结构与算法方面的类似辞典或手册类的书,于是我就与出版社编辑商量这个想法,决定完成本书。

最初《C/C++函数与算法速查手册》自2012年1月首次出版以来,得到众多读者的喜欢和好评,有来自各个院校的教师和学生,还有从事软件开发的程序员,更有一些热心的读者通过电子邮件或QQ等方式给其提出了宝贵意见,指出了书中的不足之处,期待以后进行改进。有这么多热心读者的关注,我感到非常开心,在此向所有关注的朋友们说声谢谢!

为满足读者朋友的需求,本书不仅讲解了数据结构和算法的基础知识,还融合了大量的数据结构和算法方面的典型例子,这些算法都经过精心调试运行,保证算法的正确性。调试程序是一件花费时间的事情,但是只有自己亲自动手调试,才能深刻理解算法思想,发现错误和不足,在调试程序的过程中,自身水平也得到了提高。因此,希望大家能多动手,亲自上机调试程序,哪怕是把程序敲一遍,也会比不动手效果好。

本书由西北大学的陈锐、华庆一、耿国华、姬翔和西安科技大学的李洪安编著,南阳理工学院的赵娟、辽源职业技术学院的王慧博,西北大学的吴昊参与编著。

由于时间仓促,加上本人水平有限,书中一定会存在一些不足和错误,希望读者朋友通过邮箱nwuchenrui@126.com、huaqy@nwu.edu.cn与我们联系,也可以通过QQ群(515119018)沟通交流。祝愿各位在阅读本书的过程中有一个愉快的旅程。

◎本书内容

本书涵盖数据结构和算法等内容,是一本计算机专业人士的案头必备工具书,适合从事C/C++的程序员和科研人员作为词典进行查阅,也可以作为数据结构和算法初学者的参考用书。

本书分数据结构和算法两部分,其中数据结构涵盖数据线性表、栈、队列、串、数组和广义表、树、图等内容,算法部分涵盖排序、查找、迭代、递推、枚举、递归、贪心、分治、实用算法等内容。

本书选取的案例具有代表性、趣味性和实用性。数据结构除了注重基础知识的讲解,给出了基本运算的实现,案例大部分来自著名高校的考研题目,代表性强,内容和案例结合性强,注重理论与实践相结合。算法部分不少案例极具趣味性,例如,“求n个数中的最大者”、“和式分解”、“大牛生小牛问题”巧妙利用递归来实现。在算法案例的选取上,还注重实用性,尽量将案例与实际工作生活结合,例如,加油站问题、找零钱问题,大小写金额转换。本书案例丰富,以上特点不仅涵盖了数据结构和算法的各个知识点,还能增加学习的积极性和趣味性。

本书最后提供了一个关于如何用VC++6.0调试程序的案例剖析,希望对读者有所帮助。

◎本书特点(1)结构安排合理。概念讲解通俗易懂,内容安排和案例选取都是先易后难,循序渐进,注重学习知识的连贯性。(2)注重基础知识的讲解。在数据结构部分首先是对基础知识和概念的介绍,然后给出相应的基本运算算法实现,最后是提供典型案例和考研试题的讲解及算法实现。(3)涵盖个人学习经验总结。在讲解知识点、分析案例及调试程序时,加入了作者自己学习过程中的经验总结,指出了初学者常犯的错误,避免读者少走弯路。(4)案例很多都来自全国著名高校(清华大学、哈尔滨工业大学、西北大学、华中科技大学、西安电子科技大学、北京航空航天大学、上海大学)的考研题目,并给出了完整的算法实现。(5)提供完整代码实现,所有代码均在VC++6.0以上调试通过。

◎如何使用本书

本书中涵盖大量关于数据结构和算法中的线性表、栈、队列、串、数组和广义表、树、图等基本运算和典型算法实现代码,读者朋友们在使用本书的过程中,若需要用到哪些功能,可以直接调用,不需要另外重新编写代码。但是这些已经实现的代码资源意在帮助大家学习和理解,要想真正学好数据结构与算法,需要大家尽量自己去实现,或者至少要阅读理解每段代码的功能。

本书有基本概念和相关知识点的讲解,读者朋友们可以将这本书作为一本教材从头到尾阅读;本书涵盖案例丰富、典型,有代表性,也可以作为一本工具书,需要时查阅。

本书中的算法都是使用C/C++实现,但是并不涉及面向对象知识,仅仅是考虑到输入和输出书写方便,有的代码只是用cin代替了scanf函数,cout代替了printf函数。

◎如何学好数据结构与算法

经常有读者问我在看关于数据结构部分时,为什么在线性表或栈的初始化部分会用二级指针,而在其他基本运算用一级指针,我想也有不少朋友会有这个疑惑,这说明有的读者还是比较细心的,但是也表明大家对指针的用法还是不十分清楚,这里用二级指针的目的是为了返回指针的值,所以要用二级指针。

另外,需要读者注意:在学习数据结构和算法之前,读者最好熟练掌握C语言,起码应该熟悉C语言的语法,在学习数据结构和算法的过程中也可以提高C语言水平。

发现问题是好事情,我们在学习的过程中,要不断地尝试,去实践,书上也有错误,有疑惑就要去验证,俗话说“尽信书则不如无书”,到底是书上的对还是你的判断正确,只有自己去上机调试,才知道到底哪个正确。

在看书的过程中,不要做空头理论家,只看不动手。对难以理解的算法,特别是递归、树和图的算法,可以跟着程序在纸上画一遍,不要怕麻烦,觉得这是浪费时间。在学习数据结构与算法的过程中,不能偷懒,除了理解算法思想外,还要抽时间尽量在计算机上运行,因为每个算法最终是要实现的,需要在计算机上运行起来的。学数据结构与算法的目的有两个:一是学会算法设计,这属于理论思想层次;二是要用C/C++/Java等语言实现,正确运行出算法结果。你设计的算法正确与否,不是靠想象,是需要经过编译器运行检验的。任何一个人,即使非常善于设计算法,他也不能保证写出的程序不需要修改直接在计算机上运行。因此,编写出算法然后在计算机上运行是非常重要的,只有这样才能真正学好数据结构和算法。

◎关于开发

在写作本书和之前学习数据结构与算法的过程中,我也与大家一样,会经常遇到这样或那样的困惑,只是现在越来越少了,这是因为接触多了,每遇到一个问题,就想办法试图去解决它,现在想来,其实就C语言、数据结构和算法来说,没有那么复杂。记得当时写本书第四章时,需要通过键盘接受输入两个字符串,但是直接使用C提供的gets函数或C++的cin输入流,都会遇到很莫名其妙的问题,就是当输入一个字符串完毕后回车,就会出现跳过第二个输入提示,有时是因为一个字符串中包含了空格,有时是因为连续用几个gets函数的原因,导致直接使用gets函数或cin都不行,可以尝试使用最原始的getchar函数,把它与while语句结合起来使用,即可接受一个字符串,这个字符串也可以包含空格,假设以回车符作为结束,代码如下:

这样就巧妙地解决了上面的问题。

本书中,特别是在数据结构部分,我们把基本运算单独放在一个.h文件中,以便对代码进行重用,每一章的算法调用基本比较模式化,经常会使用一些比如输入或输出的功能,这时即可把这些比较常用的功能写成一个函数,避免重复编码,这就是软件工程的思想,今后大家开发程序也要养成这个习惯。

◎程序调试

在写作本书的过程中,不断有读者让我帮忙看程序中哪里出了错误,我在调试时也会遇到这样或那样的错误,我想有不少接触C语言不久的朋友们也有类似的困惑:如何能快速找出程序的错误位置和原因,以便让程序正确运行。针对程序调试问题,我觉得首先选择一个比较合适的开发工具,比如VC++就是一个很成熟的开发工具,对于语法错误,编译器会直接定位错误行,并给出相应的错误提示。对于逻辑错误和运行时错误,需要对可能出问题的代码段设置断点,跟踪查看变量在程序运行过程中的变化情况,针对输入的数据进行分析,这样就能很快找出问题的所在。

虽然本书为所有的案例提供了完整的代码,但是还是建议读者能亲自在计算机上敲代码,在敲代码的过程中去体会算法设计思想,也许会不小心输入错误、也许会为一个小小错误苦恼半天,经过多次检查和艰难调试,终于找到错误的原因并且解决,直到程序正常运行。这个过程也是每个成功者必经之路,只有经历了痛苦、挣扎、喜悦的反复过程,你才可能成为一名经验丰富的C/C++程序员或合格的计算机教师。计算机是一门科学,也是一门技术,算法思想虽然很重要,但再伟大的算法也需要去验证,只有验证了才知道是否可行,在验证的过程中才能发现问题,这就像一个伟大的数学家提出一个定理或猜想,也需要去证明这个定理的正确性或验证猜想的正确性。

如果大家看完本书,感觉你有所收获,那我这么长时间的辛苦也有了回报,也达到写作本书的目的。

◎应该感谢的人

首先,应该感谢我的导师华庆一教授和张蕾教授。在华教授的引领下,我迈入了人机交互的大门,华教授不仅在科研上给予我耐心的指导,还在生活上给予我无微不至的关怀。华教授对科研工作的严谨态度深深地感染了我,他深厚的计算机理论知识和娴熟的技术水平折服了我,他对科研事业孜孜不倦的精神影响和鼓舞了我,促使我不敢懈怠,对待任何事情不能马虎,也让我的学习能力和认识水平有了很大提高,为本书的编写奠定了良好的理论与技术基础。

其次,还应该感谢耿国华教授,耿教授虽是国家级教学名师,但是对待学生一向平易近人,没有任何架子,她对青年人的发展给予了许多无私的帮助和支持,她在数据结构和算法领域有很深的造诣,她对我在算法和数据结构方面的学习给予了很大的启发。

最后,特别要感谢我的家人,他们是我事业和学习上的坚强后盾,正是他们的默默付出与鼓励,我才能顺利完成本书。

在本书出版的过程中,许多热心的读者提出了改进意见,特别是puppypyb(网名)很认真地提供具体的修改意见,感谢中国科学院大学的胡英鹏、中国科学技术大学的王启、华中科技大学的杨梨花、西安电子科技大学的杜坚、西安交通大学的郝昊天、华东师范大学的牛颖楠、南京航空航天大学的韩琦文、南京理工大学的邓裕彬、北京工业大学的潘姝妤、电子科技大学的丁亮、上海海事大学的左伟康、福州大学的李川、湘潭大学的王乾、天津职业技术师范大学的董春妹、桂林电子科技大学的曹礼、郑州大学的张杨,张冬冬、成都理工大学的张良、西华师范大学的刘富腾、衡水学院的杨帅、重庆电子工程职业学院的冯博、湖南女子学院的李奇、湖北汽车工业学院的李兴海、黄淮学院的于景波、九江学院的樊美林、信阳师范学院的周亚林、衡水学院的杨帅、云南大学的袁宏磊、广东技术师范学院欧阳镇、江苏省扬州中学的张佑杰、浙江工业大学的陈文邦、电子科技大学的吕鑫垚、北京邮电大学世纪学院的昂超、兴义民族师范学院的鲜一峰、赶集网的康钦谋、济南趣维网络科技有限公司的刘晓倩、中国航空计算研究所的王泉、中兴通讯公司的杨柯、华为科技有限公司的卢春俊、云南昆船设计研究院的夏翔,还有很多网友也提出了宝贵建议,这里不再一一列举。

陈锐2016年5月Chapter 1线性表

线性表是一种最基本、最常用的数据结构,表中的元素呈线性关系。线性表、栈、队列和串都属于线性结构,线性结构的特点是:除了第一个元素没有直接前驱元素,最后一个没有直接后继元素外,其他元素都有唯一的前驱元素和唯一的后继元素。1-1顺序表示的线性表——顺序表【定义】

线性表是由n个类型相同的数据元素组成的有限序列,记为(a ,a ,…,a ,a ,a ,…,a )。线性表的数据元素存在着12i-1ii+1n序偶关系,即数据元素之间具有一定的次序。在线性表中,数据元素a 位于a 的前面,a 又在a 的前面,我们把a 称为a 的直接前i-1iii+1i-1i驱元素,a 称为a 的直接前驱元素。a 称为a 的直接后继元素,ii+1ii-1a 称为a 的直接后继元素。i+1i

线性表的逻辑结构如图1.1所示。

图1.1 线性表的逻辑结构

线性表按照存储方式可以分为顺序存储和链式存储。线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。

线性表中第i个元素的存储位置与第一个元素a 的存储位置满足1以下关系:

LOC(a )=LOC(a )+(i-1)*mi1

其中,第一个元素的位置LOC(a )称为起始地址或基地址。1

线性表的这种机内表示称为线性表的顺序存储结构或顺序映像,通常将这种方法存储的线性表称为顺序表。【特点】

顺序表具有以下特征:逻辑上相邻的元素,在物理上也是相邻的。只要确定了第一个元素的起始位置,线性表中的任一元素都可以随机存取,因此,线性表的顺序存储结构是一种随机存取的存储结构。【存储结构】

其中,DataType表示数据元素类型,list用于存储线性表中的数据元素,length用来表示线性表中数据元素的个数,SeqList是结构体类型名。

如果要定义一个顺序表,则代码如下:

SeqList L;

如果要定义一个指向顺序表的指针,则代码如下:

SeqList *L;【基本运算】(1)初始化线性表。(2)判断线性表是否为空。(3)按照序号查找。(4)按内容查找。(5)插入操作。要在顺序表中的第i个位置上插入元素e,首先将第i个位置以后的元素依次向后移动1个位置,其次把元素e插入第i个位置。

例如,要在顺序表{3,15,49,20,23,44,18,36}的第5个元素之前插入一个元素22,需要将序号为8,7,6,5的元素依次向后移动一个位置,然后在第5号位置插入元素22,顺序表就变成{3,15,49,20,22,23,44,18,36},如图1.2所示。

图1.2 在顺序表中插入元素22的过程(6)删除第i个元素。在进行删除操作时,先判断顺序表是否为空,如果不空,接着判断序号是否合法,如果不空且合法,则将要删除的元素赋给e,并把该元素删除,将表长减1。

例如,要删除顺序表{3,15,49,20,22,23,44,18,36}的第4个元素,需要将序号为5,6,7,8,9的元素依次向前移动一个位置,这样就删除了第4个元素,最后将表长减1,如图1.3所示。

图1.3 在顺序表中删除元素20的过程(7)求线性表的长度。(8)清空顺序表。

将上述顺序表存储结构的定义及基本运算保存在SeqList.h文件中,在使用时通过#include"SeqList.h"引用这些基本运算。001 合并两个线性表中的元素

顺序表A和顺序表B的元素都是非递减排列,利用顺序表的基本运算,将它们合并成一个顺序表C,要求C也是非递减排列。例如,A=(8,17,17,25,29),B=(3,9,21,21,26,57),则C=(3,8,9,17,17,21,21,25,26,29,57)。【分析】

顺序表C是一个空表,首先取出顺序表A和B中元素,并将这两个元素比较,如果A中的元素m 大于B中的元素n ,则将B中的元素n 11 插入C中,继续取出B中下一个元素n 与A中元素m 比较。如果A121中的元素m 小于或等于B中的元素n ,则将A中的元素m 插入C中,111继续取出A中下一个元素m 与B中元素n 比较。依次类推比较下去,21直到一个表中元素比较完毕,将另一个表中剩余元素插入C中。

第1章\范例01-01.c

运行结果(见图1.4)

图1.4 算法运行效果【说明】

在程序中,需要调用头文件“SeqList.h”时,因为其中包含有数据类型DataType和表示顺序表长度的宏名ListSize,所以在包含命令#include"SeqList.h"前首先需要给宏名赋值、进行类型定义,其语句次序如下:002 fgetc函数和getc函数

假设线性表LA和LB分别表示两个集合A和B,利用线性表的基本运算,实现新的集合A=A∪B,即扩大线性表LA,将存在于线性表B中且不存在于A中的元素插入A中。【分析】

依次从线性表LB中取出每个数据元素,并将该元素依次与线性表LA中的元素进行比较,可以调用按照内容查找基本操作LocateElem(SeqList L,DataType e)完成以上比较操作,如果LA中不存在该元素,则将该元素插入到LA中。

第1章\范例01-02.c

运行结果(见图1.5)

图1.5 算法运行效果003 求两个线性表的差集

利用线性表的基本运算,实现如果在线性表A中出现的元素,在线性表B中也出现,则将A中该元素删除。【分析】

其实这是求两个表的差集,即A-B。依次检查线性表B中的每一个元素,如果在线性表A中也出现,则在A中删除该元素。

第1章\范例01-03.c

试读结束[说明:试读内容隐藏了图片]

下载完整电子书

若在网站上没有找合适的书籍,可联系网站客服获取,各类电子版图书资料皆有。

客服微信:xzh432

登入/注册
卧槽~你还有脸回来
没有账号? 忘记密码?