2022年数据结构实验指导书 .pdf

《2022年数据结构实验指导书 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验指导书 .pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验指导书（适用于计算机应用、软件技术专业）信息工程系名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 25 页 -目录前言 .3实验一、单链表的基本操作.错误！未定义书签。实验二栈和队列.错误！未定义书签。实验三串.错误！未定义书签。实验四二叉树的遍历.错误！未定义书签。实验五树的应用.错误！未定义书签。实验六图.错误！未定义书签。实验七、折半查找和二叉排序树.错误！未定义书签。实验八、内部排序.错误！未定义书签。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 25 页 -前言数据结构是计算机应用、软件技术等专业的专业基础必修课，主要介绍如何合理地组织数据、

2、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。数据结构 是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 25 页 -实验一链表的操作一

3、、实验目的1、通过实验，掌握链表的输入与输出2、通过实验，掌握链表的基本操作二、实验内容1、建立自己的有关链表的头文件2、练习链表的输入与输出3、练习链表的基本操作的实现4、练习链表基本操作的应用三、实验前的准备1、复习相关课程内容，理解并掌握链表基本操作算法2、准备相关的程序清单3、阅读实验指导书四、实验步骤与方法（一）、理解并运行下面的程序将用户输入的数据按头插入法建立一个带头结点的单链表。输入结点数据时以输入一串字符的方式实现，$字符为结束输入字符。#include “datastru.h”#include#include int count_head(LINKLIST*head)名师资

