《数据结构》实验指导书广东工业大学信息工程学院下面介绍一下数据结构实验环境的启动，教材里的算法使用类C语言描述，具体实现需要支持ANSI C++标准的编译器。

考虑到同学们的基础和使用习惯，我们利用Windows环境下的Visual C++来进行实验。

首先启动Visual C++，从开始——程序——Visual C++，启动好Visual C++界面如图1所示：点击菜单“文件”出现下拉菜单，选择“新建”，如下图：在上面的界面里，我们选择Win32 Console Application选项，并在工程栏目里输入一个文件名，位置根据自己的保存路径设置即可，确定后回车，出现如下界面：再点击完成，出现下面的界面：点击“OK”，出现如下界面：在上面界面里，我们开始做实验时，只要通过“文件”菜单来添加源文件或头文件进入到程序编辑状态，如下图所示：点击“OK”后进行程序编辑窗口，如下所示：这时就可以编辑程序了。

实验时将头文件（.h后缀文件）放在header files 里，而源文件（.cpp后缀文件）放在source files里进行编辑调试。

实验一：线性表的存储结构与顺序表的存储实现实验内容：编写一个程序实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中。

实验目的：了解并掌握线性表的逻辑结构特性，通过实验掌握顺序存储结构的描述方法及用高级语言进行编程实现的方法。

实验步骤：1．定义顺序表类型和结构：首先要想好自己定义的顺序表叫什么名称，顺序表结构里包括有什么项目，每一项该是什么类型，如：typedefstruct{ElemType *elem;int length;intlistsize;} SqList;2.将定义好的顺序表初始化，如：Status InitList_Sq(SqList&L){L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;}3.创建顺序表，如：void Create_Sq(SqList&L){ //创建顺序表inti,n;printf("创建一个有序表:\n");printf("输入有序表中元素的个数:");scanf("%d",&n);L.length=n;for(i=0;i<n;i++){printf("输入第%d个元素的值:",i+1);scanf("%d",&L.elem[i]);printf("\n");}}4．编写顺序表的元素输出函数voidDisp_Sq(SqList L){inti,n;n=L.length;for(i=0;i<n;i++)printf("%5d",L.elem[i]);printf("\n");}5．编写合并程序，实现题目要求的合并功能void Combine(SqList&La, SqList&Lb){//把两个有序表合为一个函数体请同学们自己编}实验二：栈和队列的应用一、实验目的熟练掌握栈结构及其应用二、实验内容利用栈结构具有先进后出的特性，编程实现：输入一个任意十进制数，转换八进制数进行输出。

1、定义栈结构，如：#define stack_size 100#define stackincrement 10typedefstruct{int *base;int *top;intstacksize;}SqStack;2．设计基本算法1)对栈进行初始化:Status InitStack (SqStack&S) {//构造一个空栈S.base = (Selemtype *)malloc(stack_size * sizeof(ElemType));if (!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = stack_size;return OK;}//InitStack2) 返回栈顶函数:Status GetTop(SqStackS,Selemtype&e){//若栈不空，则用e返回S的栈顶元素，并返回OK;否则返回ERROR if (S.top ==S.base) return ERROR;e = *(S.top-1);return OK;}// GetTop3)入栈函数Status Push (SqStack&S,Selemtype e) {//插入元素e为新的栈顶元素if (S.top - S.base>=S.stacksize){//栈满，追加存储空间S.base = (ElemType*)realloc (S.base,(S.stacksize + stackincrement) * sizeof (ElemType));if (!S.base) exit (OVERFLOW);//存储分配失败S.top = S.base+S.stacksize;S.stacksize +=stackincrement;}*S.top++=e;return OK;}//Push4)栈空处理函数Status StackEmpty(SqStack&S){if (S.base == S.top) return OK;else return ERROR;} // StackEmpty5)出栈函数Status Pop(SqStack&S,Selemtype&e){//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK//,否则返回ERRORif (S.top==S.base) return ERROR;e=*--S.top;return OK;}//Pop6)设计数制转换算法，编写转换函数conversion（）.void conversion(structSqStack&S){数制转换算法由同学们自己完成}实验三：二叉树的构造与遍历方法一、实验目的通过实验能熟练掌握二叉树的定义、性质和存储结构;二叉树的遍历和线索以及遍历算法的各种描述形式。

二、实验内容用先序次序的方法构造一棵二叉树，并以三种遍历方式遍历二叉树。

三、实验步骤1、定义二叉树和用先序次序构造二叉树。

typedefstructBiTNode{//注意采用的是二叉链表作为二叉树的存储结构TElemType data;structBiTNode *lchild,*rchild;}BiTNode,*BiTree;Status CreateBiTree_PreOrder(BiTree&T){ //先序次序构造二叉树TElemTypech;scanf("%c",&ch);if(ch==' ') T=NULL;else {if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data=ch;CreateBiTree_PreOrder(T->lchild);CreateBiTree_PreOrder(T->rchild);}return OK;}2、根据先序遍历、中序遍历和后序遍历的方法编序相应的函数，如：Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //先序遍历if(T){if((*Visit)(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;}return OK;}Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e)){ //中序遍历if(T!=NULL){if(InOrderTraverse(T->lchild,Visit))if((*Visit)(T->data))if(InOrderTraverse(T->rchild,Visit))return OK;return ERROR;}else return OK;}Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e)){ //后序遍历if(T!=NULL){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit))if((*Visit)(T->data))return OK;return ERROR;}else return OK;}3．编写各种遍历后的输出函数，如：Status Disp(TElemType e){ //输出各结点的数据值printf("%3c",e);return OK;}4．编写主函数调用以上各子函数，并调试程序以实现实验要求的各种遍历。

实验三图的遍历实验实验内容：从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问，试用程序完成图的遍历实验。

步骤：1．任务分析图有遍历是从图中某个顶点出发，沿某条搜索路径对图中的所有结点进行访问，而且仅访问一次。

遍历的流程图如图3.1所示，根据搜索的不同规则，遍历图的方法分为两种：深度优先遍历（DFS）和广度优先遍历（BFS）。

2．程序构思深度优先遍历其算法基本思想是：（1）选择一个起始点v0出发，并访问之；（2）依次从v0的未访问过的邻接点出发，深度优先遍历图，直到图中与v0有路径相通的顶点都被访问过为止；（3）如此时图中尚有顶点未被访问过，则另选图中一个未访问过的顶点作起始点，重复上述步骤过程，直到所有顶点都被访问过为止。

用流程图表示，如图3.2所示。

广度优先遍历其基本思想是：（1）选择一个起始点v0，并访问之；（2）从v0出发，依次访问v0的未被访问过的邻接顶点v1，v2，….v k,然后依次从v1，v2，….v k出发，访问各自来被访问过的邻接顶点；（3）重复步骤（2）直到所有顶点都被访问过为止。