数据结构算法实验报告.docx
《数据结构算法实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构算法实验报告.docx（56页珍藏版）》请在冰点文库上搜索。
数据结构算法实验报告
数据结构算法实验报告（总汇）
实验报告1：
1.根据1.1.2的排列函数的规格说明，编写程序实现习题1.1和习题1.2所定义的函数。
习题1.1定义下列函数检查一个序列是否有序：
boolsorted（inta[],intn）;
解：
#include
//N代表可以改动数组的元素个数
#defineN5//函数功能：
用于判断一个数组序列是否为一个非递减序列;
boolSorted（inta[],intn）
{inti,Num=0;
for（i=0;i{if（a[i]>a[i+1]）
{returnfalse;
break;}
else
Num++;}
if（Num==n-1）
returntrue;}
intmain（）
{inta[N],i;
booltest;
printf（"\n\t--程序用于判断输进来的程序是否为非递减排序--\n\n\n"）;
printf（"输入%d元素:
\n",N）;
for（i=0;iscanf（"%d",&a[i]）;
test=Sorted（a,N）;
if（test==true）
printf（"数组是非递减排序\n"）;
else
printf（"数组不是非递减排序\n"）;
return0;}
习题1.2定义下列函数检查两个序列是否互为置换：
boolpermutation（inta[],intb[],intn）;
解：
//tranverse
//功能：
用于判断两个数组：
是否互为转置，如a[3]:
123;b[3]:
321--则数组a,b互为转置；
#include
//在这里可以指定数组存储的元素的个数N
#defineN5
//函数功能：
用于判断从控制台输入的两个数组是否互为转置;
booltranverse（inta[],intb[],intn）
{inti,Num=0;
//算法的关键之处：
同时遍历两个数组的元素，其中第一个数组元素为i时，例外一个//数组元素的序号为n-i-1;
//当遍历过程一旦出现不相等的状况，程序返回false,并终止程序--表示这两个数组肯定//不互为转置;
//否则，即相等--则继续进行比较，并记录相等的次数n，当循环结束时，比较n与数组//的个数num，如果n=num;则表示
//两个数组互为转置，返回true;
for（i=0;i{if（a[i]!
=b[n-i-1]）
{returnfalse;
break;}
else
Num++;}
if（Num==n）
returntrue;}
intmain（）
{inti,a[N],b[N];
booltest;
printf（"\n\t\t--程序用于判断两个数组是否互为转置--\n\n"）;
printf（"数组a输入%d个元素:
\n",N）;
for（i=0;iscanf（"%d",&a[i]）;
printf（"数组b输入%d个元素:
\n",N）;
for（i=0;iscanf（"%d",&b[i]）;
test=tranverse（a,b,N）;
if（test==true）
printf（"数组a与数组b互为转置\n"）;
else
printf（"数组a与数组b不互为转置\n"）;
return0;}
2.编写两个不同的排列程序，使用插入排序和冒泡排序两种算法分别实现之。
解：
插入法
#include
#include
#include
#defineN10
voidinsert_sort（int*array,unsignedintn）
{inti,j;
inttemp;
for（i=0;i{temp=*（array+i）;
for（j=i;j>0&&*（array+j-1）>temp;j--）
{*（array+j）=*（array+j-1）;}
*（array+j）=temp;}
}
voidmain（）
{inti,a[N];
printf（"请输入%d个元素：
\n",N）;
for（i=0;iscanf（"%d",&a[i]）;
insert_sort（a,N）;
printf（"输出这个%d元素",N）;
for（i=0;iprintf（"%d",a[i]）;
printf（"\n"）;}
冒泡法：
#include
#include
#include
#defineN10
voidBubble（inta[],intn）
{inti,j,temp;
for（i=0;i{for（j=0;j{if（a[j]>a[j+1]）
{temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;}}}}
voidmain（）
{inti,a[N];
printf（"请输入%d个元素：
\n",N）;
for（i=0;iscanf（"%d",&a[i]）;
Bubble（a,N）;
printf（"输出这个%d元素",N）;
for（i=0;iprintf（"%d",a[i]）;
printf（"\n"）;}
3.使用取得CPU时间的方法，来比较插入排序和冒泡排序两种不同的排列方法的时间复杂度的差异。
解：
/NumbersToTestTime
/程序功能：
产生随机数rand（）%M+1:
产生1-M之间的数--冒泡排序测试时间
#include
#include
#include
#defineN2000
voidmain（）
{inti,j,temp;
inta[N];
doubleduration;
clock_tstart,finish;
for（i=0;ia[i]=rand（）%1000+1;//随机产生1-1000以内的数；
start=clock（）;//核心在于：
循环变量都从i=0,j=0开始，大循环N趟，每一趟N-j次：
jfor（j=0;j{for（i=0;i{if（a[i]>a[i+1]）
{temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;}}}
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
printf（"对随机产生的这%d个数进行冒泡排序--从小到大：
\n",N）;
for（i=0;i{if（i%10==0）
printf（"\n"）;
printf（"%d",a[i]）;}
printf（"\n"）;
printf（"排序所用的时间：
%fseconds\n",duration）;}
由程序执行的结果可知，在相同的输入规模以及程序运行环境的条件下，对系统随机产生的2000个数分别进行插入，冒泡排序，相对而言，插入排序所需要的时间更少。
1.算法
1.1什么是算法？
答：
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
1.2算法的正确性
答：
一个算法的正确性是指，对于算法的任何合法输入，算法总是给出正确的输出。
1.3算法的规格说明
答：
对于算法的任何合法输入，算法总是给出正确的输出，算法应该满足的这种输入和输出之间的关系，成为算法的规格说明。
2.请设计插入排序算法的规格说明
答：
voidinsert_sort（int*array,unsignedintn）
3.请设计冒泡排序算法的规格说明
答：
voidBubble（inta[],intn）
4.请设计测试数据，来统计插入排序和冒泡排序算法的最好，最坏和平均情况下的时间复杂度。
答：
插入排序：
最好情况下，排序前对象已按从小到大有序，每趟只需与前面有序对象序列的最后一个对象比较1次，移动2次对象，总的数据比较次数为n-1，移动次数为2（n-1）。
最坏情况下，每趟第i个对象必须与前面i-1个对象都做比较，并且每1次比较就要做1次数据移动。
最差复杂度O（N^2）最优时间复杂度O（N）平均时间复杂度O（N^2）。
冒泡排序：
最好的情形是当数据已经从小到大排好序时，此算法只执行一趟冒泡，做n-1次数据比较，不移动对象。
最坏的情形是算法执行n-1趟冒泡，第i趟（1<=i最优的时间复杂度是O（n）最差的时间复杂度O（n^2）平均时间复杂度O（n^2）。
实验报告2：
1.参考课本2.2.2使用数组编程实现线性表
解：
//ArrayOperate.CPP
//数组上面的一系列操作
#include
#include
#defineN10
typedefintElemType;
ElemTypeArray[N];
//数组元素的初始化--定义并赋初值
voidInit_Array（ElemTypea[],intn）
{inti;
printf（"请输入%d个元素：
\n",n）;
for（i=0;iscanf（"%d",&a[i]）;}//数组元素的遍历--这里采用"打印的操作"遍历数组；
voidPrint_Array（ElemTypea[],intn）
{inti;
printf（"输出这%d个元素如下：
\n",n）;
for（i=0;iprintf（"%d",a[i]）;
printf（"\n"）;
printf（"此时的数组元素个数为%d\n",n）;}//修改某一个位置元素的值
voidCorrect_Array（ElemTypea[],intpox,ElemTypeval）
{if（pox<0||pox>N）
{printf（"您输入的位置pox不合法\n"）;
exit（0）;}
a[pox-1]=val;}
//在数组中的某个位置插入某一个元素：
算法核心在于--先人为开辟一个存储空间，然后将数组元素从最后一个元素开始进行搬迁，最后插入这个元素;
voidInsert_Array（ElemTypea[],intindex,ElemTypevalue,intn）
{inti;
if（index<0）{
printf（"您想插入的元素的位置index不合法\n"）;
exit（0）;}
for（i=n-1;i>=index;i--）
a[i+1]=a[i];
a[index]=value;
//n=n+1;}
//删除数组中的指定的元素：
算法核心在于--要先找到那个元素，并对该元素记录，从记录开始直到最后，进行元素的迁移
voidDelete_Array（ElemTypea[],ElemTypedata）
{inti,record,j,count=0;
for（i=0;i{if（a[i]!
=data）
continue;//else表示跳出了if判断
elseif（i==N+1）
printf（"数组遍历完毕，没有这个元素\n"）;
else{record=i;
for（j=record;ja[j]=a[j+1];
count++;}}
printf（"删除了%d个这样的元素\n",count）;}
intmain（）
{ElemTypevalue,data,val;
intindex,pox;
printf（"--数组的初始化--\n"）;
Init_Array（Array,N）;
printf（"\n--便利数组（这里采用打印的操作）--\n"）;
Print_Array（Array,N）;
printf（"\n--数组元素的修改操作--\n"）;
printf（"请输入想要修改数组的哪个位置pox的元素值val（逗号隔开输入）\n"）;
scanf（"%d,%d",&pox,&val）;
Correct_Array（Array,pox,val）;
Print_Array（Array,N）;
printf（"\n\n--数组元素的插入操作--\n"）;
printf（"请输入插入元素的位置index（这里指数组元素的下标且index>0,index<%d）以及元素的值value（用逗号隔开输入）:
\n",N）;
scanf（"%d,%d",&index,&value）;
Insert_Array（Array,index,value,N+1）;
Print_Array（Array,N+1）;
printf（"\n\n--数组元素的删除操作--\n"）;
printf（"请输入想要删除的元素的值data:
\n"）;
scanf（"%d",&data）;
Delete_Array（Array,data）;
Print_Array（Array,N）;
printf（"\n"）;
return0;}
2.请编程实现两个有序序列的合并排序（使用顺序表示方式）
解：
//ArrayMerge
//功能：
数组元素的归并
#include
#include"InsertSorted.h"
#defineN4
#defineM6
typedefintElemType;
intmain（）
{inti,j,k;
ElemTypea[N],b[M],c[M+N];
printf（"\t--两个数组元素的合并并有序输出--\n\n"）;
printf（"请输入a数组的%d个元素：
\n",N）;
for（i=0;iscanf（"%d",&a[i]）;
printf（"请输入b数组的%d个元素：
\n",M）;
for（i=0;iscanf（"%d",&b[i]）;
for（i=0;ic[i]=a[i];
for（j=0;jc[N+j]=b[j];
Insertsorted（c,M+N）;
printf（"将a数组与b数组进行合并后中的元素采取某种排序从小到大输出如下:
\n"）;
for（k=0;kprintf（"%d",c[k]）;
printf（"\n"）;
return0;}/*ArrayMerge.CPP的头文件*/
/*InsertSorted.h文件*/
typedefintElemType;
voidInsertsorted（ElemTypearray[],intnum）
{inti,j,key;//算法核心
for（j=1;j{key=array[j];
i=j-1;
while（（i>=0）&&（array[i]>key））
{array[i+1]=array[i];
i=i-1;}
array[i+1]=key;}}
2.参考课本2.2.4使用单链表编程实现线性表
解：
//ListOperate.cpp的头文件
/*Struct.h*/
typedefstructstudent
{intnum;
structstudent*next;
}student;
intn;
//ListOperate.cpp
//动态建立一个链表并在上面的一系列操作-执行过程--应该需要在草稿纸上进行描绘--演示
#include
#include
#include"Struct.h"
#defineNULL0
intn;
///动态链表的建立
student*creat（void）
{student*head,*p1,*p2;
n=0;
//开辟一个存储单元
p2=p1=（student*）malloc（sizeof（student））;
//printf（"输入个人信息，输入0时结束\n"）;
//scanf（"%ld,%f",&p1->num,&p1->score）;
scanf（"%ld",&p1->num）;
head=NULL;
while（p1->num!
=0）
{n=n+1;
if（n==1）//说明这是第一个结点;
head=p1;
else
p2->next=p1;
p2=p1;//开辟新的存储单元--意味着这将用于存储新的生成的新结点
p1=（structstudent*）malloc（sizeof（structstudent））;
scanf（"%ld",&p1->num）;}
p2->next=NULL;
returnhead;}
//用于输出这个建立的动态链表--首先要获取建立好动态链表之后返回的头指针;
voidprint（student*head）
{student*p;
printf（"输出的数据如下:
\n"）;
p=head;
if（head!
=NULL）
do
{//printf（"%ld%4.2f\n",p->num,p->score）;
printf（"%ld",p->num）;
p=p->next;}
while（p!
=NULL）;}
//修改链表中的数据--获取头指针，需要修改的数据num,需要修改成num为新的值Newnum;
student*correct（student*head,longnum,longNewnum）{
student*p1;
if（head==NULL）
{printf（"链表为空\n"）;
returnhead;}
p1=head;
while（num!
=p1->num&&p1->next!
=NULL）
{p1=p1->next;}
if（num==p1->num）
{p1->num=Newnum;}
else
printf（"没有找到这个结点\n"）;
returnhead;}//删除链表中的某一个结点
student*del（student*head,longdata）
{student*p1,*p2;
if（head==NULL）
{printf（"链表为空\n"）;
returnhead;}
p1=head;
while（data!
=p1->num&&p1->next!
=NULL）
{p2=p1;
p1=p1->next;}
if（data==p1->num）
{if（p1==head）
head=p1->next;
else
p2->next=p1->next;
printf（"删除了结点:
%ld\n",data）;
n=n-1;}
else
printf（"没有找到这个结点\n"）;
returnhead;}//链表中插入结点
student*insert（student*head,student*stud）
{student*p0,*p1,*p2;
p1=head;
p0=stud;
if（head==NULL）
{head=p0;
p0->next=NULL;}
else
{while（（p0->num>p1->num）&&（p1->next!
=NULL））
{p2=p1;
p1=p1->next;}
if（p0->num<=p1->num）
{if（head==p1）
head=p0;
else
p2->next=p0;
p0->next=p1;}
else
{p1->next=p0;
p0->next=NULL;}}
n=n+1;
returnhead;}
voidmain（）
{student*head,stu;
longnum,num1,Newnum;//printf（"下面用于一个建立动态链表输入0结束）\n"）;
printf（"\n--链表的初始化--一个建立动态链表,输入数据num（输入0结束）:
--\n"）;
head=creat（）;
printf（"\n--链表数据元素的遍历（这里采用打印链表数据元素操作）--\n"）;
print（head）;
printf（"\n"）;//修改链表中的数据
printf（"\n--链表数据元素的修改--输入想要修改的数据以及将它修改为的数值（num1,Newnum）:
\n"）;
scanf（"%ld,%ld",&num1,&Newnum）;
head=correct（head,num1,Newnum）;
printf（"输出修改数据后的链表\n"）;
print（head）;
printf（"\n\n--链表数据元素的删除--\n"）;
printf（"\n输入要删除的num：
"）;
scanf（"%ld",&num）;
head=del（head,num）;
print（head）;
printf（"\n\n--链表数据元素的插入--\n"）;
printf（"\n输入要插入的结点的信息（num）\n"）;
scanf（"%ld",&stu.num）;
head=insert（head,&stu）;
printf（"输出插入结点后的新链表\n"）;
print（head）;
printf（"\n"）;}
3.请编程实现习题2.13的内容（使用链式表示方式）
解：
//ListCreatAndOutput.cpp
//功能：
简单链表的建立与输出
#include
#include
#defineNULL0
intn;
structdata
{intinfo;
st
升级会员 