算法与数据结构实验报告
学
生
实
验
报
告
册
课程名称:算法与数据结构
实验项目名称:
顺序表
实验学时:
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;i<=l、last;i++)
printf("%2d",l、data[i]); }
2、#define maxsize 100 typedef struct{
int data[maxsize];
int last; }sequenlist; main {
int x,i,s=1;
sequenlist l={{2,5,6,7,9,8,4,3},7};
printf("\nThe list is:");
for(i=0;i<=l、last;i++)
printf("%2d",l、data[i]);
printf("\nPlease input the number :");
scanf("%d",&x);
for(i=0;i<=l、last;i++)
if(l、data[i]==x)
{s=i;break;
}
printf("%d",s); } 3、#define maxsize 100 typedef struct{
int data[maxsize];
int last; }sequenlist; main {
int i,x,j;
sequenlist l={{1,3,5,6,7,9},5};
printf("\nThe list is:");
for(i=0;i<=l、last;i++)
printf("%2d",l、data[i]);
printf("\nInput the insert number:");
scanf("%d",&x);
for(i=1;i<=l、last;i++)
if(l、data[i1]>x) break;
for(j=l、last;j>=i1;j)
l、data[j+1]=l、data[j];
l、data[i1]=x;
l、last++;
printf("the list after insertion is:\n");
for(j=0;j<=l、last;j++)
printf("%3d",l、data[j]); } 4、#define maxsize 100 typedef struct{
int data[maxsize];
int last; }sequenlist; main{
int i,j,x=0,k=0;
sequenlist L={{1,3,5,7,2,4,6,8,2,9},9};
printf("\n The list is:");
for(i=0;i<=L、last;i++) printf("%3d",L、data[i]);
printf("\nPlease input a number x:");
scanf("%d",&x);
for(i=1;i<=L、last+1;i++)
if(L、data[i1]==x){
for(j=i;j<=L、last+1;j++) L、data[j1]=L、data[j];
L、last;
i;
k=1;
}
if(k==1){
printf("The list after deletion is:\n");
for(j=0;j<=L、last;j++) printf("%3d",L、data[j]);
}
else
printf("Not found!\n"); } 四、实验结果与分析(程序运行结果及其分析) 1、输出结果:The list is: 2 5 6 8 2 8 4 3 2、输出结果:The list is: 2 5 6 7 9 8 4 3
Please input the number:8
5 The list is: 2 5 6 7 9 8 4 3
Please input the number:1
1 3、输出结果:The list is: 1 3 5 6 7 9
Input the insert number:8
The list after insertion is:
1
3
5
6
7
8
9 4、输出结果:The list is:
1
3
5
7
2
4
6
8
2
9
Please input a number x:5
The list after deletion is:
1
3
7
2
4
6
8
2
9
The list is:
1
3
5
7
2
4
6
8
2
9
Please input a number x:11
Not found！
五、实验体会(遇到问题及解决办法,编程后得心得体会) 遇到问题:读取数据元素时,误将==写成=,导致错误。实验过程中,顺序表得赋值没有弄懂,以致输出多个 0 或者少输出。格式运算符也要正确控制,否则系统会停止工作。
实验体会:通过实验掌握了顺序表得基本操作,如初始化、插入、读取元素、删除等等。并了解到线性表顺序存储结构得特点,即逻辑关系上相邻得两个元素在物理位置上也相邻,然而从另一方面来瞧,在做插入与删除时需要移动大量元素。本次实验基本完成了实验要求得目得,顺序表得初始化,定义,插入,查找等,更好得了解了顺序表基本操作得算法,以及更直观得了解了数据结构在 C 语言环境下得体现。
实验项目名称:
单链表
实验学时:
2
同组学生姓名:
实验地点: 工科楼 A205
实验日期:
2013 年 10 月 23 日
实验成绩:
批改教师:
批改时间:
实验 2
单链表 一、实验目得与要求 1、实验目得 掌握单链表得定位、插入、删除等操作。
2、实验要求 (1)注意链表得空间就是动态分配得,某结点不用之后要及时进行物理删除,以便释放其内存空间。
(2)链表不能实现直接定位,一定注意指针得保存,防止丢失。
二、实验仪器与设备 Turbo C 2、0 三、实验内容与过程(含程序清单及流程图) 1、必做题 （1）
编写程序建立一个单链表,并逐个输出单链表中所有数据元素。
（2）
在递增有序得单链表中插入一个新结点 x,保持单链表得有序性。
解题思路:首先查找插入得位置然后进行插入操作;从第一个结点开始找到第一个大于该新结点值得结点即为插入位置;然后在找到得此结点之前插入新结点;注意保留插入位置之前结点得指针才能完成插入操作。
（3）
编写实现带头结点单链表就地逆置得子函数,并编写主函数测试结果。
2、选做题 已知指针 LA 与 LB 分别指向两个无头结点单链表得首元结点。要求编一算法实现,从表 LA 中删除自第 i 个元素起共 len 个元素后,将它们插入到表 LB中第 j 个元素之前。
程序清单: :
1、#include<stdlib、h> typedef int datattype; typedef struct node{
char data;
struct node *next; }linklist; main{
char ch;linklist *head,*s,*r,*p;
head=malloc(sizeof(linklist));
r=head;
scanf("%c",&ch);
while(ch!="$"){
s=malloc(sizeof(linklist));
s>data=ch;
r>next=s;
r=s;
scanf("%c",&ch);
}
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 node *next; }linklist; main{
int x,y;
linklist *head,*s,*r,*p,*q,*m,*n;
clrscr;
head=malloc(sizeof(linklist));
r=head;
printf("input the order numbers :");
scanf("%d",&x);
while(x!=0){
s=malloc(sizeof(linklist));
s>data=x;
r>next=s;
r=s;
scanf("%d",&x);
}
r>next=NULL;
printf("Please input the insert value:");
scanf("%d",&y);
p=head>next;
while(p!=NULL){
if (p>data<y) p=p>next;
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 node *next; }linklist; main{
int a;
linklist *head,*s,*r,*p,*q,*t;
clrscr;
head=malloc(sizeof(linklist));
r=head;
printf("Input some numbers:");
scanf("%d",&a);
while(a!=0){
s=malloc(sizeof(linklist));
s>data=a;
r>next=s;
r=s;
scanf("%d",&a);
}
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 && s、top==0) printf("Match!\n");
else if(result==1) printf("Missing left!\n");
else if(s、top>0) printf("Missing right!\n"); } 2、#include<stdio、h> 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(n1,a,c,b);
printf("\n Move disk %d from pile %c to pile %c",n,a,c);
hanoi(n1,b,a,c);
} } void main{
int n;
clrscr;
printf("\n Please enter the number of disks to be moved:");
scanf("%d",&n);
hanoi(n,"A","B","C"); } 3、#include<stdio、h> #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<n/2;i++){
s、top++;
s、data[s、top]=str[i];
}
i=i1;
if(n%2==0)
i++;
else
i=i+2;
while(i<n && s、data[s、top]==str[i]){
i++;
s、top;
}
if(i==n) printf("Yes\n");
else printf("No\n"); } 四、实验结果与分析(程序运行结果及其分析) 1、输入:(a) 输出结果:Match！
输入:(a 输出结果:Missing right！
输入:a) 输出结果:Missing left！
2、输入:3
输出结果:Move disk 1 from pile A to pile C Move disk 2 from pile A to pile B Move disk 1 from pile C to pile B Move disk 3 from pile A to pile C Move disk 1 from pile B to pile A Move disk 2 from pile B to pile C Move disk 1 from pile A to pile C 3、输入:qwewq
输出结果:Yes
输入:qwerewr
输出结果 No 五、实验体会(遇到问题及解决办法,编程后得心得体会) 遇到问题:在本章栈与队列中编程,有许多得if语句,编写时一不小心就会少加一个花括号,以致编写不成功。在本章汉诺塔问题中,使用了栈以及函数得递归,这其中得过程一直不就是很了解,在经过老师得讲解后,理解了大致过程。
实验体会:递归函数就是编程中经常会用到得一种函数,它可以实现许多我们在平时言语与解释上解决不了得问题,我们需要理解并且可以熟练得使用它,这对我们之后得编程会有很大得帮助。而汉诺塔利用栈就是一种很经典得递归得算法,这让我们理解栈与递归。
实验项目名称:
串
实验学时:
2
同组学生姓名:
实验地点:
工科楼 A205 实验日期:
2013 年 11 月 6 日
实验成绩:
批改教师:
批改时间:
实验 4
串 一、实验目得与要求 掌握串得存储及应用。
二、实验仪器与设备 Turbo C 2、0 三、实验内容与过程(含程序清单及流程图) 1、必做题 （1）
编写输出字符串 s 中值等于字符 ch 得第一个字符得函数,并用主函数测试结果。
（2）
编写输出字符串 s 中值等于字符 ch 得所有字符得函数,并用主函数测试结果。
解题思路:可以将第一题程序改进成一个子函数,在本题中循环调用。
（3）
设字符串采用单字符得链式存储结构,编程删除串 s 从位置 i 开始长度为 k 得子串。
2、选做题 假设以链结构表示串,编写算法实现将串 S 插入到串 T 中某个字符之后,若串T 中不存在这个字符,则将串 S 联接在串 T 得末尾。
提示:为提高程序得通用性,插入位置字符应设计为从键盘输入。
程序清单: :
1、#define maxsize 100 typedef struct{
char ch[maxsize];
int curlen; }seqstring; main{
int i;
char ch;
seqstring s={{"asdfghg"},6};
for(i=0;i<s、curlen;i++)
printf("%c",s、ch[i]);
printf("\nPlease input aa character ch:");
scanf("%c",&ch);
for(i=0;i<s、curlen;i++)
if(s、ch[i]==ch){
printf("ch=s、ch[%d]=%c\n",i,s、ch[i]);
break;
}
if(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<s、curlen;i++)
printf("%c",s、ch[i]);
printf("\nPlease input aa character ch:");
scanf("%c",&ch);
for(i=0;i<s、curlen;i++)
if(s、ch[i]==ch){
printf("ch=s、ch[%d]=%c\n",i,s、ch[i]);
flag++;
}
if(flag==0)
printf("Not find!\n"); } 3、#include<stdio、h> #include<stdlib、h> typedef struct linknode{
char data;
struct linknode *next; }linkstring; main{
linkstring *head,*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",&b,&l);
if(b>k1||b+l>k){
printf("Error!\n"); return;
}
p=head;
for(i=0;i<b1;i++){
p=p>next;
}
printf("%c %d %d %d \n",p>data,b,l,k);
for(i=b1;i<b+l1;i++){
q=p>next;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<stdio、h> #include<stdlib、h> #define maxsize 100 typedef struct node{
char data;
struct node *lchild,*rchild; }bitree; bitree *Q[maxsize]; bitree *Creatree{
char ch;
int front,rear;
bitree *root,*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 && Q[front])
if(rear%2==0) Q[front]>lchild=s;
else
Q[front]>rchild=s;
if(rear%2==1) front++;
}
ch=getchar;
}
return root; } void preorder(t) bitree *t; {
if(t) {
printf("%c",t>data);
preorder(t>lchild);
preorder(t>rchild);
} } void inorder(t) bitree *t; {
if(t){
inorder(t>lchild);
printf("%c",t>data);
inorder(t>rchild);
} } void postorder(t) bitree *t; {
if(t){
postorder(t>lchild);
postorder(t>rchild);
printf("%c",t>data);
} } main{
bitree *root;
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<stdio、h> #include<stdlib、h> #define maxsize 100 typedef struct node{
char data;
struct node *lchild,*rchild; }bitree; bitree *Q[maxsize]; bitree *Creatree{
char ch;
int front,rear;
bitree *root,*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 && Q[front])
if(rear%2==0) Q[front]>lchild=s;
else
Q[front]>rchild=s;
if(rear%2==1) front++;
}
ch=getchar;
}
return root; } int left(bitree *t){
int num1,num2;
if(t==NULL) return 0;
else if(t>lchild==NULL && t>rchild==NULL)
return 1;
else{
num1=left(t>lchild);
num2=left(t>rchild);
return(num1+num2);
} } main{
bitree *root;
clrscr;
root=Creatree;
printf("lefts is %d\n",left(root)); }? (3)#include<stdio、h> #include<stdlib、h> #define maxsize 100 typedef struct node{
char data;
struct node *lchild,*rchild; }bitree; bitree *Q[maxsize]; bitree *Creatree{
char ch;
int front,rear;
bitree *root,*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 && Q[front])
if(rear%2==0) Q[front]>lchild=s;
else
Q[front]>rchild=s;
if(rear%2==1) front++;
}
ch=getchar;
}
return root; } int nodes(bitree *t){
int num1,num2;
if(t==NULL) return 0;
else if(t>lchild==NULL &&t>rchild==NULL) return 1;
else{
num1=nodes(t>lchild);
num2=nodes(t>rchild);
return (num1+num2+1);
} } main{
bitree *root;
clrscr;
root=Creatree;
printf("nodes is %d\n",nodes(root)); }? (4)#include<stdio、h> #include<stdlib、h> #define maxsize 100 typedef struct node{
char data;
struct node *lchild,*rchild; }bitree; bitree *Q[maxsize]; bitree *Creatree{
char ch;
int front,rear;
bitree *root,*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 && Q[front])
if(rear%2==0) Q[front]>lchild=s;
else
Q[front]>rchild=s;
if(rear%2==1) front++;
}
ch=getchar;
}
return root; } int depth(bitree *t){
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{
bitree *root;
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: abc# preorder is:abc inorder is:abc postorder is:cba (2)Now Creat the bitree,input baseing the order top to bottom,left to right: abc# lefts is 1 (3)Now Creat the bitree,input baseing the order top to bottom,left to right: abc# nodes is 3 (4)Now Creat the bitree,input baseing the order top to bottom,left to right: abc# 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<stdio、h> #define n 6 #define e 8 typedef struct {
char vexs[n];
float arcs[n][n]; } graph1; creatgraph{
graph1 *ga;
int i,j,k;
float w;
clrscr;
for(i=0;i<n;i++)
ga>vexs[i]=getchar;printf("ok\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ga>arcs[i][j]=0;
for(k=0;k<e;k++){
scanf("%d%d%f",&i,&j,&w);
ga>arcs[i][j]=w;
ga>arcs[j][i]=w;
}
printf("ok\n");
} main{
creatgraph; } (2)#include<stdio、h> #define n 3 #define e 2 typedef struct {
char vexs[n];
float arcs[n][n]; } graph1; creatgraph{
graph1 *ga;
int i,j,k;
float w;
clrscr;
for(i=0;i<n;i++)
ga>vexs[i]=getchar;printf("ok\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ga>arcs[i][j]=0;
for(k=0;k<e;k++){
scanf("%d%d%f",&i,&j,&w);
ga>arcs[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<n;j++)
if(g、arc[i][j] &&(!visited[j])) dfs(j); } typedef struct{
int data[10];
int front,read; }sequeue; sequeue Q; bfs(i){
int i,j;
Q、front=1;Q、rear=1;
printf("%c\n",g、vexs[k]);
visited[k]=1;
Q、data[++Q、rear]=k;
while(Q、front!=Q、rear){
Q、front++;
i=Q、front1;
for(j=0;j<n;j++)
if(g、arcs[i][j] && (!visited[j])){
printf("%c\n",g、vexs[j]);
visited[j]=1;
Q、data[++Q、rear]=j;
}
} } main{
creatgraph; dfs(1);
bfs(0); } 四、实验结果与分析(程序运行结果及其分析) 1(1)abcdef ok 1 2 11 1 3 12 0 1 15 0 2 16 0 3 45 0 4 15 2 3 55 3 4 55 ok
(2)abc ok 0 1 11 0 2 12 ok
深度优先:abc
广度优先:abc 五、实验体会(遇到问题及解决办法,编程后得心得体会) 遇到问题:这一章编写得极其得不顺利,首先在理论上我认为就是正确得程序在运行时却一次次得出现 error 与 warning,让我这章内容进行了两次课时。耽误了下一章得编写。首先就是在文档中编写时,首字母自动大写而没有发现,其次就是有 clrscr 这个函数但就是头文件却忘记写了,然后老师批评最严重得一个问题就是没有标志语言,这章图得编写即使输入进去也不会显示出来,因此应该添加标志语言。
实验体会:在编写时需要认真对待,认真检查 C 语言语法以及在编写时有可能忘记得内容。最重要得就是在一些程序中,需要添加标志语言,不能因为完成了就就是完成了,需要简明易懂给人提示。
实验项目名称:
排序
实验学时:
2
同组学生姓名:
实验地点:工科楼 A205
实验日期:
2013 年 11 月 27 日
实验成绩:
批改教师:
批改时间:
实验 7
排序 一、实验目得与要求 (1)熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序与基数排序得基本概念。
(2)掌握以上各种排序得算法。区分以上不同排序得优、缺点。
二、实验仪器与设备 Turbo C 2、0 三、实验内容与过程(含程序清单及流程图) 1、必做题 用随机数产生 100000 个待排序数据元素得关键字值。测试下列各排序函数得机器实际执行时间(至少测试两个):直接插入排序、希尔排序(增量为4,2,1)、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序与基于链式队列得基数排序。
2、选做题 假设含 n 个记录得序列中,其所有关键字为值介于 v 与 w 之间得整数,且其中很多关键字得值就是相同得。则可按如下方法排序:另设数组number[v…w],令 number[i]统计关键字为整数 i 得纪录个数,然后按 number重排序列以达到有序。试编写算法实现上述排序方法,并讨论此种方法得优缺点。
程序清单: :
1(1)#include<time、h> #include<stdio、h> #include<dos、h> #include<stdlib、h> #include<conio、h> #define M 20000 typedef struct{
int a[M];
int key; }sequenlist; main{
int i,j,k,temp;
sequenlist L;
time_t first,second;
clrscr;
first=time(NULL);
randomize;
for(i=0;i<M1;i++) L、a[i]=rand%1000;
for(i=0;i<M2;i++){
for(j=M1;j>=i;j)
if(L、a[j+1]<L、a[j]){
temp=L、a[j+1];
L、a[j+1]=L、a[j];
L、a[j]=temp;
}
}
second=time(NULL);
printf("The differece is %f second",difftime(second,first));
getch;
return 0; } (2)#include<time、h> #include<stdio、h> #include<dos、h> #include<stdlib、h> #include<conio、h> #define M 20000 typedef struct{
int a[M];
int key; }sequenlist; main{
int i,j,k,temp;
sequenlist L;
time_t first,second;
clrscr;
first=time(NULL);
randomize;
for(i=0;i<M1;i++) L、a[i]=rand%1000;
for(i=0;i<M1;i++){
k=i;
for(j=i+1;j<M;j++)
if(L、a[j]<L、a[k]) k=j;
if(k!=i){
temp=L、a[i];
L、a[i]=L、a[k];
L、a[k]=temp;
}
}
second=time(NULL);
printf("The differece is %f second",difftime(second,first));
getch;
return 0; } 四、实验结果与分析(程序运行结果及其分析) 1.(1)The differece is 2、000000 second
(2)The differece is 1、000000 second 五、实验体会(遇到问题及解决办法,编程后得心得体会) 实验体会:直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序与基于链式队列得基数排序。这几种排序各有优缺点,但就是总就是将这几个弄混,在瞧书后得以解决。在这几种排序中:若只从存储空间考虑,则应首先选取堆排序方法,其次选取快速排序方法,最后选取归并排序方法; 若只从排序结果得稳定性考虑,则应选取归并排序方法;若只从平均情况下最快考虑,则应选取快速排序方法;若只从最坏情况下最快并且要节省内存考虑,则应选取堆排序方法。
实验项目名称:
查找
实验学时:
2
同组学生姓名:
实验地点:工科楼 A205
实验日期:
2013 年 12 月 4 日
实验成绩:
批改教师:
批改时间:
实验 8
查找 一、实验目得与要求 (1)掌握顺序表查找、有序表查找、索引顺序表查找得各种算法。
(2)掌握哈希表设计。
二、实验仪器与设备 Turbo C 2、0 三、实验内容与过程(含程序清单及流程图) 1、必做题 （1）
在一个递增有序得线性表中利用二分查找法查找数据元素 X。
2、选做题 （2）
构造一个哈希表,哈希函数采用除留余数法,哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。
提示:构造哈希表只就是完成查找得第一步,大家应该掌握在哈希表上进行查找得过程,可以试着编程序实现。
程序清单: :
1.#define maxsize 100 typedef struct{
int data[maxsize];
int last; }sequenlist; main{
int i,low,mid,high,x;
sequenlist L={{1,3,5,7,7,11,15,23},8};
for(i=0;i<L、last;i++) printf("%3d",L、data[i]);
printf("\n Now please input a number for looking:");
scanf("%d",&x);
low=0;high=L、last;
while(low<=high){
mid=(low+high)/2;
if(x==L、data[mid]){
printf("Find the number %d\n",L、data[mid]);
break;
}
if(x<L、data[mid]) high=mid1;
else low=mid+1;
}
if(low>high) printf("Not Find\n"); }
四、实验结果与分析(程序运行结果及其分析) 1.
1
3
5
7
7 11 15 23
Now please input a number for looking:7 Find the number 7
1
3
5
7
7 11 15 23
Now please input a number for looking:12 Not Find 五、实验体会(遇到问题及解决办法,编程后得心得体会) 实验体会:本章规定要使用二叉查找法查找元素,并没有太大难度,需要有三个指示器,分别就是:low,high 与 mid。这种查找只适用于顺序存储结构。