数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告.docx（45页珍藏版）》请在冰点文库上搜索。
数据结构实验报告
《数据结构》实验报告
专业惠普测试
班级142班
姓名张建一
学号1408090219
学期2015-2016学年第一学期
指导老师刘勇
实验
1
2
3
4
总分
成绩
成绩：
教师评语：
数据结构上机实验报告
学号：
1408090219姓名：
张建一所在系：
信息学院班级：
惠普测试142
实验名称：
线性结构基本算法的实现实验日期
实验指导教师刘勇实验机房弘毅楼D410
------------------------------------------------------------------------------------------------------
1.实验目的：
（1）掌握线性表顺序存储结构的基本操作：
插入、删除、查找；
（2）掌握线性表链式结构的基本操作：
插入、删除、合并等运算；
（3）掌握栈和队列基本运算的算法；
（4）掌握稀疏矩阵的压缩存储的算法。
2.实验内容：
（1）实现顺序表的创建、插入、删除和查找的操作；
（2）实现单链表插入、删除、合并的操作；
（3）实现2个有序线性表的合并；
（4）利用顺序栈实现括号匹配的算法；
（5）实现顺序队列各种基本运算的算法；
（6）实现链栈各种基本运算的算法；（选做）
（7）实现链队列各种基本运算的算法；（选做）
（8）实现稀疏矩阵压缩存储的算法。
3．算法设计（编程思路或流程图或源代码）
内容：
1、顺序表的插入和删除
2、有序单链表的合并
3、数制转换的算法实现
1
#include
#include
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineTURE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintElemType;
typedefintStatus;
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
StatusInitList_Sq（SqList*L）
{
L->elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L->elem）returnOVERFLOW;
L->length=0;
L->listsize=LIST_INIT_SIZE;
returnOK;
}
StatusCreatList_Sq（SqList*L,intn）
{
inti;
L->length=n;
for（i=0;i{
printf（"请输入第%d个整数:
",i+1）;
scanf（"%d",&L->elem[i]）;
}
returnOK;
}
voidTraverList_Sq（SqList*L）
{
inti;
printf（"顺序表的长度为：
%d\n",L->length）;
printf（"顺序表中的元素依次为：
"）;
for（i=0;ilength;i++）
{
printf（"%5d",L->elem[i]）;
}
printf（"\n"）;
}
intListInsert_Sq（SqList*L,inti,inte）
{
int*newbase,*q,*p;
if（i<1||i>L->length+1）
{
printf（"由于插入位置不合法导致插入操作失败\n"）;
returnERROR;
}
else
{
if（L->length>=L->listsize）
{
newbase=（int*）realloc（L->elem,（L->listsize+LISTINCREMENT）*sizeof（int））;
if（!
newbase）returnOVERFLOW;
L->elem=newbase;
L->length=+LISTINCREMENT;
}
q=&（L->elem[i-1]）;
for（p=&L->elem[L->length];p>=q;p--）
*（p+1）=*p;
*q=e;
++L->length;
returnOK;
}
}
intDeleteList_Sq（SqList*L,inti,inte）
{
intx,*q,*p;
if（i<1||i>L->length）
{
printf（"由于删除位置不合法无法进行删除\n"）;
returnERROR;
}
elseif（L->length==0）
{
printf（"由于是空表无法删除\n"）;
returnOVERFLOW;
}
else
{
q=&（L->elem[i-1]）;
e=L->elem[i-1];
printf（"第%d个元素%d已删除\n",i,e）;
for（p=&（L->elem[L->length-1]）;q--L->length;
returnOK;
}
}
intmain（）
{
SqLista,*l=&a;
intselect,n,i,x,m,b;
do{
printf（"\n第一次使用初始化\n"）;
printf（"1初始化\n"）;
printf（"2顺序表的创建\n"）;
printf（"3顺序表的插入\n"）;
printf（"4顺序表的删除\n"）;
printf（"5顺序表的遍历\n"）;
printf（"0退出\n\n"）;
printf（"请选择操作1-5:
"）;
scanf（"%d",&select）;
switch（select）{
case1:
{
if（!
InitList_Sq（l））printf（"顺序表初始化失败\n"）;
InitList_Sq（l）;
printf（"顺序表已经初始化\n"）;
break;
}
case2:
{
printf（"请输入要创建的顺序表的长度：
"）;
scanf（"%d",&n）;
CreatList_Sq（l,n）;
TraverList_Sq（l）;
break;
}
case3:
{
printf（"请输入要插入的位置：
"）;
scanf（"%d",&i）;
printf（"请输入要插入的元素：
"）;
scanf（"%d",&x）;
ListInsert_Sq（l,i,x）;
TraverList_Sq（l）;
break;
}
case4:
{
printf（"请输入要删除的位置：
"）;
scanf（"%d",&m）;
DeleteList_Sq（l,m,b）;
TraverList_Sq（l）;
break;
}
case5:
{
TraverList_Sq（l）;
break;
}
}
}while（select<=5&&select>=1）;
return0;
}
2
#include
#include
typedefstructnode{
intdata;
structnode*next;
}node,*list;
voidinit（list&head）
{
head=（list）malloc（sizeof（node））;
head->next=NULL;
}
voidinput（list&h）
{
listp,q;
q=h;
printf（"输入数据的个数：
"）;
intn;
scanf（"%d",&n）;
printf（"请输入%d个有序递增的数据",n）;
for（inti=0;i{
p=（list）malloc（sizeof（node））;
scanf（"%d",&p->data）;
p->next=q->next;
q->next=p;
q=p;
}
}
voidoutput（listh）
{
listp;
p=h->next;
printf（"输出数据\n"）;
while（p!
=NULL）
{
printf（"%d",p->data）;
p=p->next;
}
}
voidcombine（list&a,list&b,list&c）
{
listp,q,t;
p=a->next;
q=b->next;
free（b）;
b=q;
c=a;
a=p;
c->next=NULL;
while（p&&q）
{
if（p->data<=q->data）
{
a=a->next;
p->next=c->next;
c->next=p;
p=a;
}
else
{
b=q->next;
q->next=c->next;
c->next=q;
q=b;
}
}
if（p!
=NULL）
{
while（p）
{
a=a->next;
p->next=c->next;
c->next=p;
p=a;
}
}
if（q!
=NULL）
{
while（q）
{
b=q->next;
q->next=c->next;
c->next=q;
q=b;
}
}
}
intmain（）
{
lista,b,c;
init（a）;init（b）;
printf（"输入链表A:
\n"）;
input（a）;
printf（"输入链表B:
\b"）;
input（b）;
combine（a,b,c）;
output（c）;
return0;
}
3
#include
voidfun（intx,intk）;
intmain（）
{
intn;
printf（"你要测试几组数据?
"）;
scanf（"%d",&n）;
printf（"请输入%d组数据（输入格式:
ab）:
\n",n）;
inti,k,x;
for（i=0;i{
scanf（"%d%d",&x,&k）;
printf（"十进制数%d的%d进制表示是:
",x,k）;
fun（x,k）;printf（"\n"）;
}
return0;
}
voidfun（intx,intk）
{
inta,b,c=0,zu[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
b=x;
do{
a=b%k;
zu[c]=a;
c++;
b=b/k;
}while（b>0）;
for（--c;c>=0;--c）
{
if（zu[c]!
=-1&&zu[c]>9）
{
printf（"%c",zu[c]+（'A'-10））;
}
else
{
printf（"%d",zu[c]）;
}
}
}
4.程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。
或对其他程序环境的使用情况的记录。
注：
必须认真书写）
1
2
3
5.讨论（通过实验的一些体会、学会的知识和技能等）
1、线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素
2、线性链表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素
数据结构上机实验报告
学号：
1408090219姓名：
张建一所在系：
信息学院班级：
惠普测试142
实验名称：
二叉树的基本应用实验日期
实验指导教师刘勇实验机房D410
------------------------------------------------------------------------------------------------------
2.实验目的：
（1）理解树这种数据结构。
（2）掌握二叉树二叉链表这种存储结构。
（3）完成二叉树各种基本运算的算法。
2.实验内容：
（1）实现二叉树创建的算法。
（2）实现二叉树各种遍历算法。
（3）实现二叉树其他操作的算法，包括：
统计叶子结点的个数、求二叉树的深度、线索二叉树等。
3．算法设计（编程思路或流程图）
1、二叉树创建的算法
2、叶子结点统计的算法
3、二叉树深度统计算法
1#include
#include
#include
#defineMAX20
#defineOK1
#defineERROR0
#defineOVERFLOW0
typedefcharTElemType;
typedefintStatus;
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
BiTreeCreateBiTree（BiTreeT）
{
charch;
scanf（"%c",&ch）;
if（ch=='#'）T=NULL;
else{
T=（BiTNode*）malloc（sizeof（BiTNode））;
if（!
T）exit（OVERFLOW）;
T->data=ch;
T->lchild=CreateBiTree（T->lchild）;
T->rchild=CreateBiTree（T->rchild）;
}
returnT;
}
voidLevelOrder（BiTreeT）
{
BiTreeQueue[MAX],b;
intfront,rear;
front=rear=0;
if（T）{
Queue[rear++]=T;
while（front!
=rear）{
b=Queue[front++];
printf（"%2c",b->data）;
if（b->lchild!
=NULL）Queue[rear++]=b->lchild;
if（b->rchild!
=NULL）Queue[rear++]=b->rchild;
}
}
}
主函数
#include"BiTNode.h"
intmain（）
{
BiTreeT=NULL;
printf（"*******采用递归函数构造一棵二叉树*******\n"）;
printf（"请读入构造二叉树的字符序列:
"）;
if（T=CreateBiTree（T））{
printf（"二叉树建立成功!
并以层序遍历输出构造的二叉树\n"）;
LevelOrder（T）;
printf（"\n"）;
}
elseprintf（"很遗憾，不能成功建立二叉树！
！
！
\n"）;
return0;
}
2
#include
#include"BiTNode.h"
intleafcount（BiTreebt）
{
intn;
if（bt==NULL）return0;
elseif（（bt->lchild==NULL）&&（bt->rchild==NULL））n=1;
elsen=leafcount（bt->lchild）+leafcount（bt->rchild）;
returnn;
}
intmain（）
{
BiTreeT=NULL;
intm;
printf（"*******构造一颗二叉树并统计叶子结点的数*******\n"）;
printf（"请输入二叉树的序列:
"）;
T=CreateBiTree（T）;
if（T）
{
printf（"二叉树建立成功！
以层序遍历输出构造的二叉树\n"）;
LevelOrder（T）;
m=leafcount（T）;
printf（"\n该二叉树的叶子结点数目是:
%d\n",m）;
}
elseprintf（"二叉树建立不成功！
\n"）;
return0;
}
3#include
#include"BiTNode.h"
intdepth（BiTreebt）;
intmain（）
{
BiTreeT=NULL;
printf（"*******构造一颗二叉树并统计深度*******\n"）;
printf（"请输入二叉树的序列:
"）;
T=CreateBiTree（T）;
if（T）
{
printf（"二叉树建立成功！
以层序遍历输出构造的二叉树\n"）;
LevelOrder（T）;
intm=depth（T）;
printf（"\n该二叉树的深度是:
%d\n",m）;
}
elseprintf（"二叉树建立不成功！
\n"）;
return0;
}
intdepth（BiTreebt）
{
if（bt==NULL）return0;
else
{intdm=depth（bt->lchild）;
intdn=depth（bt->rchild）;
returndm>dn?
dm+1:
dn+1;
}
}
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。
或对其他程序环境的使用情况的记录。
注：
必须认真书写）
1
2
3
5．讨论（通过实验的一些体会、学会的知识和技能等）
1、树形结构是一类重要的非线性数据结构。
二叉树的特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分次序不能任意颠倒
2、二叉树的性质：
（1）在二叉树的第i层上至多有2^i-1个结点（i>=1）
（2）深度为K的二叉树至多有2^k-1个结点（k>=1）
（3）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2则n0=n2+1
（4）具有n个结点的完全二叉树的深度为log2n+1
数据结构上机实验报告
学号：
1408090219姓名：
张建一所在系：
信息学院班级：
惠普测试142
实验名称：
图的基本实现与应用实验日期
实验指导教师刘勇实验机房D410
------------------------------------------------------------------------------------------------------
3.实验目的：
（1）理解图这种数据结构。
（2）掌握邻接矩阵、邻接表这种存储结构的实现方法。
（3）完成图的遍历的算法。
2.实验内容：
（1）实现图的邻接矩阵与邻接表结构的转换。
（必做）
（2）实现图遍历的算法。
（必做）
（3）实现图的拓扑排序的算法。
（4）实现图的最短路径的算法
3．算法设计（编程思路或流程图）
1、图的邻接矩阵和邻接表创建的算法
2、图的两种遍历算法
1
#defineVERTEXTYPEint
#defineADJTYPEint
#defineMAXLEN40
#include
#include
typedefstruct{
VERTEXTYPEvexs[MAXLEN];
ADJTYPEarcs[MAXLEN][MAXLEN];
intvexnum,arcnum;
intkind;
}MGRAGH;
typedefstructnode3{
intadjvex;
structnode3*next;
}EDGENODE;
typedefstruct{
VERTEXTYPEvertex;
EDGENODE*link;
intid;
}VERTEXNODE;
typedefstruct{
VERTEXNODEadjlist[MAXLEN];
intvexnum,arcnum;
intkind;
}ADJGRAGH;
MGRAGHcreate_MGRAGH（）
{
inti,j,k;
MGRAGHmg;
mg.kind=2;
printf（"\n\ninputvertexnumandarcnum（,）:
"）;
scanf（"%d,%d",&i,&j）;fflush（stdin）;
mg.vexnum=i;
mg.arcnum=j;
printf（"\n\n"）;
for（i=0;i{
printf（"inputthevalueofvertex%d:
",i+1）;
scanf（"%d",&mg.vexs[i]）;fflush（stdin）;
}
for（i=0;i
升级会员 