数据结构实验2012

1、数据结构实验第一节 概述一、实验目的实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的练习题要复杂，也更接近实际。实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。本实验指导书仅列出一个实验项目下一个实验题存储结构、算法；供其他实验题作为参考。二、实验名称与学时分配序号实 训 名 称学时数1线性表的算法设计及应用42栈的算法设计与应用43基于队列的基数排序算法设计与应用44串的算法设计与应用5二叉树的算法设计及应用46图的算法设计与应用4 5

2、查找算法设计 6排序算法设计三、实验考核每次实验结束后，均应上交实验报告。实验成绩占数据结构课程结业成绩的20%。实验报告应包括如下内容： 1、问题描述：简述题目要解决的问题是什么。2、设计：包括存储结构设计、主要算法设计等。用类C语言或用框图描述。3、调试报告：调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、算法分析与改进：算法的时间复杂度和空间复杂度分析；算法改进的设想。5、经验和体会附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。四、实验时间安排16学时。五、选题

3、安排实验1，5，6必做，实验2和实验3两题选作1题，实验报告上交4个实验。其余题选作。第二节 线性表算法设计及应用一、目的与要求（一）目的了解线性表及在计算机中的两类不同的存储结构；熟练掌握线性表的查找、插入和删除等算法并灵活运用这些算法。（二）要求用C语言编写程序，实现多项式求值或求解约瑟夫问题。二、示例1、题目 报数问题编号为1，2，···，n的n个人围坐在一圆桌旁，从第s个人开始报数，报到第m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。例如，设s=1，m=4，n=8，则退席的人的编号依次为4，8，5，2，1，3，7，6。2、存储结构

4、（1）以顺序表为存储结构 int pn; / n常量 （2）以循环链表为存储结构typedef struct lnodeint data;struct lnode *next; lnode；3、算法设计（1）void josephus_1(int p, int m, int n) int i,j,t; for(i=0;i<=n-1;i+) pi=i+1; /p0.pn-1：n个人 t=0; /第一次报数的位置 (第一人的位置) for(i=n;i>=1;i-) t=(t+m-1)%i ; / t：定位于第m人，i：当前圆桌上的人数，%：实现环（圆桌）的处理 cout<<

5、pt<<" " / 输出第m人信息（第m人报数） for (j=t+1;j<=i-1;j+) pj-1=pj; /元素前移（第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;j<=m-1;+j) p=p->next; /p后移m-1次，定位于m-1处（要退席的人之前）s=p->next; /s定位于m人（要退席的人）cout<<

6、;s->data<<" " /第m人报数 p->next=s->next; delete s ; /第m人退席，删除第m人 4、小结线性表是软件设计中最基础的数据结构。用顺序方法存储的线性表称为顺序表，当线性表中很少做插入和删除操作，线性表的长度变化不大，易于事先确定其大小时，可以采用顺序表作为存储结构。用链接方法存储的线性表称为线性链表，当线性表的长度变化较大，难以估计其存储规模，另外对线性表频繁进行插入和删除操作时，则采用链表作为存储结构可能会更好一些。在实际应用中应该考虑以下因素：（）应有利于运算的实现；（）应有利于数据的特性；（）应有利

7、于软件环境。三、实验题实验题1.1 问题描述：有两个指数递减的一元多项式，写一程序先求这两个多项式的和，再求它们的积。提示1：用带表头结点的单链表作为多项式的存储表示；要建立两个单链表；多项式相加就是要把一个单链表中的结点插入到另一个单链表中去，要注意插入、删除操作中指针的正确修改。实验题1.2 问题描述：编号为1，2，···，n的n个人围坐在一圆桌旁，每人持有一个正整数的密码。从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7

8、，7个人的密码依次是3，1，7，2，4，8，4，则退席的人的编号依次为6，1，4，7，2，3，5。提示2：用不带表头结点的循环单链表表示围成圆圈的n个人；建立此循环单链表；某人离席相当于删除一个结点要正确设置程序中循环终止的条件和删除结点时指针的修改变化。第三节 栈和队列的算法设计及应用一、目的与要求（一）目的了解栈和队列的特点及存储结构；熟练掌握栈和队列的算法实现; 运用栈和队列的算法求解应用问题。（二）要求 用C语言实现运算器问题或魔王语言解释。二、示例1、题目 表达式求值2、表达式的表示 前缀表达式 *3-72中缀表达式 3*(7-2)后缀表达式 372-*3、算法设计 int valE

