数据结构实验指导书(共16页)

1、精选优质文档-倾情为你奉上数据结构与算法课程简介：本课程总学时需要64学时,其中实验课10学时,共有5个实验,每个实验为2学时,从其中的7个实验选其中的5个。本课程的先行课为C+程序设计实验一 线性表及其应用一、实验目的 1、掌握用上机调试线性表的基本方法； 2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。 二、实验环境 硬件：PC 微型计算机、256M以上内存，40G以上硬盘。 软件：Windows XP，VC或VS.Net三、实验内容 线性表基本操作的实现 当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第

2、i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。 四、实验步骤 1、 本实验的程序清单如下。 下面只是根据实验指导书上的程序，各位同学要按照实际上机调试后的结果程序附上： typedef Null 0; typedef int datatype; #define maxsize 1024; typedef struct datatype datamaxsize; int last; sequenlist; int insert(L, x, i) sequenlist *L; int i; in

3、t j; if (*L).last= =maxsize-1) printf(“overflow”); return Null; else if (i<1)(i>(*L).last+1) printf(“error”); return Null; else for(j=(*L).last; j>=i-1; j-) (*L).dataj+1=(*L).dataj; (*L).datai-1=x; (*L).last=(*L).last+1; return(1); int delete(L,i) sequenlist *L; int i; int j; if (i<1)(i&

4、gt;(*L).last+1) printf (“error”); return Null; else for(j=i, j<=(*L).last; j+) (*L).dataj-1=(*L).dataj; (*L).data - -; return(1); void creatlist( ) sequenlist *L; int n, i, j; printf(“请输入n个数据n”); scanf(“%d”,&n); for(i=0; i<n; i+) printf(“data%d=”, i); scanf (“%d”, (*L).datai); (*L).last=n-

5、1; printf(“n”); printout (L) sequenlist *L; int i; for(i=0; i<(*L).last; i+) printf(“data%d=”, i); printf(“%d”, (*L).datai); void main( ) sequenlist *L; char cmd; int i, t; clscr( ); printf(“i, I.插入n”); printf(“d,D.删除n”); printf(“q,Q退出n”); do do cmd =getchar( ); while(cmd!=d)(cmd!=D) (cmd!=q) (cm

6、d!=Q) (cmd!=i) (cmd!=I); switch (cmd) case i,I; scanf(&x); scanf(&i); insert(L, x, i); printout(L); break; case d,D; scanf(&i); delete(L, i); printout(L); break; while (cmd!=q)&&( cmd!=Q); 2、 本程序运行的结果如下： 根据各位同学的实际调试数据编写。 3、 结合以上程序如何进行分析和改进。并把分析和改进的内容附上。 五、实验小结 实验过程中的体会和收获。 六、实验思考

7、题与练习 线性表的非顺序存储结构如何实现？链表是如何操作的？模仿线性表的顺序存储结构的实验编写线性表的非顺序存储结构的实验报告并进行相应的实验。 实验二 栈的基本操作 一、 实验目的 1掌握栈的基本操作：2初始化栈、判栈为空、出栈、入栈等运算。 二、实验要求 1 认真阅读和掌握本实验的算法。 2 上机将本算法实现。 3 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验内容 利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为： 1、定义栈的顺序存取结构 2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3、定义一个函数用来实现上面问题： 十进制整数X和R作为形参

8、 初始化栈 只要不为重复做下列动作 将入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 四、实验思考题与练习 1、如何实现队列的操作 2、利用栈实现数学表达式的转换 3、迷宫问题 选择一个以上题目进行实验，并编写实验报告 实验三、队列应用迷宫问题 一、 实验内容 n*m迷宫是一个矩形区域，（1，1）为入口（n，m）为出口，0表示该方格可通过，1表示该方格有阻碍不能通过，每次只能从一个无障碍方格向其周围8各方向的邻接任一无障碍方格移动一步，问，当迷宫有解时如何寻找一条由入口到出口的路径并返回这个序列，或者不能连通时给出无解标志。迷宫如下表所示。 一个带边界哨的10×

9、15迷宫 1 1 1 1 1 1 1 11111111 1 1 1 0 0 0 1 0 0 01000100 1 1 1 0 1 0 0 0 1 01000111 1 1 1 0 1 1 1 1 1 01101110 1 1 1 1 1 0 0 0 1 10111010 1 1 1 1 0 0 1 0 1 11101010 1 1 1 1 0 1 0 0 1 01010101 0 1 1 1 0 1 1 1 1 10011111 0 1 1 1 1 1 0 1 1 11010101 0 1 1 1 0 1 0 1 0 11101000 1 1 1 0 1 0 1 0 1 00011001 0

10、1 1 1 1 1 1 1 1 11111111 1 1 二、 实验要求 提出思想 给出算法 程序设计 给定一个迷宫表，列出运行结果 三、 实验目的 通过实验，同学掌握队列数据结构在算法中的深入应用方法，这是宽度优先的搜索过程中使用队列结构的典型应用 实验四 二叉树的操作 一、实验目的 1、进一步掌握指针变量、动态变量的含义； 2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围； 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、 实验要求 1 认真阅读和掌握本实验的程序。 2 上机运行本程序。 3 保存和打印出程序的运行结果，并结合程序进行分析。 4 按照你二叉树的操作需要，重新

