数据结构(C语言版)实验报告 下载本文

scanf(\

printf(\

for(i=0;in;i++) //建立边表 {

scanf(\

G->adjlist[i].vertex=a; //读入顶点信息 G->adjlist[i].firstedge=NULL; //边表置为空表 }

printf(\ for(k=0;ke;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;in;i++)

visited[i]=FALSE; //标志向量初始化 for(i=0;in;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;in;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=pivot.key) //基准记录pivot相当与在位置i上 j--; //从右向左扫描,查找第一个关键字小于pivot.key的记录R[j] if(i

R[i++]=R[j]; //交换R[i]和R[j],交换后i指针加1

while(i

if(i pivot.key,则

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); //对左区间递归排序