算法与数据结构实验报告 本文关键词：数据结构，算法，实验，报告
算法与数据结构实验报告 本文简介：金陵科技学院实验报告学生实验报告册课程名称：算法与数据结构实验项目名称：顺序表实验学时：2同组学生姓名：实验地点：工科楼A205实验日期：2013年10月16日实验成绩：批改教师：批改时间：实验1顺序表一、实验目的和要求掌握顺序表的定位、插入、删除等操作。二、实验仪器和设备TurboC2.0三、实验
算法与数据结构实验报告 本文内容：
金陵科技学院实验报告
学
生
实
验
报
告
册
课程名称：算法与数据结构
实验项目名称：
顺序表
实验学时：
2
同组学生姓名：
实验地点：
工科楼A205
实验日期：
2013年10月16日
实验成绩：
批改教师：
批改时间：
实验1
顺序表
一、实验目的和要求
掌握顺序表的定位、插入、删除等操作。
二、实验仪器和设备
Turbo
C
2.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、#define
maxsize
100
typedef
struct{
int
data[maxsize];
int
last;
}sequenlist;
main()
{
int
i;
sequenlist
l={{2,5,6,8,2,8,4,3},7};
printf(“/nThe
list
is:“);
for(i=0;ix)
break;
for(j=l.last;j>=i-1;j--)
l.data[j+1]=l.data[j];
l.data[i-1]=x;
l.last++;
printf(“the
list
after
insertion
is:/n“);
for(j=0;j
typedef
int
datattype;
typedef
struct
node{
char
data;
struct
nodenext;
}linklist;
main(){
char
ch;linklisthead,*s,*r,*p;
head=malloc(sizeof(linklist));
r=head;
scanf(“%c“,while(ch!=
$
){
s=malloc(sizeof(linklist));
s->data=ch;
r->next=s;
r=s;
scanf(“%c“,}
r->next=NULL;
r=head->next;
while(r!=NULL){
printf(“%c“,r->data);
r=r->next;
}
}
2、#include
“stdio.h“#include
“stdlib.h“typedef
struct
node{
int
data;
struct
nodenext;
}linklist;
main(){
int
x,y;
linklisthead,*s,*r,*p,*q,*m,*n;
clrscr();
head=malloc(sizeof(linklist));
r=head;
printf(“input
the
order
numbers
:“);
scanf(“%d“,while(x!=0){
s=malloc(sizeof(linklist));
s->data=x;
r->next=s;
r=s;
scanf(“%d“,}
r->next=NULL;
printf(“Please
input
the
insert
value:“);
scanf(“%d“,p=head->next;
while(p!=NULL){
if
(p->datanext;
else
break;
}
q=malloc(sizeof(linklist));
q->data=y;
m=head;
while(m->next!=p)
m=m->next;
q->next=p;
m->next=q;
n=head->next;
printf(“the
list
are:“);
while(n!=NULL){
printf(“%3d“,n->data);
n=n->next;
}
}
3、#include
“stdio.h“#include
“stdlib.h“typedef
struct
node{
int
data;
struct
nodenext;
}linklist;
main(){
int
a;
linklisthead,*s,*r,*p,*q,*t;
clrscr();
head=malloc(sizeof(linklist));
r=head;
printf(“Input
some
numbers:“);
scanf(“%d“,while(a!=0){
s=malloc(sizeof(linklist));
s->data=a;
r->next=s;
r=s;
scanf(“%d“,}
r->next=NULL;
printf(“/n
The
linklist
before
changed
is:/n
“);
p=head->next;
while(p){
printf(“%d“,p->data);
p=p->next;
}
p=head->next;
q=p->next;
while(q!=NULL){
t=q->next;
q->next=p;
p=q;
q=t;
}
head->next->next=NULL;
head->next=p;
printf(“/nAfter
changed:/n“);
p=head->next;
while(p!=NULL){
printf(“%d“,p->data);
p=p->next;
}
}
四、实验结果与分析（程序运行结果及其分析）
1、输入：1
2
3
a
b
c
$
输出结果：1
2
3
a
b
c
2、输入：input
the
order
numbers
:
1
3
5
7
8
9
0
Please
input
the
insert
value:：4
输出结果：the
list
are:
1
3
4
5
7
8
9
3、输入：Input
some
numbers:1
3
4
5
8
0
输出结果：The
linklist
before
changed
is:
13458
After
changed:
85431
五、实验体会（遇到问题及解决办法，编程后的心得体会）
遇到问题：编写成功后运行时，没有加入$导致程序运行不成功，不能够退出。后注意到这个问题才继续运行下去。
实验体会：在编写程序时，设置了结束字符一定要牢牢记住，并且在输入时观察仔细类型是什么，以及是否是输入一串有顺序的数字，编写成功不难，但是要规范格式，不能仅仅以完成程序为目的。而完成这一章的实验也让我了解了，顺序表便于查找不便于插入删除，而链表恰恰相反，链表的插入删除只需要移动指针，而顺序表要从后往前依次移动，二者各有优劣。
实验项目名称：
堆栈和队列
实验学时：
2
同组学生姓名：
实验地点：
工科楼A205
实验日期：
2013年10月30日
实验成绩：
批改教师：
批改时间：
实验3
堆栈和队列
一、实验目的和要求
（1）掌握应用栈解决问题的方法。
（2）掌握利用栈进行表达式求和的算法。
（3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。
二、实验仪器和设备
Turbo
C
2.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）
判断一个算术表达式中开括号和闭括号是否配对。
（2）
测试“汉诺塔”问题。
（3）
假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。
2、选做题
在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。
程序清单：
1、typedef
int
datatype;
#define
M
100
typedef
struct{
char
data[M];
int
top;
}
seqstack;
main(){
char
str[M];
int
result=0,i=0;
seqstack
s;
s.top=0;
gets(str);
while(str[i]!=
/0
){
if(str[i]==
(
){
s.top++;
s.data[s.top]=
(
;
}
if(str[i]==
)
){
if(s.top==0){
result=1;
break;
}
else
s.top--;
}
i++;
}
if(result==0
else
if(result==1)
printf(“Missing
left!/n“);
else
if(s.top>0)
printf(“Missing
right!/n“);
}
2、#include
void
hanoi(int
n,char
a,char
b,char
c){
if(n==1)
printf(“/n
Move
disk
%d
from
pile
%c
to
pile
%c“,n,a,c);
else{
hanoi(n-1,a,c,b);
printf(“/n
Move
disk
%d
from
pile
%c
to
pile
%c“,n,a,c);
hanoi(n-1,b,a,c);
}
}
void
main(){
int
n;
clrscr();
printf(“/n
Please
enter
the
number
of
disks
to
be
moved:“);
scanf(“%d“,hanoi(n,A,B,C
);
}
3、#include
#define
M
100
typedef
struct{
char
data[M];
int
top;
}seqstack;
main(){
char
str[M];
int
i=0,n;
seqstack
s;
s.top=0;
gets(str);
while(str[i]!=
@
)
i++;
if(i==1){
printf(“Yes/n“);
return;
}
n=i;
for(i=0;i=s.curlen)
printf(“Not
find!/n“);
}
2、#define
maxsize
100
typedef
struct{
char
ch[maxsize];
int
curlen;
}seqstring;
main(){
int
i,flag=0;
char
ch;
seqstring
s={{“abadeag“},6};
for(i=0;i
#include
typedef
struct
linknode{
char
data;
struct
linknodenext;
}linkstring;
main(){
linkstringhead,*s,*r,*p,*q;
int
i,b,l,k=0;
char
ch;
head=NULL;r=NULL;
printf(“/n
Next
to
creat
LinkString,$
as
end
mark/n“);
ch=getchar();
while(ch!=
$
){
s=malloc(sizeof(linkstring));
s->data=ch;
if(head==NULL)
head=s;
else
r->next=s;
r=s;
ch=getchar();
}
if(r!=NULL)
r->next=NULL;
q=head;
while(q){
printf(“%c“,q->data);
q=q->next;
k++;
}
printf(“/n
Now
input
two
int
for
stratpostion
and
length
for
deleted:“);
scanf(“%d
%d“,if(b>k-1||b+l>k){
printf(“Error!/n“);
return;
}
p=head;
for(i=0;inext;
}
printf(“%c
%d
%d
%d
/n“,p->data,b,l,k);
for(i=b-1;inext;p->next=q->next;free(q);
}
q=head;
while(q){
printf(“%c“,q->data);
q=q->next;
}
printf(“/n“);
}
四、实验结果与分析（程序运行结果及其分析）
1、输入：s
输出结果：ch=s.ch[1]=s
2、输入：a
输出结果：ch=s.ch[0]=a
ch=s.ch[2]=a
ch=s.ch[5]=a
3、输入：asdfghjkl$
2
5
输出结果：s
2
5
9
askl
五、实验体会（遇到问题及解决办法，编程后的心得体会）
实验体会：本章第一题可以作为第二题的子函数，使用调用；也可以从开头查找对应的字符到结尾，最后全部输出。前两题使用顺序串，后面一题是链串。串的存储结构包含有顺序存储结构和链式存储结构。在串的顺序存储结构中，表示串的长度通常有两种方法：一种方法是设置一个串的长度参数，其优点在于便于在算法中用长度参数控制循环过程；另一种方法是在串值得末尾添加结束标记，此种方法的优点在于便于系统自动实现。在串的存储过程中，串值用双引号引起来，系统将自动在串值得末尾添加结束标记/0字符。
实验项目名称：
二叉树
实验学时：
2
同组学生姓名：
实验地点：
工科楼A205
实验日期：
2013年11月13日
实验成绩：
批改教师：
批改时间：
实验5
二叉树
一、实验目的和要求
（1）掌握二叉树的生成，以及前、中、后序遍历算法。
（2）掌握应用二叉树递归遍历思想解决问题的方法。
二、实验仪器和设备
Turbo
C
2.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）
建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。
（2）
在第一题基础上，求二叉树中叶结点的个数。
（3）
在第一题基础上，求二叉树中结点总数。
（4）
在第一题基础上，求二叉树的深度。
2、选做题
已知一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。
解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。
程序清单：
1（1）#include
#include
#define
maxsize
100
typedef
struct
node{
char
data;
struct
nodelchild,*rchild;
}bitree;
bitreeQ[maxsize];
bitreeCreatree(){
char
ch;
int
front,rear;
bitreeroot,*s;
root=NULL;front=1;rear=0;
printf(“Now
Creat
the
bitree,input
baseing
the
order
top
to
bottom,left
to
right:/n“);
ch=getchar();
while(ch!=
#
){
s=NULL;
if(ch!=
@
){
s=malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else{
if(s
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return
root;
}
void
preorder(t)
bitreet;
{
if(t)
{
printf(“%c“,t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void
inorder(t)
bitreet;
{
if(t){
inorder(t->lchild);
printf(“%c“,t->data);
inorder(t->rchild);
}
}
void
postorder(t)
bitreet;
{
if(t){
postorder(t->lchild);
postorder(t->rchild);
printf(“%c“,t->data);
}
}
main(){
bitreeroot;
clrscr();
root=Creatree();
printf(“preorder
is:“);preorder(root);
printf(“/n“);
printf(“inorder
is:“);inorder(root);
printf(“/n“);
printf(“postorder
is:“);postorder(root);
printf(“/n“);
}
（2）#include
#include
#define
maxsize
100
typedef
struct
node{
char
data;
struct
nodelchild,*rchild;
}bitree;
bitreeQ[maxsize];
bitreeCreatree(){
char
ch;
int
front,rear;
bitreeroot,*s;
root=NULL;front=1;rear=0;
printf(“Now
Creat
the
bitree,input
baseing
the
order
top
to
bottom,left
to
right:/n“);
ch=getchar();
while(ch!=
#
){
s=NULL;
if(ch!=
@
){
s=malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else{
if(s
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return
root;
}
int
left(bitreet){
int
num1,num2;
if(t==NULL)
return
0;
else
if(t->lchild==NULL
else{
num1=left(t->lchild);
num2=left(t->rchild);
return(num1+num2);
}
}
main(){
bitreeroot;
clrscr();
root=Creatree();
printf(“lefts
is
%d/n“,left(root));
}
（3）#include
#include
#define
maxsize
100
typedef
struct
node{
char
data;
struct
nodelchild,*rchild;
}bitree;
bitreeQ[maxsize];
bitreeCreatree(){
char
ch;
int
front,rear;
bitreeroot,*s;
root=NULL;front=1;rear=0;
printf(“Now
Creat
the
bitree,input
baseing
the
order
top
to
bottom,left
to
right:/n“);
ch=getchar();
while(ch!=
#
){
s=NULL;
if(ch!=
@
){
s=malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else{
if(s
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return
root;
}
int
nodes(bitreet){
int
num1,num2;
if(t==NULL)
return
0;
else
if(t->lchild==NULL
else{
num1=nodes(t->lchild);
num2=nodes(t->rchild);
return
(num1+num2+1);
}
}
main(){
bitreeroot;
clrscr();
root=Creatree();
printf(“nodes
is
%d/n“,nodes(root));
}
（4）#include
#include
#define
maxsize
100
typedef
struct
node{
char
data;
struct
nodelchild,*rchild;
}bitree;
bitreeQ[maxsize];
bitreeCreatree(){
char
ch;
int
front,rear;
bitreeroot,*s;
root=NULL;front=1;rear=0;
printf(“Now
Creat
the
bitree,input
baseing
the
order
top
to
bottom,left
to
right:/n“);
ch=getchar();
while(ch!=
#
){
s=NULL;
if(ch!=
@
){
s=malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else{
if(s
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return
root;
}
int
depth(bitreet){
int
dep1,dep2;
if(t==NULL)
return
0;
else{
dep1=depth(t->lchild);
dep2=depth(t->rchild);
if(dep1>dep2)
return
(dep1+1);
else
return(dep2+1);
}
}
main(){
bitreeroot;
clrscr();
root=Creatree();
printf(“depth
is
%d/n“,depth(root));
}
四、实验结果与分析（程序运行结果及其分析）
（1）Now
Creat
the
bitree,input
baseing
the
order
top
to
bottom,left
to
right:
[email protected]@@@c#
preorder
is:abc
inorder
is:abc
postorder
is:cba
（2）Now
Creat
the
bitree,input
baseing
the
order
top
to
bottom,left
to
right:
[email protected]@@@c#
lefts
is
1
（3）Now
Creat
the
bitree,input
baseing
the
order
top
to
bottom,left
to
right:
[email protected]@@@c#
nodes
is
3
（4）Now
Creat
the
bitree,input
baseing
the
order
top
to
bottom,left
to
right:
[email protected]@@@c#
depth
is
3
五、实验体会（遇到问题及解决办法，编程后的心得体会）
遇到问题：这章从一开始编写成功后运行就一直不顺利，理论上程序时正确的，但是输入运行处的结果却总是错误一大堆。在询问老师后，经过运行及测试，才明白我是对ch=getchar();这个函数的理解错误，在这个函数中，空格也算作一个字符，所以当我输入的时候，每一个字符中间空一个，输入五个对于程序我相当于输入了十个字符。
实验体会：这次的实验让我明白了基础理论知识的重要性，没有坚实的基础知识，在这种问题上，即使编写出来了，检查错误调试就要花许多时间。并且我也学会了二叉树的输入赋值以及它的各种计算。
实验项目名称：
图
实验学时：
2
同组学生姓名：
实验地点：
工科楼A205
实验日期：
2013年11月20日
实验成绩：
批改教师：
批改时间：
实验6
图
一、实验目的和要求
（1）熟练掌握图的基本概念、构造及其存储结构。
（2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。
二、实验仪器和设备
Turbo
C
2.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）构造一个无向图（用邻接矩阵表示存储结构）。
（2）对上面所构造的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。
2、选做题
采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。
程序清单：
1（1）
#include
#define
n
6
#define
e
8
typedef
struct
{
char
vexs[n];
float
arcs[n][n];
}
graph1;
creatgraph(){
graph1ga;
int
i,j,k;
float
w;
clrscr();
for(i=0;ivexs[i]=getchar();printf(“ok/n“);
for(i=0;iarcs[i][j]=0;
for(k=0;karcs[i][j]=w;
ga->arcs[j][i]=w;
}
printf(“ok/n“);
}
main(){
creatgraph();
}
（2）#include
#define
n
3
#define
e
2
typedef
struct
{
char
vexs[n];
float
arcs[n][n];
}
graph1;
creatgraph(){
graph1ga;
int
i,j,k;
float
w;
clrscr();
for(i=0;ivexs[i]=getchar();printf(“ok/n“);
for(i=0;iarcs[i][j]=0;
for(k=0;karcs[i][j]=w;
ga->arcs[j][i]=w;
}
printf(“ok/n“);
}
int
visited[n]={0};
dfs(i);
int
i;
{
int
j;
printf(“node:%c/n“,g.vexs[i]);
visited[i]=1;
for(j=0;j if(g.arc[i][j] &&(!visited[j])) df