2022年实验任务书 .pdf

《2022年实验任务书 .pdf》由会员分享，可在线阅读，更多相关《2022年实验任务书 .pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、目录实验 1 顺序表的应用 . 2实验 2 链表的应用 . 5实验 3 栈的应用 . 6实验 4 队列的应用 . 7实验 5 树的应用 . 8实验 6 图的应用 . 9实验 7 图的应用 . 10实验 8 查找与排序 . 11名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 实验 1 顺序表的应用实验目的1 熟悉 C语言的上机环境，掌握C语言的基本结构。2 会定义线性表的顺序存储结构。3 熟悉对顺序表的一些基本操作和具体的函数定

2、义。4 掌握在线性表的顺序存储结构上的一些其它操作。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容1、基础题：编写应用程序（填空） ，实现可以在顺序表中插入任意给定数据类型（定义为抽象数据类型） 数据的功能。要求在主函数中定义顺序表并对该顺序表插入若干个整数类型的数据（正整数） ，对它们求和并输出。请使用动态内存分配的方式申请数组空间， 并把主函数设计为一个文件SeqList.cpp，其余函数设计为另一个文件 SeqList.h 。请填空完成以下给出的源代码并调试通过。（1） 文件 SeqList.h:typedef struct List ElemType *list; int

3、 size; int MaxSize; SeqList; void InitList(SeqList &L) / 初始化线性表 void ClearList(SeqList &L) / 清除线性表 int LengthList(SeqList L) / 求线性表长度 . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - bool InsertList(SeqList &L, ElemType item, int pos) / 按

4、给定条件 pos向线性表插入一个元素 . ElemType GetList(SeqList L, int pos) / 在线性表 L中求序号为 pos的元素，该元素作为函数值返回. （2）文件 SeqList.cpp：#include #include typedef ElemType; #define MAXSize 10 #include SeqList.h void main(void) SeqList myList; int i=1, x, sum=0, n; InitList ( ); scanf( “ %d” , &x); while ( x!= -1 ) if ( InsertL

5、ist (myList, , i )=0) printf(错误!n); return ; i+; scanf( “ %d” , &x); n = LengthList (myList); for (i=1; i=n; i+) x=GetList(myList, i); sum = + x; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - printf(%dn , sum); ClearList(myList); 2、 提高部分

6、：编写函数 bool DeleteElem(SeqList &L, int min, int max)实现从顺序表中删除其值在给定值min 和 max之间（ min 0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0i=n)，另一个为起始报数上限值m。接着从编号为 i 的人开始按顺时针方向自1 起顺序报数，报到 m 时停止报数，且报到 m 的人出列，并将他的密码作为新的m 值，从他在顺时针方向上的下一个人起重新自 1 报数，, ，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。基本要求 : 人数 n、

7、每人的正整数密码、首次报数人编号i、初始报数上限值m 均由键盘输入。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 实验 3 栈的应用实验目的1 会定义顺序栈和链栈的结点类型。2 掌握栈的插入和删除结点在操作上的特点。3 熟悉对栈的一些基本操作和具体的函数定义。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容1、基础题：设栈采用顺序存储结构（用动态数组） ，请编写栈的各种基本操作的实现函数，并存放在头文件stack

8、.h中。同时建立一个验证操作实现的主函数文件stack.cpp ，编译并调试程序，直到正确运行。提示： 栈的动态数组顺序存储结构可定义如下：struct Stack ElemType *stack ; / 存栈元素int top; / 栈顶指示器int MaxSize; / 栈的最大长度; 栈的基本操作可包括： void InitStack (Stack &S); /构造一个空栈S int EmptyStack (Stack S); /若栈 S 为空栈返回 1，否则返回 0 void Push(Stack &S, ElemType item); /元素 item 进栈 ElemType Pop

9、(Stack &S); /栈 S 的栈顶元素出栈并返回 ElemType Peek(Stack S); /取栈 S 的当前栈顶元素并返回 void ClearStack (Stack &S); /清除栈 s，使成为空栈2、应用题：写一函数，判断给定的字符串是否中心对称。如字符串“abcba” 、 “abccba”均为中心对称，字符串“ abcdba”不中心对称。要求利用stack.h 中已实现的有关栈的基本操作函数来实现。 请把该函数添加到文件stack.cpp中的主函数前， 并在主函数中添加相应语句进行测试。函数原型如下：int IsReverse(char *s) / 判断字符串 S是否中

10、心对称，是返回1，否则返回 0名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 实验 4 队列的应用实验目的1 掌握队列的存储结构及基本操作。2 掌握循环队列的设置及循环队列的各种基本操作的实现。3 通过具体的应用实例，进一步熟悉和掌握队列的实际应用。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容1、基础题：建立头文件queue.h ，定义顺序存储的循环队列存储结构，并编写循环队列的各种基本操作实现函数。 同时建立

11、一个验证操作实现的主函数文件queue.cpp ，编译并调试程序，直到正确运行。说明： 队列的基本操作可包括： void InitQueue (Queue &Q); /构造一个空队列Q int EmptyQueue (Queue Q); /判断队列 Q 是否为空，若空返回1，否则返回 0 void EnQueue (Queue &Q, ElemType item); /元素 item 进队列 Q ElemType OutQueue (Queue &Q); /队头元素出队列 Q，并返回其值 ElemType PeekQueue (Queue Q); /返回队头元素值 void ClearQueu

