新書推薦：
《
送你一匹马（“我不求深刻，只求简单。”看三毛如何拒绝内耗，为自己而活）
》
售價：NT$
295.0
《
秦汉史讲义
》
售價：NT$
690.0
《
万千心理·我的精神分析之道：复杂的俄狄浦斯及其他议题
》
售價：NT$
475.0
《
荷马：伊利亚特（英文）-西方人文经典影印21
》
售價：NT$
490.0
《
我的心理医生是只猫
》
售價：NT$
225.0
《
股权控制战略：如何实现公司控制和有效激励（第2版）
》
售價：NT$
449.0
《
汉译名著·哲学经典十种
》
售價：NT$
3460.0
《
成吉思汗传：看历代帝王将相谋略 修炼安身成事之根本
》
售價：NT$
280.0
|
| 編輯推薦： |
|
数据结构与算法是软件开发技术的一门重要的专业基础课程。课程主要讨论现实世界中数据之间的各种逻辑结构、在计算机中的存储结构以及各种算法的设计问题。本书讨论的内容包括：线性表、堆栈、队列、串、数组、树、图、查找、排序。其中，线性表、堆栈、队列、串、数组属于线性结构，树和图是非线性结构，查找和排序是两个应用广泛的算法设计问题。
|
| 內容簡介： |
本书系统全面地讲解了数据结构与算法的主要内容，包括线性表、栈和队列、字符串、数组与矩阵、树、图、查找以及排序。对于每一种类型的数据结构，都详细阐述了基本概念、各种不同的存储结构和不同存储结构上一些主要操作的算法，并给出完整的C语言代码和Java代码，有助于不同语言学习者的理解。C语言的指针概念虽较好地阐述了链表的结构，但目前软件设计的主流方法是面向对象思想，所以本书在附录中提供了各个算法对应的Java代码。
本书可作为应用型本科、高职高专、成人高校计算机相关专业课程的教材，也可作为各类培训、计算机从业人员和爱好者的参考用书。本书封面贴有清华大学出版社防伪标签，无标签者不得销售。
|
| 目錄：
|
第1章绪论1
1.1学习数据结构的意义1
1.1.1引言1
1.1.2数据结构研究什么2
1.2数据结构的基本概念3
1.3算法及其描述4
1.3.1算法的概念和特性4
1.3.2算法设计的要求5
1.3.3算法的分析5
1.4小结7
1.5习题7
第2章线性表9
2.1线性表的定义及运算9
2.1.1线性表的定义9
2.1.2线性表的基本运算10
2.2顺序线性表11
2.2.1顺序存储的定义11
2.2.2顺序线性表的基本运算12
2.3线性表的链式存储结构14
2.3.1线性表链式存储结构的定义14
2.3.2单链表的定义15
2.3.3线性表链式存储结构代码描述15
2.3.4单链表的基本运算16
2.3.5单链表的创建20
2.4循环链表和双向链表22
2.4.1循环链表22
2.4.2双向链表23
2.5实训24
实训1随机生成5个数放入顺序表中,实现插入
和删除操作24实训2创建5个节点的单链表,随机生成5个数并放入单链表中,
实现插入和删除操作27
2.6小结33
2.7习题33
第3章栈和队列34
3.1栈的定义和基本运算34
3.1.1栈的定义34
3.1.2栈的基本运算35
3.2顺序栈35
3.2.1顺序栈存储的定义35
3.2.2顺序栈的基本运算36
3.3链栈39
3.3.1链栈的定义39
3.3.2链栈的基本运算39
3.4队列的定义和基本运算42
3.4.1队列的定义42
3.4.2队列的基本运算42
3.5顺序队列42
3.5.1顺序队列的存储结构42
3.5.2顺序队列的基本运算45
3.6链式队列49
3.6.1链式队列的存储结构49
3.6.2链式队列的基本运算50
3.7实训52
实训1顺序共享栈的简单实现52
实训2链式队列分队的简单实现54
3.8小结57
3.9习题57
第4章字符串59
4.1字符串的定义和基本运算59
4.1.1字符串的定义59
4.1.2字符串的基本运算60
4.2串的线性存储结构和基本运算的实现60
4.2.1串的赋值运算61
4.2.2求串的长度61
4.2.3判断两个串是否相等61
4.2.4求子串61
4.2.5串值的连接62
4.2.6插入子串62
4.2.7删除子串63
4.3串的模式匹配算法63
4.3.1BruteForce算法的设计思路63
4.3.2BruteForce算法的实现过程66
4.3.3BruteForce算法的时间复杂度66
4.4实训练习和掌握BruteForce算法66
4.5小结69
4.6习题69
第5章数组与矩阵71
5.1数组的基本概念71
5.1.1数组的定义71
5.1.2一维数组72
5.1.3二维数组72
5.1.4多维数组73
5.1.5数组的顺序存储结构73
5.2特殊矩阵的压缩存储74
5.2.1对称矩阵74
5.2.2三角矩阵75
5.2.3对角矩阵76
5.3稀疏矩阵76
5.3.1三元组顺序存储表77
5.3.2稀疏矩阵的赋值运算77
5.3.3稀疏矩阵的转置运算78
5.3.4稀疏矩阵的加法运算79
5.4实训二维数组的相加81
5.5小结84
5.6习题85
第6章树87
6.1树的相关知识87
6.1.1树的基本概念87
6.1.2树的表示方法88
6.1.3树的常用术语89
6.2树的基本操作90
6.3树的存储结构90
6.3.1双亲表示法90
6.3.2孩子表示法91
6.3.3孩子兄弟表示法93
6.4二叉树的定义和基本操作94
6.4.1二叉树的定义94
6.4.2二叉树的基本操作94
6.4.3二叉树的性质95
6.4.4二叉树的顺序存储结构96
6.4.5二叉树的链表存储结构98
6.5二叉树的遍历98
6.5.1二叉树的先根遍历方法99
6.5.2二叉树的中根遍历方法101
6.5.3二叉树的后根遍历方法102
6.5.4遍历序列与二叉树的结构103
6.6创建二叉树105
6.6.1用顺序存储方式创建二叉树105
6.6.2用链表方式创建二叉树106
6.7树、森林与二叉树的转换108
6.7.1一般树转换为二叉树108
6.7.2二叉树还原为一般树109
6.7.3森林转换为二叉树110
6.7.4二叉树还原为森林110
6.7.5树与森林的遍历111
6.8二叉树的应用哈夫曼树111
6.8.1哈夫曼树的定义112
6.8.2哈夫曼树的构造113
6.8.3哈夫曼算法的实现114
6.8.4哈夫曼树的应用116
6.9实训创建二叉树并遍历117
6.10小结121
6.11习题121
第7章图123
7.1图的基本概念123
7.1.1图的定义123
7.1.2图的基本术语124
7.2图的存储结构126
7.2.1邻接矩阵的概念126
7.2.2建立图的邻接矩阵127
7.2.3邻接表128
7.3图的遍历131
7.3.1连通图的深度优先搜索132
7.3.2连通图的广度优先搜索133
7.3.3非连通图的遍历135
7.4最小生成树135
7.4.1生成树及最小生成树135
7.4.2普里姆算法136
7.4.3克鲁斯卡尔算法139
7.5最短路径140
7.5.1迪杰斯特拉算法141
7.5.2弗洛伊德Floyd算法147
7.6拓扑排序152
7.7实训邻接矩阵与遍历算法153
7.8小结162
7.9习题162
第8章查找164
8.1查找的相关定义164
8.2顺序查找算法164
8.2.1顺序查找描述165
8.2.2数据结构定义165
8.2.3典型算法与分析165
8.3折半查找算法166
8.3.1折半查找描述166
8.3.2折半查找分析166
8.3.3数据结构定义167
8.3.4典型算法与分析167
8.4分块查找168
8.4.1分块查找描述168
8.4.2分块查找分析169
8.4.3数据结构定义169
8.4.4典型算法与分析169
8.5二叉排序树查找169
8.5.1二叉排序树描述169
8.5.2二叉排序树分析170
8.5.3数据结构定义173
8.5.4典型算法与分析173
8.6哈希表查找173
8.6.1哈希表查找描述173
8.6.2哈希表查找分析174
8.6.3数据结构定义177
8.6.4典型算法与分析177
8.7实训应用各种查找算法178
8.8小结181
8.9习题181
第9章排序184
9.1插入排序184
9.1.1直接插入排序184
9.1.2希尔排序187
9.2交换排序188
9.2.1冒泡排序188
9.2.2快速排序189
9.3选择排序191
9.3.1直接选择排序191
9.3.2堆排序192
9.3.3归并排序198
9.4基数排序200
9.4.1多关键字排序200
9.4.2基数排序方法200
9.5实训实现不同的排序算法202
9.6小结210
9.7习题211
附录对应章节的Java代码215
习题答案258
参考文献271
|
| 內容試閱：
|
本书是广东省高等职业教育一类品牌专业建设项目资助的广东省精品资源开放课程数据结构与算法的配套教材。全体参编教师借鉴学习了国外一些相关的专著和多所国内高职院校的高水平教材，结合多年的教学经验和实际教学条件编撰而成。数据结构与算法是软件开发技术的一门重要的专业基础课程。课程主要讨论现实世界中数据之间的各种逻辑结构、在计算机中的存储结构以及各种算法的设计问题。本书讨论的内容包括： 线性表、栈和队列、字符串、数组与矩阵、树、图、查找、排序。其中，线性表、栈和队列、字符串、数组与矩阵属于线性结构，树和图是非线性结构，查找和排序是应用非常广泛的两个算法。2013年作者出版过类似书籍，使用三种语言编写，但在使用之后发现，C#代码和Java代码非常类似，没必要再单独列出。所以本书主要采用C语言讲解，目的是让学生更好地理解指针和链表的存储结构。同时，由于目前面向对象的软件分析和设计技术是软件开发的主流方法，所以用面向对象的程序设计语言描述数据结构问题也是必需的。本书在附录部分提供了详细的配套Java代码，读者可比较学习。本书中的所有代码配合相应的示意图，帮助大家更加容易地理解算法的实质。尤其对数据结构的初学者而言，参考的代码能运行成功是非常重要的。可以改变学习中只是了解了算法，但不能写出正确程序的困境，从而真正地理解了算法。书中大部分章节都列出了技能目标，有相应的实训、小结，课后有习题供读者思考，是一本提纲挈领、重点突出、给读者留出思考空间的教材。本书的编写出版是本课程全体教学人员集体智慧的结晶。全书编写过程中，初稿撰写完成后，各位教师相互校阅得到第二稿，在此基础上又花了较多的时间和精力进行集体审稿，从而得到第三稿，最后统稿、审稿、交稿。本书由唐懿芳、钟达夫、林萍任主编，陶南、钟丽萍、崔晓坤任副主编，附录的所有Java代码由唐懿芳整理。本书在编写过程中，得到了广东科学技术职业学院教务处、计算机工程技术学院领导和同事们的大力支持。同时，艾连科信息技术有限公司技术总监肖冠峰、项目经理席冯彦和珠海宇能科技有限公司项目经理李江对全书的实例和知识点的选择给出了很好的建议。在此向支持和参与本书编写工作的所有老师、同事及朋友表示衷心的感谢！为了方便教师教学，本书配有电子课件等相关资源，请有此需要的教师或学生登录http： 61.145.231.44： 8080skillssolverclassView.do?classKey=1088675网站，在资源下载相应链接处下载，或者访问清华大学出版社网站下载。尽管课程组教师在写作过程中非常认真和努力，但书中难免有疏漏之处，敬请读者不吝指正，我们将感激不尽。
编者2017年1月
第3章栈 和 队 列栈和队列都是特殊形式的线性表,由于它们的应用十分广泛,人们早已把它们单列为新的数据结构。栈和队列在数据的插入和删除等操作上有所不同,把它们放在一起对比学习,有助于学生掌握这两种数据结构的不同特点,从而更好地在实践中加以应用。本章将介绍栈和队列的基本概念、运算以及常见的实现方法,并通过一个有趣的案例介绍栈和队列的应用。【技能目标】 理解栈和队列的定义,掌握栈和队列的特征和基本运算。 会使用栈和队列的顺序存储结构解决问题。 能实现栈和队列的各种基本运算。 会使用栈和队列的链式存储结构解决问题。 能实现链表的各种基本运算。3.1栈的定义和基本运算让我们观察一下餐饮店里盘子的堆放和取用操作,可以发现以下一些特点： 盘子一个个地叠放成一摞,可以看成是一个由盘子组成的线性表。每次将洗净的盘子放入盘叠,总是放在最顶部,而每次用盘子时,也总是先取用盘叠最上方的那个盘子。当我们交考试试卷时,也可以发现这种情况的存在： 第一个交卷的同学卷子放在最底下,而最后一个交卷的同学卷子放在最上面。当老师改卷时,总是先从最上面的试卷开始批阅。图3.1堆栈从上述两个例子可以看出,在对事物的组织和管理上,采用的是同一机制,即使用一个线性表,且仅在表的一端允许插入和删除,这就是栈的概念。3.1.1栈的定义栈是一种特殊的线性表,它仅允许在表的一端进行运算。在表中,允许插入和删除的一端称为栈顶,另一端称为栈底,将元素插入栈顶的操作成为进栈,称删除栈顶元素的操作为出栈,如图3.1所示。因为出栈操作时后进栈的元素先出,所以栈也被称为是一种后进先出表,简称为LIFOLast In First Out。3.1.2栈的基本运算根据实际应用,通常认为,栈应该包含了以下一些基本运算。1 栈初始化置栈为空栈。2 判断栈是否为空若栈为空,则返回true,否则返回false。3 求栈的长度返回栈的元素个数。4 进栈将一个元素下推进栈。5 出栈将栈顶元素托出栈。6 读栈顶返回栈顶元素。3.2顺序栈与线性表类似,栈的存储结构也分为顺序存储结构和链式存储结构。顺序存储结构的栈简称为顺序栈,链式存储结构的栈称为链栈。3.2.1顺序栈存储的定义与顺序线性表类似,顺序栈也需要通过一个一维数组存储元素,同时设置栈顶元素的位置下标,即：顺序栈=一维数组 栈顶指示顺序栈的存储结构如图3.2所示。图3.2顺序栈的存储结构具体地说,顺序栈的数据类型描述如下： #define MAX_SIZE100设置最大元素个数typedef int Elemtype;typedef struct{Elemtype stack\[MAX_SIZE\];堆栈的元素个数int top;栈顶位置}sqstack;若将顺序栈st定义为SeqStack st=new SeqStack;顺序栈st中序号为i的元素对应数组的下标是i-1,即用st.elem\[i-1\]表示,st的栈顶用st.top表示。此外,在栈的上述存储表示下,不难得到以下栈空及栈满条件。栈空条件： st.top=-1栈满条件： st.top=MaxSize-13.2.2顺序栈的基本运算根据顺序栈的运算定义,可实现顺序栈的以下操作。1. 栈初始化栈的初始化实现比较简单,即将栈顶top的值设置为-1即可。算法实现如下： sqstack StackInit{sqstack s=sqstackmallocsizeofsqstack;if NULL== sreturn NULL;s-top=-1 ;return s ;}2. 判断栈是否为空在判断栈是否为空时,只需将栈顶指示top值与-1相比即可,若top值为-1,则表示顺序栈中不包含任何元素。算法实现如下： intStackEmptysqstack s{ifs-top top 1;}4. 进栈操作假设顺序栈中包含元素a1,a2,a3,当将元素e入栈时,实际就是要在栈顶位置插入该元素。相关算法如图3.3所示,具体描述为：1 栈顶指示top朝栈的增长方向前进一步即top值增1。2 将元素放入栈中由当前栈顶top指向的位置上。图3.3将元素入栈应该注意的是,在栈的这种静态实现中,进行进栈运算时,必须先进行栈满检查,以避免错误。插入元素x为新的栈顶元素int Pushsqstack s, Elemtype x{ifs-top = MAX_SIZE - 1栈满{printf"溢出\\n";return 0 ;}s-top;栈顶指针加1s-stack\[s-top\]=x ;将新元素x赋值给栈顶空间return 1 ;}图3.4将元素出栈5. 出栈操作同样假设顺序栈中包含元素a1,a2,a3,现将a3元素出栈,只需将栈顶指示top后退一步即top值减1即可,如图3.4所示。同时若需要在出栈的同时返回该出栈元素,还需通过一个临时变量获取a3并返回。应该注意的是,出栈前应进行栈空检查。相关的算法实现如下： 若栈不空,则删除s栈顶元素,返回其值,修改栈顶指针Elemtype Popsqstack s{Elemtype x ;if s-top stack\[s-top\];将要删除的栈顶元素返回s-top--;栈顶指针减1return x;}6. 获取栈顶元素根据栈顶指示top,可以直接获取最后入栈的元素。应该注意的是,在进行读取之前,也要进行栈空检查。相关的算法实现如下： Elemtype GetTopsqstack s{ifs-topstack\[s-top\];}要测试上述这些方法,可以使用如下语句。int _tmainint argc, _TCHAR argv\[\]{sqstack myStack=StackInit;if NULL== myStackreturn -1;printf"IsEmpty： %d, Length： %d\\n", StackEmptymyStack, StackLengthmyStack;PushmyStack, 100;PushmyStack, 200;PushmyStack, 300;printf"IsEmpty： %d, Length： %d\\n", StackEmptymyStack, StackLengthmyStack;int val=PopmyStack;printf"IsEmpty： %d, Length： %d\\n", StackEmptymyStack, StackLengthmyStack;return 0;}程序运行的结果如图3.5所示。图3.5程序运行的结果大家可能注意到,这些栈的运算都极其简单,因此,在实际编程中,有时并不将这些操作设计为方法,而是直接以语句的方式操作。不过,当涉及的栈较多,或栈的元素较为复杂,或要在多个地方进行栈的操作,还是应该采用方法调用的方式,这既符合结构化程序设计的要
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
