数据结构实验报告.docx

数据结构实验报告.docx

《数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告.docx（16页珍藏版）》请在冰点文库上搜索。

数据结构实验报告

管理学院实验报告

实验课程名称：

 数据结构与算法               

实验地点：

   经济管理教学实验中心             

年 月至 年 月     

专  业            

班  级            

学生姓名            

学  号　           

指导老师            

实验报告

实验项目：

线性表及其应用

实验学时：

2

实验日期：

实验要求：

熟悉并掌握单链表的存储及基本算法的使用

实验内容：

单链表就地逆置

#include"conio.h"

#include"stdlib.h"

#definemsizeof（structLnode）

typedefstructLnode{

intdata;

structLnode*next;

};

structLnode*LinkList;

structLnode*p,*q,*head;

intn;

voidbuild（）

{

inti;

head=（structLnode*）malloc（m）;

p=head;

for（i=1;i<4;i++）

{

p->data=i;

p->next=（structLnode*）malloc（m）;

p=p->next;

}

p->data=4;

p->next=NULL;

}

voiddisplay（）

{

p=head;

while（p->next!

=NULL）

{

printf（"%d",p->data）;

p=p->next;

}

printf（"%d",p->data）;

}

voidJiudi（）

{

structLnode*p,*q,*r;

p=head;

q=p->next;

while（q!

=NULL）

{

r=q->next;

q->next=p;

p=q;

q=r;

}

head->next=NULL;

head=p;

}

voidmain（）

{

build（）;

display（）;

Jiudi（）;

printf（"\n"）;

display（）;

getch（）;

}

实验项目：

栈的应用

实验学时：

2

实验日期：

实验要求：

熟悉并掌握利用栈的特性进行相关运算

实验内容：

回文判断

#include

#include

#defineINIT_SIZE100

typedefstructStack

{

int*base[2];

int*top[2];

intstacksize;

}SqStack;

voidinitStack（SqStack&s）

{

inti;

s.base[0]=（int*）malloc（INIT_SIZE*sizeof（SqStack））;

if（s.base[0]==NULL）

{

exit（0）;

}

s.base[1]=s.base[0];

for（i=0;i<100;i++）

s.base[1]++;

s.base[1]--;

s.top[0]=s.base[0];

s.top[1]=s.base[1];

s.stacksize=INIT_SIZE;

}

voidpush（SqStack&s,inti,intx）

{

if（i==0）

{

if（s.top[0]-s.base[0]>=s.stacksize||s.top[0]>=s.top[1]）

{

exit（0）;

}

*（s.top[0]++）=x;

}

else

{

if（s.base[1]-s.top[1]>=s.stacksize||s.top[0]>=s.top[1]）

{

exit（0）;

}

*（s.top[1]--）=x;

}

}

intpop（SqStack&s,inti,intx）

{

if（i==0）

{

if（s.top[0]-s.base[0]==0）

{

exit（0）;

}

x=*--s.top[0];

}

else

{

if（s.top[1]-s.base[1]==0）

{

exit（0）;

}

x=*++s.top[1];

}

returnx;

}

intmain（）

{

inti,num,n;

SqStacks;

initStack（s）;

printf（"请输入要在0号栈中插入的数的个数:

"）;

scanf（"%d",&n）;

for（i=0;i

{

printf（"请输入要插入的第%2d个数:

",i+1）;

scanf（"%d",&num）;

push（s,0,num）;

}

printf（"请输入要在1号栈中插入的数的个数:

"）;

scanf（"%d",&n）;

for（i=0;i

{

printf（"请输入要插入的第%2d个数:

",i+1）;

scanf（"%d",&num）;

push（s,1,num）;

}

printf（"请输入要在0号栈中删除的数的个数:

"）;

scanf（"%d",&n）;

for（i=0;i

{

num=pop（s,0,num）;

printf（"删除的第%2d个数:

%4d\n",i+1,num）;

}

printf（"请输入要在1号栈中删除的数的个数:

"）;

scanf（"%d",&n）;

for（i=0;i

{

num=pop（s,1,num）;

printf（"删除的第%2d个数:

%4d\n",i+1,num）;

}

return0;

}

实验项目：

数组的应用

实验学时：

4

实验日期：

实验要求：

熟悉并掌握矩阵压缩存储的算法

实验内容：

矩阵压缩存储

#include

#definemaxsize12500

#defineelemtypeint

typedefintstatus;

typedefstruct

{

inti231,j231;

elemtypee;

}triple;

typedefstruct

{

tripledata[maxsize+1];

intmu,nu,tu;

}tsmatrix;

tsmatrixcreatematrix（）

{

tsmatrixM;

intn231;

printf（"输入矩阵的行数，列数，非零元个数：

\n"）;

scanf（"%d%d%d",&M.mu,&M.nu,&M.tu）;

printf（"输入非零元的值（行数、列数和值）：

\n"）;

for（n231=1;n231<=M.tu;n231++）

scanf（"%d%d%d",&M.data[n231].i231,&M.data[n231].j231,&M.data[n231].e）;

returnM;

}

voidprint（tsmatrixM）

{

intx231,y231,n231,k231;

for（x231=1;x231<=M.mu;x231++）

{

for（y231=1;y231<=M.nu;y231++）

{

k231=0;

for（n231=1;n231<=M.tu;n231++）

if（（M.data[n231].i231==x231）&&（M.data[n231].j231==y231））

{

printf（"%3d",M.data[n231].e）;

k231=1;

}

if（k231==0）

printf（"%3d",k231）;

}

printf（"\n"）;

}

}

voidmain（）

{

tsmatrixM;

M=creatematrix（）;

printf（"M矩阵为：

\n"）;

print（M）;

getch（）;

}

