数据结构的作业.docx

数据结构的作业.docx

《数据结构的作业.docx》由会员分享，可在线阅读，更多相关《数据结构的作业.docx（20页珍藏版）》请在冰点文库上搜索。

数据结构的作业

实验2、单链表一元多项式运算

目的：

掌握链式存储的单链表的一个典型应用。

问题描述：

用单向链表保存一元多项式，实现它的创建、显示以及算术加法操作。

步骤：

1.定义一元多项式的ADT和基本操作。

2.采用链式存储结构保存多项式并实现创建、显示。

3.实现多项式加法操作。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够定义一元多项式，掌握有序单链表的复杂合并。

实验3、线性表的顺序存储和链式存储实现

目的：

1.掌握线性表的不同存储结构下的实现。

2.练习编写实验报告1。

问题描述：

完成线性表的顺序存储和链式存储方式的实现。

实现线性表ADT中列出的基本操作。

采用有/无头结点两种不同的方式逐一实现。

步骤：

1.定义线性表的ADT和基本操作，并给出相应的C语言版本。

2.完成创建、查找、插入、删除以及遍历。

3.实现双向链表的各项基本操作，包括：

创建、撤销、清除、插入、修改、删除、定位等。

4.完成实验的实验报告，报告的格式采用《数据结构题集》的模板格式。

两周之后提交。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够用不同存储结构实现线性表，可以采用有/无头节点的方法来管理，能够体会其中的差异。

思考题：

1.链式考虑动态链和静态链两种方法。

实验4、表达式求值

目的：

1.掌握使用栈来计算四则运算表达式的值。

2.通过这个学期的强化练习，能够较熟练地掌握一门编程语言。

问题描述：

完成教材3.2的应用举例，特别是实现利用栈结构完成表达式求值。

步骤：

1.用C语言定义所需栈的ADT和基本操作。

2.实现表达式求值的算法。

3.测试自己完成的练习，包括不断改进程序的输入、输出等。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解进而掌握对栈结构的定义和使用；理解基于栈结构的应用的基本特点。

思考题：

1.实现一个可编程计算器。

计算器能够完成多个功能：

a）、能够执行带括号的四则算术运算；b）、支持表达式包含变量，包括支持重复出现的变量；c）、使用自定义的简单函数；d）、其他你自己想到的功能。

2.迷宫求解目前可以选作。

实验5、银行排队的模拟[选做]

目的：

掌握使用队列来模拟类似银行的排队处理系统。

问题描述：

完成教材3.5（pp65）的银行应用模拟。

步骤：

1.用C语言定义所需队列的ADT和基本操作。

2.实现银行排队的模拟算法。

3.测试自己完成的练习，观察并理解模拟程序的各个处理。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解进而掌握对队列结构的定义和使用；理解基于队列的应用的基本特点。

思考题：

1.计算杨辉三角某一行的系数的程序。

2.实现通用的输出二项式系数的算法。

即：

对任意整数n，n>0，使用循环队列输出（a+b）n的各项系数。

实验6、字符串ADT实现

目的：

掌握字符串的定义及基本操作的实现。

问题描述：

用堆存储方式保存字符串，实现字符串的各种基本操作，包括赋值、替换、取子串、串连接等。

步骤：

1.用C语言定义字符串的ADT和基本操作。

2.实现赋值、替换、取子串、串连接等操作。

3.测试自己完成的练习，观察每个操作的执行效果。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解并掌握字符串的定义和堆存储方式的实现方法。

思考题：

1.估算各个操作的复杂度和空间利用效率。

实验7、文件字符串查找

目的：

掌握字符串模式匹配的经典算法。

问题描述：

分别用简单方法和KMP方法实现index在文本文件中查找指定字符串的功能。

步骤：

1.定义字符串类型并实现简单的index操作，从文件中查找指定字符串。

2.定义字符串类型并实现KMP方法的index操作，从文件中查找指定字符串。

3.建立一个文本文件，测试自己完成的练习，观察并理解模拟程序的各个处理。

[选做]

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握字符串模式匹配的典型算法。

思考题：

1.对KMP算法分别用手工和程序对某个模式串输出next和nextval。

实验8、定位递归函数[选做]

目的：

掌握并利用字符串模式匹配的算法。

问题描述：

实现index在文本文件中查找指定字符串的功能。

分析C源程序中是否存在递归函数。

如果有，则输出该函数的定义以及在本程序内对它调用的代码行。

步骤：

1.定义字符串类型并实现简单的index操作，从文件中查找指定字符串。

2.可以进行必要的假设，比如开始可以假定文件能够1次读入内存等等。

3.使用index（）根据具体函数的定义找到函数定义并检查是否发生递归调用。

4.本程序内对它调用的代码行。

5.建立一个文本文件，测试自己完成的练习，观察并理解模拟程序的各个处理。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握字符串模式匹配的典型算法。

特别是，能够利用index方法完成复杂查找任务。

思考题：

无

实验9、稀疏矩阵转置

目的：

掌握特殊矩阵的存储和操作算法。

问题描述：

