数据结构随堂实验
实验报告
指导教师：
姓名：
学号：
班级：
专业：计算机科学与技术
目录
C语言结构体与指针. 1
线性顺序表的实现及操作. 3
串的匹配与替换. 6
线性链表的实现及操作. 8
栈和队列的应用. 13
二叉树的实现及遍历. 21
图的实现及遍历. 27
查找算法的实现及比较. 33
C语言结构体与指针
指导教师： 实验时间：第六周 星期三 九十节
学院： 计算机科学与技术学院 专业： 计算机科学与技术
班级： 学号： 姓名： 实验室：
实验目的：
巩固复习前期所学c语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。
实验内容及步骤：
学生信息的显示，具体要求如下：
² 定义一个结构体描述学生信息(学号，姓名，性别，年龄，住址)；
² 设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型；
² 设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于5人）。
示例程序：
#include "stdio.h"
typedef struct Student
{
int Snum;
char Sname[10];
char Sx[2];
int Sage;
char Sid[10];
}std;
void display(std x)
{
printf("%d\n",x.Snum);
printf("%s\n",x.Sname);
printf("%s\n",x.Sx);
printf("%d\n",x.Sage);
printf("%s\n",x.Sid);
}
void main()
{
std a[5];
printf("请输入学生信息：学号 姓名 性别 年龄 住址\n");
for(int i=0;i<2;i++)
scanf("%d%s%s%d%s",&a[i].Snum,&a[i].Sname,&a[i].Sx,&a[i].Sage,&a[i].Sid);
for(i=0;i<2;i++)
display(a[i]);
}
程序结果：
心得体会：
本次实验是以后所有实验的基础，是对过去所学知识的巩固加深。通过本次实验，我对之前所学的C语言函数参数传递、指针和结构体等知识要点有了进一步实践，加深了我对些知识点的理解和运用。
线性顺序表的实现及操作
指导教师： 实验时间：第七周 星期三 九十节
学院： 计算机科学与技术学院 专业： 计算机科学与技术
班级： 学号： 姓名： 实验室：
实验目的：
1) 掌握建立线性顺序表的基本方法。
2) 理解和掌握线性顺序表元素查找算法。
3) 掌握线性顺序表的插入、删除算法的思想和实现。
实验内容：
1) 建立一个线性顺序表，要求从键盘输入10个整数，并将该线性顺序表的元素从屏幕显示出来；
2) 编写查找函数，在上面的线性顺序表中查找其中一个元素，如果找到，返回该元素在线性顺序表中的位置和该元素的值，否则提示无此元素。要求被查找元素从键盘输入。
3) 编写插入和删除函数，由用户输入待插入元素及插入位置，将完成插入后的线性顺序表输出；由用户输入删除第几个元素，将完成删除后的线性顺序表输出。
示例程序：
#include "stdio.h"
#include "stdlib.h"
#define Listsize 3
typedef struct
{
int *elem;
int length;
}Sqlist;
void Initlist(Sqlist &L)
{
L.elem=(int *)malloc(Listsize*sizeof(int));
L.length=0;
}
void check(Sqlist L,int i)
{
if (i>2)printf("顺序表中没有此数\n");
else{
printf("该元素的值为%d\n",L.elem[--i]);
printf("该元素的下标为%d\n",i);
}
}
void addnum(Sqlist L,int i,int num)
{ if(num==3)L.elem[2]=i;
else for(int a=1;a>=num-1;--a)
L.elem[a+1]=L.elem[a];
L.elem[num-1]=i;
printf("插入后的线性表为：\n");
for(i=0;i<3;i++)
printf("%d\n",L.elem[i]);
}
void deletenum(Sqlist L,int num)
{ if(num==3);
else { for(int a=num-1;a<3;a++)
L.elem[a]=L.elem[a+1];}
printf("删除后的线性表为：\n");
for(int i=0;i<2;i++)printf("%d\n",L.elem[i]);
}
void main()
{
Sqlist L;
int num;
Initlist(L);
printf("请输入2个数：\n");
for(int i=0;i<2;i++)
scanf("%d",&L.elem[i]);
printf("您输入的数字是：\n");
for(i=0;i<2;i++)
printf("%d\n",L.elem[i]);
printf("您要查找第几个元素?：\n");
scanf("%d",&i);
check(L,i);
printf("要插入的值和位数？:\n");
scanf("%d%d",&i,&num);
addnum(L,i,num);
printf("要删除第几个元素？：\n");
scanf("%d",&num);
deletenum(L,num);
}
程序结果：
心得体会：
用了很多时间在编程上，主要是因为C语言基础不好，特别是对于C语言中链表的一些定义和基本操作不够熟练，导致在编程过程中还要不断的拿着C语言的教材查找，所以今后还要对C语言多练习，多动手，多思考。 数据结构有很强的逻辑性，因此我认为如果在上机之前先把逻辑搞清楚很重要，不管是对算法的设计还是对程序的调试都有很大帮助。 经过上机实践，我认为实践课很重要。理论课只是纸上谈兵，只是被动地接受，而实践课上能将学过的知识利用起来，同时还有一些东西只能是自己上机实践才能慢慢探索出的。
串的匹配与替换
指导教师： 实验时间：第八周 星期三 九十节
学院： 计算机科学与技术学院 专业： 计算机科学与技术
班级： 学号： 姓名： 实验室：
实验目的：
1) 掌握串存储结构；
2) 掌握串的匹配算法，并能进行相关应用。
实验内容：
设串采用静态数组存储结构，编写函数实现串的替换Replace(S，start，T，V)，即要求在主串S中从位置start开始查找是否存在子串T。若存在，则用子串V去替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。要求设计主函数进行测试 。
示例程序：
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int Replace(char *S,int start,char *T,char *V)
{
char *p=NULL, *a,*b;
p = strstr(&S[start],T);
if(p)
{
int pl=strlen(p),tl=strlen(T),vl=strlen(V);
if( pl>tl ) memmove(p+vl,p+tl,pl-tl+1);
a=p;b=V;
for(; *V ; ++V, ++p ) *p = *V;
if( pl==tl ) return(1);
Replace(a+vl,0,T,b);
return(1);
}
else return(0);
}
int main()
{
static char S[20];
char T[10],V[10];
int start;
printf("请输入字符串：\n");
gets(S);
printf("输入要查询的字串:\n");
gets(T);
printf("输入要替换的子串:\n");
gets(V);
printf("从第几位开始查询？:\n");
scanf("%d",&start);
if( Replace(S,start-1,T,V) ) printf("%s\n",S);
else printf("没找到该子串\n");
return(0);
}
程序结果：
心得体会：
在课堂上我对串的知识掌握得不是很好，通过本次实验，我也遇到很多困难，通过在网上搜集资料、请教同学，我渐渐对这部分知识有了更深更生动地理解。对于串的存储结构、串的匹配算法以及相应的查询替换，我也能较为熟练的操作。这再一次证明实践对课堂上学到的知识有着巩固加深的作用，在学习过程是必不可少的。
线性链表的实现及操作
指导教师： 实验时间：第九周 星期三 九十节
学院： 计算机科学与技术学院 专业： 计算机科学与技术
班级： 学号： 姓名： 实验室：
实验目的：
1) 深入理解线性链表的逻辑结构和链式存储结构；
2) 掌握线性链表的基本操作及应用；
3) 培养学生灵活使用结构解决实际问题的能力。
实验内容：
设计一个 100 位以内的长整数加减运算的程序。要求如下：
² 输入输出要求：每四位一组，组间用逗号分隔；
² 加和减分别用不同的程序实现；
² 程序应考虑输入数据的符号示例程序：
示例程序：
#include “stdio.h”
#include “stdlib.h”
#include “string.h”
typedef struct node{
int n;
struct node *next;
struct node *prev;
} node;
int conv(char *a)
{
int n=0,i;
for(i=0;a[i];++i)
{
n*=10;
n+=(a[i]-'0');
}
return n;
}
int main()
{
char num1[200],num2[200];
char c[2];
int i,f;
node *q,*p;
p=(node*)malloc(sizeof(node));
p->next=p->prev=0;
q=p;
num1[0]=num2[0]=',';
printf("Enter num 1:\n");
scanf("%s",num1+1);
for(i=strlen(num1);i>=0;--i)
{
if(num1[i]==',')
{
num1[i]=0;
q->next=(node*)malloc(sizeof(node));
q->next->prev=q;
q->next->next=0;
q=q->next;
q->n=conv(num1+i+1);
}
}
q->next=p;
p->prev=q;
printf("Enter op:\n");
scanf("%s",c);
c[0]=c[0]=='+'?0:1;
printf("Enter num 2:\n");
scanf("%s",num2+1);
q=p;f=0;
if(!*c) //+
{
for(i=strlen(num2);i>=0;--i)
{
if(num2[i]==',')
{
num2[i]=0;
if(q->next==p)
{
q->next=(node*)malloc(sizeof(node));
q->next->next=p;
q->next->prev=q;
q->next->n=0;
p->prev=q->next;
}
q=q->next;
q->n+=(conv(num2+i+1)+f);
if(q->n<10000)
f=0;
else
{
f=1;
q->n-=10000;
}
}
}
if(f)
{
if(q->next==p)
{
q->next=(node*)malloc(sizeof(node));
q->next->next=p;
q->next->prev=q;
q->next->n=1;
}
else
{
while(q->next!=p)
{
q=q->next;
q->n+=1;
if(q->n<10000)
{
f=0;
break;
}
else
{
q->n=0;
f=1;
}
}
if(f)
{
q->next=(node*)malloc(sizeof(node));
q->next->next=p;
q->next->prev=q;
q->next->n=1;
}
}
}
printf("%d,",p->prev->n);
for(q=p->prev->prev;q!=p;q=q->prev)
printf("%04d,",q->n);
}
else //-
{
for(i=strlen(num2);i>=0;--i)
{
if(num2[i]==',')
{
num2[i]=0;
if(q->next==p)
{
q->next=(node*)malloc(sizeof(node));
q->next->next=p;
q->next->prev=q;
q->next->n=0;
p->prev=q->next;
}
q=q->next;
q->n-=(conv(num2+i+1)+f);
if(q->n>=0)
f=0;
else
{
f=1;
q->n+=10000;
}
}
}
if(f)
{
if(q->next==p)
{
q->n-=10000;
}
else
{
while(q->next!=p)
{
q=q->next;
q->n-=1;
if(q->n>=0)
{
f=0;
break;
}
else
{
q->n+=10000;
f=1;
}
}
if(f)
{
q->n-=10000;
}
}
}
printf("%d,",p->prev->n);
for(q=p->prev->prev;q!=p;q=q->prev)
printf("%04d,",q->n);
}
return 0;
}
程序结果：
心得体会：
通过本次实验，我对线性链表有了更深的理解，同时也对其与线性顺序表的优势劣势有了更生动地体会。在实验过程中有很多代码不熟悉，需要花费很多时间翻书、查资料，最后还调试了很久。在以后的学习中我还要加强写代码的能力，不能只有理论知识。
栈和队列的应用
指导教师： 实验时间：第十周 星期三 九十节
学院： 计算机科学与技术学院 专业： 计算机科学与技术
班级： 学号： 姓名： 实验室：
实验目的：
掌握栈与队列的基本结构和操作方法，培养学生灵活使用结构解决实际问题的能力。
实验内容：
1)利用栈深度优先进行迷宫求解。
用数组表示迷宫;
建立栈，利用栈实现深度优先搜索
2)利用队列宽度优先进行迷宫求解。
用数组表示迷宫;
建立队列，利用队列实现宽度优先搜索
示例程序：
#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;
struct step //定义一个栈
{
int x,y,n; //x，y表示步子坐标，n表示步数
};
void change(char **maze,int hang,int lie)
{
for(int i=0;i<hang+2;i++)
{
for(int j=0;j<lie+2;j++)
switch(maze[i][j])
{
case '1':
maze[i][j]='#';
break;
case '+':
case '0':
case '.':
maze[i][j]=' ';
break;
}
}
}
void step_to_step(char **maze,step *Step,int hang,int lie,int n)
{ //单步输出
for(int k=0;k<=n;k++)
{
for(int i=0;i<hang+2;i++)
{
for(int j=0;j<lie+2;j++)
{
if(Step[k].x==i&&Step[k].y==j)
cout<<"."<<" ";
else cout<<maze[i][j]<<" ";
}
cout<<endl;
}
cout<<"这是第"<<k+1<<"步"<<endl<<endl;
getch();
}
}
void out(char **maze,int hang,int lie,int i,int j) //输出所走的路程
{
if(i==1&&j==1) //若回到原点则表明无出路
{
cout<<endl;
cout<<"************************************************************"<<endl;
cout<<"|-------------此迷宫没有出路，所走路线如下图---------------|"<<endl;
cout<<"************************************************************"<<endl;
}
else //否则有出路
{
cout<<endl;
cout<<"************************************************************"<<endl;
cout<<"|----------------找到迷宫出路，如图所示--------------------|"<<endl;
cout<<"************************************************************"<<endl;
}
for(i=0;i<hang+2;i++) //输出步子
{
for(j=0;j<lie+2;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
}
void cure(char **maze,int hang,int lie)
{
int i=1,j=0,n=-1;
char Q;
step *Step; //定义一个存储路程的栈
Step=new step [hang*lie]; //事先给其分配一定的空间，[hang*lie]表示空间足够
if(maze[1][1]=='1')
{
cout<<"进不去!!!"<<endl<<endl;
getch();
exit(0);
}
else while(maze[hang][lie]!='.') //由右、下、左、上的顺序判断是否走通
{ //'1'表示走不通，'+'表示已经走过但不通又回来的步子，'.'表示已经走过并通了的步子
if(maze[i][j+1]!='1'&&maze[i][j+1]!='.'&&maze[i][j+1]!='+')
{
if(i==1&&j==0)
{
cout<<"入口"<<endl;
}
else
cout<<"右"<<endl;
maze[i][j+1]='.';
j=j+1;
n++;
Step[n].x=i;
Step[n].y=j;
cout<<i<<","<<j;
}
else if(maze[i+1][j]!='1'&&maze[i+1][j]!='.'&&maze[i+1][j]!='+')
{
cout<<"下"<<endl;
maze[i+1][j]='.';
i=i+1;
n++;
Step[n].x=i;
Step[n].y=j;
cout<<i<<","<<j;
}
else if(maze[i][j-1]!='1'&&maze[i][j-1]!='.'&&maze[i][j-1]!='+')
{
cout<<"左"<<endl;
maze[i][j-1]='.';
j=j-1;
n++;
Step[n].x=i;
Step[n].y=j;
cout<<i<<","<<j;
}
else if(maze[i-1][j]!='1'&&maze[i-1][j]!='.'&&maze[i-1][j]!='+')
{
cout<<"上"<<endl;
maze[i-1][j]='.';
i=i-1;
n++;
Step[n].x=i;
Step[n].y=j;
cout<<i<<","<<j;
}
else //若走不通则返回上一步
{
if(i==1&&j==1) //当回到入口时，说明无通路，结束循环
break;
else
{
maze[i][j]='+'; //将走不通的点置为+
n--;
i=Step[n].x; //返回上一个点
j=Step[n].y;
cout<<"返回"<<endl<<i<<","<<j; //输出返回信息
}
}
if(i==hang&&j==lie)
cout<<"(出口)"<<" "<<"(共"<<n+1<<"步"<<")";
}
out(maze,hang,lie,i,j);
cout<<endl<<endl<<endl;
cout<<"是否单步输出(y/n):";
cin>>Q;
cout<<endl<<endl;
if(Q=='y')
{
change(maze,hang,lie);
step_to_step(maze,Step,hang,lie,n);
}
}
int main()
{
char **maze; //定义一个迷宫，空间可动态
int hang,lie,i,j;
char Q;
cout<<"希望手动输入还是文件读入(s:手动输入,w:文件读入):";
cin>>Q;
cout<<endl<<endl;
if(Q=='s')
{
cout<<"请输入矩阵的行列"<<endl;
cout<<"行数:";
cin>>hang;
cout<<"列数:";
cin>>lie;
cout<<endl;
maze=new char *[hang+2]; //分配连续空间给迷宫
for(i=0;i<hang+2;i++)
maze[i]=new char [lie+2];
cout<<"请输入迷宫，0表示通路，1表示墙"<<endl;
for(i=1;i<=hang;i++)
for(j=1;j<=lie;j++)
cin>>maze[i][j];
}
else if(Q=='w')
{
ifstream infile("F:\\migong.txt",ios::in); //可用文件外部输入
infile>>hang;
infile>>lie;
maze=new char *[hang+2]; //分配连续空间给迷宫
for(i=0;i<hang+2;i++)
maze[i]=new char [lie+2];
for(i=1;i<=hang;i++)
for(j=1;j<=lie;j++)
infile>>maze[i][j];
cout<<"文件读取成功！"<<endl;
}
for(i=0;i<hang+2;i++) maze[i][0]='1';
for(i=0;i<lie+2;i++) maze[0][i]='1';
for(i=0;i<lie+2;i++) maze[hang+1][i]='1';
for(i=0;i<hang+2;i++) maze[i][lie+1]='1';
cout<<endl<<endl;
cout<<"********************您输入的迷宫为******************************"<<endl;
cout<<"行数："<<hang<<" "<<"列数："<<lie;
cout<<" "<<"入口："<<"1,1"<<" "<<"出口："<<hang<<","<<lie<<endl;
for(i=0;i<hang+2;i++)
{
for(j=0;j<lie+2;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
cout<<endl<<endl<<"所走的步骤如下:"<<endl;
cure(maze,hang,lie);
cout<<endl<<endl<<endl;
getch();
return 0;
}
程序结果：
心得体会：
这次的实验对于我来说是个很大的挑战，从理解知识点到最后实现实验要求，每一步都不容易。这次实验有很大一部分不是自己写的代码，而且在学习别人的代码时也有很多不懂的地方，通过一行一行阅读，查阅书籍和询问同学，大致懂得了其中的道理。以后我应该多学习一些这样的题目，和生活结合得比较紧密，既有趣又蕴含很大的学习价值。
二叉树的实现及遍历
指导教师： 实验时间：第十一周 星期三 九十节
学院： 计算机科学与技术学院 专业： 计算机科学与技术
班级： 学号： 姓名： 实验室：
实验目的：
1) 掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围。
2) 掌握用指针类型描述、访问和处理二叉树的运算。
3) 掌握二叉树的建立方法
4) 掌握二叉树遍历的基本方法（前序、中序、后序）
实验内容：
1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
2) 输出树的深度，最大元，最小元。
示例程序：
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define Max 20
typedef struct node
{
char data;
struct node *lchild,*rchild;
}
BinTNode; //自定义二叉树的结点类型//
typedef BinTNode *BinTree; //定义二叉树的指针//
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数//
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针//
else
{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点//
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树//
T->rchild=CreatBinTree(); //构造右子树//
return(T);
}
}
//========NLR 先序遍历=============//
void Preorder(BinTree T)
{
if(T)
{
printf("%c",T->data); //访问结点//
Preorder(T->lchild); //先序遍历左子树//
Preorder(T->rchild); //先序遍历右子树//
}
}
//========LNR 中序遍历===============//
void Inorder(BinTree T)
{
if(T)
{
Inorder(T->lchild); //中序遍历左子树//
printf("%c",T->data); //访问结点//
Inorder(T->rchild); //中序遍历右子树//
}
//==========LRN 后序遍历============//
void Postorder(BinTree T){
if(T){
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========//
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T)
{
hl=TreeDepth(T->lchild); //求左深度//
hr=TreeDepth(T->rchild); //求右深度//
max=hl>hr? hl:hr; //取左右深度的最大值//
NodeNum=NodeNum+1; //求结点数//
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。//
return(max+1);
}
else return(0);
}
//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========//
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq//
cq[1]=T; //根入队//
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队//
printf("%c",p->data); //出队，输出结点的值 //
if(p->lchild!=NULL)
{
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队//
}
if(p->rchild!=NULL)
{
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队//
}
}
}
//==========主函数=================//
void main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree; Input preorder:"); //输入完全二叉树的先序序列//
// 用#代表虚结点，如ABD###CE##F##//
root=CreatBinTree(); //创建二叉树，返回根结点//
do
{ //从菜单中选择遍历方式，输入序号//
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数//
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）//
switch (i)
{
case 1:
printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历//
break;
case 2:
printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历//
break;
case 3:
printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历//
break;
case 4:
depth=TreeDepth(root); //求树的深度及叶子数//
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5:
printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历//
break;
default: exit(1);
}
printf("\n");
}
while(i!=0);
}
程序结果：
二叉树及后序遍历（虚线路径）
心得体会：
这次的实验让我对二叉树有了更进一步的理解，对二叉树的操作也更加熟悉。本次实验的存储结构为二叉树链表，对二叉树进行建立、先序遍历、后序遍历、中序遍历的操作，并求出叶子总数。通过对这些操作的代码实现，让我充分掌握了二叉树的定义、性质、及存储方式。虽然最后结果是做出来了，但是过程很复杂。二叉树是数据结构中很重要的一部分知识，也是数据结构的难点，我相信在以后的学习中还会遇到，而我也要进行更深入的学习，以掌握功能强大的二叉树。
图的实现及遍历
指导教师： 实验时间：第十二周 星期三 九十节
学院： 计算机科学与技术学院 专业： 计算机科学与技术
班级： 学号： 姓名： 实验室：
实验目的：
1) 掌握有向图和无向图的概念；
2) 掌握邻接矩阵和邻接链表建立图的存储结构；
3) 掌握DFS及BFS对图的遍历操作和过程；
4) 了解图结构在人工智能、工程等领域的广泛应用。
实验内容：
1) 采用邻接矩阵作为图的存储结构，完成有向图和无向图的DFS和BFS操作；
2) 采用邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。
示例程序：
1.邻接矩阵作为存储结构的程序示例
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数//
typedef struct{
char vexs[MaxVertexNum]; //顶点表//
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表//
int n,e; //图中的顶点数n和边数e//
}MGraph; //用邻接矩阵表示的图的类型//
//=========建立邻接矩阵=======//
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数//
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i<G->n;i++)
{
scanf("%c",&a);
G->vexs[i]=a; //读入顶点信息，建立顶点表//
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0; //初始化邻接矩阵//
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;k<G->e;k++) { //读入e条边，建立邻接矩阵 //
scanf("%d%d",&i,&j); //输入边（Vi，Vj）的顶点序号//
G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句//
}
}
//=========定义标志向量，为全局变量=======//
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======//
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵
int j;
printf("%c",G->vexs[i]); //访问顶点Vi//
visited[i]=TRUE; //置已访问标志//
for(j=0;j<G->n;j++) //依次搜索Vi的邻接点//
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点//
}
void DFS(MGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //标志向量初始化//
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未访问过//
DFSM(G,i); //以Vi为源点开始DFS搜索//
}
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索//
int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列 //
for(i=0;i<G->n;i++)
visited[i]=FALSE; //标志向量初始化//
for(i=0;i<G->n;i++)
cq[i]=-1; //队列初始化//
printf("%c",G->vexs[k]); //访问源点Vk//
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队//
while(cq[f]!=-1) { //队非空则执行//
i=cq[f]; f=f+1; //Vf出队//
for(j=0;j<G->n;j++) //依次Vi的邻接点Vj//
if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问//
printf("%c",G->vexs[j]); //访问Vj//
visited[j]=TRUE;
r=r+1; cq[r]=j; //访问过Vj入队//
}
}
}
//==========main=====//
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间//
CreatMGraph(G); //建立邻接矩阵//
printf("Print Graph DFS: ");
DFS(G); //深度优先遍历//
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3); //以序号为3的顶点开始广度优先遍历//
printf("\n");
}
执行顺序：
Input VertexNum(n) and EdgesNum(e): 8，9
Input Vertex string: 01234567
Input edges,Creat Adjacency Matrix
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 6
Print Graph DFS: 01374256
Print Graph BFS: 31704256
2.邻接链表作为存储结构程序示例
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 50 //定义最大顶点数//
typedef struct node{ //边表结点//
int adjvex; //邻接点域//
struct node *next; //链域//
}EdgeNode;
typedef struct vnode{ //顶点表结点//
char vertex; //顶点域//
EdgeNode *firstedge; //边表头指针//
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型//
typedef struct {
AdjList adjlist; //邻接表//
int n,e; //图中当前顶点数和边数//
} ALGraph; //图类型//
//=========建立图的邻接表=======//
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定义边表结点//
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //读入顶点数和边数//
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i<G->n;i++) //建立边表//
{
scanf("%c",&a);
G->adjlist[i].vertex=a; //读入顶点信息//
G->adjlist[i].firstedge=NULL; //边表置为空表//
}
printf("Input edges,Creat Adjacency List\n");
for(k=0;k<G->e;k++) { //建立边表 //
scanf("%d%d",&i,&j); //读入边（Vi，Vj）的顶点对序号//
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点//
s->adjvex=j; //邻接点序号为j//
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部//
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i//
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部//
}
}
//=========定义标志向量，为全局变量=======//
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======//
void DFSM(ALGraph *G,int i)
{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索//
EdgeNode *p;
printf("%c",G->adjlist[i].vertex); //访问顶点Vi//
visited[i]=TRUE; //标记Vi已访问//
p=G->adjlist[i].firstedge; //取Vi边表的头指针//
while(p) { //依次搜索Vi的邻接点Vj，这里j=p->adjvex//
if(! visited[p->adjvex]) //若Vj尚未被访问//
DFSM(G,p->adjvex); //则以Vj为出发点向纵深搜索//
p=p->next; //找Vi的下一个邻接点//
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //标志向量初始化//
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未访问过//
DFSM(G,i); //以Vi为源点开始DFS搜索//
}
//==========BFS：广度优先遍历=========//
void BFS(ALGraph *G,int k)
{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索//
int i,f=0,r=0;
EdgeNode *p;
int cq[MaxVertexNum]; //定义FIFO队列//
for(i=0;i<G->n;i++)
visited[i]=FALSE; //标志向量初始化//
for(i=0;i<=G->n;i++)
cq[i]=-1; //初始化标志向量//
printf("%c",G->adjlist[k].vertex); //访问源点Vk//
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队//
while(cq[f]!=-1)
{ 队列非空则执行
i=cq[f]; f=f+1; //Vi出队//
p=G->adjlist[i].firstedge; //取Vi的边表头指针//
while(p) { //依次搜索Vi的邻接点Vj（令p->adjvex=j）//
if(!visited[p->adjvex]) { //若Vj未访问过//
printf("%c",G->adjlist[p->adjvex].vertex); //访问Vj//
visited[p->adjvex]=TRUE;
r=r+1; cq[r]=p->adjvex; //访问过的Vj入队//
}
p=p->next; //找Vi的下一个邻接点//
}
}//endwhile
}
//==========主函数===========//
void main()
{
int i;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf("Print Graph DFS: ");
DFS(G);
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3);
printf("\n");
}
执行顺序：
Input VertexNum(n) and EdgesNum(e): 8，9
Input Vertex string: 01234567
Input edges,Creat Adjacency List
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 6
Print Graph DFS: 02651473
Print Graph BFS: 37140265
心得体会：
图在数据结构中也是一个重要的知识点，是一种较线性表和树更为复杂的数据结构。在本实验中，我掌握了有向图和无向图的概念和掌握邻接矩阵和邻接链表建立图的储存结构；学会DFS及BFS对图的遍历操作；了解到图结构在人工智能、工程领域的广泛应用。在以后的学习中我一定还会遇到很多关于图的实例，这次的实验给我帮助很大，我相信有了这次实验的基础，以后的问题会迎刃而解。
查找算法的实现及比较
指导教师： 实验时间：第十三周 星期三 九十节
学院： 计算机科学与技术学院 专业： 计算机科学与技术
班级： 学号： 姓名： 实验室：
实验目的：
1) 掌握线性结构（顺序查找、折半查找）上查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。
2) 掌握树形结构（二叉排序树）实现查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。
实验内容：
1) 有序表的二分查找
建立有序表，然后进行二分查找
2) 二叉排序树的查找
建立二叉排序树，然后查找
有序表二分查找程序示例：
#include “stdio.h”
#include “stdlib.h”
static int a[1024],count=0;
void Find1(int low,int high,int x)
{
int mid;
if(low<=high)
{
mid=(low+high)/2;
count++;
if(a[mid]>x)Find1(low,mid-1,x);
else
if(a[mid]<x)Find1(mid+1,high,x);
else
printf("\n查找到元素位置为%d，查找次数为%d。",mid,count);
}
else
printf("\n查找失败，查找次数为%d。",count);
}
void Find2(int low,int high,int x)
{
int mid;
if(low<=high)
{
mid=(low+high)/2;
count++;
if(a[mid]<x)Find2(low,mid-1,x);
else
if(a[mid]>x)Find2(mid+1,high,x);
else
printf("\n查找到元素位置为%d，查找次数为%d。",mid,count);
}
else
printf("\n查找失败，查找次数为%d。",count);
}
int main()
{
int n,x;
printf("请输入元素个数:");
scanf("%d",&n);
printf("\n请按从高到低或从低到高顺序输入各元素(以空格隔开):\n\n");
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("\n请输入要查找的元素：");
scanf("%d",&x);
if(a[1]<=a[n])Find1(1,n,x);
else
Find2(1,n,x);
printf("\n\n");
system("pause");
}
程序结果：
二叉排序树查找程序示例：
#include “iostream.h”
typedef struct TreeNode
{
int key;
struct TreeNode *left;
struct TreeNode *right;
}treeNode;
class BiSortTree
{
public:
BiSortTree(void);
void desplayTree(void);//显示这个树
void insertTree(int key);//在树中插入一个值
deleteTree(int key);//在树中删除一个值
treeNode* searchTree(int key);//在树中查找一个值
~BiSortTree();
private:
treeNode* buildTree(treeNode* head,int number);//建立一个树
treeNode* search(treeNode* head ,int key);//查找
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父亲节点的指针
treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子树中最小的节点
void showTree(treeNode* head);//显示
void destroyTree(treeNode* head);//删除
treeNode *Head;
};
/**************以下是建立一个二叉排序树****************/
BiSortTree::BiSortTree()
{
cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): "<<endl;
Head=NULL;
int number;
cin>>number;
while(number!=-1)
{
Head=buildTree(Head,number);
cin>>number;
}
}
treeNode* BiSortTree::buildTree(treeNode* head,int number)
{
treeNode *p;
p=new treeNode;
p->key=number;
p->left =p->right=NULL;
if(head==NULL)
{
return p;
}
else
{
if(p->key <head->key)
head->left=buildTree(head->left,number);
else
head->right=buildTree(head->right,number);
return head;
}
}
/*****************以下是在一棵二叉排序树插入一个数***********************************/
void BiSortTree::insertTree(int key)
{
Head=buildTree(Head,key);
}
/*****************以下是在一个二叉排序树查找一个数是否存在*************************/
treeNode* BiSortTree::searchTree(int key)
{
return search(Head,key);
}
treeNode* BiSortTree::search(treeNode* head ,int key)
{
if(head==NULL)
return NULL;
if(head->key==key)
return head;
else
{
if(key<head->key )
return search( head->left,key);
else
return search(head->right,key);
}
}
/************以下是在一个二叉排序树删除一个给定的值*********************************/
BiSortTree::deleteTree(int key)
{
treeNode *p;
p=NULL;
p=search(Head,key);
if(p==NULL)
{
cout<<"Don't find the key";
}
if(p==Head)
{
Head=NULL;
}
else
{
treeNode* parent;
parent=searchParent(Head,p);
if(p->left==NULL&&p->right==NULL)//叶子节点
{
if(parent->left==p)
{
parent->left=NULL;
}
else
{
parent->right=NULL;
}
}
else //非叶子节点
{
if(p->right==NULL)//该节点没有右孩子
{
if(parent->left==p)
{
parent->left=p->left ;
}
else
{
parent->right=p->left;
}
}
else//该点有左右孩子
{
treeNode * rightMinSon,* secondParent;//secondParent为右子树中的最小节点的父亲
rightMinSon=searchMinRight(p->right);
secondParent=searchParent(p->right ,rightMinSon);
secondParent->left=rightMinSon->right;
if(p->right==rightMinSon)//右子树中的最小节点的父亲为p
{
p->right=rightMinSon->right ;
}
p->key=rightMinSon->key ;
}
}
}
}
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p)
{
if(head->left==p||head->right==p||head==p||head==NULL)
return head;
else
{
if(p->key<head->key)
return searchParent(head->left ,p);
else
return searchParent(head->right ,p);
}
}
treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点
{
if(head->left ==NULL||head==NULL)
{
return head;
}
else
{
return searchMinRight(head->left);
}
}
/*****************以下是显示一个二叉排序树****************************************/
void BiSortTree::desplayTree(void)
{
showTree(Head);
cout<<endl;
}
void BiSortTree::showTree(treeNode* Head)
{
if(Head!=NULL)
{
showTree(Head->left ) ;
cout<<Head->key<<' ' ;
showTree(Head->right) ;
}
}
/*****************以下是删除一棵整二叉排序树************************************/
BiSortTree::~BiSortTree()
{
cout<<"已经消除了一棵树!!!!"<<endl;
destroyTree(Head);
}
void BiSortTree::destroyTree(treeNode* head )
{
if(head!=NULL)
{
destroyTree(head->left );
destroyTree(head->right);
delete head;
}
}
/*********************/
void print()
{
cout<<endl<<endl<<"以下是对二叉排序树的基本操作:"<<endl
<<"1.显示树"<<endl
<<"2.插入一个节点"<<endl
<<"3.寻找一个节点"<<endl
<<"4.删除一个节点"<<endl;
}
void main()
{
BiSortTree tree;
int number;
int choiceNumber;
char flag;
while(1)
{
print();
cout<<"请选择你要进行的操作(1~4)"<<endl;
cin>>choiceNumber;
switch(choiceNumber)
{
case 1:
tree.desplayTree();
break;
case 2:
cout<<"请插入一个数: "<<endl;
cin>>number;
tree.insertTree(number);
tree.desplayTree();
break;
case 3:
cout<<"请插入你要找数: "<<endl;
cin>>number;
if(tree.searchTree(number)==NULL)
{
cout<<"没有发现"<<endl;
}
else
{
cout<<"发现"<<endl;
}
break;
case 4:
cout<<"请输入你要删除的数: "<<endl;
cin>>number;
tree.deleteTree(number);
tree.desplayTree();
break;
default: break;
}
cout<<"你是否要继续(Y/N)?"<<endl;
cin>>flag;
if(flag=='N'||flag=='n')
break;
}
}
程序结果：
心得体会：
这次实验比较困难，以我自己的水平实在无法独立完成。在反复翻阅书籍，重新学习所需知识点后，对实验要求才有了初步想法。但在代码编写方面，着实费了很长一段时间。最多通过询问同学和上网查询才有了现在的代码。在对现有代码进行细致地学习后，我对本次实验的要求和目的有了更深地理解和体会，相信在以后的学习工作中，这些经验将给我莫大的帮助。最后，我必须感谢我的老师和其他同学。在几次实验过程中，大家都给予我许多帮助，让我度过难关。数据结构是一门重要且深奥的知识，我定会继续学习下去，充实自己，努力为祖国的计算机事业贡献自己的力量！