4、料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 25 页 -/*带头结点的单链表:输出单链表元素值并计数*/int I=0;LINKLIST*p;p=head-next;printf(“输出单链表元素值:“);while(p!=NULL)printf(“%c”,p-data);I+;p=p-next;printf(“n”);return I;LINKLIST*creatlink_head_head(LINKLIST*head)/*用头插入法建立带头结点的单链表*/LINKLIST *t;char ch;t=(LINKLIST*)malloc(sizeof(LINKLIST);head=

5、t;t-next=NULL;printf(“单链表元素值为单个字符,连续输入，$为结束字符:“);while(ch=getchar()!=$)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 25 页 -t=(LINKLIST*)malloc(sizeof(LINKLIST);t-data=ch;t-next=head-next;head-next=t;return(head);main()LINKLIST*head=NULL;int num;printf(“n 建立单链表n”);head=creatlink_head_head(head);fflush(stdin);num=co

6、unt_head(head);printf(“单链表元素个数n”,num);运行情况如下：输入：输出：名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 25 页 -（二）、建立自己的头文件mylinklist.h，内容包括单链表数据结构的说明，链表的建立与输出、插入与删除操作等要求：程序自己用附页附上（三）、单链表基本操作的应用1、通过调用基本操作的功能函数，完成单链表指定位置元素的插入、删除。程序清单：运行结果：五、实验中出现的问题与解决方法名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 25 页 -实验二栈与队列的基本操作一、实验目的1、通过实验，掌握输入与输出2

7、、通过实验，掌握栈与队列的基本操作二、实验内容3、建立相关的头文件4、栈与队列的基本操作练习三、实验前的准备1、复习相关课程内容，掌握并理解栈与队列的基本操作2、准备相关的程序清单3、阅读实验指导书四、实验步骤与方法（一）、建立自己的有关栈与队列的头文件，内容包括栈与队列数据结构的说明，基本操作的实现等（二）、完成一栈的建立与输出。写出程序及运行结果（三）、完成一队列的建立与输出五、实验中出现的问题与解决方法名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 25 页 -实验三串的操作一、实验目的1、通过实验，掌握顺序串的数据类型描述及基本操作的实现二、实验内容1、练习顺序串的应用三

8、、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法（一）、顺序串的应用1、建立自己的头文件MYSTRING.H,内容包括顺序串的数据类型描述,串的连接、串的定位操作等2、编写算法，完成顺序串的数据生成与数据的输出，并将这两个函数加入到 MYSTRING.H 中3、编写算法，通过调用相关函数验证子串的定位操作五、实验中出现的问题与解决方法名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 25 页 -实验四二叉树一、实验目的1、通过实验，掌握二叉树的建立与存储2、通过实验，掌握二叉树的遍历方法二、实验内容1、练习二叉树的建立与存储2、练习二

9、叉树的遍历三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法，其中，建立二叉树的代码如下：BTCHINALR *createbt()BTCHINALR*q;struct node1*s30;int j,i,x;printf(建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开 nn);名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 25 页 -printf(i,x=);scanf(%d,%c,&i,&x);while(i!

10、=0&x!=$)q=(BTCHINALR*)malloc(sizeof(BTCHINALR);/*建立一个新结点 q*/q-data=x;q-lchild=NULL;q-rchild=NULL;si=q;/*q新结点地址存入 s 指针数组中*/if(i!=1)/*i=1，对应的结点是根结点*/j=i/2;/*求双亲结点的编号j*/if(i%2=0)sj-lchild=q;/*q结点编号为偶数则挂在双亲结点 j 的左边*/else sj-rchild=q;/*q结点编号为奇数则挂在双亲结点 j 的右边*/printf(i,x=);scanf(%d,%c,&i,&x);return s1;/*返回

11、根结点地址*/2、建立教材中 P77图 6.9 示的二叉树,并通过调用函数,，输出先序遍历、中序遍历与后序遍历的结果。写出有关算法五、实验中出现的问题与解决方法名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 25 页 -实验五树的应用一、实验目的通过实验，进一步掌握树的应用二、实验内容练习二叉树的应用三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、查找二叉链表中指定的结点的子函数如下，请编写程序验证此算法#include#include#include BTCHINALR*search_ch(BTCHINALR*cur,ch

12、ar x)/*先序查找*/BTCHINALR*temp;if(cur=NULL)return NULL;if(x=cur-data)return cur;temp=search_ch(cur-lchild,x);if(temp!=NULL)return temp;else return search_ch(cur-rchild,x);名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 25 页 -;main（）2、编写算法，求二叉树中叶子结点的个数3、查找给定结点的双亲结点的算法，请编写程序，验证此算法#include#include#include BTCHINALR*paren

13、t(BTCHINALR*start,BTCHINALR*current)/*从 start所指结点起查找当前结点current的父亲结点*/BTCHINALR*p;if(start=NULL)return NULL;if(start-lchild=current|start-rchild=current)return start;p=parent(start-lchild,current);if(p!=NULL)return p;else return parent(start-rchild,current);main（）五、实验中出现的问题与解决方法名师资料总结-精品资料欢迎下载-名师精心整

14、理-第 13 页，共 25 页 -实验六图的建立与存储一、实验目的1、通过实验，掌握图的建立与存储二、实验内容1、练习用图的邻接矩阵表示法存储图2、练习用图的邻接链表表示法存储图三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、图的邻接矩阵表示法算法如下，通过如下算法，完成图的建立#include#include#include MGRAPH create_mgraph()/*建立图的邻接矩阵*/int i,j,k;MGRAPH mg;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 25 页 -mg.kind=2;printf

15、(nn输入顶点数和边数(用逗号隔开):);scanf(%d,%d,&i,&j);fflush(stdin);mg.vexnum=i;mg.arcnum=j;printf(nn);for(i=0;img.vexnum;i+)printf(输入顶点%d 的值:,i+1);scanf(%d,&mg.vexsi);fflush(stdin);for(i=0;img.vexnum;i+)for(j=0;jmg.vexnum;j+)mg.arcsij=0;for(k=1;k=mg.arcnum;k+)printf(输入第%d 条边的起始顶点和终止顶点(用逗号隔开):,k);scanf(%d,%d,&i,&

16、j);fflush(stdin);while(img.vexnum|jmg.vexnum)printf(输入错，重新输入:);scanf(%d,%d,&i,&j);mg.arcsi-1j-1=1;mg.arcsj-1i-1=1;return mg;名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 25 页 -main（）2、图的邻接链表表示法算法如下，通过如下算法，完成图的建立#include#include#include ADJGRAPH creat_adjgraph()EDGENODE *p;int i,s,d;ADJGRAPH adjg;adjg.kind=2;print

17、f(nn输入顶点数和边数(用逗号隔开):);scanf(%d,%d,&s,&d);fflush(stdin);adjg.vexnum=s;/*存放顶点数在adjg.vexnum 中*/adjg.arcnum=d;/*存放边点数在adjg.arcnum 中*/printf(nn);名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 25 页 -for(i=0;i adjg.vexnum;i+)printf(输入顶点%d 的值:,i+1);scanf(%d,&adjg.adjlisti.vertex);/*输入顶点的值*/fflush(stdin);adjg.adjlisti.link

18、=NULL;printf(nn);for(i=0;i adjg.arcnum;i+)printf(输入第%d 条边的起始顶点和终止顶点(用逗号隔开):,i+1);scanf(%d,%d,&s,&d);/*输入边的起始顶点和终止顶点*/fflush(stdin);while(s adjg.vexnum|d adjg.vexnum)printf(输入错，重新输入:);scanf(%d,%d,&s,&d);s-;d-;p=malloc(sizeof(EDGENODE);/*建立一个和边相关的结点*/p-adjvex=d;p-next=adjg.adjlists.link;/*挂到对应的单链表上*/a

19、djg.adjlists.link=p;p=malloc(sizeof(EDGENODE);/*建立另一个和边相关的结点*/p-adjvex=s;p-next=adjg.adjlistd.link;/*挂到对应的单链表上*/名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 25 页 -adjg.adjlistd.link=p;return adjg;main（）五、实验中出现的问题与解决方法名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 25 页 -实验七基本查找算法一、实验目的1、通过实验，掌握静态查找的算法2、通过实验，掌握动态查找的算法二、实验内容1、练习顺

20、序表上查找元素2、练习二分法查找元素三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、完成顺序表上顺序查找元素的算法#include datastru.h#include int seq_search(KEYTYPE k,SSTABLE *st)/*顺序表上查找元素*/int j;j=st-len;/*顺序表元素个数*/st-r0.key=k;/*st-r0单元作为监视哨*/名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 25 页 -while(st-rj.key!=k)j-;/*顺序表从后向前查找*/return j;/*j

21、=0,找不到；j0 找到*/main()运行情况如下：2、写一算法，完成有序表上二分法查找元素五、实验中出现的问题与解决方法名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 25 页 -实验八简单内部排序一、实验目的通过实验，掌握简单的排序方法二、实验内容1、练习直接插入排序2、练习冒泡排序3、练习选择排序三、实验前的准备1、复习课本的相关内容2、阅读实验指导书3、准备好相关的程序清单四、实验步骤与方法1、完成直接插入排序的算法，理解并运行下面的程序#include datastru.h#include void insertsort(RECNODE*r,int n)名师资料总结

22、-精品资料欢迎下载-名师精心整理-第 21 页，共 25 页 -main()RECNODE aMAXSIZE;int i,j,k,len;printf(nn输入待排序数据(整数，以空格隔开，0 结束):);k=0;scanf(%d,&j);while(j!=0)k+;ak.key=j;scanf(%d,&j);len=k;printf(n排序前 :);for(i=0;i len;i+)printf(%d,ai+1.key);printf(n);insertsort(a,len);printf(nn排序后 :);for(i=0;i len;i+)printf(%d,ai+1.key);print

23、f(nn);2、完成冒泡排序的算法，理解并运行下面的程序名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 25 页 -#include void bublesort(RECNODE*r,int n)main()RECNODE aMAXSIZE;int i,j,k,len;printf(nn输入待排序数据(整数，以空格隔开，0 结束):);k=0;scanf(%d,&j);while(j!=0)k+;ak.key=j;scanf(%d,&j);len=k;printf(n排序前 :);for(i=0;i len;i+)printf(%d,ai+1.key);printf(n);名师

24、资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 25 页 -bublesort(a,len);printf(nn排序后 :);for(i=0;i len;i+)printf(%d,ai+1.key);printf(nn);3、完成简单选择排序的算法，理解并运行下面的程序#include datastru.h#include void selesort(RECNODE*r,int n)main()RECNODE aMAXSIZE;名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 25 页 -int i,j,k,len;printf(nn输入待排序数据(整数，以空格隔开，0 结束):);k=0;scanf(%d,&j);while(j!=0)k+;ak.key=j;scanf(%d,&j);len=k;printf(n排序前 :);for(i=0;i len;i+)printf(%d,ai+1.key);printf(n);selesort(a,len);printf(nn排序后 :);for(i=0;i len;i+)printf(%d,ai+1.key);printf(nn);五、实验中出现的问题与解决方法名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 25 页 -