数据结构与算法实验报告.docx
《数据结构与算法实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构与算法实验报告.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构与算法实验报告
数据结构实验报告
题目：
线性表
班级：
网络工程1401班
学号：
1408020106
指导教师：
高峰
日期：
2016/7/6
实验一：
线性表
一：
实验要求
掌握数据结构中线性表的基本概念。
熟练掌握线性表的基本操作：
创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构撒谎能够的实验。
熟练掌握链表的各种操作和应用。
二．实验内容
1.编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。
2.编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。
三：
实验过程及步骤
源代码：
#include
#include
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
typedefstruct{
int*elem;
intlength;
intlistsize;
}SqList;
//SqListsq;
voidInitList_Sq（SqList*sq）//初始化列表
{
sq->elem=（int*）malloc（LIST_INIT_SIZE*sizeof（int））;
sq->length=0;
sq->listsize=LIST_INIT_SIZE;
printf（"---申请空间成功---!
\n"）;
}
voidGetElem（SqList*sq,inti）//获取第i位置元素的值
{
int*p;
p=&（sq->elem[i-1]）;
printf（"%d",*p）;
printf（"\n"）;
}
intListInsert_Sq（SqList*sq,inti,inta）//在i位置之前插入a
{
int*p,*q;
if（i<=0||i>sq->length+1）
{
printf（"---位置不合法---!
\n"）;
return0;
}
if（sq->length>=sq->listsize）
{
int*newbase=（int*）realloc（sq->elem,（sq->listsize+LISTINCREMENT）*sizeof（int））;
if（!
newbase）
{
printf（"申请空间溢出\n"）;
return0;
}
sq->elem=newbase;
sq->listsize+=LISTINCREMENT;
}
p=&（sq->elem[i-1]）;//p指向第i位置的元素
q=&（sq->elem[sq->length-1]）;//q指向最后一个元素
for（;q>=p;--q）*（q+1）=*q;
*p=a;
++sq->length;
return1;
}
intListDelete_Sq（SqList*sq,inti）//删除i位置上的值
{
int*p,*q;
if（i<1||i>sq->length）return0;
p=&（sq->elem[i-1]）;//p指向第i位置的元素
q=sq->elem+sq->length-1;//q指向最后一个元素
for（++p;p<=q;++p）
{
*（p-1）=*p;
}
--sq->length;
return1;
}
voidvisit（SqList*sq）//输出数据
{
inti=1;
for（;i<=sq->length;i++）
{
int*p;
p=&sq->elem[i-1];
printf（"%d",*p）;
printf（""）;
}
}
voidmain（）
{
inti=1,a=0,boo=1,number=0;
SqLists,*sq;
sq=&s;
InitList_Sq（sq）;
printf（"初始化空表\n"）;
printf（"输入数据个数：
\n"）;
scanf（"%d",&number）;
printf（"输入%d个数据：
",number）;
printf（"\n"）;
for（;i<=number;i++）
{
scanf（"%d",&a）;
if（boo=ListInsert_Sq（sq,i,a））
{
printf（"---插入成功！
---\n"）;
}
else
{
printf（"---插入不成功,重新插入---！
\n"）;
i=i-1;
}
}
printf（"输出所有元素\n"）;
visit（sq）;
printf（"\n"）;
printf（"输出删除的位置:
"）;
scanf（"%d",&a）;
if（boo=ListDelete_Sq（sq,a））
{
printf（"---数据删除成功！
---\n"）;
}else
{
printf（"---没有删除成功---\n"）;
}
printf（"输出所有元素:
\n"）;
visit（sq）;
printf（"\n"）;
printf（"输出要显示数据的位置：
"）;
scanf（"%d",&a）;
printf（"输出%d位置数值\n",a）;
if（a<0||a>sq->length）
{
printf（"---输出位置的数据不存在---\n"）;
}
else
{
GetElem（sq,a）;
}
}
步骤：
1.初始化空表
2.顺序插入数据后输出所有元素
3.选择删除位置，删除数据后输出所有元素
4.选择查看的数据位置，输出选择查看的数据
四：
实验结果及分析
分析：
本程序在实现顺序存储插入以及删除i个元素开始的k个元素删除（数据类型为整型）。
之外在删除、查看是实时输出结果，并且可以查看希望显示数据的位置。
数据结构实验报告
题目：
树
班级：
网络工程1401班
学号：
1408020106
指导教师：
高峰
日期：
2016/7/6
实验二：
树
一：
实验要求
掌握二叉树，二叉树排序数的概念和存储方法。
掌握二叉树的遍历算法。
熟练掌握编写实现树的各种运算的算法。
二．实验内容
统计一棵二叉树中每种类型节点数（度为0/1/2的节点数）。
三：
实验过程及步骤
#include
#include
#include
typedefstructBitNode{
intdata;
structBitNode*lchild,*rchild;
}BitNode,*BitTree;
BitTreeBitTreeInit（）{
BitTreeBT;
BT=（BitNode*）malloc（sizeof（BitNode））;
BT=NULL;
returnBT;
}
BitTreeBitTreeCreat（BitTree&BT）{
intch;
printf（"请输入节点的内容,输入0时结束建立！
\n"）;
scanf（"%d",&ch）;
if（ch==0）
BT=NULL;
else{
BT=（BitTree）malloc（sizeof（BitNode））;
BT->data=ch;
BitTreeCreat（BT->lchild）;
BitTreeCreat（BT->rchild）;
}
returnBT;
}
voidBitTreeEmpty（BitTreeBT）{
if（BT==NULL）
printf（"树为空！
\n"）;
else
printf（"树非空！
\n"）;
}
voidPreOrderTraverse（BitTreeBT）{
if（BT!
=NULL）{
printf（"树结点的内容为:
%d\n",BT->data）;
PreOrderTraverse（BT->lchild）;
PreOrderTraverse（BT->rchild）;
}
}
voidInOrderTraverse（BitTreeBT）{
if（BT!
=NULL）{
InOrderTraverse（BT->lchild）;
printf（"树结点的内容为:
%d\n",BT->data）;
InOrderTraverse（BT->rchild）;
}
}
voidPostOrderTraverse（BitTreeBT）{
if（BT!
=NULL）{
PostOrderTraverse（BT->lchild）;
PostOrderTraverse（BT->lchild）;
printf（"树结点的内容为:
%d\n",BT->data）;
}
}
intcount（BitTreeBT）{
if（BT==NULL）
return0;
else
return（count（BT->lchild）+count（BT->rchild）+1）;
}
intBinTreeDepth（BitTreeBT）{
inti=1,j=1;
if（BT==NULL）
return0;
else
{
i=BinTreeDepth（BT->lchild）;
j=BinTreeDepth（BT->rchild）;
if（i>j）
return（i+1）;
else
return（j+1）;
}
}
voidBinTreeClear（BitTree&BT）{
if（BT）{
if（BT->lchild）
BinTreeClear（BT->lchild）;
if（BT->rchild）
BinTreeClear（BT->rchild）;
free（BT）;
BT=NULL;
}
}
main（）{
inti=1,j,l;
BitTreeBT;
while（i!
=0）{
printf（"-----------------欢迎使用-------------------\n"）;
printf（"请选择要进行的操作\n"）;
printf（"1.初始化一棵树2.建立一棵树3.判断树是否为空\n"）;
printf（"4.按前序遍历树5.按中序遍历树6.按后序遍历树\n"）;
printf（"7.求树的深度8.求树的结点数9.把树清空\n"）;
printf（"0.退出操作界面\n"）;
printf（"-----------------谢谢使用-------------------\n"）;
scanf（"%d",&j）;
switch（j）{
case1:
BT=BitTreeInit（）;printf（"树已经初始化！
\n"）;break;
case2:
BitTreeCreat（BT）;break;
case3:
BitTreeEmpty（BT）;break;
case4:
PreOrderTraverse（BT）;break;
case5:
InOrderTraverse（BT）;break;
case6:
PostOrderTraverse（BT）;break;
case7:
l=BinTreeDepth（BT）;printf（"树的深度为：
%d\n",l）;break;
case8:
l=count（BT）;printf（"树的结点数为：
%d\n",l）;break;
case9:
BinTreeClear（BT）;printf（"树已经清空！
\n"）;break;
case0:
exit（0）;
}
}
}
步骤：
1.选择进行的操作
2.初始化、建立、判断树是否空、先/中/后序遍历、求深度/结点，清空树
3.显示结果
四：
实验结果及分析
分析：
本程序不仅可以统计一棵二叉树中每种类型节点数（度为0/1/2的节点数）。
同时让他有以下功能：
1.初始化一棵树。
2.建立一棵树。
3.判断树是否为空。
4.分别按先/中/后序遍历树。
5.求树的深度。
6.求树的结点数。
7.清空树。
升级会员 