3.3 栈和队列
栈和队列是两种重要的数据结构，它们都属于线性结构。栈和队列广泛应用于各种软件系统中，因此它们有着十分重要的作用。学好栈和队列的应用将会在以后的软件开发中起到很大的作用。本节应用几个典型实例来演示栈和队列的应用，相信通过本节的学习读者能够掌握栈和队列的使用方法。
实例090 应用栈实现进制转换
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\090
实例说明
本实例实现应用栈实现进制的转换，可以将十进制数转换为其他进制数。程序运行效果如图3.24所示。
图3.24 进制转换程序示意图
技术要点
本实例使用栈实现进制的转换。由于栈具有后进先出的固有特性，使栈成为了程序设计中有用的工具。这里实现的是十进制数n和其他进制数d的转换。其解决方法很多，本实例中算法思想为：将十进制数与要转换的进制数值做整除运算，取余，将整除运算得到的商再与要转换的进制数值做整除运算，再取余，重复上面操作，直到除尽，最后将得到的余数逆序排列，即是要得到的结果。
例如要将十进制数1000转换为八进制数，其运算过程如表：
其中div为整除运算，mod为求余运算。
因为进制转换结果是上述取余运算的逆序序列，这正符合了栈的后进先出的特性。先将每次运算所得的余数入栈，然后出栈，得到的出栈序列即是所要的结果。
提示：栈是顺序表的特殊形式。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）声明struct student类型：
typedef struct{
DataType *base;
DataType *top;
int stacksize;
}SeqStack;
（4）创建自定义函数实现构造栈、进栈、出栈、取栈顶元素等操作。实现代码如下：
void Initial（SeqStack *s）
{/*构造一个空栈*/
s->base=（DataType *）malloc（STACK_SIZE * sizeof（DataType））;
if（!s->base）exit（-1）;
s->top=s->base;
s->stacksize=STACK_SIZE;
}
/*判栈空*/
int IsEmpty（SeqStack *S）
{
return S->top= =S->base;
}
/*判栈满*/
int IsFull（SeqStack *S）
{
return S->top-S->base= =STACK_SIZE-1;
}
/*进栈*/
void Push（SeqStack *S,DataType x）
{
if（IsFull（S））
{
printf（"栈上溢"）; /*上溢,退出运行*/
exit（1）;
}
*S->top++ =x; /*栈顶指针加1后将x入栈*/
}
/*出栈*/
DataType Pop（SeqStack *S）
{
if（IsEmpty（S））
{
printf（"栈为空"）; /*下溢,退出运行*/
exit（1）;
}
return *--S->top; /*栈顶元素返回后将栈顶指针减1*/
}
/* 取栈顶元素*/
DataType Top（SeqStack *S）
{
if（IsEmpty（S））
{
printf（"栈为空"）; /*下溢,退出运行*/
exit（1）;
}
return *（S->top-1）;
}
（5）创建自定义函数conversion（）实现十进制整数的进制转换功能。实现代码如下：
void conversion（int N,int B）
{/*假设N是非负的十进制整数，输出等值的B进制数*/
int i;
SeqStack *S;
Initial（S）;
while（N）{ /*从右向左产生B进制的各位数字，并将其进栈*/
Push（S,N%B）; /*将bi进栈0<=i<=j*/
N=N/B;
}
while（!IsEmpty（S））{ /*栈非空时退栈输出*/
i=Pop（S）;
printf（"%d",i）;
}
}
（6）创建main（）函数作为程序的入口函数，调用conversion（）自定义函数实现对给定的十进制整数进行进制转换。程序代码如下：
void main（）
{
int n,d;
printf（"Input the integer you want to transform:"）;
scanf（"%d",&n）;
printf（"Input the integer of the system: "）;
scanf（"%d",&d）;
printf（"result:"）;
conversion（n,d）;
getch（）;
}
举一反三
根据本实例，读者可以：
顺序栈公用。
用数组实现进制的转换。
实例091 用栈设置密码
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\091
实例说明
本实例使用栈设置一个密码，当输入错误密码时，系统提示密码错误，输入错误3 次退出。输入了正确的密码后，显示密码正确。程序密码为“13579”，程序运行效果如图3.25所示。
图3.25 设置密码程序示意图
技术要点
本实例使用栈来设置密码，应用到了栈的定义、初始化、进栈、出栈等功能。这里将这些功能设置成了单个的自定义函数，并在相应的位置进行调用。本实例首先定义一个密码字符串，将键盘上输入的密码压倒栈中，将栈中数据与密码字符串进行比较，看密码是否正确。出入错误3次则退出。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include<string.h>
#include<conio.h>
#include<stdlib.h>
（3）预定义全局变量：
#define STACK_SIZE 100 /*假定预分配的栈空间最多为100个元素*/
char PASSWORD[10]= "13579";
typedef char DataType; /*假定栈元素的数据类型为字符*/
（4）声明struct student类型：
typedef struct{
DataType *base;
DataType *top;
int stacksize;
int length;
}SeqStack;
（5）创建自定义函数实现构造栈、进栈、出栈、取栈顶元素等操作。实现代码如下：
void Initial（SeqStack *s）
{
s->base=（DataType *）malloc（STACK_SIZE * sizeof（DataType））;
if（!s->base）exit（-1）;
s->top=s->base;
s->stacksize=STACK_SIZE;
s->length=0;
}
/*判栈空*/
int IsEmpty（SeqStack *S）
{
return S->top= =S->base;
}
/*判栈满*/
int IsFull（SeqStack *S）
{
return S->top-S->base= =STACK_SIZE-1;
}
/*进栈*/
void Push（SeqStack *S,DataType x）
{
if（IsFull（S））
{
printf（"栈上溢"）; /*上溢,退出运行*/
exit（1）;
}
*（S->top++）=x; /*栈顶指针加1后将x入栈*/
++S->length;
/* printf（"%c",*S->top）;*/
}
/*出栈*/
DataType Pop（SeqStack *S）
{
if（IsEmpty（S））
{
printf（"栈为空"）; /*下溢,退出运行*/
exit（1）;
}
--（S->length）;
return*--S->top; /*栈顶元素返回后将栈顶指针减1*/
}
/* 取栈顶元素*/
DataType GetTop（SeqStack *S,DataType *e）
{
if（IsEmpty（S））
{
printf（"栈为空"）; /*下溢,退出运行*/
exit（1）;
}
*e= *（S->top-1）;
S->top--;
}
void change（SeqStack *s,char *a）
{
int n=s->length-1;
while（!IsEmpty（s））
{
GetTop（s,&a[n--]）;} /*获取栈顶元素*/
}
void clearstack（SeqStack *s）
{
s->top=s->base; /*清空栈*/
s->length=0; /*设置栈的长度为0*/
}
（6）创建PwdSet（）自定义函数，实现使用栈判断用户输入的密码是否正确，程序代码如下：
void PwdSet（SeqStack *s）
{
int i=0,k,j=0;
DataType ch,*a;
k=strlen（PASSWORD）;
printf（"input password "）;
for（;;）
{
if（i>=3）
{
i++;
break;
}
else if（i>0 && i<3）
{
for（j=1;j<=s->length;j++）printf（" "）;
clearstack（s）; /*清空栈*/
}
for（;;）
{
ch=getch（）;
if（ch!=13）
{
if（ch= =8）{
Pop（s）;
gotoxy（4+j,2）;
printf（" "）;
gotoxy（4+j,2）;
}
else{printf（"*"）;Push（s,ch）;}
j=s->length;
}
else
{printf（"\n"）;
break;}
}
i++;
if（k!=j）continue;
else
{
a=（DataType *）malloc（s->length * sizeof（DataType））;
change（s,a）;
for（j=1;j<=s->length;）
{
if（*（a+j-1）= =PASSWORD[j-1]）j++;
else
{
j=s->length+2;
printf（"\n passwrod wrong!\n"）;
break;
}
}
if（j= =s->length+2）continue;
else break;
}
}
if（i= =4）printf（"\n Have no chance,It will quit!"）;
else printf（"\n password right!\n"）;
free（a）;
}
（7）创建main（）函数作为程序的入口函数，调用PwdSet（）自定义函数使用栈判断用户输入的密码是否正确。程序代码如下：
main（）
{
LinkList L1;
L1 = create（）;
printf（"The linklist is:\n"）;
while（L1）
{
printf（"%c ", L1->num）;
L1 = L1->next;
}
getch（）;
}
举一反三
根据本实例，读者可以：
用数组仿真堆栈。
动态堆栈。
实例092 栈实现行编辑程序
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\092
实例说明
本实例要求编写一个简单的行编辑程序，它的主要功能是将用户输入的信息存入用户的数据区。当用户发现输入错误时，可补进一个“#”，表示前一个字符无效；当发现错误较多是可补进一个“@”，表示前面写过的字符均无效，回车表示该行输入完毕。运行结果如图3.26所示。
图3.26 栈实现行编辑程序
技术要点
根据本实例的要求，可将这个输入缓冲区以一个栈的形式来实现，当从终端接受了一个字符时先做判断，看它是不是退格符（“#”）或清行符（“@”），若是退格符，则进行一次出栈，若是清行符则进行一次清空栈的操作。当然这些操作的前提是先初始化一个栈，并自定义栈的相关操作函数，像出栈函数、进栈函数、清空栈的函数等。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件、进行宏定义及数据类型的指定：
#include <stdio.h>
#define STACK_SIZE 100 /*假定预分配的栈空间最多为100个元素*/
typedef char DataType; /*设定DataType的代表的数据类型为字符型*/
（3）定义结构体类型及变量：
typedef struct /*定义结构体*/
{
DataType*base; /*定义栈底指针*/
DataType*top; /*定义栈顶指针*/
int stacksize; /*定义栈的大小*/
}SeqStack; /*SeqStack为该结构体类型*/
（4）创建自定义函数实现构造栈、进栈、出栈、取栈顶元素、清空栈等操作。实现代码如下：
void Initial（SeqStack *S） /*初始化栈*/
{
S->base =（DataType*）malloc（STACK_SIZE *sizeof（DataType））;
if（!S->base）
exit（-1）;
S->top=S->base; /*栈为空时栈顶栈底指针指向同一处*/
S->stacksize = STACK_SIZE;
}
int IsEmpty（SeqStack*S） /*判栈空*/
{
return S->top = = S->base;
}
int IsFull（SeqStack*S） /*判栈满*/
{
return S->top - S->base = = STACK_SIZE -1;
}
void Push（SeqStack*S,DataType x） /*进栈*/
{
if（IsFull（S））
{
printf（"overflow"）; /*上溢,退出运行*/
exit（1）;
}
else
*S->top++=x; /*栈顶指针加1后将x入栈*/
}
void Pop（SeqStack*S） /*出栈*/
{
if（IsEmpty（S））
{
printf（"NULL"）; /*下溢,退出运行*/
exit（1）;
}
else
--S->top; /*栈顶元素返回后将栈顶指针减1*/
}
DataType Top（SeqStack*S） /* 取栈顶元素*/
{
if（IsEmpty（S））
{
printf（"empty"）; /*下溢,退出运行*/
exit（1）;
}
return *（S->top -1）;
}
void ClearStack（SeqStack*S） /*清空栈*/
{
S->top = S->base;
}
（5）创建自定义函数LineEdit（）实现行编辑功能。实现代码如下：
void LineEdit（SeqStack*S） /*自定义行编辑程序*/
{
int i=0,a[100],n; /*定义变量数据类型为基本整型*/
char ch; /*定义ch为字符型*/
ch=getchar（）; /*将输入字符赋给ch*/
while（ch!='\n'） /*当未输入回车时执行循环体语句*/
{
i++; /*记录进栈元素个数*/
switch（ch） /*判断输入字符*/
{
case'#': /*当输入字符为#*/
Pop（S）; /*出栈*/
i-=2; /*元素个数减2*/
break;
case'@': /*当输入字符为@*/
ClearStack（S）; /*清空栈*/
i=0; /*进栈元素个数清零*/
break;
default:
Push（S,ch）; /*当不是#和@，其余元素进行进栈操作*/
}
ch=getchar（）; /*接收输入字符赋给ch*/
}
for（n=1;n<=i;n++） /*将栈中元素存入数组中*/
{
a[n] = Top（S）;
Pop（S）;
}
for（n=i;n>=1;n--） /*将数组中的元素输出*/
printf（"%c", a[n]）;
}
（6）创建main（）函数作为程序的入口函数，调用LineEdit（）函数实现简单的行编辑程序。程序代码如下：
main（）/*主函数*/
{
SeqStack *ST;
printf（"please input\n"）;
Initial（ST）;
LineEdit（ST）; /*调用行编辑函数*/
}
举一反三
根据本实例，读者可以：
在本程序的基础上用栈实现多行编辑。
用栈实现表达式求值。
实例093 括号匹配检测
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\093
实例说明
本实例要求编写检测括号是否匹配的程序，它的主要功能是对输入的一组字符串进行检测，当输入的字符串中括号（包括“{}”、“[]”、“（）”）匹配时输出matching，否则输出No matching。运行结果如图3.27所示。
图3.27 括号匹配检测
技术要点
[（36-21）*56-23/（23+12）]，观察该字符串会发现如果从右向左扫描，那么每个右括号（包括“）”、“）”及“）”）将与最近的那个未配对的左括号相配对。从这个分析中我们可以想到一种方法，就是对输入的每个字符进行判断，如果输入的是左括号中的任意一种就进行进栈操作，如输入的是右括号中的任意一种，则进行取栈顶元素操作，看取出的元素是否是与这个右括号相匹配的元素。如果是则令其标志作用的变量置1，否则置0，若标志变量有一次为0就不需要进行下面的操作说明该字符串不匹配。当对整个字符串中的字符均进行了判断后看标志位是否为1且该栈是否为空，若标志位为1且该栈为空这说明该字符串括号匹配，否则不匹配。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件、进行宏定义及数据类型的指定：
#include <stdio.h>
#define STACK_SIZE 100 /*假定预分配的栈空间最多为100个元素*/
typedef char DataType; /*设定DataType的代表的数据类型为字符型*/
（3）定义结构体类型及变量：
typedef struct /*定义结构体*/
{
DataType*base; /*定义栈底指针*/
DataType*top; /*定义栈顶指针*/
int stacksize; /*定义栈的大小*/
}SeqStack; /*SeqStack为该结构体类型*/
（4）创建自定义函数实现构造栈、进栈、出栈、取栈顶元素等操作。实现代码如下：
void Initial（SeqStack *S）/*初始化栈*/
{
S->base =（DataType*）malloc（STACK_SIZE *sizeof（DataType））;
if（!S->base）
exit（-1）;
S->top=S->base; /*栈为空时栈顶栈底指针指向同一处*/
S->stacksize = STACK_SIZE;
}
int IsEmpty（SeqStack*S） /*判栈空*/
{
return S->top = = S->base;
}
int IsFull（SeqStack*S） /*判栈满*/
{
return S->top - S->base = = STACK_SIZE -1;
}
void Push（SeqStack*S,DataType x） /*进栈*/
{
if（IsFull（S））
{
printf（"overflow"）; /*上溢,退出运行*/
exit（1）;
}
else
*S->top++=x; /*栈顶指针加1后将x入栈*/
}
void Pop（SeqStack*S） /*出栈*/
{
if（IsEmpty（S））
{
printf（"NULL"）; /*下溢,退出运行*/
exit（1）;
}
else
--S->top; /*栈顶元素返回后将栈顶指针减1*/
}
DataType Top（SeqStack*S） /* 取栈顶元素*/
{
if（IsEmpty（S））
{
printf（"empty"）; /*下溢,退出运行*/
exit（1）;
}
return *（S->top -1）;
}
（5）创建自定义函数match（）实现行编辑功能。实现代码如下：
int match（SeqStack *S, char *str）
{
char x;
int i, flag = 1;
for（i = 0; str[i] != '\0'; i++）
{
switch（str[i]）
{
case '（':
Push（S, '（'）;
break;
case '[':
Push（S, '['）;
break;
case '{':
Push（S, '{'）;
break;
case '）':
x = Top（S）;
Pop（S）;
if（x != '（'）
flag = 0;
break;
case ']':
x = Top（S）;
Pop（S）;
if（x != '['）
flag = 0;
break;
case '}':
x = Top（S）;
Pop（S）;
if（x != '{'）
flag = 0;
break;
}
if（!flag）
break;
}
if（IsEmpty（S）= = 1 && flag）
return 1;
else
return 0;
}
（6）主函数程序代码如下：
main（）
{
SeqStack *st;
char str[100];
Initial（st）;
gets（str）;
if（match（st, str））
printf（"matching\n"）;
else
printf（"no matching\n"）;
}
举一反三
根据本实例，读者可以：
在本实例的基础上编程实现输入一字符串，当检测出该字符串括号不匹配时输出提示信息后输入匹配的字符串。
在本实例的基础上编程实现检测多个字符串括号是否匹配，当输入“#”时退出程序。
实例094 用栈及递归计算多项式
这是一个可以提高分析能力的实例
实例位置：光盘\mingrisoft\03\094
实例说明
已知一个多项式
，试编写计算fn（x）值的递归算法。运行结果如图3.28所示。
图3.28 括号匹配检测
技术要点
本题要求用栈及递归的方法来求解多项式的值，首先说下递归方法如何来求。
用递归的方法来求解本题关键要找出能让递归结束的条件，否则程序将进入死循环，从题中给的多项式来看f0（x）=1及f1（x）=2x便是递归结束的条件。那么当n>0时，所对应的函数便是递归计算的公式。
下面介绍下如何用栈来求该多项式的值，这里利用了栈后进先出的特性将n由大到小入栈，再由小到大出栈，每次出栈时求出该数所对应的多项式的值为求下一个出栈的数所对应的多项式的值做基础。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）自定义f1（）函数用来实现递归求解多项式的值。代码如下：
double f1（int n,int x） /*自定义函数f1，递归的方法*/
{
if（n = = 0）
return 1; /*n为0时返回值为1*/
else if（n = = 1）
return 2*x; /*n为1时返回值为2与x的乘积*/
else
return 2*x*f1（n-1,x）-2*（n-1）*f1（n-2,x）; /*当n大于2时递归求值*/
}
（4）自定义f2（）函数来实现用栈的方法求解多项式的值。代码如下：
double f2（int n,int x） /*自定义函数f2，栈的方法*/
{
struct STACK
{
int num; /*num用来存放n值*/
double dat /*data存放不同n所对应的不同结果*/
} stack[100];
int i,top=0; /*变量数据类型为基本整型*/
double sum1=1,s um2; /*多项式的结果为双精度型*/
sum2=2*x; /*当n是1的时候结果是2*/
for（i = n; i >= 2; i--）
{
top++; /*栈顶指针上移*/
stack[top].num=i; /*i进栈*/
}
while（top > 0）
{
stack[top].data=2*x*sum2-2*（stack[top].num-1）*sum1; /*求出栈顶元素对应的函数值*/
sum1=sum2; /*sum2赋给sum1*/
sum2=stack[top].data; /*刚算出的函数值赋给sum2*/
top--; /*栈顶指针下移*/
}
return sum2; /*最终返回sum2的值*/
}
（5）主函数程序代码如下：
main（）
{
int x,n; /*定义x、n为基本整型*/
double sum1,sum2; /*sum1、sum2为双精度型*/
printf（"please input n:\n"）;
scanf（"%d",&n）; /*输入n值*/
printf（"please input x:\n"）;
scanf（"%d",&x）; /*输入x的值*/
sum1=f1（n,x）; /*调用f1，算出递归求多项式的值*/
sum2=f2（n,x）; /*调用f2，算出栈求多项式的值*/
printf（"the result of recursion is %f\n",sum1）; /*将递归方法算出的函数值输出*/
printf（"the result of stack is %f\n",sum2）; /*将使用栈方法算出的函数值输出*/
}
举一反三
根据本实例，读者可以：
采用非递归方法求解本实例。
已知一个多项式
，试编写计算fn（x）值的递归算法。
实例095 链队列
这是一个可以提高基础技能的实例
实例位置：光盘\mingrisoft\03\095
实例说明
采用链式存储法编程实现元素入队、出队以及将队列中的元素显示出来，要求整个过程以菜单选择的形式实现。运行结果如图3.29所示。
图3.29 链队列
技术要点
队列的链式存储结构是通过由节点构成的单链表实现的，此时只允许再单链表的表首进行删除，在单链表的表尾进行插入，因此需要使用两个指针：队首指针front和队尾指针rear。用front指向队首节点的存储位置，用rear指向队尾节点的存储位置。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <stdlib.h>
（3）定义结构体node及quefr，分别存储入队元素内容及队首队尾指针，代码如下：
typedef struct node /*定义节点*/
{
ElemType data; /*存放元素内容*/
struct node *next; /*指向下个节点*/
} quenode;
struct quefr /*定义节点存放队首队尾指针*/
{
quenode*front, *rear;
};
（4）自定义creat（）函数，作用是初始化链队列，代码如下：
void creat（struct quefr *q）/*自定义函数初始化链队列*/
{
quenode *h;
h =（quenode*）malloc（sizeof（quenode））;
h->next = NULL;
q->front = h; /*队首指针队尾指针均指向头节点*/
q->rear = h;
}
（5）自定义enqueue（）函数，作用是元素入队列，代码如下：
void enqueue（struct quefr *q, int x）/*自定义函数，元素x入队*/
{
quenode *s;
s =（quenode*）malloc（sizeof（quenode））;
s->data = x; /*x放到节点的数据域中*/
s->next = NULL; /*next域为空*/
q->rear->next = s;
q->rear = s; /*队尾指向s节点*/
}
（6）自定义dequeue（）函数，作用是元素出队列，代码如下：
ElemType dequeue（struct quefr *q）/*自定义函数实现元素出队*/
{
quenode *p;
ElemType x;
p =（quenode*）malloc（sizeof（quenode））;
if（q->front = = q->rear）
{
printf（"queue is NULL \n"）;
x = 0;
}
else
{
p = q->front->next;
q->front->next = p->next; /*指向出队元素所在节点的后一个节点*/
if（p->next = = NULL）
q->rear = q->front;
x = p->data;
free（p）; /*释放p节点*/
}
return（x）;
}
（7）自定义display（）函数，作用是显示队列中的元素，代码如下：
void display（struct quefr dq）
/*自定义函数显示队列中元素*/
{
quenode *p;
p =（quenode*）malloc（sizeof（quenode））;
p=dq.front->next;/*指向第一个数据元素节点 */
while（p != NULL）
{
printf（"data=%d\n", p->data）;
p = p->next; /*指向下个节点*/
} printf（"end \n"）;
}
（8）主函数程序代码如下：
main（）
{
struct quefr *que;
int n, i, x, sel;
void display（）; /*显示队列中元素*/
void creat（）; /*创建队列*/
void enqueue（）; /*元素入队列*/
ElemType dequeue（）; /*元素出队列*/
do
{
printf（"\n"）;
printf（" 1 creat queue \n"）;
printf（" 2 into the queue \n"）;
printf（" 3 delete from queue \n"）;
printf（" 4 display\n"）;
printf（" 5 exit \n"）;
printf（"-------------------------------\n"）;
printf（"please choose（1, 2, 3, 4，5）"）;
scanf（"%d", &sel）; /*输入相关功能所对应的标号*/
switch（sel）
{
case 1:
que =（struct quefr*）malloc（sizeof（struct quefr））;
/*分配内存空间*/
creat（que）; /*初始化队列*/
printf（
"please input the number of element which do you want to creat:"）;
scanf（"%d", &n）; /*输入队列元素个数*/
for（i = 1; i <= n; i++）
{
scanf（"%d", &x）; /*输入元素*/
enqueue（que, x）;
}
break;
case 2:
printf（"please input the element:"）;
scanf（"%d", &x）; /*输入元素*/
enqueue（que, x）; /*元素入队*/
break;
case 3:
printf（"x=%d\n", dequeue（que））; /*元素出队*/
break;
case 4:
display（*que）; /*显示队列中元素*/
break;
case 5:
exit（0）;
}
}
while（sel <= 4）;
}
举一反三
根据本实例，读者可以：
利用队列，编程实现模拟飞机售票。
编写顺序队列入队/出队过程。
实例096 循环缓冲区问题
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\096
实例说明
有两个进程同时存在于一个程序中，其中第一个进程在屏幕上连续显示字母“A”，同时程序不断检测键盘是否有输入，如果有的话，就读入用户输入的字符并保存到输入缓冲区中。在用户输入时，输入的字符并不立即显示在屏幕上，当用户输入一个“，”时，表示第一个进程结束，第二个进程从缓冲区中读取那些已输入的字符并显示在屏幕上。第二个进程结束后，程序又进入第一个进程，重新显示字符“A”，同时用户又可以继续输入字符，直到用户输入一个“；”，才结束第一个进程，同时也结束整个程序。运行结果如图3.30所示。
图3.30 循环缓冲区问题
技术要点
本实例的实现主要是采用了循环队列，下面着重介绍下循环队列。
循环的产生主要是为了解决顺序队列“假溢出”的现象，所谓循环队列的就是把顺序队列构造成一个首尾相连的循环表。当队列的Maxsize-1的位置被占用后，只要队列前面还有可用空间，就还可以添加新的元素。
循环队列判断队空的条件：
q->rear=q->front
循环队列判断队满的条件（采用少用一个数据元素空间的方法）：
（q->rear+1）modMaxsize= =q->front
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件，进行宏定义及全局变量声明。代码如下：
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <stdlib.h>
#define Maxsize 30
#define TRUE 1
#define FALSE 0
char queue[Maxsize];
int front, rear;
（3）自定义init（）函数，作用是队首队尾指针初始化。代码如下：
void init（） /*队首队尾指针初始化*/
{
front=rear= -1;
}
（4）自定义enqueue（）函数，作用实现元素入队列。代码如下：
int enqueue（char x） /*元素入队列*/
{
if（front== -1&&（rear+1）==Maxsize）
/*只有元素入队没有元素出队判断是否满足队满条件*/
{
printf（"overflow!\n"）;
return 0;
}
else if（（rear+1）% Maxsize==front） /*判断是否队满*/
{
printf（"overflow!\n"）;
return 0;
}
else
{
rear=（rear+1）% Maxsize; /*rear指向下一位置*/
queue[rear]=x; /*元素入队*/
return 1;
}
}
（5）自定义dequeue（）函数，作用实现元素出队列。代码如下：
void dequeue（） /*元素出队列*/
{
if（front = = rear）
/*判断队列是否为空*/
printf（"NULL\n"）;
else
front =（front + 1）% Maxsize;
/*队首指针指向下一个位置*/
}
（6）自定义getchar（）函数，作用实现取队首元素。代码如下：
char gethead（） /*取队首元素*/
{
if（front = = rear）
/*判断队列是否为空*/
printf（"NULL\n"）;
else
return（queue[（front + 1）% Maxsize]）;
/*取出队首元素*/
}
（7）主函数程序代码如下：
main（）
{
char ch1, ch2;
init（）; /*队列初始化*/
for（;;）
{
for（;;）
{
printf（"A"）;
if（kbhit（））
{
ch1=bdos（7,0,0）; /*通过dos命令读入一个字符*/
if（!enqueue（ch1））
{
printf（"IS FULL\n"）;
break;
}
}
if（ch1 = = ';' || ch1 = = ','）
/*判断输入字符是否是分号或逗号*/
break;
}
while（front != rear）
/*判断队列是否为空*/
{
ch2 = gethead（）; /*取队首元素*/
dequeue（）; /*元素出队列*/
putchar（ch2）; /*输出该元素*/
}
if（ch1 = = ';'）
/*判断输入的是否是分号*/
break;
/*跳出循环*/
else
ch1 = '';
}
}
举一反三
根据本实例，读者可以编程实现以下问题：
假设以带头节点的循环链表表示队列，并且只设一个指针指向队尾节点，但不设头指针。试设计相应的初始化队列、入队列和出队列的算法。
由一个循环队列q（n），入队和出队指针分别为r和f，并有一个有序线性表a[m]，编写一个把循环队列中的数据逐个出队并同时插入到线性表中的算法。若线性表满则停止出队，并保证线性表的有序性。
3.4 串与广义表
计算机上的非数值处理的对象基本上是字符串数据，现在使用的计算机的硬件结构主要是反应数值计算需要的，因此处理字符串数据是比处理整数和浮点数要复杂得多。不同应用中所处理的字符串有不同的特点，要有效地实现字符串处理就必须因情况不同合理使用存储结构。
广义表是线性表的推广，目前广泛用于人工只能等领域的表处理语言中。本小节有关串和广义表的几个实例。
实例097 串的模式匹配
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\097
实例说明
分别从键盘中输入主串和模式串，如果能够找到子串在主串的位置则将该位置输出，否则匹配不成功，输出提示信息。运行结果如图3.31所示。
图3.31 串的模式匹配
技术要点
算法的基本思想是：分别设置计数指针i和j指示主串和模式串当前正待比较的字符位置，从主串的第一个字符和模式的第一个字符开始比较，若相等，则继续逐个比较后续字符，否则从主串的下一个字符起再重新和模式串的字符比较。依此类推，直到找到主串中的一串连续字符和模式串中的字符相等，则说明模式匹配成功，否则匹配不成功。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件并进行宏定义，代码如下：
#include <string.h>
#include <stdio.h>
#define Maxsize 100
（3）定义结构体用来存储串的相关信息。代码如下：
typedef struct /*定义结构体，用来存储串的相关信息*/
{
char string[Maxsize];
int len;
}str; /*定义str为该结构体类型*/
（4）自定义firststr（）函数来实现模式匹配检测。代码如下：
int findstr（str s,str t） /*自定义函数findstr*/
{
int i = 1, j = 0, k = 0, pos;
while（i < s.len && j < t.len）
{
if（s.string[k]==t.string[j]） /*判断主串与模式串对应元素是否匹配*/
{
k++; /*主串向后移一位*/
j++; /*模式串向后移一位*/
}
else
{ /*主串和模式串重新退回，从主串的下一个位置开始下一次匹配*/
i++;
k = i;
j = 0;
}
}
if（j==t.len） /*判断模式串是否已经匹配到最后一个字符*/
pos=k-j+1; /*指向匹配成功的第一个字符*/
else
pos= -1;
return（pos）;
}
（5）主函数程序代码如下：
main（）
{
str s, t;
int p;
printf（"qing shu ru zhu cuan:\n"）;
scanf（"%s",s.string）; /*从键盘中输入主串*/
s.len = strlen（s.string）;
printf（"qing shu ru mo shi cuan:\n"）;
scanf（"%s",t.string）; /*从键盘中输入模式串*/
t.len=strlen（t.string）; /*获取模式串的长度*/
p=findstr（s,t）; /*调用findstr函数返回值赋给p*/
if（p== -1）
printf（"no matching!"）; /*返回值如果为-1说明未匹配*/
else
printf（"matching!the position is:%d",p）;/*将匹配位置输出*/
}
举一反三
根据本实例，读者可以：
用Knuth-Pratt-Morris（KMP）算法实现模式匹配。
已知两个串为s1="agudkigjerg"，s2="ki"；试设计算法求两个串的长度，并判断s2串是否是s1串的子串，如果是，指出s2在s1中的起始位置。
实例098 简单的文本编辑器
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\098
实例说明
本程序要求实现3个功能：第一，要求对指定行输入字符串；第二，删除指定行的字符串；第三，显示输入的字符串的内容。运行结果如图3.32所示。
图3.32 简单的文本编辑器
技术要点
串是由零个或多个字符组成的有限序列，对串的存储可以有两种方式：一种是静态存储；另一种是动态存储。其中动态存储结构有两种方式：一种是链式存储结构，另一种是堆结构存储方式。这里着重说一下链式存储结构。
串的链式存储结构是包含数据域和指针域的节点结构。因为每个节点仅存放一个字符，这样比较浪费空间，为了节省空间，可使每个节点存放若干个字符，这种结构叫做块链结构，本实例就是采用这种块链结构来实现的。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件并进行宏定义并对自定义函数进行声明。代码如下：
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
void Init（）;
void input（）;
void Delline（）;
void List（）;
int Menu（）;
（3）定义结构体用来存储每行字符串的相关信息并声明结构体类型数组Head。代码如下：
typedef struct node /*定义存放字符串的节点*/
{
char data[50];
struct node *next;
} strnode;
typedef struct head /*定义每行的头节点*/
{
int number; /*行号*/
int length; /*字符串的长度*/
strnode *next;
} headnode;
headnode Head[MAX]; /*定义有100行*/
（4）自定义init（）函数来实现每行头节点的初始化。代码如下：
void Init（）/*定义初始化函数*/
{
int i;
for（i = 0; i < MAX; i++）
{
Head[i].length = 0;
}
}
（5）自定义Menu（）函数来实现选择菜单，并将选择的菜单所对应的序号返回。代码如下：
int Menu（）/*定义菜单*/
{
int i;
i = 0;
printf（" 1. Input\n"）;
printf（" 2. Delete\n"）;
printf（" 3. List\n"）;
printf（" 4. Exit\n"）;
while（i <= 0 || i > 4）
{
printf（"please choose\n"）;
scanf（"%d", &i）;
}
return i;
}
（6）自定义input（）函数来实现向指定行中输入字符串。代码如下：
void input（） /*自定义输入字符串函数*/
{
strnode*p, *find（）;
int i, j, LineNum;
char ch;
while（1）
{
j= -1;
printf（"input the number of line（0～100）,101-exit:\n"）;
scanf（"%d",&LineNum）; /*输入要输入的字符串所在的行号*/
if（LineNum < 0 || LineNum >= MAX）
return ;
printf（"please input,#-end\n"）;
i = LineNum;
Head[i].number = LineNum;
Head[i].next=（strnode*）malloc（sizeof（strnode））;/*分配内存空间*/
p = Head[i].next;
ch = getchar（）;
while（ch != '#'）
{
j++; /*计数*/
if（j >= 50）
/*如果字符串长度超过50需要再分配一个节点空间*/
{
p->next =（strnode*）malloc（sizeof（strnode））;
p=p->next; /*p指向新分配的节点*/
}
p->data[j % 50] = ch; /*将输入的字符串放入data中*/
ch = getchar（）;
}
Head[i].length = j + 1; /*长度*/
}
}
（7）自定义Delline（）函数来实现对指定行的删除。代码如下：
void Delline（） /*自定义删除行函数*/
{
strnode*p, *q;
int i, LineNum;
while（1）
{
printf（
"input the number of line which do you want to delete（0～100）,101-exit:\n"）;
scanf（"%d",&LineNum）; /*输入要删除的行号*/
if（LineNum < 0 || LineNum >= MAX）
/*如果超出行的范围则返回菜单界面*/
return ;
i = LineNum;
p = Head[i].next;
if（Head[i].length > 0）
while（p != NULL）
{
q = p->next;
free（p）; /*将p的空间释放*/
p = q;
}
Head[i].length = 0;
Head[i].number = 0;
}
}
（8）自定义list（）函数来实现将输入的内容显示在屏幕上。代码如下：
void List（）
{
strnode *p;
int i, j, m, n;
for（i = 0; i < MAX; i++）
{
if（Head[i].length > 0）
{
printf（"line %d", Head[i].number）;
n = Head[i].length;
m = 1;
p = Head[i].next;
for（j = 0; j < n; j++）
if（j >= 50 *m）
/*以50为准，超过一个则指向下一个节点*/
{
p = p->next;
m++; /*节点个数*/
}
else
printf（"%c", p->data[j % 50]）;
/*将节点中内容输出*/
printf（"\n"）;
}
}
printf（"\n"）;
}
（9）主函数程序代码如下：
main（）
{
int sel;
Init（）; /*初始化*/
while（1）
{
sel = Menu（）;
switch（sel） /*输入对应数字进行选择*/
{
case 1:
input（）;
break;
case 2:
Delline（）;
break;
case 3:
List（）;
break;
case 4:
exit（0）;
}
}
}
举一反三
根据本实例，读者可以：
令s1="cccdd",s2="dccdede",u="cdeccdecccidiccccddeuiidddd"，试分别求出它们的next[j]函数值。
设有s="good"，t="morning"，写出s+t运算的结果。
实例099 广义表的存储
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\099
实例说明
编程实现用动态链接结构存储广义表，要求输出该广义表的长度与深度，运行结果如图3.33所示。
图3.33 广义表的存储
技术要点
在一个广义表中，数据元素可为单个元素，也可为子表，相应地在对应的存储结构中，其存储结构节点也有单元素节点和子表节点之分。单元素节点包含值域和指向其后继节点的指针域。对于子表节点，应包括指向子表中第一个节点的表头指针和指向其后继节点的指针域。为了区分广义表中单元素节点和子表节点，我们设置tag作为标志，当tag=0时表示本节点为单元素，当tag=1时表示本节点为子表。
当tag=1时，说明其为子表节点，则第二个域是sublist域，存放的是指向其子表的指针，next域存放指向与该节点同层的直接后继节点的指针，当该节点是所在层的最后一个节点时，此时next为空（NULL）。
例如广义表L=（a，（b，c，d））的存储结构如图3.34所示。
图3.34 广义表L存储结构
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件并进行宏定义。代码如下：
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
（3）定义结构体用来存储存储广义表中单元素节点和子表节点。代码如下：
typedef struct lnode
{
int tag;
union
{
ElemType data;
struct lnode *sublist;
} val;
struct lnode *next;
}GLNode;
（4）自定义creatGList（）函数来实现广义表的创建。代码如下：
void creatGList（struct lnode **gl）
{
char ch; /* 读入一个字符*/
ch = getchar（）;
if（ch = = '#'）
{
*gl = NULL;
}
else if（ch = = '（'）
/*若输入左括号则递归构造子表*/
{
*gl = malloc（sizeof（struct lnode））;
（*gl）->tag = 1;
creatGList（&（（*gl）->val.sublist））;
}
else
/* 若输入为字符则建立单元素节点 */
{
*gl = malloc（sizeof（struct lnode））;
（*gl）->tag = 0;
（*gl）->val.data = ch;
}
ch=getchar（）; /*读入一个字符*/
if（*gl = = NULL）
{
;
}
/* 若输入为逗号则递归构造后继表 */
else if（ch = = ','）
{
creatGList（&（（*gl）->next））;
}
else
/* 否则*gl后继指针域为空 */
（*gl）->next = NULL;
return ;
}
（5）自定义printGList（）函数来实现广义表的输出。代码如下：
void printGList（struct lnode*gl） /*打印广义表*/
{
if（gl->tag = = 1）
/*判断是否存在子表*/
{
printf（"（"）; /* 存在子表，先输出左括号 */
if（gl->val.sublist = = NULL）
{
printf（"#"）;
}
else
{
}
printGList（gl->val.sublist）; /*递归输出子表*/
printf（"）"）; /*输出右括号 */
}
else
printf（"%c", gl->val.data）;
/*如果是单个节点则直接输出*/
if（gl->next != NULL）
/* 输出节点的后继表 */
{
printf（","）; /*输出逗号*/
printGList（gl->next）; /*递归输出后继表*/
}
return ;
}
（6）自定义GLLength（）函数来实现求广义表的长度。代码如下：
int GLLength（GLNode *gl）/*求广义表的长度*/
{
int n = 0;
gl = gl->val.sublist;
while（gl != NULL）
{
n++; /*若gl不为空n加1*/
gl = gl->next;
}
return n;
}
（7）自定义GLDepth（）函数来实现求广义表的深度。代码如下：
int GLDepth（GLNode*gl） /*求广义表的深度*/
{
int max = 0, dep;
if（gl->tag = = 0）
return 0;
gl = gl->val.sublist;
if（gl = = NULL）
return 1;
while（gl != NULL）
{
if（gl->tag = = 1）
{
dep=GLDepth（gl）; /*递归求广义表深度*/
if（dep > max）
max = dep;
}
gl = gl->next;
}
return（max+1）; /*返回广义表的深度*/
}
（8）主函数程序代码如下：
main（）
{
int len = 0;
int dep = 0;
struct lnode *h;
creatGList（&h）;
len = GLLength（h）;
dep = GLDepth（h）;
printf（"\n"）;
printf（"The length is:"）;
printf（"%d", len）;
printf（"\n"）;
printf（"The depth is:"）;
printf（"%d", dep）;
printf（"\n"）;
if（h != NULL）
{
printf（"Glist is:"）;
printGList（h）;
printf（"\n"）;
}
else
printf（"Glist is NULL"）;
}
举一反三
根据本实例，读者可以：
编程求广义表的深度与长度，广义表为（a,（b，d），（c，e，f））。
编程求广义表的深度与长度，广义表为（a，b，d，（c，e，f））。
实例100 广义表的复制
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\100
实例说明
编程实现广义表的复制，从键盘中输入一广义表，在屏幕中输出该广义表的表头及表尾。运行结果如图3.35所示。
图3.35 广义表的复制
技术要点
本实例中广义表的复制采用递归实现的，程序中并没有太多难点，在复制成员变量时只需递归的调用该复制函数本身即可。
通过调用自定义的复制函数，同样可求出表头及表尾。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件并进行宏定义。代码如下：
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
（3）定义结构体用来存储存储广义表中单元素节点和子表节点。代码如下：
typedef struct lnode
{
int tag;
union
{
ElemType data;
struct lnode *sublist;
} val;
struct lnode *next;
}GLNode;
（4）自定义creatGList（）函数来实现广义表的创建。代码如下：
void creatGList（struct lnode **gl）
{
char ch; /*读入一个字符*/
ch = getchar（）;
if（ch = = '#'）
{
*gl = NULL;
}
else if（ch = = '（'）
/*若输入左括号则递归构造子表*/
{
*gl = malloc（sizeof（struct lnode））;
（*gl）->tag = 1;
creatGList（&（（*gl）->val.sublist））;
}
else
/* 若输入为字符则建立单元素节点 */
{
*gl = malloc（sizeof（struct lnode））;
（*gl）->tag = 0;
（*gl）->val.data = ch;
}
ch = getchar（）; /*读入一个字符*/
if（*gl = = NULL）
{
;
}
/* 若输入为逗号则递归构造后继表 */
else if（ch = = ','）
{
creatGList（&（（*gl）->next））;
}
else
/* 否则*gl后继指针域为空 */
（*gl）->next = NULL;
return ;
}
（5）自定义printGList（）函数来实现广义表的输出。代码如下：
void printGList（struct lnode*gl） /*打印广义表*/
{
if（gl->tag = = 1）
/*判断是否存在子表*/
{
printf（"（"）; /* 存在子表，先输出左括号 */
if（gl->val.sublist = = NULL）
{
printf（"#"）;
}
else
{
printGList（gl->val.sublist）; /*递归输出子表*/
}
printf（"）"）; /*输出右括号 */
}
else
printf（"%c", gl->val.data）;
/*如果是单个节点则直接输出*/
if（gl->next != NULL）
/* 输出节点的后继表 */
{
printf（","）; /*输出逗号*/
printGList（gl->next）; /*递归输出后继表*/
}
return ;
}
（6）自定义GLCopy（）函数来实现求广义表的复制。代码如下：
GLNode*GLCopy（GLNode*gl） /*广义表复制函数*/
{
GLNode *q;
if（gl = = NULL）
return NULL;
q =（GLNode*）malloc（sizeof（GLNode））;
q->tag = gl->tag;
if（gl->tag = = 1）
q->val.sublist = GLCopy（gl->val.sublist）;
/*递归复制子表*/
else
q->val.data = gl->val.data;
/*复制数据信息*/
q->next=GLCopy（gl->next）; /*递归复制next信息*/
return q;
}
（7）自定义head（）函数来实现求广义表的表头。代码如下：
GLNode *head（GLNode *gl）
{
GLNode *p = gl->val.sublist;
GLNode*q, *t;
if（gl = = NULL）
{
printf（"NULL\n"）;
return NULL;
}
if（gl->tag = = 0）
{
printf（"atom is not head！\n"）;
return NULL;
}
if（p->tag = = 0）
{
q =（GLNode*）malloc（sizeof（GLNode））;
q->tag = 0;
q->val.data = p->val.data;
q->next = NULL;
}
else
{
t =（GLNode*）malloc（sizeof（GLNode））;
t->tag = 1;
t->val.sublist = p->val.sublist;
t->next = NULL;
q = GLCopy（t）;
free（t）;
}
return q;
}
（8）自定义tail（）函数来实现求广义表的表尾。代码如下：
GLNode *tail（GLNode *gl）
{
GLNode *p = gl->val.sublist;
GLNode*q, *t;
if（gl = = NULL）
{
printf（"NULL\n"）;
return NULL;
}
if（gl->tag = = 0）
{
printf（"atom is not tail!\n"）;
return NULL;
}
p = p->next;
t =（GLNode*）malloc（sizeof（GLNode））;
t->tag = 1;
t->val.sublist = p;
t->next = NULL;
q = GLCopy（t）;
free（t）;
return q;
}
（9）主函数程序代码如下：
main（）
{
struct lnode*g, *v;
struct lnode *h;
creatGList（&h）;
printf（"\n"）;
v = head（h）;
if（v != NULL）
{
printf（"Head is:"）;
printGList（v）;
printf（"\n"）;
} g = tail（h）;
if（g != NULL）
{
printf（"Tail is:"）;
printGList（g）;
printf（"\n"）;
}
if（h != NULL）
{
printf（"Glist is:"）;
printGList（h）;
printf（"\n"）;
}
else
printf（"Glist is NULL"）;
}
举一反三
根据本实例，读者可以：
编程实现复制广义表（a，（b，d），（c，e，f））并输出。
编程实现复制广义表（a，b，d，（c，e，f））并输出。
3.5 二叉树
二叉树是一种最典型的树形结构，特别适合计算机处理，任何树都可以转换成二叉树来处理并且具有存储方便和操作灵活等优点，所以是一种广泛使用的树形结构，本节的几个实例重点介绍二叉树的存储结构及操作的实现。
实例101 二叉树的递归创建
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\101
实例说明
编程实现递归创建二叉树，要求显示树的节点内容、深度及叶子节点数。运行结果如图3.36所示。
图3.36 二叉树的递归创建
技术要点
二叉树（可以是一棵空树）是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。
存储二叉树通常采用二叉链表法，即每个节点带两个指针和一个数据域，一个指针指向左子树，另一个指向右子树。节点的结构如图3.37所示。
图3.37 节点
若一棵二叉树如图3.38所示，则该二叉树的二叉链表表示如图3.39所示。
图3.38 二叉树
图3.39 二叉链表
我们可以用递归创建二叉链表的方法来实现二叉树的创建。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <stdlib.h>
（3）二叉链表的结构声明，代码如下：
typedef struct node /*二叉链表结构声明*/
{
struct node *lchild;
char data;
struct node *rchild;
}bitnode, *bitree; /*bitnode、bitree为该结构体类型*/
（4）自定义CreatTree（）函数，用于构造二叉树，代码如下：
bitree CreatTree（） /*构造二叉树*/
{
char a;
bitree new;
scanf（"%c", &a）;
if（a = = '#'）
return NULL;
else
{
new =（bitree）malloc（sizeof（bitnode））;
new->data = a;
new->lchild=CreatTree（）; /*递归创建左子树*/
new->rchild=CreatTree（）; /*递归创建右子树*/
}
return new;
}
（5）自定义print（）函数，用于输出二叉树的节点内容，代码如下：
void print（bitree bt） /*自定义函数print用中序遍历的方式输出二叉树节点内容*/
{
if（bt != NULL）
{
print（bt->lchild）;
printf（"%c", bt->data）;
print（bt->rchild）;
}
}
（6）自定义btreedepth（）函数，用于求二叉树的深度，代码如下：
int btreedepth（bitree bt） /*自定义函数btreedepth（）求二叉树的深度*/
{
int ldepth, rdepth;
if（bt = = NULL）
return 0;
else
{
ldepth = btreedepth（bt->lchild）;
rdepth = btreedepth（bt->rchild）;
return（ldepth > rdepth ? ldepth + 1: rdepth + 1）;
}
}
（7）自定义ncount（）函数，用于求二叉树中节点个数，代码如下：
int ncount（bitree bt）/*自定义函数ncount求节点的个数*/
{
if（bt = = NULL）
return 0;
else
return（ncount（bt->lchild）+ ncount（bt->rchild）+ 1）;
}
（8）自定义lcount（）函数，用于求二叉树中叶子节点个数，代码如下：
int lcount（bitree bt） /*自定义函数lcount求叶子节点的个数*/
{
if（bt = = NULL）
return 0;
else if（bt->lchild = = NULL && bt->rchild = = NULL）
return 1;
else
return（lcount（bt->lchild）+ lcount（bt->rchild））;
}
（9）主函数程序代码如下：
void main（）
{
bitree root;
root=CreatTree（）; /*调用函数创建二叉链表*/
printf（"contents of binary tree:\n"）;
print（root）; /*调用函数输出节点内容*/
printf（"\ndepth of binary tree:%d\n", btreedepth（root））;
/*调用函数输出树的深度*/
printf（"the number of the nodes:%d\n", ncount（root））;
/*调用函数输出树中节点个数*/
printf（"the number of the leaf nodes:%d\n", lcount（root））;
/*调用函数输出树中叶子节点个数*/
}
举一反三
根据本实例，读者可以：
编程实现二叉树非递归创建。
编程求如图3.40所示的二叉树叶子节点数。
图3.40 求二叉树叶子节点
实例102 二叉树的遍历
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\102
实例说明
构造一棵二叉树，分别采用先序遍历、中序遍历和后序遍历遍历该二叉树。运行结果如图3.41所示。
图3.41 二叉树遍历
技术要点
在遍历二叉树时若先左后右，则有3中遍历方法，分别为先序遍历、中序遍历和后序遍历，它们的递归定义如下。
● 先序遍历：若二叉树非空，则先访问根节点，再按先序遍历左子树，最后按前序遍历右子树。
● 中序遍历：若二叉树非空，则先按中序遍历左子树，再访问根节点，最后按中序遍历右子树。
● 后序遍历：若二叉树非空，则先按后序遍历左子树，再按后序遍历右子树，最后访问根节点。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <stdlib.h>
（3）二叉链表的结构声明，代码如下：
typedef struct node /*二叉链表结构声明*/
{
struct node *lchild;
char data;
struct node *rchild;
}bitnode, *bitree; /*bitnode、bitree为该结构体类型*/
（4）自定义CreatTree（）函数，用于构造二叉树，代码如下：
bitree CreatTree（） /*构造二叉树*/
{
char a;
bitree new;
scanf（"%c", &a）;
if（a = = '#'）
return NULL;
else
{
new =（bitree）malloc（sizeof（bitnode））;
new->data = a;
new->lchild=CreatTree（）; /*递归创建左子树*/
new->rchild=CreatTree（）; /*递归创建右子树*/
}
return new;
}
（5）自定义preorderTraverse（）函数，用于先序遍历二叉树，代码如下：
void preorderTraverse（bitree bt） /*先序遍历二叉树*/
{
if（bt != NULL）
{
printf（"%c",bt->data）; /*访问根节点*/
preorderTraverse（bt->lchild）; /*访问左子树*/
preorderTraverse（bt->rchild）; /*访问右子树*/
}
}
（6）自定义inorderTraverse（）函数，用于中序遍历二叉树，代码如下：
void InorderTraverse（bitree bt） /*中序遍历二叉树*/
{
if（bt != NULL）
{
InorderTraverse（bt->lchild）; /*访问左子树*/
printf（"%c",bt->data）; /*访问根节点*/
InorderTraverse（bt->rchild）; /*访问右子树*/
}
}
（7）自定义postorderTraverse（）函数，用于后序遍历二叉树，代码如下：
void postorderTraverse（bitree bt）
{
if（bt != NULL）
{
postorderTraverse（bt->lchild）; /*访问左子树*/
postorderTraverse（bt->rchild）; /*访问右子树*/
printf（"%c",bt->data）; /*访问根节点*/
}
}
（8）主函数程序代码如下：
main（）
{
bitree root;
root=CreatTree（）; /*调用CreatTree函数构造二叉树*/
printf（"preorder traversal:\n"）;
preorderTraverse（root）; /*调用preorderTraverse函数先序遍历二叉树*/
printf（"\n"）;
printf（"inorder traversal:\n"）;
InorderTraverse（root）; /*调用inorderTraverse函数中序遍历二叉树*/
printf（"\n"）;
printf（"postorder traversal:\n"）;
postorderTraverse（root）; /*调用postorderTraverse函数后序遍历二叉树*/
printf（"\n"）;
}
举一反三
根据本实例，读者可以编程实现以下问题：
已知一棵二叉树的中序遍历和后序遍历分别为BDCEAFHG和DECBHGFA，编程求出该二叉树前序遍历的结果。
编程求如图3.42所示的二叉树的前序、中序及后序遍历的结果。
图3.42 求二叉树前序、中序及后序
实例103 线索二叉树的创建
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\103
实例说明
构造一棵二叉树，将其线索化并将中序遍历该线索二叉树的结果显示到屏幕上。运行结果如图3.43所示。
图3.43 线索二叉树的创建
技术要点
若节点有左子树，则其lchild域指向其左孩子，否则lchild指向所遍历序列的前驱，若节点有右子树，则其rchild域指向其有孩子，否则rchild指向其遍历序列的后继。为了区分指针指向的是孩子还是作为线索指针，设定了两个标志位ltag和rtag。
● 当ltag=0时表示lchild域指向该节点的左孩子。
● 当ltag=1时表示lchild域指向该节点的前驱线索。
● 当rtag=0时表示rchild域指向该节点的右孩子。
● 当rtag=1时表示rchild域指向该节点的后继线索。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <stdlib.h>
（3）二叉链表的结构声明，代码如下：
typedef struct node /*定义线索二叉树节点结构*/
{
char data;
struct node*lchild, *rchild;
int ltag, rtag;
}bithrnode, *bithrtree;
（4）自定义CreatTree（）函数，用于构造二叉链表，代码如下：
bithrtree CreatTree（） /*创建二叉链表*/
{
char a;
bithrtree new;
scanf（"%c", &a）;
if（a = = '#'）
return NULL;
else
{
new =（bithrtree）malloc（sizeof（bithrnode））;
new->data = a;
new->ltag = 0;
new->rtag = 0;
new->lchild=CreatTree（）; /*递归创建左子树*/
new->rchild=CreatTree（）; /*递归创建右子树*/
}
return new;
}
（5）自定义inthread（）函数，用于将二叉树线索化，代码如下：
void inthread（bithrtree p,bithrtree pre） /*将二叉树线索化*/
{
if（p）
{
inthread（p->lchild,pre）; /*将左子树线索化*/
if（p->lchild = = NULL）
{
p->ltag=1; /*p->ltag置1*/
p->lchild=pre; /*左指针指向其前驱*/
}
if（pre->rchild = = NULL）
{
pre->rtag=1; /*pre->rtag置1*/
pre->rchild=p; /*右指针指向其前驱*/
}
pre = p;
inthread（p->rchild,pre）; /*将右子树线索化*/
}
}
（6）自定义inorder_thread（）函数，用于中序遍历二叉树，并将其线索化，代码如下：
bithrtree inorder_thread（bithrtree t） /*中序遍历线索二叉树并将其线索化*/
{
bithrtree thrt; /*头节点*/
bithrtree pre,p; /*pre访问过的节点，p当前节点*/
thrt=（bithrtree）malloc（sizeof（bithrnode））;/*为头节点分配空间*/
thrt->ltag=0; /*初始化标志域*/
thrt->rtag = 1;
thrt->rchild=thrt; /*右指针指向头节点本身*/
if（t = = NULL）
/*判断二叉树是否为空*/
thrt->lchild = thrt;
/*左指针指向头节点*/
else
{
p=thrt->lchild=t; /*头节点左指针指向二叉树*/
thrt->ltag = 0;
pre = thrt;
inthread（p,pre）; /*进行线索化*/
pre->rchild=thrt; /*最后一个节点*/
pre->rtag = 1;
thrt->rchild=pre; /*头节点右指针指向最后一个节点*/
thrt->rtag = 1;
}
return thrt;
}
（7）自定义inorder_thr（）函数，用于中序遍历线索二叉树，代码如下：
void Inorder_thr（bithrtree t） /*中序遍历线索二叉树*/
{
if（t != NULL）
{
if（t->ltag = = 0）
Inorder_thr（t->lchild）;
/*递归遍历左子树*/
printf（"%c", t->data）;
if（t->rtag = = 0）
Inorder_thr（t->rchild）;
/*递归遍历右子树*/
}
}
（8）主函数程序代码如下：
void main（）
{
bithrtree root;
root=CreatTree（）; /*构建二叉树*/
printf（"inorder traversal:\n"）;
Inorder_thr（root）; /*中序遍历二叉树*/
}
举一反三
根据本实例，读者可以：
编程将如图3.42所示的二叉树线索化。
对任意森林编程求其前序和后序遍历的结果。
实例104 二叉排序树
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\104
实例说明
编程实现以下功能：创建一棵二叉排序树，创建完成后输入要查找的数据进行查找并将查找结果显示出来。运行结果如图3.44所示。
图3.44 二叉排序树
技术要点
二叉排序树是一棵具有如下特征的非空二叉树。
（1）若它的左子树非空，则左子树上所有节点的关键字均小于根节点的关键字。
（2）若它的右子树非空，则右子树上所有节点的关键字均大于根节点的关键字。
（3）左、右子树本身又各是一棵二叉排序树。
二叉排序树的创建与普通二叉树的思想相同，但在输入数值时要注意输入的数值应满足二叉排序树的规则即左小右大。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <stdlib.h>
（3）二叉链表的结构声明，代码如下：
ttypedef struct node /*二叉链表结构声明*/
{
struct node *lchild;
int data;
struct node *rchild;
}bitnode, *bitree; /*bitnode、bitree为该结构体类型*/
（4）自定义CreatTree（）函数，用于构造二叉树，代码如下：
bitree CreatTree（） /*构造二叉树*/
{
int a;
bitree new;
scanf（"%d", &a）;
if（a = = 0）
return NULL;
else
{
new =（bitree）malloc（sizeof（bitnode））;
new->data = a;
new->lchild=CreatTree（）; /*递归创建左子树*/
new->rchild=CreatTree（）; /*递归创建右子树*/
}
return new;
}
（5）自定义Search（）函数，用于节点数据查找，代码如下：
void Search（bitree p,int key） /*自定义函数search实现数据查找*/
{
int n = 0;
while（p!=NULL） /*当节点不为空执行循环体语句*/
{
n++; /*记录查询次数*/
if（p->data==key） /*找到要查找的元素*/
{
printf（"successful,search %d times",n）; /*输出查询次数*/
break; /*跳出循环*/
}
else if（p->data > key）
p = p->lchild;
/*当节点的数据比要查找的数据大，则继续查询左孩子节点*/
else
p = p->rchild;
/*当节点的数据比要查找的数据小，则继续查询右孩子节点*/
}
if（p = = NULL）
printf（"no found!"）; /*当节点为空，输出提示未查到*/
}
（6）主函数程序代码如下：
void main（）
{
bitree root;
int key;
root=CreatTree（）; /*构建二叉排序树*/
printf（"please input the number which do you want to search:\n"）;
scanf（"%d",&key）; /*输入要查找的数据*/
Search（root,key）; /*调用Search函数进行查找*/
}
举一反三
根据本实例，读者可以：
编程实现树的存储及遍历。
假设二叉排序树t的各元素值均不相同，设计一个算法按递增次序打印各元素值。
实例105 哈夫曼编码
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\105
实例说明
已知a、b、c、d、e、f各节点的权值分别为18、20、4、13、16、38，采用哈夫曼编码法对各节点进行编码。运行结果如图3.45所示。
图3.45 哈夫曼编码
技术要点
哈夫曼编码算法：森林中共有n棵二叉树，每棵二叉树中仅有一个孤立的节点，他们既是根又是叶子，将当前森林中的两棵根节点权值最小的二叉树合并成一棵新二叉树，每合并一次，森林中就减少一棵树。森林中n棵树要进行n−1次合并，才能使森林中的二叉树的数目由n棵减少到一棵最终的哈夫曼树。每次合并时都会产生一个新节点，合并n−1次也就产生n−1个新节点，所以最终求得的哈夫曼树有2n−1个节点。
哈夫曼树中没有度为1的节点，实际上一棵具有n个叶子节点的哈夫曼树共有2n−1个节点，可以存储在一个大小为2n−1的一维数组中。在构造完哈夫曼树后再求编码需从叶子节点出发走一条从叶子到根的路径。对每个节点我们既需要知道双亲的信息，又需要知道孩子节点的信息。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件并进行宏定义：
#define MAXSIZE 50
#include <string.h>
#include <stdio.h>>
（3）定义结构体类型huffnode及huffcode，分别来存储节点信息及各节点编码，代码如下：
typedef struct
{
char data; /*节点值*/
int weight; /*权值*/
int parent; /*父节点*/
int left; /*左节点*/
int right; /*右节点*/
int flag; /*标志位*/
} huffnode;
typedef struct /*节点编码结构体*/
{
char code[MAXSIZE];
int start;
} huffcode;
huffnode htree[2 *MAXSIZE];
huffcode hcode[MAXSIZE];
（4）自定义select（）函数用来寻找权值最小的节点。代码如下：
int select（int i）/*找出权值最小的节点*/
{
int k = 32767;
int j, q;
for（j = 0; j <= i; j++）
if（htree[j].weight<k&&htree[j].flag== -1）
{
k = htree[j].weight;
q = j;
}
htree[q].flag=1; /*将找到的节点标志位置1*/
return q;
}
（5）自定义creat_hufftree（）函数来创建哈夫曼树。代码如下：
void creat_hufftree（int n） /*创建哈夫曼树*/
{
int i, l, r;
for（i = 0; i < 2 *n -1; i++）
htree[i].parent=htree[i].left=htree[i].right=htree[i].flag= -1;
/*均置-1*/
for（i = n; i < 2 *n -1; i++）
{
l = select（i -1）;
r=select（i-1）; /*找出权值最小的两个节点*/
htree[l].parent = i;
htree[r].parent = i;
htree[i].weight = htree[l].weight + htree[r].weight;
/*左右节点权值相加等于新节点的权值*/
htree[i].left = l;
htree[i].right = r;
}
}
（6）自定义creat_code（）函数来为各节点进行哈夫曼编码。代码如下：
creat_huffcode（int n） /*求哈夫曼编码*/
{
int i, f, c;
huffcode d;
for（i = 0; i < n; i++）
{
d.start = n + 1;
c = i;
f = htree[i].parent;
while（f!= −1）
{
if（htree[f].left = = c）
/*判断c是否是左子树*/
d.code[--d.start] = '0';
/*左边编码为0*/
else
d.code[--d.start] = '1';
/*右边编码为1*/
c = f;
f = htree[f].parent;
}
hcode[i] = d;
}
}
（7）自定义display（）函数来输出各节点的编码。代码如下：
void display_huffcode（int n） /*输入各节点编码*/
{
int i, k;
printf（"huffman is:\n"）;
for（i = 0; i < n; i++）
{
printf（"%c:",htree[i].data）; /*输出节点*/
for（k = hcode[i].start; k <= n; k++）
printf（"%c", hcode[i].code[k]）;
/*输出每个节点对应的编码*/
printf（"\n"）;
}
}
（8）主函数程序代码如下：
void main（）
{
int n = 6;
htree[0].data = 'a';
htree[0].weight = 18;
htree[1].data = 'b';
htree[1].weight = 20;
htree[2].data = 'c';
htree[2].weight = 4;
htree[3].data = 'd';
htree[3].weight = 13;
htree[4].data = 'e';
htree[4].weight = 16;
htree[5].data = 'f';
htree[5].weight = 48;
creat_hufftree（n）; /*调用函数创建哈夫曼树*/
creat_huffcode（n）; /*调用函数构造哈夫曼编码*/
display_huffcode（n）; /*显示各节点哈夫曼编码*/
}
举一反三
根据本实例，读者可以：
若哈夫曼树中有n个叶子节点，试证明树中共有2n−1个节点。
对于一组给定的权值W={10，28，5，7，24，9，26}，建立相应的哈夫曼树并计算其WPL值。
3.6 图及图的应用
图是一种比线性表和树更为复杂的非线性结构。图结构可以描述各种复杂的数据对象，特别是近年来的迅速发展，已经被广泛应用到人工智能、工程、计算科学、语言学、物理、化学等领域中。本节的几个实例就是关于图存储及简单应用。
实例106 图的邻接表存储
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\106
实例说明
利用邻接表存储无向图，要求从键盘中输入每条边所连接的顶点，如图3.46所示，输入的内容应为1，2，1，4，2，1，2，3，2，5，3，2，3，4，3，5，4，1，4，3，5，2，5，3，运行结果如图3.47所示。
图3.46 无向图
图3.47 邻接表存储无向图
技术要点
邻接表表示法是使用基本链表来链接每个顶点的邻接顶点的。顶点的结构如图3.48所示。
图3.48 顶点结构
这里的nextnode指向下一个邻接的节点。本题中无向图的邻接表表示如图3.49所示。
图3.49 图的邻接表存储
邻接表存储图的算法描述如下。
（1）用数组存储无向图的顶点，实际上是存储无向图的边（每条边存储两次，因为起点和终点不同）。
（2）在内存中给一个新节点分配空间，并初始化新节点内容。
（3）设置指针位置，将指针每次遍历至链尾等待下次要插入节点。
（4）将前面存储在数组中边的内容插入到链表中。
（5）最后将邻接表的内容输出。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <stdlib.h>
（3）定义图的顶点结构并定义数组vertex_node为该结构体变量同时也定义graph为节点类型，同时声明代码如下：
struct node /*图的顶点结构*/
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph;
struct node vertex_node[10];
（4）自定义creat_graph（）函数，用于构造邻接表，代码如下：
void creat_graph（int *node, int n）
{
graph newnode,p; /*定义一个新节点及指针*/
int start, end, i;
for（i = 0; i < n; i++）
{
start=node[i*2]; /*边的起点*/
end=node[i*2+1]; /*边的终点*/
newnode =（graph）malloc（sizeof（struct node））;
newnode->vertex=end; /*新节点的内容为边终点处顶点的内容*/
newnode->nextnode = NULL;
p=&（vertex_node[start]）; /*设置指针位置*/
while（p->nextnode != NULL）
p=p->nextnode; /*寻找链尾*/
p->nextnode=newnode; /*在链尾处插入新节点*/
}
}
（5）主函数程序代码如下：
main（）
{
graph p;
int node[100], i,sn,vn;
printf（"please input the number of sides:\n"）;
scanf（"%d",&sn）; /*输入无向图的边数*/
printf（"please input the number of vertexes\n"）;
scanf（"%d",&vn）;
printf（"please input the vertexes which connected by the sides:\n"）;
for（i = 0; i < 4 *sn; i++）
scanf（"%d", &node[i]）;
/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/
for（i = 1; i <= vn; i++）
{
vertex_node[i].vertex=i; /*将每个顶点的信息存入数组中*/
vertex_node[i].nextnode = NULL;
}
creat_graph（node,2*sn）; /*调用函数创建邻接表*/
printf（"the result is:\n"）;
for（i=1;i<=vn;i++） /*将邻接表内容输出*/
{
printf（"vertex%d:",vertex_node[i].vertex）; /*输出顶点内容*/
p = vertex_node[i].nextnode;
while（p != NULL）
{
printf（"->%3d",p->vertex）; /*输出邻接顶点的内容*/
p=p->nextnode; /*指针指向下个邻接顶点*/
}
printf（"\n"）;
}
}
举一反三
根据本实例，读者可以：
编程对图3.50实现邻接表存储。
编程对图3.50实现邻接矩阵存储。
图3.50 邻接表存储
实例107 图的深度优先搜索
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\107
实例说明
编程实现对如图3.51所示的无向图进行深度优先搜索，运行结果如图3.52所示。
图3.51 无向图
图3.52 图的深度优先搜索
技术要点
假设初始时图中所有顶点未曾被访问，则深度优先搜索可从图3.52中某个顶点v出发，首先访问此顶点，然后任选一个v的未被访问的邻接点v1出发，继续进行深度优先搜索，直至图中所有和v有路径相通的顶点都被访问到。若此时图中还有顶点未被访问，则选一个图中未被访问的顶点出发，重复上面的过程，直到图中所有顶点均被访问。
下面举例具体说明，如图3.53所示，深度优先搜索的过程如下。
首先从顶点1开始，检查顶点1的表头找到指针域指向的链表的第一个顶点2，顶点2未被访问过则访问顶点2，将指针移到顶点2的表头，找到指针域指向的链表的第一个顶点1，顶点1被访问过，再在链表中找下一个即顶点3，顶点3未被访问过则访问顶点3，将指针移到顶点3的表头，找到指针域指向的链表的第一个顶点1，顶点1被访问过，再在链表中找下一个即顶点2，顶点2也被访问过，继续在链表中找下一个即顶点5，顶点5未访问过则访问，将指针移到顶点5的表头，找到指针域指向的链表的第一个顶点3，顶点3被访问过，再在链表中找下一个即顶点4，顶点4未被访问，则访问顶点4，然后将指针移到顶点4的表头，找到指针域指向的链表的第一个顶点2，顶点2被访问过，再在链表中找下一个即顶点5，顶点5也被访问过。那么现在所有的顶点均被访问过，则最终遍历的顺序是：1，2，3，5，4。
图3.53 深度优先搜索
通过上面的叙述我们会发现图的深度遍历与二叉树的遍历一样可以通过递归调用函数实现。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <stdlib.h>
（3）定义图的顶点结构并定义数组vertex_node为该结构体变量同时也定义graph为节点类型，同时声明代码如下：
struct node /*图的顶点结构*/
{
int vertex;
int flag;
struct node *nextnode;
};
typedef struct node *graph;
struct node vertex_node[10];
（4）自定义creat_graph（）函数，用于构造邻接表，代码如下：
void creat_graph（int *node, int n）
{
graph newnode,p; /*定义一个新节点及指针*/
int start, end, i;
for（i = 0; i < n; i++）
{
start=node[i*2]; /*边的起点*/
end=node[i*2+1]; /*边的终点*/
newnode =（graph）malloc（sizeof（struct node））;
newnode->vertex=end; /*新节点的内容为边终点处顶点的内容*/
newnode->nextnode = NULL;
p=&（vertex_node[start]）; /*设置指针位置*/
while（p->nextnode != NULL）
p=p->nextnode; /*寻找链尾*/
p->nextnode=newnode; /*在链尾处插入新节点*/
}
}
（5）自定义dfs（）函数，实现图的深度优先遍历，代码如下：
void dfs（int k）
{
graph p;
vertex_node[k].flag=1; /*将标志位置1，证明该节点已访问过*/
printf（"vertex[%d]", k）;
p=vertex_node[k].nextnode; /*指针指向下个节点*/
while（p != NULL）
{
if（vertex_node[p->vertex].flag==0） /*判断该节点的标志位是否为0*/
dfs（p->vertex）; /*继续遍历下个节点*/
p=p->nextnode; /*若已遍历过p指向下一个节点*/
}
}
（6）主函数程序代码如下：
main（）
{
graph p;
int node[100], i, sn,vn;
printf（"please input the number of sides:\n"）;
scanf（"%d",&sn）; /*输入无向图的边数*/
printf（"please input the number of vertexes\n"）;
scanf（"%d",&vn）;
printf（"please input the vertexes which connected by the sides:\n"）;
for（i = 0; i < 4 *sn; i++）
scanf（"%d", &node[i]）;
/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/
for（i = 1; i <= vn; i++）
{
vertex_node[i].vertex=i; /*将每个顶点的信息存入数组中*/
vertex_node[i].flag = 0;
vertex_node[i].nextnode = NULL;
}
creat_graph（node,2*sn）; /*调用函数创建邻接表*/
printf（"the result is:\n"）;
for（i=1;i<=vn;i++） /*将邻接表内容输出*/
{
printf（"vertex%d:",vertex_node[i].vertex）; /*输出顶点内容*/
p = vertex_node[i].nextnode;
while（p != NULL）
{
printf（"->%3d",p->vertex）; /*输出邻接顶点的内容*/
p=p->nextnode; /*指针指向下个邻接顶点*/
}
printf（"\n"）;
}
printf（"the result of depth-first search is:\n"）;
dfs（1）; /*调用函数进行深度优先遍历*/
printf（"\n"）;
}
举一反三
根据本实例，读者可以：
深度优先搜索非递归算法。
编程实现对图3.54实现深度优先搜索。
图3.54 实现深度优先搜索
实例108 图的广度优先搜索
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\03\108
实例说明
编程实现对图3.55所示的无向图进行广度优先搜索，运行结果如图3.56所示。
图3.55 无向图
图3.56 图的广度优先搜索
技术要点
假设初始时图中所有顶点未曾被访问，则广度优先搜索从图中某个顶点V出发，访问此顶点，然后依次访问V的各个未被访问的邻接点，再分别从这些邻接点出发一次访问它们的各个未被访问的邻接点，邻接点出发的次序按“先被访问的先出发”的原则，直到图中前面已被访问的顶点的邻接点都被访问到。若此时图中还有顶点未被访问，则另选图中一个未曾被访问的顶点作始点，重复上面的过程。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <stdlib.h>
（3）定义图的顶点结构并定义数组vertex_node为该结构体变量同时也定义graph为节点类型，同时声明代码如下：
struct node
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph;
struct node vertex_node[10];
#define MAXQUEUE 100
int queue[MAXQUEUE];
int front= -1;
int rear= -1;
int visited[10];
（4）自定义creat_graph（）函数，用于构造邻接表，代码如下：
void creat_graph（int *node, int n）
{
graph newnode,p; /*定义一个新节点及指针*/
int start, end, i;
for（i = 0; i < n; i++）
{
start=node[i*2]; /*边的起点*/
end=node[i*2+1]; /*边的终点*/
newnode =（graph）malloc（sizeof（struct node））;
newnode->vertex=end; /*新节点的内容为边终点处顶点的内容*/
newnode->nextnode = NULL;
p=&（vertex_node[start]）; /*设置指针位置*/
while（p->nextnode != NULL）
p = p->nextnode;
/*寻找链尾*/
p->nextnode = newnode; /*在链尾处插入新节点*/
}
}
（5）自定义enqueue（）和dequeue（）函数，用于实现元素入队和出队，代码如下：
int enqueue（int value） /*元素入队列*/
{
if（rear >= MAXQUEUE）
return -1;
rear++; /*移动队尾指针*/
queue[rear] = value;
}
int dequeue（）/*元素出队列*/
{
if（front = = rear）
return -1;
front++; /*移动队头指针*/
return queue[front];
}
（6）自定义bfs（）函数，实现图的广度优先遍历，代码如下：
void bfs（int k）/*广度优先搜索*/
{
graph p;
enqueue（k）; /*元素入队*/
visited[k] = 1;
printf（"vertex[%d]", k）;
while（front != rear）
/*判断是否对空*/
{
k = dequeue（）; /*元素出队*/
p = vertex_node[k].nextnode;
while（p != NULL）
{
if（visited[p->vertex] = = 0）
/*判断其是否被访问过*/
{
enqueue（p->vertex）;
visited[p->vertex]=1; /*访问过的元素置1*/
printf（"vertex[%d]", p->vertex）;
}
p = p->nextnode; /*访问下一个元素*/
}
}
}
（7）主函数程序代码如下：
main（）
{
graph p;
int node[100], i, sn, vn;
printf（"please input the number of sides:\n"）;
scanf（"%d",&sn）; /*输入无向图的边数*/
printf（"please input the number of vertexes\n"）;
scanf（"%d", &vn）;
printf（"please input the vertexes which connected by the sides:\n"）;
for（i = 0; i < 4 *sn; i++）
scanf（"%d", &node[i]）;
/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/
for（i = 1; i <= vn; i++）
{
vertex_node[i].vertex=i; /*将每个顶点的信息存入数组中*/
vertex_node[i].nextnode = NULL;
}
creat_graph（node,2*sn）; /*调用函数创建邻接表*/
printf（"the result is:\n"）;
for（i = 1; i <= vn; i++）
/*将邻接表内容输出*/
{
printf（"vertex%d:",vertex_node[i].vertex）; /*输出顶点内容*/
p = vertex_node[i].nextnode;
while（p != NULL）
{
printf（"->%3d",p->vertex）; /*输出邻接顶点的内容*/
p=p->nextnode; /*指针指向下个邻接顶点*/
}
printf（"\n"）;
}
printf（"the result of breadth-first search is:\n"）;
bfs（1）; /*调用函数进行深度优先遍历*/
printf（"\n"）;
}
举一反三
根据本实例，读者可以：
不用visited数组，改进此程序。
编程实现对图3.57实现广度优先搜索。
图3.57 实现广度优先搜索
实例109 Prim算法求最小生成树
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\109
实例说明
用Prim算法求如图3.58所示的连通网的最小生成树。运行结果如图3.59所示。
图3.58 连通图
图3.59 Prim算法
技术要点
Prim算法用于求无向图的最小生成树，算法的具体思想如下。
设图G =（V，E）是一个具有n个顶点的连通网，其生成树的顶点集合为U。首先把v0放入U，再在所有u∈U，v∈V−U的边（u，v）∈E中找一条最小权值的边，加入生成树，并把该边的v加入U集合。如果U集合已有n个元素，则结束，否则在剩下部分中继续寻找最小权值的边。其算法的时间复杂度为O（n^2）。
下面来具体看一下本实例Prim算法的执行过程。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件并进行宏定义：
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 30
#define MAXCOST 1000
（3）自定义prim（）函数，用来求最小生成树，代码如下：
void prim（int c[MAXVEX][MAXVEX], int n）
{
int i, j, k, min, lowcost[MAXVEX], closest[MAXVEX];
for（i = 2; i <= n; i++）
{
lowcost[i] = c[1][i]; /*从顶点1开始*/
closest[i] = 1;
}
closest[1] = 0;
for（i = 2; i <= n; i++）
/*从U之外求离U中某一顶点最近的顶点*/
{
min = MAXCOST;
j = 1;
k = i;
while（j <= n）
{
if（lowcost[j] < min && closest[j] != 0）
/*在V-U中找出离U最近的顶点，赋给k*/
{
min = lowcost[j];
k = j;
}
j++;
}
printf（"（%d,%d）", closest[k], k）; /*打印边*/
closest[k]=0; /*k加入到U中*/
for（j = 2; j <= n; j++）
if（closest[j] != 0 && c[k][j] < lowcost[j]）
{
lowcost[j]=c[k][j]; /*修改数组lowcost和closest*/
closest[j] = k;
}
}
}
（4）主要程序代码如下：
main（）
{
int n = 7, i, j, mx[MAXVEX][MAXVEX];
for（i = 0; i <= n; i++）
for（j = 0; j <= n; j++）
mx[i][j] = MAXCOST;
/*给mx中每个元素赋初值*/
mx[1][2] = 50;
mx[1][3] = 60;
mx[2][4] = 65;
mx[2][5] = 40;
mx[3][4] = 52;
mx[3][7] = 45;
mx[4][5] = 50;
mx[5][6] = 70;
mx[4][6] = 30;
mx[4][7] = 42;
printf（"Minimal Spanning Tree is:\n"）;
prim（mx, n）;
}
举一反三
根据本实例，读者可以：
用Prim算法求图3.60中的连通网的最小生成树。
用Kruskal算法求图3.60中的连通网的最小生成树。
图3.60 求最小生成树
实例110 迪杰斯特拉算法
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\03\110
实例说明
用迪杰斯特拉算法求解如图3.61所示的顶点1到各顶点的最短路径，运行结果如图3.62所示。
图3.61 求顶点1到各点的最短路径
图3.62 迪杰斯特拉算法
技术要点
迪杰斯特拉算法思想：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个将V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件并进行宏定义及全局变量声明：
#include <stdlib.h>
#include <stdio.h>
#define MAXNODE 30
#define MAXCOST 1000
int dist[MAXNODE], cost[MAXNODE][MAXNODE], n = 5
（3）自定义prim（）函数，用来求最小生成数，代码如下：
void dijkstra（int v0）
{
int s[MAXNODE];
int mindis, dis, i, j, u;
for（i = 1; i <= n; i++）
{
dist[i] = cost[v0][i];
s[i] = 0;
}
s[v0] = 1;
for（i = 1; i <= n; i++）
{
mindis = MAXCOST;
for（j = 1; j <= n; j++）
if（s[j] = = 0 && dist[j] < mindis）
{
u = j;
mindis = dist[j];
}
s[u] = 1;
for（j = 1; j <= n; j++）
if（s[j] = = 0）
{
dis = dist[u] + cost[u][j];
dist[j] =（dist[j] < dis）? dist[j]: dis;
}
}
}
（4）自定义display_path（）函数，用来输出到各顶点的最短路径，代码如下：
void display_path（int v0）
{
int i;
printf（"\n顶点 %d到各顶点的最短路径长度如下:\n",v0）;
for（i = 1; i <= n; i++）
{
printf（" （v%d->v%d）:",v0,i）;
if（dist[i] = = MAXCOST）
printf（"wu lun jing\n"）;
else
printf（"%d\n", dist[i]）;
}
}
（5）主要程序代码如下：
main（）
{
int i, j, v0 = 1;
for（i = 1; i <= n; i++）
for（j = 1; j <= n; j++）
cost[i][j] = MAXCOST;
for（i = 1; i <= n; i++）
cost[i][i] = 0;
cost[1][2] = 10;
cost[1][5] = 100;
cost[1][4] = 30;
cost[2][3] = 50;
cost[4][3] = 20;
cost[3][5] = 10;
cost[4][5] = 60;
dijkstra（v0）;
display_path（v0）;
}
举一反三
根据本实例，读者可以：
用迪杰斯特拉算法求解图3.63顶点1到各顶点的最短路径。
用弗洛伊德算法求解图3.63顶点1到各顶点的最短路径。
图3.63 求解最短路径