朱颢东2015-2016学年第二学期《数据结构》实验指导书（修订版）-1

《数据结构》 实验指导书

郑州轻工业学院 2016.02.20

目 录

前 言 ................................................................................ 3 实验01 顺序表的基本操作........................................... 5 实验02 单链表的基本操作......................................... 13 实验03 栈的基本操作 ................................................. 21 实验04 队列的基本操作 ............................................. 23 实验05 二叉树的基本操作......................................... 25 实验06 哈夫曼编码 ..................................................... 26 实验07 图的两种存储和遍历 .................................... 28 实验08 最小生成树、拓扑排序和最短路径 ............ 31 实验09 二叉排序树的基本操作 ................................ 33 实验10 哈希表的生成 ................................................. 34 实验11 常用的内部排序算法 ..................................... 35 附：实验报告模板 ........................ 错误！未定义书签。

2

前 言

《数据结构》是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一。它主要介绍线性结构、树型结构、图状结构三种逻辑结构的特点和在计算机内的存储方法，并在此基础上介绍一些典型算法及其时、空效率分析。这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在计算机中的表示、存储和运算，培养学生能够设计有效表达和简化算法的数据结构，从而提高其程序设计能力。通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设计思想及程序实现，能够根据实际问题选取合适的数据表达和存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。另外本课程的学习过程也是进行复杂程序设计的训练过程，通过算法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设计能力。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。 一、实验目的

本课程实验主要是为了原理和应用的结合，通过实验一方面使学生更好的理解数据结构的概念和常用的几种数据结构在计算机中的存储和实现的方法，加强学生动手能力；另一方面培养学生从实际问题中抽象出对应的抽象数据类型，进而找到合适的计算机存储方法和算法，为以后课程的学习、大型软件的开发、实际工程问题打下良好的软件开发基础。 二、实验要求

1、每次实验前学生必须根据实验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。

4、遵守实验室规章制度、不缺席、按时上、下机。

5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。

6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。 三、实验环境

VC++6.0或其他C++相关的编译环境。 四、说明

1、本实验的所有算法中元素类型应根据实际需要合理选择。

2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。

3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在

3

学习过程中注意各种算法的理解，以便为考研做一定的准备。

4、好的算法决定了好的程序，要有效地实现算法，就需要设计能够有效表达和简化算法的数据结构，因此数据结构是有效进行程序设计的基础，是每个程序员的必修课。 五、实验报告的书写要求

1、明确实验的目的及要求。 2、记录实验的输入数据和输出结果。 3、说明实验中出现的问题和解决过程。

4、写出实验的体会和实验过程中没能解决的问题。

5、实验程序请构建为多文件程序，每一个算法对应的函数原型声明存放在头文件*.h中，对应的函数实现存放在源文件*.c中；main()函数存放在另一个源文件中，该文件包含头文件*.h即可。 六、成绩考评办法

1、期末考试占70分，闭卷。

2、平时考评占30分。其中实验环节占20分（实验准备、上机、报告、验收等）；平时占10分（出勤、作业、测验等）。 七、参考书目

1、《数据结构》（Ｃ语言版） 严蔚敏等 清华大学出版社。 2、《数据结构题集》 （C语言版） 严蔚敏等 清华大学出版社。

3、《数据结构与算法分析——C语言描述》，Mark Allen Weiss著，机械工业出版社，2012。

4

实验01 顺序表的基本操作

实验学时：2学时 实验类型：上机

背景知识：顺序表的插入、删除及应用。 目的要求：

1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。

实验内容：

编写一个完整的程序，实现顺序表的生成、插入、删除、输出等基本运算。 （1） 建立一个顺序表，含有n个数据元素。 （2） 输出顺序表。

（3） 在顺序表中删除值为x的结点或者删除给定位置i的结点。

（4） 实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。 （5） 输入整型元素序列，利用有序表插入算法建立一个有序表。

（6） *利用算法5建立两个非递减有序表A和B，并把它们合并成一个非递减有序表C。 （7） 在主函数中设计一个简单的菜单，分别测试上述算法。 （8） *综合训练：

利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。

实验说明：

1．请构建多文件程序，算法1至算法6对应的函数原型声明存放在头文件SqList.h中，对应的函数实现存放在源文件SqList.c中；main()函数存放在另一个源文件中，该文件包含头文件SqList.h即可。