9、xpression () /后缀表达式求值 initstack(S)；/ 初始化栈S while (w=getchar()!=) /=:表达式结束标志 if (w=+)| (w=-) |(w=*)|(w=/) pop(s,a); pop(s,b); push(s,operate(b,w,a); / 从操作数栈中取2个操作数，进行运算，并将计算结果入栈 / operate(b,w,a); /b+a or b-a or b*a or b/a运算 else push(s,w); / 操作数进栈 中缀表达式求值算法见教材算法3.4；思考：前缀表达式求值算法。4、小结 栈和队列都是特殊的线性表，他们的逻

10、辑结构和存储结构与线性表是一样的，不同的是运算受限。栈是限定在一端进行插入和删除的线性表，其特点是后进先出，队列是限定在一端进行插入另一端进行删除的线性表，其特点是先进先出。在本章中，应熟练掌握栈和队列的基本算法，解决表达式计算问题、递归程序设计问题和排队等问题。三、实验题实验题2.1：算术运算器设计 问题描述 设计一个模拟计算器功能的程序，它读入一个表达式，如果是一个正确的表达式（即它由操作数、圆括号和+、-、*、/四种运算符组成），则求出该表达式的值；否则给出某种错误信息。提示：读入一个以字符序列形式给出的以等号（=）结尾的表达式；程序中应考虑运算符的优先级、运算的合法性。实验题2.2：魔

11、王语言解释。 问题描述 有一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的： （1） 12m （2） (12m)(m21) 在这两种形式中，从左到右均表示解释； 从右到左均表示抽象。 写一个魔王解释程序，将魔王的话解释成人能听懂的话。 基本要求：设大写字母表示魔王语言的词汇，小写字母表示人的词汇，希腊字母表示可以用大写字母或小写字母代换的变量。用下述两种规则和下述规则（2）实现。 (1) BtAdA(2) Asae测试数据：B(einxgz)BB(einxgz)B=>t

12、AdA(einxgz)tAdA=>tsaedsae(einxgz)tsaedsae => tsaedsaeezegexeneietsaedsae字母-汉字对应表:tdsaezgxni天 在 上一个鹅追赶下蛋恨则魔王说的是：“天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。提示：该题中涉及栈、队列和线性表。（）利用队列处理B：tsaedsae （由BtAdA, Asae得）（2） 利用栈处理：(12m)(m21)（）利用线性表（字母-汉字对应表）进行魔王语言解释。第四节 二叉树算法设计及应用一、目的与要求（一）目的了解二叉树及存储结构；掌握建立哈夫曼树的方法，实现哈

13、夫曼编码。（二）要求 用C语言实现哈夫曼编码。二、示例1、问题构造huffman树。2、huffman树的构造方法 (1) 给定w1,w2,.,wn, 构成F=T1,T2,.,Tn, 每个树只有一个根结点;(2) 选择两个根结点最小的二叉树,作为lchild和rchild, 构成一新的二叉树;, 直至一棵树止。3、存储结构 typedef struct int weight;int parent, lchild, rchild; HTNode ,*HuffmanTree; / 动态分配数组存储huffman树4、算法设计void createHuffmantree() ht=(HuffmanT

14、ree)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.weight=wi; /初始化，wi：n个叶子的权值 for (i=n+1;i<=m,+i) /建哈夫曼树 select(i-1),s1,s2); /在htk(1<=k<=i-1)中选择两个双亲域为零而权值取最小的结点 :s1和s2 hts1.parent= h

15、ts2.parent=i; hti.lch=s1; hti.rch=s2; hti.weight=hts1.weight + hts2.weight ; ;5、小结树与二叉树是数据结构的重点章节，树（层次）结构是软件设计中常用的非线性结构。Huffman树是二叉树的应用之一，可以用于数据压缩等问题的描述。三、实验题实验题3：赫夫曼编码及译码问题描述：对任意输入的一段英文，为每个字符编制其相应的赫夫曼编码；并利用该编码为任意输入的0、1序列进行解码 基本要求：一个完整的系统应具有以下功能：（1）初始化 从终端读入一段英文字符，统计每个字符出现的频率，建立赫夫曼树，并将该树存入某文件；（2）编码

16、利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在屏幕上，并将编码结果存入另一文件中； （3）解码 利用保存的赫夫曼编码，对任意输入的0，1序列能正确解码； 第五节 图的算法设计及应用一、目的与要求（一）目的了解图的存储结构，掌握并灵活运用图的算法。（二）要求 利用图的基本算法解决接近于实际的问题，并用C语言实现。二、示例1、问题用FLOYD算法求图的最短路径问题 2、FLOYD算法思想( 详见教材7.6.2节)3、存储结构:用邻接矩阵表示无向网4、算法设计: 详见教材算法7.165、小结图是一种复杂的数据结构，在解决实际问题中应用很广泛。学习本章应熟悉图的各种存储结构，了解在解决实际问题中应采取何种存储结构，如何选择最合适的算法。三、实验题实验题4-1 为新建医院选址问题描述：n个村庄之间的无向图，边上的权值w(i,j)表示村庄i和j之间道路长度现要从这n个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短设计一程序求解此问题 基本要求：用邻接矩阵表示无向网，应显示所选中的村庄到各村庄的最短距离。实验题4-2 高速公路收费