数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构实验报告
实验报告
实验项目：
线性表及其应用
实验学时：
2
实验日期：
实验要求：
熟悉并掌握单链表的存储及基本算法的使用
实验内容：
单链表就地逆置
程序代码如下：
#include"stdio.h"
#include"malloc.h"
typedefstructnode
{
intdata09;
structnode*next09;
}link;
link*creat（intn09）//创建链表
{
link*head09,*p09,*s09;
inti;
p09=head09=（link*）malloc（sizeof（link））;
for（i=1;i<=n09;i++）
{
s09=（link*）malloc（sizeof（link））;
scanf（"%d",&s09->data09）;
p09->next09=s09;
p09=s09;
}
p09->next09=NULL;
returnhead09;
}
voidreverse（link*head09）//原地置换
{
link*p09,*s09,*t09;
p09=head09;
s09=p09->next09;
while（s09->next09!
=NULL）//主要置换过程
{
t09=s09->next09;
s09->next09=p09;
p09=s09;
s09=t09;
}
s09->next09=p09;
head09->next09->next09=NULL;//收尾
head09->next09=s09;//赋头
}
voiddisplay（link*head09）//显示链表内容
{
link*p09;
p09=head09->next09;
while（p09!
=NULL）
{
printf（"%d",p09->data09）;
p09=p09->next09;
}
printf（"\n"）;
}
voidmain（）
{
link*head09;
head09=creat（5）;//创建一个5个节点的链表
printf（"原链表：
\n"）;
display（head09）;
reverse（head09）;
printf（"置换后链表：
\n"）;
display（head09）;
}
运行结果如下：
实验项目：
栈的应用
实验学时：
2
实验日期：
实验要求：
熟悉并掌握利用栈的特性进行相关运算
实验内容：
回文判断
程序代码如下：
#include
#include
#definenull0
#definemax50
typedefstructsn09{
chardata;
structsn09*next;
}node;
intishw（node*head,intn09）{
charstack[max];
inttop=0;
node*p09;
p09=head->next;
while（top{
stack[top]=p09->data;
top++;
p09=p09->next;
}
top--;
if（n09%2==1）p09=p09->next;//判断是否为回文数
while（top>=0）
{
if（stack[top]!
=p09->data）return0;
top--;
p09=p09->next;
}
return1;
}
intpush（node*head,char*s09）//将数据压入栈中
{
inti09;
node*p09,*q09;
p09=head;
for（i09=0;s09[i09]!
='\0';i09++）
{
q09=（node*）malloc（sizeof（node））;
q09->data=s09[i09];
q09->next=null;
p09->next=q09;
p09=q09;
}
return（i09）;
}
voidmain（）//输出判断结果
{
chars09[max];
node*head;
inti09;
printf（"Pleaseinputadata:
",max）;
scanf（"%s09",s09）;
head=（node*）malloc（sizeof（node））;
i09=push（head,s09）;
if（ishw（head,i09））
printf（"是回文数.\n"）;
else
printf（"不是回文数.\n"）;
}
运行结果如下：
实验项目：
数组的应用
实验学时：
4
实验日期：
实验要求：
熟悉并掌握矩阵压缩存储的算法
实验内容：
矩阵相加运算的实现
程序代码如下：
#include
#include
#defineMAXSIZE100//非零元素个数最大值
#defineOK1
typedefintElemType;
typedefintStatus;
typedefstruct{
inti09,j09;
ElemTypee;
}Triple;
typedefstruct{
Tripledata[MAXSIZE+1];
intmu09,nu09,tu09;
}TSMatrix;
StatusCreatSMatrix（TSMatrix&A09）
{//创建稀疏矩阵A
inti09,m09,n09;
ElemTypee;
printf（"请输入矩阵的行数，列数和非零元素个数（可用空格隔开）:
"）;
scanf（"%d",&A09.mu09）;scanf（"%d",&A09.nu09）;scanf（"%d",&A09.tu09）;
if（A09.tu09>MAXSIZE）
{printf（"非零元素个数太多请重新输入\n"）;exit（0）;}
A09.data[0].i09=0;
for（i09=1;i09<=A09.tu09;i09++）
{
printf（"请按行序输入第%d个非零元素所在行、列、元素的值:
",i09）;
scanf（"%d",&m09）;scanf（"%d",&n09）;scanf（"%d",&e）;
if（m09<1||m09>A09.mu09||n09<1||n09>A09.nu09）//行或列超出范围
{printf（"行或列超出范围请重新输入\n"）;exit（0）;}
if（m09//行或列的顺序有错
{printf（"行或列的顺序有错请重新输入\n"）;exit（0）;}
A09.data[i09].i09=m09;
A09.data[i09].j09=n09;
A09.data[i09].e=e;
}
returnOK;
}
Statuscomp（intc109,intc209）
{//比较行列的大小
if（c109return-1;
if（c109==c209）
return0;
return1;
}
StatusAddSMatrix（TSMatrixA09,TSMatrixB09,TSMatrix&C09）
{//求稀疏矩阵的和C=A+B
intm09=1,n09=1,q09=0;
if（A09.mu09!
=B09.mu09||A09.nu09!
=B09.nu09）//A、B两稀疏矩阵行或列数不同
{printf（"不满足矩阵相加的条件请重新输入\n"）;exit（0）;}
C09.mu09=A09.mu09;C09.nu09=A09.nu09;//矩阵C的行数和列数与矩阵A（矩阵B）相同
while（m09<=A09.tu09&&n09<=B09.tu09）
{
switch（comp（A09.data[m09].i09,B09.data[n09].i09））{
case-1:
C09.data[++q09]=A09.data[m09++];
break;
case0:
//A、B矩阵当前行元素相等继续比较
switch（comp（A09.data[m09].j09,B09.data[n09].j09））{
case-1:
C09.data[++q09]=A09.data[m09++];
break;
case0:
//A、B矩阵当前非零元素的行列均相等
C09.data[++q09]=A09.data[m09++];
C09.data[q09].e+=B09.data[n09++].e;//矩阵A、B当前元素求和并赋值给矩阵C
if（C09.data[q09].e==0）//元素值不存入压缩矩阵
q09--;
break;
case1:
C09.data[++q09]=B09.data[n09++];//将矩阵B当前元素赋值给矩阵C
}
break;
case1:
C09.data[++q09]=B09.data[n09++];
}
}
while（m09<=A09.tu09）
C09.data[++q09]=A09.data[m09++];
while（n09<=B09.tu09）
C09.data[++q09]=A09.data[n09++];
C09.tu09=q09;
if（q09>MAXSIZE）//非零元素个数太多
{printf（"非零元素个数太多请重新输入\n"）;exit（0）;}
returnOK;
}
StatusPrintSMatrix（TSMatrix&A09）
{//输出稀疏矩阵A
inti09;
printf（"共%d行%d列%d个非零元素\n",A09.mu09,A09.nu09,A09.tu09）;
printf（"行列元素值\n"）;
for（i09=1;i09<=A09.tu09;i09++）
printf（"%d%d%d\n",A09.data[i09].i09,A09.data[i09].j09,A09.data[i09].e）;
returnOK;
}
intmain（）//输入矩阵A、B,输出矩阵C
{
TSMatrixA09,B09,C09;
printf（"输入矩阵A\n"）;
CreatSMatrix（A09）;
printf（"输入矩阵B\n"）;
CreatSMatrix（B09）;
AddSMatrix（A09,B09,C09）;
printf（"输入矩阵A和B的和:
\n"）;
PrintSMatrix（C09）;
returnOK;
}
运行结果如下：
实验项目：
树的应用
实验学时：
2
实验日期：
实验要求：
熟悉并掌握建立树及利用二叉树遍历算法进行其他操作
实验内容：
二叉树的叶子结点计算
程序代码如下：
#include
#include
structBiTree{
chardata;
structBiTree*lchild;
structBiTree*rchild;
};//二叉树的结构体
structBiTree*CreatBiTree（）{//创建二叉树的函数
charx09;
structBiTree*p09;
scanf（"%c",&x09）;
if（x09!
=''）
{
p09=（structBiTree*）malloc（sizeof（structBiTree））;
p09->data=x09;
p09->lchild=CreatBiTree（）;
p09->rchild=CreatBiTree（）;
}
else
p09=NULL;
returnp09;
}
intLeafNum（structBiTree*T09）
{//计算二叉树中叶子结点的个数
if（!
T09）
return0;
else
if（!
T09->lchild&&!
T09->rchild）
return1;
else
returnLeafNum（T09->lchild）+LeafNum（T09->rchild）;
}
intmain（）
{
intnum09;
structBiTree*T09;
printf（"请输入二叉树的元素:
\n"）;
T09=CreatBiTree（）;//创建二叉树
while（T09==NULL）
{
printf（"empoty,again:
\n"）;
T09=CreatBiTree（）;
}
num09=LeafNum（T09）;
printf（"二叉树叶子结点数目位:
%d\n",num09）;
return0;
}
运行结果如下：
实验项目：
图的应用
实验学时：
2
实验日期：
实验要求：
熟悉并掌握图的构造算法的使用
实验内容：
有向图的邻接表存储
程序代码如下：
#include
constintMAX_SIZE=20;
typedefstructArcNode
{
intadjvex09;
intvalue09;
structArcNode*nextarc09;
};
typedefstructVNode
{
intdata09;//
ArcNode*firstarc;//邻接表表头指针
}VNode,AdjList[MAX_SIZE];
typedefstruct
{
AdjListvertices;//邻接表数组
intvexnum09,arcnum09;//顶点数和边数
}ALGraph;
voidCreateALGraph（ALGraph&algraph）//创建图函数
{
inti,head09,tail09,value09;
ArcNode*p09,*q09;
printf（"输入顶点数:
"）;
scanf（"%d",&algraph.vexnum09）;
printf（"输入边数:
"）;
scanf（"%d",&algraph.arcnum09）;
//初始化图
for（i=0;i{
algraph.vertices[i].data09=i;
algraph.vertices[i].firstarc09=NULL;
}
printf（"输入边集:
（headtailvalue）\n"）;
for（i=0;i{
scanf（"%d%d%d",&head09,&tail09,&value09）;
//生成新节点
p09=newArcNode;
p->adjvex09=tail09;
p->value09=value09;
if（algraph.vertices[head09].firstarc09==NULL）//表头为空
{
algraph.vertices[head09].firstarc09=p;
p->nextarc09=NULL;
}
else//表头非空
{p->nextarc09=algraph.vertices[head09].firstarc09;
algraph.vertices[head09].firstarc09=p09;
}
}//endfor
};
voidPrintALGraph（constALGraph&algraph）//输出图
{
for（inti=0;i{
printf（"顶点V%d的边集:
{",algraph.vertices[i].data09）;
ArcNode*p09=algraph.vertices[i].firstarc09;//用p指向每个顶点边集的表头指针
boolfirst=true;
while（p09!
=NULL）
{
if（!
first）//输出格式控制
printf（","）;
else
first=false;
printf（"<%d,%d>%d",algraph.vertices[i].data09,p->adjvex09,p->value09）;
p09=p09->nextarc09;//指向下个节点
}
printf（"}\n\n"）;
}
}
intmain（）
{
ALGraphalgraph1,algraph2;
CreateALGraph（algraph1）;
PrintALGraph（algraph1）;
return0;
}
运行结果如下：
实验项目：
查找和排序算法应用
实验学时：
4
实验日期：
实验要求：
熟悉并掌握查找和排序算法的使用
实验内容：
对某字符串进行排序，并在此基础上利用查找算法进行查找
程序代码如下：
#include//头文件
intmain（）
{
intisearch（inta[],intn09,intx09）;//函数声明
voidsort（inta[],intn09）;
intx09,n09;
inta[10],i;
printf（"enterarray:
\n"）;
for（i=0;i<10;i++）
scanf（"%d",&a[i]）;
sort（a,10）;//选择排序
printf（"输入要查找的数:
"）;
scanf（"%d",&x09）;//输入数据
n=isearch（a,x09,n09）;//折半查找
printf（"Thesortedarray:
\n"）;
for（i=0;i<10;i++）
{printf（"%d",a[i]）;}//输出
printf（"\n"）;
if（n09<0）//输出查找结果.
{printf（"没找到数据:
%d\n",x09）;}
else
{printf（"数据:
%d位于数组的第%d个元素处.\n",x09,n09+1）;}
return0;
}
voidsort（inta[],intn09）
{
inti,j,k,t09;
for（i=0;i{k=i;
for（j=i+1;jif（a[j]k=j;
t09=a[k];a[k]=a[i];a[i]=t09;
}
}
intisearch（inta[],intx,intn）//折半查找
{
intmid,low09,high09;
low09=0;
high09=9;
while（low09<=high09）
{mid=（low09+high09）/2;
if（a[mid]==x09）
returnmid;
elseif（a[mid]>x09）
high09=mid-1;
else
low09=mid+1;}
return-1;
}
运行结果如下：
实验总结
升级会员 