#include
#define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8
typedef struct {
ElemType *base; //数组元素基址，由InitArray分配
int dim; //数组维数
int *bounds; //数组维界基址，由InitArray分配
int *constants; //数组映象函数常量基址，由InitArray分配
}Array;
Status InitArray(Array &A,int dim,...){//这里用的是“可变参”形参方式。它主要解决维数不定的问题。
//举例：设有4维数组，各维分别是：4,5,6,7（这些数字是随意给的），那么，调用方式：
//InitArray(ar, 4, 4, 5, 6, 7);
//ar其中，ar也是假设的变量名称, 4表示数组有4维, 4, 5, 6, 7这4个数是各维大小
//如果是5维的，那么就这样：
//InitArray(ar, 5, 第一维数，第二维数，第三维数，第四维数，第五维数);
//若维数dim和随后的各维长度合法，则构造相应的数组A，并返回OK。
if (dim<1 ||dim>MAX_ARRAY_DIM) return ERROR;
A.dim=dim;
A.bounds=(int *)malloc(dim*sizeof(int));
if (!A.bounds) exit(OVERFLOW);
//若各维长度合法，则存入A.bounds，并求出A的元素总数elemtotal。
elemtotal=1;
va_start(ap,dim); //ap为va_list类型，是存放变长参数表信息的数组。
for (i=0;i A.bounds[i]=va_arg(ap,int);//从这里可以看出，A.bounds数组中，存放的是各维的大小 if (A.bounds[i]<0) return UNDERFLOW; elemtotal * = A.bounds[i];//各维数之积，自然是数组中元素的总个数 } va_end(ap); A.base=(ElemType *)malloc(elemtotal *sizeof(ElemType));//这个就是“多维数组”的存储本质：一维数组！//用一维方式表示多维数组后（其实，从管理和使用的角度看，内存就只有一维这么一种形式），存在如何按“多维”的逻辑角度定位元素的问题。再说清楚些：假设前面所讲的4维数组，其元素用下标形式表示，范围为：(0,0,0,0)到(3,4,5,6)。对于任意下标（在有效范围内）(i1, i2, i3, i4)所对应的元素，转换到“一维”空间后，其下标应该是什么？这就是这个程序后面要处理的主要问题。 if (!A.base) exit (OVERFLOW): //求映象函数的常数ci（i为下标），并存入A.constants[i-1]，i=1，...dim。 A.constants=(int *)malloc(dim *sizeof(int)); if (!A.constants)exit (OVERFLOW); //以前面的4维数组为例子，其中A.bounds[0]=4，A.bounds[1]=5，A.bounds[2]=6，A.bounds[3]=7。 //跟踪下面的程序： A.constants[dim-1]=1;//A.constants[3] = 1 for (i=dim-2;i>=0;--i)//A.constants[2] = 7，A.constants[1] = 6*7，A.constants[0] = 5*6*7 A.constants[i]=A.bounds[i+1] * A.constants[i+1]; //说到这里，这个问题就清晰了：A.constants中的元素，是帮助定位用的。比如说：对于(2,0,0,0)这个下标 的元素，应该越过前面的(0,0,0,0)~(0,4,5,6)和(1,0,0,0)~(1,4,5,6)这两大块，而这两大块中的每一块都有5*6*7个元素，这正好就是A.constants[0]中所存放的数据啊！ //现在应该明白了吧！ return OK; } status Locate(Array A,va_list ap,int &off){ //若ap指示的各下标值合法，则求出该元素在A中相对地址off。 off=0; for (i=0;i ind=va_arg(ap,int); if (ind<0 || ind>=A.bounds[i]) return OVERFLOW； off + = A.constants[i] * ind; } return OK; 1、A.constants[dim-1]等于1因为程序里是通过乘法进行计算的，所以初值必须为1； 2、（这是关键）在具体定位时，最后那一维其实直接取决于下标。假设有下标：(3, 2, 2, 5)，那么定位公式应该是： t = 3*A.constants[0] + 2*A.constants[1] + 2*A.constans[2] + 5*A.constans[3]//因为A.constans[3]的值是1，所以可以不用写；写上也有一个好处：利于循环体的一致性。 暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题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 习题五数组和广义表 一、单项选择题 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．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。 A. 808 B. 818 C. 1010 D. 1020 2．同一数组中的元素( )。 A. 长度可以不同B．不限C．类型相同 D. 长度不限 3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。 (1)存放A至少需要( )个字节。 (2)A的第8列和第5行共占( )个字节。 (3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址 一致。 供选择的答案： (1)A. 90 B. 180 C. 240 D. 270 (2) A. 108 B. 114 C. 54 D. 60 (3)[8][5] B. A[3][10] [5][8] [O][9] 4.数组与一般线性表的区别主要是( )。 A.存储方面 B.元素类型方面 C.逻辑结构方面 D.不能进行插入和删除运算 5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。 A. (i-l)×n+j B. (i-l)×n+j-l C．i×(j-l) D. j×m+i-l 6．所谓稀疏矩阵指的是( )。 A.零元素个数较多的矩阵 B.零元素个数占矩阵元素中总个数一半的矩阵 C.零元素个数远远多于非零元素个数且分布没有规律的矩阵 D.包含有零元素的矩阵 7．对稀疏矩阵进行压缩存储的目的是( )。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D. 降低运算的时间复杂度 8．稀疏矩阵一般的压缩存储方法有两种，即( )。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。 A. 60 B. 66 C．18000 D．33 10. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+I)/2] 中，则对任一上三角元素a[i][j]对应T[k]的下标k是( )。 A. i(i-l)/2+j B. j(j-l)/2+i C. i(j-i)/2+1 D. j(i-l)/2+1 11．已知广义表L=((x，y,z)，a，(u，t，w))，从L表中取出原子项t的运算是( ) A. head(tail(tail(L))) B. tail(head(head(taiI(L)))) C. head(tail(head(taiI(L)))) D. head(tail(head(tail(tail(L))))) 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 实验五 查找算法实现 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 数据结构课程实验报告-实验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， 实验三的实验报告 学期： 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中首次出现的位置的运算称作： 《数据结构》实验报告 班级:10011006 姓名:刘恋学号:2010302521 E-mail:_1020383169@https://www.doczj.com/doc/fb6775375.html,日期:12.21 ◎实验题目: 图的结构建立和最短路径算法 ◎实验内容： 利用邻接矩阵构造图，并求出某一顶点到其余顶点的最短路径并打印输出。 一、需求分析 1、本实验中，以计算机和用户的对话形式进行。 2、程序所执行的命令有： 构造顶点关系和边的存储结构；初始图的结构；详图中插入元素；查找元素在图顶点中的位置；创建邻接表；查找最短路径；输出。 3、显示界面： 二概要设计 为了实现上述操作，应以链栈为存储结构。 1. 基本操作： void InitGraph(MGraph *G) void InsertGreph(MGraph *G,int i,VertexType e) 插入元素 int LocateVex(MGraph G,VertexType v1) 确定元素位置 void CreatGraph(MGraph *G) 构建邻接矩阵 void ShortestPath(MGraph G,int v0,int **p,int *D) 查找最短路径 void Print(MGraph G) 输出邻接矩阵 三详细设计 1.元素类型，结构定义 typedef struct AreCell { int adj; //权值 }AreCell,**AdjMatrix; typedef struct type { char data[3];//顶点值 }VertexType; typedef struct { VertexType *vexs;//顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum;//定点个数，弧的条数 }MGraph; 2.各模块分析： （1）主函数模块 int main() { MGraph G; VertexType e; int i,j; int **p; 数据结构实验报告全集 实验一线性表基本操作和简单程序 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<<"建立一个单链表"<数据结构实验8实验报告
数据结构实验五矩阵的压缩存储与运算学习资料
数据结构实验五-查找与排序的实现
(完整word版)数据结构第五章数组和广义表习题及答案
数据结构实验五图子系统
数据结构实验报告
数据结构实验报告5(电大)
数据结构 第五章数组和广义表
数据结构实验五
数据结构实验——查找算法的实现
数据结构实验五A
数据结构-实验五-图
数据结构课程实验报告-实验5
数据结构 实验报告三
数据结构实验报告3543435
数据结构上机实验5
数据结构 第4—5章串和数组自测卷答案
数据结构实验报告5
数据结构实验报告全集
相关主题
文本预览