内容发布更新时间 : 2024/11/15 16:56:32星期一 下面是文章的全部内容请认真阅读。
scanf(\
printf(\
for(i=0;i
scanf(\
G->adjlist[i].vertex=a; //读入顶点信息 G->adjlist[i].firstedge=NULL; //边表置为空表 }
printf(\ for(k=0;k
scanf(\读入边（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(\访问顶点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
visited[i]=FALSE; //标志向量初始化 for(i=0;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
visited[i]=FALSE; //标志向量初始化 for(i=0;i<=G->n;i++)
cq[i]=-1; //初始化标志向量 printf(\访问源点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(\访问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(\ DFS(G);
printf(\
printf(\ BFS(G,3); printf(\}
实验结果：
1. 邻接矩阵作为存储结构 执行顺序：
Input VertexNum(n) and EdgesNum(e): 8，9 Input Vertex string: 01234567
V1 Input edges,Creat Adjacency Matrix 0 1 V3 0 2 1 3 1 4 2 5
V7 2 6 3 7 4 7 5 6
Print Graph DFS: 01374256 Print Graph BFS: 31704256 2. 邻接链表作为存储结构 执行顺序：
Input VertexNum(n) and EdgesNum(e): 8，9 Input Vertex string: 01234567 Input edges,Creat Adjacency List 0 1 0 2 V1 1 3
V3 1 4 2 5 2 6 3 7 4 7 V7 5 6
Print Graph DFS: 02651473
Print Graph BFS: 37140265
V0 V2 V4 V5 V6 V0 V2 V4 V5 V6 心得体会：
这次实验较以前的实验难度加大，必须先理解深度优先和广度优先两种遍历思路，和数据结构中队列的基本操作，才能看懂理解代码。同时图这种数据结构对抽象的能力要求非常高，代码不容易看懂，排错也比较麻烦，应该多加练习，才能掌握。
实验4
实验题目：排序
实验目的：
掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。
实验要求：
实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。
实验主要步骤：
实验代码
#include\#include\
#define Max 100 //假设文件长度 typedef struct{ //定义记录类型 int key; //关键字项 }RecType;
typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵 int n; //顺序表实际的长度
//==========直接插入排序法====== void InsertSort(SeqList R)
{ //对顺序表R中的记录R[1‥n]按递增序进行插入排序 int i,j;
for(i=2;i<=n;i++) //依次插入R[2]，……，R[n]
if(R[i].key R[0]=R[i];j=i-1; //R[0]是R[i]的副本 do { //从右向左在有序区R[1‥i-1]中查找R[i] 的位置 R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; } while(R[0].key //==========冒泡排序======= typedef enum {FALSE,TRUE} Boolean; //FALSE为0，TRUE为1 void BubbleSort(SeqList R) { //自下向上扫描对R做冒泡排序 int i,j; Boolean exchange; //交换标志 for(i=1;i exchange=FALSE; //本趟排序开始前，交换标志应为假 for(j=n-1;j>=i;j--) //对当前无序区R[i‥n] 自下向上扫描 if(R[j+1].key exchange=TRUE; //发生了交换，故将交换标志置为真 } if(! exchange) //本趟排序未发生交换，提前终止算法 return; }// endfor（为循环） } //1.========一次划分函数===== int Partition(SeqList R,int i,int j) { // 对R[i‥j]做一次划分，并返回基准记录的位置 RecType pivot=R[i]; //用第一个记录作为基准 while(i while(i R[i++]=R[j]; //交换R[i]和R[j]，交换后i指针加1 while(i if(i R[j--]=R[i]; //交换R[i]和R[j]，交换后j指针减1 } R[i]=pivot; //此时，i=j，基准记录已被最后定位 return i; //返回基准记录的位置 } //2.=====快速排序=========== void QuickSort(SeqList R,int low,int high) { //R[low..high]快速排序 int pivotpos; //划分后基准记录的位置 if(low pivotpos=Partition(R,low,high); //对R[low..high]做一次划分，得到基准记录的位置 QuickSort(R,low,pivotpos-1); //对左区间递归排序