浙江师范大学

Size: px

Start display at page:

Download "浙江师范大学"

燥艇徐
5 years ago
Views:

1 软件与通信工程学院数据结构与算法实验指导书江西财经大学软件与通信工程学院通信工程系 2016 年 9 月 - 1 -

2 目录写在上机实验之前数据结构与算法( 电子 ) 课程实验教学大纲实验一线性表链式表示和实现实验二栈的应用之表达式求值实验三二叉树的遍历操作实验四图的遍历操作实验五查找与排序

3 写在上机实验之前上机实践是学生对本门课程所学知识的一种全面综合的能力训练, 是与课堂听讲自学和练习相辅相成的必不可少的一个教学环节, 也是对课堂教学与实践教学效果的一种检验通常, 实验项目中的问题比平时的习题复杂得多, 也更接近实际实习着眼于原理与应用的结合, 使学生学会如何把书上学到的知识运用于解决实际问题的过程中去, 培养从事软件开发设计工作所必需的基本技能 ; 另一方面, 能使书上的知识变活, 起到深化理解和灵活掌握教学内容的目的平时的练习较偏重于如何编写功能单一的小算法, 而实验题是软件设计的综合训练, 包括问题分析, 总体结构设计, 用户界面设计, 程序设计基本技能和技巧, 多人合作, 以至一整套软件工程规范的训练和科学作风的培养此外, 还有很重要的一点是 : 机器是比任何教师都严厉的主考者为了达到上述目的, 本篇安排了 5 个实验项目, 各项目的训练重点在于基本的数据结构, 而不强调面面俱到各实验单元与教科书的各章具有紧密的对应关系, 在个别实验单元中安排有难度差别不等的拓展练习, 以便学生选做此外, 每个实验题采取了统一的格式, 实验目的实验内容实验要求源程序清单程序运行情况等 5 个部分组成 - 3 -

4 数据结构与算法 ( 电子 ) 课程实验教学大纲课程名称 : 数据结构与算法 ( 电子 ) 英文名称 :Data Structure and Algorithms(Electronics) 课程编号 :17913 实验课性质 : 必修课程负责人 : 尧文元大纲主撰人 : 蒋娜大纲审核人 : 尧文元一学时学分课程总学时 :48 实验学时 :24 课程总学分 :3 实验学分 :0 二适用专业及年级 2014 级电子信息工程通信工程物联网工程三实验教学目的与基本要求通过上机操作, 力求能够加深学生对课堂讲授内容的理解, 掌握基本数据结构 : 集合线性结构树形结构图状结构的基本操作实现和在求解实际问题中的应用, 进一步熟悉高级程序设计语言的编程环境及其编程规则, 同时培养学生书写规范文档的习惯, 要求学生具有编制相当规模的程序的能力, 养成良好的程序设计风格对学生上机实验的要求如下 : (1) 上机实验之前, 学生应当为每次上机的内容作好充分准备对每次上机需要完成的题目进行认真的分析, 列出实验具体步骤, 写出符合题目要求的程序清单, 准备出调试程序使用的数据, 以便提高上机实验的效率 (2) 按照实验目的和实验内容以及思考题的要求进行上机操作录入程序, 编译调试, 反复修改, 直到使程序正常运行, 得出正确的输出结果为止 (3) 根据实验结果, 写出实验报告实验报告应当包括 : 实验题目, 实验目的, 实验要求, 程序实现, 实验结果以及分析讨论等内容四主要仪器设备及消耗品硬件最低要求 :586 微型计算机, 主频 450MHZ 以上, 内存 64MB 以上, 硬 - 4 -

