数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告.docx（30页珍藏版）》请在冰点文库上搜索。
数据结构实验报告
数据结构实验报告
实验一
1、编写算法实现线性顺序表的逆置。
2、用线性表的链式模式编写算法，实现两个表La=（1,5,4,8,6,11）和Lb=（9,7,4,2,1,5）的并集。
实验1-1
主要代码：
boolGetElem（intposition,int&e）const//求指定位置的元素
{
if（position<=0||position>count）
returnfalse;
else
{
e=elems[position-1];
returntrue;
}
}
boolSetElem（intposition,constint&e）//设置指定位置的元素值
{
if（position<=0||position>count）
returnfalse;
else
{
elems[position-1]=e;
returntrue;
}
}
voiddisp（）
{
for（inti=0;i{
cout<}
cout<}
};
voidreverse（SqList&la）
{
intleftposition=1;
intrightposition=la.Length（）;
inta,b;
while（leftposition{la.GetElem（leftposition,a）;
la.GetElem（rightposition,b）;
la.SetElem（leftposition,b）;
la.SetElem（rightposition,a）;
leftposition++;
rightposition--;
}//在这里加代码
}
intmain（）
{
inta[10]={1,2,3,4,5,6,7,8,9,10};
SqListla（a,10）;
la.disp（）;
reverse（la）;//该函数完成逆置功能
la.disp（）;
return0;
}
int*p,*q;
intposition=0;
boolflag=false;
p=head;
p=p->next;
while（p!
=null）
{position++;
if（position>=2&&p->data==x）
{q=GetElemPtr（position-2）;
*tmpPtr=q->next;
}
q->next=tmpPt->next;
deletetmpPtr;
flag=true;
position--;}
p=p->next;
}//这里加代码
returnflag;
实验1-2
主要代码：
SimpleLinkList:
:
SimpleLinkList（constSimpleLinkList©）
//操作结果：
由线性表copy构造新线性表——复制构造函数模板
{
intcopyLength=copy.Length（）;//copy的长度
inte;
Init（）;//初始化线性表
for（intcurPosition=1;curPosition<=copyLength;curPosition++）
{
boolSimpleLinkList:
:
Delete_x（int&x）
{
Node*p,*q;
intposition=0;
p=head;
p=p->next;
while（p!
=NULL）
{
position++;
if（position>=2&&p->data==x）
{
q=GetElemPtr（position-2）;
Node*tmpPtr=q->next;
q->next=tmpPtr->next;
deletetmpPtr;
position--;
}
p=p->next;
}
returntrue;//这里加代码
}
intmain（）
{
inta[9]={1,5,4,8,6,11,11,11,56};
SimpleLinkListla（a,9）;
la.Traverse（）;
la.Delete_x（a[5]）;
//这里完成删除x的前一个节点操作
la.Traverse（）;
}
实验二
1、已知q是一个非空顺序队列，s是一个顺序栈，请设计一个算法，实现将队列q中所有元素逆置。
2、请完成队列划分子集问题的算法。
实验2-1
主要代码：
voidSqQueue:
:
Traverse（）const
//操作结果：
依次对队列的每个元素调用函数（*visit）
{
for（intcurPosition=front;curPosition!
=rear;
curPosition=（curPosition+1）%maxSize）
{//对队列每个元素调用函数（*visit）
cout<}
cout<}
boolSqQueue:
:
OutQueue（int&e）
//操作结果：
如果队列非空，那么删除队头元素，并用e返回其值，返回SUCCESS,
//否则返回UNDER_FLOW，
{
if（!
Empty（））
{//队列非空
e=elems[front];//用e返回队头元素
front=（front+1）%maxSize;//front指向下一元素
returntrue;
}
else
{//队列为空
returnfalse;
}
}
boolSqQueue:
:
GetHead（int&e）const
//操作结果：
如果队列非空，那么用e返回队头元素，返回SUCCESS,
//否则返回UNDER_FLOW，
{
if（!
Empty（））
{//队列非空
e=elems[front];//用e返回队头元素
returntrue;
}
else
{//队列为空
returnfalse;
}
}
boolSqQueue:
:
InQueue（constint&e）
//操作结果：
如果队列已满，返回OVER_FLOW,
//否则插入元素e为新的队尾，返回SUCCESS
{
if（Full（））
{//队列已满
returnfalse;
}
else
{//队列未满，入队成功
elems[rear]=e;//插入e为新队尾
rear=（rear+1）%maxSize;//rear指向新队尾
returntrue;
}
}
intmain（）
{
inta[10]={1,2,3,4,5,6,7,8,9,10};
inti,temp,n=10;
SqQueueq（n+1）;
SqStacks（n+1）;
for（i=0;iq.InQueue（a[i]）;
cout<<"队列目前的元素为:
";
q.Traverse（）;
for（i=0;i{
q.OutQueue（temp）;
s.Push（temp）;
}
cout<<"栈的元素为:
";
s.Traverse（）;
for（i=0;i{
s.Pop（temp）;
q.InQueue（temp）;
}
cout<<"新队列的元素为:
";
q.Traverse（）;
return0;
}
实验2-2
主要代码：
boolSqQueue:
:
OutQueue（int&e）
//操作结果：
如果队列非空，那么删除队头元素，并用e返回其值，返回SUCCESS,
//否则返回UNDER_FLOW，
{
if（!
Empty（））
{
//队列非空
e=elems[front];//用e返回队头元素
front=（front+1）%maxSize;//front指向下一元素
returntrue;
}
else
{
//队列为空
returnfalse;
}
}
boolSqQueue:
:
InQueue（constint&e）
//操作结果：
如果队列已满，返回OVER_FLOW,
//否则插入元素e为新的队尾，返回SUCCESS
{
if（Full（））
{
//队列已满
returnfalse;
}
else
{
//队列未满，入队成功
elems[rear]=e;//插入e为新队尾
rear=（rear+1）%maxSize;//rear指向新队尾
returntrue;
}
}
intmain（）
{
intA[9]={1,2,3,4,5,6,7,8,9};
intR[9][9],n=9,a,b,i,j,temp,group,num_all,num_group;
intresult[n],newr[n];
SqQueueq（n+1）;
for（i=0;i{
result[i]=0;
for（j=0;j{
R[i][j]=0;
}
}
for（i=0;iq.InQueue（A[i]）;
cout<<"请输入相互排斥的数据对，以-1为结束信号：
"<while（cin>>a,a!
=-1）//完成关系矩阵的赋值操作
{
cin>>b;
R[a-1][b-1]=1;
R[b-1][a-1]=1;
}
group=0;
num_all=n;
num_group=0;
while（!
q.Empty（））//只要循环队列中元素不为空，就做如下的划分操作
{
group++;//第group组的元素划分
q.OutQueue（temp）;//该组第一个元素出栈
num_group++;//该组目前具有的数量
result[temp-1]=group;//该组元素对应的位置放到result中
for（i=0;inewr[i]=R[temp-1][i];//把与该元素的冲突关系记录到数组newr中
num_all=num_all-num_group;//还需要出队列判断的元素数量
num_group=0;//初始化
for（j=0;j{
q.OutQueue（temp）;
if（newr[temp-1]==1）//如果该元素与当前的组的元素有冲突，重新入队
q.InQueue（temp）;
else//否则把该元素加入到当前组中
{
result[temp-1]=group;
for（i=0;i{
if（R[temp-1][i]==1）//把鱼当前元素有冲突的冲突关系加入到数组newr中
newr[i]=1;
}
num_group++;//该组目前具有的元素数量
}
}
}
for（i=1;i<=group;i++）//打印出划分结果
{
cout<<"第"<";
for（j=0;j{
if（result[j]==i）
cout<}
cout<}
return0;
}
实验三
1、系数矩阵的快速转置，并输出转置之后的矩阵
2、二叉树的遍历，分别调用先序，中序和后序遍历算法输出遍历结果。
实验3-1
主要代码：
voidTriSparseMatrix:
:
FastTranspose（constTriSparseMatrix&source,TriSparseMatrix&dest）
//操作结果：
将稀疏矩阵source转置成稀疏矩阵dest的快速算法
{
dest.rows=source.cols;
dest.cols=source.rows;
dest.num=source.num;
dest.maxSize=source.maxSize;
delete[]dest.triElems;
dest.triElems=new
Triple[dest.maxSize];
if（dest.num>0）
{
intdestPos=0;
for（intcol=1;col<=source.cols;col++）
{
for（intsourcePos=0;sourcePos{
if（source.triElems[sourcePos].col==col）
{
dest.triElems[destPos].row=source.triElems[sourcePos].col;
dest.triElems[destPos].col=source.triElems[sourcePos].row;
dest.triElems[destPos].value=source.triElems[sourcePos].value;
destPos++;
}
}
}
}
//代码写在这里
//释放cPos
}
intmain（void）
{
constintn=5;
TriSparseMatrixa（n,n）;//定义一个n行n列稀疏矩阵
intb[n][n]=
{
1,0,3,0,0,
4,0,6,0,0,
0,0,8,9,0,
0,0,0,1,12,
1,0,0,3,1
};
inti,j,v;//工作变量
//设置稀疏矩阵a的元素值
for（i=1;i<=n;i++）
{
//行
for（j=1;j<=n;j++）
{
//列
a.SetElem（i,j,b[i-1][j-1]）;//设置元素值
}
}
//显示转置前的稀疏矩阵a
cout<<"转置前稀疏矩阵a:
"<for（i=1;i<=a.GetRows（）;i++）
{
//行
for（j=1;j<=a.GetCols（）;j++）
{
//列
a.GetElem（i,j,v）;//求元素值
cout<}
cout<}
TriSparseMatrixc;
TriSparseMatrix:
:
FastTranspose（a,c）;//转置a成c
//显示转置后稀疏矩阵c
cout<<"转置后的稀疏矩阵c:
"<for（i=1;i<=c.GetRows（）;i++）
{
//行
for（j=1;j<=c.GetCols（）;j++）
{
//列
c.GetElem（i,j,v）;//求元素值
cout<}
cout<}
return0;//返回值0,返回操作系统
}
实验3-2
主要代码：
voidBinaryTree:
:
InOrderHelp（BinTreeNode*r）const
//操作结果：
中序遍历以r为根的二叉树
{
if（r!
=NULL）
{
InOrderHelp（r->leftChild）;
cout<<（r->data）;
InOrderHelp（r->rightChild）;
}//代码写在这里
}
voidBinaryTree:
:
InOrder（）const
//操作结果：
中序遍历二叉树
{
InOrderHelp（root）;
}
voidBinaryTree:
:
PostOrderHelp（BinTreeNode*r）const
//操作结果：
后序遍历以r为根的二叉树
{
if（r!
=NULL）
{PostOrderHelp（r->leftChild）;
PostOrderHelp（r->rightChild）;
cout<<（r->data）;
}//代码写在这里
}
实验四
1、分别用普通查找和折半查找在数组中查找一个数字，输出其数组的下标和比较的次数。
2、散列表的构建与查找已知一组关键字（19,14,23,1,68,20,84,27,55,11,10,79）
哈希函数为：
H（key）=keyMOD13,哈希表长为m=16，利用线性探索法构建散列表，并根据每个输入的key值输出其位置下标和比较的次数。
实验4-1
主要代码：
#include
usingnamespacestd;
boolsqSearch（inta[],intn,intkey,int&loc,int&count）//顺序查找函数：
数组为a；n为数组中元素个数；key为查找的数据，loc为数据对应的位置；count为比较的次数；查找成功返回true，否则返回false.
{
//代码内容
inti;
for（i=0;i{
if（a[i]==key）
{
loc=i;
count=i+1;
returntrue;
}
}
returnfalse;
}
boolBinSearch（inta[],intn,intkey,int&loc,int&count）//折半查找函数：
数组为a;n为数组中元素个数;key为查找的数据，loc为数据对应的位置;count为比较的次数;查找成功返回true，否则返回false.
{
//代码内容
intcou,mid,low,high;
cou=0;
low=0;
high=n-1;
while（low<=high）
{
mid=（low+high）/2;
cou=cou+1;
cout<if（a[mid]==key）
{
count=cou;
loc=mid;
returntrue;
}
else
if（keyhigh=mid-1;
else
low=mid+1;
}
returnfalse;
}
intmain（）
{
intnum[19]={3,4,9,11,12,13,16,22,23,24,29,30,38,66,87,91,93,95,99};
intloc,count,n=19,key=91;
if（sqSearch（num,n,key,loc,count）==true）
{
cout<<"顺序查找：
"<cout<<"下标为：
"<cout<<"比较次数为：
"<}
if（BinSearch（num,n,key,loc,count）==true）
{
cout<<"折半查找：
"<cout<<"下标为：
"<cout<<"比较次数为：
"<}
return0;
}
实验4-2
主要代码：
#include
usingnamespacestd;
voidHconstruct（inta[],intn,intc[],intp,intm）
{
inti,te;
int*temp=newint[m];
for（i=0;i{
temp[i]=0;
}
for（i=0;i{
te=a[i]%p;
if（temp[te]==0）
{
c[te]=a[i];
temp[te]=1;
}
else
{while（temp[te]==1）
{
te=（te+1）%m;
}
c[te]=a[i];
temp[te]=1;
}
}
}
voidHsearch（intkey,intc[],intp,intm,int&loc,int&time）
{
inttemp;
time=1;
temp=key%p;
while（c[temp]!
=key）
{
temp=（temp+1）%m;
time++;
}
loc=temp;
}
intmain（）
{
inta[12]={19,14,23,1,68,20,84,27,55,11,10,79};
intc[16];
intloc,time,key,p,m;
p=13;
m=16;
Hconstruct（a,12,c,p,m）;
while（cin>>key,key!
=-1）
{
Hsearch（key,c,p,m,loc,time）;
cout<<"数据"<"<cout<<"数据"<"<}
return0;
}
实验五
1、对于100个无序的整数，分别使用冒泡排序、快速排序和希尔排序使其有序。
2、假设有100个红白蓝三种颜色的小色块（无序：
三种颜色分别用0,1,2表示），编写程序，使每种颜色有序排列（注意：
要求时间复杂度为O（n））.
实验5-1
主要代码：
#in
升级会员 