实验报告
院（系）：信息科学与技术学院课程名称：数据结构日期：
暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.37 6.38 6.39 指导教师孙世良 实验项目编号实验8 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 理解二叉树线索化的实质是建立结点与其在相应序列中的前去或后继之间的直接联系，熟练掌握二叉树的线索化的过程以及在中序线索化树上找给定结点的前驱和后继的方法。 (二)实验内容和要求 6.37试利用栈的基本操作写出先序遍历的非递归形式的算法。 6.38同题6.37条件，写出后序遍历的非递归算法（提示：为分辨后序遍 历时两次进栈的不同返回点需在指针进栈时同时将一个标志进栈）。 6.39假设在二叉链表的结点中增设两个域：双亲域以指示其双亲结点； 标志域以区分在遍历过程中到达该结点时应继续向左或向右或访问该节点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。(三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序
6.37： #include
数据结构实验五矩阵的压缩存储与运算
第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1
k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，‘%’表示求余。
实验报告 课程名称数据结构实验名称查找与排序的实现 系别专业班级指导教师11 学号实验日期实验成绩 一、实验目的 (1)掌握交换排序算法（冒泡排序）的基本思想； (2)掌握交换排序算法（冒泡排序）的实现方法； (3)掌握折半查找算法的基本思想； (4)掌握折半查找算法的实现方法； 二、实验内容 1.对同一组数据分别进行冒泡排序，输出排序结果。要求： 1)设计三种输入数据序列：正序、反序、无序 2)修改程序： a)将序列采用手工输入的方式输入 b)增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂 性 2.对给定的有序查找集合，通过折半查找与给定值k相等的元素。 3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置， 算法如何改进？ 三、设计与编码 1.本实验用到的理论知识 2.算法设计
3.编码 package sort_search; import java.util.Scanner; public class Sort_Search { //冒泡排序算法 public void BubbleSort(int r[]){ int temp; int count=0,move=0; boolean flag=true; for(int i=1;i 编译原理实验报告语法分析程序的设计 文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688] 实验5语法分析程序的设计（2） 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。 二、实验内容 设计一个文法的算法优先分析程序，判断特定表达式的正确性。 三、实验要求 1、给出文法如下： G[E] E->T|E+T; T->F|T*F; F->i|(E); +*()i + * ( ) i 21）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式； 1、给出算符优先分析算法如下： k:=1; S[k]:=‘#’; REPEAT 把下一个输入符号读进a中； IF S[k]∈V T THEN j:=k ELSE j:=k-1; WHILE S[j] a DO BEGIN REPEAT Q:=S[j]; IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] Q 把S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N; END OF WHILE; IF S[j] a OR S[j] a THEN BEGIN k:=k+1;S[k]:=a END ELSE ERROR UNTIL a=‘#’ 1、根据给出算法，利用适当的数据结构实现算符优先分析程序； 2、利用算符优先分析程序完成下列功能： 1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束； 2）读入文本文件中的表达式； 3）调用实验2中的词法分析程序搜索单词； 4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息； 5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 习题五数组和广义表 一、单项选择题 1．常对数组进行的两种基本操作是（） A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定. A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3．稀疏矩阵的压缩存储方法是只存储 ( ) A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 5. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。 A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是（）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 9. 广义表（（a,b,c,d））的表头是（），表尾是（）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 10. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、填空题 1．通常采用___________存储结构来存放数组。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行，第_ _列的元素。 数据结构实验五图子系统 实验五 实验题目:图子系统 指导老师:王春红 专业班级:计算机科学与技术系1105班姓名:李慧2011100521杜丽20111005122 白莹2011100523王媛2011100529 2013年 5月23日 实验类型综合实验室_软件实验室一__ 一、实验题目 1 图子系统 二、实验目的和要求 ,(掌握图的存储思想及其存储实现 ,(掌握图的深度、广度优先遍历算法思想及其程序实现 ,(掌握图的常见应用算法的思想及其程序实现。三、实验内容 实验内容二:所有顶点对的最短路径 1(设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。 2(设计分析 用有向加权图表示的交通图中，有向边 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 实验报告五查找（学科：数据结构） 姓名单位班级学号实验日期成绩评定教师签名批改日期 实验名称：实验五查找 5.1 折半查找 【问题描述】 某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。 【基本信息】 （1）建立现有学生信息表，平均成绩已有序。 （2）输入插入学生的记录信息。 （3）用折半查找找到插入位置，并插入记录。 【测试数据】 自行设计。 【实验提示】 （1）用结构数组存储成绩信息表。 （2）对记录中的平均成绩进行折半查找。 【实验报告内容】 设计程序代码如下: #include low=1; hight=n; strcpy(y,s[0].name ); x=s[0].avg ; while(low<=hight) { mid=(low+hight)/2; if(x>s[mid].avg ) hight=mid-1; else low=mid+1; } for(k=0;k 1. 实验步骤： 先定义顺序表的结点： typedef struct { KeyType key; InfoType otherinfo; }ElemType; typedef struct { ElemType *R; int length; }SqList; 然后定义一个随机取数的函数，存到顺序表中： void CreateList(SqList &L,int n) 然后定义一个显示顺序表的函数，将顺序表中的数据显示出来： void ListTraverse(SqList L) 然后通过排序函数，将所有的数据按照从大到小的顺序排列： void BubbleSort(SqList &L) 实验结果： 测试数据： 38 86 9 88 29 18 58 27 排序后： 9 18 27 29 38 58 86 88 BubbleSort排序方法中数据的比较次数为：27 疑难小结： 这个程序的难点在于排序函数，总是把从第几个数开始排序以及怎样循环弄错。 源代码： #include 编译原理实验报告 学院: 计算机与通信工程学院专业: 计算机科学与技术 班级: 学号: 姓名: 实验成绩： 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ：= + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 3.2词法分析程序流程图： 四、词法分析程序的C++语言程序源代码： #include"stdio.h" #include"stdlib.h" #include"string.h" #define _KEY_WORD_END "waiting for your expanding" typedef struct 开始 变量初始化 是否文件结束？ 返回 拼数 Syn=11 返回 拼字符串 是否是关键字？ Syn 为对应关键字的单词种别码 Syn=10 给不同的符号相同的 Syn 值 报错 是 否 数字 字母 是 否 运算符, 界符等 其他 实验五 查找算法实现 1、实验目的 熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。 2、问题描述 查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。 3、基本要求 （1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。 （2）根据给定的数据建立平衡二叉树。 4、测试数据 随即生成 5、源程序 #include<> #include<> #include<> #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>(b)) typedef int Keytype; typedef struct { Keytype key; //关键字域 }ElemType; typedef struct BSTnode { ElemType data; int bf; struct BSTnode *lchild,*rchild; }BSTnode,*BSTree; void InitBSTree(BSTree &T) {T=NULL; } void R_Rotate(BSTree &p) {BSTnode *lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } void L_Rotate(BSTree &p) {BSTnode *rc; rc=p->rchild; p->rchild=rc->lchild; 《数据结构与算法分析》 实验报告书 学期：2014 － 2015 学年第 2 学期 班级：信息管理与信息系统2班 学号： 1310030217 姓名：田洪斌 实验类别：（★）基础型（）设计型 实验时间： 成绩： 信息管理系 一、实验内容 实现程序，按满二叉树给元素编号并输入的方式构造二叉树。 二、实验目的 1、掌握二叉树的静态及操作特点； 2、掌握二叉树的各种遍历方法； 3、掌握二叉树的存储、线索化等在C语言环境中的实现方法； 4、掌握哈夫曼树的构造方法及编码方法。 三、需求分析 用二叉树结构表示来完成输入、编辑、调试、运行的全过程。并规定： a.手动输入数字建立二叉树 b.程序可以输入、调试、运行、显示、遍历 c.测试数据：用户手动输入的数据 四、系统设计 1．数据结构设计 在本程序中对二叉树的存储主要用的是顺序存储结构，将二叉树存储在一个一维数组中。数据的输入输出都是采用整型数据进行。在主函数中只是定义数据类型，程序的实现功能化主要是在主函数中通过给要调用的函数参数来实现程序要求的功能。 2．程序结构设计 （1）程序中主要函数功能： main()/////////////////////////////////////////////主函数 menu()/////////////////////////////////////////////菜单 BiTree CreateBiTree()///////////////////////先序建立二叉树 （2）函数调用关系 见图4-1。 图4-1 函数关系图 五、 调试分析 1.算法和函数中出现了一些系统无法识别的变量，照成程序出现了错 误。原因是没有注意算法与源程序的区别。算法是简单的对源程序进行描述 的，是给人阅读的，所以有些变量没有定义我们就能看懂。而程序中的变量一定要先定义才能够被引用，才能被计算机识别。 2.在调试过程中遇到问题是利用C++程序进行调试的，找出错误并改正。 3.数据输出函数运行不正常，经检查程序，发现是定义错误，更改后错误排除； 六、 测试结果 1．运行时输入正确密码进入主界面，系统根据输入的数字选项来调用相应的函数。主要实现“功能选择”的界面，在这个界面里有显示系统的五大功能，根据每个功能前面的序号进行选择。以下为该界面： main BiTree CreateB iTree() meun() 数据结构与算法课程实验报告实验五：图的相关算法应用 姓名：cll 班级： 学号： 【程序运行效果】 一、实验内容： 求有向网络中任意两点之间的最短路 实验目的： 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 二、问题描述： 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 三、问题的实现： 3.1数据类型的定义 #define MAXVEX 50 //最大的顶点个数 #define MAX 100000 typedef struct{ char name[5]; //城市的名称 }DataType; //数据结构类型 typedef struct{ int arcs[MAXVEX][MAXVEX]; //临接矩阵 DataType data[MAXVEX]; //顶点信息 int vexs; //顶点数 }MGraph,*AdjMetrix; //邻接矩阵表示图 3.2主要的实现思路： 用邻接矩阵的方法表示各城市直接路线的图，之后用Floyd算法求解两点直接的最短距离，并用递归的方法求出途经的城市。 主要源程序代码： #include 编译原理实验报告 题目构造识别字符串的自动机学院 专业 班级 学号 学生姓名 指导教师 西安思源学院教务处制 二〇一年 实验二构造识别符号串的自动机 一、实验目的 1 掌握形式语言与自动机的概念 2 了解正规集及有穷自动机的关系 3 能构造识别相应符号串的自动机 4 能构造词法分析程序所识别的各类单词的自动机 二、实验环境 Microsoft Visual C++ 6.0 三、实验内容 1 用高级语言编写程序：该程序能接受C++所有的标识符。 2 用高级语言编写程序：该程序能接受C++所有的常数(整数和定点小数)。 3 用高级语言编写程序：该程序能接受C++的所有保留字。 4 用高级语言编写程序：该程序能接受C++的所有界符、运算符。 四、设计说明 void main() { void find_word(); void show_all(); void Input(); Input(); cout<<"运行结果如下"< 数据结构课程实验报告-实验5 HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名康小雪 学生学号 20090810310 专业班级计科三班 指导老师李晓鸿 完成日期2010-10-24 一、需求分析 1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将 其转化为后缀表达式，并计算其结果，否则说明该表达式错误 2．.输入的表达式包含数字和运算符及括号，之间用空格隔开 3．数字可以为整数和小数 4．运算结果保留两位小数 输入输出举例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 二、概要设计 在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。 最后用堆栈来实现后缀表达式的计算。 抽象数据类型 二叉树 ADT BiTree { 数据对象D：D是具有相同特性的数据元素集合 数据关系R： 若D为空集，则R为空集，则称BinaryTree 为空二叉树； 若D不为空集，否则R={H}，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-{root}≠空集，则存在D-{root}的一个划分{D1,Dr} 且D1∩Dr=空集； （3）若D1≠空集，则D1中存在唯一元素x1， 词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序，设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 各种单词符号对应的种别码： 表各种单词符号对应的种别码 词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根 据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 实验三的实验报告 学期： 2010 至_2011 第 2 学期 2011年 3月 27日课程名称: 数据结构专业:信息与计算科学 09 级5班实验编号： 03 实验项目：栈和队列实验指导教师 _冯山_姓名：朱群学号： 2009060548 实验成绩： 一实验目的： (1)熟练掌握栈和队列的抽象数据类型及其结构特点； (2)实现基本的栈和队列的基本操作算法程序。 二实验内容：(类C算法的程序实现，任选其一) (1) 设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP 等操作）(必做)； (2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计 与实现（选做）； (3)以迷宫问题为例，以堆栈结构完成迷宫问题的求解算法和程序（选做）。三实验准备： 1) 计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分 析与代码设计与分析准备。 四实验步骤： 1.录入程序代码并进行调试和算法分析； 2.编写实验报告。 五实验过程 一设计与实现基本的堆栈结构下的各种操作（如堆栈的PUSH、POP等操作）（1）问题描述 实现堆栈各种基本操作，如Pop,Push,GetTop等操作，即输入数据，通过Push入栈，再通过Pop操作输出出栈的元素,即入栈a,b,c,d,出栈d,c,b,a （2）算法实现及基本思想 堆栈是后进先出的线性表，由Push输入元素，Pop输出元素，堆栈的Push 操作思想,即插入元素e为新的的栈顶元素，先判断栈满与否，追加存储空间，然后将e值赋给栈顶指针Top。输入数据时用for循环 堆栈的Pop操作思想，先判断栈是否为空，若栈不空，则删除栈的栈顶元素，用e返回其值， （3）数据结构 栈的顺序存储结构 Typedef struct { 合肥师范学院实验报告册 2013 / 2014 学年第2 学期 系别计算机科学与技术系 实验课程数据库原理 专业计算机软件 班级软件一班 姓名周锦 学号1210431081 指导教师潘洁珠 实验一——数据库基本操作 一、实验目的 1.熟悉MS SQL SERVER运行界面，掌握服务器的基本操作。 2.掌握界面操作方法完成用户数据库建立、备份和还原。 3.建立两个实验用的数据库，使用企业管理器和查询分析器对数据库和表进行基本操作。 二、实验预习内容 在认真阅读教材及实验指导书的基础上，上机前请预习以下内容，并在空白处填写相应的步骤或命令。 1.熟悉SQL SERVER 2000 的运行环境，练习服务器基本操作：打开、停止、关闭。 2.使用SQL SERVER 2000 中的企业管理器完成以下任务。 数据库名称：STC 表：STU（sno char(9), sname varchar(50), ssex char(2) , sage int, sdept char(2) ）； COUTSES（cno char(3), cname varchar(50), cpno char(3), credit int ）； SC（sno char(9), cno char(3), grade int ）； 说明：以上为表结构，以sno char（9）为例，说明sno属性设置为字符类型，宽度为9，int指整型数据。 1）建立数据库STC，分别建立以上三张表，并完成数据录入。（表结构及数据参见教材） 建立数据库：数据库→右击鼠标→新建数据库，出现如上图所示的框，然后填上所建数据库的名称。 数据结构上机实验（五）递归 班级：学号：姓名： 上机时间：地点： 一、实验目的 1.理解递归的定义和递归模型。 2.掌握递归设计的一般方法，能用递归算法解决一些较复杂应用问题。 二、实验内容 1．编写程序求解皇后问题 要求：（1）皇后的个数n由用户输入，其值不能超过20； （2）采用递归方法求解。 2．编写一个程序求解背包问题 三、实验过程 1．了解常用函数所在的头文件 stdlib.h stdlib 头文件里包含了C语言的一些函数 该文件包含了的C语言标准库函数的定义 stdlib.h里面定义了五种类型、一些宏和通用工具函数。类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX 和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。具体的内容你自己可以打开编译器的include目录里面的stdlib.h头文件看看。 conio.h conio.h不是C标准库中的头文件。 conio是Console Input/Output（控制台输入输出）的简写，其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作，比如getch()函数等等。 &表示引用传递。在函数参数表中，出现带&这个的形参，表示引用传递。2．程序实现（以下代码仅起参考作用） （1）求解皇后问题 #include 第4～5章串和数组自测卷答案姓名班级 一、填空题（每空1分，共20分） 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。 4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。 6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。 (注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！) 8.设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。 答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标、列下标和元素值。 10.求下列广义表操作的结果： （1）GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 （2）GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ; （3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ; （4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d）; 二、单选题（每小题1分，共15分） （ D ）1.串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （ B ）2.设有两个串p和q，求q在p中首次出现的位置的运算称作：编译原理实验报告语法分析程序的设计
(完整word版)数据结构第五章数组和广义表习题及答案
数据结构实验五图子系统
数据结构实验报告
数据结构实验报告5(电大)
数据结构实验五
北京科技大学编译原理实验报告
数据结构实验——查找算法的实现
数据结构实验五A
数据结构-实验五-图
编译原理实验报告二
数据结构课程实验报告-实验5
编译原理词法分析实验报告
数据结构 实验报告三
数据结构实验报告3543435
数据结构上机实验5
数据结构 第4—5章串和数组自测卷答案
相关主题
文本预览