范文一:数据结构 C+描述
数据结构 C++描述
目 录
译者序
前言
第一部分 预备知识
第 1章 C++程序设计 1
1.1 引言 1
1.2 函数与参数 2
1.2.1 传值参数 2
1.2.2 模板函数 3
1.2.3 引用参数 3
1.2.4 常量引用参数 4
1.2.5 返回值 4
1.2.6 递归函数 5
1.3 动态存储分配 9
1.3.1 操作符 new 9
1.3.2 一维数组 9
1.3.3 异常处理 10
1.3.4 操作符 delete 10
1.3.5 二维数组 10
1.4 类 13
1.4.1 类 Currency 13
1.4.2 使用不同的描述方法 18
1.4.3 操作符重载 20
1.4.4 引发异常 22
1.4.5 友元和保护类成员 23
1.4.6 增加 #ifndef, #define和 #endif语句 24 1.5 测试与调试 24
1.5.1 什么是测试 24
1.5.2 设计测试数据 26
1.5.3 调试 28
1.6 参考及推荐读物 29
第 2章 程序性能 30
2.1 引言 30
2.2 空间复杂性 31
2.2.1 空间复杂性的组成 31
2.2.2 举例 35
2.3 时间复杂性 37
2.3.1 时间复杂性的组成 37 2.3.2 操作计数 37
2.3.3 执行步数 44
2.4 渐进符号(O 、 健 ? 、 o ) 55 2.4.1 大写 O 符号 56
2.4.2 椒 ?58
2.4.3 符号 59
2.4.4 小写 o 符号 60
2.4.5 特性 60
2.4.6 复杂性分析举例 61
2.5 实际复杂性 66
2.6 性能测量 68
2.6.1 选择实例的大小 69
2.6.2 设计测试数据 69
2.6.3 进行实验 69
2.7 参考及推荐读物 74
第二部分 数据结构
第 3章 数据描述 75
3.1 引言 75
3.2 线性表 76
3.3 公式化描述 77
3.3.1 基本概念 77
3.3.2 异常类 NoMem 79
3.3.3 操作 79
3.3.4 评价 83
3.4 链表描述 86
3.4.1 类 ChainNode 和 Chain 86 3.4.2 操作 88
3.4.3 扩充类 Chain 91
3.4.4 链表遍历器类 92
3.4.5 循环链表 93
3.4.6 与公式化描述方法的比较 94 3.4.7 双向链表 95
3.4.8 小结 96
3.5 间接寻址 99
3.5.1 基本概念 99
3.5.2 操作 100
3.6 模拟指针 102
3.6.1 SimSpace 的操作 103 3.6.2 采用模拟指针的链表 106 3.7 描述方法的比较 110 3.8 应用 111
3.8.1 箱子排序 111
3.8.2 基数排序 116
3.8.3 等价类 117
3.8.4 凸包 122
3.9 参考及推荐读物 127 第 4章 数组和矩阵 128 4.1 数组 128
4.1.1 抽象数据类型 128 4.1.2 C++数组 129
4.1.3 行主映射和列主映射 129 4.1.4 类 Array1D 131
4.1.5 类 Array2D 133
4.2 矩阵 137
4.2.1 定义和操作 137
4.2.2 类 Matrix 138
4.3 特殊矩阵 141
4.3.1 定义和应用 141
4.3.2 对角矩阵 143
4.3.3 三对角矩阵 144
4.3.4 三角矩阵 145
4.3.5 对称矩阵 146
4.4 稀疏矩阵 149
4.4.1 基本概念 149
4.4.2 数组描述 149
4.4.3 链表描述 154
第 5章 堆栈 161
5.1 抽象数据类型 161
5.2 派生类和继承 162
5.3 公式化描述 163
5.3.1 Stack 的效率 164
5.3.2 自定义 Stack 164
5.4 链表描述 166
5.5 应用 169
5.5.1 括号匹配 169
5.5.2 汉诺塔 170
5.5.3 火车车厢重排 172 5.5.4 开关盒布线 176
5.5.5 离线等价类问题 178 5.5.6 迷宫老鼠 180
5.6 参考及推荐读物 188 第 6章 队列 189
6.1 抽象数据类型 189 6.2 公式化描述 190
6.3 链表描述 194
6.4 应用 197
6.4.1 火车车厢重排 197 6.4.2 电路布线 201
6.4.3 识别图元 204
6.4.4 工厂仿真 206
6.5 参考及推荐读物 217 第 7章 跳表和散列 218 7.1 字典 218
7.2 线性表描述 219
7.3 跳表描述 222
7.3.1 理想情况 222
7.3.2 插入和删除 223
7.3.3 级的分配 224
7.3.4 类 SkipNode 224
7.3.5 类 SkipList 225
7.3.6 复杂性 229
7.4 散列表描述 229
7.4.1 理想散列 229
7.4.2 线性开型寻址散列 230 7.4.3 链表散列 234
7.5 应用 —— 文本压缩 238 7.5.1 LZW 压缩 239
7.5.2 LZW 压缩的实现 239 7.5.3 LZW 解压缩 243 7.5.4 LZW 解压缩的实现 243 7.6 参考及推荐读物 247 第 8章 二叉树和其他树 248 8.1 树 248
8.2 二叉树 251
8.3 二叉树的特性 252
8.4 二叉树描述 253
8.4.1 公式化描述 253
8.4.2 链表描述 254
8.5 二叉树常用操作 256
8.6 二叉树遍历 256
8.7 抽象数据类型 BinaryTree 259 8.8 类 BinaryTree 260
8.9 抽象数据类型及类的扩充 263 8.9.1 输出 263
8.9.2 删除 264
8.9.3 计算高度 264
8.9.4 统计节点数 265
8.10 应用 265
8.10.1 设置信号放大器 265
8.10.2 在线等价类 268
8.11 参考及推荐读物 275
第 9章 优先队列 276
9.1 引言 276
9.2 线性表 277
9.3 堆 278
9.3.1 定义 278
9.3.2 最大堆的插入 279
9.3.3 最大堆的删除 279
9.3.4 最大堆的初始化 280
9.3.5 类 MaxHeap 281
9.4 左高树 285
9.4.1 高度与宽度优先的最大及最小 左高树 285
9.4.2 最大 HBLT 的插入 287 9.4.3 最大 HBLT 的删除 287 9.4.4 合并两棵最大 HBLT 287 9.4.5 初始化最大 HBLT 289 9.4.6 类 MaxHBLT 289
9.5 应用 293
9.5.1 堆排序 293
9.5.2 机器调度 294
9.5.3 霍夫曼编码 297
9.6 参考及推荐读物 302
第 10章 竞 ?303
10.1 引言 303
10.2 抽象数据类型 WinnerTree 306 10.3 类 WinnerTree 307
10.3.1 定义 307
10.3.2 类定义 307
10.3.3 构造函数、析构函数及 Winner 函数 308
10.3.4 初始化赢者树 308
10.3.5 重新组织比赛 310
10.4 输者树 311
10.5 应用 312
10.5.1 用最先匹配法求解箱子装载 问题 312
10.5.2 用相邻匹配法求解箱子装载 问题 316
第 11章 搜索树 319
11.1 二叉搜索树 320
11.1.1 基本概念 320
11.1.2 抽象数据类型 BSTree 和 IndexedBSTree 321
11.1.3 类 BSTree 322
11.1.4 搜索 322
11.1.5 插入 323
11.1.6 删除 324
11.1.7 类 DBSTree 326
11.1.8 二叉搜索树的高度 327
11.2 AVL 树 328
11.2.1 基本概念 328
11.2.2 AVL 树的高度 328
11.2.3 AVL 树的描述 329
11.2.4 AVL 搜索树的搜索 329 11.2.5 AVL 搜索树的插入 329 11.2.6 AVL 搜索树的删除 332 11.3 红-黑树 334
11.3.1 基本概念 334
11.3.2 红-黑树的描述 336
11.3.3 红-黑树的搜索 336
11.3.4 红-黑树的插入 336
11.3.5 红-黑树的删除 339
11.3.6 实现细节的考虑及复杂性分析 343 11.4 B -树 344
11.4.1 索引顺序访问方法 344
11.4.2 m 叉搜索树 345
11.4.3 m 序 B -树 346
11.4.4 B -树的高度 347
11.4.5 B -树的搜索 348
11.4.6 B -树的插入 348
11.4.7 B -树的删除 350
11.4.8 节点结构 353
11.5 应用 354
11.5.1 直方图 354
11.5.2 用最优匹配法求解箱子装载
问题 357
11.5.3 交叉分布 359
11.6 参考及推荐读物 363
第 12章 图 365
12.1 基本概念 365
12.2 应用 366
12.3 特性 368
12.4 抽象数据类型 Graph 和 Digraph 370 12.5 无向图和有向图的描述 371
12.5.1 邻接矩阵 371
12.5.2 邻接压缩表 373
12.5.3 邻接链表 374
12.6 网络描述 375
12.7 类定义 376
12.7.1 不同的类 376
12.7.2 邻接矩阵类 377
12.7.3 扩充 Chain 类 380
12.7.4 类 LinkedBase 381
12.7.5 链接类 382
12.8 图的遍历 386
12.8.1 基本概念 386
12.8.2 邻接矩阵的遍历函数 387 12.8.3 邻接链表的遍历函数 388 12.9 语言特性 389
12.9.1 虚函数和多态性 389 12.9.2 纯虚函数和抽象类 391 12.9.3 虚基类 391
12.9.4 抽象类和抽象数据类型 393 12.10 图的搜索算法 394
12.10.1 宽度优先搜索 394 12.10.2 类 Network 395
12.10.3 BFS 的实现 395
12.10.4 BFS 的复杂性分析 396 12.10.5 深度优先搜索 397
12.11 应用 399
12.11.1 寻找路径 399
12.11.2 连通图及其构件 400 12.11.3 生成树 402
第三部分 算法设计方法
第 13章 贪婪算法 405
13.1 最优化问题 405
13.2 算法思想 406
13.3 应用 409
13.3.1 货箱装船 409
13.3.2 0/1背包问题 410 13.3.3 拓扑排序 412
13.3.4 二分覆盖 415
13.3.5 单源最短路径 421
13.3.6 最小耗费生成树 424 13.4 参考及推荐读物 433
第 14章 分而治之算法 434
14.1 算法思想 434
14.2 应用 440
14.2.1 残缺棋盘 440
14.2.2 归并排序 443
14.2.3 快速排序 447
14.2.4 选择 452
14.2.5 距离最近的点对 454 14.3 解递归方程 462
14.4 复杂性的下限 463
14.4.1 最小最大问题的下限 464 14.4.2 排序算法的下限 465 第 15章 动态规划 467
15.1 算法思想 467
15.2 应用 469
15.2.1 0/1背包问题 469
15.2.2 图像压缩 471
15.2.3 矩阵乘法链 476
15.2.4 最短路径 480
15.2.5 网络的无交叉子集 483 15.2.6 元件折叠 486
15.3 参考及推荐读物 491 第 16章 回溯 492
16.1 算法思想 492
16.2 应用 496
16.2.1 货箱装船 496
16.2.2 0/1背包问题 503
16.2.3 最大完备子图 506 16.2.4 旅行商问题 508
16.2.5 电路板排列 510
第 17章 分枝定界 516
17.1 算法思想 516
17.2 应用 519
17.2.1 货箱装船 519
17.2.2 0/1背包问题 526
17.2.3 最大完备子图 528 17.2.4 旅行商问题 529
17.2.5 电路板排列 532
范文二:数据结构C描述
时间复杂度
就是执行算法所需要的时间(执行多少次赋值、比较、判断等操作),
空间复杂度
就 是 执 行 该 算 法 需 要 消 耗 多 少 存 储 空 间 。
数据的逻辑结构也称为数据结构,分两大类:线性结构和非线性结构。
存储结构分四类:顺序存储、链接存储、索引存储和散列存储。
树的定义:树是 n(n>=0)个 结 点 的 有 限 集
(Insertion Sort)
1. 插入排序基本思想:每次将一个待排序的数据元素, 插入到前面已经排好序的数列中的适 当位置,使数列依然有序;直到待排序数据元素全部插入完为止。 二、选择排序基本思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺 序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 三、 冒泡排序 (BubbleSort) 1. 基本思想:两两比较待排序数据元素的大小, 发现两个数据元素 的次序相反时即进行交换,直到没有反序的数据元素为止
数据:是对客观事物的符号表示。
数据元素:是数据的基本单位,也称节点或记录 record n o d e
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
数据项:有独立含义的数据最小单位,也称域 (field)
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
根据数据元素间关系的基本特性,有四种基本数据结构
集合:结构中的数据元素之间除了“同属于一个集合”的关系外,别无其他关 系。
线性结构:结构中的数据元素之间存在一个对一个的关系。
树形结构:结构中的数据元素之间存在一个对多个的关系。
图状结构或网状结结构:结构中的数据元素之间存在多个对多个的关系。 逻辑结构:抽象反映数据元素之间的逻辑关系。 (算法设计)
物理结构(存储结构)
:数据结构在计算机中的表示。
(算法实现)
存储结构分为:
顺序存储结构:借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。 链式存储结构:借助指示元素存储地址的指针表示数据元素间的逻辑关系。 算法:对特定问题求解步骤的一种描述。
算法的五个重要特性:有穷性,确定性,可行性,输入和输出。
算法设计的原则或要求:正确性,可读性,健壮性,效率与低存储量需求。 衡量算法效率的方法:事后统计法和事前分析估算法
算法执行时间的增长率和
) 时间复杂度 算法运行时间的衡量准则:以基本操作在算法中重复执行的次数。
栈:限定仅在表尾进行插入或删除操作线性表。
入栈:插入元素的操作
出栈:删除栈顶元素的操作。
队列:只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾, 删除的一端叫队头。
串:由零个或多个字符组成的有限序列;
空串:零个字符的串;
长度:串中字符的数目
空串:零个字符的串;
子串:串中任意个连续的字符组成的子序列;
位置:字符在序列中的序号;
相等:串的值相等;
空格串:由一个或多个空格组成的串,空格串的长度为串中空格字符的个数。 存储位置:
LOC(i ,j)=LOC(0,0)+(b
2
*i+j)L
结点 包含一个数据元素及若干指向其子树的分支;
结点的度 结点拥有的子树;
树的度 :树中所有结点的度的最大值;
叶子结点 :度为零的结点;
分支结点 :度大于零的结点
树的深度:树中叶子结点所在的最大层次
森林:m 棵互不相交的树的集合。
满二叉树:指的是深度为 k 且含有 2k-1个结点的二叉树。
完 全二叉树:树中所含的 n 个结点和满二叉树中编号为 1至 n 的结点一一对应。 路径长度:路径上分支的数目。 树的路径长度:树根到每个结点的路径长度之和。 树的带权路径长度:树中所有叶子结点的带权路径长度之和
带权路径 长度最小的二叉树,称为最优树二叉树或赫夫曼树。
关键路径:路径长度最长的路径
数据结构对程序设计的作用 1、数据结构是一门综合性较强的计算机软件、程序设 计理论和技术相结合的重要基础知识。 它主要讨论抽象数据关系和算法在计算机 中的表示与实现 , 涉及到的数据在计算机中的表示、 组织和处理 , 以及相应结构上 的算法设计和算法性能上的分析技术。 它所包含的知识与提倡的技术方法 , 无论 对大家进一步学习计算机领域里的其他知识 , 还是对今后从事理论研究、 应用开 发及技术管理工作都起着重要的作用。
2、 学习数据结构目的与要求是学会从问题入手 , 分析和研究计算机加工的数 据结构特性 , 使大家能够为他们应用的数据选择适当的逻辑结构、 存储结构及其 相应的操作算法 , 并初步掌握算法的性能分析技术。同时 , 学习中还要进行复杂 的程序设计训练 , 也培养了大家数据抽象能力、 算法构造性思维方法能力及逻辑 思维能力 , 这些能力也是软件系统开发过程中非常重要的一种创造性思维活动。 3、 数据结构和程序设计语言本身虽然没有多大的联系 , 但数据结构是一种抽 象数据 , 是实用程序语言去描述数据结构 , 通过程序设计语言可以将它在计算机 中进行实现。 学会了数据结构 , 就会用所学知识对实践任务进行充分分析、 抽象 , 建立与之相适应的模式 , 使问题最终在计算机上得以实现。在这个过程中 , 大家 不仅对所学知识加深了理解 , 更重要的是培养了大家分析问题、解决问题的能 力 , 这对充分发挥大家的实践能力、创造能力起着重要的作用 , 也提高大家算法 设计和程序设计能力。
所以说,数据结构在软件编程中有着举足轻重的作用,可以说一个系统的工 程离不开数据结构的支持。 一个优秀的软件开发人员, 数据结构是其必备的基础 知识
C 语言的特点
1. 简洁紧凑、灵活方便 2. 运算符丰富 3. 数据结构丰富 4. C是结构式语言
5. C语法限制不太严格,程序设计自由度大
6. C语言允许直接访问物理地址,可以直接对硬件进行操作
7. C语言程序生成代码质量高,程序执行效率高
8. C语言适用范围大,可移植性好
#include
main()
{
int i;
double s[10],pingjunshu,max=0,min=0;
for(i=0;i<>
{
printf(
scanf(
}
max=s[0];
min=s[0];
pingjunshu=s[0];
for(i=1;i<>
{
if(max<>
if(min>s[i])min=s[i];
pingjunshu+=s[i];
}
pingjunshu/=10;
printf(
printf(
for(i=0;i<>
{
if(s[i]>pingjunshu)printf(
}
printf(
#include #define N 10 void main() { int a[N],i,temp; printf( for(i=0;i<> scanf( printf( printf( printf( for(i=0;i { temp=a[i]; a[i]=a[N-1-i]; a[N-1-i]=temp; } printf( printf( printf( } 1. 第一章 习题答案 2、××? 3、(1)包含改变量定义的最小范围(2)数据抽象、信息隐蔽 (3)数据对象、对象间的关系、一组处理数据的操作 (4)指针类型 (5)集合结构、线性结构、树形结构、图状结构 (6)顺序存储、非顺序存储 (7)一对一、一对多、多对多 (8)一系列的操作 (9)有限性、输入、可行性 )A(2)C(3)C 4、(1 5、语句频度为1+(1+2)+(1+2+3)+…+(1+2+3+…+n) 第二章 习题答案 1、(1)一半,插入、删除的位置 2)顺序和链式,显示,隐式 ( (3)一定,不一定 (4)头指针,头结点的指针域,其前驱的指针域 2、(1)A(2)A:E、A B:H、L、I、E、A C:F、M D:L、J、A、G或J、A、G (3)D(4)D(5)C(6)A、C 3、头指针:指向整个链表首地址的指针,标示着整个单链表的开始。 头结点:为了操作方便,可以在单链表的第一个结点之前附设一个结点,该结点的数据 域可以存储一些关于线性表长度的附加信息,也可以什么都不存。 首元素结点:线性表中的第一个结点成为首元素结点。 4、算法如下: int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”); return(0); } while(i<=l->last&&L->elem[i] i++; for(k=L->last;k>=I;k--) L->elem[k+1]=L->elem[k]; L->elem[i]=X; L->last++; return(1); } 5、算法如下: #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i,k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=l->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下: #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink { printf(“参数不合法”); return ERROR; } else { p=L; while(p->next-data<=mink)>=mink)> p=p->next; while(q->data { p->next=q->next; free(q); q=p->next; } return OK; } } 9、算法如下: int Dele(Node *S) { Node *p; P=s->next; If(p= =s) {printf(“只有一个结点,不删除”); return 0; } else {if((p->next= =s) {s->next=s; free(p); return 1; } Else { while(p->next->next!=s) P=p->next; P->next=s; Free(p); return 1; } } } 第三章 习题答案 2、(1) 3、栈有顺序栈和链栈两种存储结构。 在顺序栈中,栈顶指针top=-1时,栈为空;栈顶指针top=Stacksize-1时,栈为满。 头结点链栈中,栈顶指针top-〉 next=NULL,则代表栈空;只要系统有可用空间, 在带 链栈就不会出现溢出,既没有栈满。 5、 #include #include "stdio.h" void main( ) { char ch,temp; SeqStack s; InitStack(&s); scanf("%c",&ch); while(ch!='@'&&ch!='&') { Push(&s,ch); scanf("%c",&ch); } while(ch!='@'&&!IsEmpty(&s)) { Pop(&s,&temp); scanf("%c",&ch); if(ch!=temp) break; } if(!IsEmpty(&s)) printf("no!\n"); else { scanf("%c",&ch); if(ch=='@') printf("yes!\n"); else printf("no!\n"); } } 12、(1)功能:将栈中元素倒置。 (2)功能:删除栈中的e元素。 (3)功能:将队列中的元素倒置。 第五章习题答案 1、(1)数组A共占用48*6=288个字节; (2)数组A的最后一个元素的地址为1282; (3)按行存储时loc(A)=1000+[(3-1)*8+6-1]*6=1126 36 (4)按列存储时loc(A)=1000+[(6-1)*6+3-1]*6=1192 36 9、(1)(a,b)(2)((c,d))(3)(b)(4)b(5)(d) 10、D 第六章 习题答案 1、三个结点的树的形态有两个;三个结点的二叉树的不同形态有5个。 3、证明:分支数=n+2n+…+kn (1) 12k n= n+n+…+n(2) 01k ?n=分支数+1 (3) 将(1)(2)代入(3)得 n= n+2n+3n+…+(k-1)n+1 0234k 4、 注:C结点作为D的右孩子(画图的时候忘记了,不好意思) 5、n0=50,n2=n0-1=49,所以至少有99个结点。 6、(1)前序和后序相同:只有一个结点的二叉树 (2)中序和后序相同:只有左子树的二叉树 (3)前序和中序相同:只有右子树的二叉树 7、证明:?n个结点的K叉树共有nk个链域,分支数为n-1(即非空域)。 ?空域=nk-(n-1)=nk-n+1 8、对应的树如下: 9、(答案不唯一) 哈夫曼树如下图所示: 哈夫曼编码如下: 频率 编码 0.07 0010 0.19 10 0.02 00000 0.06 0001 0.32 01 0.03 00001 0.21 11 0.10 0011 11、对应的二叉树如下: 12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。 typedef int ElemType; void Ancestor(ElemType A[],int n,int i,int j) {while(i!=j) if(i>j) i=i/2; else j=j/2; printf("所查结点的最近公共祖先的下标是%d,值是%d",i,A[i]); } 15、编写递归算法,对于二叉树中每一个元素值为X的结点,删去以它为根的子树,并释放相应的空间。 void Del_Sub(BiTree T) { if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); } void Del_Sub_x(BiTree T,int x) { if(T->data==x) Del_Sub(T); else {if(T->lchild) Del_Sub_x(T->lchild,x); if(T->rchild) Del_Sub_x(T->rchild,x); } } 22、 int Width(BiTree bt) {if (bt==NULL) return (0); else {BiTree p,Q[50]; int front=1,rear=1,last=1; int temp=0, maxw=0; Q[rear]=bt; while(front<=last)>=last)> {p=Q[front++]; temp++; if (p->lchild!=NULL) Q[++rear]=p->lchild; if (p->rchild!=NULL) Q[++rear]=p->rchild; {last=rear; if(temp>maxw) maxw=temp; temp=0;} } return (maxw); } } 第七章 习题答案 1、(1)顶点1的入度为3,出度为0; 顶点2的入度为2,出度为2; 顶点3的入度为1,出度为2; 顶点4的入度为1,出度为3; 顶点5的入度为2,出度为1; 顶点6的入度为2,出度为3; (2)邻接矩阵如下: 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 (3)邻接表 (4)逆邻接表 2、答案不唯一 (2)深度优先遍历该图所得顶点序列为:1,2,3,4,5,6 边的序列为:(1,2)(2,3)(3,4)(4,5)(5,6) (3)广度优先遍历该图所得顶点序列为:1,5,6,3,2,4 边的序列为:(1,5)(1,6)(1,3)(1,2)(5,4) 3、(1)每个事件的最早发生时间:ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16, ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23 每个事件的最晚发生时间:: vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15, vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0 (2)每个活动的最早开始时间:e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12, e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21 每个活动的最迟开始时间: l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15, l(7,8)=19, l(6,9)=19, l(8,9)=21 (3)关键路径如下图所示: 4、顶点1到其余顶点的最短路经为: ,3;长度为15 1-〉3最短路经为1 1-〉2最短路经为1,3,2;长度为19 1-〉5最短路经为1,3,5;长度为25 1-〉4最短路经为1,3,2,4;长度为29 1-〉6最短路经为1,3,2,4,6;长度为44 13、A(7)B(3)C(2)D(11)E(8) 第八章 查找 1、画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找 长度。 解:ASL=(1+2*2+4*3+3*4)/10=2.9 5、解:(1)插入完成后的二叉排序树如下: ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5 (2)ASL=(1+282+3*4+4*5)=37/12 12、解:哈希表构造如下: 56 10 1 2 3 4 7 8 9 0 1 2 4305436 2 1 0 1 3 6 7 H(22)=(22*3)%11=0 H(41)=(41*3)%11=2 H(53)=(53*3)%11=5 H(46)=(46*3)%11=6 H(30)=(30*3)%11=2 与(41)冲突 H1(30)=(2+1)%11=3 H(13)=(13*3)%11=6 与46冲突 H1(13)=(6+1)%11=7 30冲突 H(01)=(01*3)%11=3 与 H1(01)=(3+1)%11=4 H(67)=(67*3)%11=3 与30冲突 H1(67)=(3+1)%11=4 与01冲突 H2(67)=(3+2)%11=5 与53冲突 H3(67)=(3+3)%11=6 与46冲突 H4(67)=(3+4)%11=7 与13冲突 H5(67)=(3+5)%11=8 ASLsucc=(1*4+2*3+6)/8=2 ASLunsucc=(2+8+7+6+5+4+3+2)/8=37/8 第九章 排序 1、以关键字序列(503,087,512,061,908,170,897,275,653,426)为例,手工执行以下排序算法,写出每一趟派结束时的关键字状态。 (1)直接插入排序(2)希尔排序(增量序列为5,3,1) (3)快速排序 (4)堆排序(5)归并排序 解: (2)增量为5的排序结果:170,087,275,061,426,503,897,512,653,908 增量为3的排序结果:061,087,275,170,426,503,897,512,653,908 增量为1的排序结果:061,087,170,275,426,503,512,653,897,908 (3)一次划分后:{426 087 275 061 170}503{897 908 653 512} 分别进行:{170 087 275 061}426 503 {512 653} 897 {908} {061 087}170{275}426 503 512 {653} 897 908 061 087 170 275 426 503 512 653 897 908 7、已知一组关键字:(40,27,28,12,15,50,7),要求采用快速排序法从小到大排序。请写出每趟排序后的划分结果。 解:初始状态:40 27 28 12 15 50 7 一次划分:{7 27 28 12 15} 40 {50} 依次划分:7 {27 28 12 15} 40 50 7 {15 12} 27 {28} 40 50 7 12 15 27 28 40 50 16、(1)A3 B1 C4 D2 E7 (2)C (3)C 17、对,错,对 #include #include //2.2.1顺序表的 C 语言描述 #define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int last; }Sequenlist; //2.3.2单链表的 C 语言描述 (注意循环链表 ) typedef int datatype; typedef struct node{ datatype data; struct node *next; }linklist; linklist *head; //2.3.5双链表的 C 语言描述 typedef struct dnode{ datatype data; struct dnode *prior,*next; }dlinklist; //3.2.1顺序栈的 C 语言描述 typedef struct{ datatype data[MAXSIZE]; int top; }seqstack; //3.3链式栈的 C 语言描述 typedef struct snode{ datatype data; struct snode *next; }linkstack; //4.2.1顺序队列的 C 语言描述 (注意 4.2.3循 环队列的定义和基本操作 ) typedef struct{ datatype data[MAXSIZE]; int front; int rear; }seqqueue; //4.3.1链队列的 C 语言描述 typedef struct qnode{ datatype data; struct qnode *next; }qnode_linklist; typedef struct { qnode_linklist *front ,*rear; }linkqueue; //5.2.1串的顺序存储的 C 语言定义 (注意建 立串时候的 fflush(stdin);) char sstr[MAXSIZE]; typedef struct{ datatype data[MAXSIZE]; int len; }sstring; //5.2.2链串的类型描述 typedef struct linknode{ char data; struct linknode *next; }linkstring; //5.2.3堆串的描述 typedef struct{ char *ch; int length; }hstring; //7.3.2二叉链表结点的 C 语言描述 #define MAX_SIZE 100 typedef struct btnode{ datatype data; struct btnode *lchild,*rchild; }btnode; //三叉链表结点的 C 语言描述 typedef struct btnode_3{ datatype data; struct btonde_3 *lchild,*rchild,*parent; }btnode_3; //线索二叉树的 C 语言描述 typedef struct bithrnode{ datatype data; struct bithrnode *lchild,*rchild; int ltag,rtag; }bithrnode; //7.7.1树的存储结构 1、双亲表示法(顺序 存储结构) typedef struct tnode{ datatype data; int parent; }ptnode; typedef struct{ ptnode node[MAX_SIZE]; int num; 1 / 2 }ptree; //7.7.1树的存储结构 2孩子表示法 typedef struct listnode{ int childno; struct listnode *next; }ctnode; typedef struct{ datatype data; ctnode *firstchild; }hnode; typedef struct{ hnode nodes[MAX_SIZE]; int root; int num; }clinklist; //7.7.1树的存储结构 3. 孩子兄弟表示法 (二 叉树表示法) typedef struct csnode{ datatype data; struct csnode *firstchild,*nextchild; }csnode; //8.2.1图的邻接矩阵 typedef char elemtype; typedef struct{ elemtype vex[MAXSIZE]; int edge[MAXSIZE][MAXSIZE]; int e; int n; }adjgraph; //8.2.2图的邻接表节点及其类型定义如下: typedef struct graph_linknode{ int adjvex; char info; struct linknode *firstarc; }graph_linknode; typedef struct vexnode{ char data; graph_linknode *firstarc; }vexnode; typedef struct{ vexnode adjlist[MAXSIZE]; int n,e; }algraph; //9.1排序的数据结构定义 #define sort_maxsize 10 typedef int keytype; typedef struct{ keytype key; }recordtype; recordtype r[sort_maxsize]; int main(){ return 0; } 2 / 2 基础概念 数据结构:是相互之间存在一种或多种关系的数据元素的集合。 逻辑结构和物理结构 关于数据结构,我们可以从逻辑结构和物理结构这两个维度去描述 逻辑结构是数据对象中数据元素之间的关系,是从逻辑意义上去描述的数据之间的组织形式。 逻辑结构有4种: 集合结构 (数据元素之间仅以集合的方式体现,元素之间没有别的关系) 线性结构 (数据元素之间存在一对一的关系) 树 (数据元素之间为一对多或多对一的关系) 图 (数据元素之间为多对多的关系) 物理结构则是逻辑结构在计算机中内存中的存储形式,分为两种: 顺序存储结构 链式存储结构 线性表(list) 线性表是零个或多个数据元素的的有限序列 线性表是线性结构,元素之间存在一对一的关系,线性表可通过顺序和链式两种方式来实现。 顺序存储结构,是用一段地址连续的存储单元依次存储线性表的数据元素 链式存储结构,用一组任意的存储单元来存储数据元素,不要求物理存储单元的连续性,由一系列结点组成,每个结点除了要存储数据外,还需存储指向后继结点或前驱结点的存储地址。 顺序存储和链式存储对比 顺序存储结构 优点 实现比较简单 查找指定位置的元素效率很快,时间复杂度为常数阶O(1) 无需额外存储元素之间的逻辑关系(链式存储由于存储空间随机分配,需要存储元素之间的逻辑关系) 缺点 需要预先分配存储空间,如果数据元素数量变化较大,很难确定存储容量,并导致空间浪费 若频繁进行插入删除操作,则可能需要频繁移动大量数据元素 链式存储结构 优点 不需要提前分配存储空间,元素个数不受限制 对于插入删除操作,在已找到目标位置前提下,效率很高,仅需处理元素之间的引用关系,时间复杂度为O(1) 缺点 实现相对复杂 查找效率较低,最坏情况下需要遍历整张表 由于物理存储位置不固定,需要额外存储数据元素之间的逻辑关系 链式存储代码实现 单链表 package listdemo;/** * Created by chengxiao on 2016/10/18. */public class MyLinkedList { /** * 指向头结点的引用 */ private Node first ; /** * 线性表大小 */ private int size; /** * 结点类 */ private static class Node{ //数据域 private int data; //指向后继结点的引用 private Node next; Node(int data){ this.data = data; } } /** * 从头部进行插入 * 步骤:1.新结点的next链指向当前头结点;2.将first指向新节点 * 时间复杂度:O(1) * @param data */ public void insertFirst(int data){ Node newNode = new Node(data); newNode.next = first; first = newNode; size++; } /** * 从头部进行删除操作 * 步骤:1.将头结点的next链置空 2.将first引用指向第二个结点 * 时间复杂度为:O(1) * @return */ public boolean deleteFirst{ if(isEmpty){ return false; } Node secondNode = first.next; first.next = null; first = secondNode; size--; return true; } /** * 取出第i个结点 * 步骤:从头结点进行遍历,取第i个结点 * 时间复杂度:O(n),此操作对于利用数组实现的顺序存储结构,仅需常数阶O(1)即可完成。 * @param index * @return */ public int get(int index) throws Exception { if(!checkIndex(index)){ throw new Exception('index不合法!'); } Node curr = first; for(int i=0;i= 0 && index 输出结果 4 3 2 1 2 3 2 1 双端链表 上面罗列了线性表中的几种基本操作,考虑下,如果要提供一个在链表尾部进行插入的操作insertLast,那么由于单链表只保留了指向头结点的应用first,需要从头结点不断通过其next链找后继结点来遍历,时间复杂度为O(n)。其实,我们可以在保留头结点引用的时候,也保留一个尾结点的引用。这样,在从尾部进行插入时就方便多了 双端链表同时保存对头结点和对尾结点的引用 /** * 指向头结点的引用 */ private Node first ; /** * 指向尾结点的引用 */ private Node rear; 从尾部进行插入 /** * 双端链表,从尾部进行插入 * 步骤:将当前尾结点的next链指向新节点即可 * 时间复杂度:O(1) * @param data */ public void insertLast(int data){ Node newNode = new Node(data); if(isEmpty){ first = newNode; rear = newNode; size++; return; } rear.next = newNode; rear = newNode; size++; } 做其他操作的时候也需注意保持对尾结点的引用,此处不再赘述。 双向链表 再考虑下,如果我们要提供一个删除尾结点的操作,步骤很简单:在删除尾结点的过程中需要将其前驱结点(即倒数第二个结点)的next链引用置为空,但由于我们的链表是单链表,一条道走到黑,要找倒数第二个结点得从头开始遍历,这种情况下,我们就可以考虑使用双向链表。 双向链表的的每一个结点,包含两个指针域,一个指向它的前驱结点,一个指向它的后继结点。 /** * 删除尾结点 * 主要步骤:1.将rear指向倒数第二个结点 2.处理相关结点的引用链 * 时间复杂度:O(1) * @return */ public void deleteLast throws Exception { if(isEmpty){ throw new Exception('链表为空'); } Node secondLast = rear.prev; rear.prev = null; rear = secondLast; if(rear == null){ first = null; }else{ rear.next = null; } size--; } 其他操作同理,在过程中需要同时保持对结点的前驱结点和后继结点的引用,删除操作时,需要注意解除废弃结点的各种引用,便于GC。 总结 本文对数据结构的一些基本概念,逻辑结构和物理结构,线性表等概念进行了基本的阐述。同时,介绍了线性表的顺序存储结构和链式存储结构,对线性表的链式存储结构(单链表,双端链表,双向链表),使用Java语言做了基本实现。数据结构的重要性毋庸置疑,它是软件设计的基石,由于自己非科班出身,虽曾自学过一段时间,也不够系统,最近希望能重新系统地梳理下,本篇就当自己数据结构再学习的开篇吧,共勉。范文三:数据结构——C语言描述耿国华习题及答案
范文四:各种数据结构定义的C语言描述
范文五:数据结构(Java描述)之线性表