《数据结构》课程实验教学大纲

数据结构课程实验教学大纲【课程名称】： 数据结构/Data Structure【课程学时/学分】： 59/3.5 实验总学时： 8【先修课程】：C/C+语言程序设计离散数学【适用专业】：计算机科学与技术、信息管理【开课院系】：信息技术学院、数统学院【教材、教学参考书】：1. 严蔚民，吴伟民编著。数据结构。清华大学出版社，2002.7。2. 严蔚民，吴伟民编著。数据结构习题。清华大学出版社，2002.7。3. 徐孝凯 编著。 数据结构实用教程。清华大学出版社，2002.7一、本课程实验的性质和任务通过上机实验，要求在数据结构的逻辑特性和物理表示，数据结构的选择和应用，算法设计及其实现等方面加深对课程基本内容的理解，同时在程序设计方法以及上机操作等基本技能方面受到比较系统的和严格的训练，能够灵活利用基本算法解决一些实际问题。二、实验内容和基本要求实验项目的设置及学时分配表序号实验项目学时实验性质实验者类别每组人数备注1抽象数据类型2设计本科生1选作*2线性表的操作及应用2设计本科生1必作3栈和队列的基本操作2设计本科生1必作4迷宫问题求解2设计本科生1选作*5广义表的基本操作2设计本科生1选作*6树的各种操作2设计本科生1必作7哈夫曼树的建立2设计本科生1选作*8图的各种操作2设计本科生1必作9最小生成树的建立2设计本科生1选作*10排序和查找的算法2设计本科生1选作三、对培养学生的能力要求要求学生理解数据结构的基本算法，并能够用程序设计语言实现这些算法。灵活运用数据结构的基本算法解决的实际问题，培养学生的数据抽象能力和复杂编程能力。1. 完成线性表的顺序存储结构和链式存储结构的基本操作的实现，并能设计实现线性的应用程序，提高编程能力。2. 完成栈和队列的顺序存储结构和链式存储结构的基本操作的实现。3. 完成二叉树和树的存储、遍历等基本操作的实现。4. 完成图的存储、遍历等基本操作的实现。5. 掌握各种查找和排序的算法，设计一个综合应用程序，为后续课程的应用打下基础。四、本实验课程对学生的考核评分方法本实验课程成绩应占整个课程成绩的10；考勤情况占整个实验成绩的的20；实验报告占整个实验成绩的70；五、说明本实验教学大纲适用于计算机技术及应用专业、信息管理专业以及数统专业的本科生。实验的学时总数为8学时。可根据讲课进度安排上机时间，也可根据不同情况适当增加实验上机时数，以适应不同专业的需要。数据结构课程实验指导书河北经贸大学信息技术学院目 录实验1 抽象数据类型6实验2 线性表的基本操作8实验3 栈和队列的基本操作16实验4 迷宫问题递归21实验5 广义表的基本操作23实验6 二叉树的基本操作26实验7 哈夫曼树及哈夫曼编码31实验8 图的基本操作34实验9 最小生成树的建立43实验10 查找和排序46实验1 抽象数据类型1实验目的（1） 熟悉抽象数据类型的表示与实现方法。（2） 复习高级编程语言C+的使用方法。2 实验内容设计一个可进行复数运算的演示程序。【基本要求】实现下列六种基本运算：（1）由输入的实部和虚部生成一个复数；（2）两个复数求和；（3）两个复数求差；（4）两个复数求积；（5）从已知复数中分离出实部；（6）从已知复数中分离出虚部。运算结果以相应的复数或实数的表示形式显示。【测试数据】自定参考程序如下：/ 抽象数据类型复数的表示与实现#include typedef struct RECORD double real; double image; cmptp; int create(double x,double y,cmptp &z) z.real=x; z.image=y; return 1; int add(cmptp z1,cmptp z2,cmptp &sum) sum.real=z1.real+z2.real; sum.image=z1.image+z2.image; return 1; int SUBSTRACT(cmptp z1,cmptp z2,cmptp &difference) difference.real=z1.real-z2.real; difference.image=z1.image-z2.image; return 1; int multiply(cmptp z1,cmptp z2,cmptp &product) product.real=(z1.real*z2.real)-z1.image*z2.image; product.image=z1.image*z2.real+z1.real*z2.image; return 1; double getreal(cmptp z) return z.real; double getimage(cmptp z) return z.image; / 上机调试验证 void main() cmptp z; create(1,2,z); coutz.realz.imageendl; cmptp z1=3,4; coutgetreal(z1)endl; cmptp z2=5,6; cmptp sum;add(z1,z2,sum); coutsum.real sum.imageendl; SUBSTRACT(z1,z2,sum); coutsum.real sum.imageendl; multiply(z1,z2,sum); coutsum.real sum.imageendl; 3 实验要求按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。实验2 线性表的基本操作1实验目的(1) 熟练掌握线性表的逻辑特征。（2）熟练掌握线性表的基本操作在两种存储结构上的实现。2实验内容（1） 设计一个顺序表的基本操作的演示程序（2） 设计一个单链表的基本操作的演示程序（3） 设计一个双链表的基本操作的演示程序【基本要求】实现下列4种基本运算：（1）初始化线性表；（2）在第I个元素前插入一个元素e；（3）删除第I个元素；（4）遍历线性表；（5）将单链表逆置【测试数据】自定参考程序如下：/顺序表的基本操作#include /顺序表的定义#define MAX 15typedef struct int elemMAX; int length;Sqlist;void Initlist_sq(Sqlist &L);void ListInsert_sq(Sqlist &L,int i, int e);void ListDel_sq(Sqlist &L,int i, int &e);void print_sq(Sqlist L);/ 函数的定义void Initlist_sq(Sqlist &L) L.length =0;void ListInsert_sq(Sqlist &L,int i, int e) int *p,*q;if(iL.length +1) return;q=&L.elemi-1; /插入位置for(p=&L.elemL.length -1;p=q;-p )*(p+1)=*p;*q=e;+L.length ;return;void ListDel_sq(Sqlist &L,int i, int &e) if(iL.length ) return;e=L.elemi-1; for(int j=i;jL.length ;j+)L.elemj-1=L.elemj;-L.length ;void print_sq(Sqlist L)int *p,*q=L.elem+L.length-1 ;for(p=L.elem;p=q;p+ )cout*p ;coutn;void main()int a11=10,20,30,40,50,60,70,80,90,100;Sqlist L; /初始化顺序表Initlist_sq(L);cout现在的表长： L.length endl; / 插入10个数据元素 for( int i=1;i=10;+i) ListInsert_sq(L, i, ai-1); cout插入10个元素后的线性表：endl; /遍历 print_sq( L); cout现在的表长： L.length endl; /删除第5个元素 int x; ListDel_sq(L,5, x); cout删除的元素值是：xendl; cout删除第5个元素后的表：endl; print_sq( L); cout现在的表长： L.length endl;/ 单链表的操作#include struct NODE int data;NODE *next; ;void print(NODE *&head); /遍历int data6=25,41,17,98,5,6;void Setup_L(NODE *&head,int n); /生成单链表void Insert_L(NODE *&head, int I, int e); /插入void Delete_L(NODE * &head, int I,int &e); /删除void Convert_L(NODE *&head)； /逆序void main() NODE *L; Setup_L(L,6);print(L);/Insert_L(L,7,50);print(L);int x;Delete_L(L,0,x);coutX=xnext ; while(p) coutdatanext; /后移指针 coutnext=NULL; /先建立一个带头结点的单链表 q=head; for(int i=0;idata=datai; q-next=p; q=p; /插入到表头q-next =NULL;void Insert_L(NODE *&L,int i, int e)NODE *p=L,*q;int j=0;while(p&jnext ; j+; if(!p|ji-1)cout插入值超出范围！data=e;q-next =p-next ;p-next =q;void Delete_L(NODE *&L,int i,int &e)NODE *p=L,*q;int j=0;while(p&jnext ; j+; if(!p|ji-1)cout删除值超出范围！next ;e=q-data ;p-next =q-next;delete q;void Convert_L(NODE *&L)NODE *p,*q,*r;p=L-next;q=p-next ;p-next =NULL;while(q) r=q-next;q-next =p;L-next=q;p=q;q=r;/双链表的基本操作struct NODEint data;NODE *next;NODE *prior;int data6=3,5,7,19,20,21; /测试用数据/ 函数声明void print(NODE *&head);void Setup_L(NODE*&head,int n);void Insert_L(NODE *&L,int i,int e);void Delete_L(NODE *&L,int i,int &e);void Convert_L(NODE*&L);/ 主函数和各函数的定义void main()NODE *L;Setup_L(L,6);print(L);Insert_L(L,7,50);print (L);int x;Delete_L(L,1,x);coutX=xnext;while(p)coutdatanext;coutnext=NULL;q=head;for(int i=0;idata=datai;/cinp-data;p-prior=q;q-next=p;q=p;q-next=NULL;/return(head);void Insert_L(NODE *&L,int i,int e)/在带头结点的双链表中第i个位置插入元素eNODE*p=L,*q;int j=0; /j为计数器while(p&jnext;j+; /寻找第i-1个结点if(!p|ji-1) /i小于1或大于表长cout插入值超出范围!data=e;if(p-next=NULL)q-next=p-next;p-prior=q;p-next=q;else q-next=p-next;p-next-prior=q;p-next=q;q-prior=p; /插入L中void Delete_L(NODE*&L,int i,int &e)/在带头结点的双链表L中，删除第i个元素，并由e返回其值NODE *p=L,*q;int j=0;while(p&jnext;j+;if(!p|ji-1)cout删除值超出范围!next;e=q-data;q-next-prior=p;p-next=q-next;delete q;/删除并释放结点3 实验要求按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。实验3 栈和队列的基本操作1实验目的(1) 深入了解栈和队列的基本特性(2) 熟练掌握栈的基本操作在两种存储结构上的实现。(3) 熟练掌握循环队列的基本操作(4) 熟练掌握链队列的基本操作2实验内容（1） 设计一个顺序栈的基本操作的演示程序（2） 设计一个链栈的基本操作的演示程序（3） 设计一个循环队列的基本操作的演示程序（4） 设计一个链队列的基本操作的演示程序【基本要求】实现下列6种基本运算：（1）初始化；（2）入栈（队列）；（3）出栈（队列）；（4）遍历；（5）求栈（队列）的长度【测试数据】自定参考程序如下：/顺序栈的基本操作#include #define MAX 10typedef struct int base; int top; int stMAX; SqStack; /基本操作说明 void InitStack(SqStack &S); void push(SqStack &S, int e); void pop(SqStack &S,int &e); /基操作的算法描述void InitStack(SqStack &S)S.base=S.top=0;void push(SqStack &S, int e)if(S.top=MAX) cout”栈满n”; return;S.stS.top =e;S.top+=1; void pop(SqStack &S,int &e) if(S.top =0) cout”栈空n”; return; S.top -=1; e=S.stS.top ; void print(SqStack S) cout”栈的各个元素如下：n”; for(int I=0;IS.top ;I+) coutS.stI” “; coutendl; void main() SqStack S; /初始化cout”初始化栈n”;InitStack(S);cout”栈底和栈顶：”S.base”,”S.topendl;/入栈cout”5个元素入栈n”;for(int I=0;I5;I+)push(S, 2*I+1);cout”栈顶为：”S.top endl;print(S);/出栈int x;pop(S,x);cout”出栈元素为：”x”栈顶”S.topendl;print(S); /循环队列的基本操作#include #define MAX 8 typedef struct int baseMAX; int front; int rear; SqQueue;/* 初始化 */void InitQueue(SqQueue &Q) Q.front=Q.rear=0;/*求队列长度*/int QueueLength(SqQueue Q) return (Q.rear-Q.front+MAX)%MAX; /*入队列*/void EnQueue(SqQueue &Q,int e)if(Q.rear+1)%MAX=Q.front) cout”队列满！”endl; else Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAX;/*遍历队列*/void traverse(SqQueue &Q) int I, k; if (Q.front=Q.rear)k=0; elsek=1; switch(k) case 0: for(I=Q.front;IQ.rear;I+) coutQ.baseI” “; break; case 1: for(I=Q.front;IMAX;I+) coutQ.baseI” “; for(I=0;IQ.rear ;I+) coutQ.baseI” “;break; /*出队*/int DeQueue(SqQueue &Q,int &e) if (Q.rear=Q.front) return 1; e=Q.baseQ.front; Q.front=(Q.front+1)%MAX; return 1;void main() SqQueue Q; InitQueue(Q); int j,m,x; for(j=0;j7;j+) EnQueue(Q,2*j); traverse(Q);m=QueueLength(Q);cout”n长度”mendl;EnQueue(Q,500); traverse(Q);DeQueue(Q,x);m=QueueLength(Q);cout”n长度”mendl; traverse(Q);EnQueue(Q,500);m=QueueLength(Q);cout”n长度”mendl; traverse(Q);DeQueue(Q,x);m=QueueLength(Q);cout”n长度”mendl; traverse(Q);EnQueue(Q,600);m=QueueLength(Q);cout”n长度”mendl; traverse(Q);3 实验要求按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。实验4 迷宫问题递归1实验目的（1） 熟练递归特点。（2） 掌握递归与栈的关系。（3） 掌握将递归程序转换为非递归的实现方法。2 实验内容设计一个程序，实现对迷宫问题的求解。【基本要求】分别用递归方法和非递归方法实现参考代码如下：/采用递归的方法实现#include const m=6,n=8;int mazem+2n+2; /迷宫数组int markm+2n+2; /标记数组int move42=0,1,1,0,0,-1,-1,0; /前进数组int seekpath(int x,int y);void main() int i,j; coutPlease input maze Matrixn; for(i=0;im+2;i+) for(j=0;jmazeij;/初始化mark数组 for(i=0;im+2;i+) for(j=0;jn+2;j+) markij=0;/置入口处点对应的访问标记为 9 mark11=9; /从入口点（1，1）开始调用求解迷宫的递归算法 if(seekpath(1,1) cout(1,1)endl; for(i=0;im+2;i+)for(j=0;jn+2;j+) coutmazeij;coutn;int seekpath(int x,int y) int i,g,h;if(x=m)&(y=n)return 1;for(i=0;i4;i+)g=x+movei0;h=y+movei1;if(mazegh=0)&(markgh=0)markgh=1;if(seekpath(g,h)cout(g,h),;mazegh=9;return 1;if(x=1)&(y=1)coutNo path!endl;return 0;3 实验要求按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。实验5 广义表的基本操作1实验目的（1） 掌握广义表的线性结构特点及其特殊性。（2） 掌握广义表的扩展线性链表的存储结构。（3） 掌握广义表的基本操作的实现方法。2 实验内容设计一个可进行广义表的基本操作的演示程序。【基本要求】实现下列4种基本运算：（1）创建广义表；（2）遍历广义表；（3）求广义表的深度；（4）求广义表的长度；参考代码如下： /采用扩展的线性链表存储表示/实现广义表的创建、遍历、求深度、长度的基本操作/输入形式为：（a,(b,c)）的字符串#include #include enum BooleanFalse,True; /False=0；原子；True=1；子表typedef char ElemType;struct GLNode /采用扩展的线性链表存储表示 Boolean tag; /公用部分，用于区分原子结点和表结点 union ElemType data; /原子结点的值 GLNode *sublist; /表结点的表头指针;GLNode *next; /指向下一个元素结点;void Create(GLNode *&GL)char ch;cinch;if(ch=#)GL=NULL;else if(ch=()GL=new GLNode;GL-tag=True;Create(GL-sublist );elseGL=new GLNode;GL-tag =False;GL-data=ch;cinch;if(GL=NULL);else if(ch=,)Create(GL-next);else if(ch=)|(ch=;)GL-next=NULL;void Print(GLNode *GL)if(GL-tag=True)coutsublist=NULL)coutsublist);elsecoutdata;if(GL-tag=True)coutnext!=NULL)coutnext); int Depth(GLNode *GL)/递归算法 int max=0;while(GL!=NULL) /遍历表中的每一个结点if(GL-tag=True)int dep=Depth(GL-sublist); /递归调用求出子表的深度if(depmax) max=dep; /让max始终为同一层所求过的子表中深度的最大值GL=GL-next;return max+1; /空表深度为1int Length(GLNode *GL)/递归算法 if(GL!=NULL) return (1+Length(GL-next); else return 0;void main() GLNode *L=NULL;Create(L);Print(L);coutendl;cout广义表的长度：sublist) endl;cout广义表的深度：sublist) endl;实验6 二叉树的基本操作1实验目的（1） 掌握二叉树的非线性和递归特点。（2） 熟练掌握二叉树的存储结构。（3） 熟练掌握二叉树的各种遍历操作和其它操作的实现方法。2 实验内容设计一个可进行二叉树基本操作的演示程序。【基本要求】实现下列六种基本运算：（1）创建二叉树；（2）先序遍历二叉树；（3）中序遍历二叉树；（4）后序遍历二叉树；（5）层序遍历二叉树；（6）求度为1的结点的个数；（7）求叶子结点的个数；（8）求度为2的结点的个数。二叉树以链式结构表示，主程序以菜单方式的用户界面。【测试数据】自定/二叉树的基本操作#include typedef struct node /定义结点 char data; struct node *lchild, *rchild; BinTNode;typedef BinTNode *BinTree; /定义二叉树void CreateBinTree(BinTree &T); /先序创建二叉树void PreOrder(BinTree T); /先序遍历二叉树void InOrder(BinTree T); /中序遍历二叉树void PostOrder(BinTree T); /后序遍历二叉树int onechild(BinTree T); /求度为1的结点的个数int leafs(BinTree T); /求叶子结点的个数int twochild(BinTree T); /度为2的结点的个数void translevel(BinTree b) /层序遍历二叉树void main() int n; BinTree T; char ch1,ch2; coutWelcome to enter the testing program for bintree basic operatorendl; coutPlease Choseendl; ch1=y; while(ch1=y|ch1=Y) coutA -building n; coutB-PreOrdern; coutC-InOrdern; coutD-PostOrdern; cout”E- transleveln”; cout F-onechildn; coutG-twochildn; cout H-leafsn; coutch2; switch(ch2) case a:case A: cout请输入按先序建立二叉树的结点序列：n;CreateBinTree(T);break; case b:case B: cout二叉树的先序遍历序列：n; PreOrder(T); break; case c:case C: cout二叉树的中序遍历序列：n; InOrder(T); break; case d:case D: cout二叉树的后序遍历序列：n; PostOrder(T); break;case f:case F: cout二叉树的单孩子结点数：n; n=onechild(T); coutnendl; break;case g:case G: cout二叉树的双孩子结点数：n; n=twochild(T); coutnendl; break;case h:case H: cout二叉树的叶子结点数：n; n=leafs(T); coutnendl; break;case e:case E: coutch; if(ch=0) T=NULL; else T=(BinTNode *)new BinTNode; T-data=ch; CreateBinTree(T-lchild ); CreateBinTree(T-rchild ); void InOrder(BinTree T)if(T)InOrder(T-lchild );coutdatarchild );void PostOrder(BinTree T)if(T)PostOrder(T-lchild );PostOrder(T-rchild );coutdataendl ;void PreOrder(BinTree T)if(T)coutdatalchild );PreOrder(T-rchild );/层序遍历二叉树/采用一个队列q，先将二叉树的根 结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。因为队列的特点是先进先出，从而达到按层序遍历的目的。#define MAXLEN 100void translevel(BinTree b) struct node BinTree vecMAXLEN; int f, r;q; /定义队列q， f 表示队头指针，r队尾指针q.f=0; /置队列为空队列q.r=0;if(b!=NULL) coutdata” “;q.vecq.r=b; /结点指针进入队列q.r=q.r+1; /队尾指针后移while(q.flchild!=NULL) /输出左孩子，并入队列 coutlchild-datalchild; q.r=q.r+1;if(b-rchild!=NULL) /输出右孩子，并入队列 coutrchild-datarchild; q.r=q.r+1;int onechild(BinTree T)int num1,num2;if(T=NULL) return 0;else if(T-lchild =NULL & T-rchild!=NULL|T-lchild!=NULL & T-rchild=NULL) return 1;elsenum1=onechild(T-lchild);num2=onechild(T-rchild );return num1+num2; int twochild(BinTree T)int num1,num2;if(T=NULL) return 0;else num1=twochild(T-lchild);num2=twochild(T-rchild );if(T-lchild !=NULL & T-rchild !=NULL) return (1+num1+num2); else return (num1+num2); int leafs(BinTree T)int num1,num2;if(T=NULL) return 0;else if(T-lchild=NULL &T-rchild =NULL) return 1;else num1=leafs(T-lchild );num2=leafs(T-rchild );return num1+num2;3 实验要求按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。实验7 哈夫曼树及哈夫曼编码1实验目的（1） 熟练掌握哈夫曼树的特点。（2） 熟悉哈夫曼树的构造方法2 实验内容 哈夫曼算法3 实验要求按要求编写实验程序，将实验程序上机调试运行，并提交实验报告。参考代码：#include#include#define MAX 21typedef structchar data; int weight; int parent,lchild,rchild;huffnode;typedef structchar cdMAX;int start;huffcode;void main()huffnode ht2*MAX;huffcode hcdMAX,d;int i, k,f ,l,r, n,c,m1,m2;printf(元素个数:);coutn; for(i=1;i=n;i+)cout第”int结点值:; cinhti.data);coutt权重:;couthti.weight;for(i=1;i=2*n-1;i+) hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=2*n-1;i+)m1=m2=32767;l=r=0;for(k=1;k=i-1;k+)if(htk.parent=0)if(htk.weightm1)m2=m1;r=1;m1=htk.weight;l=k;else if(htk.weightm2)m2=htk.weight;r=k;htl.parent=i;htr.parent=i;hti.weight=htl.weight+htr.weight;hti.lchild=l;hti.rchild=r;for(i=1;i=n;i+)d.start=n+1;c=i;f=hti.parent;while(f!=0)if(htf.lchild=c)d.cd-d.start=0;else d.cd-d.start=1;c=f;f=htf.parent;hcdi=d;cout输出哈夫曼编码:n;for(i=1;i=n;i+)couthti.data;for(k=hcdi.start;k=n;k+)couthcdi.cdk;coutendl;实验8 图的基本操作1实验目的（3） 熟练掌握图的非线性结构的特点。（4） 掌握图的邻接矩阵和邻接表的存储结构。（5） 掌握图的两种常用存储结构下的深度优先搜索和广度优先搜索操作和其它操作的实现2 实验内容(1) 设计一个基于图的邻接矩阵的图的基本操作的演示程序。(2) 设计一个基于图的邻接表的图的基本操作的演示程序。【基本要求】实现下列六种基本运算：（1）创建图；（2）深度优先遍历图；（3）广度优先遍历图；（4）转换图的存储结构分别在图的邻接矩阵和邻接表的存储结构实现【测试数据】自定参考程序如下：/图的邻接矩阵的基本操作#define MAX_VERTEX_NUM 20typedef struct ArcCellint adj;AdjMatrixMAX_VERTE