2．类型定义

#define MAXSIZE 100 //表中元素的最大个数 typedef int ElemType; //元素类型 typedef struct {

ElemType *elem; //线性表 int length; //表的实际长度 int listsize; //当前分配的存储容量 }SqList; //顺序表的类型名

5

3．建立顺序表时可利用随机函数自动产生数据。

注意问题：

1、 插入、删除时元素的移动原因、方向及先后顺序。 2、 理解函数形参与实参的传递关系。

部分源代码： DS.h

#include #include #include #include

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

typedef int Status;

SqList.h

#ifndef SQLIST_H_INCLUDED #define SQLIST_H_INCLUDED

#include \

typedef int ElemType; typedef struct {

ElemType *elem; int length; int listsize; }SqList; void menu();

Status InitList_Sq(SqList &L, int n);/*初始化顺序表*/ Status CreateList_Sq(SqList &L);/*建立顺序表*/ void PrintList_Sq(SqList L);/*输出顺序表*/

Status DeleteList_Sq(SqList &L,int i,ElemType &e);/*删除第i个元素*/ Status DeleteListX_Sq(SqList &L,ElemType x);/*删除值为x的元素*/

6

Status AdjustList_Sq(SqList &L);/*奇数排在偶数之前*/ Status OrderList_sq(SqList &L, int n);/*插入法生成递增有序表*/

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc );/*两个非递减有序表A和B，并把它们合并成一个非递减有序表C*/

#endif // SQLIST_H_INCLUDED

SqList.cpp

#include \

void menu() {

printf(\ 顺序表基本操作\\n\\n\ printf(\建 立 顺 序 表\\n\ printf(\遍 历 顺 序 表\\n\ printf(\删 除 第 i 个 元 素\\n\ printf(\删 除 值 为 x 的 元 素\\n\ printf(\奇 数 排 在 偶 数 之 前\\n\ printf(\插 入 法 生 成 递 增 有 序 表\\n\

printf(\两个非递减有序表La和Lb合并成非递减有序表Lc\\n\ printf(\退 出\\n\\n\}

/*初始化顺序表*/

Status InitList_Sq(SqList &L, int n) {

L.elem=(ElemType*)malloc(n*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=n; return OK; }

/*建立顺序表*/

Status CreateList_Sq(SqList &L)

7

{

int n, i;

printf(\请输入顺序表长度：\ scanf(\ if(InitList_Sq(L, n)) {

printf(\请输入%d个元素：\ for(i = 0; i < n; i++) {

scanf(\ L.length++; } return OK; } else

return ERROR; }

/*输出顺序表*/

void PrintList_Sq(SqList L) { int i;

printf(\顺序表中元素为：\\n\ for(i = 0; i < L.length; i++) {

printf(\ }

printf(\}

/*删除第i个元素*/

Status DeleteList_Sq(SqList &L,int i,ElemType &e) {

ElemType *p, *q;

if( (i<1) || (i>L.length) ) return ERROR; p = &(L.elem[i-1]); e = *p;

8

q = L.elem+L.length-1;

}

for(++p; p <= q; ++p) *(p-1) = *p; --L.length; return OK;

/*删除值为x的元素，删除成功返回OK，删除失败返回ERROR*/ Status DeleteListX_Sq(SqList &L,ElemType x) { }

/*奇数排在偶数之前*/ Status AdjustList_Sq(SqList &L) {

ElemType *p, *q; int temp;

return OK; }

/*插入法生成递增有序表，有序表生成成功返回OK，失败返回ERROR*/ Status OrderList_sq(SqList &L, int n) {

int i, j, x; /*x表示每次待插入的元素*/ }

/*两个非递减有序表A和B，并把它们合并成一个非递减有序表C*/ void MergeList_Sq(SqList La, SqList Lb, SqList &Lc ) {

ElemType *pa, *pb, *pc, *pa_last, *pb_last; pa = La.elem; pb = Lb.elem;

Lc.listsize = Lc.length = La.length+Lb.length;

pc = Lc.elem = (ElemType *)malloc(Lc.listsize * sizeof(ElemType));

9

ElemType *p, *q;

if (!Lc.elem) exit (OVERFLOW); pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1; while (pa <= pa_last && pb <= pb_last) {

if (*pa <= *pb) *pc++ = *pa++; else *pc++ = *pb++; }

while(pa <= pa_last) *pc++ = *pa++; while(pb <= pb_last) *pc++ = *pb++; }

main.cpp

#include \int main() {

int choice, n, i, x; SqList L, La, Lb, Lc; while(1) {

menu();

printf(\选择你的操作：\ scanf(\ switch(choice) {

case 1:

if(CreateList_Sq(L))

printf(\顺序表创建成功\\n\ else

printf(\顺序表创建失败\\n\ break; case 2:

PrintList_Sq(L); break; case 3:

printf(\请输入删除元素的位置：\ scanf(\ if(DeleteList_Sq(L, i, x))

10

printf(\合 并 生 成 升 序 链 表\\n\ printf(\分 解 链 表\\n\ printf(\退 出\\n\\n\}

/*初始化空表*/

Status Init_Linklist(LinkList &L) {

L=(LinkList)malloc(sizeof(Lnode)); if(!L) return ERROR; L->next=NULL; return OK;

}

/*尾插法建立单链表*/

Status Creat_Linklist(LinkList &L) { int x;

LinkList p,rear; Init_Linklist(L); rear = L;

printf(\输入-1表示输入结束\\n\ while(scanf(\ {

p = (LinkList)malloc(sizeof(Lnode)); if(!p) return ERROR; p->data = x; rear->next = p; rear = p; }

rear->next = NULL; return OK; }

/*单链表遍历*/

void Disp_Linklist(LinkList L) {

LinkList p;

16

p = L->next; while(p) {

printf(\ p = p->next; }

printf(\}

/*计算单链表长度*/ int length_Linklist(LinkList L) {

int count = 0; /*count表示单链表长度*/ LinkList p;

return count; }

/*单链表逆置*/

void Reverse_Linklist(LinkList L) {

LinkList p, q ; }

/*删除值为偶数的结点*/ void DelEven_Linklist(LinkList L) {

LinkList p, q; }

/*在有序单链表中插入元素，链表仍然有序，插入成功返回OK，插入失败返回ERROR*/ Status Insert_Linklist(LinkList L, int x) { ; }

17

/*创建非递减有序单链表，创建成功返回OK，创建失败返回ERROR*/ Status CreatOrder_Linklist(LinkList &L) { }

/*两个非递减有序单链表La和Lb合并成一个非递增有序链表Lc*/ void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc) { }

/*两个非递减有序单链表La和Lb合并成一个非递减有序链表Lc*/ void MergeAscend_Linklist(LinkList La, LinkList Lb, LinkList &Lc) {

LinkList pa, pb, pc; pa = La->next; pb = Lb->next; pc = Lc = La; while(pa && pb) {

if(pa->data <= pb->data) {

pc->next = pa; pc = pa; pa = pa->next; } else {

pc->next = pb; pc = pb; pb = pb->next; } }

pc->next = pa ? pa : pb; free(Lb); }

/*链表La按值分解成两个链表，La全部为奇数，Lb全部为偶数*/ void Split_Linklist(LinkList La, LinkList &Lb) { }

18

main.cpp

#include \int main() {

int choice, length; LinkList L, La, Lb, Lc; while(1) {

menu();

printf(\选择你的操作：\ scanf(\ switch(choice) {

case 1:

if(Creat_Linklist(L))

printf(\单链表创建成功\\n\ else

printf(\单链表创建失败\\n\ break; case 2:

Disp_Linklist(L); break; case 3:

length = length_Linklist(L);

printf(\单链表长度为：%d\\n\ break; case 4:

Reverse_Linklist(L);

printf(\逆置后的链表为：\\n\ Disp_Linklist(L); break; case 5:

DelEven_Linklist(L); printf(\新链表为：\\n\ Disp_Linklist(L); break; case 6:

if(CreatOrder_Linklist(L))

19

{

printf(\值有序链表为：\\n\ Disp_Linklist(L); } else

printf(\单链表创建失败\\n\ break; case 7:

} } }

CreatOrder_Linklist(La); CreatOrder_Linklist(Lb);

MergeDescend_Linklist(La, Lb, Lc);

printf(\合并后的新链表为：\\n\ break; case 8:

CreatOrder_Linklist(La); CreatOrder_Linklist(Lb);

MergeAscend_Linklist(La, Lb, Lc);

printf(\合并后的新链表为：\\n\ break; case 9:

Creat_Linklist(L); Split_Linklist(L, Lb);

printf(\分裂后的新链表为：\\n\ Disp_Linklist(L); Disp_Linklist(Lb); break; case 0: return 0; default:

printf(\输入错误，请重新输入\\n\20

1．在RedType中增加一个数据项验证各种排序算法的稳定性。

2．注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况选择合适的排序方法。

36

附：实验报告模板

郑 州 轻 工 业 学 院

课程名称：实验名称：院 （系）：姓 名：学 号：专业班级：指导教师：实 验 报 告

年 月 日

实验报告成绩评定表

评定项目 实验态度 内 容 实验认真，态度端正，遵守纪律，出勤情况。 按实验要求完成各种功能或操作，实验过程 代码书写规范，注释清晰，设计严谨，运行结果正确。 报告字迹整洁、内容丰富、条理清报告撰写 楚；图、表、文字表达准确规范，上交及时。 总成绩 评语： 指导老师签字： 年 月 日

满 分 20 评 分 总 分 40 40 采用五级分制：优、良、中、及格、不及格 1

实验报告正文

一、

二、

实验内容及要求 实验目的

1、 任务描述

2、 主要数据类型与变量

（必要时，可对数据类型和变量进一步解释或说明，增加可读性）

3、 算法或程序模块

（必要时，可对算法或程序模块进一步解释或说明，增加可读性）

三、

测试

1、 方案

描述测试方案、测试数据实例（文字数据、图或表等形式）…… 2、 结果

结合测试数据实例描述测试过程和测试结果，最好给出表示测试过程和结果的抓图，对测试结果进行分析并得出结论。 四、

总结与讨论

可针对本设计谈体会、谈遇到的问题、谈改进、谈设想等，展示你的概括、归纳和创新思维能力，看重的不是你的对与错，而是鼓励你的想象和创新思维。

附：程序的源代码

2

实验03 栈的基本操作

实验学时：2学时 实验类型：上机

背景知识：顺序栈、链栈，入栈、出栈。 目的要求：

1．掌握栈的思想及其存储实现。 2．掌握栈的常见算法的程序实现。

实验内容：

（1） 采用顺序存储实现栈的初始化、入栈、出栈操作。 （2） 采用链式存储实现栈的初始化、入栈、出栈操作。 （3） 在主函数中设计一个简单的菜单，分别测试上述算法。 （4） * 综合训练：

1） 堆栈操作合法性：假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成

的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。

2） 括号匹配检验：假设表达式中允许包括两种括号：圆括号和方括号，其嵌套的顺序随意，

即([]())或[([][])]等为正确的格式，[(])或([())等均为不正确格式。输入一个表达式，判断其中的括号是否能正确匹配。

3） 表达式转换：算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算

术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\\以及左右括号()，表达式不超过20个字符。在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

实验说明：

1．类型定义 顺序栈示例

#define MAX 100 //栈的最大值 typedef struct { SElemType *base； SElemType *top；

21

int stacksize； }SqStack； 链栈示例

typedef int ElemType; //元素类型 typedef struct snode {

SElemType data;

struct snode *next; }StackNode, *LinkStack;

2．算法4的每个子功能尽可能写成函数形式。

注意问题：

1．重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。 2．注意算法4的各个函数之间值的传递情况。

3．栈的算法是后续实验的基础（树、图、查找、排序等）。

22

实验04 队列的基本操作

实验学时：2学时 实验类型：上机

背景知识：循环队列、链队列，入队、出队。 目的要求：

1．掌握队列的思想及其存储实现。 2．掌握队列的常见算法的程序实现。

实验内容：

（1） 采用顺序存储实现循环队列的初始化、入队、出队操作。 （2） 采用链式存储实现队列的初始化、入队、出队操作。 （3） 在主函数中设计一个简单的菜单，分别测试上述算法。 （4） *综合训练：

银行排队系统模拟:请用一个队列来模拟银行排队系统，队列中存储序号。请设置一个菜单，包括叫号和排号两个选项。若选择叫号，则输出并删除队首元素；若选择排号，则顺序生成一个序号，加入队列，并输出该序号和前面有多少人等候。

实验说明：

1．类型定义 循环队列示例

#define MAXQSIZE 100 //队列的最大长度 typedef struct { QElemType *base；

int front； int rear； }SqQueue；

链队列示例 typedef struct QNode

{

QElemType data;

struct QNode *next; }QNode, *QueuePtr;

23

typedef struct { QueuePtr front;

QueuePtr rear; }LinkQueue;

注意问题：

1．重点理解队列的算法思想，能够根据实际情况选择合适的存储结构。 2．队列的算法是后续实验的基础（树、图、查找、排序等）。

24

实验05 二叉树的基本操作

实验学时：2学时 实验类型：上机

背景知识：二叉树的存储、建立、遍历及其应用。 目的要求：

1．掌握二叉树的存储实现。 2．掌握二叉树的遍历思想。

3．掌握二叉树的常见算法的程序实现。

实验内容：

（1） 从键盘上输入数据，建立二叉链表。

（2） 前序遍历、中序遍历、后序遍历二叉树：递归算法。 （3） 前序遍历、中序遍历、后序遍历二叉树：非递归算法。 （4） 借助队列实现二叉树的层次遍历。

（5） 在主函数中设计一个简单的菜单，分别调试上述算法。 （6） *综合训练：

家族关系查询系统：建立家族关系数据库，可以实现家族成员的添加，可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。

实验说明：

1．类型定义 //二叉链表存储

#define TElemType char //元素类型 typedef struct BiTNode{ TElemType data;

struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;

注意问题：

1．注意理解递归算法的执行步骤。

2．注意字符类型数据在输入时的处理。 3．重点理解如何利用栈结构实现非递归算法。

25

实验06 哈夫曼编码

实验学时：4学时 实验类型：综合型实验

背景知识：二叉树的应用、哈夫曼树。 目的要求：

掌握哈夫曼树和哈夫曼编码的基本思想和算法的程序实现。

实验内容：

（1）修理牧场：农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。

但是农夫自己没有锯子，请人锯木头的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

首先输入一个正整数N（N≤104），表示要将木头锯成N块。接着给出N个正整数Li（Li≤50），表示每段木块的长度。输出一个整数，即将木头锯成N块的最少花费。 例如： 输入：

8

4 5 1 2 1 3 1 1 输出：

49

*（2）压缩软件：

给定一篇文章，只含有英文大小写字母和空格，以.txt格式存储，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。

实验说明：

1．参考类型定义 //双亲孩子表示法 typedef struct {

26

unsigned int weight;

unsigned int parent, lchild, rchild;

} HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * * HuffmanCode; //动态分配数组存储哈夫曼编码表

注意问题：

1．递归算法的灵活应用。 2．多级指针的使用。

27

实验07 图的两种存储和遍历

实验学时：2学时 实验类型：上机

背景知识：图的存储、遍历及其应用。 目的要求：

1．掌握图的存储思想及其存储实现。

2．掌握图的深度、广度优先遍历算法思想及其程序实现。

实验内容：

（1） 键盘输入数据，分别建立一个有向图和一个无向图的邻接表。 （2） 输出该邻接表。

（3） 在有向图的邻接表的基础上计算各顶点的度，并输出。 （4） 采用邻接表存储实现无向图的深度优先遍历。 （5） 采用邻接表存储实现无向图的广度优先遍历。 （6） 在主函数中设计一个简单的菜单，分别调试上述算法。 （7） *综合训练

地下迷宫探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

输入格式：

输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1

若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点

28

序列，最后输出0，此时表示迷宫不是连通图。

由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。 输入样例：

6 8 1 1 2 2 3 3 4 4 5 5 6 6 4 3 6 1 5 输出样例：

1 2 3 4 5 6 5 4 3 2 1

实验说明：

1．类型定义（邻接表存储）

#define MAX_VERTEX_NUM 20 //顶点最大个数 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc;

int weight; //边的权值 }ArcNode; //表结点

#define VertexType int //顶点元素类型 typedef struct VNode{ VertexType data; ArcNode *firstarc;

}VNode, AdjList[MAX_VERTEX_NUM]; // typedef struct{

AdjList vertices;

int vexnum, arcnum; //顶点的实际数，边的实际数 int kind; }ALGraph;

2．上述类型定义可以根据实际情况适当调整。 3．算法4、5分别利用栈、队列实现非递归算法。

29

注意问题：

1．注意理解各算法实现时所采用的存储结构。

2．注意区别正、逆邻接。

30

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