2020-03-03 05:40:48 来源:范文大全收藏下载本文
数据结构实验报告
课程 数据结构 _ 院 系
专业班级 实验地点
姓 名 学 号
实验时间 指导老师
数据结构上机实验报告1
一﹑实验名称:
实验一——链表
二﹑实验目的:
1.了解线性表的逻辑结构特性;
2.熟悉链表的基本运算在顺序存储结构上的实现,熟练掌握链式存储结构的描述方法;
3.掌握链表的基本操作(建表、插入、删除等) 4.掌握循环链表的概念,加深对链表的本质的理解。 5.掌握运用上机调试链表的基本方法
三﹑实验内容:
(1) (2) (3) (4) 创建一个链表 在链表中插入元素 在链表中删除一个元素 销毁链表 四﹑实验步骤与程序
#include #include typedef struct LNode {int data; struct LNode *next; }Lnode, *LinkList; //假设下面的链表均为带头结点。 void CreatLinkList(LinkList &L,int j) {//建立一个链表L,数据为整数,数据由键盘随机输入。
LinkList p,q; L=(LinkList )malloc(sizeof(Lnode)); L->next=NULL; q=L;
cout
for(int i=0;i
{
p=(LinkList)malloc(sizeof(Lnode));
cin>>p->data;
p->next=q->next;
q->next=p;
q=p;
} } int PrintLinkList(LinkList &L) {//输出链表L的数据元素
LinkList p;
} void LinkListLengh(LinkList &L) {//计算链表L的数据元素个数。 int i=0; p=L->next; if(L->next==NULL) {
} cout
{
coutdata
p=p->next; } cout
} LinkList p; p=L->next; while(p) {
i++;
p=p->next;
} cout
LinkList p,s; int j=0; p=L;
while(p&&j
} if(!p||j>i-1) { p=p->next; ++j;
}
} coutdata=x; s->next=p->next; p->next=s; return 1; int DeleteLinkList(LinkList &L,int i) {//删除链表L的第I个数据元素。
LinkList p,q; int j=0; p=L; while(p->next&&j
} if(!(p->next)||j>i-1) { p=p->next; ++j;
}
} coutnext; p->next=q->next; i=q->data; free(q); return 1; void DestroyLinkList(LinkList &L) {//销毁链表L。
LinkList p,q; p=L->next; while(L->next!=NULL) { q=p->next; L->next=q;
free(p); } p=q;
free(L);
cout
LinkList L;
int i,j,x; cout>j;
CreatLinkList(L,j);
LinkListLengh(L);
PrintLinkList(L);
cout>i; cout>x;
InsertLinkList(L,i,x);
LinkListLengh(L);
PrintLinkList(L);
cout>i;
DeleteLinkList(L,i);
LinkListLengh(L);
PrintLinkList(L);
cout
DestroyLinkList(L); } 五﹑实验结果
六﹑实验心得体会:
链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表中每一个元素称为“结点”,每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址。
实验的程序设计规划(实现的功能、分几个模块、子函数) (1) 编写链表创建子函数void CreatLinkList(L,j) (2) 编写链表插入子函数 int InsertLinkList(LinkList &L, int i, int x) (3)链表的打印int PrintLinkList(LinkList &L) (4)编写链表删除子函数 int DeleteLinkList(LinkList &L,int i) (5)编写链表销毁子函数void DestroyLinkList(LinkList &L) (6)编写主函数Main(),通过功能菜单调用子函数 (7)编译调试程序
经过多次的调试,修改,实验结果终于正确了,在这个过程中,经历了不知道怎么进行声明区的编写如包含文件,宏定义,函数声明,全局变量声明,结构体等的定义等的结合,到学会了使用先把程序主要规划为四个部分来写就简单多了,第一,定义;第二,写所要调用的子函数;第三,写主函数,调用子函数;第四就是程序的编译与调试,修改。数据结构实验需要我们对每个程序的算法有深刻的理解,才能应用到实际中去,因此我们需要在做实验之前要熟悉实验的内容,且先把所要实验的程序写出来,在实验中就可以查找错误并加以改正,这是一个成长的过程。
数据结构上机实验报告
2 一﹑实验名称:
实验二—队列
二﹑实验目的: 1.掌握队列这种抽象数据类型的特点, 掌握栈与队列在实际问题中的应用和基本编程技巧,并能在相应的问题中选用它; 2.熟练掌握循环队列和链队列的基本操作实现算法,特别是队满和队空的描述方法;
3.掌握栈与队列的数据类型描述及特点;
4.掌握栈的顺序和链式存储存表示与基本算法的实现; 5.掌握队列的链式存储表示与基本操作算法实现; 6.按照实验题目要求,独立完成实际程序的编写编写、调试和运行,并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性; 7.认真书写实验报告,并按时提交。
三﹑实验内容:
对顺序循环队列,常规的设计方法是使用対尾指针和对头指针,对尾指针用于指示当前的対尾位置下标,对头指针用于指示当前的対头位置下标。现要求:
(1)掌握栈和队列的特点,即后进先出和先进先出的原则。 (2)设计一个使用对头指针和计数器的顺序循环队列抽象数据类型,其中操作包括:初始化,入队列,出队列,取对头元素和判断队列是否为空;
(3)编写主函数进行测试。
四﹑实验步骤与程序
#include #include #include
} Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode)); if(!Q.rear) exit(OVERFLOW); Q.front->next=NULL; return OK; void QueueEmpty(LinkQueue Q) {
} void EnQueue(LinkQueue &Q,int e) {
} int EnnQueue(LinkQueue &Q,int e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) printf(\"error\"); if(Q.front==Q.rear) printf(\"该链队为空:\"); else printf(\"该链队不为空:\"); p->data=e; Q.rear->next=p; Q.rear=p; printf(\"元素%d入队成功\",e);
} if(!p) return ERROR; p->data=e; Q.rear->next=p; Q.rear=p;
return OK; void DeQueue(LinkQueue &Q) {
} void GetHead(LinkQueue &Q) { QueuePtr p; QueuePtr p; if(Q.front==Q.rear) printf(\"该链队为空\"); p=Q.front->next; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); printf(\"队首元素删除成功\");
} if(Q.front==Q.rear) printf(\"该链队为空\"); p=Q.front->next; printf(\"队首元素为:%d\",p->data); void OutQueue(LinkQueue &Q) {
} void LengthQueue(LinkQueue &Q) {
int f=0; QueuePtr p; if(Q.front==Q.rear) QueuePtr p; if(Q.front==Q.rear) printf(\"该链队为空\"); p=Q.front->next; while(p!=Q.rear->next) {
} printf(\"%d%,\",p->data); p=p->next;
} printf(\"该队列的长度为:%d\",f); else {
} p=Q.front->next; while(p!=Q.rear->next) {
} printf(\"该队列的长度为:%d\",f); p=p->next; f++; void main() {
system(\"cls\"); int flag=1,i; LinkQueue Q; InitQueue(Q); printf(\"************************链队列功能菜单***********************\\n\"); printf(\"1:初始化链队列,
2:判断链队列是否为空, 3:进入队列,
4:取出队首元素\\n\"); printf(\"5:输出该队列的所有元素,6:输出该队列的长度,
7:结束程序,
8:清屏\\n\");
while(flag) {
printf(\"\\n请输入操作符:\"); scanf(\"%d\",&i); switch(i) { case 1:
int e,n,k; printf(\"请输入队列的长度:\"); scanf(\"%d\",&n); printf(\"请输入队列的元素:\"); for(e=1;e
} printf(\"初始化链队成功\"); break; scanf(\"%d\",&k); EnnQueue(Q,k); case 2: QueueEmpty(Q);
break; case 3:
int j; printf(\"请输入要进入队列的元素\"); scanf(\"%d\",&j); EnQueue(Q,j); break; case 4: GetHead(Q); break; case 5:
printf(\"该队列的元素为:\"); OutQueue(Q); break;
case 6: LengthQueue(Q); break; case 7: flag=0; break; case 8: system(\"cls\"); } break;
} } 五﹑实验结果
六﹑实验心得体会:
程序主要构造了主函数main()和 InitQueue(),QueueEmpty ()EnQueue(),OutQueue()等调用函数,实现了队列的创立,队列是否为空的判断,入队和出队等功能。
通过此次实验,加深了对队列的存储结构的了解,同时也对程序设计能力有了提高,加深了对队列先进先出性质的理解,它允许在表的一端进行插入,在另一端删除元素,这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。 我们往往写不出程序,这其中的原因我觉得是对程序的结构不是很了解,对实验的内容也不熟练的结果,数据结构给我们许多程序的算法和模型,对我们写程序的思维有很大的锻炼,我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题,从而达到提升写程序的能力。
数据结构上机实验报告
3 一﹑实验名称:
实验三—二叉树的遍历
二﹑实验目的:
1、熟悉二叉树的结构特性,了解相应的证明方法;
2、掌握二叉树的生成,掌握二叉树的定义和存储表示,学会建立一棵特定二叉树的方法;
3、理解二叉树的三种遍历方法:先序遍历、中序遍历和后序遍历;
4、学会编写实现树的各种操作的算法。
二、实验内容:
1、使用类定义实现二叉树,补充完整所缺的函数,并实现创建和遍历二叉树的基本操作;
2、编程实现在二叉链表这种存储方式下,实现二叉的遍历,可采用递归或者非递归实现,遍历算法为在先序、中序和后序遍历算法。
三、实验步骤与程序:
#include #include #include typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;//定义结点类型 BiTree CreateBiTree()//创建树 { char p;BiTree T; scanf(\"%c\",&p); if(p==\' \') T=NULL; else { T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间 T->data=p; T->lchild=CreateBiTree(); T->rchild=CreateBiTree(); } return (T); }
void PreOrder(BiTree T)//先序 { if(T!=NULL) { printf(\"%c\",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T)//中序 { if(T!=NULL) { InOrder(T->lchild); printf(\"%c\",T->data); InOrder(T->rchild); } } void PostOrder(BiTree T)//后序 { if(T!=NULL) { PostOrder(T->lchild); PostOrder(T->rchild); printf(\"%c\",T->data); } } void main()//主函数 {
printf(\"------------二叉树的遍历-------------\\n\"); printf(\"请输入要遍历的数:\"); BiTree Ta; Ta=CreateBiTree(); printf(\"先序遍历:\"); printf(\"\\n\"); PreOrder(Ta); printf(\"\\n\"); printf(\"中序遍历:\"); printf(\"\\n\"); InOrder(Ta); printf(\"\\n\"); printf(\"后序遍历:\"); printf(\"\\n\"); PostOrder(Ta); } 五﹑实验结果
六﹑实验心得体会:
实验的程序设计规划(实现的功能、分几个模块、子函数) (1) 先序遍历递归算法函数:void PreOrder(BiTree T) (2) 中序遍历递归算法函数:void InOrder(BiTree T) (3) 后续遍历递归算法函数:void PostOrder(BiTree T) (4) 主函数的实现:void main()
在实验前我认真阅读关于二叉树的实现的内容,为编程实现第一步,本次实验通过按上述的实验步骤一步步实现的,实验过程中出现了一些错误,经过一步步的调试,修改错误,得到了二叉树的遍历用递归运算的方法的程序。通过这个实验,我体会到了理解数据结构的重要性,这有真正理解了定义数据类型的好处,才能用好这样一种数据结构。二叉树的先序,中序与后序的输出都用了递归的算法,而且用起来不是很复杂,这使我更进一步理解了函数递归调用并得到灵活运用;在实现算法上,从算法的效率看,递归方法书写形式较为简洁,更为直观,一般具有较好的空间效率。
总之,不管做什么实验,我们在做实验前都要先预习,对所做的实验有较深的理解,在做实验的时候需要很严谨,仔细的查找错误,从而能在实验中收获知识,提升自己。
数据结构上机实验报告4 一﹑实验名称:
实验四—查找
二﹑实验目的:
1、熟悉掌握顺序表的查找方法;
2、熟练掌握二叉排序树的构造方法和查找算法
3、掌握描述查找过程的判定树的构造方法,以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度;
4、学会定义线性表的储存类型,实现C++程序的基本结构对线性表的一些基本操作和具体的函数定义;
5、掌握顺序表的基本操作,实现顺序表的查找的等基本运算;
6、掌握对于多函数程序的输入,编辑,调试和运算过程。
二、实验内容:
1、实现顺序表的查找算法
2、关于衡量查找的主要操作—查找的查找平均效率的平均长度的讨论。
三、实验步骤与程序:
#include #define MAX_SIZE 100 typedef struct{ int key; }element;
element list[MAX_SIZE];
int seqsearch(element list[],int searchnum,int num); int main() {
int i,num,searchnum,k;
printf(\"---------------数据结构查找实验-------------\\n\"); printf(\"请输入数据元素的个数:\"); scanf(\"%d\",&num); printf(\"请输入数据的元素:\\n\"); for(i=0;i
printf(\"请输入要查询的数据元素:\"); scanf(\"%d\",&searchnum); k=seqsearch(list,searchnum,num); if(k!=-1) { printf(\"所查询元素的下标为:\"); printf(\"%d\\n\",k); } else printf(\"查询元素不存在。\\n\"); } return 0; }
int seqsearch(element list[],int searchnum,int num) { int j;
list[num].key=searchnum;
for(j=0;list[j].key!=searchnum;j++) ; return j
六﹑实验心得体会:
实验的程序设计规划为先写一个主函数int main() ,再写一个查找的子函数int seqsearch(element list[],int searchnum,int num) ,主函数通过调用子函数的方法实现程序的设计。
所谓“查找”即为在一个众多的数据元素(或记录)的查找表中找出某个“特定的”数据元素(或记录),通过本次实验,我更进一步的了解数据结构程序实验设计实现算法的基本模型,和算法实现等基本内容,学会了顺序表的查找方法。
数据结构上机实验报告5 一﹑实验名称:
实验五—内部排序
二﹑实验目的:
1、通过实现下述实验内容,学习、实现、对比各种排序算法,掌握各种排序算法的优劣,以及各种算法使用的情况,并加以灵活应用。
2、掌握各种排序时间复杂度的分析方法。
二、实验内容:
1、插入排序:依次将待排序的序列中的每一个记录插入到先前排序好的序列中,直到全部记录排序完毕。
2、快速排序:首先选择一个基准,将记录分割为两部分,左支小于或等于基准,右支则大于基准,然后对两部分重复上述过程,直至整个序列排序完成。
3、讨论各种内部排序方法的基本思路,算法特点,排序过程及它们的时间复杂度的分析。
三、实验步骤与程序:
#include void main() {
} int x; void charu(); void kuaisu(); printf(\"----------内部排序---------\\n\"); printf(\"
1、插入排序:\\n\"); printf(\"
2、选择排序:\\n\"); printf(\"请根据序号选择:\"); scanf(\"%d\",&x); if(x==1) charu(); else kuaisu(); void charu() { int a[7],j,i,m;
printf(\"插入排序\\n\");
printf(\"请输入个您想排序的数据:\\n\");
for(i=0;i
for(j=1;j
{ m=a[j];
for(i=j-1;i>=0;i--)
{
if(a[i]
break;
else a[i+1]=a[i];
}
a[i+1]=m;
}
printf(\"排序成功:\");
for(i=0;i
printf(\" %d\",a[i]);
printf(\"\\n\"); } quick(int first,int end,int L[]) { int left=first,right=end,key;
key=L[first];
while(left
{ while((left=key))
right--;
if(left
L[left++]=L[right];
while((left
left++;
if(left
L[left]=key;
return left;
}
quick_sort(int L[],int first,int end)
{ int split;
if(end>first)
{ split=quick(first,end,L);
quick_sort(L,first,split-1);
quick_sort(L,split+1,end);
}
} void kuaisu() {
int a[7],i;
printf(\"快速排序\\n\");
printf(\"请输入个您想排序的数据:\\n\");
for(i=0;i
scanf(\"%d\",&a[i]);
quick_sort(a,0,9);
printf(\"排序成功:\");
for(i=0;i
printf(\" %d\",a[i]);
printf(\"\\n\"); } 五﹑实验结果:
六﹑实验心得体会:
排序的功能是将一个数据元素(或记录)的任意序列,从新排成按关键字有序的序列;直接插入排序的稳定性比快速排序高,且算法较简单。本次实验运用到的是插入排序和快速排序。
人人范文网 m.inrrp.com.cn 手机版