12、e (Queue &Q); /清空队列2、应用（选做部分）：编写程序，实现舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队， 跳舞开始时， 依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同， 则较长的那一队中未配对者等待下一轮舞曲。现要求设计一个函数 void partner() ，模拟上述舞伴配对问题。基本要求 : 1)由键盘输入数据，每对数据包括姓名和性别；2)输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称和队头者的姓名；3)要求利用 queue.h中已实现的顺序循环队列的基本操作函数来实现。函数 void partner()添加到文件 qu

13、eue.cpp中， 在主函数中进行调用测试。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 实验 5 树的应用实验目的1 熟悉二叉树结点的结构和对二叉树的基本操作。2 掌握对二叉树每一种操作的具体实现。3 学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。5 掌握构造哈夫曼树以及哈夫曼编码的方法。实验要求1 独立完成；2 程序调试正确，有执行结果。

14、实验内容1、 基础题：建立头文件 tree.h ，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件tree.cpp ，编译并调试程序，直到正确运行。注意，需要用到栈和队列的有关操作，可使用已编制过的栈和队列的基本操作文件stack.h 、queue.h 来实现。说明： 二叉树的基本操作可包括：(1) void InitBTree ( BTreeNode *&BT ) /初始化二叉树 BT (2) void CreateBTree ( BTreeNode *&BT, char *a ) /根据字符串 a 所给出的广义表表示的二叉树建立二

15、叉链表存储结构(3) int EmptyBTree ( BTreeNode *BT) /检查二叉树 BT 是否为空，空返回 1，否则返回 0 (4) int DepthBTree ( BTreeNode *BT) /求二叉树 BT 的深度并返回该值(5) int FindBTree ( BTreeNode *BT, ElemType x) /查找二叉树 BT 中值为 x 的结点，若查找成功返回1，否则返回 0 2、提高部分：(6) void PreOrder( BTreeNode *BT) /先序遍历二叉树BT (7) void InOrder( BTreeNode *BT) /中序遍历二叉树

16、 BT (8) void PostOrder( BTreeNode *BT) /后序遍历二叉树 BT (9) void LevelOrder( BTreeNode *BT ) /按层次遍历二叉树BT (10) void PrintBTree( BTreeNode *BT ) /输出二叉树 BT (11) void ClearBTree( BTreeNode *&BT ) /清除二叉树 BT 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - -

17、- - - 实验 6 图的应用实验目的1 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容（ 2 选 1）1、 图的邻接矩阵定义及实现：建立头文件 AdjM.h ，在该文件中定义图的 邻接矩阵存储结构 ，并编写图的初始化 、建立图 、输出图、输出图的每个顶点的度 等基本操作实现函数。同时建立一个验证操作实现的主函数文件AdjM.cpp （以下图为例），编译并调试程序，直到正确运行。2、图的邻接表 的定义及实现：建立头文件Ad

18、jL.h ，在该文件中定义图的 邻接表存储结构 ，并编写图的 初始化、建立图 、输出图 、输出图的每个顶点的度 等基本操作实现函数。同时在主函数文件 AdjL.cpp中调用这些函数进行验证（以下图为例）。012340 1 2 4 6 5 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 实验 7 图的应用实验目的1. 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普里姆算法。2. 掌握以邻接矩阵作为存储结构的生成图的最小生

19、成树的克鲁斯卡尔算法。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容1、 编写用 邻接矩阵 表示无向带权图时图的基本操作的实现函数，主要包括：初始化邻接矩阵表示的无向带权图void InitMatrix(adjmatrix G); 建立邻接矩阵表示的无向带权图void CreateMatrix(adjmatrix G, int n)（即通过输入图的每条边建立图的邻接矩阵） ; 输出邻接矩阵表示的无向带权图void PrintMatrix(adjmatrix G, int n) （即输出图的每条边） 。把邻接矩阵的结构定义以及这些基本操作实现函数存放在头文件Graph1.h中。2、

20、 编写生成 最小生成树的Prim 算法 函数 void Prim(adjmatrix G, edgset CT, int n)以及输出边集数组的函数void PrintEdge(edgeset CT, int n)。3、 编写测试程序（即主函数），通过调用上述函数首先建立并输出无向带权图，然后生成最小生成树 并输出（即输出边集） 。要求：把边集数组的结构定义、Prim 算法函数、输出边集数组的函数PrintEdge以及主函数存放在文件Gragh1.cpp中。测试数据如下：0 1 2 3 5 4 5 8 12 3 10 7 6 2 9 6 15 名师资料总结 - - -精品资料欢迎下载 - -

21、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 实验 8 查找与排序实验目的1 熟悉并掌握各种查找算法2 掌握排序的基本概念。3 熟悉各种内部排序的方法。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容编写程序，完成以下任务：a)通过键盘输入n 个学生的考试成绩表( 设计为一个线性表) ， 表中每个元素由姓名与分数组成；b)按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；c)按名次打印出每个学生的姓名与分数。要求：选用二种排序算法分别实现该程序中的排序要求，二种排序算法存放在头文件sort.h中。在主函数中首先输入数据，然后调用排序函数排序，并按分数高低次序打印名次与成绩表，主函数存放在文件sort.cpp中。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -