算法与数据结构实验册.docx
《算法与数据结构实验册.docx》由会员分享，可在线阅读，更多相关《算法与数据结构实验册.docx（81页珍藏版）》请在冰点文库上搜索。
算法与数据结构实验册
学生实验报告册
（理工类）
课程名称：
算法与数据结构专业班级：
学生学号：
学生姓名：
所属院部：
指导教师：
2014——2015学年第二学期
金陵科技学院教务处制
实验报告书写要求
实验报告原则上要求学生手写，要求书写工整。
若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。
纸张一律采用A4的纸张。
实验报告书写说明
实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。
各院部可根据学科特点和实验具体要求增加项目。
填写注意事项
（1）细致观察，及时、准确、如实记录。
（2）准确说明，层次清晰。
（3）尽量采用专用术语来说明事物。
（4）外文、符号、公式要准确，应使用统一规定的名词和符号。
（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。
实验报告批改说明
实验报告的批改要及时、认真、仔细，一律用红色笔批改。
实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。
实验报告装订要求
实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。
实验项目名称：
顺序表实验学时：
2
同组学生姓名：
实验地点：
实验日期：
实验成绩：
批改教师：
批改时间：
实验1顺序表
一、实验目的和要求
掌握顺序表的定位、插入、删除等操作。
二、实验仪器和设备
TurboC2.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。
编写主函数测试结果。
（2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。
如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。
编写主函数测试结果。
（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。
解题思路：
首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。
（4）删除顺序表中所有等于X的数据元素。
2、选做题
（5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。
程序清单：
1、
（1）
#include
#include
#definemaxsize100
typedefintdatatype;
typedefstruct
{
datatypea[maxsize];
intsize;
}sequence_list;
sequence_listmylist;
voiddisplay（sequence_listslt）
{
inti;
if（slt.size==0）
printf（"\n顺表表是空的"）;
else
for（i=0;iprintf（"%5d",slt.a[i]）;
}
voidinit（sequence_list*slt）
{
slt->size=0;
}
voidmain（）
{
inti,number;
init（&mylist）;
printf（"顺序表是空的请建立顺序表！
"）;
printf（"\n"）;
printf（"请输入顺序表中的元素个数！
\n"）;
scanf（"%d",&number）;
mylist.size=number;
for（i=0;i{
scanf（"%d",&mylist.a[i]）;
}
display（mylist）;
printf（"\n"）;
}
（2）
#include
#include
#definemaxsize100
typedefintdatatype;
typedefstruct
{
datatypea[maxsize];
intsize;
}sequence_list;
sequence_listmylist;
voiddisplay（sequence_listslt）
{
inti;
if（slt.size==0）
printf（"\n顺表表是空的"）;
else
for（i=0;iprintf（"%5d",slt.a[i]）;
}
voidinit（sequence_list*slt）
{
slt->size=0;
}
intfind（sequence_list*slt,intx）
{
inti,a;
for（i=0;isize;i++）
{
if（x==slt->a[i]）
{
a=i;
break;
}
}
if（i!
=slt->size）
returna;
else
return-1;
}
voidmain（）
{
inti,number,a,b;
init（&mylist）;
printf（"顺序表是空的请建立顺序表！
"）;
printf（"\n"）;
printf（"请输入顺序表中的元素个数！
\n"）;
scanf（"%d",&number）;
mylist.size=number;
for（i=0;i{
scanf（"%d",&mylist.a[i]）;
}
display（mylist）;
printf（"\n"）;
printf（"输入要查找的数：
"）;
scanf（"%d",&a）;
b=find（&mylist,a）;
if（b!
=-1）
{
printf（"顺序表的下标为：
%d\n",b）;
}
else
printf（"cannotbefound!
"）;
}
（3）
#include
#include
#definemaxsize100
typedefintdatatype;
typedefstruct
{
datatypea[maxsize];
intsize;
}sequence_list;
sequence_listmylist;
voiddisplay（sequence_listslt）
{
inti;
if（slt.size==0）
printf（"\n顺表表是空的"）;
else
for（i=0;iprintf（"%5d",slt.a[i]）;
}
voidinit（sequence_list*slt）
{
slt->size=0;
}
voidsort（sequence_list*slt）
{
inti,j,temp;
//交换法排序
for（i=0;isize;i++）
{
for（j=i+1;jsize;j++）
{
if（slt->a[i]>slt->a[j]）
{
temp=slt->a[i];
slt->a[i]=slt->a[j];
slt->a[j]=temp;
}
}
}
}
voidappend（sequence_list*slt,intx）
{
slt->a[slt->size]=x;
slt->size++;
sort（&mylist）;
}
voidmain（）
{
inti,number,x;
init（&mylist）;
printf（"顺序表是空的请建立顺序表！
"）;
printf（"\n"）;
printf（"请输入顺序表中的元素个数！
\n"）;
scanf（"%d",&number）;
mylist.size=number;
for（i=0;i{
scanf（"%d",&mylist.a[i]）;
}
display（mylist）;
sort（&mylist）;
printf（"\n"）;
display（mylist）;
printf（"\n"）;
printf（"输入要插入的元素：
"）;
printf（"\n"）;
scanf（"%d",&x）;
append（&mylist,x）;
display（mylist）;
printf（"\n"）;
}
（4）
#include
#include
#definemaxsize100
typedefintdatatype;
typedefstruct
{
datatypea[maxsize];
intsize;
}sequence_list;
sequence_listmylist;
voiddisplay（sequence_listslt）
{
inti;
if（slt.size==0）
printf（"\n顺表表是空的"）;
else
for（i=0;iprintf（"%5d",slt.a[i]）;
}
voidinit（sequence_list*slt）
{
slt->size=0;
}
voidsort（sequence_list*slt）
{
inti,j,temp;
//交换法排序
for（i=0;isize;i++）
{
for（j=i+1;jsize;j++）
{
if（slt->a[i]>slt->a[j]）
{
temp=slt->a[i];
slt->a[i]=slt->a[j];
slt->a[j]=temp;
}
}
}
}
voiddel（sequence_list*slt,intx）
{
intm[maxsize];
inti,n=0,j,a=0;
for（i=0;isize;i++）
{
if（slt->a[i]!
=x）
{
m[n++]=slt->a[i];
}
elsea++;
}
slt->size=slt->size-a;
for（i=0;i{
slt->a[i]=m[i];
}
for（j=slt->size;jsize+n;j++）
slt->a[i]=0;
}
voidmain（）
{
inti,number,x;
init（&mylist）;
printf（"顺序表是空的请建立顺序表！
"）;
printf（"\n"）;
printf（"请输入顺序表中的元素个数！
\n"）;
scanf（"%d",&number）;
printf（"请建立顺序表！
\n"）;
mylist.size=number;
for（i=0;i{
scanf（"%d",&mylist.a[i]）;
}
display（mylist）;
sort（&mylist）;
printf（"\n"）;
display（mylist）;
printf（"\n"）;
printf（"请输入要删除的元素：
"）;
scanf（"%d",&x）;
del（&mylist,x）;
display（mylist）;
}
（5）
#include
#include
#definemaxsize100
typedefintdatatype;
typedefstruct
{
datatypea[maxsize];
intsize;
}sequence_list;
sequence_listmylistA,mylistB,mylistC;
voiddisplay（sequence_listslt）
{
inti;
if（slt.size==0）
printf（"\n顺表是空的"）;
else
for（i=0;iprintf（"%5d",slt.a[i]）;
}
voidinit（sequence_list*slt）
{
slt->size=0;
}
voidhebing（sequence_list*sltA,sequence_list*sltB,sequence_list*sltC）
{
inti,j=0;
for（i=0;isize;i++）
{
sltC->a[i]=sltA->a[i];
}
for（i=sltA->size;isize+sltB->size;i++）
{
sltC->a[i]=sltB->a[j++];
}
}
voidsort（sequence_list*slt）
{
inti,j,temp;
//交换法排序
for（i=0;isize;i++）
{
for（j=i+1;jsize;j++）
{
if（slt->a[i]>slt->a[j]）
{
temp=slt->a[i];
slt->a[i]=slt->a[j];
slt->a[j]=temp;
}
}
}
}
voidmain（）
{
inti,numberA,numberB;
init（&mylistA）;
printf（"顺序表是空的请建立顺序表A！
"）;
printf（"\n"）;
printf（"请输入顺序表中的元素个数;"）;
scanf（"%d",&numberA）;
mylistA.size=numberA;
for（i=0;i{
scanf（"%d",&mylistA.a[i]）;
}
display（mylistA）;
printf（"\n"）;
sort（&mylistA）;
display（mylistA）;
printf（"\n"）;
printf（"顺序表是空的请建立顺序表B！
"）;
printf（"\n"）;
printf（"请输入顺序表中的元素个数:
"）;
scanf（"%d",&numberB）;
mylistB.size=numberB;
for（i=0;i{
scanf（"%d",&mylistB.a[i]）;
}
display（mylistB）;
printf（"\n"）;
sort（&mylistB）;
display（mylistB）;
printf（"\n"）;
printf（"顺序表C"）;
init（&mylistC）;
mylistC.size=mylistA.size+mylistB.size;
hebing（&mylistA,&mylistB,&mylistC）;
sort（&mylistC）;
display（mylistC）;
printf（"\n"）;
}
四、实验结果与分析（程序运行结果及其分析）
五、实验体会（遇到问题及解决办法，编程后的心得体会）
通过该实验，我熟练地掌握了顺序表的建立以及顺序表中的元素查找。
实验项目名称：
单链表实验学时：
2
同组学生姓名：
实验地点：
实验日期：
实验成绩：
批改教师：
批改时间：
实验2单链表
一、实验目的和要求
1、实验目的
掌握单链表的定位、插入、删除等操作。
2、实验要求
（1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。
（2）链表不能实现直接定位，一定注意指针的保存，防止丢失。
二、实验仪器和设备
TurboC2.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。
（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。
解题思路：
首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。
（3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。
2、选做题
已知指针LA和LB分别指向两个无头结点单链表的首元结点。
要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。
程序清单：
（1）
#include
#include
typedefstructnode{
intdata;
structnode*next;
}*Linklist,Node;
Linklistcreat（intn）
{
Linklisthead,r,p;
intx,i;
head=（Node*）malloc（sizeof（Node））;
r=head;
printf（"输入数字:
\n"）;
for（i=n;i>0;i--）
{
scanf（"%d",&x）;
p=（Node*）malloc（sizeof（Node））;
p->data=x;
r->next=p;
r=p;
}
r->next=NULL;
returnhead;
}
voidoutput（Linklisthead）
{
Linklistp;
p=head->next;
do{
printf（"%3d",p->data）;
p=p->next;
}while（p）;
printf（"\n"）;
}
voidmain（）
{
Linklisthead;
intx,n;
printf（"输入数字的个数（n）:
\n"）;
scanf（"%d",&n）;
head=creat（n）;
printf（"输出数字:
\n"）;
output（head）;
}
（2）
#include
#include
typedefstructnode{
intdata;
structnode*next;
}*Linklist,Node;
Linklistcreat（intn）
{
Linklisthead,r,p;
intx,i;
head=（Node*）malloc（sizeof（Node））;
r=head;
printf（"输入数字:
\n"）;
for（i=n;i>0;i--）
{
scanf（"%d",&x）;
p=（Node*）malloc（sizeof（Node））;
p->data=x;
r->next=p;
r=p;
}
r->next=NULL;
returnhead;
}
voidoutput（Linklisthead）
{
Linklistp;
p=head->next;
do{
printf（"%3d",p->data）;
p=p->next;
}while（p）;
printf（"\n"）;
}
voidsort（Linklisthead）
{
Linklistp,q,small;
inttemp;
for（p=head->next;p->next!
=NULL;p=p->next）
{
small=p;
for（q=p->next;q;q=q->next）
if（q->datadata）
small=q;
if（small!
=p）
{
temp=p->data;
p->data=small->data;
small->data=temp;
}
}
printf（"输出升序排序后的数字:
\n"）;
output（head）;
}
display（Linklisthead）
{
Linklistp;
printf（"有序表为:
\n"）;
for（p=head;p!
=NULL;p=p->next）
printf（"%4d",p->data）;
}
insert（Linklisthead,intx）
{
Linklistp,s;
intt;
p=head;
while（p->datap=p->next;
s=（Linklist）malloc（sizeof（Linklist））;
s->data=x;
s->next=p->next;
p->next=s;
t=p->data;
p->data=s->data;
s->data=t;
display（head）;
}
voidmain（）
{
Linklisthead;
intx,n;
printf（"输入数字的个数（n）:
\n"）;
scanf（"%d",&n）;
head=creat（n）;
printf（"输出数字:
\n"）;
output（head）;
sort（head）;
printf（"输入要插入的数字（x）:
\n"）;
scanf（"%d",&x）;
insert（head,x）;
}
（3）
#include
#include
typedefstructnode{
intdata;
升级会员 