21葛义杰 算法与数据结构实验册_算法与数据结构实验册
21葛义杰 算法与数据结构实验册由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“算法与数据结构实验册”。
金陵科技学院实验报告
学 生 实 验 报 告 册
课程名称：
学生学号：
所属院部：
（理工类）
算法与数据结构 专业班级：15计算机科学与技术（单）
1513902021 学生姓名： 葛义杰
计算机工程学院 指导教师： 章海鸥
2016 ——2017 学年 第 1 学期
金陵科技学院教务处制
金陵科技学院实验报告
实验报告书写要求
实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。
实验报告书写说明
实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。
填写注意事项
（1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。
（3）尽量采用专用术语来说明事物。
（4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。
实验报告批改说明
实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。
实验报告装订要求
实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。
金陵科技学院实验报告
实验项目名称： 顺序表 实验学时： 2 同组学生姓名： ╱ 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
金陵科技学院实验报告
实验1 顺序表
一、实验目的和要求
掌握顺序表的定位、插入、删除等操作。
二、实验仪器和设备
VC6.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.#include #define maxsize 20 typedef int datatype;typedef struct{ datatype data[maxsize];int last;}sequenlist;
void CreateList(sequenlist *L,int n){int i;printf(“please input n numbersn”);for(i=0;i
金陵科技学院实验报告
{ scanf(“%d”,&L->data[i]);(*L).last=n;} }
void PrintList(sequenlist *L,int n){int i;printf(“the sequenlist isn”);for(i=0;idata[i]);} main(){ int i,x;int n=10;sequenlist L;CreateList(&L,n);PrintList(&L,n);getchar();getchar();} 2.#include #define maxsize 100 typedef int datatype;typedef struct{ datatype data[maxsize];int last;}sequenlist;
void CreateList(sequenlist *L,int n){int i;printf(“请你输入数据元素：n”);for(i=0;i(*L).last)return-1;else return i;}
main(){ int i,x,a;int n;sequenlist L;L.last=0;printf(“请你输入顺序表的长度:n n=”);scanf(“%d”,&n);CreateList(&L,n);//调用顺序表的建立函数
金陵科技学院实验报告
// PrintList(&L,n);//调用顺序表的 打印输出函数 // printf(“n”);printf(“请输入要查找的数据元素X：nx=”);scanf(“%d”,&x);a=Seek(&L,x);if(a==-1)printf(“没有找到你所要找的数据元素！”);else {printf(“你所要查找的数据元素位置是：”);printf(“%d”,a);} getchar();getchar();} 3.#include #define maxsize 20 typedef int datatype;typedef
struct{ datatype data[maxsize];int last;}sequenlist;
void CreateList(sequenlist *L,int n){int i;printf(“请你输入数据元素：n”);for(i=0;i
{
scanf(“%d”,&(*L).data[i]);
}(*L).last=n-1;}
InsertaInteger(sequenlist *L,int c){
int i,j,m;
for(i=0;i
{
if(c
{m=i;break;}
}
(*L).last++;
for(j=(*L).last;j>=m;j--)
{
(*L).data[j+1]=(*L).data[j];
(*L).data[m]=c;
}
(*L).last++;
for(i=0;i
printf(“%d
”,(*L).data[i]);
}
main(){ int i,x;int a,c,n;sequenlist L;L.last=0;
金陵科技学院实验报告
printf(“请你输入顺序表的长度:n n=”);scanf(“%d”,&n);CreateList(&L,n);//调用顺序表的建立函数
printf(“n请输入你要插入的数据元素C：”);scanf(“%d”,&c);InsertaInteger(&L,c);getchar();getchar();} 4.#include #define maxsize 100 typedef int datatype;typedef struct{ datatype data[maxsize];int last;}sequenlist;void CreateList(sequenlist *L,int n){int i;printf(“请你输入数据元素：n”);for(i=0;i(*L).last)return-1;else return i;} void Deleate(sequenlist *L,int x){int i,j=0;
金陵科技学院实验报告
i=Get(&L,x);if(i==-1)printf(“你所要删除的元素不存在”);else { while(i
金陵科技学院实验报告
getchar();getchar();}
四、实验结果与分析（程序运行结果及其分析）1.2.3.4.金陵科技学院实验报告
五、实验体会（遇到问题及解决办法，编程后的心得体会）编程要求我们有足够的耐心，细细推敲。越着急可能就越无法得到我们想要的结果，遇到不会的问题要多多请教，知识是在实践与向别人请教的过程中积累的，所以问是至关重要的，只要肯下功夫很多东西都是可以完成的。
金陵科技学院实验报告
实验项目名称： 单链表 实验学时： 2 同组学生姓名： ╱ 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
金陵科技学院实验报告
实验2 单链表
一、实验目的和要求
1、实验目的掌握单链表的定位、插入、删除等操作。
2、实验要求
（1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。
（2）链表不能实现直接定位，一定注意指针的保存，防止丢失。
二、实验仪器和设备
Visual C++6.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。
解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。
（3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。
2、选做题
已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。
程序清单：
1.#include #include typedef struct node { int data;struct node *next;}linklist;
linklist *CREATLINKLISTR(){int a;linklist *head,*s,*r;head=NULL;r=NULL;printf(“请输入单链表的数据元素：n”);
金陵科技学院实验报告
scanf(“%d”,&a);while(a!=-1){ s=(linklist*)malloc(sizeof(linklist));s->data=a;if(head==NULL)head=s;else r->next=s;r=s;scanf(“%d”,&a);} if(r!=NULL)r->next=NULL;return head;}
void *PRINTLINKLIST(linklist *q){ while(q){ printf(“%d ”,q->data);q=q->next;} }
main(){linklist *p;p=CREATLINKLISTR();printf(“n”);printf(“你所输入的单链表为：n”);PRINTLINKLIST(p);getchar();getchar();} 2.#include #include typedef struct node { int data;struct node *next;}linklist;
linklist *CREATLINKLISTR(){int a;linklist *head,*s,*r;head=NULL;r=NULL;printf(“请输入单链表的数据元素(输入时数据元素递增)：n”);scanf(“%d”,&a);
金陵科技学院实验报告
while(a!=-1){ s=(linklist*)malloc(sizeof(linklist));s->data=a;if(head==NULL)head=s;else r->next=s;r=s;scanf(“%d”,&a);} if(r!=NULL)r->next=NULL;return head;}
void *PRINTLINKLIST(linklist *q){ while(q){ printf(“%d ”,q->data);q=q->next;} }
linklist *Insert(linklist *head,int x){linklist *s,*q;s=(linklist*)malloc(sizeof(linklist));s->data=x;q=head;if(q->data>x){ s->next=q;head=s;} else while(q!=NULL){ if(q->next->data>x){ s->next=q->next;q->next=s;break;}
金陵科技学院实验报告
q=q->next;} q=head;
PRINTLINKLIST(q);}
main(){linklist *p;int x;p=CREATLINKLISTR();printf(“你所建立的单链表为：n”);PRINTLINKLIST(p);printf(“n”);printf(“请输入在以上有序递增的单链表中插入数据x：n”);scanf(“%d”,&x);Insert(p,x);getchar();getchar();} 3.#include typedef struct node { int data;struct node *next;}linklist;
linklist *CREATLINKLISTR(){int a;linklist *head,*s,*r;head=(linklist*)malloc(sizeof(linklist));r=head;printf(“请输入单链表中的数据元素n”);scanf(“%d”,&a);while(a!=1){ s=(linklist*)malloc(sizeof(linklist));s->data=a;r->next=s;r=s;scanf(“%d”,&a);} r->next=NULL;
金陵科技学院实验报告
return head;}
void *PRINTLINKLIST(linklist *q){ while(q){ printf(“%d ”,q->data);q=q->next;} }
linklist *InverseLinklist(linklist *q){linklist *p,*head;p=head->next;if(p!=NULL){ p=p->next;head->next->next=NULL;} while(p!=NULL){ q=p->next;p->next=head->next;head->next=p;p=q;} printf(“n单链表被逆置后为n”);PRINTLINKLIST(head->next);} int main(){linklist *p;p=CREATLINKLISTR();// PRINTLINKLIST(p->next);InverseLinklist(p);getchar();getchar();}
四、实验结果与分析（程序运行结果及其分析）
1金陵科技学院实验报告
2.3.五、实验体会（遇到问题及解决办法，编程后的心得体会）
链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。链表不能实现直接定位，一定注意指针的保存，防止丢失。
金陵科技学院实验报告
实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： ╱ 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
金陵科技学院实验报告
实验3 堆栈和队列
一、实验目的和要求
（1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。
（3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。
二、实验仪器和设备
Visual C++6.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）判断一个算术表达式中开括号和闭括号是否配对。（2）测试“汉诺塔”问题。
（3）假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。
2、选做题
在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单：
1． 判断一个算术表达式中开括号和闭括号是否配对。#include #include typedef char datatype;#define maxsize 64 typedef struct {
datatype data[maxsize];int top;} seqstack;
int match(char exp[],int n){ char st[maxsize];//ÉèÖÃÒ»¸öÕ»£¬ÓÃÀ´´æ·ÅɨÃè±í´ïʽÖеÄÀ¨ºÅ
int top=-1,i=0,tag=1;while(i
if(exp[i]=='('||exp[i]=='['||exp[i]=='{')//Óöµ½'(''[''{',Ôò½«ÆäÈëÕ» {
top++;
st[top]=exp[i];
金陵科技学院实验报告
}
if(exp[i]==')')//Óöµ½')',ÈôÕ»¶¥ÊÇ'(',Ôò¼ÌÐø´¦Àí£¬·ñÔòÒÔ²»Åä¶Ô·µ»Ø
if(st[top]=='(')top--;
else tag=0;
if(exp[i]==']')
if(st[top]=='[')top--;
else tag=0;
if(exp[i]=='}')
if(st[top]=='{')top--;
else tag=0;
i++;} if(top>=0)tag=0;//ÈôÕ»²»¿Õ£¬Ôò²»Åä¶Ô return tag;}
main(){ int tag,i;char exp[7]={'(','+','(','2','-','4',')'};
printf(“ÇëÊäÈëÒ»¸öËãʽ±í´ïʽ£ºn”);
for(i=0;i
exp[i]=getchar();tag=match(exp,7);if(tag)
printf(“Ëãʽ±í´ïʽÖеĿªÀ¨ºÅºÍ±ÕÀ¨ºÅÅä¶Ô¡£”);else
printf(“Ëãʽ±í´ïʽÖеĿªÀ¨ºÅºÍ±ÕÀ¨ºÅ²»Åä¶Ô£¡”);getchar();getchar();}
2．#include
void move(char x,char z){printf(“%c-->”,x);printf(“%cn”,z);}
void Hanoi(int n,char x, char y,char z){ if(n==1)move(x,z);else {Hanoi(n-1,x,z,y);move(x,z);Hanoi(n-1,y,x,z);} }
main(){ int m;printf(“请你输入A上面的碟子总数”);scanf(“%d”,&m);Hanoi(m,'A','B','C');getchar();getchar();}
金陵科技学院实验报告
3．#include #include typedef struct { char data[10];int top;}seqstack;main(){int i;char a[9],b[9];int m;seqstack *s;s=(seqstack*)malloc(sizeof(seqstack));s->top=-1;printf(“请你输入8位的a字符串：n”);for(i=0;itop++;s->data[s->top]=a[i];i++;} //printf(“%d ”,i);i=7;while(s->top>=0){ b[i]=s->data[s->top];s->top--;i--;} b[8]='!';m=strcmp(a,b);//printf(“%d”,m);if(m==1)printf(“你所输入的字符串为回文！”);else printf(“你所输入的字符串不是回文！”);getchar();getchar();}
四、实验结果与分析（程序运行结果及其分析）．
金陵科技学院实验报告
2．3．
五、实验体会（遇到问题及解决办法，编程后的心得体会）
链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
金陵科技学院实验报告
实验项目名称： 串 实验学时： 2 同组学生姓名： ╱ 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
金陵科技学院实验报告
实验4 串
一、实验目的和要求
掌握串的存储及应用。
二、实验仪器和设备
Visual C++6.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。
（2）编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。
解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3）设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。
2、选做题
假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。
提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单：
1．#include #include
int seekfirst(char a[],char x){int i;for(i=0;i
main(){int location;char ch;char s[50];gets(s);scanf(“%c”,&ch);location=seekfirst(s,ch);
金陵科技学院实验报告
printf(“%d”,location);getchar();getchar();} 2．
#include #include
void seeklocation(char a[],char x){int i;for(i=0;i
main(){ char ch;char s[50];gets(s);scanf(“%c”,&ch);seeklocation(s,ch);getchar();getchar();} 3．
#include #include #include typedef struct linknode {char data;struct linknode *next;}linkstring;void DeleateSmallString(linkstring *head,int i,int k){linkstring *p,*h,*f;int m=1,n=1;p=head;while(p!=NULL){p=p->next;if(m==i-1){ h=p->next;break;
} m++;} while(h!=NULL){ h=h->next;n++;
if(n==k)
金陵科技学院实验报告
break;
}
p->next=h->next;f=head->next;while(f!=NULL){ printf(“%c”,f->data);f=f->next;
}
} main(){char ch;int i,k;linkstring *s,*head,*r,*q;
head=(linkstring*)malloc(sizeof(linkstring));r=head;ch=getchar();while(ch!='n'){ s=(linkstring *)malloc(sizeof(linkstring));s->data=ch;r->next=s;r=s;ch=getchar();
} r->next=NULL;q=head;printf(“输入位置和长度”);scanf(“%d%d”,&i,&k);printf(“%d %dn”,i,k);DeleateSmallString(q,i,k);
getchar();getchar();
}
四、实验结果与分析（程序运行结果及其分析）1．
2．金陵科技学院实验报告
3．五、实验体会（遇到问题及解决办法，编程后的心得体会）
在串顺序存储结构中，实现串操作的原操作为字符序列的复制串与线性表在逻辑结构上极为相似，区别仅在于串的数据对象约束为字符集 ；在基本操作上差别很大，线性表的基本操作大多数以单个元素作为操作对象，而串的基本操作通常以 串的整体 作为操作对象。两个串相等的充分必要条件是两个串的长度相等且各个对应位置的字符都相等。空串是指 不含任何字符的串，空格串是指仅含空格字符的串。
金陵科技学院实验报告
实验项目名称： 二叉树 实验学时： 2 同组学生姓名： ╱ 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
金陵科技学院实验报告
实验5 二叉树
一、实验目的和要求
（1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。
二、实验仪器和设备
Visual C++6.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。
（2）在第一题基础上，求二叉树中叶结点的个数。（3）在第一题基础上，求二叉树中结点总数。（4）在第一题基础上，求二叉树的深度。
2、选做题
已知一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。
解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单：
1．#include #include #define maxsize 20 typedef int datatype;typedef struct node{ datatype data;struct node *lchild,*rchild;}bitree;int m=0;//二叉树的建立函数
bitree *creattree()//建立二叉树，函数返回指向根的指针 {bitree *Q[maxsize];//队列Q为bitree指针类型的数组 char ch;
金陵科技学院实验报告
int front,rear;//队头队尾指针 bitree *root,*s;root=NULL;//置空二叉树 front=1;rear=0;//置空队列
ch=getchar();//输入第一个字符
while(ch!='n')//不是结束符的时候重复做 { s=NULL;if(ch!='@')//空格表示虚结点，不是虚结点时建立新的结点 { s=(bitree*)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;//rear是左孩子 else Q[front]->rchild=s;//孩子已处理完毕，出队列
if(rear%2==1)front++;} ch=getchar();// } return root;//} //前序遍历二叉树并计算二叉树的叶结点个数 void leaf(bitree *T){ if(T){ if(T->lchild==NULL&&T->rchild==NULL)m++;leaf(T->lchild);leaf(T->rchild);
将虚结点指针NULL或输入第一个结点为根孩子和双亲结点均不为偶数，新结点结点*Q[front]的两个输入下一个字符 返回头指针 金陵科技学院实验报告
} } //主函数 void main(){ bitree *L;printf(“建立的二叉树为：n”);L=creattree();leaf(L);printf(“二叉树叶节点个数为：n”);printf(“%d”,m);getchar();getchar();} 2．
#include #include #define maxsize 20 typedef int datatype;typedef struct node{ datatype data;struct node *lchild,*rchild;}bitree;
//二叉树的建立函数
bitree *creattree()//建立二叉树，函数返回指向根的指针 {bitree *Q[maxsize];//队列Q为bitree指针类型的数组 char ch;int front,rear;//队头队尾指针 bitree *root,*s;root=NULL;//置空二叉树 front=1;rear=0;//置空队列 ch=getchar();//输入第一个字符
while(ch!='n')//不是结束符的时候重复做
金陵科技学院实验报告
{ s=NULL;if(ch!='@')//空格表示虚结点，不是虚结点时建立新的结点 { s=(bitree*)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;//rear是左孩子 else Q[front]->rchild=s;//孩子已处理完毕，出队列 if(rear%2==1)front++;} ch=getchar();// } return root;//}
将虚结点指针NULL或输入第一个结点为根孩子和双亲结点均不为偶数，新结点结点*Q[front]的两个输入下一个字符 返回头指针 金陵科技学院实验报告
//二叉树的深度函数 int high(bitree *T){int m,n;if(T==NULL)return 0;else m=high(T->lchild);n=high(T->rchild);return((m>n?m:n)+1);} //主函数 void main(){int m;bitree *L;printf(“建立的二叉树为：n”);L=creattree();m=high(L);printf(“二叉树的高度为：n”);printf(“%d”,m);getchar();getchar();} 3．。
#include #include #define maxsize 20 typedef int datatype;typedef struct node{ datatype data;
金陵科技学院实验报告
struct node *lchild,*rchild;}bitree;int m=0;//二叉树的建立函数
bitree *creattree()//建立二叉树，函数返回指向根的指针 {bitree *Q[maxsize];//队列Q为bitree指针类型的数组 char ch;int front,rear;//队头队尾指针 bitree *root,*s;root=NULL;//置空二叉树 front=1;rear=0;//置空队列 ch=getchar();//输入第一个字符
while(ch!='n')//不是结束符的时候重复做 { s=NULL;if(ch!='@')//空格表示虚结点，不是虚结点时建立新的结点 { s=(bitree*)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;} rear++;Q[rear]=s;//将虚结点指针NULL或新结点地址入队
if(rear==1)root=s;//输入第一个结点为根结点 else
金陵科技学院实验报告
{if(s&&Q[front])//孩子和双亲结点均不是虚结点
if(rear%2==0)Q[front]->lchild=s;//rear为偶数，新结点是左孩子 else Q[front]->rchild=s;//结点*Q[front]的两个孩子已处理完毕，出队列 if(rear%2==1)front++;} ch=getchar();// } return root;//} //求二叉树的节点的总数 int sum(bitree *T){ int num1,num2;if(T==NULL)return 0;else if(T->lchild==NULL&&T->rchild==NULL)return 1;else { num1=sum(T->lchild);num2=sum(T->rchild);return(num1+num2+1);} } main(){int m;
输入下一个字符 返回头指针 金陵科技学院实验报告
bitree *L;printf(“建立的二叉树为：n”);L=creattree();m=sum(L);printf(“二叉树的结点总数为：n”);printf(“%d”,m);getchar();getchar();} 4．
#include #include #define maxsize 20 typedef int datatype;typedef struct node{ datatype data;struct node *lchild,*rchild;}bitree;
//二叉树的建立函数
bitree *creattree()//{bitree *Q[maxsize];// char ch;int front,rear;// bitree *root,*s;root=NULL;// front=1;rear=0;// ch=getchar();// while(ch!='n')//建立二叉树，函数返回指向根的指针队列Q为bitree指针类型的数组 队头队尾指针 置空二叉树 置空队列 输入第一个字符
不是结束符的时候重复做
金陵科技学院实验报告
{ s=NULL;if(ch!='@')//空格表示虚结点，不是虚结点时建立新的结点 { s=(bitree*)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;//rear是左孩子 else Q[front]->rchild=s;//孩子已处理完毕，出队列 if(rear%2==1)front++;} ch=getchar();// } return root;//}
将虚结点指针NULL或输入第一个结点为根孩子和双亲结点均不为偶数，新结点结点*Q[front]的两个输入下一个字符 返回头指针 金陵科技学院实验报告
//二叉树的深度函数 int high(bitree *T){int m,n;if(T==NULL)return 0;else m=high(T->lchild);n=high(T->rchild);return((m>n?m:n)+1);} //主函数 main(){int m;bitree *L;printf(“建立的二叉树为：n”);L=creattree();m=high(L);printf(“二叉树的高度为：n”);printf(“%d”,m);getchar();getchar();}
金陵科技学院实验报告
四、实验结果与分析（程序运行结果及其分析）1．
2．金陵科技学院实验报告
3．。
4．。
五、实验体会（遇到问题及解决办法，编程后的心得体会）
树是常用的数据结构。通过实验加深了我对树的遍历的认识，巩固了课本中所学的关于树的基本算法。按要求完成了实验内容。通过实验，有如下几点收获和体会：
1、通过实验还提高了一点改错能力，对于一些常见问题加深了印象。
2、编程需要细心，有时一个不注意小错误就能引出大问题。编程也需要规范，不仅为了他人能看得懂程序，也为了方便自己以后程序的更改与进一步的完善。
3、程序由算法和数据结构组成，一个好的程序不仅算法重要，数据结构的设计也很重要。4.二叉树的先序、中序与后序的输出都用了递归算法。而且用起来并不复杂，这使我更进一步学习理解了函数的递归调用并得到灵活的运用。经过本次实验基本上解决的一些所遇到的问题，我对二叉树的结构等有了较为深入的理解。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步。
金陵科技学院实验报告
实验项目名称： 图 实验学时： 2 同组学生姓名： ╱ 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
金陵科技学院实验报告
实验6 图
一、实验目的和要求
（1）熟练掌握图的基本概念、构造及其存储结构。
（2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。
二、实验仪器和设备
Visual C++6.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）构造一个无向图（用邻接矩阵表示存储结构）。
（2）对上面所构造的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。
2、选做题
采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。程序清单：
(1)#include #include typedef int datatype;#define maxsize 1024 #define n 100 typedef char VEXTYPE;typedef int ADJTYPE;typedef struct { VEXTYPE vexs[n];ADJTYPE arcs[n][n];int num;}GRAPH;
void GraphInit(GRAPH *L){ L->num=0;}
int GraphVexs(GRAPH *L){ return(L->num);}
金陵科技学院实验报告
void GraphCreate(GRAPH *L){ int i,j;GraphInit(L);printf(“请输入顶点数目：n”);scanf(“%d”,&L->num);printf(“请输入各顶点的信息：n”);for(i=0;inum;i++){
fflush(stdin);
scanf(“%c”,&L->vexs[i]);} printf(“请输入边权矩阵的信息：n”);for(i=0;inum;i++){
for(j=0;jnum;j++)
{
scanf(“%d”,&L->arcs[i][j]);
} } printf(“图已经创建完毕！”);}
void GraphOut(GRAPH L){ int i,j;printf(“n图的顶点数目为：%d”,L.num);printf(“n图的各顶点的信息为：n”);for(i=0;i
for(j=0;j
{
printf(“%6d”,L.arcs[i][j]);
}
printf(“n”);} printf(“图已经输出完毕！”);}
void main(){ GRAPH tu;GraphCreate(&tu);GraphOut(tu);system(“pause”);getchar();}(2)#include #include typedef int datatype;#define maxsize 1024
金陵科技学院实验报告
#define n 100 typedef char VEXTYPE;typedef int ADJTYPE;typedef struct { VEXTYPE vexs[n];ADJTYPE arcs[n][n];int num;}GRAPH;
void GraphInit(GRAPH *L){ L->num=0;}
int GraphVexs(GRAPH *L){ return(L->num);}
void GraphCreate(GRAPH *L){ int i,j;GraphInit(L);printf(“请输入顶点数目：n”);scanf(“%d”,&L->num);printf(“请输入各顶点的信息：n”);for(i=0;inum;i++){
fflush(stdin);
scanf(“%c”,&L->vexs[i]);} printf(“请输入边权矩阵的信息：n”);for(i=0;inum;i++){
for(j=0;jnum;j++)
{
scanf(“%d”,&L->arcs[i][j]);
} } printf(“图已经创建完毕！”);}
void GraphOut(GRAPH L){ int i,j;printf(“n图的顶点数目为：%d”,L.num);printf(“n图的各顶点的信息为：n”);for(i=0;i
for(j=0;j
{
printf(“%6d”,L.arcs[i][j]);
}
金陵科技学院实验报告
printf(“n”);} printf(“图已经输出完毕！”);}
void DFS(GRAPH g,int qidian,int mark[]){ int v1;mark[qidian]=1;printf(“%6c”,g.vexs[qidian]);for(v1=0;v1
mark[v]=0;} for(v=qidian;v
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);} } typedef int DATATYPE;typedef struct { DATATYPE data[maxsize];int front,rear;} SEQQUEUE;void QueueInit(SEQQUEUE *sq){ sq->front=0;sq->rear=0;} int QueueIsEmpty(SEQQUEUE sq){ if(sq.rear==sq.front)return(1);else return(0);} int QueueFront(SEQQUEUE sq,DATATYPE *e){ if(QueueIsEmpty(sq)){
printf(“queue is empty!n”);
return 0;}
金陵科技学院实验报告
else {
*e=sq.data[(sq.front)];
return 1;} } int QueueIn(SEQQUEUE *sq,DATATYPE x){ if(sq->front==(sq->rear+1)%maxsize){
printf(“queue is full!n”);
return 0;} else {
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);} } int QueueOut(SEQQUEUE *sq){ if(QueueIsEmpty(*sq)){
printf(“queue is empty!n”);
return 0;} else {
sq->front=(sq->front+1)%maxsize;
return 1;} } void BFS(GRAPH g,int v,int mark[]){ int v1,v2;SEQQUEUE q;QueueInit(&q);QueueIn(&q,v);mark[v]=1;printf(“%6c”,g.vexs[v]);while(QueueIsEmpty(q)==0){
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf(“%6c”,g.vexs[v2]);
}
} } } void GraphBFS(GRAPH g){
金陵科技学院实验报告
int qidian,v,v1,mark[maxsize];printf(“n广度优先遍历：”);printf(“n请输入起点的下标：”);scanf(“%d”,&qidian);for(v=0;v
mark[v]=0;} for(v=qidian;v
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);} }
void main(){ GRAPH tu;GraphCreate(&tu);GraphOut(tu);GraphDFS(tu);GraphBFS(tu);system(“pause”);getchar();}
金陵科技学院实验报告
四、实验结果与分析（程序运行结果及其分析）
1．金陵科技学院实验报告
2．五、实验体会（遇到问题及解决办法，编程后的心得体会）
这次的图的操作实验，与树的操作类似，但又比树复杂，包含更多的存储结构和遍历方法的操作，而且图的遍历需要沿着弧进行，以便输出弧上的信息。本实验中图的亢奋采用邻接表的存储结构，在输入图的信息时，首先要画出图的邻接表信息。图有两种遍历的形式，一种为深度优先搜索，一种为广度优先搜索。由于能力有限，没有能实现图的深度非递归优先搜索。本次实验基本完成了图的操作，也学到了很多关于图的知识和算法。
金陵科技学院实验报告
实验项目名称： 排序 实验学时： 2 同组学生姓名： ╱ 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
