数据结构(2)实验报告二
数据结构（2）上机实验报告报告二
实验名称K叉Huffman树
小组成员12125804肖凯雷
12125802 刘世洋
12125806 张涛
计算机工程与科学学院
报告日期2015年4 月12 日
1.实验名称：K叉Huffman树
【问题描述】设某系统在通信联系中可能出现n种字符，在通信中它们出现的频率分别为：p1、p2、…、pn。如果电文中只允许出现0、1、2三个码值。请构造这n种字符的最优不等长前缀编码。
【基本要求】输入通信联系中出现的n种字符以及出现的频率：p1、p2、…、pn。以这n种字符的出现频率为权，通过构造3叉Huffman树，对这n种字符构造最优不等长前缀编码。
【测试数据】
假设n=9，对应字符分别为：A、B、…、I，它们在通信中出现的频率分别为：0.15、0.01、0.11、0.14、0.09、0.04、0.19、0.24、
0.03。
【测试用例】：
1)、码值：AABBCCC
预测对应Huffman编码：11，22，000
运行结果：
2)、增加一个空数组，其权值为0，假设{A,B,C,D}对应权值分别为{3,4,5,6}
预测结果：02,1,00,2 若为空则为：01
运行结果：
3)、码值：ABCDEABCCE
预测对应Huffman编码：02,00,2,01,1, 02 00, 2 ,2 ,1
运行结果：
4)、码值：ABCDEFGGADCB
预测对应Huffman编码：20,01,02,00,21,22,1,1,20,00,02,01 运行结果：
2.任务分配：
肖凯雷：上机实验报告
刘世洋：代码，编程实现
张涛：研讨PPT，测试数据
3.源代码：
#ifndef __HUFFMAN_TREE_H__
#define __HUFFMAN_TREE_H__
#include "String.h" // 串类
#include "HuffmanTreeNode.h" // 哈夫曼树结点类
// 哈夫曼树类
template
class HuffmanTree
{
protected:
// 哈夫曼树的数据成员:
HuffmanTreeNode
CharType *LeafChars; // 叶结点字符信息
String *LeafCharCodes; // 叶结点字符编码信息
int num; // 叶结点个数
// 辅助函数:
void Select(int n, int &r1, int &r2,int &r3); // 在nodes[0 ~ n-1]中选择双亲为0,权值最小的两个结点r1,r2
void CreatHuffmanTree(CharType ch[], WeightType w[], int n);
// 由n个字符和权值创建一棵哈夫曼树
public:
// 哈夫曼树方法声明及重载编译系统默认方法声明:
HuffmanTree(CharType ch[], WeightType w[], int n); // 由n个字符和权值构造哈夫曼树
virtual ~HuffmanTree(); // 析构函数
String Encode(CharType ch); // 编码
LinkList
HuffmanTree(const HuffmanTree
HuffmanTree WeightType>& copy); // 赋值运算符重载 }; // 孩子兄弟表示哈夫曼树类的实现部分 template void HuffmanTree // 操作结果：在nodes[0 ~ n-1]中选择双亲为0,权值最小的两个结点r1,r2 { r3 = r1 = r2 = -1; for (int i = 0; i < n; i++) // 查找树值最小的两个结点 if (nodes[i].parent == -1) // 只处理双亲不为-1的结点 if (r1 == -1) r1 = i; else if (nodes[i].weight < nodes[r1].weight) { r2 = r1; r1 = i; } else if (r2 == -1 || nodes[i].weight < nodes[r2].weight){ r3 = r2; r2 = i; } else if(r3 ==-1 || nodes[i].weight< nodes[r3].weight){ r3=i; } } template void HuffmanTree { num = n; // 叶结点个数 int m = (3 * n - 1)/2; // 结点个数 nodes = new HuffmanTreeNode LeafChars = new CharType[n]; LeafCharCodes = new String[n]; int i, p, q; for (i = 0; i < n; i++) { // 存储叶结点信息 nodes[i].weight = w[i]; nodes[i].firstChild = -1; nodes[i].secondChild = -1; nodes[i].thirdChild =-1; nodes[i].parent = -1; LeafChars[i] = ch[i]; } for (i = n; i < m; i++){ // 构造哈夫曼树 int r1, r2,r3; Select(i, r1, r2,r3); // 合并以r1,r2，r3为根的树 nodes[r1].parent = nodes[r2].parent =nodes[r3].parent= i;// r1,r2的双亲为i nodes[i].firstChild = r1; // r1为i的第一个孩子 nodes[i].secondChild = r2; // r2为i的第二个孩子 nodes[i].thirdChild = r3; //r3 为i的第三个孩子 nodes[i].parent = -1; // i为新的根结点 nodes[i].weight = nodes[r1].weight + nodes[r2].weight+ nodes[r3].weight;//i的权为r1,r2的权值之和 } for (i = 0; i < n; i++) { // 求n个叶结点字符的编码 LinkList q = i; p = nodes[q].parent; while (p != -1) { // 从叶结点到根结点逆向求编码 if (nodes[p].firstChild == q) {charCode.InsertElem(1, '1');}// 第一个孩子分支编码为'1' else if(nodes[p].secondChild == q) {charCode.InsertElem(1, '2');}// 第二个孩子分支编码为'2' else if(nodes[p].thirdChild == q) {charCode.InsertElem(1,'0');} //第三个孩子分支编码为'0’ q = p; p = nodes[q].parent; } LeafCharCodes[i] = charCode; // 复制字符编码 } } template HuffmanTree // 操作结果：由字符,权值和字符个数构造哈夫曼树 { CreatHuffmanTree(ch, w, n); // 由字符,权值和字符个数构造哈夫曼树 } template HuffmanTree // 操作结果：销毁哈夫曼树 { if (nodes != NULL) delete []nodes; // 释放结点信息 if (LeafChars != NULL) delete []LeafChars; // 释放叶结点字符信息 if (LeafCharCodes != NULL) delete []LeafCharCodes; // 释放叶结点字符编码信息 } template String HuffmanTree // 操作结果：返回字符编码 { for (int i = 0; i < num; i++) // 找到字符,得到编码 if (LeafChars[i] == ch) return LeafCharCodes[i]; throw Error("非法字符,无法编码!"); // 抛出异常 } template LinkList // 操作结果：对编码串strCode进行译码,返回编码前的字符序列 { LinkList int p = (3* num - 3)/2; for (int i = 0; i < strCode.GetLength(); i++) { // 处理每位编码 if (strCode[i] == '1') { p = nodes[p].firstChild;} // '2'表示第一个孩子分支 else if(strCode[i] == '2') {p = nodes[p].secondChild;} // '1'表示第二个孩子分支 else if(strCode[i] == '0') {p = nodes[p].thirdChild;} if (nodes[p].firstChild == -1 && nodes[p].secondChild == -1 && nodes[p].thirdChild == -1) { // 译码时从根结点开始搜索到一个叶结点 charList.InsertElem(charList.GetLength() + 1, LeafChars[p]); p = (3 * num - 3)/2; // 从根开始重新搜索 } } if (p != (3 * num - 3)/2) //最后一段代码没有对应字符 throw Error("编码不对,无法译码!"); // 抛出异常 return charList; // 返回编码前的字符序列 } template HuffmanTree // 操作结果：由哈夫曼树copy构造新哈夫曼树——复制构造函数 { num = copy.num; // 叶结点个数 int m = (3 * num - 1)/2; // 结点总数 nodes = new HuffmanTreeNode LeafChars = new CharType[num]; LeafCharCodes = new String[num]; int i; for (i = 0; i < m; i++) // 复制结点信息 nodes[i] = copy.nodes[i]; for (i = 0; i < num; i++) { LeafChars[i] = copy.LeafChars[i]; // 复制叶结点字符信息 LeafCharCodes[i] = copy.LeafCharCodes[i];// 复制叶结点字符编码信息 } } template HuffmanTree // 操作结果：将哈夫曼树copy赋值给当前哈夫曼树——赋值运算符重载 { if (© != this) { if (nodes != NULL) delete []nodes; // 释放结点信息 if (LeafChars != NULL) delete []LeafChars; // 释放叶结点字符信息 if (LeafCharCodes != NULL) delete []LeafCharCodes; // 释放叶结点字符编码信息 num = copy.num; // 叶结点个数 int m = (3 * num - 1)/2; // 结点总数 nodes = new HuffmanTreeNode LeafChars = new CharType[num]; LeafCharCodes = new String[num]; int i; for (i = 0; i < m; i++) // 复制结点信息 nodes[i] = copy.nodes[i]; for (i = 0; i < num; i++) { LeafChars[i] = copy.LeafChars[i]; // 复制叶结点字符信息 LeafCharCodes[i] = copy.LeafCharCodes[i];// 复制叶结点字符编码信息 } } return *this; } #endif //测试程序 #include "HuffmanTree.h" // 哈夫曼树类 int main(void) { try { // 用try封装可能出现异常的代码char ch[] = {'A', 'B', 'C', 'D','E'}; int w[] = {12, 3, 5, 9,6}; int n = 5, i; HuffmanTree HuffmanTree hmTree = hmTree1; String strText = "ABCDEAEDCEBD"; // 文本串 String strCode = "12010200"; // 编码串 cout << "各字符的编码为:" << endl; for (i = 0; i < n; i++) { String strTmp = hmTree.Encode(ch[i]); cout << ch[i] << " : " << strTmp.CStr() << endl; } cout << "文本串" << strText.CStr() << "编码为:"; for (i = 0; i < strText.GetLength(); i++) { String strTmp = hmTree.Encode(strText[i]); cout << strTmp.CStr(); } cout << endl; system("PAUSE"); cout << "编码串" << strCode.CStr() << "译码为:"; LinkList strText = lkText; cout << strText.CStr() << endl; } catch (Error err) { // 捕捉并处理异常 err.Show(); // 显示异常信息 } system("PAUSE"); return 0; } 实验二结构相关 一、实验目得: 通过本实验,加深对结构相关得理解,了解结构相关对CPU性能得影响。 二、实验内容: 1、用WinDLX模拟器运行程序structure_d、s 。 2、通过模拟,找出存在结构相关得指令对以及导致结构相关得部件。 3、记录由结构相关引起得暂停时钟周期数,计算暂停时钟周期数占总执行 周期数得百分比。 4、论述结构相关对CPU性能得影响,讨论解决结构相关得方法。 三、实验程序structure_d、s LHI R2, (A>>16)&0xFFFF 数据相关 ADDUI R2, R2, A&0xFFFF LHI R3, (B>>16)&0xFFFF ADDUI R3, R3, B&0xFFFF ADDU R4, R0, R3 loop: LD F0, 0(R2) LD F4, 0(R3) ADDD F0, F0, F4 ;浮点运算,两个周期,结构相关 ADDD F2, F0, F2 ; < A stall is found (an example of how to answer your questions) ADDI R2, R2, #8 ADDI R3, R3, #8 SUB R5, R4, R2 BNEZ R5, loop ;条件跳转 TRAP #0 ;; Exit < this is a ment !! A: 、double 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 B: 、double 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 四、实验过程 打开软件,load structure_d、s文件,进行单步运行。经过分析,此程序一 次循环中共有五次结构相关。(Rstall 数据相关Stall 结构相关) 1)第一个结构相关:addd f2,,f0,f2 由于前面得数据相关,导致上一条指令addd f0,f0,f4暂停在ID阶段,所以下一条指令addd f2,,f0,f2发生结构相关,导致相关得部件:译码部件。 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 【精品实验报告】软件体系结构设计模式实验报告软件体系结构 设计模式实验报告 学生姓名: 所在学院: 学生学号: 学生班级: 指导老师: 完成日期: 一、实验目的 熟练使用PowerDesigner和任意一种面向对象编程语言实现几种常见的设计模式，包括组合模式、外观模式、代理模式、观察者模式和策略模式，理解每一种设计模式的模式动机，掌握模式结构，学习如何使用代码实现这些模式，并学会分析这些模式的使用效果。 二、实验内容 使用PowerDesigner和任意一种面向对象编程语言实现组合模式、外观模式、代理模式、观察者模式和策略模式，包括根据实例绘制模式结构图、编写模式实例实现代码，运行并测试模式实例代码。 (1) 组合模式 使用组合模式设计一个杀毒软件(AntiVirus)的框架，该软件既可以对某个文件夹(Folder)杀毒，也可以对某个指定的文件(File)进行杀毒，文件种类包括文本文件TextFile、图片文件ImageFile、视频文件VideoFile。绘制类图并编程模拟实现。 (2) 组合模式 某教育机构组织结构如下图所示: 北京总部 教务办公室湖南分校行政办公室 教务办公室长沙教学点湘潭教学点行政办公室 教务办公室行政办公室教务办公室行政办公室 在该教育机构的OA系统中可以给各级办公室下发公文，现采用 组合模式设计该机构的组织结构，绘制相应的类图并编程模拟实现，在客户端代码中模拟下发公文。(注:可以定义一个办公室类为抽象叶子构件类，再将教务办公室和行政办公室作为其子类;可以定义一个教学机构类为抽象容器构件类，将总部、分校和教学点作为其子类。) (3) 外观模式 某系统需要提供一个文件加密模块，加密流程包括三个操作，分别是读取源文件、加密、保存加密之后的文件。读取文件和保存文件使用流来实现，这三个操作相对独立，其业务代码封装在三个不同的类中。现在需要提供一个统一的加密外观类，用户可以直接使用该加密外观类完成文件的读取、加密和保存三个操作，而不需要与每一个类进行交互，使用外观模式设计该加密模块，要求编程模拟实现。参考类图如下: reader = new FileReader();EncryptFacadecipher = new CipherMachine();writer = new FileWriter();-reader: FileReader-cipher: CipherMachine-writer: FileWriter +EncryptFacade () +fileEncrypt (String fileNameSrc,: voidString plainStr=reader.read(fileNameSrc); String fileNameDes)String 实验一顺序表问题 【实验报告】 《数据结构与算法》实验报告一 学院：计算机与信息学院班级： 学号：姓名： 日期：程序名： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输出结点值。 调试数据：9 8 7 6 5 4 3 2 1 2.从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到， 则显示“找不到”。 调试数据：第一次输入11，第二次输入3 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 调试数据：第一次insert "11" after "6" ，第二次insert "86" at "2" 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 调试数据：第一次delete the number at "2" ，第二次delete value "9" 注意：顺序表输出表现形式如下（实验报告上为截图）： 顺序表： 第一题 Initially Seq: head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第二题 找不到 6 第三题 insert "11" after "6": head -> 9 -> 8 -> 7 -> 6 -> 11 -> 5 -> 4 -> 3 -> 2 -> 1 -> null insert"86"at"2":head -> 9 -> 8 -> 86 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第四题 delete the number at "2":head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->null delete value "9": head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 中南大学软件学院 软件体系结构 设计模式实验报告 学生姓名：宋昂 所在学院：软件学院 学生学号： 3901080115 学生班级：软件0801 指导老师：刘伟 完成日期： 2010-12-7 一、实验目的 熟练使用PowerDesigner和任意一种面向对象编程语言实现几种常见的设计模式，包括简单工厂模式、工厂方法模式、抽象工厂模式、单例模式和适配器模式，理解每一种设计模式的模式动机，掌握模式结构，学习如何使用代码实现这些模式，并学会分析这些模式的使用效果。 二、实验内容 使用PowerDesigner和任意一种面向对象编程语言实现简单工厂模式、工厂方法模式、抽象工厂模式、单例模式和适配器模式，包括根据实例绘制模式结构图、编写模式实例实现代码，运行并测试模式实例代码。 (1) 简单工厂模式 使用简单工厂模式设计一个可以创建不同几何形状(Shape)的绘图工具类，如可创建圆形(Circle)、方形(Rectangle)和三角形(Triangle) 对象，每个几何图形都要有绘制draw()和擦除erase()两个方法，要求在绘制不支持的几何图形时，提示一个UnsupportedShapeException，绘制类图并编程实现。 (2) 简单工厂模式 使用简单工厂模式模拟女娲(Nvwa)造人(Person)，如果传入参数“M”，则返回一个Man 对象，如果传入参数“W”，则返回一个Woman对象，使用任意一种面向对象编程语言实现该场景。现需要增加一个新的Robot类，如果传入参数“R”，则返回一个Robot对象，对代码进行修改并注意女娲的变化。 (3) 工厂方法模式 某系统日志记录器要求支持多种日志记录方式，如文件记录、数据库记录等，且用户可以根据要求动态选择日志记录方式，现使用工厂方法模式设计该系统。用代码实现日志记录器实例，如果在系统中增加一个中的日志记录方式——控制台日志记录(ConsoleLog)，绘制类图并修改代码，注意增加新日志记录方式过程中原有代码的变化。 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 学期：2010-2011学年第一学期指导教师：杨华莉成绩： 实验一顺序表的基本操作 一、实验目的 1．掌握使用VC++6.0调试程序的基本方法； 2．掌握线性表的顺序存储结构的类型定义； 3．掌握顺序表的基本操作的实现,如：插入、删除、遍历、查找、排序、修改、合并等； 4．掌握顺序表的应用。 二、实验要求 1．认真阅读和掌握本实验的示例程序。 2．上机运行示例程序，打印出程序的运行结果，并作必要的说明。 3．对示例程序，按照对线性表的操作需要，在程序中至少添加2个顺序表的相关操作。如： i.查找并显示分数在区间[a，b）的学生信息； ii.查找并显示最高分或最低分学生信息； iii.统计不及格或及格人数及所占比例； iv.将信息表按学号、姓名或分数升序或降序排列； v.按学号顺序进行数据元素的插入； vi.删除指定学号或姓名的学生信息； vii.修改某个学生的信息； viii.其它。 4．重新改写主函数（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数、修改后的主函数和运行结果）。 5．对修改后的程序，分析每一个算法（函数）的时间复杂度。 6．根据上述要求撰写实验报告，并简要给出算法设计小结和心得。 三、实验环境 1．台式计算机每人一台； 2．软件：Visual C++6.0 四、实验内容和实验结果 一．示例程序运行结果及说明 二．自己添加的新函数(至少2个)，要求加必要的注释。 SqList Delete_SqList(SqList &L)//删除学生信息 { Elemtype x; int i=0; int choice=DMenu(); char name[25]; int num,k; if(!L.length) { printf("表为空，无法删除!"); exit(0); } switch(choice) { case 1: //按姓名删除 printf("\n请输入要删除的学生的姓名\n"); scanf("%s",&name); k=strcmp(name,L.data[i].name);//比较姓名 if(k==0) { x=L.data[i-1]; for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 2: //按学号删除 printf("\n请输入要删除学生的学号\n"); scanf("%d",&num); if(num==L.data[i].num) { for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 3:break; } return L; 云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号：姓名：本人承担角色： 综合得分：（满分100分） 指导教师：年月日（注：此表在难度为C时使用，每个成员一份。） （下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include 计算机系统结构实验报告 一．流水线中的相关 实验目的： 1. 熟练掌握WinDLX模拟器的操作和使用，熟悉DLX指令集结构及其特点； 2. 加深对计算机流水线基本概念的理解； 3. 进一步了解DLX基本流水线各段的功能以及基本操作； 4. 加深对数据相关、结构相关的理解，了解这两类相关对CPU性能的影响； 5. 了解解决数据相关的方法，掌握如何使用定向技术来减少数据相关带来的暂停。 实验平台： WinDLX模拟器 实验内容和步骤： 1.用WinDLX模拟器执行下列三个程序： 求阶乘程序fact.s 求最大公倍数程序gcm.s 求素数程序prim.s 分别以步进、连续、设置断点的方式运行程序，观察程序在流水线中的执行情况，观察 CPU中寄存器和存储器的内容。熟练掌握WinDLX的操作和使用。 2. 用WinDLX运行程序structure_d.s，通过模拟找出存在资源相关的指令对以及导致资源相 关的部件；记录由资源相关引起的暂停时钟周期数，计算暂停时钟周期数占总执行周期数的 百分比；论述资源相关对CPU性能的影响，讨论解决资源相关的方法。 3. 在不采用定向技术的情况下（去掉Configuration菜单中Enable Forwarding选项前的勾选符），用WinDLX运行程序data_d.s。记录数据相关引起的暂停时钟周期数以及程序执行的 总时钟周期数，计算暂停时钟周期数占总执行周期数的百分比。 在采用定向技术的情况下（勾选Enable Forwarding），用WinDLX再次运行程序data_d.s。重复上述3中的工作，并计算采用定向技术后性能提高的倍数。 1. 求阶乘程序 用WinDLX模拟器执行求阶乘程序fact.s。这个程序说明浮点指令的使用。该程序从标准 输入读入一个整数，求其阶乘，然后将结果输出。 该程序中调用了input.s中的输入子程序，这个子程序用于读入正整数。 实验结果： 在载入fact.s和input.s之后，不设置任何断点运行。 a.不采用重新定向技术，我们得到的结果 实验二结构相关 一、实验目的： 通过本实验，加深对结构相关的理解，了解结构相关对CPU性能的影响。 二、实验内容： 1. 用WinDLX模拟器运行程序structure_d.s 。 2. 通过模拟，找出存在结构相关的指令对以及导致结构相关的部件。 3. 记录由结构相关引起的暂停时钟周期数，计算暂停时钟周期数占总执行 周期数的百分比。 4. 论述结构相关对CPU性能的影响，讨论解决结构相关的方法。 三、实验程序structure_d.s LHI R2, (A>>16)&0xFFFF 数据相关 ADDUI R2, R2, A&0xFFFF LHI R3, (B>>16)&0xFFFF ADDUI R3, R3, B&0xFFFF ADDU R4, R0, R3 loop: LD F0, 0(R2) LD F4, 0(R3) ADDD F0, F0, F4 ；浮点运算，两个周期，结构相关 ADDD F2, F0, F2 ; <- A stall is found (an example of how to answer your questions) ADDI R2, R2, #8 ADDI R3, R3, #8 SUB R5, R4, R2 BNEZ R5, loop ；条件跳转 TRAP #0 ;; Exit <- this is a comment !! A: .double 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 B: .double 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 四、实验过程 打开软件，load structure_d.s文件，进行单步运行。经过分析，此程序一 次循环中共有五次结构相关。（R-stall 数据相关Stall- 结构相关） 1)第一个结构相关：addd f2,,f0,f2 由于前面的数据相关，导致上一条指令addd f0,f0,f4暂停在ID阶段，所以下一条指令addd f2,,f0,f2发生结构相关，导致相关的部件：译码部件。 2)第二个结构相关：ADDI R2, R2, #8，与第一个结构相关类似。由于数据相关， 上一条指令暂停在ID阶段，所以导致下一条指令发生结构相关。 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 福建农林大学计算机与信息学院 实验报告 课程名称：软件设计与体系结构 姓名：陈宇翔 系：软件工程系 专业：软件工程 年级：2007 学号：070481024 指导教师：王李进 职称：讲师 2009年12月16日 实验项目列表 福建农林大学计算机与信息学院实验报告 学院：计算机与信息学院专业：软件工程系年级：2007 姓名：陈宇翔 学号：070481024 课程名称：软件设计与体系结构实验时间：2009-10-28 实验室田实验室312、313计算机号024 指导教师签字：成绩： 实验1：ACME软件体系结构描述语言应用 一、实验目的 1）掌握软件体系结构描述的概念 2）掌握应用ACMESTUDIO工具描述软件体系结构的基本操作 二、实验学时 2学时。 三、实验方法 由老师提供软件体系结构图形样板供学生参考，学生在样板的指导下修改图形，在老师的指导下进行软件体系结构描述。 四、实验环境 计算机及ACMESTUDIO。 五、实验内容 利用ACME语言定义软件体系结构风格，修改ACME代码，并进行风格测试。 六、实验操作步骤 一、导入Zip文档 建立的一个Acme Project，并且命名为AcmeLab2。如下图： 接着导入ZIP文档，导入完ZIP文档后显示的如下图： 二、修改风格 在AcmeLab2项目中,打开families下的TieredFam.acme.如下图： 修改组件外观 1. 在组件类型中，双击DataNodeT; 在其右边的编辑器中，将产生预览；选择Modify 按钮，将打开外观编辑器对话框。 2. 首先改变图形：找到Basic shape section，在Stock image dropdown menu中选 择Repository类型. 3. 在Color/Line Properties section修改填充颜色为深蓝色。 4. 在颜色对话框中选择深蓝色，并单击 [OK]. 5. 修改图形的边框颜色为绿色 7. 单击Label tab，在Font Settings section, 设置字体颜色为白色,单击[OK] 产生的图形如下图： 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 《数据结构实验》的实验题目及实验报告模板 实验一客房管理（链表实验） ●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ●实验机时：8 ●设计要求： #include 实验名称多通路运算器和寄存器堆实验地点信息楼420 实验日期2012-12-7 一、实验目的 1．了解多通路的运算器与寄存器堆的组成结构。 2．掌握多通路的运算器与寄存器堆的工作原理及设计方法。 二、实验设备 PC 机一台， TD-CMX 实验系统一套。 三、实验原理 1．ALU® 单元的结构 ALU®单元由运算器和双端口寄存器堆构成，通过不同的控制信号SEL1、SEL0 产生不同结构的运算器。运算器内部含有三个独立运算部件，分别为算术、逻辑和移位运算部件，要处理的数据存于暂存器A 和暂存器B。 SEL0 和SEL1 用于选择运算器和寄存器堆的通路： (1)当SEL1=0、SEL0=0，ALU 的输出D7…D0、REG（右口）的输出OUT7…OUT0 和ALU与REG 的输入IN7…IN0 接到CPU 内总线上时，如图1-2-1 所示，寄存器堆只能从右口进行操作，相当于只有一组控制线的单端口寄存器堆，一般计算机组成原理实验涉及到的运算器和寄存器就是采用这种结构。 (2)当SEL1=1、SEL0=0，REG（右口）的输出OUT7…OUT0 和ALU 与REG（右口）的输入IN7…IN0 接到CPU 内总线上时，运算器和双端口寄存器堆的结构如图1-2-2 所示，寄存器堆由两组控制信号来分别进行控制，每组控制信号都可以相对独立的对寄存器堆进行读写操作，同时增加了执行专用通道A 总线，以利于提高指令执行的效率。 (3)当SEL1=1、SEL0=1，REG（右口）的输出OUT7…OUT0 和ALU 与REG（右口）的输入IN7…IN0 接到CPU 内总线上时，运算器和双端口寄存器堆的结构如图1-2-3 所示，在双通道双端口运算器和寄存器堆的基础上增加了暂存器旁路，把运算结果写回到寄存器堆的同时也可以写到暂存器A、暂存器B 中。由于在运算型指令中把运算的结果写到通用寄存器中的指令很多，占运算型指令的大多数，发生通用寄存器数据相关的概率相当高，因此，可以用硬件设置专用路径来解决这种通用寄存器数据相关问题。 上面介绍了运算器和寄存器堆的三种典型的数据通路图，在计算机组成原理这门课程中我们已经对运算器有了初步的了解，明白运算器的主要功能是完成算术和逻辑类运算。在系统结构这门课程中经过进一步的研究，还会了解到运算器与寄存器堆的结构对于计算机系统的设计有着重要的作用，对于计算机性能的优劣有着很大的影响。 2．ALU® 单元的应用 在了解运算器与寄存器堆结构的基础上，基于如图1-2-3 所示的双通道双端口运算器和双端口寄存器堆的结构可以设计一段程序：从IN 单元读入一个数据，存入R0；从IN 单元读入另一个数据，存于R1；将R0 和R1 相加，结果存于R0；将R0 和R1 相加，结果存于R3，同时打入暂存器A 中；再将R0 的值送OUT 单元显示。 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存计算机体系结构实验报告二
数据结构实验报告格式
【精品实验报告】软件体系结构设计模式实验报告
数据结构实验一顺序表问题及实验报告模板 - Copy
数据结构实验报告
数据结构实验报告全集
体系结构实验报告
数据结构实验报告模板
数据结构实验报告模板(验证型)
数据结构实验报告七查找、
计算机系统结构实验报告
计算机体系结构实验报告二
数据结构实验报告及心得体会
软件设计与体系结构实验报告
数据结构实验报告图实验
《数据结构实验》实验题目及实验报告模板
计算机体系结构 实验报告2 华东理工大学
数据结构实验报告 - 答案汇总