第一篇：数据结构基础实验1
浙江大学城市学院实验报告
课程名称
数据结构基础
实验项目名称
实验一
熟悉Project组织应用程序
学生姓名
专业班级
学号
实验成绩
指导老师（签名）
日期
一.实验目的和要求
1、熟悉VC6.0开发环境；使用Workspace和Project组织应用程序；
2、回顾C语言程序设计，编写完整的实验应用程序，并调试通过。
3、掌握文件包含，以及库函数iostream.h中的标准输入、输出流对象cin和cout，理解“引用（&）”方式的参数传递。
二.实验内容
1、按下述介绍的方法，练习并掌握使用Project组织应用程序的方法。步骤：
① 启动VC++，选择“文件（File）”菜单中的“新建（New）”项，选择“工程（Projects）页，然后选择“Win32 Console Application”，在右上角输入project的名称（如：test1），再选择合适的存储路径，然后按下“确定”按钮。这样就建立了一个新的工程。如下图所示：
② 在窗口左侧出现WorkSpace视图，选择“FileView”页可浏览该工程所包含的文件。然后可在项目中新建源文件（菜单：文件新建），包括“C/C++Header File”和“C/C++Source File”两类文件，或将已有的源文件加入到这个工程中（菜单：工程增加到工程）。如下图：
完成后程序组织结构如下图：
其中Source Fileste中包含主程序等源程序文件（如：test1_main.cpp），Header Fileste中包含头文件等（如：test1_function.h）。
2、在VC中建立工程（取名为test1），并编写如下程序加入到工程中，编译执行该程序。要求使用cin和cout进行数据的输入输出。程序题目如下：
设a为长度为n的整数型一维数组。
（1）试编写求a中的最大值、最小值和平均值的函数。
请分别用两种方法完成：
分别编写三个函数int aMAX(int *a,int n)、int aMIN(int *a,int n)、int aAVE(int *a,int n)实现求最大值、最小值和平均值。
用一个函数void aMAX_MIN_AVE(int *a, int n, int &max, int &min, int &aver)实现求上述三个值，用“引用参数”带回结果。
（2）试编写函数 int prime_SUM(int *a, int n)计算a中所有素数之和。（3）编写函数 void aSORT(int *a,int n)对a进行从小到大的排序，并输出排序结果。
要求：
把以上函数存放在头文件test1.h中，并自行设计主函数来测试各类操作实现的正确性，主函数存放在文件test1.cpp中。
3、填写实验报告，实验报告文件取名为report1.doc。
4、上传实验报告文件report1.doc、源程序文件test1.cpp及test1.h到Ftp服务器上（ftp://10.61.14.240:5000）自己的文件夹下。
三.函数的功能说明及算法思路
（包括每个函数的功能说明，及一些重要函数的算法实现思路）
1、求a中的最大值 int aMAX(int *a,int n){ int i,max;max=a[0];for(i=0;i if(max max=a[i];} return max;} 2、求a中的最小值 int aMIN(int *a,int n){ int i,min=a[0];for(i=0;i if(min>a[i]) min=a[i];} return min;} 3、求a中的平均值 int aAVE(int *a,int n){ int i,sum=0,ave;for(i=0;i sum=sum+a[i]; ave=sum/n; return ave;} 4、用一个函数求a中的最大值、最小值、平均值 void aMAX_MIN_AVE(int *a, int n, int &max, int &min, int &aver){ int sum,i;sum=0;max=a[0];min=a[0];aver=a[0];for(i=0;i if(a[i]>max)max=a[i]; if(a[i] sum=sum+a[i];} aver=sum/n;} 5、计算a中所有素数之和 int prime_SUM(int *a, int n){ int i,sum=0;for(i=0;i if(prime(a[i])) sum=sum+a[i];} return sum;} int prime(int x) //判断一个数是否是素数 { int i;for(i=2;i<(x/2);i++) if(x%i==0)break; if(i>=x/2) return 1; else return 0;} 6、对a进行从小到大的排序，并输出排序结果 void aSORT(int *a,int n){ int i, index,j,temp;for(i=0;i index=i; for(j=i+1;j if(a[j] index=j; temp=a[i]; a[i]=a[index]; a[index]=temp;} } 四.实验结果与分析 （包括运行结果截图、结果分析等）input data:0 1 2 3 4 5 6 7 8 9 max in a:9 min in a:0 ave in a:4 sum of prime:18 max in a:9 min in a:0 ave in a:4 the sort is:0 1 2 3 4 5 6 7 8 9Press any key to continue 五.心得体会 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。） 最开始编译时，总是有十几个错误，或是变量未定义，或是函数中有错误，在经过调试和与同学交流之后，终于解决了这些问题。这使我意识到自己在综合编程方面的不足，函数一多容易搞混，以后一定改正。【附录----源程序】 Test1_func.h int prime(int x) ////判断一个数是否是素数 { } int aMAX(int *a,int n){ } int aMIN(int *a,int n)int i,max;max=a[0];for(i=0;i } return max;if(max if(x%i==0)break;if(i>=x/2)return 1;else return 0;{ } int aAVE(int *a,int n){ } int prime_SUM(int *a, int n){ return ave;ave=sum/n;int i,sum=0,ave;for(i=0;i } return min;if(min>a[i])min=a[i]; } int i,sum=0;for(i=0;i } return sum;if(prime(a[i]))sum=sum+a[i];void aMAX_MIN_AVE(int *a, int n, int &max, int &min, int &aver){ } int sum,i;sum=0;max=a[0];min=a[0];aver=a[0];for(i=0;i } aver=sum/n;if(a[i]>max)max=a[i];if(a[i] void aSORT(int *a,int n){ int i, index,j,temp;for(i=0;i } index=i;for(j=i+1;j if(a[j] Test1_main.cpp }#include } int a[10],i,max,min,ave;cout<<“input data:”;for(i=0;i<10;i++)cin>>“%d”,&a[i];cout<<“max in a:”< 数据结构基础实验总结 本学期开设的《数据结构基础》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。 各章知识点概要 第一章交代了该学科的相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构。紧接着介绍了一些常用的数据运算。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。 第二章具体地介绍了线性表的概念、基本运算及其应用。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。链表与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）、定义、结构、功能和基本算法。 第四章堆栈与队列是两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。 第五章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法：递归算法、先序、中序和后序遍历非递归算法。树与二叉树是不同的概念。教材介绍了树的概念、遍历和存储结构，还有树和二叉树的相互关系，树怎样转化成二叉树，二叉树又如何转换为树等。 第七章介绍了图的概念及其应用，是本书的难点。图的存储结构的知识点有：邻接矩阵、邻接表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、最短路径问题。 学习体会和教学建议 这是一门纯属于设计的科目，它需用把理论变为上机调试。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序。 这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。 其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好 多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。 建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生保持良好的精神状态。 以上便是我对《数据结构基础》这门课的学习总结，我会抓紧时间将没有吃透的知识点补齐。因为我们还要学习《数据结构与算法》，所以今后我会继续学习，克服学习中遇到的难关，在打牢基础的前提下向更深入的层面迈进！ 《数据结构》实验(训)指导书 电气与信息工程学院实验中心 前 言 《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍线性结构、树型结构、图形结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法分析、设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法的最佳途径是上机实验。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写该实验指导书。 一、实验目的、要求和任务 计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。 1.熟练掌握C语言的编辑、编译、调试程序。2.会书写类C语言的算法，并将算法转变为程序实现。 3.正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。4.有较强的逻辑分析能力。 5.针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。 6.学会分析研究计算机加工的数据结构的特性，以便为应用设计的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。 7.本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力。 8.通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序做一些铺垫。 二、实验基本内容及学时分配 为了达到实验目的，本课程安排了4个实验单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实验单元与教科书的各章只具有粗略的对应关系，一个实验题常常涉及到几部分教学内容。总学时：8学时。 1、线性表（2学时） （1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；（2）以线性表的各种操作（建立、插入、删除等）的实现为重点； （3）通过本次实验帮助学生提高C语言的编程能力（特别是函数参数、指针类型、链表的使用）。 2、数组和广义表（2学时）（1）掌握稀疏矩阵的压缩存储 （2）掌握稀疏矩阵的转置算法 3、树与二叉树（2学时） 常见的二叉树遍历算法有先序遍历，中序遍历和后序遍历算法。实现简单的先序遍历，中序遍历和后序遍历算法。 4、排序（2学时） 常见的内部排序算法，插入类排序算法，如直接插入排序和希尔排序；交换类排序算法，如冒泡排序和快速排序；选择类排序算法，如简单选择排序、树形选择类排序和堆排序。实冒泡排序或者直接插入排序算法。 三、说明 该课程采用理论与实践相结合的教学方法，集知识性与趣味性于一体，达到良好的教学效果。硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供电脑等设备。学生每次上机实验都必须遵守实验室的有关规定。 四、实验报告规范 实验报告的内容包括： 1、实验目的：说明实验所验证的知识点。 2、需求分析：以无歧义的陈述说明程序设计的任务、约束条件、输入输出要求、对功能的规定及模型。 3、逻辑设计：说明本程序中用到的所有抽象的数据类型的定义、主程序的流程以及各程序模块之间的层次调用关系。 4、详细设计：逻辑设计中定义的所有数据类型的实现，核心算法的设计描述、人机界面设计、函数之间调用关系的描述，主要功能的算法框架，测试数据设计。 5、测试分析：测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。 6、心得：软件设计与实现过程中的经验与体会，进一步改进的设想。 7、程序清单：源程序中应有足够的注释。如果提交源程序软盘，列出程序文件名。 五、如何提高上机效率 为了提高上机的效率，真正达到实验目的，要求同学做好实验前的准备工作，写好实验预习报告，即实验报告规范中的1）、2）、3）、4）部分，编写好程序，并用一组测试数据手工执行程序静态检查程序是否有错，通过阅读、执行程序或给别人讲解自己的程序而深入全面地理解程序逻辑，提高程序的正确性。对C语言程序不熟悉的同学，上机时最好带上C语言程序设计的教材，以备查阅。调试中遇到问题，应认真分析，确定可疑点，设置调试断点或输出断点处变量的值，以便发现问题，迅速排除问题，加快调试速度。 实验室要求： 不能旷课，不迟到，不穿拖鞋进实验室 实验需预习报告（不能单纯抄写，预习程序代码）实验报告（总结，注释，实验结果） 目 录 实验一 线性表实验（设计性实验）..........................................4 实验二 数组和广义表实验（设计性实验）....................................6 实验三 树与二叉树（设计性实验）..........................................8 实验四 排序（设计性实验）................................................9 实验一 线性表实验（设计性实验） 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 五、实验提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype;/* 线性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 顺序表的长度 */ }sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype;typedef struct node { elemtype data;//数据域 struct node *next;//指针域 }linklist; 注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址： p=(linklist *)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。 六、实验总结与思考 1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在main函数里如果去掉L=&a语句，会出现什么结果？ 实验二 数组和广义表实验（设计性实验） 一、实验目的 1.掌握稀疏矩阵的压缩存储 2.掌握稀疏矩阵的转置算法 二、实验内容 1.实现上三角阵的压缩存储。 2.用三元组顺序表存储稀疏矩阵，并实现矩阵的转置。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.创建一个数组。2.输入数据 3.给定矩阵任一元素的下标，4.打印给定下标所对应的数据。5.创建三元组顺序表。a22 7.A输出对应的矩阵。 21五、实验提示 aaa6.输入矩阵中的数据。11a11a313233a21221.对于如下对称矩阵： Aaaa424341a31a32a331个位置，a21存入到第二个位置，将它们存入到一个线性数组中B，不存非零元素，a11存入到第a41a42aija44aij的位则aij能存到第几个位置，我们要以用梯形公式算面积。置是它上面的元素之和再加上左边的元素之和。 它上面的元素之和为((1+(i-1))×(i-1)/2，左边的元素为(j-1)所以这个元素存储的位置为k=i(i-1)/2+j-1。 因为矩阵A为对称矩阵，(另一部分没有写出)，所以另一部分的元素为 k=j(j-1)/2+i-1.所以存在关系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i 2.结点结构 struct triple{ int i,j;//非零元的行下标和列下标 elemtype e;//非零元数据} 三元组顺序表存储类型 struct tsmatrix{ triple data[12500];aaa44 int mu,nu,tu;} 三元顺序表的转置 方法：(1)将矩阵行列互换，(2)重排矩阵 六、实验总结与思考 1.如何存储三对角阵？ 2.如何用行逻辑链接顺序表及十字链表存储稀疏矩阵？ 实验三 树与二叉树（设计性实验） 一、实验目的 1.掌握稀疏矩阵的压缩存储 2.掌握稀疏矩阵的转置算法 二、实验内容 1.练习二叉树的建立与存储 2.练习二叉树的遍历 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。 2.建立二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历的结果。 五、实验提示 建立二叉树的代码如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$') {q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一个新结点q*/ q->data = x;q->lchild = NULL;q->rchild = NULL; s[i] = q;/*q新结点地址存入s指针数组中*/ if(i!= 1)/*i = 1，对应的结点是根结点*/ {j = i / 2;/*求双亲结点的编号j*/ if(i % 2 == 0)s[j]->lchild = q;/*q结点编号为偶数则挂在双亲结点j的左边*/ else s[j]->rchild = q;} /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(“i,x = ”); scanf(“%d,%c”,&i,&x);} return s[1];/*返回根结点地址*/ } 六、实验总结与思考 1.如何用孩子兄弟表示法存储树？ 2.熟悉及难赫夫曼树。 实验四 排序（设计性实验） 一、实验目的 1.掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 2.深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用； 3.了解各种方法的排序过程及其时间复杂度的分析方法。 二、实验内容 统计成绩 给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法： （1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；（2）按名次列出每个学生的姓名与分数。 三、实验仪器设备与器材 上机电脑 四、实验步骤 1.定义结构体。2.定义结构体数组。 3.定出主程序，对数据进行排序。 五、实验提示 #define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n请输入学生成绩: n”);for(i=0;i if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score 六、实验总结与思考 1.快速排序算法解决本问题。2.较各种排序算法的优缺点及。 3.使用其它排序算法实现该问题（直接插入排序、希尔排序、简单选择排序、堆排序等）。 数 据 结 构 实 验 指 导 书 南京工程学院 信息管理与信息系统教研室 2014年3月 实验一 线性表操作 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype;/* 线性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 顺序表的长度 */ }sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2.注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype;typedef struct node { elemtype data;//数据域 struct node *next;//指针域 }linklist;注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址： p=(linklist *)malloc(sizeof(linklist));该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。 五、思考与提高 1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在main函数里如果去掉L=&a语句，会出现什么结果？ 实验二 栈和队列的应用 一、实验目的 1.掌握栈的顺序表示和实现 2.掌握队列的链式表示和实现 二、实验内容 1.编写一个程序实现顺序栈的各种基本运算。2.实现队列的链式表示和实现。 三、实验步骤 1.顺序栈(1)初始化顺序栈;(2)插入元素(3)删除栈顶元素(4)取栈顶元素(5)遍历顺序栈(6)置空顺序栈 2.链队列 (1)初始化并建立链队列(2.)入链队列(3)出链队列(4)遍历链队列 四、实现提示 1./*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM];int top;}SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack));/*申请空间*/} /*入栈函数*/ void Push(SqStack *p,ElemType x){if(p->top SqStack S; ElemType e; int N; /*初始化顺序栈*/ /*入栈*/ /*出栈*/ /*遍历顺序栈*/ getch();} 2./*定义链队列*/ typedef struct Qnode { ElemType data;struct Qnode *next;}Qnodetype;typedef struct { Qnodetype *front;Qnodetype *rear;}Lqueue; /*初始化并建立链队列函数*/ void creat(Lqueue *q) { h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申请空间*/ h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循环快速输入数据*/ { scanf(“%d”,&x);Lappend(q,x);} /*利用入链队列函数快速输入数据*/ } /*入链队列函数*/ void Lappend(Lqueue *q,int x){ s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;} /*出链队列函数*/ ElemType Ldelete(Lqueue *q){ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);} /*释放空间*/ /*遍历链队列函数*/ void display(Lqueue *q){ while(p!=NULL)/*利用条件判断是否到队尾*/ { printf(“%d-->”,p->data);p=p->next;} } 可参考如下代码： #include “stdio.h” #define MaxSize 100 typedef int ElemType;main(){ LinkQueue Q; ElemType e; /*初始化并建立链队列*/ /*入链队列*/ /*出链队列*/ *遍历链队列*/ } DestoryQueue(&Q); getch();} 五、思考与提高 1.读栈顶元素的算法与退栈顶元素的算法有何区别？ 试写一个算法，判别读入的一个以‘@’为结束符的字符序列是否是‚回文‛。实验三 树操作 一、实验目的 1.通过实验，掌握二叉树的建立与存储 2.通过实验，掌握二叉树的遍历方法 二、实验内容 1.练习二叉树的建立与存储 2.练习二叉树的遍历 三、实验步骤 1.建立二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。 2.建立二叉树,并通过调用函数, 输出先序遍历、中序遍历与后序遍历的结果。 四、实现提示 1.采用递归方法建立二叉树： 首先建立二叉树的根 结点，然后建立其左右子树，直到空子树为止。 2.先序遍历、中序遍历与后序遍历二叉树。#include BiTree CreateBiTree(BiTree &T){ } /*先序遍历*/ Status PreOrderTraverse(BiTree T){ } /*中序遍历*/ Status InOrderTraverse(BiTree T){ } /*后序遍历*/ Status PostOrderTraverse(BiTree T){ } int main(){ BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf(“n”);/*先序遍历*/ InOrderTraverse(T);printf(“n”);/*中序遍历*/ PostOrderTraverse(T);printf(“n”);/*后序遍历*/ return 0;} 五、思考与提高 编写递归算法，计算二叉树中叶子结点的数目。 目 录 实验规则················································2 实验环境················································2 实验报告要求············································3 实验一 单链表 （一）······································4 实验二 单链表 （二）······································5 实验三 栈···············································6 实验四 二叉树···········································7 实验五 最短路径·········································8 实验六 内部排序·········································9 实 验 规 则 为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则： 1、实验前必须充分预习，完成指定的预习任务。预习要求如下： （1）认真阅读指导书，进行必要的设计与计算。（2）熟悉实验内容。 （3）预先复习，并按要求编写程序。（4）未完成预习任务者不得进入实验室。 2、遵守以下纪律： （1）在实验室不得做和实验无关的事情。 （2）进行任课老师指定内容以外的实验，必须经指导教师同意。（3）遵守纪律，不迟到。 （4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。 实 验 环 境 本实验在386以上的微机上进行，运行环境为VC6.0。 实验报告要求 1、实验题目 2．实验目的 3．实验环境 4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案 6．实验思考：（学生对本次实验的收获的总结） 实验一 单链表 （一）一、实验目的 掌握线性表的链式存储结构及其基本操作。 二、预习要求 1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。 2、根据要求，编写程序准备上机调试。 三、实验内容 实现一个简单的学生信息管理系统，该系统的功能有： 1、利用单链表建立学生基本信息表 2、浏览每个学生的信息 3、根据学号查询某个学生的基本信息 4、添加学生信息到单链表中 5、删除一个学生的信息 四、实现提示 设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。 实验二 单链表 （二）一、实验目的 掌握线性表的链式存储结构及其基本操作。 二、预习要求 1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。 2、根据要求，编写程序准备上机调试。 三、实验内容 1、实现单链表的就地逆置。 2、建立两个非递减有序单链表，然后合并成一个非递减链表。 3、建立两个非递减有序单链表，然后合并成一个非递增链表。 4、编写一个主函数,调试上述算法。 四、选做题、思考题 1、如何用带表头结点的单链表作为多项式的存储表示，实现两个多项式的相加。 2、约毖夫环的实现。 3、如何利用文件实现学生信息的存取。 实验三 栈 一、实验目的 深入了解并掌握栈的特性及其在实际中的应用；熟练掌握栈的算法实现；运用栈操作求解实际问题。 二、预习要求 1、看懂书上的算法，深入理解栈的特性和存储结构，以便在实际问题背景下灵活运用。 2、根据要求，编写程序准备上机调试。 三、实验内容 利用栈实现数据的分类，要求当输入为偶数时进栈1，当输入为奇数时进栈2，最后分别从栈1和栈2输出偶数和奇数序列。 四、实现提示 1、开辟一个连续的存储空间，实现两个栈顺序存储空间的共享；分别在两端设置栈顶指针，并按要求实现栈操作。 2、采用顺序存储实现栈的初始化、入栈、出栈操作。 五、选做题、思考题 1、两栈空间共享时，栈满的条件是什么？ 2、为停车场编制进行管理的模拟程序（习题集P96，2.1）。 3、编写程序，利用栈实现表达式求值。 实验四 二叉树 一、实验目的 通过实践掌握二叉树的存储结构和遍历思想；掌握二叉树的常见算法的程序实现。 二、预习要求 二叉树的三种遍历方法。 三、实验内容 1、输入字符序列，建立二叉链表。 2、利用栈，编写非递归算法，编程实现二叉树的中序遍历。 3、求二叉树的叶子结点个数。 4、在主函数中设计一个简单的菜单，分别调试上述算法。 四、选做题、思考题 1、如何实现二叉树的后序遍历（非递归）。 2、如何求二叉树的高度。 实验五 最短路径（旅游景点导游咨询模拟） 一、实验目的 利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。 二、预习要求 学习了解图的存储结构，掌握求最短路径的两种算法。 三、实验内容 设计一个旅游景点导游模拟程序，为来访的客人提供景点最短路径的信息查询服务，任意选取n城市，构成一个有向带权图，图中顶点表示城市，边上的权值表示两点间的距离，根据用户指定的始点和终点输出相应的最短路径。 四、实现提示 咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的城市。存储结构可选用邻接矩阵。 五、选做题、思考题 1．如何实现对城市信息进行编辑（如：添加或删除）的功能。 2．用邻接表作存储结构，求一指定景点出发，到其余各景点的最短路径。 实验六 内部排序 一、实验目的 直观感受算法的关键字比较次数和关键字移动次数。 二、预习要求 1、常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。 2、根据要求，编写程序准备上机调试。 三、实验内容 1、对直接插入排序和简单选择排序算法进行关键字比较次数和关键字移动次数的比较。 2、利用链式存储结构，编写程序，实现直接插入排序和冒泡排序。 四、实现提示 测试数据可以为几组典型的数据：正序、逆序、乱序。 五、选做题、思考题 1、快速排序算法的非递归实现。 2、结合实验，理解针对不同待排元素的特点而选择不同排序方法的重要性。 3、如何对本实验进行时间、空间的复杂度分析。第二篇：数据结构基础__实验总结
第三篇：《数据结构》实验指导书
第四篇：《数据结构》实验指导书
第五篇：数据结构实验指导书
点击咨询 