数据结构实验指导书-2014

《数据结构》

实验指导书

计算机专业实验中心

2014年9月

目 录

实验一、线性表的实现及操作（一） .............................................................................................. 5 实验二、线性表的实现及操作（二） .............................................................................................. 8 实验三、线性表的应用 .................................................................................................................... 13 实验四、二叉树的实现及操作 ........................................................................................................ 14 实验五、二叉树的应用 .................................................................................................................... 19 实验六、图的遍历操作 .................................................................................................................... 20 实验七、图的应用 ............................................................................................................................ 27

2

《数据结构》上机实验的内容和要求

通过上机实验加深对课程内容的理解，增加感性认识，提高程序设计、开发及调试能力。 本实验指导书适用于16学时《数据结构》实验课，实验项目具体内容如下：

序号 实 验 名 称 线性表的实现及操作1 （一） 线性表的实现及操作2 （二） 3 4 5 6 7 8 内 容 每组 实验 提 要 人数 时数 顺序表建立、插入、删除1 2 等基本操作 单链表的建立、插入、删1 2 除等基本操作 约瑟夫环问题或者长整数线性表的应用 1 2 相加的设计与实现 二叉树的基本操作：树的二叉树的实现及操作 建立、前序、中序、后序1 2 遍历 二叉树的应用 赫夫曼树 1 2 图的遍历：深度优先和广图的遍历 1 2 度优先 最短路径算法：Dijkstra图的应用 1 2 算法和Floyd算法 对实验课涉及到的算法进算法性能测试、总结行性能测试、对实验所遇1 2 和答疑 到的问题进行总结和答疑 实验 实验 分值（总要求 类别 100分） 必做 设计 15分 必做 设计 15分 选作 综合 10分 必做 设计 20分 选作 综合 10分 必做 设计 20分 选作 综合 10分 其中，第1、2、4、6实验项目为设计性实验，的其内容为程序代码分析与调试，要求每位同学在每次实验课结束前通过检查。这部分实验应撰写1份实验报告，总分70分。

第3、5、7实验项目为综合应用性实验，学生根据自己的兴趣和基础选作。这三个实验要求学生利用所学的理论知识解决实际问题，每一个实验应撰写一份实验报告，每个实验10分。

此实验指导书也适用于8学时《数据结构》实验课，要求完成第1、2、4、6实验项目。

实验报告要求

请按照实验教师要求，按时提交实验报告电子版文件。 实验报告格式可个性化定义，内容包括但不限于以下内容：

1、题目、姓名、学号、班级（首页）

2、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定： （1）输入的形式和输出值的范围； （2）输出的形式； （3）程序所能达到的功能；

3

（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。

3、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。 4、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。 5、调试分析：

（1）调试过程中所遇到的问题及解决方法； （2）算法的时空分析； （3）经验与体会。

6、用户使用说明：说明如何使用你设计的程序，详细列出每一步操作步骤。（如果程序操作简单，可略去）

7、测试结果：列出对于给定的输入所产生的输出结果。（若有可能，测试随输入规模的增长所用算法的实际运行时间的变化） 8、总结

4

实验一、线性表的实现及操作（一）

一、实验目的

了解和掌握线性表的顺序存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：（1）建立一个线性表；（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；（3）删除数据元素5；（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用顺序表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，修改后上机调试得到正确的运行结果。

三、程序代码 #include #define MaxSize 100 typedef int DataType;

typedef struct {

DataType list[MaxSize]; int size; } SeqList;

void ListInitiate(SeqList *L) { }

int ListLength(SeqList L) { }

int ListInsert(SeqList *L, int i, DataType x)

/*在顺序表L的位置i（0 ≤ i ≤ size）前插入数据元素值x*/ /*插入成功返回1，插入失败返回0*/

5

/*初始化顺序表L*/ /*定义初始数据元素个数*/

L->size = 0;

/*返回顺序表L的当前数据元素个数*/

return L.size;

