数据结构课程实验指导书_管理学_高等教育_教育专区.doc

数据结构实验指导书第一部分前言一、实验的目的数据结构是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。本课程的另一重要教学目的是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，要做到这一点，上机实习是必须的。数据结构实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验课题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，训练学生实际动手进行程序设计和调试程序的能力，加深对数据结构相关概念和算法的理解。通过完成本实验课程的实验，学生应学会并掌握本课程的基本和重点知识，深刻理解逻辑结构、物理结构和算法设计之间的关系，初步学会算法分析的方法，并能在一定范围内运用所掌握的分析方法进行算法分析，培养软件工作所需要的动手能力和作为一个软件工作者所应具备的科学工作方法和作风。二、实验前的准备工作1每个学生需配备一台计算机，操作系统需Windows2000/XP以上版本，软件需Visual C+6.0以上版本。2实验前要求学生按实验要求编写好相关实验程序，准备上机调试运行。三、实验的步骤（一）建立一个文件夹，如“数据结构”，用来存放自己的所有实验程序，在该文件夹中建立子目录用来存放每个项目（一个子目录一个项目），如“顺序表”，项目中需要的所有文件都存在该文件夹中。（二）新建一个项目文件1双击Visual C+ 6.0快捷图标，进入Visual C+ 6.0集成开发环境；或者点击 “开始”“程序” “Microsoft Visual Studio 6.0” “Microsoft Visual C+ 6.0” 进入Visual C+ 6.0集成开发环境。2单击“File”菜单，选择“New”命令3创建一个项目文件并保存在项目所在文件夹中；3. 创建源程序文件并保存在项目所在文件夹中； 4输入源程序； 5单击“保存”按钮保存源程序。（三）编译、构建和运行1编译：“编译Compile” ”编译”或者按ctrl-F7。在改正语法错误（包括“错误（error）”和“警告(warning)”）后，程序经过连接（link）就得到可执行的目标程序。2构建：“编译Compile” “构建Build” 或者按F73运行：“编译Compile” ”运行Run” 或者按 Ctrl+F5。（四）运行错误处理通常所说的运行错误有两种：一种是逻辑错误，即程序的实际运行结果和对程序结果的期望不符；另一种是程序设计上的错误，但他躲过了编译程序和连接程序的检查，通常表现为突然死机、自行热启动或者输出信息混乱。运行结果不对，大多属于逻辑错误。一种逻辑错误是由于在设计程序的算法时考虑欠周到引起的，如对边界和特殊情况未作妥善处理，另一种常见的逻辑错误是由于程序输入时的打字错误造成的，例如将判断条件中的“=”误输入为“”，将相等判断“= =”误输入为赋值号“=”等。含有这类错误的程序在运行时出现的故障现象多种多样，而且通常很难与错误的原因联系起来。相对于编译和连接错误来说，运行错误的查找和判断更为困难。编译和连接错误分别由编译程序和连接程序检查，尽管有时它们报告的出错信息和错误的实际原因之间有一些差距，但总还可以作为查错时的一种参考。而运行错误就不同了，很少或根本没有提示信息，只能靠程序员的经验来判断错误的性质和位置。一种逻辑错误是由于在设计程序的算法时考虑欠周到引起的，如对边界和特殊情况未作妥善处理。输入的数据中包含错误或者输入数据的格式不符合要求当然也会影响到程序的运行结果。对这类错误往往需要仔细检查和分析才能发现。可以采用以下办法：1.将程序与流程图仔细对照，如果流程图是正确的，程序写错了，是很容易发现的。例如，复合语句忘记写花括弧，只要一对照流程图就能很快发现。2.如果实在找不到错误，可以采用“分段检查”的方法。在程序不同的位置设几个printf函数语句，输出有关变量的值，逐段往下检查。直到找到在某一段中数据不对为止。这时就已经把错误局限在这一段中了。不断减小“查错区”，就能发现错误所在。3.也可以用“条件编译”命令进行程序调试（在程序调试阶段，若干printf函数语句就要进行编译并执行。当调试完毕，这些语句不用再编译了，也不再被执行了）。这种方法可以不必一一去掉printf函数语句，以提高效率。4.如果在程序中没有发现问题，就要检查流程图有无错误，即算法有无问题。如有则改正之，接着修改程序。5.系统还提供debug（调试）工具，跟踪程序并给出相应信息，使用更为方便，请查阅有关手册。总之，程序调试是一项细致深入的工作，需要下功夫，动脑子，善于积累经验。在程序调试过程中往往反映出一个人的水平，经验和态度。上机调试程序的目的决不是为了“验证程序的正确”，而是“掌握调试的方法和技术”，要学会自己找问题，这样慢慢自己就会写出错误较少的实用程序。（四）保存，关闭，下次打开。1保存：“文件”“保存工作区Save Workspace”2关闭：“文件”“关闭工作区Close Workspace”3下次打开（1）“文件”“打开工作区Open Workspace” 顺序表.dsw（2） “文件”“最近工作区Recent Workspace”四、实验的要求（一）要求严格按照软件工程的开发步骤来完成实验1.问题分析和任务定义2.数据类型和系统设计3.编码实现和静态检查4.上机准备和上机调试5.总结和整理实验报告（二）写好实验报告实验报告的开头应给出题目、班级、姓名、学号和完成日期，实验报告的撰写应包括以下内容：1实验目的。2实验内容。3程序清单。4运行结果。5对运行结果的分析，以及本次实验取得的经验。五、实验任务与时间安排实验序号实验内容拟实验时间实验性质1实验一 线性表及应用2基础性2实验二 栈和队列2基础性3实验三 串的连接2基础性4实验四 数组和广义表2基础性5实验五 二叉树及其应用2设计性6实验六 哈夫曼编码2设计性7实验七 图的遍历及应用2设计性8实验八 查找及其应用2设计性9实验九 内部排序2设计性六、教材杨晓光编著数据结构实例教程清华大学出版社北京交通大学出版社：北京2008年第1版。第二部分实验内容实验一线性表及应用一、实验目的1. 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；2. 运用线性表解决线性结构问题。二、实验内容和步骤1建立一个类型为整型顺序表的头文件和基本操作，特别是初始化操作、插入操作、删除操作、查找操作、遍历操作等。 2创建有10个元素的线性顺序表，验证插入、删除、查找操作的结果，将源程序以实验2-1为文件名保存在自己的文件夹里面 3建立一个类型为整型链接表的头文件和基本操作，特别是初始化操作、插入操作、删除操作、查找操作、遍历操作等。 4创建有10个元素的线性链接表，验证插入、删除、查找操作的结果，将源程序以实验2-2为文件名保存在自己的文件夹里面。选作：5将事先建立好的顺序表La和Lb合并成一个顺序表。 要求：将Lb中不同于La中的元素插入到La的最后面。 将源程序以实验2-3为文件名保存在自己的文件夹里面。 6在上述实验的基础上分别实现类型为结构体的线性顺序表和链接表的基本操作及其有序表的合并操作。三、实验提示（一）顺序表的基本操作实现实验1、建立头文件SqList.h，完成顺序表的类型定义及基本操作。/*/*顺序表的头文件，文件名SqList.h */*/#include #define LISTSIZE 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /* DataType可以是任何相应的数据类型，如struct等 */ typedef struct DataType itemsLISTSIZE;/ 存放顺序表元素 int length; / 存放顺序表的长度 SqList; / 顺序表的类型定义/*算法2-1初始化顺序表*/int InitList(SqList *L)L-length=0;return 1;/*算法2-2求顺序表长*/int ListLength(SqList L)return L.length;/*算法2-3判断顺序表是否为空*/int ListEmpty(SqList L)if(L.lengthlength=LISTSIZE)printf(顺序表已满，无法进行插入操作！);return 0;if(posL-length+1)printf(插入位置不合法，其取值范围应该是1,length+1);return 0;for(i=L-length-1; i=pos-1; i-)L-itemsi+1=L-itemsi;L-itemspos-1=item;L-length+;return 1;/*算法2-5删除*/int ListDelete(SqList *L,int pos,DataType *item)int i;if(ListEmpty(*L)printf(顺序表为空表，无法进行删除操作！);return 0; if(posL-length)printf(删除位置不合法，其取值范围应该是1,length);return 0; *item=L-itemspos-1;for(i=pos;ilength;i+)L-itemsi-1=L-itemsi;L-length-;return 1; /*算法2-6查找指定元素在顺序表中的位置*/int Find(SqList L,DataType item)int pos=0;if(ListEmpty(L)printf(顺序表为空表，无法进行查找操作！);return 0;while(posL.length & L.itemspos!=item)pos+;if(posL.length)return pos+1;elsereturn 0;/*算法2-7获取顺序表中指定位置上的数据元素*/int GetElem(SqList L,int pos,DataType *item)if(ListEmpty(L)return 0;if(posL.length)printf(位置信息输入不合法，请重新输入);return 0;*item=L.itemspos-1;return 1;/*算法2-8遍历顺序表*/int TraverseList(SqList L)int i;for(i=0;iL.length;i+)printf(%dt,L.itemsi);printf(n);return 1;/*补充顺序表的建立算法*/void CreateList(SqList *L,int n)/*顺序表的建立：*/int i;for (i=0;iitemsi);L-length=n;2、编写源程序实现对顺序表的插入删除等基本操作。/* 顺序表的基本操作实现 */#include ./sqlist.hint main(int argc, char* argv)SqList L;int n=10;/*欲建立的顺序表长度*/L.length=0;CreateList(&L,n);/*建立顺序表*/TraverseList(L);/*遍历顺序表*/ printf(%d,ListLength(L);/*打印顺序表长度*/printf(n);（二）单链表的基本操作实现实验1、建立头文件LinkList.h，完成单链表的类型定义及基本操作。/*/*单链表的头文件，文件名LinkList.h */*/#include malloc.h#include stdio.h/*单链表的存储结构*/typedef int DataType;#define NULL 0typedef struct NodeDataType data;struct Node *next;LNode,*PNode,*LinkList;/*算法2-9初始化单链表*/int InitList(LinkList *h)*h=(LinkList)malloc(sizeof(LNode);if(!h)printf(初始化链表错误！n);return 0;(*h)-next=NULL;return 1;/*算法2-10求单链表表长*/int ListLength(LinkList h)int total=0;PNode p=h-next;while(p)total+;p=p-next;return total;/*算法2-11判断单链表是否为空*/int ListEmpty(LinkList h)if(h-next)return 0;elsereturn 1;/*算法2-12插入*/int ListInsert(LinkList h,int pos,DataType x)PNode p=h,q;int i=0;while(p & inext;i+;if(!p | ipos-1)printf(插入位置不合法！n);return 0;q=(PNode)malloc(sizeof(LNode);if(!q)printf(不能生成新结点n);return 0;q-data=x;q-next=p-next;p-next=q;return 1;/*算法2-13删除*/int ListDelete(LinkList h,int pos,DataType *item)PNode p=h,q;int i=0;while(p-next & inext;i+;if(!p-next | ipos-1)printf(删除位置不合法！n);return 0;q=p-next;p-next=q-next;*item=q-data;free(q);return 1;/*算法2-14查找指定元素在单链表中的位置*/PNode Find(LinkList h,DataType item)PNode p=h-next;while(p & p-data!=item)p=p-next;return p;/*算法2-15获取单链表中指定位置上的数据元素*/int GetElem(LinkList h,int pos,DataType *item)int i=0;PNode p=h-next;while(p & inext;if(!p | ipos-1)printf(位置参数不合法！n);return 0;*item=p-data;return 1;/*算法2-16销毁单链表*/void DestroyList(LinkList h)PNode p=h-next;while(h)p=h;h=h-next;free(p);/*算法2-17遍历单链表*/void TraverseList(LinkList h)PNode p=h-next;while(p)printf(%dt,p-data);p=p-next;printf(n);2、编写源程序实现对单链表的插入删除等基本操作。/* 单链表的基本操作实现 */#include ./LinkList.hint main(int argc, char* argv)int i,x;LinkList h;h=(LinkList)malloc(sizeof(lnode);/*由系统生成一个LNode型的结点，同时将该结点的起始位置赋给指针变量h */creat(h);TraverseList (h);printf(请输入欲插入的元素：n);scanf(%d,&x);printf(请输入欲插入元素的位置：n);scanf(%d,&i);insert(h,i,x);TraverseList (h);printf(请输入欲删除的结点：n);scanf(%d,&x);Delete(h,x);TraverseList (h);实验二栈和队列一、实验目的1. 掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用；2. 掌握栈和队列的特点，即后进先出与先进先出的原则；3. 掌握栈和队列的基本操作，如入栈与出栈、入队与出队等；4. 运用栈和队列解决问题。二、实验内容和步骤1利用顺序栈将一个非负的十进制整数N转换为对应的B进制数。将源程序以实验31为文件名保存在自己的文件夹里面。 2利用链栈进行后缀表达式求值。将源程序以实验32为文件名保存在自己的文件夹里面。选作：3实现汉诺塔问题算法，模拟圆盘移动过程。4实现迷宫问题算法，要求输出迷宫及其问题可解时的路径。三、实验提示（一）利用顺序栈将一个非负的十进制整数N转换为对应的B进制数。1、建立头文件SqStack.h，完成顺序栈类型定义及基本操作/*顺序栈的头文件SqStack.h */#include/*顺序栈存储结构*/#define STACKSIZE 100typedef int DataType;typedef structDataType itemsSTACKSIZE;int top;SqStack;/*算法3-1初始化顺序栈*/int InitStack(SqStack *S)S-top=-1;return 1;/*算法3-2判空栈*/int StackEmpty(SqStack S)if(S.top=-1)return 1;elsereturn 0;/*算法3-3入栈*/int Push(SqStack *S,DataType e)if(S-top=STACKSIZE-1)printf(堆栈已满，不能完成入栈操作！n);return 0;S-top+;S-itemsS-top=e;return 1;/*算法3-4出栈*/int Pop(SqStack *S,DataType *e)if(S-topitemsS-top;S-top-;return 1;/*算法3-5 取栈顶元素*/int GetTop(SqStack S,DataType *e)if(S.topnext=NULL;return 1;/*算法3-7判空栈*/int StackEmpty(LinkStack top)if(top-next=NULL)return 1;elsereturn 0;/*算法3-8入栈*/int Push(LinkStack top,DataType e)SNode *p;p=(SNode*)malloc(sizeof(SNode);if(!p)printf(入栈操作出错！n);return 0;p-data=e;p-next=top-next;top-next=p;return 1;/*算法3-9出栈*/int Pop(LinkStack top,DataType* e)SNode *p;if(!top-next)printf(栈已空，无法完成出栈操作！n);return 0;p=top-next;top-next=p-next;*e=p-data;free(p);return 1;/*算法3-10 取栈顶元素*/int GetTop(LinkStack top,DataType* e)SNode *p;if(!top-next)printf(栈已空，无法完成取栈顶元素操作！n);return 0;p=top-next;*e=p-data;return 1;/*算法3-11销毁链栈*/int Destroy(LinkStack top)SNode *p;while(top)p=top;top=top-next;free(p);return 1;2、编写源程序实现插入删除等基本操作，完成后缀表达式求值算法。实验三 串的连接一、实验目的1掌握串的顺序定长存储结构的类型定义方法2掌握串的堆分配存储结构的类型定义方法3理解串的基本模式匹配算法二、实验内容和步骤1利用串的顺序定长存储结构实现两个子串的连接。要求：两个子串从键盘输入获得；从屏幕显示连接后的新串元素列表。 将源程序以实验4-1为文件名保存在自己的文件夹里面。选作：2利用串的堆配存储结构实现两个子串的连接。3上机实现朴素的串匹配算法。要求： 从键盘输入主串和子串元素，调用朴素的串匹配算法，判断子串是否在主串中，若在，返回起始位置，否则显示否定信息。三、实验提示（一）利用串的顺序定长存储结构实现两个子串的连接。1、建立头文件SqString.h，完成顺序串类型定义及基本操作/*串的定长顺序存储头文件SqString.h */#include/*存储结构*/#define STRSIZE 100typedef structchar chSTRSIZE;int length;SqString;/*算法4-1初始化串*/int InitString(SqString *S,char *str)int i, len=0;char *c=str;while(*c!=0)len+;c+; /*求str的长度*/S-length = len; /*置串的当前长度值*/for(i = 0; i length; i+)/*赋值串值*/S-chi = stri;return 1;/*算法4-2串插入*/int StrInsert(SqString *S,int pos,SqString T)int i;if(posS-length)printf(插入位置不合法，其取值范围应该是0,length);return 0;/*插入后串长STRSIZE，则正常插入*/if (S-length + T.lengthlength-1; i=pos-1; i-)S-chi+T.length=S-chi;for(i=0; ichi+pos=T.chi;S-length+=T.length;/*插入后串长STRSIZE，则串T可以全部插入，串S部分被截断*/else if(T.length+posT.length+pos-1;i-) S-chi=S-chi-T.length;for (i=0;ichi+pos=T.chi;S-length=STRSIZE;/*插入后串长STRSIZE,并且串T部分也要被截断*/else for (i=0;ichi+pos=T.chi;S-length=STRSIZE;return 1;/*算法4-3串删除*/int StrDelete(SqString *S,int pos,int len)int i;if(S-length=0)printf(空串，无法进行删除操作！);return 0; if(pos0 | lenS-length)printf(删除位置pos以及删除长度len不合法，无法完成删除操作！);return 0; if(pos+lenS-length) len=S-length-pos+1;/*当删除长度超过串长度，则只删到串尾即可*/for(i=pos+len;ilength;i+)S-chi-len=S-chi;S-length-=len;return 1; /*算法4-4求子串*/int SubStr(SqString S,int pos,int len,SqString *T)int i;if(S.length=0)printf(空串，无法完成求子串操作！);return 0; if(pos0 | lenS.length)printf(子串的位置pos以及子串长度len不合法，无法完成求子串操作！);return 0; if(pos+lenS.length) len=S.length-pos+1;/*当子串长度超过主串长度，则只取到串尾即可*/for(i=0;ichi=S.chi+pos;T-length=len;return 1; /*算法4-5串连接*/int Concat(SqString *S,SqString T)int i;if(S-length+T.length=STRSIZE)/*连接后串长STRSIZE*/for(i=0;ichi+S-length=T.chi;S-length+=T.length;else if(S-lengthlength;ichi=T.chi-S-length;S-length=STRSIZE;return 1; /*算法4-6串比较*/int StrCmp(SqString S, SqString T) int i;for (i=0;iS.length & iT.length;i+)if (S.chi!=T.chi) return(S.chi - T.chi);return(S.length - T.length);/*算法2-7串定位int GetElem(SqList L,int pos,DataType *item)if(ListEmpty(L)return 0;if(posL.length)printf(位置信息输入不合法，请重新输入);return 0;*item=L.chpos-1;return 0;*/*算法2-8遍历顺序表int TraverseList(SqList L)int i;for(i=0;iL.length;i+)printf(%dt,L.chi);printf(n);return 1;*/2、编写源程序实现插入删除等基本操作，完成两个子串的连接算法。#include ./SqString.hint main(int argc, char* argv)int i;/SqString S=Strings,7;/SqString T= Demo,5;SqString S,T,R;InitString(&S,Strings);InitString(&T, Demo);InitString(&R,);StrInsert(&S,7,T);for(i=0;iS.length;i+)printf(%c,S.chi);printf(n);StrDelete(&S,6,5);for(i=0;iS.length;i+)printf(%c,S.chi);printf(n);return 0;实验四 数组和广义表一、实验目的1了解数组的两种存储表示方法，掌握数组在作为运行的存储结构中的地址计算方法；2了解稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运算采用的处理方法。 3理解广义表实现方法。二、实验内容及步骤1用C语言编程实现稀疏矩阵的转置，将源程序以实验5-1为文件名保存在自己的文件夹里面。采用三元组顺序表创建一个稀疏矩阵；将矩阵的行列值相互交换；将每个三元组中的i和j相互调换；重排三元组之间的次序实现矩阵转置。选作：2、用C语言编程实现两稀疏矩阵的乘积采用行逻辑链接的顺序表建立两个稀疏矩阵；求两稀疏矩阵的乘积3实现广义表的递归算法，如求广义表的深度算法。将源程序以实验5-2为文件名保存在自己的文件夹里面。三、思考问题结合实验过程，回答下列问题：1、两稀疏矩阵相乘，其乘积是否一定为稀疏矩阵？实验五 二叉树及其应用一、实验目的1掌握构造二叉链表树的算法。 2掌握遍历二叉树的三种递归算法。 3掌握计算二叉树深度、二叉树结点所在层次、二叉树叶子结点和二叉树所有路径的算法。 4理解树的遍历算法和哈夫曼树的构造算法 二、实验内容及步骤1用C语言编程实现二叉树的中序遍历算法采用二叉链存储结构创建一个二叉树；用非递归方法实现二叉树的中序遍历算法，将源程序以实验61为文件名保存在自己的文件夹里面。输出二叉树中每个结点的值；给定具体数据调试程序。2、用C语言编程实现在线索二叉树上进行遍历先进行二叉树的线索化，即建立线索二叉树；在线索二叉树中遍历每个结点并输出每个结点的信息；给定具体数据调试程序。 3增加二叉树的基本操作，如计算二叉树深度、二叉树结点所在层次、二叉树叶子结点和二叉树所有路径等算法。然后分别调用相应算法并显示对应结果。将源程序以实验62为文件名保存在自己的文件夹里面。三、思考问题结合实验过程，回答下列问题：1、采用非递归方法实现二叉树遍历与采用递归方法实现二叉树的遍历，哪个方法执行效率高；2、为什么在线索二叉树上进行遍历，要比在二叉树上进行遍历快捷方便？实验六 哈夫曼编码一、实验目的1掌握最优二叉树的含义。 2掌握最优二叉树的结构特征，以及各种存储结构的特点及使用范围。 3掌握哈夫曼编码的构成。 二、实验内容及步骤1、假定用于通信的电文由8个字母A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5%，25%，4%，7%，9%，12%，30%，8%，试编程为这8个字母设计赫夫曼编码。分析问题编程创建此问题的赫夫曼树；编程求出此8个字母赫夫曼编码并输出；将源程序以实验61为文件名保存在自己的文件夹里面。调试程序。三、思考问题结合实验过程，回答下列问题：针对同一问题，构成的赫夫曼树是否是唯一的，构成的赫夫曼编码是否唯一？实验七 图的遍历及应用一、实验目的1、 掌握图的基本存储方法；2、 掌握图的两种搜索路径的遍历算法；3、 掌握拓扑排序算法；(选做)二、实验内容及步骤1建立ADT图的头文件及其相应操作。调用图的遍历算法，显示遍历结果。将源程序以实验71为文件名保存在自己的文件夹里面。 采用邻接表存储结构创建一个图；编程实现图的深度优先搜索（或广度优先搜索）遍历算法输出遍历结果；给定具体数据调试程序。2、教学计划编制问题软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表：课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计与分析C3,C4C6计算机原理C11C7编