安徽工程大学数据结构各章作业和实验
第一章
?一、简答题
1 设有数据逻辑结构为：
?B=（K，R）；K={K1，K2…Kn};
?R={
?画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点
2 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。
1)A=（K，R），其中K={a,b,c,d,e,f,g,h};
R={r}，r={
2)B=(K,R),其中K={a,b,c,d,e,f,g,h};
R={r}，r={
?二、求下列程序段的时间复杂度
(1) for (I=0;I for (j=0;j A[I][j]=0; return 1; (2) I=s=0; else While (s { I++; } s+=I; (5) s=0; } for(I=0;I<=n;I++) (3) I=1; for(j=0;j<=n;j++) While (I<=n) for(k=0;k I=I*3; s++; ?第二章 ?一.选择、填空： ? 1 不带头结点的单链表head为空的判定条件是_ ；带头结点的单链表head为空的判定条件是_ ? A. head==null B. head->next=null ? C. Head->next=head D. Head!=null ? 2 在循环双链表P所指接点之前插入S所指结点的操作是__ ? A. P->prior=S;S->next=P;p->next= S;S ->prior=P->prior ? B. P->prior=S;P->prior->next=S;S->next= P;S ->prior=P->prior ? C. S->next=P; S->prior=P->prior; P->prior=S;P->right->next=S ? D. S->next=P; S->prior=P->prior; P->prior->next=S;P->prior=S ? 3. 双向链表删除P结点，执行的主要语句是_______ ? 4. 在单链表中，在指针P所指结点后面插入一个结点S的语句是_________ ? 5. 在单链表中删除P指针所指结点的的后一个结点的语句是_________ ? 6. 向长度为n的向量第i个元素C（0≤i≤n-1 ）之前插入一个元素时，需后移____个元素；删除长度为n的向量第i个元素C（0≤i≤n-1 ）之前插入一个元素时，需前移____个元素 ? 第三章作业 一选择、填空题 1 判定一个栈（最多n个元素）为空的条件是__;判定为满的条件是__ A. S->top!=0 B. S->top= =0 C. S->top!=n D. S->top= =n 2 一个栈序列：a,b,c,d,e,则栈不可能输出序列__ A. abcde B. decba C. dceab D. Edcba 3 判定一个队列Q（最多n个元素）为空的条件___是为满的条件是___ A. Q->near-Q->front==n B. Q->near-Q->front+1==n C. Q->front=Q->rear D. Q->front=Q->rear+1 4 判定循环队列Q（最多n个元素）为空的条件是___;为满的条件是__ A. Q->rear==Q->front B. Q->rear==Q->front+1 C. Q->front==(Q->rear+1)%n D. Q->front==(Q->rear-1)%n 二综合题 1 设有4个元素ABCD进栈，写出它们所有可能的出栈次序共几种 2 设计一个算法，利用栈的基本运算将指定栈中的内容进行逆转 ?第四章作业 ?一填空、选择题 ? 1. ___是C语言中“abcd321ABCD”的子串。 ? A. abcd B.321AB C.”abcAB” D. “21AB” ? 2. 有串S1=…ABCDEFG?，S2=…PQRST?，设con(x,y)返回串X与串Y的连接串，subs(s,I,j)返回从序号i字符开始的j个字符组成的子串，len(s)返回串s长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是___(设置串字符从0开始编号) ? A. BCDEF B. BCDEFG C. BCPQRST D. CDEFGFG 3 、串的两种基本存储方式为____ 和_____ 4、空串是____个字符的串，空白串是____个字符的串 二、编程题 1 以顺序结构存储串时，写出两串s1,s2首尾相连成一个串，其中s1在前s2 在后 第五章作业 一、选择与判断： 1 数组元素间的关系是_(1)___,一维数组和线性表的区别是__(2)__ (1) A 线性B树形 C 既线性又树形 D 非线性又非树形 （2） A 前者长度固定，后者长度可变 B后前者长度固定，前者长度可变 C 两者长度固定 D两者长度可变 2 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i范围从0到4，下标j范围从0到5，M按行存储时元素M[3][5]起始地址与M按列存储时元素___起始地址相同 A . M[2][4] B .M[3][4] C .M[3][5] D. M[4][4] 3、设一个有10阶对称矩阵A，采用压缩存储方式，以行序为主存储，a1,1为第一个元素，其地址为1，每个元素站1个地址空间，则a 8,5的地址为____ A、13 B、33 C、18 D、40 4、一个n*n的对称矩阵，如果以行或列为主序放入内存， 则容量为_____ A、n*n B、n*n/2 C、n*(n+1)/2 D、(n+1)*(n+1)/2 5、稀疏矩阵一般的压缩存储方法有两种，即____和____ 6、设广义表L=((a,c),(b,d)),运算head(head(tail(L)))是____ 7、对于广义表L=((),())，则head(L)是____,L长度是______,tail(L)是______ 8、设A=(a,b,c); B=(A,(c,d)); C=(a,(B,A),(e,f)),求head(head(head(tail(c))))=_________ 第六章作业 ?一、选择、填空 ?1、设高度为h的二叉树只有度为0和2的结点（第一层为根结点所在的层），则此类二叉树所包含的结点数至少为_____ ?A 2h B 2h-1 C 2h+1 D h+1 ?2、下图1的二叉树中序遍历为____ ?A abcdgef B dfebagc C dbaefcg D defbagc ?3、如果T2是由有序树T1转换而来的二叉树，那么T1结点的先序就是T2中结点的___ ?A 先序 B 中序 C 后序 D 层次序 图2 ?4、深度为5的二叉树至多有____个结点 ?A 16 B 32 C 31 D 10 ?5、根据使用频率为5个字符设计的哈夫曼编码不可能是___ ?A 111,110,10,01,00 B 000,001,010,011,1 C 100,11,10,1,0 D 001,000,01,11,10 ?6、如图2所示的二叉树，回答以下问题 （1）其中序遍历序列为____________ （2）其先序遍历序列为____________ （3）其中后序遍历序列为____________ （4）该二叉树对应森林是____________ 5、以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树为______,其带权路径长度为________ 二、简答题： 1 假设二叉树bt的存储结构如下：其中bt为树根结点指针，left,right分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0表指针域为空，data表结点数据域，请完成下列各题： （1）画出二叉树bt的逻辑结构 （2）写出按先序、中序、后序遍历bt所得到的结点序列 6 ?2、假设二叉树采用顺序存储结构如下表所示 ?（1）画出二叉树表示 ?（2）写出先序、中序、后序遍历结果 ?（3）写出结点值C的双亲结点，其左右孩子 ?（4）画出把此二叉树还原成森林的图 ?第七章图 ?一选择、填空 ?1、在一个图中，所有顶点的度数之和等于所有边数的____倍，对于一个有向图，所有等点的入度之和等于所有顶点出度之和的____倍 ?A、? B、1 C、2 D、4 ?2、一个有n个顶点的无向图最多有____条边，若采用邻接矩阵表示，则该矩阵的大小是_____ ?A、n B n(n-1)/2 C n-1 D n*n ?3、已知一个图，若从顶点a出发按深度有限搜索进行遍历，则可能得到的一种顶点序列是_____;若从顶点a出发按广度有限搜索进行遍历，则可能得到的一种顶点序列是_____ A、abecdf B、aedfcb C、aebcfd D、abcefd 4、已知一有向图的邻接表存储结构如图所示，则 （1）根据有向图深度有限搜索遍历算法，从顶点V1出发得到的顶点序列是_____，根据根据有向图广度有限搜索遍历算法，从顶点V1出发得到的顶点序列是_____ A、V1V2V3V4V5 B、V1V3V2V4V5 C、V1V3V4V5V2 D、V1V4V3V5V2 5、n个顶点的连通图至少___条边 A、n B、n-1 C、n*n D、n+1 二、书上P232——8-1，8-2，8-3 实验一、线性表表示及实现 实验题目: 线性表顺序和链表表示及实现 实验目的：1学会定义线性表顺序存储结构 2 通过对顺序存储结构的分析，掌握线性表动态分配存储及基本操作，熟悉线性 表基本操作及函数定义 3 进一步熟悉C语言基本结构，掌握程序头文件，实现文件及主文件关系及各 作用 实验内容：建立10个数据元素的线性表L={1，2，3…10}指定在第2位置插入元素25，然后删除第4个位置上的元素，分别显示各步骤结果 实验二:顺序栈的实践 实验目的：熟练掌握栈的结构、特点及有关概念，学会建立栈的基本操作，了解栈满和栈空的判断条件及描述方法 实验内容：建立一个字符栈 ⑴用顺序栈设计实现堆栈,堆栈操作集合包括初始化,判断栈空,入栈,出栈,取栈顶元素等 (2)设计一个主函数对顺序栈进行测试,如:依次输入数据元素1,2,3,4,5,然后判断栈是否为空,显示栈顶元素,出栈并在屏幕上显示出栈的数据元素 实验三：栈和队列的综合应用 实验目的：了解并掌握顺序栈及顺序队列的基本概念和基本操作。熟练掌握 栈和队列的结构及这两种数据结构的特点，在两种存储结构上实现栈的基本运算。特别注意栈空，栈满的判断条件；熟练掌握链队列和顺序循环队列的基本运算并能简单应用 实验题目： 1、回文是指一个字符串从头到尾和从尾到头都一样，如串“”abcba”， 设字符串从输入设备一个一个字符读入，至”#”结束，请用顺序栈和顺序队列两种算法判断一个字符串是否为回文 2、请利用所学栈的知识设计一个进制转换器，实现十进制到八进制的转换 实验四、堆分配存储表示的串操作 实验目的： 了解串的顺序存储的两种表示方式：定长顺序存储和堆分配存储，掌握其基本概念 实验内容： 利用堆分配存储法，生成两个值等于串常量的串S、T，比较两串的大小，输 出结束；在串S的第POS位置上（POS值自己设定）插入串T，并输出新串； 计算新串的串长并输出 实验要点： 利用系统提供的库函数malloc(),realloc()作为串分配或重新分配存储空间，用free函数释放串值所占空间 实验五稀疏矩阵的转置 一实验目的: 了解稀疏矩阵的三元组顺序表的表示方式,掌握矩阵转置运算的操作方法 二实验内容 输入一个稀疏矩阵A,建立A的三元组顺序表,求A的转置矩阵B,请用两种转置法实现稀疏矩阵的转置,注意矩阵的建立、输出的实现 三实验要求 1 编写源程序 2 调试体会 实验六七二叉树的基本操作 【实验目的】 1. 熟练掌握树的基本概念、二叉树的基本操作 2. 重点掌握二叉树的生成、遍历及求深度等算法。 3．掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。 【实验题目】 一、二叉树的基本运算实验 【问题描述】 二叉树采用二叉链表作存储结构，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目； 4. 将二叉树每个结点的左右子树交换位置。 【实验要求】 1 编写源程序 2 调试心得 二、赫夫曼树与赫夫曼编码 【问题描述】 利用Huffman编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据编码进行译码（复原）。对于有些信道，每端都需要一个完整的编／译码系统。试为这样的信息收发站编写一个Huffman的编／译码系统。给定一组权值{7，9，5，6，10，1，13，15， 4，8}，构造一棵赫夫曼树，并计算带权路径长度WPL。 【算法描述】 1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。（具体算法可参见教材P147的算法6.12） 2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。 3. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符'0'和'1'确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。具体算法留给读者完成。 4. 打印 Huffman树。 【实验要求】 1 编写源程序 2 画出程序流程图 3 调试心得 实验八图的建立和应用 【实验目的】 1.熟练掌握图的邻接矩阵和邻接表的存储方式； 2.实现图的一些基本运算，特别是深度遍历和广度遍历； 【实验题目】 建立一无向图的深度优先搜索生成树并输出得到的序列 【实验要求】 1 用邻接表和邻接矩阵两种方法存储图 2 编写源程序 3 调试心得 实验九查找算法的实现 【实验目的】 1. 熟练掌握各种静态查找表的查找方法（顺序查找法、折半查找法、索引顺序表查找）； 2. 熟练掌握二叉排序树的构造方法和查找算法； 3. 掌握描述查找过程的判定树的构造方法，以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度； 4. 了解二叉平衡树的建立和维护平衡的方法。 【实验题目】 静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。对静态查找表可以用顺序表或线性链表进行表示，也可组织成有序的顺序表，或者是索引顺序表，相应的查找方法可采用顺序查找方法、折半查找方法和索引顺序查找的方法。请用顺序查找方法设计一个有关静态查找表的建立、查找等基本操作的演示程序。 【实验要求】 1 编写源程序 2 调试心得 实验十内部排序算法的实现 【实验目的】 1、掌握各种排序算法的思想、方法和稳定性。 2、掌握快速排序、堆排序、归并排序算法的实现。 3、了解每一种排序算法的时间以及空间复杂度。 【实验题目】 任意给出一组关键字（关键字的个数和值在运行时由键盘输入），分别采用直接插入排序、希尔排序和快速排序算法对其进行排序，并输出每个排序算法得到的序列。 【实验要求】 1 编写源程序 2 调试心得 实验4 结构型设计模式实验 实验学时： 2 每组人数： 1 实验类型： 3 （1：基础性 2：综合性 3：设计性 4：研究性） 实验要求： 1 （1：必修 2：选修 3：其它） 实验类别： 3 （1：基础 2：专业基础 3：专业 4：其它） 一、实验目的 熟练使用PowerDesigner和任意一种面向对象编程语言实现几种常见的结构型设计模式，包括适配器模式、组合模式和外观模式，理解每一种设计模式的模式动机，掌握模式结构，学习如何使用代码实现这些模式。 二、实验内容 1. 现有一个接口DataOperation定义了排序方法sort(int[]) 和查找方法search(int[], int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法，类BinarySearch 的binarySearch(int[], int)方法实现了二分查找算法。试使用适配器模式设计一个系统，在不修改源代码的情况下将类QuickSort和类BinarySearch的方法适配到DataOperation接口中。绘制类图并编程实现。（要求实现快速排序和二分查找，使用对象适配器实现） 2. Windows Media Player和RealPlayer是两种常用的媒体播放器，它们的API结构和调用方法存在区别。现在你的应用程序需要支持这两种播放器API，而且在将来可能还需要支持新的媒体播放器，请问如何设计该应用程序绘制类图并编程模拟实现。 3. 使用组合模式设计一个杀毒软件(AntiVirus)的框架，该软件既可以对某个文件夹(Folder)杀毒，也可以对某个指定的文件(File)进行杀毒，文件种类包括文本文件TextFile、图片文件ImageFile、视频文件VideoFile。绘制类图并编程模拟实现。 4. 某教育机构组织结构如下图所示： 数据结构实验报告 一．题目要求 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<<" 建立一个单链表"< 重庆文理学院软件工程学院实验报告册 专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____201258014054 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日 实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。 2.编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。 3.编程序实现将单链表的数据逆置，即将原表的数据（a1,a2….an）变成 (an,…..a2,a1)。（单链表的数据域数据类型为一结构体，包括学生的部分信息：学号，姓名，年龄） 实验过程及步骤1. #include { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 理工学院实验报告 系部计算机系班级学号 课程名称数据结构实验日期 实验名称链表的基本操作成绩 实验目的： （1）掌握线性表的链式存储结构的特点； （2）掌握线性表的基本操作：初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。 实验条件：计算机一台，vc++6.0 实验容与算法思想： 容： 建立一有序的链表，实现下列操作： 1.把元素x插入表中并保持链表的有序性； 2.查找值为x的元素，若找到将其删除； 3.输出表中各元素的值。 算法思想：先创建并初始化一个顺序表（void init_linklist(LinkList)），通过循环，输入一串数据void CreateFromTail(LinkList L);创建主函数；编写算法，完成子函数（查找locate，插入insList，删除DelList，输出output）模块；调用子函数，完成实验要求 运行结果： 附：源程序： #include 中南大学软件体系结构设计模式实验二 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 实验3 设计模式实验二 实验学时： 4 每组人数： 1 实验类型： 3 （1：基础性 2：综合性 3：设计性 4：研究性） 实验要求： 1 （1：必修 2：选修 3：其它） 实验类别： 3 （1：基础 2：专业基础 3：专业 4：其它） 一、实验目的 熟练使用PowerDesigner和任意一种面向对象编程语言实现几种常见的行为型设计模式，包括职责链模式、命令模式、观察者模式和策略模式，理解每一种设计模式的模式动机，掌握模式结构，学习如何使用代码实现这些模式。 二、实验内容 1. 某企业的SCM(Supply Chain Management，供应链管理)系统中包含一个采购审批子系统。该企业的采购审批是分级进行的，即根据采购金额的不同由不同层次的主管人员来审批，主任可以审批5万元以下（不包括5万元）的采购单，副董事长可以审批5万元至10万元（不包括10万元）的采购单，董事长可以审批10万元至50万元（不包括50万元）的采购单，50万元及以上的采购单就需要开董事会讨论决定。如下图所示： 试使用职责链模式设计并模拟实现该系统。 2. 房间中的开关是命令模式的一个实例，现用命令模式来模拟开关的功能，可控制对象包括电灯和电风扇，绘制相应的类图并编程模拟实现。 3. 某软件公司欲开发一个基于Windows平台的公告板系统。系统提供一个主菜单(Menu)，在主菜单中包含了一些菜单项(MenuItem)，可以通过Menu类的addMenuItem()方法增加菜单项。菜单项的主要方法是click()，每一个菜单项包含一个抽象命令类，具体命令类包括OpenCommand(打开命令)，CreateCommand(新建命令)，EditCommand(编辑命令)等，命令类具有一个execute()方法，用于调用公告板系统界面类(BoardScreen)的open()、create()、edit()等方法。现使用命令模式设计该系统，使得MenuItem类与BoardScreen类的耦合度降低，绘制类图并编程实现。 4. 某实时在线股票软件需要提供如下功能：当股票购买者所购买的某支股票价格变化幅度达到5%时，系统将自动发送通知（包括新价格）给购买该股票的所有股民。试使用观察者模式设计并实现该系统，要求绘制相应的类图并编程模拟实现。 5. 某公司欲开发一套机房监控系统，如果机房达到某一指定温度，温度传感器(Thermosensor)将自动传递信号给各种响应设备，例如警示灯(CautionLight)将闪烁(flicker())、报警器(Annunciator)将发出警报(alarm())、安全逃生门(SecurityDoor)将自动开启(open())、隔热门(InsulatedDoor)将自动关闭(close()) 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 洛阳理工学院实验报告 系部计算机系班级学号姓名 课程名称数据结构实验日期 实验名称链表的基本操作成绩 实验目的： （1）掌握线性表的链式存储结构的特点； （2）掌握线性表的基本操作：初始化、插入、删除、查找数据元素等运算在链式存储结构上的实现。 实验条件：计算机一台，vc++6.0 实验内容与算法思想： 内容： 建立一有序的链表，实现下列操作： 1.把元素x插入表中并保持链表的有序性； 2.查找值为x的元素，若找到将其删除； 3.输出表中各元素的值。 算法思想：先创建并初始化一个顺序表（void init_linklist(LinkList)），通过循环，输入一串数据void CreateFromTail(LinkList L);创建主函数；编写算法，完成子函数（查找locate，插入insList，删除DelList，输出output）模块；调用子函数，完成实验要求 运行结果： 附：源程序： #include 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 数据结构实验报告 二．程序设计相关信息 （1）实验题目：编写一个程序algo2-3.cpp，实现双链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： 1.初始化双链表h； 2.依次采用尾插法插入a，b，c，d，e元素； 3.输出双链表h； 4.输出双链表h长度； 5.输出双链表h是否为空； 6.判断双链表h的第3个元素； 7.输出元素‘a’的位置； 8.在第4个元素位置上插入‘f’元素； 9.输出双链表h； 10.删除L的第3个元素； 11.输出双链表h； 12.释放双链表h。 （2）实验目的：熟悉双链表的基本操作并掌握尾插法建表。 （3）算法描述或流程图 (4)源代码 #include typedef struct DNode { char data; struct DNode *next; struct DNode *prior; }DNode,DLinkList; void initlist(DLinkList *&h) { h=(DLinkList*)malloc(sizeof(DLinkList)) ; h->next=NULL; h->prior=NULL; } void destroylist(DLinkList *&h) { DLinkList *p=h,*q=p->next; while(q!=NULL) {free(p); p=q; q=p->next; } free(p); } int getelem(DLinkList *h,int i,char &e) {int j=0; DLinkList *p=h; while(j 姓名： 学号： 班级： 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 实 验 报 告 一、实验目的 1) 加深对图的表示法和图的基本操作的理解，并可初步使用及操作； 2) 掌握用图对实际问题进行抽象的方法，可以解决基本的问题； 3) 掌握利用邻接表求解非负权值、单源最短路径的方法，即利用Dijkstra 算法求最短 路径，同时掌握邻接表的建立以及使用方法，能够解决相关的问题； 4) 学会使用STL 中的map 抽象实际问题，掌握map ，List,，priority_queue 等的应 用。 二、实验内容与实验步骤 （1） 实验内容： 使用图这种抽象的数据结构存储模拟的欧洲铁路路线图，通过Dijkstra 算法求出欧洲旅行最少花费的路线。该实验应用Dijkstra 算法求得任意两个城市之间的最少路费，并给出路费最少的路径的长度和所经过的城市名。 （2） 抽象数据类型及设计函数描述 1) 抽象数据类型 class City ： 维护一个城市的信息，包括城市名name ，是否被访问过的标记visted ，从某个城市到达该城市所需的总费用total_fee 和总路径长度total_distance ，求得最短路径后路径中到达该城市的城市名from_city 。 class RailSystem ： 用邻接表模拟欧洲铁路系统，该邻接表使用数据结构map 实现，map 的key-value 课程名称：数据结构 班级： 实验成绩： 实验名称：欧洲旅行 学号： 批阅教师签字： 实验编号：实验二 姓名： 实验日期：2013 年6 月 18 日 指导教师： 组号： 实验时间： 值对的数据类型分别为string和list<*Service>，对应出发城市名和该城市与它能 够到达的城市之间的Service链表。 class Service： 为铁路系统模拟了两个城市之间的直接路线，包括两个城市之间直接到达的费用 fee，两城市之间的直接距离distance。 部分设计函数描述 ●RailSystem(const string& filename) 构造函数，调用load_services(string const &filename)函数读取数据 ●load_services(string const &filename) 读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图 ●reset(void) 遍历cities图，初始化所有城市的信息：visted未访问，total_distance最大 值，total_fee费用最大值，from_city为空 ●~RailSystem(void) 析构函数，用delete将两个map中所有使用new操作符开辟的空间删除 ●void output_cheapest_route(const string& from, const string& to, ostream& out); 输出两城市间的最少费用的路径，调用calc_route(string from, string to)函 数计算最少费用 ●calc_route(string from, string to) 使用Dijkstra算法计算from和to两个城市间的最少费用的路径 （3）采用的存储结构 1)map 云南大学数学与统计学实验教学中心 实 验 报 告 一、实验目的： 通过实验掌握线性链表的建立及基本操作，巩固课堂内容，练习其程序的设计与实现。 由于顺序存储结构的操作相对比较简单，而且在前期课程《高级语言程序设计》中使用得也多， 所以本次实验侧重于对线性链表存储结构上的操作及应用的实现。 二、实验内容： 本实验包含以下几个子问题： 1、 采用表尾挂入法建立一个以LA 为头指针的单链表： 2、 3、 就地逆转以LB 为头指针的单链表，即得到如下形式的单链表： 4、 将逆转后的LB 表接到LA 表之尾并构成循环链： LA 二、实验要求： 1. 每一个子问题用一个C 语言的函数来完成。 2. 对每一个子问题的结果用一个打印函数输出其结果以验证程序运行是否正确。 打印函数必须是公共的，即：用一个输出函数，既可以对单链表又可对循环链表实现， 打印输出。 3.用主函数调用各个子函数，以完成题目要求。 4.程序设计时应尽量考虑通用性，若改变题给数据仍能实现要求。 [实现提示]： ．第3小题题中的“就地逆转”即只允许引入除LB外的两个工作指针来实现。 即可以以循环方式从链表首部起逐个地修改各个结点的指针：从NEXT（向后）指针改变为PRIOR（向前）的指针，并注意保存搜索时的指针。 三、实验环境 Windows win7 程序设计语言C 四、实验过程（请学生认真填写）： 1. 实验设计的（各）流程图： 2. 程序设计的代码及解释（必须给出）： /*----------------------------------LinkList-------------------------------------*/ /*基本要求---------------------------------------------------------------------*/ /*采用表尾挂入法建立一个以LA为头指针的单链表--------------*/ /*采用表首插入法建立一个以LB为头指针的单链表.---------------*/ /*就地逆转以LB为头指针的单链表，即得到如下形式的单链表.*/ /*将逆转后的LB表接到LA表之尾并构成循环链-------------------*/ /*每一个子问题用一个C语言的函数来完成--------------------------*/ /* 打印函数必须是公共的-------------------------------------------------*/ /*-------------------------------------Start-------------------------------------*/ /*--------------------------------------------------------------------------------*/ #include 计算机体系结构课程设计 学院：信息科学与工程学院 专业班级： 指导老师： 学号： 姓名： 目录 实验1 对指令操作码进行霍夫曼编码 (3) 一、实验目的 (3) 二、实验内容 (3) 三、设计思路 (4) 四、关键代码 (4) 五、实验截图 (5) 六、源代码 (5) 实验2 使用LRU 方法更新Cache (8) 一、实验目的 (8) 二、实验内容 (8) 三、设计思路 (9) 四、程序截图 (9) 五、实验代码 (9) 实验总结 (16) 参考文献 (16) 实验1 对指令操作码进行霍夫曼编码一、实验目的 了解和掌握指令编码的基本要求和基本原理 二、实验内容 1. 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。 2. 问题描述以及问题分析 举例说明此问题，例如： 下表所示： 对此组指令进行 HUFFMAN 编码正如下图所示： 最后得到的HUFFMAN 编码如下表所示： 最短编码长度为： H=0.45*1+0.30*2+0.15*3+0.05*4+0.03*5+0.01*6+0.01*6=-1.95. 要对指令的操作码进行 HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造HUFFMAN 树再进行 HUFFAM 编码。此过程的难点构造 HUFFMAN 树，进行 HUFFAM 编 码只要对你所生成的 HUFFMAN 树进行中序遍历即可完成编码工作。 三、设计思路 观察上图，不难看出构造 HUFFMAN 树所要做的工作：1、先对各指令操作码的出现概率进行排序，构造一个有序链表。2、再取出两个最小的概率节点相加，生成一个生的节点加入到链表中，同时从两表中删除此两个节点。3、在对链表进行排序，链表是否只有一个节点，是则 HUFFAN 树构造完毕，否则继续做 2 的操作。为此设计一个工作链表（链表的元素时类，此类的功能相当结构。）、HUFFMAN 树节点、HUFFMAN 编码表节点。 四、关键代码 哈夫曼树重点在于如何排列权值大小不同的结点的顺序 private int leafNum; //叶子结点个数 private HaffmanNode[] hnodes; //哈夫曼树的结点数组 public HaffManCode(double[] weight) //构造指定权值集合的哈夫曼树 { int n = weight.length; //n个叶子结点 this.leafNum = n; this.hnodes = new HaffmanNode[2*n-1]; //n个叶子结点的哈夫曼树共有2n-1个结点 for(int i=0; i中南大学软件体系结构实验4-结构型设计模式实验
数据结构实验报告
(完整版)数据结构实验报告全集
数据结构实验答案1
数据结构实验十一：图实验
数据结构实验二11180
中南大学软件体系结构设计模式实验二
数据结构实验---图的储存与遍历
数据结构实验报告图实验
数据结构实验二
数据结构实验报告图实验
数据结构实验报告2
数据结构实验报告
数据结构实验
数据结构实验二-
数据结构实验二链表
中南大学 计算机体系结构实验报告
相关文档
- 数据结构作业一答案
- 天大数据结构_实验作业二_栈顺序栈队列循环队列
- 中科大数据结构与数据库实验作业
- 数据结构作业电子版
- 安徽工程大学数据结构各章作业及实验
- !数据结构实验大作业考核要求
- 数据结构(C版)课后作业任务6-8章附答案解析
- 【免费下载】数据结构作业及答案1
- 数据结构作业——分块查找算法
- 数据结构作业及答案汇总
- 数据结构大作业(试题题目)
- 数据结构作业系统_第七章答案
- 数据结构形成性考核作业册
- 数据结构书面作业练习题
- 实验报告(数据结构(本)-作业5)(实验2)
- 安徽工程大学数据结构各章作业和实验
- 数据结构大作业(含源代码)
- 数据结构作业及答案
- 实验报告(数据结构(本)-作业5)(实验2)
- 数据结构作业