《数据结构实验指导书》(New).doc

目 录数据结构实验教学大纲1数据结构上机实验编程指南4实验一 线性表5实验二 栈与队列12实验三 二叉树17实验四 图21实验五 查找27实验六 排序31数据结构实验指导书数据结构实验教学大纲Data Structure ExperimentTeaching Program课程编号：8013030 课程类别：必修课 适用专业：计算机科学技术 学时：12 教研室主任：顾泽元 大纲执笔人：顾泽元 大纲审批人：一、本实验课的性质、任务与目的数据结构课程是计算机科学与技术专业的一门重要的专业基础课。通过此实验教学和学生的上机实践，要求学生掌握各种数据结构的具体物理实现方法，掌握用数据结构知识解决实际问题的方法，以达到理论指导实践的目的。从而进一步提高学生的编程能力、算法设计能力及分析问题、解决问题的能力。二、本实验课的基本理论1线性表存储结构及其基本操作的实现。2栈和队列的存储结构及其基本操作的实现。3二叉树的存储结构及其基本操作的实现。4图的存储结构及其基本操作的实现。5各类查找算法的设计6各类排序算法的设计三、实验内容和教学基本要求序号实验名称学时实验内容实验要求实验类型1线性表2（1）顺序表的定义及其相关操作算法的实现；必做设计性（2）链表的定义及其相关算法的实现；必做设计性（3）集合的表示与运算。选做综合性（4）一元多项式的表示与运算选做综合性2栈与队列2（1）顺序栈的定义及其操作算法的实现；必做设计性（2）链式队列定义及其操作算法的实现；选做设计性（3）循环队列定义及其操作算法的实现；必做设计性（4）利用栈实现进制转换选做综合性（5）利用栈实现括号匹配检测选做综合性3二叉树2（1）二叉树的创建、递归遍历及其它基本操作的实现。必做设计性（2）二叉树的创建、非递归遍历及其它基本操作的实现。选做设计性（3）哈夫曼树及哈夫曼编码的算法实现。选做综合性4图2（1）图的邻接矩阵存储方式的实现、图的遍历算法。必做设计性（2）图的邻接矩阵存储方式的实现、图的遍历算法。必做设计性（3）图最小生成树算法选做综合性（4）图的拓扑排序算法选做综合性（5）图的最短路径算法选做综合性5查找2（1）顺序查找算法、二分法查找算法、必做设计性（2）二叉排序树的创建与查找、选做设计性（3）哈希表的造表与查找算法选做设计性（4）班级学生成绩管理（表的存储、相关查找等）选做综合性6排序2（1）直接插入排序算法、SHELL排序算法必做设计性（2）快速排序算法、归并排序算法选做设计性（3）选择排序算法、堆排序算法必做设计性（4）班级学生成绩管理（利用某种排序方法实现按某个或某些关键字排序）选做综合性四、仪器设备配置每人一台计算机，安装Turbo C软件。五、教学文件与教学形式1教学文件数据结构（C语言版），严蔚敏、吴伟民编著，清华大学出版社，2002.9。2教学形式应用多媒体讲授实验内容、要求及注意事项，上机辅导，最后进行实验总结。六、考核方法及成绩评定办法每次完成实验内容，进行总结分析，写出实验报告。按照实验内容完成情况及实验报告书写情况进行考核，成绩按优、良、中、及格、不及格五级分评定。数据结构上机实验编程指南为了更好地帮助同学们做好数据结构实验，在此给出数据结构上机编程的一般思路和程序的基本框架结构。具体程序结构按先后顺序可分为以下3个部分：1、预定义常量及类型 对于相关的常量与类型（如状态类型）进行定义，如：#define OK 1#define ERROR 0#define OVERFLOW 2#define TRUE 1#define FALSE 0typedef int Status;2、相关数据结构类型定义此部分包括对所使用的数据结构给出其类型定义，及基本操作函数定义。（具体内容可参见实验一）3、主调程序的定义此部分给出相关的主调程序，在此程序中定义相关数据结构变量，并通过调用其操作函数，实现设计目的。（具体内容可参见实验一）实验一 线性表一、实验目的1掌握顺序表及其基本操作的实现。2掌握链表及其基本操作的实现。3掌握利用TC实现数据结构的编程方法。4通过上机实践进一步加深对线性表的顺序存储方式及链式存储方式的理解。5通过上机实践加强利用数据结构解决实际应用应用问题的能力。二、实验要求1实验前做好充分准备，包括复习第一章、第二章所学内容，事先预习好本次实验内容。2实验时记录实验结果，按要求完成各题。3实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验内容实验要求实验类型线性表2（1）顺序表的定义及其相关操作算法的实现；必做设计性（2）链表的定义及其相关算法的实现；必做设计性（3）集合的表示与运算。选做综合性（4）一元多项式的表示与运算选做综合性说明：（1）实验内容1）与实验内容2）为必做内容。（2）实验内容3）与实验内容4）为选做内容。四、实验内容与要求1、实验题目一：顺序表的定义及其相关操作算法的实现要求：编程实现顺序表的类型定义及顺序表的初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。2、实验题目二：链表的定义及其相关操作算法的实现要求：编程实现单链表（或双向链表、循环链表）的类型定义及其初始化操作、插入操作、删除操作、取元素操作、输出操作等，并对其进行验证。3、实验题目三：集合的表示与运算要求：利用题目一或题目二所定义的线性表（顺序表或链表）实现集合的表示及其并、交等运算，并进行验证给出结果。4、实验题目四：一元多项式的表示与运算要求：利用线性表（顺序表或链表）实现一元多项的类型定义及其相加等等运算，并进行验证给出结果。五、实验程序示例1、顺序表实验程序示例#include stdio.h#include alloc.h /*-（1）预定义常量及类型-*/#define OK 1#define ERROR 0#define OVERFLOW -2#define TRUE 1#define FALSE 0typedef int Status; /*-（2）顺序表类型及其基本操作函数的定义-*/#define InitSize 100#define INCR 20typedef int ElemType; /*定义元素类型为int类型*/typedef struct ElemType *Elem;int Length;int ListSize;SqList; /*SqList类型为顺序表类型*/Status InitList_sq(SqList &L) /*初始化操作函数定义*/ L.Elem=(ElemType*)malloc(InitSize*sizeof(ElemType); if (!(L.Elem)return(OVERFLOW); L.Length=0; L.ListSize=InitSize; return OK; Status ListInsert_sq(SqList &L, int i, ElemType e) /*插入操作函数定义*/ int j; if (iL.Length+1) return ERROR; if (L.Length=L.ListSize) L.Elem=(ElemType*)malloc(L.ListSize+INCR)*sizeof(ElemType);if(!(L.Elem) return(OVERFLOW);L.ListSize+=INCR; for(j=L.Length-1;j=i-1;j-) L.Elemj+1=L.Elemj; L.Elemi-1=e; L.Length+; return OK; void ListOutput_sq(SqList L)/*顺序表输出操作*/ int i; for(i=0;i=L.Length-1;i+) printf(%6d,L.Elemi); printf(n);/*其它操作如删除、查找、判空等操作略*/*-（3）主函数定义-*/main() SqList La; int i; InitList_sq(La); for (i=0;inext=NULL; return OK; Status ListInsert_l(LinkList &L,int i,ElemType e) /*插入操作函数定义*/LinkList p,s; int j; p=L;j=0; while(p&jnext;j+; if (!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(struct Lnode); s-data=e; s-next=p-next; p-next=s; return OK; void ListOutput_l(LinkList L) /*输出操作函数定义*/ LinkList p; p=L-next; while(p) printf(%6d,p-data); p=p-next; printf(n); /*其它操作如删除、查找、判空等操作略*/*-（3）主函数定义-*/ main() int i; LinkList La; InitList_l(La); for (i=0;inext=NULL; p=L; for(i=1;icoef=coef;s-expn=expn; s-next=NULL;p-next=s;p=s; void OutputPoly(POLY L)/*一元多项式的输出操作*/ int flag=1; /*flag用来是否为第一项的标识*/ POLY p; p=L-next; while(p) if(flag) printf(%dX%d,p-coef,p-expn); flag=0; else printf(%+dX%d,p-coef,p-expn); p=p-next; printf(n); void AddPoly(POLY La, POLY Lb, POLY &Lc)/*一元多项式的相加操作，即实现Lc=La+Lb*/ int x; POLY pa,pb,pc,s; Lc=(POLY)malloc(sizeof(struct PNode); Lc-next=NULL;pc=*Lc; pa=La-next;pb=Lb-next; while(pa&pb) if(pa-expnexpn) s=(POLY)malloc(sizeof(struct PNode); s-coef=pa-coef;s-expn=pa-expn; s-next=NULL;pc-next=s;pc=s; pa=pa-next; else if(pa-expnpb-expn) s=(POLY)malloc(sizeof(struct PNode); s-coef=pb-coef;s-expn=pb-expn; s-next=NULL;pc-next=s;pc=s; pb=pb-next; else x=pa-coef+pb-coef; if(x!=0) s=(POLY)malloc(sizeof(struct PNode); s-coef=x;s-expn=pa-expn; s-next=NULL;pc-next=s;pc=s; pa=pa-next; pb=pb-next; while(pa) s=(POLY)malloc(sizeof(struct PNode); s-coef=pa-coef;s-expn=pa-expn; s-next=NULL;pc-next=s;pc=s; pa=pa-next; while(pb) s=(POLY)malloc(sizeof(struct PNode); s-coef=pb-coef;s-expn=pb-expn; s-next=NULL;pc-next=s;pc=s; pb=pb-next; main() POLY La,Lb,Lc; int n; printf(Creat Poly La:n); printf(t Input the number of items of La:); scanf(%d,&n); CreatPoly(La,n); printf(nLa(x)=); OutputPoly(La); printf(Creat Poly Lb:n); printf(tInput the number of items of Lb:); scanf(%d,&n); CreatPoly(Lb,n); printf(nLb(x)=); OutputPoly(Lb); AddPoly(La,Lb, Lc); printf(Lc(x)=La(x)+Lb(x)=); OutputPoly(Lc); 实验二 栈与队列一、实验目的1掌握栈及其基本操作的实现。2掌握队列及其基本操作的实现。3进一步掌握利用TC实现数据结构的编程方法。二、实验要求1实验前做好充分准备，包括复习第三章所学内容，事先预习好本次实验内容。2实验时记录实验结果，按要求完成各题。3实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验内容实验要求实验类型栈与队列2（1）顺序栈的定义及其操作算法的实现；必做设计性（2）链式队列定义及其操作算法的实现；选做设计性（3）循环队列定义及其操作算法的实现；必做设计性（4）利用栈实现进制转换选做综合性说明：（1）实验内容1）与实验内容3）为必做内容。（2）实验内容2）与实验内容4）为选做内容。四、实验内容与要求1、实验题目一：顺序栈的定义及其操作算法的实现要求：编程实现顺序栈表的类型定义及顺序表的初始化操作、入栈操作、出栈操作、取栈顶元素操作、输出操作等，并对其进行验证。2、实验题目二：链式队列的定义及其相关操作算法的实现要求：编程实现链式队列的类型定义及其初始化操作、入队操作、出队操作、取队头操作、输出操作等，并对其进行验证。3、实验题目三：循环队列定义及其操作算法的实现要求：编程实现循环队列的类型定义及其初始化操作、入队操作、出队操作、取队头操作、输出操作等，并对其进行验证。4、实验题目四：利用栈实现进制转换要求：利用栈（顺序栈或链式栈）实现进制转换问题五、实验程序示例1、顺序栈的定义及其操作算法的实现#include stdio.h#define OK 1#define ERROR 0#define OVERFLOW -2#define TRUE 1#define FALSE 0typedef int Status; #define Init_Size 100#define INCR 20typedef int ElemType;typedef structElemType *Elem; int Top; int StackSize;SqStack;Status InitStack(SqStack &S) S.Elem=(ElemType *)malloc(Init_Size*sizeof(ElemType); if(!S.Elem) return OVERFLOW; S.Top=0; return OK;Status GetTop(SqStack S, ElemType &e)if (S.Top=0) return ERROR; e=S.ElemS.Top-1; return OK; Status Push(SqStack &S, ElemType e) if(S.Top=S.StackSize) S.Elem=(ElemType*)malloc(S.StackSize+INCR)*sizeof(ElemType); if(!S.Elem) return(OVERFLOW); S.StackSize+=INCR;S.ElemS.Top+=e; return OK; Status Pop(SqStack &S,ElemType &e) if (!S.Top) printf(stack is empty when popingn);return(ERROR); e=S.Elem-S.Top; return OK; void StackOutput(SqStack S) int i; for(i=0;iS.Top;i+) printf(%d ,S.Elemi); printf(n); main() SqStack S; ElemType e; int i; clrscr(); InitStack(S); for(i=1;i=5;i+) Push(S,2*i+1); StackOutput(S); Pop(S, e); StackOutput(S); Push(S,111); StackOutput(S); Push(S,222); StackOutput(S); Pop(S, e); StackOutput(S); 2、循环队列的定义及其相关操作算法的实现#include stdio.h#define OK 1#define ERROR 0#define OVERFLOW -2#define TRUE 1#define FALSE 0typedef int Status; #define MAX 10typedef int ElemType;typedef structElemType *Elem; int front; int rear; CirQueue;Status InitQueue(CirQueue &Q)Q.Elem=(ElemType *)malloc(MAX*sizeof(ElemType); if(!Q.Elem) return(OVERFLOW);Q.front=Q.rear=0;return OK;Status EnQueue(CirQueue &Q,ElemType e) if(Q.rear+1)%MAX=Q.front) return ERROR; Q.ElemQ.rear=e; Q.rear=(Q.rear+1)%MAX; return OK;Status DeQueue(CirQueue &Q,ElemType &e) if(Q.rear=Q.front) return ERROR; e=Q.ElemQ.front; Q.front=(Q.front+1)%MAX; return OK; void QueueOutput(CirQueue Q)int i; for(i=Q.front;i!=Q.rear;i=(i+1)%MAX) printf(%5d,Q.Elemi); printf(n); main()CirQueue Q; ElemType e; int i; InitQueue(Q); for(i=1;i=5;i+) EnQueue(Q,i); QueueOutput(Q); DeQueue(Q, e); QueueOutput(Q); for(i=1;i=3;i+) DeQueue(Q, e); QueueOutput(Q); for(i=6;idata=ch; CreatBiTree(T-lchild); CreatBiTree(T-rchild); void Preorder(BiTree T)/*先序遍历二叉树的递归算法*/ if (T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); void Inorder(BiTree T) /*中序遍历二叉树的递归算法*/ /*代码略*/ void Postorder(BiTree T) /*后序遍历二叉树的递归算法*/ /*代码略*/ int DepthTree(BiTree T) /*求二叉树深度的递归算法*/ int d1,d2; if(!T) return 0; /*当树空时*/ else d1=DepthTree(T-lchild); /*求左子树的深度*/ d2=DepthTree(T-rchild); /*求右子树的深度*/ return d1=d2?d1+1:d2+1;/*返回左、右子树深度较大者加1*/ main() BiTree T; clrscr(); CreatBiTree(T); printf(Preorder binary tree :n ); Preorder(T); printf(nInorder binary tree:n); Inorder(T); printf(nPostorder binary tree:n); Postorder(T); printf(nThe depth of this binary tree is:%dn,DepthTree(T);ABCDEFG程序运行说明：若创建的二叉树如右图所示，则应输入： ABD$EG$C$F$ 图示 预创建的二叉树2、二叉树非递归遍历算法的实现 在题目一的基础上实现二叉树先序、中序、按层遍历的非递归遍历。 void Preorder_N(BiTree T)/*先序非递归遍历*/ SqStack S; /*定义一个栈S，设栈的实现采用实验二的顺序栈，栈中元素为BiTree类型*/ BiTree p;InitStack(S); Push(S,T); while(!StackEmpty(S)/*当栈非空时*/ while (gettop(S,p)&p) printf(%c,p-data); Push(S,p-lchild); Pop(S, p);/*空指针出栈*/ if(!StackEmpty(S) Pop(S,p); Push(S,p-rchild); void Inorder_N(BiTree T) /*中序非递归遍历*/ /*略*/ void LevelOrder(BiTree T) /*按层遍历*/ CirQueue Q; /*定义一个队列Q，设队列的实现采用实验二的循环队列，队列中元素为BiTree类型*/ BiTree p; InitQueue(Q);if(T) EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,p);printf(%c,p-data); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); 实验四 图一、实验目的1掌握图的邻接矩阵作为存储结构的方法及其相关操作的实现。2掌握图的邻接表作为存储结构的方法及其相关操作的实现。3掌握图的最小生树的Prim算法。4通过实践掌握图的的拓扑排序、最短路径算法的实现。二、实验要求1实验前做好充分准备，包括复习第七章所学内容，事先预习好本次实验内容。2实验时记录实验结果，按要求完成各题。3实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。三、实验题目本次实验给出的选定题目如下表所示。实验名称学时实验内容实验要求实验类型二叉树2（1）图的邻接矩阵存储的实现、图的遍历算法。必做设计性（2）图的邻接表存储方的实现、图的遍历算法。必做设计性（3）图最小生成树算法选做综合性（4）图的拓扑排序算法选做综合性（5）图的最短路径算法选做综合性说明：（1）实验内容1）、2）为必做内容。（2）实验内容3）、4）、5）为选做内容。四、实验内容与要求1、实验题目一：图的邻接矩阵存储的实现、图的遍历算法 要求：采用邻接矩阵作为图的存储结构，实现图的相关基本操作的算法，并对其进行验证。2、实验题目二：图的邻接表存储方的实现、图的遍历算法 要求：采用邻接表作为图的存储结构，实现图的相关基本操作的算法，并对其进行验证。3、实验题目三：图最小生成树算法要求：在题目一或题目二的基础上利用邻接矩阵（或邻接表）作为图的存储结构，编程实现最小生成树求解，并对其进行验证。4、图的拓扑排序算法要求：在题目二的基础上利用邻接表作为图的存储结构，编程实现有向图的拓扑排序算法，并对其进行验证。5、图的最短路径算法要求：在题目一或题目二的基础上利用邻接矩阵（或邻接表）作为图的存储结构，编程实现最短路径算法，并对其进行验证。五、实验程序示例1、无向图的邻接矩阵存储的实现、图的遍历算法#include #include #define INFINITY INT_MAX 999#define MAX_VERTEX_NUM 20typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*矩阵类型*/typedef char VexType10; /*顶点类型*/typedef struct VexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;int kind; /*图的种类：1-无向图 2-无向网 3-有向图 4-有向网*/MGraph; /*图的类型*/int LocateVex();void CreatUDG(MGraph &G) /*无向图的创建操作*/ VexType v1,v2; int i,j,k; printf(Input vertex number and edg number:); scanf(%d%d,&G.vexnum,&G.arcnum); printf(Input vertexs:n); for(i=0;iG.vexnum;+i) scanf(%s,G.vexsi); for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j) G.arcsij=0; for(k=0;kG.arcnum;+k) printf(Input edge(v1 v2):); scanf(%s%s,v1,v2); i=LocateVex(G,v1); if(i=-1) printf( Error!n); return; j=LocateVex(G,v2); if(j=-1) printf( Error!n); return; G.arcsij=G.arcsji=1; int LocateVex(MGraph &G,VexType v) /*在图G中查找顶点v，若存在返回位置，否则返回-1*/ int i; for(i=0;iG.vexnum;i+) if(strcmp(G.vexsi,v)=0) return i; return -1; void GraphOutput(MGraph &G)/*图的邻接矩阵的输出操作*/ int i,j; printf(t); for(i=0;iG.vexnum;+i) printf(%8s,G.vexsi); printf(n); for(i=0;iG.vexnum;+i) printf(%st,G.vexsi); for(j=0;jG.vexnum;+j) printf(%8d,G.arcsij); printf(n); int FirstAdjVex(MGraph &G, int v)/*求v的第一个邻接顶点*/ /*代码略*/int NextAdjVex(MGraph &G, int v,int w) /*求v的相对于w的下一个邻接顶点*/ /*代码略*/DFSTraverse(MGraph &G)/*图的深度优先遍历算法*/ /*代码略*/BFSTraverse(MGraph &G)/*图的深度优先遍历算法*/ /*代码略*/*其他操作略*/main() MGraph G; CreatUDG(G); UDGOutput(G); DFSTraverse(G);BFSTraverse(G);2、有图的邻接表存储的实现、图的遍历算法#include stdio.h#include alloc.h#define max 20#define Null 0struct arcnode int adjvex; struct arcnode *nextarc;struct vexelem char data; struct arcnode *firstarc;typedef struct struct vexelem vexmax; int vexnum,arcnum; int kind; adjlist;int locate(adjlist &G, char v1) int i; for (i=0;iG.vexnum;i+) if(G.vexi.data=v1) return i; printf(not find); return -1;void creatdg(adjlist &G)/*有向图的创建*/ int i,jv1,jv2; char v1,v2,ch; struct arcnode *s; G.kind=1; printf(input the num of vertex:); scanf(%d,&(G.vexnum); printf(input the num of arcs:); scanf(%d,&(G.arcnum); for(i=0;iG.vexnum;i+) getchar(); printf(input %dth vertex:,i+1); scanf(%c,&(G.vexi.data); G.vexi.firstarc=Null; for(i=0;iG.arcnum;i+) getchar(); printf(input %dth edge,FORMAT:(A,B)n,i+1); scanf(%c%c%c,&v1,&ch,&v2); jv1=l