{ int j;

if(L->size >= MaxSize) { printf(\顺序表已满无法插入! \\n\ return 0;

}

else if(i < 0 || i > L->size ) { printf(\参数i不合法! \\n\ return 0;

} else

{ //此段程序有一处错误 for(j = L->size; j > i; j--) L->list[j] = L->list[j]; /*为插入做准备*/ L->list[i] = x; /*插入*/ L->size ++;

/*元素个数加1*/

return 1;

} }

int ListDelete(SeqList *L, int i, DataType *x)

/*删除顺序表L中位置i（0 ≤ i ≤ size - 1）的数据元素值并存放到参数x中*/

/*删除成功返回1，删除失败返回0*/ { int j;

if(L->size <= 0) { printf(\顺序表已空无数据元素可删! \\n\ return 0;

}

else if(i < 0 || i > L->size-1) { printf(\参数i不合法\ return 0;

} else

{//此段程序有一处错误

*x = L->list[i]; /*保存删除的元素到参数x中*/

6

for(j = i +1; j <= L->size-1; j++) L->list[j] = L->list[j-1]; /*依次前移*/

L->size--;

/*数据元素个数减1*/

return 1;

} }

int ListGet(SeqList L, int i, DataType *x)

/*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/ {

if(i < 0 || i > L.size-1) { printf(\参数i不合法! \\n\ return 0;

} else { *x = L.list[i]; return 1;

} }

void main(void)

{ SeqList myList; int i , x;

ListInitiate(&myList); for(i = 0; i < 10; i++)

ListInsert(&myList, i, i+1); ListDelete(&myList, 4, &x); for(i = 0; i < ListLength(myList); i++) { ListGet( , i, &x); //此段程序有一处错误 printf(\ \ }

}

7

实验二、线性表的实现及操作（二）

一、实验目的

了解和掌握线性表的链式存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。

二、实验要求

给定一段程序代码，程序代码所完成的功能为：（1）建立一个线性表；（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；（3）删除数据元素5；（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用单链表。

程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，上机调试并得到正确的运行结果。

三、程序代码： #include #include #include

typedef int DataType;

typedef struct Node {

DataType data; struct Node *next; } SLNode;

void ListInitiate(SLNode **head) {

/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1); (*head)->next = NULL; }

int ListLength(SLNode *head) {

SLNode *p = head;

/*该文件包含pringtf()等函数*/ /*该文件包含exit()等函数*/

/*该文件包含malloc()等函数*/

/*定义DataType为int*/

/*初始化*/

/*置链尾标记NULL */

/*p指向首元结点*/

8

int size = 0; /*size初始为0*/

while(p->next != NULL)

/*循环计数*/

{ p = p->next; size ++;

} return size; }

int ListInsert(SLNode *head, int i, DataType x)

/*在带头结点的单链表head的数据元素ai（0 ≤ i ≤ size）结点前*/ /*插入一个存放数据元素x的结点*/ {

SLNode *p, *q; int j;

p = head; /*p指向首元结点*/ j = -1;

/*j初始为-1*/

while(p->next != NULL && j < i - 1) /*最终让指针p指向数据元素ai-1结点*/ { p = p->next; j++;

}

if(j != i - 1) { printf(\插入位置参数错！\ return 0;

}

/*生成新结点由指针q指示*/

if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL) exit(1); q->data = x;

//此段程序有一处错误 p->next = q->next; /*给指针q->next赋值*/ p->next = q;

/*给指针p->next重新赋值*/

return 1;

9

}

int ListDelete(SLNode *head, int i, DataType *x)

/*删除带头结点的单链表head的数据元素ai（0 ≤ i ≤ size - 1）结点*/ /*删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0*/ {

SLNode *p, *s; int j;

p = head; /*p指向首元结点*/ j = -1;

/*j初始为-1*/

while(p->next != NULL && p->next->next!= NULL && j < i - 1) /*最终让指针p指向数据元素ai-1结点*/ { p = p->next;

j++; }

if(j != i - 1) { printf(\插入位置参数错！\ return 0;

}

//此段程序有一处错误 s = p->next; /*指针s指向数据元素ai结点*/

*x = s->data; /*把指针s所指结点的数据元素域值赋予x*/ p->next = s->next;

/*把数据元素ai结点从单链表中删除指*/

free(s);

/*释放指针s所指结点的内存空间*/

return 1; }

int ListGet(SLNode *head, int i, DataType *x)

/*取数据元素ai和删除函数类同，只是不删除数据元素ai结点*/ {

SLNode *p; int j;

p = head; j = -1;

10

while(p->next != NULL && j < i) { p = p->next; j++;

}

if(j != i) { printf(\取元素位置参数错！\ return 0;

}

//此段程序有一处错误 *x = p->next; return 1; }

void Destroy(SLNode **head) {

SLNode *p, *p1;

p = *head; while(p != NULL) { p1 = p; p = p->next; free(p1);

}

*head = NULL; }

void main(void) {

SLNode *head; int i , x;

ListInitiate(&head); for(i = 0; i < 10; i++) {

/*初始化*/

11

}

if(ListInsert(head, i, i+1) == 0) { }

printf(\错误! \\n\return;

/*插入10个数据元素*/

if(ListDelete(head, 4, &x) == 0) /*删除数据元素5*/ { printf(\错误! \\n\ return;

}

for(i = 0; i < ListLength(head); i++) { if(ListGet(head, i, &x) == 0) { printf(\错误! \\n\ return;

}

else printf(\ \

}

Destroy(&head); /*取元素*/

/*显示数据元素*/

}

12

实验三、线性表的应用

一、实验目的

加深对线性表各项操作实现的理解，增强学生问题模拟、数据抽象的能力。

二、实验要求

本实验共有两个题目，作为实验一和实验二的拓展题目，可选作其中一个或者两个都做。选取根据题目要求进行设计，并编程实现，在实验报告中给出测试数据。

三、实验内容

1、 约瑟夫环问题的设计与实现

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

问题：假设41个人围成一圈，其中有m个你的朋友不想死掉，从第一个开始报数，第3个将被杀掉。为了保护自己和m个朋友，现在编写程序，求出如何安排自己和m个朋友的初始位置。

2、 长整数表示与相加

很长整数是指无法用long型数存储的数，因此需要用字符串数组来存储两个被加数，相加的结果也保存于字符数组中，假如被加数长度不超过十进制40位，请编程实现该加法程序并将相加结果输出。

四、 实验报告要求

1、基本要求见第3页。 2、给出实验结果。

3、对算法的性能进行测试。要求分析算法的复杂度，测试程序对于不同大小输入的运行情况（例如约瑟夫环，改变人数个数为50,100,1000等，测试其是否正常运行，比较运行时间等）。

13

实验四、二叉树的实现及操作

一、 实验目的

掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围，各种遍历算法。掌握用指针类型描述、访问和处理二叉树的运算。

二、 实验内容及要求

有如下二叉树：

根 ∧ A B ∧ C ∧ D ∧ E ∧ ∧ F ∧ ∧ G ∧

程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法，同时也给出了查询“E”是否在二叉树里的代码。代码有四处错误，有标识，属于逻辑错误，对照书中的代码仔细分析后，请修改了在电脑里运行，该实验无需写实验报告，程序能完全执行得满分。改对一处得总分的四分之一。

#include #include

typedef char DataType;

typedef struct Node {

DataType data; /*数据域*/

14

struct Node *leftChild; /*左子树指针*/ struct Node *rightChild;

/*右子树指针*/

}BiTreeNode;

/*结点的结构体定义*/

/*初始化创建二叉树的头结点*/ void Initiate(BiTreeNode **root) {

*root = (BiTreeNode *)malloc(sizeof(BiTreeNode)); (*root)->leftChild = NULL; (*root)->rightChild = NULL; }

void Destroy(BiTreeNode **root) {

if((*root) != NULL && (*root)->leftChild != NULL) Destroy(&(*root)->leftChild);

if((*root) != NULL && (*root)->rightChild != NULL) Destroy(&(*root)->rightChild);

free(*root); }

/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/ /*原curr所指结点的左子树成为新插入结点的左子树*/ /*若插入成功返回新插入结点的指针，否则返回空指针*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) {

BiTreeNode *s, *t;

if(curr == NULL) return NULL;

t = curr->leftChild; /*保存原curr所指结点的左子树指针*/

s = (BiTreeNode *)malloc(sizeof(BiTreeNode));

s->data = x; s->leftChild = t;

/*新插入结点的左子树为原curr的左子树*/

s->rightChild = NULL;

curr->leftChild = s;

/*新结点成为curr的左子树*/ return curr->leftChild;

/*返回新插入结点的指针*/

}

15

/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/ /*原curr所指结点的右子树成为新插入结点的右子树*/ /*若插入成功返回新插入结点的指针，否则返回空指针*/ BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) {

BiTreeNode *s, *t;

if(curr == NULL) return NULL;

t = curr->rightChild; /*保存原curr所指结点的右子树指针*/

s = (BiTreeNode *)malloc(sizeof(BiTreeNode));

s->data = x; s->rightChild = t;

/*新插入结点的右子树为原curr的右子树*/

s->leftChild = NULL;

curr->rightChild = s; /*新结点成为curr的右子树*/

return curr->rightChild;

/*返回新插入结点的指针*/

}

void PreOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数前序遍历二叉树t {

if(t != NULL) {//此小段有一处错误 visit(t->data);

PreOrder(t-> rightChild, visit); PreOrder(t-> leftChild, visit);

} }

void InOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数中序遍历二叉树t {

if(t != NULL) {//此小段有一处错误 InOrder(t->leftChild, visit);

InOrder(t->rightChild, visit);

16

} }

visit(t->data);

void PostOrder(BiTreeNode *t, void visit(DataType item)) //使用visit(item)函数后序遍历二叉树t {

if(t != NULL) {//此小段有一处错误 } }

void Visit(DataType item) {

printf(\}

BiTreeNode *Search(BiTreeNode *root, DataType x)//需找元素x是否在二叉树中 {

BiTreeNode *find=NULL; if(root!=NULL) { }

return find; }

void main(void) {

17

visit(t->data);

PostOrder(t->leftChild, visit); PostOrder(t->rightChild, visit);

if(root->data==x) else { }

find=Search(root->leftChild,x); if(find==NULL)

find=Search(root->rightChild,x); find=root;

BiTreeNode *root, *p, *pp,*find; char x='E';

Initiate(&root);

p = InsertLeftNode(root, 'A'); p = InsertLeftNode(p, 'B'); p = InsertLeftNode(p, 'D'); p = InsertRightNode(p, 'G');

p = InsertRightNode(root->leftChild, 'C'); pp = p;

InsertLeftNode(p, 'E'); InsertRightNode(pp, 'F');

printf(\前序遍历：\

PreOrder(root->leftChild, Visit); printf(\中序遍历：\ InOrder(root->leftChild, Visit); printf(\后序遍历：\ PostOrder(root->leftChild, Visit);

find=Search(root,x); if(find!=NULL) printf(\数据元素%c在二叉树中 \\n\

else printf(\数据元素%c不在二叉树中 \\n\

Destroy(&root); }

18

实验五、二叉树的应用

一、实验目的

加深对二叉树的各项操作实现的理解，增强学生利用二叉树知识解决实际问题的能力。 二、实验要求

本实验为选作题目。需编程实现，撰写实验报告，并在实验报告中给出测试结果。 三、实验内容

假设有一串字符串“DBDBDABDCDADBDADBDADACDBDBD”或者你自己给定一串任意的字符串，利用赫夫曼树编程给出这串字符串的赫夫曼编码。

以下是上面字符串编码后程序运行结果示例（自己所编程序的输入输出形式可自由发挥）：

四、 实验报告要求 1、 基本要求见第3页。 2、 给出实验结果。

3、 对算法的性能进行测试，要求分析算法的复杂度，测试程序在不同长度的字符串下运

行情况。

19

实验六、图的遍历操作

一、实验目的

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。

二、 实验要求

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。本实验给出了示例程序，其中共有4处错误，错误段均有标识，属于逻辑错误。请认真理解程序，修改程序代码，并在电脑上调试运行。

三、 DFS和BFS 的基本思想

深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。

广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。

四、 示例程序

1． 邻接矩阵作为存储结构的程序示例 #include\#include\

#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(\

20

V7 V3 V4 V5 V6 V1 V0 V2 图G的示例

scanf(\输入顶点数和边数 scanf(\ printf(\ for(i=0;in;i++) {

scanf(\

G->vexs[i]=a; //读入顶点信息，建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

G->edges[i][j]=0; //初始化邻接矩阵

printf(\

for(k=0;ke;k++) { //读入e条边，建立邻接矩阵 }

//=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum];

//========DFS：深度优先遍历的递归算法====== void DFSM(MGraph *G,int i)

{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j;

printf(\访问顶点Vi visited[i]=TRUE; //置已访问标志 for(j=0;jn;j++) //依次搜索Vi的邻接点 }

void DFS(MGraph *G) { \\\\此段代码有一处错误 int i;

for(i=0;in;i++) }

21

scanf(\输入边（Vi，Vj）的顶点序号 G->edges[i][j]=1;

G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句

}

if(G->edges[i][j]==1 && ! visited[j])

DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点

visited[i]=FALSE; //标志向量初始化 if(!visited[i]) //Vi未访问过

DFS (G,i); //以Vi为源点开始DFS搜索

for(i=0;in;i++)

//===========BFS：广度优先遍历======= void BFS(MGraph *G,int k)

{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0;

int cq[MaxVertexNum]; //定义队列 for(i=0;in;i++)

visited[i]=FALSE;

//标志向量初始化

for(i=0;in;i++)

cq[i]=-1; //队列初始化 printf(\访问源点Vk visited[k]=TRUE;

cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队 while(cq[f]!=-1) { //队非空则执行 }

//==========main===== void main() {

int i; MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间 CreatMGraph(G); //建立邻接矩阵 printf(\

DFS(G); //深度优先遍历 printf(\

printf(\

BFS(G,3); //以序号为3的顶点开始广度优先遍历 printf(\}

执行顺序：

Input VertexNum(n) and EdgesNum(e): 8，9 Input Vertex string: 01234567

22

i=cq[f]; f=f+1; //Vf出队

for(j=0;jn;j++) //依次Vi的邻接点Vj

if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问 \\\\以下三行代码

printf(\访问Vj visited[j]=FALSE;

r=r+1; cq[r]=j; //访问过Vj入队

有一处错误

}

}

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\#include\

#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(\ scanf(\读入顶点数和边数 scanf(\

printf(\

23

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 \\\\以下3行代码有一处错误 if(! visited[p->adjvex]) //若Vj尚未被访问

DFS (G,p->adjvex); //则以Vj为出发点向纵深搜索 p=p->next; //找Vi的下一个邻接点

} }

void DFS(ALGraph *G) {

int i;

for(i=0;in;i++)

24

}

visited[i]=FALSE; //标志向量初始化 if(!visited[i]) //Vi未访问过

DFSM(G,i); //以Vi为源点开始DFS搜索

for(i=0;in;i++)

//==========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;

\\\\以下3行代码有一处错误

r=r+1; cq[r]=p->adjvex; //访问过的Vj入队

}

p=p->next->next; //找Vi的下一个邻接点 }

}//endwhile

}

//==========主函数=========== void main() {

int i; ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G);

printf(\

25

DFS(G); printf(\

printf(\ BFS(G,3); printf(\}

执行顺序：

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

26

实验七、图的应用

一、 实验目的

最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。本实验要求学生掌握Dijkstra或者Floyd算法，增加学生对图应用的深入理解。

二、 实验要求

本实验有两个题目，一个是Dijkstra，另一个是Floyd算法。学生可选作一个并撰写实验报告。

三、 问题

1. 有向带权图及邻接矩阵如下图所示：

8 E 4 15 18 10 F 7 C

D 30 5 A B 2 ?0?530???20??8??150???????0?????40?????1018

???????? ?????0?编程实现Dijkstra算法，求出从A点开始到其他点的最短距离和最短路径。 2. 编程并采用Floyd算法对上图进行计算，求出任意两点之间的最短距离和路径。

四、实验报告要求 1、基本要求见第3页。

2、给出输入数据及程序执行的结果。

3、对算法的性能进行测试，要求分析算法的复杂度。

27

本文来源：https://www.bwwdw.com/article/d7lt.html