本教材内容共包括10个项目,具体内容安排如下。
项目1 构建校园办公室网络实现校园办公室的网络配置与管理。本项目实现办公室交换机的认知、办公室交换机的登录与管理、办公室交换机的初始化配置、办公室交换机的远程登录配置与管理等4个任务。
项目2 构建校园办公楼网络实现办公楼部门、处室之间能够互相访问通信,以提高办公的便利。本项目实现办公楼交换机划分VLAN实现部门业务隔离、办公楼实现跨交换机的相同部门通信、办公楼交换机基于SVI接口实现不同部门通信等3个任务。
项目3 构建校园信息中心网络实现信息中心双核心、冗余的网络架构,实现链路备份和负载均衡,提高网络的稳定性。本项目实现信息中心服务器区交换机配置STP消除环路、信息中心服务器区交换机配置STP实现负载均衡、信息中心核心交换机之间配置端口聚合提高网络带宽等3个任务。
项目4 构建校园内部网络实现校园网内部不同区域的互联互通。本项目的实现路由器的基本配置,配置静态路由和默认路由,配置单臂路由,配置动态路由、配置路由重分布等7个任务。
项目5 筑牢校园网络安全实现接入层交换机的端口安全管理,实现终端用户的安全访问;通过对目的地是服务器的数据流的管理,实现对服务器的访问控制。本项目实现办公室交换机的端口安全配置、配置标准ACL、配置标准命名、配置扩展ACL等5个任务。
项目6 规划校园动态IP地址实现地址的集中管理,学校要求办公楼主机能够通过DHCP自动从服务器获取到IP地址及相关参数。本项目实现三层交换机DHCP配置、三层交换机DHCP中继配置等2个任务。
项目7 实施校园接入广域网实现校区广域网接入配置PAP认证、CHAP认证,保护校园网络安全。本项目实现校园主校区接入广域网配置PAP、校园分校区接入广域网配置CHAP等2个任务。
项目8 构建校园内外互联网络实现主校区服务器配置静态NAT将内网Web服务向互联网发布,分校区配置NAPT,使分校区所有的计算机都可以访问Internet,合作企业配置动态NAT将企业内部计算机都可以访问Internet等3个任务。
项目9 构建校园无线网络实现办公楼、学生宿舍区笔记本电脑、PAD等移动设备接入互联网。本项目实现分校区办公区无线路由器的配置与管理、分校区办公区无线局域网胖AP的配置与管理、分校区学生宿舍无线局域网瘦AP的配置与管理等3个任务。
项目10 构建中小型企业网络实现公司总部与分部的网络配置与管理。本项目的实现可分解为公司总部网络的互联互通、公司总部与分部网络的互联互通、公司内部接入Internet、公司的合作伙伴接入Internet等4个任务。
第1章绪论1
1.1数据、数据元素、数据项2
1.2什么是数据结构2
1.2.1数据的逻辑结构2
1.2.2数据的存储结构4
1.3算法5
1.3.1算法的基本概念5
1.3.2算法的时间复杂度6
1.3.3算法的空间复杂度7
1.4为什么要学习数据结构7
课后作业8
第2章线性表11
2.1线性表的基本定义12
2.2基于索引存储的线性表13
2.2.1索引表的基本概念13
2.2.2索引表的初始化13
2.2.3索引表元素的随机访问16
2.2.4清空列表元素clear()17
2.2.5计算列表长度18
2.2.6向列表尾部追加append()18
2.2.7在列表指定位置插入元素insert()22
2.2.8删除并返回列表中索引为指定值的元素pop()25
2.2.9查找列表中指定值的元素的索引index()28
2.2.10移除列表中指定值的元素remove()29
2.2.11列表元素逆序reverse()31
2.2.12排序操作sort()32
2.3线性表的应用——文件查找33
2.4线性表的应用——一元多项式求值33
2.4.1数据存储33
2.4.2一元多项式求值算法34
2.5线性表的链式表示和实现35
2.5.1链表的基本概念35
2.5.2链表节点的定义37
2.5.3单链表的初始化和销毁38
2.5.4访问单链表中指定位置的元素39
2.5.5清空链表元素clear()40
2.5.6计算链表长度41
2.5.7向链表尾部追加append()41
2.5.8在链表指定位置插入元素insert()42
2.5.9删除并返回链表中索引为指定值的元素pop()43
2.5.10查找链表中指定值的元素find()45
2.5.11移除链表中指定值的元素remove()46
2.5.12链表元素逆序reverse()47
2.5.13链表的功能测试48
2.6案例——资源融合49
本章小结51
课后作业52
第3章栈和队列56
3.1栈及其抽象类型定义57
3.1.1栈的引入57
3.1.2栈的抽象类型定义58
3.2栈的实现59
3.2.1索引栈的实现59
3.2.2链式栈的实现60
3.3栈的应用——表达式计算64
3.3.1前缀、中缀和后缀表达式65
3.3.2计算后缀表达式65
3.3.3中缀转后缀66
3.4递归和回溯法70
3.4.1栈和递归70
3.4.2回溯法71
3.5队列及其抽象类型定义73
3.5.1队列的引入73
3.5.2队列的抽象类型定义74
3.6队列的实现75
3.6.1索引队列的实现75
3.6.2链式队列的实现76
3.7队列的应用79
本章小结83
课后作业83
第4章树和二叉树86
4.1树的定义和基本术语87
4.1.1树的引入87
4.1.2树的基本术语88
4.2二叉树的定义与性质89
4.2.1二叉树的定义89
4.2.2二叉树的形态90
4.2.3二叉树的性质91
4.3二叉树的存储与遍历92
4.3.1二叉树的抽象类型定义92
4.3.2二叉树的存储结构93
4.3.3二叉树的遍历与实现94
4.3.4二叉树的典型应用99
4.4树和森林100
4.4.1树的存储结构100
4.4.2树的遍历103
4.4.3树、森林向二叉树的转换104
4.5哈夫曼树105
4.5.1哈夫曼树的基本概念105
4.5.2构造哈夫曼树107
4.5.3哈夫曼编码111
4.6并查集115
4.6.1并查集的主要操作115
4.6.2并查集的实现117
4.7案例——文件遍历119
本章小结121
课后作业121
第5章图125
5.1图的基本概念126
5.1.1图的引入126
5.1.2抽象数据类型定义130
5.2图的存储结构130
5.2.1图的邻接矩阵存储及实现130
5.2.2图的邻接表存储及实现133
5.2.3有向图的十字链表存储及实现136
5.3图的遍历139
5.3.1深度优先搜索遍历140
5.3.2广度优先搜索遍历142
5.3.3遍历测试代码143
5.4图的连通性144
5.4.1图的连通性144
5.4.2生成树和生成森林146
5.5最小生成树147
5.5.1克鲁斯卡尔(Kruskal)算法148
5.5.2普里姆(Prim)算法151
5.6最短路径154
5.6.1单源最短路径154
5.6.2多源最短路径158
5.7图的应用160
5.7.1AOV网与拓扑排序161
5.7.2AOE网与关键路径164
5.8案例——六度空间理论169
本章小结170
课后作业171
第6章排序176
6.1基本概念177
6.2选择排序178
6.3冒泡排序与鸡尾酒排序181
6.3.1冒泡排序181
6.3.2鸡尾酒排序183
6.4插入排序186
6.5希尔排序189
6.6堆和优先队列192
6.6.1堆192
6.6.2堆排序197
6.6.3部分排序203
6.6.4优先队列204
6.7快速排序208
6.8归并排序213
6.9桶排序216
6.9.1基本算法216
6.9.2多关键字排序218
6.10基数排序221
6.11计数排序222
6.12排序算法的应用223
本章小结224
课后作业225
第7章查找230
7.1查找的引入231
7.2相关概念231
7.2.1查找表231
7.2.2数据项(也称项或字段)232
7.2.3组合项232
7.2.4数据元素(记录)232
7.2.5关键字232
7.2.6查找232
7.3查找算法的度量232
7.4静态查找233
7.4.1顺序查找233
7.4.2折半查找与插值查找235
7.4.3分块查找239
7.5动态查找之平衡二叉树241
7.5.1二叉查找树241
7.5.2AVL树249
7.5.3红黑树259
7.6动态查找之B树263
7.6.1B树263
7.6.2B+树272
7.7动态查找之哈希275
7.7.1哈希的概念275
7.7.2哈希函数276
7.7.3冲突处理277
7.7.4哈希表的容量280
7.8动态查找之跳表282
7.9Trie树285
本章小结288
课后作业289
第8章综合项目295
8.1项目背景与需求分析295
8.1.1项目背景295
8.1.2项目功能描述296
8.2系统功能模块设计296
8.2.1场地信息管理模块设计思路297
8.2.2预约、使用信息管理模块设计思路301
本章小结304
进一步学习建议304
附录部分习题答案305
参考文献306
1.弱化公式推导和证明,强调数据结构和算法的实现;
2.使用Python语言描述数据结构和算法(目前市场上可供本专业使用的Python版本数据结构教材极为稀少),教材代码可运行,便于读者上机练习;
3.代码和案例尽可能地接近真实应用;
4.相比传统数据结构教材,本教材对跳表、平衡树、字典树等工程中常用的数据结构和算法进行了更为详细的介绍,同时结合Python语言的特点,去除了广义表、数组压缩和串等内容;
5.针对混合式教学需要,教材的每一章配有教学目标和作业题;
6.不同于类似的教材,本教材的作业题中除了基本的选择、简答和编程题,还包含了结合实际工程应用背景的应用题,帮助学生学以致用,深入理解和体会所学内容在实际中的作用和意义;
7.除了排序和查找,教材的每一章都提供应用小节,介绍本章知识点的具体应用。