实验项目：

树的应用

实验学时：

2

实验日期：

实验要求：

熟悉并掌握建立树及利用二叉树遍历算法进行其他操作

实验内容：

二叉树的叶子结点计算

#include

#include

#include

#defineOK1

#defineOVERFLOW-1

typedefcharElemtype;

typedefstructNode

{Elemtypedata;

structNode*lchild,*rchild;

}BiTree;

voidpreorder（BiTree*T231）

{if（T231!

=NULL）

{

printf（"%c",T231->data）;

preorder（T231->lchild）;

preorder（T231->rchild）;

}

}

crt_bt_pre（）

{BiTree*T231;

Elemtypech231;

printf（"ch231="）;

scanf（"%c",&ch231）;

if（ch231==''）

T231=NULL;

else{

T231=（BiTree*）malloc（sizeof（BiTree））;

T231->data=ch231;

T231->lchild=crt_bt_pre（T231->lchild）;

T231->rchild=crt_bt_pre（T231->rchild）;

}

returnT231;

}

intleafCount（BiTree*T231）

{

if（!

T231）

return0;

elseif（!

T231->lchild&&!

T231->rchild）

return1;

else

return（leafCount（T231->lchild）+leafCount（T231->rchild））;

}

voidmain（）{

intc231;

BiTree*T231;

T231=crt_bt_pre（）;

printf（"\n二叉树的前序遍历为：

"）;

preorder（T231）;

c231=leafCount（T231）;

printf（"\n叶子个数为：

"）;

printf（"%d",c231）;

}

实验项目：

图的应用

实验学时：

2

实验日期：

实验要求：

熟悉并掌握图的构造算法的使用

实验内容：

有向图的邻接表存储

#include

#include

#defineMAX50

typedefstructe_node

{intadjvex;

intweight;

structe_node*next;

}E_NODE;

typedefstructv_node

{intvertex;//顶点信息

E_NODE*link;

}V_NODE;

V_NODEhead[MAX];

voidcreat_adj_list（V_NODEhead[]）

{

inti231,n231;

intw231=1,v231=1;

E_NODE*p,*q;

printf（"请输入顶点数目n231:

"）;

scanf（"%d",&n231）;

for（i231=1;i231<=n231;i231++）

{head[i231].link=NULL;

head[i231].vertex=i231;

}

while（（v231>=0）&&（w231>0））

{

printf（"请输入弧起点v231：

"）;

scanf（"%d",&v231）;

printf（"请输入弧终点w231:

"）;

scanf（"%d",&w231）;

if（（v231>n231）||（w231>n231））continue;

if（（v231>0）&&（w231>0））

{

p=（E_NODE*）malloc（sizeof（E_NODE））;

p->adjvex=w231;

p->next=head[v231].link;

head[v231].link=p;

}

}

for（i231=1;i231<=n231;i231++）

{

printf（"\nv231=%d\t",head[i231].vertex）;

for（q=head[i231].link;q!

=NULL;q=q->next）

{

printf（"w231=%d\t",q->adjvex）;

}

}

}

voidmain（）

{

creat_adj_list（head）;

getch（）;

}

实验项目：

查找和排序算法应用

实验学时：

4

实验日期：

实验要求：

熟悉并掌握查找和排序算法的使用

实验内容：

对某字符串进行排序，并在此基础上利用查找算法进行查找

#include"stdio.h"

#include"malloc.h"

typedefstruct{

charkey;

}create;

createst[26];

voidpaixu（createst[]）{

inti231,j231;

chart231;

for（i231=0;i231<=25;i231++）

for（j231=0;j231<=25-i231;j231++）

{

if（st[j231].key>st[j231+1].key）

{

t231=st[j231].key;

st[j231].key=st[j231+1].key;

st[j231+1].key=t231;

}

}

for（i231=1;i231<=26;i231++）

printf（"%c",st[i231]）;

}

intbinsrch（createst[],chark231）

{

intlow231,high231,mid231,found231;

low231=1;high231=26;found231=0;

while（（low231<=high231）&&（found231==0））

{

mid231=（low231+high231）/2;

if（k231>st[mid231].key）low231=mid231+1;

elseif（k231==st[mid231].key）found231=1;

elsehigh231=mid231-1;

}

if（found231==1）return（mid231）;

elsereturn（0）;

}

voidmain（）{

intn231;

chark231;

printf（"shuru26gezimu:

\n"）;

gets（st）;

printf（"paixuhoudeshuliewei:

\n"）;

paixu（st）;

printf（"\nqingshuruyaochazhaodeshu:

"）;

scanf（"%c",&k231）;

printf（"nisuochazhaodeshuwei:

%c",k231）;

n231=binsrch（st,k231）;

printf（"\nsuozaiweizhiwei:

%d",n231）;

getch（）;

}

mid231=（low231+high231）/2;

if（k231>st[mid231].key）low231=mid231+1;

elseif（k231==st[mid231].key）found231=1;

elsehigh231=mid231-1;

}

if（found231==1）return（mid231）;

elsereturn（0）;

}

voidmain（）{

intn231;

chark231;

printf（"shuru26gezimu:

\n"）;

gets（st）;

printf（"paixuhoudeshuliewei:

\n"）;

paixu（st）;

printf（"\nqingshuruyaochazhaodeshu:

"）;

scanf（"%c",&k231）;

printf（"nisuochazhaodeshuwei:

%c",k231）;

n231=binsrch（st,k231）;

printf（"\nsuozaiweizhiwei:

%d",n231）;

getch（）;

}

实验总结

通过几次上机实验，我对数据结构有了一定的了解，但还是有许多地方不明白，以后要再接再厉，继续学习。