5 序号盘 10G, 有软驱每个学生每次上机实验使用一台计算机软件 :Turbo C 或 Visual C++6.0 五实验课程内容和学时分配实验项目名称线性表链式表示和实现栈的应用之表达式求值二叉树的遍历操作实验学分实验时数每组人数实验类型实验要求实验类别 3 1 基础必做专业 6 1 综合必做专业 3 1 综合必做专业 4 图的遍历操作 6 1 综合必做专业 5 查找与排序 6 1 基础必做专业实验一线性表链式表示和实现实验要求 : 编写具有链表的创建插入和删除基本操作的程序内容提要实现链表的建立, 插入删除等基本操作实现个位数的加减乘除 ( 带括号 ) 的数学表达式的运算实现二叉树的建立递归的遍历算法和层序遍历算法的实现以邻接矩阵方式来保存图, 实现这种存储方式下创建一个图的算法然后分别使用深度优先遍历算法和广度优先遍历算法对刚才创建的图进行遍历实现折半查找算法实现希尔排序或者快速排序实验内容 : 输入链表的各个数据域的值, 同时显示创建的链表结点数据 ; 实现在第 i 个结点的之前插入一个新的结点, 并显示插入后的链表结点情况 ; 实现将第 i 个结点删除, 并将删除后的链表结点情况显示出来实验二栈的应用之表达式求值实验要求 : 掌握栈在表达式求值算法中的应用实验内容 : 输入一个个位数的数学表达式, 如 6+3*(9-5)/2-8, 并将运行程序后将结果显示在屏幕上扩展要求 : 在此基础上实现十位数的加减乘除 ( 带括号 ) 的数学表达式运算实验三二叉树的遍历操作实验要求 : 掌握递归的特点, 编写二叉树的创建和遍历基本操作的实现程序 - 5 -

6 实验内容 : 输入一个表示二叉树的字符序列 ; 运行前序中序和后序遍历算法, 将遍历后的结果显示中屏幕上在此基础上实现对二叉树的中序遍历算法的非递归实现和广度优先遍历 ( 层序遍历 ) 的实现实验四图的遍历操作实验要求 : 以邻接矩阵方式来保存图, 实现这种存储方式下创建一个图的算法然后分别使用深度优先遍历算法和广度优先遍历算法对刚才创建的图进行遍历实验内容 : 1 以邻接矩阵方式来保存图, 实现这种存储方式下创建一个图的算法 2 创建一个图, 然后对这个图进行深度优先遍历和广度优先遍历实验五查找与排序实验要求 : 1 掌握折半查找算法 2 掌握希尔排序和快速排序算法实验内容 : 1 实现折半查找算法 2 实现希尔排序和快速排序六考核方式根据学生的实验预习实验纪律实验动手能力及实验报告结果进行综合评定对缺实验成绩者, 本课程不予通过七大纲使用说明 : 本大纲所所规划的实验均为基础性和综合性实验, 也是学生必做实验实验分计入本门课程的总成绩的 30% 八实验指导书参考书数据结构与算法实验指导书. 蒋娜编.2016 年 9 月 - 6 -

