华信教育资源网
数据结构与算法分析新视角
作   译   者:周幸妮等 出 版 日 期:2016-03-01
出   版   社:电子工业出版社 维   护   人:窦昊 
书   代   号:G0280840 I S B N:9787121280849

图书简介:

数据结构是高等学校计算机及其相关专业的核心课程,是计算机程序设计的基础。本书按照“像外行一样思考,像专家一样实践”的解决问题的思维方法,列举大量实际或工程案例,从具体问题中引出抽象概念,运用类比、图形化描述等各种方式,对经典数据结构内容做深入浅出的介绍。在介绍数据结构和算法的基本概念和算法分析方法的基础之上,从软件开发的角度,通过应用背景或知识背景介绍、数据分析、函数设计、算法设计、测试调试等环节,分别对顺序表、链表、栈、队列、串、数组、树、图等基本类型的数据结构进行了分析和讨论;介绍数据的典型操作方法,如数据排序方法和查找方法;介绍常见的如递归法、分治法、动态规划、贪心法等经典算法。
定价 69.0
您的专属联系人更多
关注 评论(0) 分享
配套资源 图书内容 样章/电子教材 图书评价
  • 配 套 资 源

    本书资源

    会员上传本书资源

  • 图 书 内 容

    内容简介

    数据结构是高等学校计算机及其相关专业的核心课程,是计算机程序设计的基础。本书按照“像外行一样思考,像专家一样实践”的解决问题的思维方法,列举大量实际或工程案例,从具体问题中引出抽象概念,运用类比、图形化描述等各种方式,对经典数据结构内容做深入浅出的介绍。在介绍数据结构和算法的基本概念和算法分析方法的基础之上,从软件开发的角度,通过应用背景或知识背景介绍、数据分析、函数设计、算法设计、测试调试等环节,分别对顺序表、链表、栈、队列、串、数组、树、图等基本类型的数据结构进行了分析和讨论;介绍数据的典型操作方法,如数据排序方法和查找方法;介绍常见的如递归法、分治法、动态规划、贪心法等经典算法。

    图书详情

    ISBN:9787121280849
    开 本:16开
    页 数:536
    字 数:858.0

    本书目录

    第1章  绪论	1
    1.1  从编程说起	1
    1.2  程序要处理的数据	5
    1.3  数据结构的引入	11
    1.4  数据结构的基本概念	13
    1.4.1  数据结构基本术语	13
    1.4.2  数据结构的三个要素	13
    1.5  如何设计算法	16
    1.5.1  算法的定义及表示方法	16
    1.5.2  算法设计与函数设计的关系	17
    1.5.3  软件设计描述方法	18
    1.5.4  算法设计的一般步骤	19
    1.6  如何评价算法的优劣	21
    1.6.1  算法的设计要求	21
    1.6.2  算法效率的度量方法	22
    1.7  算法性能的事前分析方法	23
    1.7.1  问题的规模与算法的策略	23
    1.7.2  算法效率的上限与下限	25
    1.7.3  渐进的上限——算法的时间
          复杂度	28
    1.7.4  算法时间复杂度的综合讨论	29
    1.7.5  算法的空间效率分析方法	33
    1.8  算法性能综合考量	37
    1.9  本章小结	38
    习题	38
    第2章  结点逻辑关系为线性的结构——线性表	41
    2.1  从逻辑结构角度看线性表	41
    2.1.1  实际问题中的线性关系	41
    2.1.2  线性表的逻辑结构	42
    2.2  线性表的存储结构方法之一——顺序表	43
    2.2.1  顺序表的存储结构设计	43
    2.2.2  顺序表的运算	46
    2.2.3  顺序存储结构的讨论	53
    2.3  线性表的存储结构方法之二——链表	53
    2.3.1  单链表的存储	56
    2.3.2  单链表的运算	60
    2.3.3  单链表的讨论	78
    2.3.4  循环链表	78
    2.3.5  双向链表	81
    2.3.6  链表小结	86
    2.4  线性表的应用举例	87
    2.4.1  逆序输出单链表结点值	87
    2.4.2  一元多项式的相加	88
    2.5  顺序表和链表的比较	95
    2.6  本章小结	96
    习题	97
    第3章  运算受限的线性表——栈和队列	100
    3.1  栈——按照先入后出的方式管理的线性表	100
    3.1.1  栈处理模式的引入	100
    3.1.2  栈的逻辑结构	104
    3.1.3  栈的存储结构设计	106
    3.1.4  栈的操作	107
    3.1.5  各种栈结构的比较	123
    3.1.6  栈的应用举例	123
    3.2  队列——按照先入先出方式管理的线性表	132
    3.2.1  队列处理模式的引入	133
    3.2.2  队列的逻辑结构	136
    3.2.3  队列的顺序存储结构	137
    3.2.4  顺序队列的基本操作	148
    3.2.5  队列的链式存储结构	152
    3.2.6  链队列的基本操作	153
    3.2.7  各种队列结构的比较	160
    3.2.8  队列的应用举例	161
    3.3  本章小结	171
    习题	172
    第4章  内容特殊的线性表——多维数组与字符串	175
    4.1  多维数组	175
    4.1.1  数组的概念	175
    4.1.2  数组的存储结构	177
    4.2  矩阵的压缩存储	181
    4.2.1  对称矩阵的压缩存储	182
    4.2.2  三角矩阵的压缩存储	183
    4.2.3  对角矩阵的压缩存储	183
    4.2.4  稀疏矩阵的压缩存储	185
    4.3  字符串	189
    4.3.1  字符串的定义	189
    4.3.2  字符串的存储结构	190
    4.3.3  字符串的查找——模式匹配	195
    4.4  本章小结	211
    习题	213
    第5章  结点逻辑关系分层次的非线性结构——树	216
    5.1  实际问题中的树	216
    5.2  树的逻辑结构	219
    5.2.1  树的定义和基本术语	219
    5.2.2  树的操作定义	222
    5.3  树的存储结构	222
    5.3.1  树的连续存储方式	223
    5.3.2  树的链式存储方式	224
    5.4  二叉树的逻辑结构	226
    5.4.1  二叉树的概念	229
    5.4.2  二叉树的基本性质	230
    5.4.3  二叉树的操作定义	231
    5.5  二叉树的存储结构及实现	231
    5.5.1  二叉树的顺序结构	232
    5.5.2  二叉树的链式存储
          结构——二叉链表	235
    5.5.3  建立动态二叉链表	236
    5.6  二叉树结点的查找 问题——树的遍历	240
    5.6.1  树的广度优先遍历	242
    5.6.2  树的深度优先遍历	244
    5.6.3  树的遍历的应用	255
    5.7  树的应用	259
    5.7.1  表达式树	259
    5.7.2  线索二叉树	260
    5.7.3  哈夫曼树及哈夫曼编码	265
    5.8  广义表	278
    5.8.1  广义表的定义	279
    5.8.2  广义表的存储	281
    5.8.3  广义表的基本运算	287
    5.9  本章小结	293
    习题	295
    第6章  结点逻辑关系任意的非线性结构——图	299
    6.1  实际问题中的图及抽象	299
    6.2  图的逻辑结构	304
    6.2.1  图的定义和基本术语	304
    6.2.2  图的操作定义	307
    6.3  图的存储结构及实现	308
    6.3.1  图的数组表示法1—— 邻接矩阵	308
    6.3.2  图的数组表示法2—— 边集数组	310
    6.3.3  图的链表表示法1——邻接表	311
    6.3.4  图的链表表示法2—— 十字链表	316
    6.3.5  图的链表表示法3——邻接多重表	317
    6.3.6  图各种存储结构的归结比较	319
    6.4  图的基本操作	320
    6.4.1  邻接矩阵的操作	320
    6.4.2  邻接表的操作	322
    6.5  图的顶点查找问题——图的遍历	328
    6.5.1  图的广度优先遍历BFS	329
    6.5.2  图的深度优先遍历DFS	334
    6.5.3  图的遍历小结	340
    6.6  图的经典应用——图中的树问题	340
    6.6.1  生成树	342
    6.6.2  最小生成树MST	343
    6.6.3  求最小生成树算法1——Prim 算法	344
    6.6.4  求最小生成树算法2——Kruskal算法	349
    6.6.5  生成树算法小结	356
    6.7  图的经典应用——最短路径问题	357
    6.7.1  最短路径问题的引入	357
    6.7.2  单源最短路径算法——Dijkstra算法	359
    6.7.3  各顶点对间最短路径算法——Floyd算法	364
    6.7.4  最短路径问题小结	369
    6.8  图的经典应用——活动顶点与活动边的问题	370
    6.8.1  图的活动顶点排序问题的引入	370
    6.8.2  AOV网与拓扑排序——活动顶点排序问题	373
    6.8.3  AOE网与关键路径——活动边最长问题	378
    6.8.4  活动顶点与活动边问题小结	390
    6.9  本章小结	390
    习题	391
    第7章  数据的处理方法——排序技术	397
    7.1  概述	397
    7.1.1  排序的基本概念	397
    7.1.2  排序算法的分类	399
    7.2  插入排序	399
    7.2.1  直接插入排序	399
    7.2.2  希尔排序	402
    7.3  交换排序	404
    7.3.1  冒泡排序	404
    7.3.2  快速排序	406
    7.4  选择排序	409
    7.4.1  简单选择排序	410
    7.4.2  堆排序	411
    7.5  归并排序	415
    7.6  分配排序	418
    7.6.1  桶排序	418
    7.6.2  基数排序	421
    7.7  各种排序算法的比较	424
    7.8  本章小结	427
    习题	428
    第8章  数据的处理——索引与查找技术	431
    8.1  索引的基本概念	433
    8.1.1  索引的定义	433
    8.1.2  索引的逻辑特征	434
    8.1.3  索引的主要操作	435
    8.2  线性索引技术	435
    8.2.1  稠密索引	435
    8.2.2  分块索引	436
    8.2.3  多重表	437
    8.2.4  倒排表	439
    8.3  树形索引	441
    8.3.1  二叉排序树	441
    8.3.2  B树	448
    8.4  查找概述	452
    8.4.1  查找的基本概念	452
    8.4.2  查找算法的性能	453
    8.5  线性表的查找技术	453
    8.5.1  顺序查找	453
    8.5.2  有序表查找	454
    8.5.3  索引查找	459
    8.6  树表的查找技术	461
    8.6.1  二叉排序树	461
    8.6.2  B树	462
    8.6.3  在非数值有序表上的查找——字典树	462
    8.7  散列表的查找技术	464
    8.7.1  散列概述	465
    8.7.2  散列函数的设计	467
    8.7.3  处理冲突的方法	469
    8.7.4  散列查找的性能分析	473
    8.8  本章小结	474
    习题	476
    第9章  经典算法	479
    9.1  递归算法	479
    9.1.1  递归的概念及要素	479
    9.1.2  递归的应用场景	481
    9.1.3  递归的计算机实现	482
    9.1.4  递归方法特点分析	483
    9.1.5  递归算法实例	485
    9.1.6  递归小结	487
    9.2  分治算法	487
    9.2.1  分治是什么	487
    9.2.2  分治法的适用条件	488
    9.2.3  分治问题的类型	488
    9.2.4  分治法小结	490
    9.3  动态规划	491
    9.3.1  什么是动态规划	491
    9.3.2  动态规划的解题方法	493
    9.3.3  动态规划解题实例	495
    9.3.4  动态规划小结	500
    9.4  贪心算法	501
    9.4.1  贪心算法是什么	501
    9.4.2  贪心算法经典问题	502
    9.4.3  贪心算法小结	504
    9.5  回溯法	504
    9.5.1  回溯法是什么	504
    9.5.2  回溯法经典问题	507
    9.5.3  回溯法小结	509
    9.6  分支限界法	509
    9.6.1  什么是分支限界法	509
    9.6.2  分支限界法的求解思想	511
    9.6.3  分支限界法经典问题	512
    9.6.4  分支限界法小结	514
    9.7  本章小结	514
    习题	516
    附录A  数据的联系图	517
    附录B  自定义头文件的加入方法	518
    附录C  软件设计说明书格式	519
    参考文献	521
    展开

    前     言

    从新视角来看待旧问题,则需要创造性的思维——爱因斯坦
    数据结构的教与学经历
    六七年前上数据结构课时,驾轻就熟地依然按照一贯的讲法上课。上了几次课后,收到班上一位同学的E-mail,信中说:“我自己是特别热爱写程序的。一方面我很熟悉电脑,软硬件都有涉猎,所以学起来就不缺基础的相关知识(像内存、寄存器、电子电路等等这些都很熟悉);另一方面我好像很能适应,也很喜欢这种思维方式……但好像班上不少的同学对数据结构的学习理解和接受起来还是比较困难的……”
    教授数据结构的课程也有十余年了,一直以来,学生们总是认为数据结构不是一门容易学的课程,“在众多的专业课中,数据结构被很多学生认为是一门很难学习的课程。”[1]虽然我在学校读书时没有学过数据结构的课程,只是因为后来要教书,才自学的数据结构。在自学的过程中,也并没有觉着内容怎么难啊,这是怎么回事呢?
    仔细回想一下自己学习与工作的经历过程,或许就是来信的这位同学说的,是因为在学习数据结构书本知识之前,已经有了较强的编程的技能、一些数据结构实际应用的先验知识吧。比如,在研究所工作时首次参加的软件开发项目中,就有多进程、链表、队列、散列等的实际应用,虽然在学校并没有学过这些概念,而是先接触到实际项目中要处理的问题,再看到其他程序员的具体算法处理和程序实现方法,从实际的问题切入,就比较容易理解相应的数据组织形式和对应的算法,等到后来再接触到书本的理论知识,就有一种一通百通,豁然开朗的感觉。还有一个原因是在软件开发过程中逐渐熟悉并掌握了程序调试方法,对例程通过跟踪的方法,很容易弄清执行的路径和结果,对算法的设计和实现的理解也起到了事半功倍的效果。
    回头来看学生们学习的教科书,概念的介绍是传统意义上的叙述方式,抽象度很高,但从实际到抽象、从抽象到实际的过程介绍不足,即感性认识不足,抽象就难以理解接受。“现在有一个不好的倾向,就是教材或课堂过于重视抽象化的知识,忽视应用背景。数据结构的教材是这一倾向的代表。这对入门阶段的学生来讲是不适宜的,因为学生难以走进所涉及的抽象世界,最终表现为不知道在讲什么。”[2]
    再看我的学生,既没有实际软件开发的经验也没有熟练的编程调试基础,对数据结构结构没有感性认识,先接触的是那些抽象的概念,感到理解和接受困难也就可以理解了。邹恒明在《数据结构:炫动的0、1之弦》一书中指出,对于很多人来说,数据结构的概念并不难,真正的难点是:
    (1)如何实现从数据结构概念到程序实现的跨越(即如何实现一个数据结构);
    (2)如何实现从实际应用到数据结构抽象的跨越(即如何利用数据结构解决实际问题)。
    对于我来说,仅仅在学校学了一点点程序设计语言(记得所有上机时间加起来不超过20小时),没有任何数据结构的知识,刚出校门就参与了历时三年多后来获得国家科技进步三等奖的大型软件开发工作,以及后续多个电信用户单位的实际软件安装、应用调试和维护工作,亲历了实现了上述两个“跨越”的最实际生动的案例。虽然项目的开发过程非常艰苦,有在用户单位调试现场连续大半年的天天加班到深夜、第二天依然要正点到机房的超负荷工作,有通宵的跟踪调试,有24小时在线系统内存泄漏的巨大压力,有上线后双机备份系统同时崩溃争分夺秒找bug的惊心动魄,等等。应该说自己是很幸运的,虽然在学校仅仅学习了一点点编程的概念,但在工作中根据需要自学和向同事学习了很多新知识、经验和技巧,这样的实践磨练,对后来的程序设计类课程的理解和教授,是非常有益的。
    学习数据结构困难的症结所在
    回想与总结起来,之所以要有上述两个鸿沟要“跨越”,也是由于学校的传统教科书教法和实际的应用要求脱节造成的。
    弗里德里希?威廉?尼采曾写道:“人们无法理解他没有经历过的事情。”[3]换句话来说,我们只接受与过去早已理解的事物相关的信息。这是一种比较学习的过程,在这个过程中,大脑要寻找每条信息之间的联系,借助以往经验来理解新事物[4]。
    “欧拉认为,如果不能把解决数学问题背后的思维过程教给学生的话,数学教学就是没有意义的。现代计算机实质上的发明者莱布尼兹也说过:在我看来,没有什么能比探索发明的源头还要重要,它远比发明本身更重要。从小到大,我们看过的数学书几乎无一不是欧几里德式的:从定义到定理,再到推论。这样的书完全而彻底地扭曲了数学发现的真实过程。目前几乎所有的算法书的讲解方式也都是欧几里德式的,每一个推导步骤都是精准制导直接面向数据结构目标的,实际上,这完全把人类大脑创造发明的步骤给反过来了。对读者来说,这就等于直接告诉你答案和做法了,然后让你去验证这个答案和做法是可行或成立的,而关于答案和做法到底是怎么来的,从问题到答案之间经历了怎样的思维过程,却鲜有书能够很好地阐释。对于这类知识讲述(欧几里德方式)方式的批判,西方(尤其是在数学领域)早就有了。”[5]
    传统数据结构教科书的一般模式都是给出问题,然后直接给出算法,而实际上要用计算机解决问题,必须要考虑的处理步骤有:如何分析问题中的已知信息,如何提炼数据及数据间的联系(数据的逻辑结构),如何选用合适的存储方式(数据的存储结构)将逻辑结构存到计算机中,然后在存储结构之上按照自顶向下逐步细化的方法给出算法,这才是真正解决实际问题的思维方法和步骤,也是软件开发中实际采用的方法。传统教科书的问题在于没有一个思维过程的引导与分析,致使概念论述、实现细节有余,设计实现过程描述不足,让学生看到的只是一个个问题具体的详解,而把握不住算法设计的总方法和原则。
    本书尝试从学以致用的角度,注意给出问题或算法的知识背景或应用背景,增加一些在实际软件开发中的算法应用背景或实例;强调算法的分析方法、设计思路、给出重要算法的测试及调试分析,弥补上述传统教科书中的不足。教学生以“软件开发的方法”处理问题,使学生容易理解并掌握它,在实际的软件开发过程中能灵活地选择适当的逻辑结构、存储结构及相应的算法,设计性能优、效率高、可读性强、易维护的程序,达到数据结构课程最终的目的。
    程序设计与数据结构的关系
    我们在学习数据结构知识之前要有程序设计的基础,那么我们先来看看与编程相关的问题。
    什么是编程?编程不仅仅是对语法的掌握,还涉及下面的诸多方面:
    (1)程序的解题思路——算法是基本运算及规定的运算顺序所构成的完整的解题步骤,是程序的灵魂,算法的优劣直接影响程序的效率。本书的算法描述方法见稍后的说明。
    (2)程序的运行速度——程序运行的速度受很多因素的影响。用户对程序的运行速度往往是有要求的,如实时响应系统。
    (3)程序的运行空间——代码运行需要相应的内存空间及相关运行环境。在有些应用场合,对程序占用空间是有限制的,如嵌入式系统。
    (4)代码规范——代码要按照一定的规范格式书写,以保证代码的一致性,便于交流和维护。
    (5)程序的结构—— 一个功能复杂的程序由多个功能相对独立的模块组成。模块内高内聚,模块间低耦合,是判断程序结构是否合理的标准。
    (6)模块接口——模块间的信息交流通过接口完成,模块间信息传递参数的设置应该合理有效。
    (7)程序的测试与调试——要有精心设计的测试样例来测试程序是否正确。调试是高效率完成软件产品的有效方法。一个程序高手,也是调试专家,调试的经验方法多数都是实践中得到的。
    我们在学习数据结构知识之前要有程序设计的基础,那么数据结构与程序设计间的关系是怎样的呢?应该说数据结构是编写规模庞大、逻辑复杂的更高级程序所需的基础。表0.1给出了程序设计与高级编程的特点。
    表0.1  程序设计与高级编程
    	涉及课程	主要内容	课程目标
    结构化程序
    设计	程序设计基础类课程	语言语法形式、语句使用规则
    模块设计思想	编写简单程序
    解决简单问题
    高级编程技术	数据结构	数据的抽象思维方法	编写规模庞大、
    逻辑复杂的程序
    		算法的规范声明、算法的性能分析、算法的性能评价	
    	软件工程	部件(模块)设计思想、软件工程思想	
    	……		
    程序设计的首要问题是模块划分及相关问题,另一个重要方面,是把要解决问题的信息转换成计算机能认识并接收的数据,这一转换过程就是数据的抽象过程。要处理规模庞大的复杂问题,必须掌握数据的抽象思维方法,同时还要熟练掌握算法的规范声明、算法的性能分析、算法的性能评价等诸多技能。
    数据结构与其他课程的关系
    作为一门重要的专业核心必修课程,“数据结构与算法”课程既是对以往课程的深入和扩展,也为深入学习其他专业课程打下基础。课程中排序问题算法以及基本的树、图等数据结构,是计算机科学的基本功。B+树、散列(Hash)等高级数据结构,也是数据库、操作系统、编译原理、计算机网络等重要专业课程的基础。本课程在计算机学科中与其他课程的关系如图0.1所示。
     
    图0.1 “数据结构与算法”课程在计算机学科中的重要地位
    数据结构的重要性
    商用程序员肖舸在他的博客中写道:“这么多年,我做过游戏、通信、工业控制、教育、VoIP、服务器集群等各个方向的项目,不可谓不宽。
    但是我知道的是,其实我都是在用一种方法写程序。那就是从最底层的数据结构和算法开始做起,用最基本的C、C++语言开发。用来用去,还是那么几个数据结构,队列、堆栈,等等。
    这好比武侠小说里面的内功,内力修好了,学招式,非常容易。但如果没有内力,练再好的招式,见到高手就软了。一力破十慧,就是这个道理。在绝对的实力面前,任何花招都是没有用的。”[6]
    对清华大学计算机系历届毕业生和部分研究生追踪调查显示,几乎所有的学生都认为“数据结构”是他们在学校里学过的最有用的课程之一;数据结构是国内外许多软件开发机构要求考核的基本课程之一;IT业公司面试或笔试考核的绝大部分内容是数据结构或算法;数据结构也是计算机科学与技术、软件工程等专业研究生考试必考科目。
    数据结构会过时吗
    电子计算机自20世纪四十年代诞生以来硬件上不断更新换代,软件也是同步发展的,作为软件的一个分支程序设计语言也从机器语言发展到了第四代,但无论软件如何发展,无论开发工具如何进步,只要我们的计算机还是基于冯诺依曼体系,数据结构和算法仍然是程序的核心,永远不会被淘汰。
    学习数据结构和算法并不仅仅要求我们学会如何使用和实现某种数据结构,更重要的是学会分析解决问题的思想和方法。
    本书关于算法与程序实现增加的内容
    在基础数据结构——线性表与运算受限的线性表栈与队列章节中,特别增加了下列内容。
    1.增加测试样例的设计
    从程序健壮性的角度出发,测试样例的设计是开始程序设计就应该考虑的一个重要内容。一般的程序设计与数据结构教科书很少考虑测试样例问题,本书在最初基本的算法设计中,给出了基础程序的测试样例设计,也是让学习者以专业的方法学习程序设计,养成良好的设计习惯。
    2.增加函数结构的设计
    对初学者而言,在学习数据结构时,程序设计语言基础并不扎实,特别是函数结构的设计不熟练。根据给定的功能、输入输出信息,在调用与被调用的函数关系中,信息是怎样传递的,往往存在多种可能的选择,该怎样确定合适的形参类型、函数类型,初学者经常会无所适从,从而造成编程困难。根据这种情况,本书特别给出了典型数据结构运算的多种方案实现,在同一问题不同函数结构设计的比较中,让读者发现各种信息传递的方式和特点,巩固和熟练编程知识和技巧,达到理论与实践的统一。
    函数结构样例分别见表0.2和表0.3。
    表0.2  函数结构样例1
    功能描述	输入	输出
    顺序表中查找给定的值
    LocateElem_Sq	顺序表地址SequenList *	正常:下标值int
    	结点值 ElemType	异常:?1
    函数名	形参	函数类型
    表0.3  函数结构样例2
    功能描述	输入	输出
    顺序表中取给定下标的元素值
    GetElem_Sq	顺序表地址SequenList *	返回	正常:1
    	下标int		异常:0
    	(结点值 ElemType)	结点值ElemType
    函数名	形参	函数类型
    说明:当函数中的输入和输出项中的内容一样时,表示函数的返回信息是通过形参的址传递方式,而非return方式。如表0.3中函数结构样例2中,输入输出都有“结点值ElemType”项,表示是形参采用“地址传递”方式。
    3.增加重要程序的调试
    程序设计的过程也是一个测试与调试的过程,程序的编与调是密不可分的。对于初学者而言,若调试不熟练,容易丧失继续学习的信心。根据多年的教学经验,若有程序调试演示,则相关程序比较容易掌握,特别是在学习链表等内容时,光是解释数据结构、结点联系,学生总觉得抽象难懂,若通过演示调试,观察各结点间的联系如何动态建立、消除等,则生动直观,一目了然。由于调试过程步骤较多,学生看过了明白了,但要再回想并模拟跟踪过程,则是不容易的事情,所以本书把一些重点例子的程序跟踪过程记录下来,以便学生学习。本书所有的源码均以C语言编制,并在VS IDE环境下通过调试和测试。
    4.算法描述方法
    算法描述按照下面的顺序给出(主要用于编程最基础的线性表部分),内容详见1.5.3节。
    1)测试用例设计。
    2)数据结构描述。
    3)函数结构设计。
    4)算法伪代码描述。
    5)程序实现。
    6)算法效率分析:
    注:#define TRUE 1
        #define FALSE 0
    数据结构课程简介
    用计算机解决实际问题,首先要做的事情就是要把涉及问题的相关信息存储到计算机中,也就是需要把问题的信息表示为计算机可接收的数据形式,然后根据问题处理功能的要求,对存储到计算机中的数据进行处理。归结为一句话,可以这样说,用计算机解题首先要用合理的结构表示数据,然后才能根据相应的算法处理数据,而数据表示和数据处理正是数据结构学科要研究的内容。
    “数据结构”主要介绍如何合理地组织数据、有效地存储和处理数据,正确地设计算法以及对算法的分析和评价。
    通过本课程的学习,学生能深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法,学会分析数据对象特征,掌握数据组织方法和计算机的表示方法,以便在实际的软件开发过程中灵活的选择适当的逻辑结构、存储结构及相应的算法,设计性能优、效率高、可读性强、易维护的程序,解决实际问题。
    数据结构是实践性很强的一门课程,本课程的特色就是注重实践活动。通过大量上机实验,能加深对课程理论知识的理解,增强学习的兴趣,提高计算计算法思维逻辑能力,为以后的学习和工作打下坚实的基础。
    本课程的基本要求如下:
    ?  了解数据结构及其分类、数据结构与算法的密切关系。
    ?  熟悉各种基本数据结构及其操作,学会根据实际问题要求来选择数据结构。
    ?  掌握设计算法的步骤和算法分析方法。
    ?  掌握数据结构在排序和查找等常用算法中的应用。
    ?  初步掌握索引技术。
    ?  了解经典算法。
    本书的组织结构
    本书共分9章。第1章介绍数据结构和算法的基本概念和算法分析方法。第2章至第6章从软件开发的角度,通过应用背景或知识背景介绍、数据分析、函数设计、算法设计、调试等环节,分别对顺序表、链表、栈、队列、串、数组、树、图等基本类型的数据结构进行分析和讨论。第7章排序技术介绍常见的数据排序方法,第8章索引查找技术介绍数据的查找方法,第7、8章的内容是对数据的典型操作方法的介绍。第9章经典算法,介绍一些常见的如递归、分治法、动态规划、贪心法等经典算法。
    前言、第1章至第6章由周幸妮老师完成;第7、9章由任智源老师完成;第8章由马彦卓老师完成;樊凯老师提供了通信等方面的部分专业应用案例;周幸妮对全书进行了统稿。
    书中设有“思考与讨论”、“知识ABC”等栏目。在“思考与讨论”栏目中提出问题,引起读者思考,并对提出的问题进行探讨,帮助读者加深对相关概念等的理解,以期活跃思路扩展思维。“知识ABC”栏目主要介绍相应概念的知识、知识背景、算法的发明背景或故事等,以扩大读者的知识面和了解数据结构的应用背景等。有些知识可能专业性比较强,对此可以“不求甚解”,大致了解即可,感兴趣了可以再去查相关资料。
    致谢
    本书的写作动力,依然是源自于我的学生,起因是09级教改班同学的提议,认为我的授课方式、思路都不错,写出来会别具一格,让大家学习这个课程时能更好理解一些,这部分内容在我的《C语言程序设计新视角》一书中有所提及。
    我的动力亦源于父亲的鼓励、家人的支持。感谢铁满霞教授、陈慧婵教授的指点;感谢屈宇澄同学自始而至终的支持和帮助;感谢孙蒙、丁煜、孙舒、孙亚萍、张柯、杨恒杰、吴伟基、黄超、张平等同学的热心帮助;感谢通信工程学院13级教改班、14级卓越班,空间科学与技术学院13级实验班同学们对本书初稿讲义提出的各种有益的意见和建议。
    所有和同学们、同事们的讨论都让人受益匪浅,这些讨论或开拓了视野,或引起了深入思考,所有的一切都是一种成长与完善的历程。
    感谢曾经给予我很多帮助、一起辛苦工作的同事们;感谢我有趣的人生经历;感谢我可爱的学生们;感谢所有关心和帮助我的人们。
    感谢Bandari的April,每天伊始,美妙的乐曲让人在纯净、安定、温暖的情绪中开始一天的写作。
    感恩一切。
    
    周幸妮         
    xnzhou@xidian.edu.cm  
    2015年春于长安
    展开

    作者简介

    本书暂无作者简介
  • 样 章 试 读
  • 图 书 评 价 我要评论
华信教育资源网