实现用三元组保存稀疏矩阵并实现矩阵转置的算法。

步骤：

1.定义稀疏矩阵的三元组形式的存储结构。

2.实现三元组矩阵的传统转置算法（pp99的算法5.1）。

3.输入矩阵非零元素，测试自己完成的算法。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握三元组存储矩阵的方法并根据存储结构设计特别的算法。

在稀疏度较高情况下，算法效率较高。

思考题：

1.将稀疏矩阵还原输出，保持相对的美观。

2.将还原输出的矩阵设计成有趣的图案。

实验10、稀疏矩阵乘法[选做]

目的：

掌握特殊矩阵的存储和操作算法。

问题描述：

实现基于行逻辑联接顺序表的稀疏矩阵的乘法。

步骤：

1.定义稀疏矩阵的三元组形式的存储结构，采用基于行逻辑联接顺序表。

2.实现三元组矩阵乘法的算法（pp99的算法5.1）。

3.输入矩阵非零元素，输出完整矩阵。

4.测试自己完成的矩阵乘法。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

在稀疏度较高情况下，设计合适的算法可以得到效率较高的乘法算法。

思考题：

无

实验11、广义表的存储和遍历[选做]

目的：

掌握广义表的链式存储结构和遍历算法。

问题描述：

对字符串形式广义表的解析后保存在链式存储结构中，并遍历和输出该广义表的全部节点。

步骤：

1.定义广义表的链式存储结构，可以是采用头尾链表或者是扩展线性链表。

2.输入的广义表形式可以使用形如"（a,b,（c,d）,（e,f,（g,h））,i）"的字符串。

3.实现字符串广义表的解析算法，解析结果保存在所选用的存储结构中。

4.遍历能够将保存的广义表还原为输入的串形式。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握的链式存储结构及相应的遍历方法。

思考题：

1.练习不同的解析方法，即：

表头+表尾或者扩展线性表方式

实验12、二叉树遍历

目的：

1.掌握二叉树的各种存储和遍历算法。

2.练习编写实验报告2。

问题描述：

实现链式存储的二叉树的多种遍历算法，包括递归、非递归以及线索二叉树等。

步骤：

1.定义字符串类型并实现简单的index操作，从文件中查找指定字符串。

2.实现二叉树的各种遍历算法和二叉树的中序线索化算法：

a）先序、中序和后序遍历算法；

b）教材中序遍历的非递归算法；

c）教材先序或后序遍历非递归算法之一；

d）建立线索后，利用线索对树进行中序遍历和反中序遍历。

[选做]

3.实现二叉树的按层遍历的算法。

4.设计一个测试用的二叉树并创建对应的内存二叉树，能够测试自己算法的边界。

5.完成实验的实验报告，报告的格式采用《数据结构题集》的模板格式。

两周之后提交。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握二叉树的存储结构并能够独立实现各种遍历算法。

思考题：

无

实验13、完全二叉树判定[选做]

目的：

掌握完全二叉树的特性。

问题描述：

对采用不同存储结构的二叉树根据完全二叉树的属性判定其是否为完全二叉树。

步骤：

1.定义基于顺序或链式存储结构的二叉树。

2.设计并实现对输入二叉树的特性判定，报告完全二叉树。

3.建立至少2个二叉树，测试自己完成的算法。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握二叉树的顺序和链式存储结构的特点并能够根据完全二叉树的特性来设计判定算法。

思考题：

1.再次分析、总结不同存储结构和算法之间的相互影响。

2.实现验证完全二叉树的属性/特点的各种算法，比如用程序验证完全二叉树的结点所在的层数。

实验14、树的结构转换[选做]

目的：

掌握树的多种存储结构以及不同结构之间的转换算法。

问题描述：

分别用双亲表示法、孩子（链表）表示法以及孩子兄弟（二叉链表）表示法等3种不同存储结构保存树，并实现不同结构间的相互转换。

步骤：

1.使用自己定义的某种方式输入一棵树并保存在一种结构。

2.能够按照约定的格式遍历整个树并将各个节点保存在其他两种的存储结构中。

3.设计一个测试用的二叉树并创建对应的内存二叉树，能够测试自己算法的边界。

4.转换在任意两个存储结构之间进行的双向转换。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握树的不同存储结构并能够进行一对一的结构转换。

思考题：

1.实现森林和二叉树间的相互转换。

实验15、赫夫曼编码和译码

目的：

掌握并运用最优二叉树解决具体应用问题。

问题描述：

实现教材上给出的赫夫曼编码的编码和译码方法。

步骤：

1.设计赫夫曼编码记译码算法。

2.使用课件或教材中的例子进行测试和验证。

3.自己给出一段短文对其进行编码和译码处理，输出译码结果。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握二叉树的加权路径长度并用来进行字符的前缀编码。

思考题：

1.手工计算测试树的某个最短路径长度并给出计算方法。

实验16、图存储与遍历

目的：

1.理解有向图和无向图不同存储结构的适用条件。

2.掌握对使用不同存储结构的图进行遍历的算法。

问题描述：