7 实验一线性表链式表示和实现一实验目的 1. 掌握用 C 语言调试程序的基本方法 2. 掌握线性表的基本运算, 如创建插入删除等二实验内容输入链表的各个数据域的值, 同时显示创建的链表结点数据 ; 实现在第 i 个结点的之前插入一个新的结点, 并显示插入后的链表结点情况 ; 实现将第 i 个结点删除, 并将删除后的链表结点情况显示出来三实验要求 1. 用 C++/C 完成算法设计和程序设计并上机调试通过 2. 实验过程中学生调试完成, 需向教师演示实验过程和结果 3. 撰写实验报告, 提供实验结果和数据 4. 分析算法, 要求给出具体的算法分析结果, 包括时间复杂度和空间复杂度, 并简要给出算法设计小结和心得 5. 采用上机情况程序质量实验报告相结合的形式, 满分为 100 分 (1) 上机情况 (30%): 包括出勤情况调试表现是否上网玩游戏 (2) 程序质量 (50%) (3) 实验报告 (20%) 四程序实现 ( 要求附主要程序清单 ) 写出每个操作的算法 ( 操作过程 ) 1. 结点和单链表的 C 语言描述 typedef struct LNode{ ElemType data; // 数据域 struct LNode *next; LNode,*LinkList; // 指针域 2. 在链表 L 中第 i 个元素之前插入数据元素 e Status ListInsert_L(LinkList &L,int i,elemtype e) 3. 删除链表 L 中第 i 个数据元素 Status ListDelete_L(LinkList &L,int i,elemtype &e) 4. 创建带头结点的具有 n 结点的单链表 void CreateList_F(LinkList &L,int n) 五写出输入数据及运行结果写出可能出现的输入数据及运行结果 - 7 -

8 实验二栈的应用之表达式求值一实验目的 1 掌握栈的特点( 先进后出 FILO) 及基本操作, 如入栈出栈等, 栈的顺序存储结构和链式存储结构, 以便在实际问题背景下灵活应用 2 掌握栈在表达式求值算法中的应用, 并掌握表达式求值算法二实验内容输入一个位数的数学表达式, 如 6+3*(9-5)/2-8, 并将运行程序后将结果显示在屏幕上 [ 扩展内容 ] 在此基础上实现十位数的加减乘除 ( 带括号 ) 的数学表达式运算三实验要求 1. 用 C++/C 完成算法设计和程序设计并上机调试通过 2. 实验过程中学生调试完成, 需向教师演示实验过程和结果 3. 撰写实验报告, 提供实验结果和数据, 实验测试表达式尽可能考虑到所有的输入情况, 并给出每次测试表达式的实验结果 4. 分析算法, 要求给出具体的算法分析结果, 包括时间复杂度和空间复杂度, 并简要给出算法设计小结和心得 5. 采用上机情况程序质量实验报告相结合的形式, 满分为 100 分 (1) 上机情况 (30%): 包括出勤情况调试表现是否上网玩游戏 (2) 程序质量 (50%) (3) 实验报告 (20%) 四程序实现 ( 要求附主要程序清单 ) 写出每个操作的算法 ( 操作过程 ) 1. 表达式求值的算法思想使用数据栈有 : 算符栈 OPTR: 有效算符 ; 操作数栈 OPND: 有效操作数, 运算结果 (1) 初始化 :OPND 置为空栈, 将 # 放入 OPTR 栈底 (2) 依次读入表达式中的每个字符, 若是操作数, 则入 OPND 栈 ; 若是算符, 则和 OPTR 栈顶算符进行优先级比较 : I 若栈顶算法优先, 则执行相应运算, 结果存入 OPND 栈 ; II 若与栈顶算符相等, 则作 () 或 ## 处理 ; III 若栈顶算符低于, 该算符入 OPTR 栈 (3) 重复 (2), 直到表达式求值完毕 ( 读入的是 #, 且 OPTR 栈顶元素也为 #) - 8 -

9 2. 算符优先关系表 ( 见表 1)(C1: 栈顶元素 C2: 读到算符 ) 3. 算法的类 C 语言描述 : int express( ) { Stack_Init(OPTR);Stack_Push(OPTR, # ) ; /* 运算符栈 */ Stack_Init(OPND); /* 运算数栈 */ w=getchar(); while(w!= # Stack_GetTop(OPTR)!= # ) /* # 是表达式结束的标记, 也是运算符栈为空的标记 */ { if(!in(w,op)) { Stack_Push(OPND,w);w=getchar(); /* 不是运算符的情况 else /* 判断运算符栈顶元素和新输入运算符的优先权 */ switch(precede(stack_gettop(optr),w)) { case < : /* 栈顶元素优先权低 */ Stack_Push(OPTR,w); w=getchar(); break; case = : /* 左右括号的优先权相同, 去掉括号并接收下一个字符 */ x=stack_pop(optr); w=getchar(); break; case > : /* 栈顶元素优先权高 */ op=stack_pop(optr); b=stack_pop (OPND); a= Stack_Pop(OPND); /* a 是第一运算数,b 是第二运算数 */ Stack_Push(OPND,Operate(a,op,b)); break; return(stack_gettop(opnd)); 五写出输入数据及运行结果测试数据 :6+3*(9-5)/2-8# 2*(7-5)+6/4# 2/0# - 9 -

10 实验三二叉树的遍历操作一实验目的 1. 进一步掌握树的结构及非线性特点, 递归特点 2. 进一步巩固对指针的使用, 编写二叉树的创建和遍历基本操作的实现程序二实验内容建立一棵二叉树, 并对其进行遍历 ( 先序中序后序 ), 将遍历后的结果显示中屏幕上 [ 实验说明 ] 从键盘接受输入 ( 先序 ), 以二叉链表作为存储结构, 建立二叉树 ( 以先序来建立 ), 并采用递归算法对其进行遍历 ( 先序中序后序 ), 将遍历结果打印输出 [ 测试数据 ] ABC##DE#G##F###( 其中 ф 表示空格字符 ) 则输出结果为, 先序 :ABCDEGF 中序 :CBEGDFA 后序 :CGEFDBA [ 拓展内容 ] 二叉树的中序遍历算法的非递归实现和广度优先遍历 ( 层序遍历 ) 的实现三实验要求 1. 用 C++/C 完成算法设计和程序设计并上机调试通过 2. 实验过程中学生调试完成, 需向教师演示实验过程和结果 3. 撰写实验报告, 提供实验结果和数据 4. 分析算法, 要求给出具体的算法分析结果, 包括时间复杂度和空间复杂度, 并简要给出算法设计小结和心得 5. 采用上机情况程序质量实习报告相结合的形式, 满分为 100 分 (1) 上机情况 (30%) 包括出勤情况调试表现是否上网玩游戏 (2) 程序质量 (50%) (3) 实验报告 (20%) 四程序实现 ( 可参见课件, 要求附主要程序清单 ) 写出每个操作的算法 ( 操作过程 )

11 1. 二叉树的二叉链表存储表示 typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 BiTNode, *BiTree; 2. 二叉树的遍历操作 (1) 先序遍历 Status PreOrderTraverse(BiTree T) Status PreOrderTraverse(BiTree T) { if(t==null) return OK; else{ cout<<t->data; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); (2) 中序遍历 Status InOrderTraverse(BiTree T) Status InOrderTraverse(BiTree T) { if(t==null) return OK; // 空二叉树 else{ InOrderTraverse(T->lchild); // 递归遍历左子树 cout<<t->data; // 访问根结点 InOrderTraverse(T->rchild); // 递归遍历右子树 (3) 后序遍历 Status PostOrderTraverse(BiTree T) Status PostOrderTraverse(BiTree T) { if(t==null) return OK; // 空二叉树 else{ PostOrderTraverse(T->lchild); // 递归遍历左子树 PostOrderTraverse(T->rchild); // 递归遍历右子树 cout<<t->data; // 访问根结点

12 3. 中序遍历非递归算法, 其中栈的相关操作请自行定义 Void InorderTraverse(BiTreee T) {// 中序遍历二叉树 T 的非递归算法 InitStack(S);p=T; q=new BiTNode; while(p StackEmpty(S)) { if(p) { pusj(s,p); P=p->lchild; else { Pop(S,q); cout<<q->data; p=q->rchild; 4. 二叉树的层序遍历算法,, 其中队列的相关操作请自行定义 void levelorder(bitree t){ BiTree c,cc; Queue q=createmptyqueue(); // 队列元素为 BiTree 类型 if(t==null) return; c=t; enqueue(q,c); // 将二叉树送入队列 while(!isemptyqueue(q)) { c=frontqueue(q); dequeue(q); cout<<c->data; // 从队列首部取出二叉树并访问 cc=c->lchild; if(cc!=null) enqueue(q,cc); // 将左子树送入队列 cc=c->rchild; if(cc!=null) enqueue(q,cc); // 将右子树送入队列五写出输入数据及运行结果写出可能出现的输入数据及运行结果

13 实验四图的遍历操作一实验目的 1. 进一步掌握图的结构及非线性特点 2. 进一步巩固对指针的使用, 编写图的创建和遍历基本操作的实现程序二实验内容很多涉及图上操作的算法都是以图的遍历操作为基础的试写一个程序, 演示无向图的遍历操作 [ 实验说明 ] 以邻接矩阵为存储结构, 实现连通无向图的深度优先和广度优先遍历以用户指定的结点为起点, 分别输出每种遍历下的结点访问序列 [ 实现提示 ] 设图的结点不超过 30 个, 每个结点用一个编号表示 ( 如果一个图有 n 个结点, 则它们的编号分别为 1,2,,n) 通过输入图的全部边输入一个图, 每个边为一个数对, 可以对边的输入顺序作出某种限制 [ 拓展内容 ] (1) 借助于栈类型 ( 自己定义和实现 ) 将深度优先遍历用非递归算法实现 (2) 建立深度优先生成树和广度优先生成树, 再按凹入表或树形打印生成树 (3) 实现有向图的遍历操作三实验要求 1. 用 C++/C 完成算法设计和程序设计并上机调试通过 2. 实验过程中学生调试完成, 需向教师演示实验过程和结果 3. 撰写实验报告, 提供实验结果和数据 4. 分析算法, 要求给出具体的算法分析结果, 包括时间复杂度和空间复杂度, 并简要给出算法设计小结和心得 5. 采用上机情况程序质量实习报告相结合的形式, 满分为 100 分 (1) 上机情况 (30%) 包括出勤情况调试表现是否上网玩游戏 (2) 程序质量 (50%) (3) 实验报告 (20%) 四程序实现 ( 可参见课件, 要求附主要程序清单 ) 写出每个操作的算法 ( 操作过程 ) 1. 邻接矩阵的存储表示 typedef char VerTexType; // 假设顶点的数据类型为字符型

14 typedef int ArcType; // 假设边的权值类型为整型 typedef struct{ VerTexType vexs[mvnum]; // 顶点表 ArcType arcs[mvnum][mvnum]; // 邻接矩阵 int vexnum, arcnum; // 图的当前点数和边数 AMGraph; 2. 采用邻接矩阵表示法创建无向图 Status CreateUDN(AMGraph &G) 3. 邻接矩阵存储的深度优先遍历 void DFS (AMGraph G, int v){ // 图 G 为邻接矩阵类型 cout<<v; visited[v] = true; // 访问第 v 个顶点 for(w = 0; w< G.vexnum; w++) // 依次检查邻接矩阵 v 所在的行 if((g.arcs[v][w]!=0)&& (!visited[w])) DFS(G, w); //w 是 v 的邻接点, 如果 w 未访问, 则递归调用 DFS void DFSTraverse(Graph G) { // 对图 G 作深度优先遍历 for (v=0; v<g.vexnum; ++v) visited[v] = FALSE; for (v=0; v<g.vexnum; ++v) if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用 DFS 4. 图的广度优先遍历, 其中队列的相关操作请自行定义 void BFS (Graph G, int v){ // 按广度优先非递归遍历连通图 G cout<<v; visited[v] = true; // 访问第 v 个顶点 InitQueue(Q); // 辅助队列 Q 初始化, 置空 EnQueue(Q, v); //v 进队 while(!queueempty(q)){ // 队列非空 DeQueue(Q, u); // 队头元素出队并置为 u for(w = FirstAdjVex(G, u); w>=0; w = NextAdjVex(G, u, w)) if(!visited[w]){ //w 为 u 的尚未访问的邻接顶点 cout<<w; visited[w] = true; EnQueue(Q, w); //w 进队

15 //if //while //BFS void BFSTraverse(Graph G) { // 对图 G 作广度优先遍历 for (v=0; v<g.vexnum; ++v) visited[v] = FALSE; for (v=0; v<g.vexnum; ++v) if (!visited[v]) BFS(G, v); // 对尚未访问的顶点调用 BFS 五写出输入数据及运行结果输入数据及运行结果, 要求在实验报告中画出所创建的图, 程序运行结果输出图的邻接矩阵

16 实验五查找与排序一实验目的 1. 进一步掌握有序顺序表的折半查找算法 2. 进一步巩固排序的算法, 编写对 20 个及以上的无序数据进行希尔排序和快速排序的实现程序二实验内容 1. 建立一 20 个及以上数据的有序顺序表, 表中可以仅存放记录的关键字, 实现对该有序的折半查找算法, 测试数据应充分考虑查找成功和查找不成功两种情况 2. 建立一 20 个及以上数据的无序顺序表, 表中可以仅存放记录的关键字, 实现对该无序表进行希尔排序, 给出每一趟希尔排序的结果 2. 建立一 20 个及以上数据的无序顺序表, 表中可以仅存放记录的关键字, 实现对该无序表进行快速排序, 给出每一趟快速排序的结果三实验要求 1. 用 C++/C 完成算法设计和程序设计并上机调试通过 2. 实验过程中学生调试完成, 需向教师演示实验过程和结果 3. 撰写实验报告, 提供实验结果和数据 4. 分析算法, 要求给出具体的算法分析结果, 包括时间复杂度和空间复杂度, 并简要给出算法设计小结和心得 5. 采用上机情况程序质量实习报告相结合的形式, 满分为 100 分 (1) 上机情况 (30%) 包括出勤情况调试表现是否上网玩游戏 (2) 程序质量 (50%) (3) 实验报告 (20%) 四程序实现 ( 可参见课件, 要求附主要程序清单 ) 写出每个操作的算法 ( 操作过程 ) 1. 顺序表的定义 typedef struct { int *R; // 表基址 int length; // 表长 SSTable; 2. 折半查找算法 int Search_Bin ( SSTable ST, KeyType key ) { // 在有序表 ST 中折半查找其关键字等于 key 的数据元素

17 // 若找到, 则函数值为该元素在表中的位置, 否则为 0 low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if (key == ST.R[mid].key ) return mid; // 找到待查元素 else if ( key < ST.R[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 return 0; // 顺序表中不存在待查元素 // Search_Bin 3. 一趟希尔排序算法 void ShellInsert(SqList &L,int dk) { for(i=dk+1;i<=l.length; ++ i) if(l.r[i].key <L. r[i-dk].key) { L.r[0]=L.r[i]; for(j=i-dk;j>0&&(l.r[0].key<l.r[j].key);j=j-dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0]; 希尔排序算法 void ShellSort(SqList &L,int dlta[ ],int t){ // 按增量序列 dlta[0 t-1] 对顺序表 L 作 Shell 排序 for(k=0;k<t;++k) ShellInsert(L,dlta[k]); // 增量为 dlta[k] 的一趟插入排序 // ShellSort 4. 一次划分 int Partition (SqList &L, int low, int high) 快速排序算法 void QSort (SqList &L, int low, int high ) { // 对记录序列 R[s..t] 进行快速排序

18 if (low < high) { // 长度大于 1 pivotloc = Partition(L, low, high); // 对 L.r[low..high] 进行一次划分, pivotloc 枢轴位置 QSort(L, low, pivotloc-1); // 对低子序列递归排序 QSort(L, pivotloc+1, high); // 对高子序列递归排序 // QSort void QuickSort( SqList & L) {// 对顺序表 L 进行快速排序 QSort(L, 1, L.length); // QuickSort 五写出输入数据及运行结果输入数据及运行结果, 要求在实验报告中详尽全面的运行结果

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378>

<4D F736F F D B8BDBCFE4220D7A8D2B5BBF9B4A1D3EBBACBD0C4BFCEB3CCC3E8CAF62E646F6378> B212CC: 数据结构与算法课程描述 0 课程基本信息课程编号 : B212CC 课程名称 : 数据结构与算法英文名称 : Data Structures and Algorithms 英文简称 : DSA 预备课程 : 计算系统基础离散数学授课时间 : 二年级第一学期时间分配 : 课堂教学 (48 课时 )+ 实验安排 (48 课时 )+ 课后作业与阅读 (48 课时 ) 学分数 : 3