11、改写主程序并运行，打印出文件清单和运行结果 三、实验内容 已知以二叉链表作存储结构，试编写按层次顺序遍历二叉树的算法。 算法思想：本算法要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。 程序实现： #define M 100 #define Null 0 typedef struct node int data; stuuct node *lchild, *rchild; bitree; bitree *queM; int

12、front=0, rear=0; bitree *creat( ) bitree *t; int x; scanf (“%d”, &x); if (x= =0) t=Null; else t=malloc(sizeof(bitree); tdata=x; tlchild=creat( ); trchild=creat( ); return t; void inorder( t ) bitree *t; if (t!=Null) inorder (tlchild); printf(“%4d”, tdata); inorder (trchild); void enqueue(t) bitr

13、ee *t; if(front!=(rear+1) % M) rear = (rear+1) % M; querear=t; bitree *delqueue( ) if (front= =rear) return Null; front=(front+1) % M; return (quefront); void levorder ( t ) bitree *t; bitree *p; if(t!=Null) enqueue( t ); while(front!=rear) p=delqueue( ); printf(“%4d”, pdata); if(plchild!=Null) enqu

14、eue(plchild); if(prchild!=Null) enqueue(prchild); main ( ) bitree *root; printf(“n”); root=creat ( ); inorder(root); printf(“n”); levorder(root); 四、实验思考题与练习 1、二叉树顺序表示和相应的操作？ 2、二叉树的递归算法？ 3、二叉树的应用举例？ 选择一个以上题目进行实验，并编写实验报告 实验五 图的及其应用 一、实验目的 1、掌握图的基本存储方法； 2、掌握有关图的操作算法并用高级语言实现； 3、熟练掌握图的两种搜索路径的遍历方法。 二、实验要求

15、 1认真阅读和掌握本实验的算法。 2上机将本算法实现。 3保存和打印出程序的运行结果，并结合程序进行分析。 三、实验内容 假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。 算法思想：下面是R、W、Floyd求每对顶点之间最短路径算法的C语言程序，程序中矩阵A用来进行n次迭代，矩阵P用来记录路径，Pij为迭代过程中当前已经求得的从顶点i到顶点j的最短路径上最后被插入的那个顶点。 算法实现： typedef

16、 struct node int no; float wgt; struct node *next; edgenode; typedef struct char vtx; edgenode *link; vexnode; typedef vexnode Graphn; void Floyd(Graph G, float Ann, int pnn) int i, j, k; for (i=0; i<n; i+) for(j=0;j<n;j+) Aij=Gij; Pij=-1; for (k=0; k<n; k+) for (i=0; i<n; i+) for (j=0;

17、j<n; j+) if(Aik +Akj<Aij) Pij=k; Aij=Aik+Akj; 四、实验思考题与练习 1、用矩阵表示图的方法及其相应的操作？ 2、用链接表表示图的方法及其相应的操作？ 3、图的应用举例？ 选择一个以上题目结合具体的应用实际进行实验，并编写实验报告 实验六 查找一、实验目的 1、掌握查找的不同方法，并能用高级语言实现查找算法； 2、熟练掌握二叉树的构造和查找方法。 二、实验要求 1认真阅读和掌握本实验的算法。 2上机将本算法实现。 3保存和打印出程序的运行结果，并结合程序进行分析。 三、实验内容 设计一个读入一串整数构成一棵二叉排序树的算法。 实现提示二叉

18、排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。 算法实现 typedef struct node int key; int other; struct node *lchild, *rchild; bstnode; void inorder ( t ) bstnode *t; if (t!=Null) inorder(tlchild); 专心-专注-专业printf(“%4d”, tkey); inorder(trchild); bs

19、tnode *insertbst(t, s) bstnode *s, *t; bstnode *f, *p; p=t; while(p!=Null) f=p; if (skey= =pkey) return t; if (skey<pkey) p=plchild; else p=prchild; if(t= =Null) return s; if (skey<fkey) flchild=s; else frchild=s; return t; bstnode *creatord( ) bstnode *t, * s; int key; t=Null; scanf(“%d”,&

20、;key); while (key!=0) s=malloc(sizeof (bitree); skey=key; slchild=Null; srchild=Null; scanf(“%d”, &data); sother=data; t=insertbst(t, s); scanf(“%d”,&key); return t; main ( ) bstnode *root ; root= creatord( ); inorder (root); 五、实验思考题1、顺序查找方法的上机验证？ 2、二分查找法的上机验证？ 3、索引结构和散列结构的查找方法？ 选择一个以上题目结合具体的应用实际进行实验，并编写实验报告实验七 排序一、实验目的 1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用； 3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂性和稳定性的分析方法。 二、实验要求 1认真阅读和掌握本实验的算法。 2上机将本算法实现。 3保存和打印出程序的运行结果，并结合程序进行分析。 三、实验内容 统计成绩 问题描述给出n个学生的考试成绩表，每条信息由