数据结构实验报告1310300.docx
《数据结构实验报告1310300.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告1310300.docx（43页珍藏版）》请在冰点文库上搜索。
数据结构实验报告1310300
（此文档为word格式，下载后您可任意编辑修改！
）
《数据结构》实验报告
专业计算机科学与技术
班级121班
姓名张航
学号
学期第1学期
指导老师刘勇
成绩：
实验
1
2
3
4
总分
成绩
教师评语：
数据结构上机实验报告
学号：
姓名：
张航所在系：
计算机科学与技术班级：
121班
实验名称：
线性结构基本算法的实现实验日期2013/11/6
实验指导教师刘勇实验机房4号机房
------
1.实验目的：
（1）掌握线性表顺序存储结构的基本操作：
插入、删除、查找；
（2）掌握线性表链式结构的基本操作：
插入、删除、合并等运算；
（3）掌握栈和队列基本运算的算法；
（4）掌握稀疏矩阵的压缩存储的算法。
2.实验内容：
（1）实现顺序表的创建、插入、删除和查找的操作；
（2）实现单链表插入、删除、合并的操作；
（3）实现2个有序线性表的合并；
（4）利用顺序栈实现括号匹配的算法；
（5）实现顺序队列各种基本运算的算法；
（6）实现链栈各种基本运算的算法；（选做）
（7）实现链队列各种基本运算的算法；（选做）
（8）实现稀疏矩阵压缩存储的算法。
3．算法设计（编程思路或流程图或源代码）
内容：
1、顺序表的插入和删除
//SqList.h
#include
#include
#include
#defineElemTypeint
#defineOK1
#defineERROR0
#defineOVERFLOW0
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
intInitList（SqList*L）
{
L->elem=（ElemType*）malloc（100*sizeof（ElemType））;
if（!
L->elem）
returnOVERFLOW;
L->listsize=100;
L->length=0;
returnOK;
}
intCreateList（SqList*L,intn）
{
inti;
L->length=n;
printf（"请输入%d个整数：
\n",L->length）;
for（i=0;ilength;i++）
scanf（"%d",&L->elem[i]）;
returnOK;
}
voidTravelList（SqList*L）
{
inti;
for（i=0;ilength;i++）
printf（"当前顺序表第%d个元素为：
%d\n",i+1,L->elem[i]）;
}
intInsertList（SqList*L,inti,ElemTypee）
{
ElemType*newbase,*p,*q;
if（i<0||i>（L->length+1））
returnERROR;
if（L->length>=L->listsize）
{
newbase=（ElemType*）realloc（L->elem,（100+50）*sizeof（ElemType））;
if（!
newbase）
returnERROR;
L->elem=newbase;
L->listsize=100+50;
}
p=&L->elem[i-1];
for（q=&L->elem[L->length-1];q>=p;q--）
*（q+1）=*q;
*p=e;
L->length++;
returnOK;
}
intDelList（SqList*L,inti,ElemType&x）
{
ElemType*p,*q;
if（i<1||i>L->length||L->length==0）
returnERROR;
p=&L->elem[i-1];
x=*p;
for（q=&L->elem[L->length-1];q>p;p++）
*p=*（p+1）;
L->length--;
returnOK;
}
//.cpp
#include
#include
#include"SqList.h"
voidmain（）
{
intn,i;
ElemTypee,x;
SqListsq;
SqList*l=&sq;
printf（"***顺序表的基本操作***\n"）;
printf（"计算机12117张航\n\n\n"）;
printf（"***初始化顺序表***\n"）;
InitList（l）;
printf（"成功初始化顺序表！
\n\n"）;
printf（"***建立顺序表***\n"）;
printf（"输入要建立顺序表的长度：
\n"）;
scanf（"%d",&n）;
CreateList（l,n）;
printf（"成功建立顺序表！
\n"）;
TravelList（l）;
printf（"\n\n"）;
printf（"***顺序表的插入***\n"）;
printf（"输入插入位置及插入元素：
\n"）;
scanf（"%d%d",&i,&e）;
InsertList（l,i,e）;
printf（"成功插入顺序表！
\n"）;
TravelList（l）;
printf（"\n\n"）;
printf（"***顺序表的删除***\n"）;
printf（"输入删除位置：
\n"）;
scanf（"%d",&i）;
DelList（l,i,x）;
printf（"成功删除顺序表第%d个元素%d\n",i,x）;
}
2、有序单链表的合并
//LinkList.h
#include
#include
#include
#defineElemTypeint
#defineNULL0
typedefstructLNode
{
ElemTypedata;
LNode*next;
}*LinkList;
voidCreateList（LinkListL,intn）
{
inti;
LinkListp,q;
p=L;
for（i=1;i<=n;i++）
{
q=（LinkList）malloc（sizeof（LNode））;
printf（"输入第%d个元素：
\n",i）;
scanf（"%d",&q->data）;
q->next=p->next;
p->next=q;
p=p->next;
}
}
voidTravelList（LinkListL）
{
inti=1;
LinkListp;
p=L->next;
while（p）
{
printf（"第%d个元素为：
%d\n",i,p->data）;
i++;
p=p->next;
}
}
voidMergeList（LinkListLa,LinkListLb,LinkListLc）
{
LinkListpa,pb,pc;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while（pa&&pb）
{
if（pa->data<=pb->data）
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?
pa:
pb;
free（Lb）;}
//.cpp
#include
#include
#include
#include"LinkList.h"
voidmain（）
{
LinkListLa,Lb,Lc;
intn1,n2;
La=（LinkList）malloc（sizeof（LNode））;
La->next=NULL;
Lb=（LinkList）malloc（sizeof（LNode））;
Lb->next=NULL;
printf（"***两个有序单链表的合并操作***\n"）;
printf（"计算机12117张航\n\n\n"）;
printf（"输入第一个单链表的长度：
\n"）;
scanf（"%d",&n1）;
printf（"非递减顺序输入%d个整数：
\n",n1）;
CreateList（La,n1）;
printf（"第一个单链表中的元素为：
\n"）;
TravelList（La）;
printf（"\n\n"）;
printf（"输入第二个单链表的长度：
\n"）;
scanf（"%d",&n2）;
printf（"非递减顺序输入%d个整数：
\n",n2）;
CreateList（Lb,n2）;
printf（"第二个单链表中的元素为：
\n"）;
TravelList（Lb）;
printf（"\n\n"）;
printf（"正在执行合并操作......\n\n\n"）;
Lc=La;
MergeList（La,Lb,Lc）;
printf（"合并后单链表的元素为：
\n"）;
TravelList（Lc）;
}
3、数制转换的算法实现
//SqStack.h
#include
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW0
#defineElemTypeint
typedefstruct
{
ElemType*base;
ElemType*top;
intstacksize;
}SqStack;
intInitStack（SqStack*S）
{
S->base=（ElemType*）malloc（20*sizeof（ElemType））;
if（!
S）
returnOVERFLOW;
S->top=S->base;
S->stacksize=20;
returnOK;
}
intPush（SqStack*S,ElemTypee）
{
if（S->top-S->base>=S->stacksize）
{
S->base=（ElemType*）realloc（S->base,（20+10）*sizeof（ElemType））;
if（!
S->base）
returnOVERFLOW;
S->top=S->base+S->stacksize;
S->stacksize=20+10;
}
*（S->top++）=e;
returnOK;
}
intPop（SqStack*S,ElemType&x）
{
if（S->top==S->base）
returnERROR;
x=*（--S->top）;
returnOK;
}
//.cpp
#include
#include
#include
#include"SqStack.h"
voidconversion（intn,intm）
{
inte;
SqStacksq;
SqStack*s=&sq;
InitStack（s）;
while（n）
{
Push（s,n%m）;
n=n/m;
}
while（sq.base!
=sq.top）
{
Pop（s,e）;
printf（"%d",e）;
}
}
voidmain（）
{
intn,m;
printf（"***数制转换***\n"）;
printf（"计算机12117张航\n\n\n"）;
printf（"输入一个10进制整数：
\n"）;
scanf（"%d",&n）;
printf（"输入需要转换的数制：
\n"）;
scanf（"%d",&m）;
printf（"正在进行转换......\n\n"）;
printf（"10进制数%d转换成%d进制数为：
\n",n,m）;
conversion（n,m）;
printf（"\n"）;
}
4、快速转置算法的实现
//.cpp
#include
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW0
#defineElemTypeint
#defineMAXSIZE12500
typedefstruct
{
intr,c;
ElemTypee;
}Triple;
typedefstruct
{
Tripledata[MAXSIZE];
introws,cols,nums;
}TSMatrix;
intCreateMatrix（TSMatrix&t,ElemTypea[5][5]）
{
inti,j;
t.rows=5;
t.cols=5;
t.nums=0;
for（i=0;i<5;i++）
{
for（j=0;j<5;j++）
{
if（a[i][j]!
=0）
{
t.data[t.nums+1].r=i+1;
t.data[t.nums+1].c=j+1;
t.data[t.nums+1].e=a[i][j];
t.nums++;
}
}
}
t.data[0].r=t.rows;
t.data[0].c=t.cols;
t.data[0].e=t.nums;
returnOK;
}
voidDisplayMatrix（TSMatrixt）
{
inti;
for（i=0;i<=t.nums;i++）
printf（"%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].e）;
}
intFastTransposeMatrix（TSMatrixt,TSMatrix&t1）
{
intcol,i,p,q;
intnum[6];
intcpot[6];
t1.rows=t.cols;
t1.cols=t.rows;
t1.nums=t.nums;
if（t.nums）
{
for（col=1;col<=t.cols;col++）
num[col]=0;
for（i=1;i<=t.nums;i++）
num[t.data[i].c]++;
cpot[1]=1;
for（col=2;col<=t.cols;col++）
cpot[col]=cpot[col-1]+num[col-1];
for（p=1;p<=t.nums;p++）
{
col=t.data[p].c;
q=cpot[col];
t1.data[q].r=t.data[p].c;
t1.data[q].c=t.data[p].r;
t1.data[q].e=t.data[p].e;
cpot[col]++;
}
}
t1.data[0].r=t1.rows;
t1.data[0].c=t1.cols;
t1.data[0].e=t1.nums;
returnOK;
}
voidmain（）
{
ElemTypea[5][5];
TSMatrixt,t1;
inti,j;
printf（"***5*5稀疏矩阵快速转置操作***\n"）;
printf（"计算机12117张航\n\n\n"）;
printf（"输入25个整数：
\n"）;
for（i=0;i<5;i++）
{
for（j=0;j<5;j++）
scanf（"%d",&a[i][j]）;
}
CreateMatrix（t,a）;
printf（"当前稀疏矩阵的三元组顺序表表示为：
\n"）;
DisplayMatrix（t）;
printf（"\n\n正在进行快速转置操作......\n\n"）;
FastTransposeMatrix（t,t1）;
printf（"转置后矩阵的三元组顺序表表示为：
\n"）;
DisplayMatrix（t1）;
}
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。
或对其他程序环境的使用情况的记录。
注：
必须认真书写）
算法1
realloc函数原型是externvoid*realloc（void*mem_address,unsignedintnewsize）;
算法2
pc->next=pa?
pa:
pb;等价于if（pa）pc->next=paelsepc->next=pb;
free（Lb）;这一句，返回的Lc指向了La，所以不能freeLa。
Lc中的Lb的数据是从Lb->next开始插入的pb=Lb->next。
Lb这个指针还指向一个链表头，所以需要free。
算法3
x=*（--S->top）;此句第一次写成x=--S->top;导致编译出错。
S->top还是一个指针，*（--S->top）才是指针所指的内容，才可以赋值给整形变量x。
算法4
调试过程中第一个大错误是将intCreateMatrix（TSMatrix&t,ElemTypea[5][5]）写成intCreateMatrix（TSMatrixt,ElemTypea[5][5]），区别在于按值传递和按地址传递。
按照错误的写法，导致程序DisplayMatrix（t）时，输出为空。
因为在main（）中CreateMatrix（t,a）时，按值传递不改变参数t的状态，t还是保持TSMatrixt时的未赋值状态，所以输出为空。
修改为按地址传递后，CreateMatrix（t,a）运行一系列操作，形参t发生变化就是实参t发生变化，进而输出正确结果。
调试过程中intFastTransposeMatrix（TSMatrixt,TSMatrix&t1）函数中
for（p=1;p<=t.nums;p++）语句本来写成for（p=1;p<=t.cols;p++）,这是一个很微小的错误，误把变量搞错。
但是这个小错误却导致FastTransposeMatrix（t,t1）运行结果不正确：
执行DisplayMatrix（t1），只有t1.data[0]~t1.data[5]正确输出，其余t1.data[]都是未知。
经过长时间分析检查发现这个错误并改正。
这说明写代码一定要认真仔细，这样才能尽可能避免话费大量的时间来发现小错误。
另外写本算法时还有若干小错误。
5．讨论（通过实验的一些体会、学会的知识和技能等）
见4.程序调试。
数据结构上机实验报告
学号：
姓名：
张航所在系：
计算机科学与技术班级：
121班
实验名称：
二叉树的基本应用实验日期2013/11/20
实验指导教师刘勇实验机房4号机房
------
2.实验目的：
（1）理解树这种数据结构。
（2）掌握二叉树二叉链表这种存储结构。
（3）完成二叉树各种基本运算的算法。
2.实验内容：
（1）实现二叉树创建的算法。
（2）实现二叉树各种遍历算法。
（3）实现二叉树其他操作的算法，包括：
统计叶子结点的个数、求二叉树的深度、线索二叉树等。
3．算法设计（编程思路或流程图）
1、二叉树创建的算法
//BiTNode.h
#include
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW0
#defineNULL0
#defineElemTypechar
typedefstructBiTNode
{
ElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
intCreateBiTree（BiTree&T）
{
ElemTypech;
scanf（"%c",&ch）;
if（ch=='#'）
T=NULL;
else
{
T=（BiTNode*）malloc（sizeof（BiTNode））;
if（!
T）
exit（OVERFLOW）;
T->data=ch;
CreateBiTree（T->lchild）;
CreateBiTree（T->rchild）;
}
returnOK;
}
voidLevelBiTree（BiTreeT）
{
BiTreeQueue[20],b;
intfront,rear;
front=rear=0;
if（T）
{
Queue[rear]=T;
rear=（rear+1）%20;
while
升级会员 