数据结构实验内容及代码.docx
- 文档编号:258408
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:26
- 大小:229.56KB
数据结构实验内容及代码.docx
《数据结构实验内容及代码.docx》由会员分享,可在线阅读,更多相关《数据结构实验内容及代码.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构实验内容及代码
数据结构实验内容及代码
实验内容和目的:
掌握几种基本的数据结构:
集合、线性结构、树形结构等在求解实际问题中的应用,以及培养书写规范文档的技巧。
学习基本的查找和排序技术。
让我们在实际上机中具有编制相当规模的程序的能力。
养成一种良好的程序设计风格。
实验教材:
数据结构题集(C语言版)清华大学出版社2007年
实验项目:
实验一、栈和循环队列
㈠、实验内容:
1栈
掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等,栈的顺序存储结构和链式存储结构,以便在实际问题背景下灵活应用。
本程序采用的是链栈结构,具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。
2循环队列
掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等,学会循环队列的实现,以便在实际问题背景下灵活运用。
本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。
㈡、实验代码
1栈
程序代码:
#include
#include
#defineStack_Size6
#defineERROR0
#defineOK1
typedefintSElemType;
typedefstructSNode
{
SElemTypedata;
structSNode*next;
}SNode,*LinkStack;
intCreatTwo(LinkStack&head,intn)
{
inti;
SNode*p;
head=(LinkStack)malloc(sizeof(SNode));
head->next=NULL;
printf("请输入数据(数字):
\n");
for(i=n;i>0;--i)
{
p=(SNode*)malloc(sizeof(SNode));
scanf("%d",&p->data);
p->next=head->next;
head->next=p;
}
return1;
}
intmenu_select()
{
intsn;
for(;;)
{
scanf("%d",&sn);
if(sn<1||sn>6)
printf("\n\t输入错误,请重新输入\n");
else
break;
}
returnsn;
}
intPush(LinkStack&top,SElemTypee)
{
SNode*q;
q=(LinkStack)malloc(sizeof(SNode));
if(!
q)
{
printf("溢出!
\n");
return(ERROR);
}
q->data=e;
q->next=top->next;
top->next=q;
return(OK);
}
intPop(LinkStack&top,SElemType&e)
{
SNode*q;
if(!
top->next)
{printf("error!
\n");
return(ERROR);}
e=top->next->data;
q=top->next;
top->next=q->next;
free(q);
return(OK);
}
voidmain()
{inte;
LinkStacktop;
printf("1.初始化一个栈;\n2.PUSH;\n3.POP;\n4.显示所有栈里的元素;\n5.结束;\n");
while
(1)
{
switch(menu_select())
{
case1:
if(CreatTwo(top,Stack_Size))printf("Success!
\n");break;
case2:
printf("Push:
\n");
scanf("%d",&e);
if(Push(top,e))printf("Success!
\n");
break;
case3:
if(Pop(top,e))printf("Success!
\n");
printf("%d\n",e);
break;
case4:
LinkStackp;
printf("所有栈里的元素:
\n");
p=top;
while(p->next)
{p=p->next;
printf("%7d",p->data);
}
printf("\n");
break;
case5:
return;
}
}
}
运行结果:
2循环队列
程序代码:
#include
#include
#defineOVERFLOW-1
#defineOK1
#defineERROR0
#defineMAXSIZE100
typedefstruct
{
int*elem;//队列存储空间
intfront;
intrear;
}SqQueue;
//判断选择是否正确
intmenu_select()
{
intsn;
for(;;)
{
scanf("%d",&sn);
if(sn<1||sn>6)
printf("\n\t输入错误,请重新输入\n");
else
break;
}
returnsn;
}
//参数(传出)SqQueue&Q,循环队列(空)
intInitQueue(SqQueue&Q)
{
Q.elem=(int*)malloc(MAXSIZE*sizeof(int));
if(!
Q.elem)exit(OVERFLOW);
Q.front=Q.rear=-1;
for(inti=0;i Q.elem[i]=-1; returnOK; } //返回Q的元素个数 intQueueLength(SqQueueQ) { return(Q.rear-Q.front+MAXSIZE)%MAXSIZE; } //显示队列的元素 voidDisplay(SqQueueQ) { for(inti=0;i<=QueueLength(Q);i++) if(Q.elem[i]! =-1)printf("%d",Q.elem[i]); printf("\n"); } //入队 intEnQueue(SqQueue&Q,inte) { Q.rear=(Q.rear+1)%MAXSIZE; if(Q.rear==Q.front)returnERROR; Q.elem[Q.rear]=e; returnOK; } //出队 intDeQueue(SqQueue&Q,int&e) { if(Q.front==Q.rear)returnERROR; e=Q.elem[Q.front+1]; Q.elem[Q.front+1]=-1; Q.front=(Q.front+1)%MAXSIZE; returnOK; } voidmain() { SqQueueQ; InitQueue(Q); intelem,e; printf("请输入队列元素(以0结束): \n"); scanf("%d",&elem); while(elem! =0) { EnQueue(Q,elem); scanf("%d",&elem); } printf("队列为: \n"); Display(Q); printf("1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度: \n6.结束;\n"); while (1) { switch(menu_select()) { case1: printf("请输入队列元素(以0结束): \n"); scanf("%d",&elem); while(elem! =0) {EnQueue(Q,elem); scanf("%d",&elem);} printf("队列为: \n"); Display(Q); fflush(stdin); break; case2: scanf("%d",&elem); EnQueue(Q,elem); printf("队列为: \n"); Display(Q); fflush(stdin); break; case3: DeQueue(Q,elem); printf("队列为: \n"); Display(Q); break; case4: printf("\n队列的所有元素: \n"); Display(Q); break; case5: printf("%d\n",QueueLength(Q)); break; case6: return; } } } 运行结果: 实验二、数组 ㈠、实验内容: 数组一般不做插入或删除操作,也就是说,一旦建立了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动。 本程序数组的大小定义为3*3,可以通过修改“#defineM”来变动。 本程序具有矩阵相加、矩阵A转置、矩阵B转置、矩阵相乘四个功能。 ㈡、实验代码: #include #defineM3 voidMatrixAdd(intm1[M][M],intm2[M][M],intresult[M][M])//两个矩阵m1和m2相加,结果放到result { inti,j; for(i=0;i { for(j=0;j result[i][j]=m1[i][j]+m2[i][j]; } } voidMatrixTrams(intm1[M][M],intresult[M][M])//矩阵转置 { inti,j; for(i=0;i { for(j=0;j result[i][j]=m1[j][i]; } } voidMatrixMultiply(intm1[M][M],intm2[M][M],intresult[M][M]) { inti,j; for(i=0;i { for(j=0;j { result[i][j]=0; for(intk=0;k result[i][j]+=m1[i][k]*m2[k][j]; } } } voidDisplay(intresult[M][M])//显示矩阵 { inti,j; for(i=0;i { for(j=0;j printf("%-5d",result[i][j]); printf("\n"); } } voidmain() { intA[M][M],B[M][M]; inti,j; printf("请输入第一个矩阵: \n"); for(i=0;i for(j=0;j scanf("%d",&A[i][j]); printf("请输入第二个矩阵: \n"); for(i=0;i for(j=0;j scanf("%d",&B[i][j]); intresult[M][M]; /*printf("\n矩阵A: \n"); Display(A); printf("\n矩阵B: \n"); Display(B);*/ printf("请选择: \n1.矩阵相加: \n2.矩阵A转置: \n3.矩阵B转置: \n4.矩阵相乘: \n5.退出。 \n\n"); while (1) {intl; scanf("%d",&l); switch(l) { case1: printf("矩阵相加的运算结果: \n"); MatrixAdd(A,B,result); Display(result); printf("\n"); break; case2: printf("矩阵A转置的运算结果: \n"); MatrixTrams(A,result); Display(result); printf("\n"); break; case3: printf("矩阵B转置的运算结果: \n"); MatrixTrams(B,result); Display(result); printf("\n"); break; case4: printf("矩阵相乘的运算结果: \n"); MatrixMultiply(A,B,result); Display(result); printf("\n"); break; case5: printf("退出。 \n"); return; default: printf("输入错误! "); printf("\n"); } } } 实验结果: 实验三、查找 1、实验内容 掌握各种查找(顺序、二分法、查找树、哈希)方法及适用场合,并能在解决实际问题时灵活应用。 本实验采用二分查找。 二分查找又称折半查找,它是一种效率较高的查找方法。 折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。 因此,折半查找方法适用于不经常变动而查找频繁的有序列表。 本程序具有找出数据位置和显示查找次数两个功能。 ㈡、实验代码: #include #defineMAX100 voidmain() { intr[MAX],i,k,low,high,mid,m,n; printf("\n\n建立递增有序的查找顺序表(以-1结束): \n"); for(i=0;i { scanf("%d",&r[i]); if(r[i]==-1) { n=i; break; } } printf("\n请输入要查找的数据: \n"); scanf("%d",&k); low=0;high=n-1;m=0; while(low<=high) { mid=(low+high)/2; m++; if(r[mid]>k) high=mid-1; else if(r[mid] low=mid+1; else break; } if(low>high) { printf("没有找到\n"); printf("共进行%d次比较。 \n",m); if(r[mid] mid++; printf("可将这个数插入到第%d个数的后面。 \n",mid); } else { printf("\n要找的数据=%d在第%d个数的位置上。 \n",k,mid+1); printf("\n\n共进行了%d次比较。 \n",m); } } 实验结果: 实验四、树 1、实验内容: 进一步掌握树的结构及非线性特点,递归特点和动态性;进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入输出。 本程序将第一个元素作为树根,其余元素若小于树根则为左子树,若大于树根则为右子树。 本程序具有求左子树、求右子树、求深度、先序遍历、中序遍历(递归算法)、中序遍历(非递归算法)、后序遍历六个功能。 ㈡、实验代码 //描述: 两个指针指向左右孩子,算法见教材 #include #include #defineMAX50 typedefstructbtnode { intData; structbtnode*Llink; structbtnode*Rlink; }btnode,*btreetype; btreetypeCreatTree(intn)//传入数据数量,返回根结点指针 { inti; btreetyperoot=NULL; for(i=0;i { btreetypenewNode,currentNode,parentNode; newNode=(btreetype)malloc(sizeof(btnode)); scanf("%d",&newNode->Data); newNode->Llink=NULL; newNode->Rlink=NULL; currentNode=root; if(currentNode==NULL)root=newNode; else{ while(currentNode! =NULL) { parentNode=currentNode; if(newNode->Data currentNode=currentNode->Llink; else currentNode=currentNode->Rlink; } if(newNode->Data parentNode->Llink=newNode; else parentNode->Rlink=newNode; } } returnroot; } voidOutputTree(btreetype&root) { btreetypep; p=root->Llink; printf("建立的二叉树的左子树为: \n"); while(p! =NULL) { printf("%-8d",p->Data); p=p->Llink; } p=root->Rlink; printf("\n建立的二叉树的右子树为: \n"); while(p! =NULL) { printf("%-8d",p->Data); p=p->Rlink; } } intdepth(btreetyperoot) { btreetypep; p=root; intdep1; intdep2; if(root==NULL)return0; else { dep1=depth(p->Llink); dep2=depth(p->Rlink); if(dep1>dep2)return(dep1+1); elsereturn(dep2+1); } } voidPreOrder(btreetype&root)//先序遍历(递归) { btreetypep; p=root; if(p! =NULL) { printf("%-5d",p->Data); PreOrder(p->Llink); PreOrder(p->Rlink); } } voidInOrder(btreetype&root)//中序遍历(递归) { btreetypep; p=root; if(p! =NULL) { InOrder(p->Llink); printf("%-5d",p->Data); InOrder(p->Rlink); } } voidInOrder_Norecuision(btreetype&root) { btreetypestack[MAX]; btreetypep; inttop=0; p=root; do { while(p! =NULL) { top++; stack[top]=p; p=p->Llink; } if(top>0) { p=stack[top]; top--; printf("%-5d",p->Data); p=p->Rlink; } }while(p! =NULL||top! =0); } voidPostOrder(btreetype&root) { btreetypep; p=root; if(p! =NULL) { PostOrder(p->Llink); PostOrder(p->Rlink); printf("%-5d",p->Data); } } voidmain() { btreetypebtree; intcount; printf("请输入元素个数: \n"); scanf("%d",&count); printf("请输入数据: \n"); btree=CreatTree(count); OutputTree(btree); printf("\n建立的二叉树的深度为: %d\n",depth(btree)); printf("\n先序遍历: \n"); PreOrder(btree); printf("\n中序遍历(递归算法): \n"); InOrder(btree); printf("\n中序遍历(非递归算法): \n"); InOrder_Norecuision(btree); printf("\n后序遍历: \n"); PostOrder(btree); printf("\n"); } 实验结果:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 内容 代码
![提示](https://static.bingdoc.com/images/bang_tan.gif)