自己任意给出一个有向图和对应的无向图，分别用数组（邻接矩阵）、邻接表、十字链表、邻接多重表加以存储并给出对该图的深度和广度优先遍历算法。

对于无向图，在遍历过程中指出连通分量的边界。

步骤：

1.分别定义数组（邻接矩阵）、邻接表、十字链表以及邻接多重表的图存储结构。

2.实现在每种存储结构上图的深度优先遍历算法。

3.实现在每种存储结构上图的广度优先遍历算法。

4.给出一个有向图和对应的无向图，能够分别测试自己的遍历算法。

5.对无向图，给出发现图中连通分量的算法并用水面的图进行测试。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握图的不同存储结构以及使用不同存储结构的图遍历方法。

思考题：

无

实验17、生成树的Prim方法

目的：

掌握带权无向图的生成树概念与生成算法，同时估算时间复杂度。

问题描述：

任意给出一个带权无向图，实现获得最小生成树的Prim方法。

步骤：

1.定义使用邻接矩阵保存的带权无向图。

2.设计并实现从无向图某个顶点u出发获得生成树的Prim算法。

3.设计一个带权无向图，能够测试自己实现的算法。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握带权无向图的邻接矩阵存储方法并用来得到生成树的经典算法。

特别是，能够估算算法的时间复杂度。

思考题：

1.实现获得生成树的Kruskal算法。

实验18、计算单源最短路径

目的：

掌握求解带权有向图中单源最短路径的方法。

问题描述：

带权有向图中从指定顶点u出发实现用Dijkstra方法计算u到所有其它顶点的最短路径值的算法，同时保留相应的最短路径。

步骤：

1.定义使用带权邻接矩阵保存的带权有向图。

2.设计并实现从某个顶点u出发获得所有最短路径值的Dijkstra算法。

3.设计一个带权有向图，能够测试自己实现的Dijkstra算法。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握Dijkstra算法。

思考题：

1.理解并实现带权有向图上的Floyd算法计算所有顶点间的最短路径。

实验19、有序表二分查找

目的：

掌握经典的二分查找算法。

问题描述：

实现有序表的二分查找算法并用程序给出每个元素的查找长度和整个有序表的平均查找长度。

步骤：

1.采用顺序存储结构保存有序线性表，假定有序表中的元素互不相同。

2.设计并实现有序表的二分查找算法。

算法能够同时记录查找长度。

3.设计一个测试用的有序表，能够测试自己算法的边界，包括第一个、最后一个等。

4.使用有序表中的元素以及不在表中的元素对比手工计算和程序记录的查找长度。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握有序表二分查找的方法、查找长度以及平均查找长度。

思考题：

无

实验20、实现二叉排序树

目的：

1.掌握二叉排序树的定义以及基本操作的实现算法。

2.编写实验报告3。

问题描述：

实现二叉排序树的查找、插入和删除操作。

步骤：

1.定义二叉链表结构存储二叉排序树。

2.实现二叉排序树的查找、插入和删除操作算法。

3.设计测试用二叉排序树并使用插入算法创建对应的内存二叉树，能够测试查找、插入和删除算法的边界。

4.完成实验的实验报告，报告的格式采用《数据结构题集》的模板格式。

两周之后提交。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握二叉排序树的基本算法。

思考题：

1.手工和程序记录查找长度，估计针对具体数据记得算法平均查找长度。

实验21、哈希表管理[选做]

目的：

理解并掌握哈希表管理的基本操作，以及分析平均查找长度ASL。

问题描述：

根据不同的哈希函数和哈希冲突消解方法实现哈希表的查找、插入和删除操作。

步骤：

1.设计哈希函数和哈希冲突消解方法。

2.统一的接口操作hash/collision，不同的hash函数和冲突实现策略。

3.设计一组有冲突数据和无冲突数据，创建对应的哈希表，测试算法。

4.支持使用链地址法的冲突消解方法。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握哈希函数和冲突消解的概念和实现方法，特别是掌握链地址法。

能够分析、估算特定方法的平均查找长度ASL。

思考题：

1.对链地址法设计将溢出桶保存在磁盘文件中的管理算法。

实验22、综合排序算法

目的：

掌握对同一数据集进行排序的多种方法。

问题描述：

设计一个数据集，分别用不同的排序算法对集合中的元素进行排序，包括：

插入、交换、选择、归并和基数排序等。

步骤：

1.设计一个数据集，假定有序表中的元素键值互不相同。

数据集可以对课件中的例子数据扩充

2.设计并实现插入、交换、选择、归并和基数排序等多种不同的排序算法。

3.使用设计的数据集测试自己算法的边界并用二分查找检测排序结果的正确性。

4.估算算法的时间、空间复杂度。

5.用全局计数器记录并比较不同算法的比较次数和数据移动次数。

设备和环境：

PC计算机、Windows操作系统、C/C++开发环境

结论：

能够理解和掌握内排序的各种基本算法并能够分析算法相应的时空复杂度。

思考题：

1.构造多个不同的数据集测试、对比不同算法的排序稳定性。