《2022年数据结构实验 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构实验第一节概述一、实验目的实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的练习题要复杂，也更接近实际。实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。本实验指导书仅列出一个实验项目下一个实验题存储结构、算法；供其他实验题作为参考。二、实验名称与学时分配序号实训名称学时数1 线性表的算法设计及应用4 2 栈的算法设计与应用4 3 基于队列的基数排序算法设计与应用4 4 串的算法设计与应用5 二叉树的算法设计及应用4 6 图的算法设计
2、与应用4 5 查找算法设计 6 排序算法设计三、实验考核每次实验结束后，均应上交实验报告。实验成绩占数据结构课程结业成绩的20%。实验报告应包括如下内容：1、问题描述：简述题目要解决的问题是什么。2、设计：包括存储结构设计、主要算法设计等。用类C语言或用框图描述。3、调试报告：调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、算法分析与改进：算法的时间复杂度和空间复杂度分析；算法改进的设想。5、经验和体会附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。四、实验时间安排16
3、 学时。五、选题安排实验 1，5，6 必做，实验2 和实验 3 两题选作1 题，实验报告上交4 个实验。其余题选作。第二节线性表算法设计及应用一、目的与要求（一）目的了解线性表及在计算机中的两类不同的存储结构；熟练掌握线性表的查找、插入和删除等算法并灵活运用这些算法。（二）要求用 C语言编写程序，实现多项式求值或求解约瑟夫问题。二、示例1、题目报数问题名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -编号为 1，2，n 的 n 个人围坐在一圆桌旁，从第s 个人开始报数，报到第m的人退席，下一个人又重新从1 开始报数，依此重复，直至所有的人都退席。例如，设 s=1，m=4，
4、n=8，则退席的人的编号依次为4，8，5，2，1，3，7，6。2、存储结构（1）以顺序表为存储结构 int pn;/n常量（2）以循环链表为存储结构typedef struct lnode int data;struct lnode *next;lnode；3、算法设计（1）void josephus_1(int p,int m,int n)int i,j,t;for(i=0;i=1;i-)t=(t+m-1)%i;/t：定位于第m人，i：当前圆桌上的人数，%：实现环（圆桌）的处理 coutpt;/输出第 m人信息（第m人报数）for(j=t+1;j=i-1;j+)pj-1=pj;/元素前移（第
5、m人退席，删除第m人）（2）void josephus_2(lnode*r,int m,int n)/r：（不带头结点的）单向循环链表的尾指针Lnode*p=r;/p：指向尾指针for(i=1;i=n;+i)for(j=1;jnext;/p后移 m-1 次，定位于m-1 处（要退席的人之前）s=p-next;/s定位于 m人（要退席的人）coutdatanext=s-next;delete s;/第 m人退席，删除第m人 4、小结线性表是软件设计中最基础的数据结构。用顺序方法存储的线性表称为顺序表，当线性表中很少做插入和删除操作，线性表的长度变化不大，易于事先确定其大小时，可以采用顺序表作为存
6、储结构。用链接方法存储的线性表称为线性链表，当线性表的长度变化较大，难以估计其存储规模，另外对线性表频繁进行插入和删除操作时，则采用链表作为存储结构可能会更好一些。在实际应用中应该考虑以下因素：（）应有利于运算的实现；（）应有利于数据的特性；（）应有利于软件环境。三、实验题实验题 1.1问题描述：有两个指数递减的一元多项式，写一程序先求这两个多项式的和，再求它们的积。提示 1：用带表头结点的单链表作为多项式的存储表示；要建立两个单链表；多项式相加就是要把一个单链表中的结点插入到另一个单链表中去，要注意插入、删除操作中指针的正确修改。实验题 1.2问题描述：编号为1，2，n 的 n 个人围坐在一
7、圆桌旁，每人持有一个正整数的密码。从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1 开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7，7 个人的密码依次是3，1，7，2，4，8，4，名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -则退席的人的编号依次为6，1，4，7，2，3，5。提示 2：用不带表头结点的循环单链表表示围成圆圈的n 个人；建立此循环单链表；某人离席相当于删除一个结点要正确设置程序中循环终止的条件和删除结点时指针的修改变化。第三节栈和队列的算法设计及应用一、目的与要
8、求（一）目的了解栈和队列的特点及存储结构；熟练掌握栈和队列的算法实现;运用栈和队列的算法求解应用问题。（二）要求用 C语言实现运算器问题或魔王语言解释。二、示例1、题目表达式求值2、表达式的表示前缀表达式 *3-72 中缀表达式 3*(7-2)后缀表达式 372-*3、算法设计 int valExpression()/后缀表达式求值 initstack(S)；/初始化栈 S while(w=getchar()!=)/=:表达式结束标志 if(w=+)|(w=-)|(w=*)|(w=/)pop(s,a);pop(s,b);push(s,operate(b,w,a);/从操作数栈中取2 个操作数，
9、进行运算，并将计算结果入栈 /operate(b,w,a);/b+a or b-a or b*a or b/a运算 else push(s,w);/操作数进栈 中缀表达式求值算法见教材算法3.4；思考：前缀表达式求值算法。4、小结栈和队列都是特殊的线性表，他们的逻辑结构和存储结构与线性表是一样的，不同的是运算受限。栈是限定在一端进行插入和删除的线性表，其特点是后进先出，队列是限定在一端进行插入另一端进行删除的线性表，其特点是先进先出。在本章中，应熟练掌握栈和队列的基本算法，解决表达式计算问题、递归程序设计问题和排队等问题。三、实验题实验题 2.1：算术运算器设计问题描述设计一个模拟计算器功能的
10、程序，它读入一个表达式，如果是一个正确的表达式（即它由操作数、圆括号和+、-、*、/四种运算符组成），则求出该表达式的值；否则给出某种错误信息。提示：读入一个以字符序列形式给出的以等号（=）结尾的表达式；程序中应考虑运算符的优先级、运算的合法性。实验题 2.2：魔王语言解释。问题描述有一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）12,m（2）(12,m)(m,2 1)在这两种形式中，从左到右均表示解释；从右到左均表示抽象。写一个魔王解释程序，将魔王的话解释成人能听
11、懂的话。基本要求：设大写字母表示魔王语言的词汇，小写字母表示人的词汇，希腊字母表示可以用大写字母或小写字母代换的变量。用下述两种规则和下述规则（2）实现。(1)BtAdA(2)A sae 测试数据：B(einxgz)B 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -B(einxgz)B=tAdA(einxgz)tAdA=tsaedsae(einxgz)tsaedsae=tsaedsaeezegexeneietsaedsae 字母-汉字对应表:t d s a e z g x n i 天在上一个鹅追赶下蛋恨则魔王说的是：“天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个
12、鹅地上一个鹅”。提示：该题中涉及栈、队列和线性表。（）利用队列处理B：tsaedsae（由 B tAdA,A sae 得）（2）利用栈处理：(12,m)(m,2 1)（）利用线性表（字母-汉字对应表）进行魔王语言解释。第四节二叉树算法设计及应用一、目的与要求（一）目的了解二叉树及存储结构；掌握建立哈夫曼树的方法，实现哈夫曼编码。（二）要求用 C语言实现哈夫曼编码。二、示例1、问题构造 huffman 树。2、huffman 树的构造方法(1)给定 w1,w2,.,wn,构成 F=T1,T2,.,Tn,每个树只有一个根结点;(2)选择两个根结点最小的二叉树,作为 lchild和 rchild,构
13、成一新的二叉树;,直至一棵树止。3、存储结构 typedef struct int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储huffman 树4、算法设计void createHuffmantree()ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/动态分配数组存储huffman 树,号单元未用/m:huffman 树中的结点数（m=2*n-1）for(i=1;i=m;+i)hti.parent=hti.lch=hti.rch=0;for(i=1;i=n;+i)hti.we
14、ight=wi;/初始化，wi：n 个叶子的权值 for(i=n+1;i=m,+i)/建哈夫曼树 select(i-1),s1,s2);/在 htk(1=k=i-1)中选择两个双亲域为零而权值取最小的结点:s1和 s2 hts1.parent=hts2.parent=i;hti.lch=s1;hti.rch=s2;hti.weight=hts1.weight+hts2.weight;5、小结树与二叉树是数据结构的重点章节，树（层次）结构是软件设计中常用的非线性结构。Huffman 树是二叉树的应用之一，可以用于数据压缩等问题的描述。三、实验题名师资料总结-精品资料欢迎下载-名师精心整理-第 4
15、 页，共 5 页 -实验题 3：赫夫曼编码及译码问题描述：对任意输入的一段英文，为每个字符编制其相应的赫夫曼编码；并利用该编码为任意输入的0、1 序列进行解码基本要求：一个完整的系统应具有以下功能：（1）初始化从终端读入一段英文字符，统计每个字符出现的频率，建立赫夫曼树，并将该树存入某文件；（2）编码利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在屏幕上，并将编码结果存入另一文件中；（3）解码利用保存的赫夫曼编码，对任意输入的0，1 序列能正确解码；第五节图的算法设计及应用一、目的与要求（一）目的了解图的存储结构，掌握并灵活运用图的算法。（二）要求利用图的基本算法解决接近于实际的问题，并
16、用C语言实现。二、示例1、问题用 FLOYD 算法求图的最短路径问题2、FLOYD算法思想(详见教材 7.6.2节)3、存储结构:用邻接矩阵表示无向网4、算法设计:详见教材算法7.16 5、小结图是一种复杂的数据结构，在解决实际问题中应用很广泛。学习本章应熟悉图的各种存储结构，了解在解决实际问题中应采取何种存储结构，如何选择最合适的算法。三、实验题实验题 4-1 为新建医院选址问题描述：n 个村庄之间的无向图，边上的权值w(i,j)表示村庄 i 和 j 之间道路长度 现要从这 n 个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短设计一程序求解此问题基本要求：用邻接矩阵表示无
17、向网，应显示所选中的村庄到各村庄的最短距离。实验题 4-2 高速公路收费程序设计问题描述：在一个高速公路网一无向图表示，边上的权值w(i,j)表示入口到出口的道路长度。任意一辆汽车可以从任一入口进入到任一出口驶出。写一高速公路收费程序，注意要考虑各种不同的车辆收费标准不同。实验题 4-3 公交线路问题问题描述：假设以一个带权有向图表示某一城市的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。而且要求输出最短路径。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -