数据结构实验指导书2013

更新时间：2023-10-29 22:16:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

西安科技大学通信学院数据结构与算法实验指导书

张小红 2013.1

实验一线性表 ............................................................. 1 (一) 实验目的 ............................................................ 1 (二) 实验内容 ............................................................ 1 (三) 实验报告 ............................................................ 8 实验二堆栈 ............................................................... 9 (一) 实验目的 ............................................................ 9 (二) 实验内容 ............................................................ 9 (三) 实验报告 ........................................................... 16 实验三队列 .............................................................. 17 (一) 实验目的 ........................................................... 17 (二) 实验内容 ........................................................... 17 (三) 实验报告 ........................................................... 20 实验四模式匹配 .......................................................... 21 (一) 实验目的 ........................................................... 21 (二) 实验内容 ........................................................... 21 (三) 实验报告 ........................................................... 24 实验五二叉树 ............................................................ 25 (一) 实验目的 ........................................................... 25 (二) 实验内容 ........................................................... 25 (三) 实验报告 ........................................................... 32 实验六图和图的遍历 ...................................................... 33 (一) 实验目的 ........................................................... 33 (二) 实验内容 ........................................................... 33 (三) 实验报告 ........................................................... 39 实验七查找 .............................................................. 40 (一) 实验目的 ........................................................... 40 (二) 实验内容 ........................................................... 40 (三) 实验报告 ........................................................... 44 实验八内部排序 .......................................................... 45 (一) 实验目的 ........................................................... 45 (二) 实验内容 ........................................................... 45 (三) 实验报告 ........................................................... 46 附录1：实验报告 .......................................................... 48 实验名称：（一）线性表 ................................................... 48 实验名称：（二）堆栈 ..................................................... 50 实验名称：（三）队列 ..................................................... 52 实验名称：（四）模式匹配 ................................................. 56 实验名称：（五）二叉树 ................................................... 58

实验名称：（六）图和图的遍历 ............................................. 60 实验名称：（七）查找 ..................................................... 62 实验名称：（八）内部排序 ................................................. 64 附录2： .................................................................. 69 《数据结构》模拟试卷一 .................................................. 69 《数据结构》模拟试卷二 .................................................. 73

III

实验一线性表

(一) 实验目的

（1）掌握线性表的顺序存储（2）掌握线性表的链式存储

（3）掌握基本算法（建表、插入、删除）的实现

(二) 实验内容

1. 线性表的顺序存储：掌握线性表的顺序存储结构及其基本操作、合并、逆置等算法

设顺序表的存储结构定义如下：（同学们可扩展考虑其他形式的存储结构定义） #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct {

int *elem; // 存储空间基址 int length; // 当前长度

int listsize; // 当前分配的存储容量（以sizeof(int)为单位） }SqList;

[题目1：编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。]

#include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct {

int *elem; int length; int listsize; }SqList;

int InitList_Sq(SqList &L) {

// 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE // 请补全代码

}

int Load_Sq(SqList &L) {

// 输出顺序表中的所有元素 int i;

if( ) printf(\ // 请填空 else { printf(\ for( ) printf(\ ); // 请填空 }

printf(\ return OK; }

int ListInsert_Sq(SqList &L,int i,int e) {

// 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e // i的合法值为1≤i≤L.length +1 // 请补全代码 }

int ListDelete_Sq(SqList &L,int i, int &e) {

// 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值 // i的合法值为1≤i≤L.length // 请补全代码 }

int main() {

SqList T; int a, i;

ElemType e, x;

if( ) // 判断顺序表是否创建成功，请填空 { printf(\ }

while(1) { printf(\ scanf(\

switch(a) { case 1: scanf(\ if( ) printf(\判断i值是否合法，请填空 else printf(\ break; case 2: scanf(\ if( ) printf(\判断i值是否合法，请填空 else printf(\ break; case 3: Load_Sq(T); break; case 0: return 1; } } }

测试样例格式说明：根据菜单操作：

1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开 2、输入2，表示要实现删除操作，紧跟着要输入删除的位置 3、输入3，表示要输出顺序表的所有元素 4、输入0，表示程序结束

[题目2：编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。本题不提供代码，请同学们独立完成，所需子函数参考前面题目1完成的内容。]

测试样例格式说明： [键盘输入]

第一行：顺序表A的元素个数

第二行：顺序表A的各元素（非递减），用空格分开第三行：顺序表B的元素个数

第四行：顺序表B的各元素（非递减），用空格分开 [正确输出]

第一行：顺序表A的元素列表第二行：顺序表B的元素列表

第三行：合并后顺序表C的元素列表

测试样例：

[第一组自测数据] [第二组自测数据] [键盘输入] [键盘输入]

5↙ 6↙ 1 3 5 7 9↙ 12 24 45 62 84 96↙ 5↙ 4↙ 2 4 6 8 10↙ 15 31 75 86↙ [正确输出] [正确输出]

List A:1 3 5 7 9 List A:12 24 45 62 84 96 List B:2 4 6 8 10 List B:15 31 75 86 List C:1 2 3 4 5 6 7 8 9 10 List C:12 15 24 31 45 62 75 84 86 96

[题目3：设有一顺序表A=（a0,a1,..., ai,...an-1)，其逆顺序表定义为A'=( an-1,..., ai,...,a1, a0)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。本题不提供代码，请同学们独立完成，所需子函数参考前面题目1完成的内容。]

测试样例格式说明： [键盘输入]

第一行：输入顺序表的元素个数

第二行：输入顺序表的各元素，用空格分开 [正确输出]

第一行：逆置前的顺序表元素列表第二行：逆置后的顺序表元素列表

测试样例：

[第一组自测数据] [第二组自测数据]

[键盘输入] [键盘输入] 10↙ 8↙

1 2 3 4 5 6 7 8 9 10↙ 32 97 54 65 35 84 61 75↙ [正确输出] [正确输出]

The List is:1 2 3 4 5 6 7 8 9 10 The List is:32 97 54 65 35 84 61 75 The turned List is:10 9 8 7 6 5 4 3 2 1 The turned List is:75 61 84 35 65 54 97 32

2. 线性表的链式存储：掌握线性表的链式存储结构及其基本操作、合并、逆置等算法。本实验以单链表为例，在完成题目的过程中，同学们可扩展考虑双链表及循环链表等结构的操作。设单链表的存储结构定义如下：（同学们可扩展考虑其他形式的存储结构定义）

#include typedef struct LNode {

int data; // 存储在结点中的数据 struct LNode *next; // 指向下一结点的指针 }LNode,*LinkList;

[题目4：编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全内容]

#include #include #define ERROR 0 #define OK 1

#define ElemType int

typedef struct LNode {

int data;

struct LNode *next; }LNode,*LinkList;

int CreateLink_L(LinkList &L,int n){ // 创建含有n个元素的单链表 LinkList p,q; int i;

ElemType e;

L = (LinkList)malloc(sizeof(LNode));

L->next = NULL; // 先建立一个带头结点的单链表 q = (LinkList)malloc(sizeof(LNode)); q = L;

for (i=0; i

p = (LinkList)malloc(sizeof(LNode)); // 生成新结点 // 请补全代码 }

return OK; }

int LoadLink_L(LinkList &L){ // 单链表遍历

LinkList p = L->next;

if( )printf(\请填空 else {

printf(\

while( ) // 请填空 { printf(\ // 请填空 } }

printf(\ return OK; }

int LinkInsert_L(LinkList &L,int i,ElemType e){ // 算法2.9

// 在带头结点的单链线性表L中第i个位置之前插入元素e // 请补全代码 }

int LinkDelete_L(LinkList &L,int i, ElemType &e){ // 算法2.10

// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值 // 请补全代码 }

int main() {

LinkList T; int a,n,i;

ElemType x, e;

printf(\ scanf(\

printf(\

if( ) // 判断链表是否创建成功，请填空 {

printf(\ LoadLink_L(T); }

while(1) { printf(\ scanf(\ switch(a) { case 1: scanf(\ if( ) printf(\判断i值是否合法，请填空 else printf(\ break; case 2: scanf(\ if( ) printf(\判断i值是否合法，请填空 else printf(\ break; case 3: LoadLink_L(T);

}

break; case 0: return 1;

测试样例格式说明：根据菜单操作：

[题目5：设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。本题不提供代码，请同学们独立完成，所需子函数参考题目4完成的内容。]

测试样例格式说明： [键盘输入]

第一行：单链表A的元素个数

第二行：单链表A的各元素（非递减），用空格分开第三行：单链表B的元素个数

第四行：单链表B的各元素（非递减），用空格分开 [正确输出]

第一行：单链表A的元素列表第二行：单链表B的元素列表

第三行：合并后单链表C的元素列表

测试样例：

[键盘输入] 6↙

12 24 45 62 84 96↙ 4↙

15 31 75 86↙ [正确输出]

List A:12 24 45 62 84 96 List B:15 31 75 86

List C:12 15 24 31 45 62 75 84 86 96

[题目6：设有一线性表A=（a0,a1,..., ai,...an-1)，其逆线性表定义为A'=( an-1,..., ai,...,a1, a0)，设计一个算法，将链式线性表逆置，要求线性表仍占用原线性表的空间。本题不提供代码，请同学们独立完成，所需子函数参考题目4完成的内容。]

测试样例格式说明： [键盘输入]

第一行：输入n，表示单链表的元素个数第二行：输入单链表的各元素，用空格分开 [正确输出]

第一行：输出单链表逆置前的元素列表第二行：输出单链表逆置后的元素列表

测试样例：

[键盘输入] 8↙

32 97 54 65 35 84 61 75↙ [正确输出]

The List is:32 97 54 65 35 84 61 75

The turned List is:75 62 84 35 65 54 97 32

(三) 实验报告

（1）（2）（3）（4）（5）（6）

本实验所有题目要求在JudgeOnline上提交通过。实验报告针对以上所有实验内容。

实验目的主要是阐述本实验需要掌握的知识要点。

实验总结主要是对实验内容的掌握及理解程序作一个归纳性的叙述。对于思考题进行分析和思考，并做出相应的结论。本次实验报告可以在堂下完成。

实验二堆栈

(一) 实验目的

(1) 理解堆栈的结构及操作特点

(2) 实现堆栈的PUSH、POP等基本操作算法 (3) 熟练掌握入栈、出栈时栈顶指针的变化情况 (4) 掌握堆栈的实际应用

(二) 实验内容

1. 顺序栈的基本操作

[题目1：创建一个空的顺序栈，并实现栈的入栈、出栈、返回栈的长度、返回栈顶元素、栈的遍历等基本算法。请将下面的程序补充完整。]

#include #include #define OK 1 #define ERROR 0

#define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量

typedef int SElemType; // 定义栈元素类型

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等

struct SqStack {

SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针

int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈

Status InitStack(SqStack &S) {

// 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE // 请补全代码 }

Status Push(SqStack &S,SElemType e) {

// 在栈S中插入元素e为新的栈顶元素 // 请补全代码 }

Status Pop(SqStack &S,SElemType &e) {

// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR // 请补全代码 }

Status GetTop(SqStack S,SElemType &e)

{

// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR // 请补全代码 }

int StackLength(SqStack S) {

// 返回栈S的元素个数 // 请补全代码 }

Status StackTraverse(SqStack S) {

// 从栈顶到栈底依次输出栈中的每个元素 SElemType *p = (SElemType *)malloc(sizeof(SElemType)); p = //请填空 if( )printf(\请填空 else { printf(\ p--; while( ) //请填空 { printf(\ //请填空 } } printf(\ return OK; }

int main() {

int a;

SqStack S;

SElemType x, e;

if( ) // 判断顺序表是否创建成功，请填空

{ printf(\

}

while(1) {

printf(\\\n2:Pop \\n3:Get the Top \\n4:Return the Length of the Stack\\n5:Load the

Stack\\n0:Exit\\nPlease choose:\\n\

scanf(\ switch(a) { case 1: scanf(\

if( ) printf(\判断Push是否合法，请填空

else printf(\ break; case 2: if( ) printf(\判断Pop是否合法，请填空 else printf(\ break; case 3: if( )printf(\判断Get Top是否合法，请填空 else printf(\

break; case 4: printf(\ ); //请填空 break; case 5: //请填空 break; case 0: return 1; } } }

测试样例格式说明：根据菜单操作：

1、输入1，表示要实现Push操作，紧跟着输入要Push的元素 2、输入2，表示要实现Pop操作 3、输入3，返回栈顶元素 4、输入4，返回栈的元素个数

5、输入5，表示从栈顶到栈底输出栈的所有元素 6、输入0，表示程序结束

2. 栈的应用

[题目2：利用顺序栈的基本操作算法，编写满足下列要求的数制转换程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。]

测试样例格式说明： [键盘输入]

第一行：输入一个非负的十进制整数 [正确输出］

第一行：与输入等值的八进制数

测试样例

[第一组自测数据] [第二组自测数据] [键盘输入] [键盘输入] 15↙ 38↙

[正确输出] [正确输出] 17 46

[题目3：利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（[]（））或[（[][]）]等为正确的格式，[（]或（[（））或（（）]）均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。本题给出部分chech()函数，要求将check()函数补充完整，并完成整个程序。]

typedef char SElemType; #include #include #include

#include // exit() #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等 #define STACK_INIT_SIZE 10 // 存储空间初始分配量

#define STACKINCREMENT 2 // 存储空间分配增量 struct SqStack {

SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针

int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈

Status InitStack(SqStack &S) { }

Status StackEmpty(SqStack S) { }

Status Push(SqStack &S,SElemType e) { }

Status Pop(SqStack &S,SElemType &e) { }

void check()

{ // 对于输入的任意一个字符串，检验括号是否配对 SqStack s;

SElemType ch[80],*p,e;

if(InitStack(s)) // 初始化栈成功 {

//printf(\请输入表达式\\n\

__________________________________; p=ch;

while(*p) // 没到串尾 switch(*p) {

case '(':

case '[':_______________________;

break; // 左括号入栈，且p++ case ')':

case ']':if(!StackEmpty(s)) // 栈不空 {

_________________________; // 弹出栈顶元素

if(*p==')'&&e!='('||__________________&&__________________) // 弹出的栈顶元素与*p不配对

{

printf(\ exit(ERROR); } else {

__________________________; break; // 跳出switch语句 } }

// 请补全代码 }

int QueueLength(SqQueue Q) {

// 返回Q的元素个数 // 请补全代码 }

Status QueueTraverse(SqQueue Q) {

// 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR. int i;

i=Q.front;

if( )printf(\ //请填空 else{ printf(\ while( ) //请填空 { printf(\ ); //请填空 i = ; //请填空 } }

printf(\ return OK; }

int main() {

int a;

SqQueue S;

QElemType x, e;

if( ) // 判断顺序表是否创建成功，请填空 { printf(\ }

while(1) { printf(\\\n2:Delete \\n3:Get the Front \\n4:Return the Length of the Queue\\n5:Load the

Queue\\n0:Exit\\nPlease choose:\\n\

scanf(\ switch(a) { case 1: scanf(\ if( ) printf(\判断入队是否合法，请填空 else printf(\ break; case 2: if( ) printf(\判断出队是否合法，请填空 else printf(\ break; case 3: if( )printf(\判断Get Head是否合法，请填空 else printf(\ break; case 4: printf(\ ); //请填空 break; case 5: //请填空

}

break; case 0: return 1;

测试样例格式说明：根据菜单操作：

1、输入1，表示要实现入队操作，紧跟着输入要入队的元素 2、输入2，表示要实现出队操作 3、输入3，返回队头元素

4、输入4，返回队列的元素个数

5、输入5，表示从队头到队尾输出队的所有元素 6、输入0，表示程序结束

2. 队列的应用

[题目2：某银行有一个客户办理业务站，在一天内随机地有客户到达，设每位客户的业务办理时间是某个范围内的值。设只有一个窗口，一位业务人员，要求程序模拟统计在一天时间内，所有客户的平均等待时间。模拟数据按客户到达的先后顺序依次由键盘输入，对应每位客户有两个数据，到达时刻和需要办理业务的时间。]

测试样例格式说明： [键盘输入]

第一行：一天内的客户总人数n

第二行：第一个客户的到达时刻和需要办理业务的时间第三行：第二个客户的到达时刻和需要办理业务的时间 ??

第n行：第n - 1个客户的到达时刻和需要办理业务的时间第n + 1行：第n 个客户的到达时刻和需要办理业务的时间 [正确输出］

第一行：所有客户的平均等待时间（精确到小数点后2位）

测试样例：

[第一组自测数据] [键盘输入] 3↙ 1 3↙ 2 1↙ 3 5↙

[正确输出] 1.33

[第二组自测数据] [键盘输入] 4↙ 1 1↙ 12 5↙ 15 1↙ 16 5↙

[正确输出] 1.00

(三) 实验报告

（1）本实验所有题目要求在JudgeOnline上提交通过。（2）实验报告针对以上所有实验内容。

（3）实验总结主要是对实验内容的掌握及理解程序作一个归纳性的叙述。（4）对于思考题进行分析和思考，并做出相应的结论。（5）本次实验报告可以在堂下完成。

实验四模式匹配

(一) 实验目的

﹙1﹚ 理解和掌握KMP算法及计算NEXT值的方法。

(二) 实验内容

1. NEXT值的计算

本实验采用定长顺序存储结构存储字符串，同学们可扩展考虑其他形式存储结构的相应操作。 [题目1：编写算法，录入多个字符串计算并验证NEXT值，输入0结束。本题目给出部分代码，请补全内容。]

#include #include #include

#define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN+1]; // 0号单元存放串的长度

void get_next(SString T,int next[]){ // 算法4.7

// 求模式串T的next函数值并存入数组next // 请补全代码 }

void main(){

int next[MAXSTRLEN]; SString S; int n,i,j; char ch;

scanf(\ // 指定要验证NEXT值的字符串个数 ch=getchar();

for(i=1;i<=n;i++) {

ch=getchar();

for(j=1;j<=MAXSTRLEN&&(ch!='\\n');j++) // 录入字符串 {

S[j]=ch;

ch=getchar(); }

S[0]=j-1; // S[0]用于存储字符串中字符个数

get_next(S,next); printf(\for(j=1;j<=S[0];j++) printf(\printf(\} }

测试样例格式说明： [键盘输入]

第一行：输入n，表示有n个需计算NEXT值的字符串第二至n+1行：每行输入一个字符串 [正确输出]

第1至第n行：通过计算每相应行的字符串得出的NEXT值

测试样例：

[键盘输入] 4↙

abcdefg↙ aaaaab↙ abaabcac↙ aaabaaab↙ [正确输出]

NEXT J is:0111111 NEXT J is:012345 NEXT J is:01122312 NEXT J is:01231234

2. KMP算法

[题目2：用KMP算法对主串和模式串进行模式匹配。本题目给出部分代码，请补全内容。]

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

#define INFEASLBLE -1 #define OVERFLOW -2 #define MAXSTRLEN 255 //用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度

void get_next(SString T,int next[]){ // 算法4.7

#FG###C#H##↙ [正确输出] [正确输出] ABC ABDEFGCH BAC CEBGFACH BCA EDGFBHCA

2. 实现二叉排序树的各种算法（本题目为综合性实验,除本指导书要求外,要求另外书写实验报告并提交电子版,格式要求由任课教师提供电子版。为便于不同能力的同学成功地提交代码,本实验分为2个题目）

[题目2：用函数实现如下算法：

（1）插入新结点

（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法（4）层次遍历二叉树

（5）在二叉树中查找给定关键字(函数返回值为成功1,失败0)

测试样例格式说明： [键盘输入]

第一行：准备建树的结点个数n

第二行：输入n个整数，用空格分隔第三行：输入待查找的关键字第四行：输入待查找的关键字第五行：输入待插入的关键字

实验六图和图的遍历

(一) 实验目的

(1) 掌握图的邻接表存储结构及基本操作的实现 (2) 掌握邻接表结构下图的深度优先遍历的算法 (3) 掌握邻接表结构下图的广度优先遍历的算法

(二) 实验内容

1. 实现图的存储结构

[题目1：实现有向图的邻接矩阵存储结构。]

测试样例格式说明： [键盘输入]

第一行：输入图的顶点个数n（各个顶点的默认编号为1~n），边的条数m。

第二 ~ m+1行：每行输入两个顶点编号i、j，表示连接顶点i到顶点j的一条边。 [正确输出］

分n行输出n*n的邻接矩阵，表示所输入的图存储，顶点i和顶点j之间如果有边相连，则输出1，没边相连则输出0。测试样例：

[第一组自测数据] [键盘输入] 4 4↙ 1 2↙ 1 3↙ 3 4↙ 4 1↙

[正确输出] 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0

提示：输入的图如下所示：

1 2 3 4

2．实现图的遍历算法

[题目2：实现图的邻接表存储结构及一些基本操作函数。在此基础上实现图的深度遍历算

法并加以测试。本题只给出部分代码,请补全内容。] 参考代码：

#include /* 图的顶点使用字符串来表示 */ #include /* malloc()等 */ #include

#include /* exit() */

#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */

typedef char VertexType[MAX_NAME]; /* 图顶点字符串类型，最大长度2 */ typedef int InfoType; /* 顶点权值类型 */ /* 图的邻接表存储表示，教材163页 */ #define MAX_VERTEX_NUM 20

typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct ArcNode {

int adjvex; /* 该弧所指向的顶点的位置 */

struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; /* 网的权值指针） */ }ArcNode; /* 表结点 */ typedef struct {

VertexType data; /* 顶点信息 */

ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */ typedef struct {

AdjList vertices;

int vexnum,arcnum; /* 图的当前顶点数和弧数 */ int kind; /* 图的种类标志 */ }ALGraph;

/* LocateVex，初始条件: 图G存在,u和G中顶点有相同特征。操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int LocateVex(ALGraph G,VertexType u) { int i;

for(i=0;i

if(strcmp(u,G.vertices[i].data)==0) return i; return -1; }

/* CreateGraph采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */ void CreateGraph(ALGraph *G) { int i,j,k;

int w; /* 权值 */ VertexType va,vb; ArcNode *p;

printf(\ scanf(\

printf(\ scanf(\ printf(\

for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */ {

scanf(\ (*G).vertices[i].firstarc=NULL; }

if((*G).kind==1||(*G).kind==3) /* 网 */

printf(\ arc weight,head and tail (Takes the gap by the blank space ):\\n\ else /* 图 */

printf(\ arc head and tail (Takes the gap by the blank space ):\\n\ for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */ {

if((*G).kind==1||(*G).kind==3) /* 网 */ scanf(\ else /* 图 */

scanf(\

i=LocateVex(*G,va); /* 弧尾 */ j=LocateVex(*G,vb); /* 弧头 */

p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;

if((*G).kind==1||(*G).kind==3) /* 网 */ {

p->info=(int *)malloc(sizeof(int)); *(p->info)=w; } else

p->info=NULL; /* 图 */

p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */ (*G).vertices[i].firstarc=p;

if((*G).kind>=2) /* 无向图或网,产生第二个表结点 */ {

p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i;

if((*G).kind==3) /* 无向网 */ {

p->info=(int*)malloc(sizeof(int)); *(p->info)=w; } else

p->info=NULL; /* 无向图 */

p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */ (*G).vertices[j].firstarc=p; } }

}

/* GetVex，初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */ VertexType* GetVex(ALGraph G,int v) { if(v>=G.vexnum||v<0) exit(0);

return &G.vertices[v].data; }

/* FirstAdjVex，初始条件: 图G存在,v是G中某个顶点。操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */ int FirstAdjVex(ALGraph G,VertexType v) { ArcNode *p; int v1;

v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ p=G.vertices[v1].firstarc; if(p)

return p->adjvex; else

return -1; }

/* NextAdjVex，初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点操作结果: 返回v的（相对于w的）下一个邻接顶点的序号。若w是v的最后一个邻接点,则返回-1 */ int NextAdjVex(ALGraph G,VertexType v,VertexType w) { ArcNode *p; int v1,w1;

v1=LocateVex(G,v); /* v1为顶点v在图G中的序号 */ w1=LocateVex(G,w); /* w1为顶点w在图G中的序号 */ p=G.vertices[v1].firstarc;

while(p&&p->adjvex!=w1) /* 指针p不空且所指表结点不是w */ p=p->nextarc;

if(!p||!p->nextarc) /* 没找到w或w是最后一个邻接点 */ return -1;

else /* p->adjvex==w */

return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */ }

int visited[MAX_VERTEX_NUM];

/* 访问标志数组(全局量),未访问标记0，访问标记1 */ void (*VisitFunc)(char* v); /* 函数变量(全局量) */ void DFS(ALGraph G,int v)

{ /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */ int w;

VertexType v1,w1;

strcpy(v1,*GetVex(G,v));

; /* 设置访问标志为TRUE(已访问) */ ; /* 访问第v个顶点 */

for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))