第一篇：数据结构第一次实验要求
数据结构实验课
第一组实验（2012.05.6）
一、线性表
1、题集P79，实验1.1
1）把描述的问题中包含的相关对象及其之间的关系找出来；
2）画一张对象及其关系图；
3）把每个对象投影到一个线性表；
4）把关系投影到表上或表间操作；
5）用C或C++实现；
6）上机调试。
2、参照教材P31，算法2.12，实现合并有序单链表（均带头节点）操作；
3、自学题集P83实习报告，用对象及其关系图描述问题，并分析它们的实现细节；
4、从你学习、生活环境中举出一个线性表的应用实例，分析它包含的对象及其之间的关系。尝试着用线性表顺序表示和链式表示来实现。
二、队列与栈
1、从你学习生活中找出一个典型的队列的实例，分析它的特点，并参照教材P60~65中的算法，分别实现这个队列的链式表示和顺序表示。
2、从你学习生活中找出一个典型的栈的实例，分析并与队列实例进行比较，找出它们的异同，并参照教材P45~47中的内容，实现栈的两种存储模式。
3、回文识别：自定义顺序栈及队列，并在实现“回文识别算法”中运用.题集P26, 3.31
三、要求：把自己严格按照一个入门专业人员来要求。
1、以上实验要求可以以组为单位讨论完成，但每组人数不得超过5人，且需要分配一个小组长负责本组的学习组织和进展跟踪；
2、把以上实验中需要的分析步骤和分析结果写成正式的报告，以组为单位在实验课上进行讲解（尽量让每一位同学表达一次）；
3、实现部分在课下组织讨论，尽量提前写出详细实现草稿，实验课上进行调试和实验结果汇报；
4、讨论和汇报过程中，每位同学要做好笔记，分析对比自己和他人在处理问题中存在的不同，总结自己的不足和长处，以及其他同学给你的借鉴，为进一步改进自己的学习方式方法以及态度给出切实可行的建议。
第二篇：《数据结构》上机实验的目的和要求
《数据结构》上机实验的目的和要求
通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。
要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为：
1、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：
（1）输入的形式和输出值的范围；
（2）输出的形式；
（3）程序所能达到的功能；
（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。
2、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。
3、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。
4、调试分析：
（1）调试过程中所遇到的问题及解决方法；
（2）算法的时空分析；
（3）经验与体会。
5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。
6、测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。
第三篇：《数据结构》实验指导书
《数据结构》实验(训)指导书
电气与信息工程学院实验中心
前 言
《数据结构》是计算机相关专业的一门核心基础课程，也是很多高校研究生入学考试专业课必考课程之一。它主要介绍线性结构、树型结构、图形结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法分析、设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法的最佳途径是上机实验。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写该实验指导书。
一、实验目的、要求和任务
计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。
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、如何对本实验进行时间、空间的复杂度分析。第四篇：《数据结构》实验指导书
第五篇：数据结构实验指导书
点击咨询 