3.4 应用实例
3.4.1 约瑟夫环问题
本章的引言部分给出了约瑟夫环问题及其数据模型，下面考虑算法设计与程序实现。
【算法】 由于约瑟夫环问题本身具有循环性质，考虑采用循环单链表。约瑟夫环问题的基本思想是设置一个计数器count和工作指针p，当计数器累加到m时删除结点p。为了统一对表中任意结点的操作，循环单链表不带头结点；为了便于删除操作，设两个工作指针为pre和p，pre指向结点p的前驱结点；为了使计数器从1开始计数，采用尾指针指示的循环单链表，将pre初始化为指向终端结点，将p初始化为指向开始结点，如图3-33所示。
图3-33 约瑟夫环的初始状态
用函数Joseph求解约瑟夫环问题，算法用伪代码描述如下 ：
算法：Joseph（rear，m）
输入：尾指针指示的循环单链表rear，密码m
输出：约瑟夫环的出环顺序
1.初始化：pre=rear；p=rear-＞next；count=1；
2.重复下述操作，直到链表中只剩一个结点：
2.1 如果count小于m，则：
2.1.1 工作指针pre和p后移；
2.1.2 count++；
2.2 否则，执行下述操作：
2.2.1 输出结点p的数据域；
2.2.2 删除结点p；
2.2.3 p指向pre的后继结点；count=1重新开始计数；
3.输出结点p的数据域，删除结点p；
【程序】 主函数首先输入约瑟夫环的长度n和密码m，然后调用函数Creat建立由尾指针rear指示的循环单链表，最后调用函数Joseph打印出环的顺序。程序如下：
#include＜stdio.h＞ //使用库函数printf和scanf
#include＜malloc.h＞ //使用malloc等库函数实现动态存储分配
typedefstructNode //定义单链表的结点Node
{
intdata；
structNode*next；
}Node；
Node*Creat（intn）； //函数声明，构造尾指针指示的约瑟夫环
voidJoseph（Node*rear，intm）； //函数声明，打印出环的顺序
//以下是主函数
intmain（）
{
intn，m；
Node*rear=NULL； //定义尾指针rear并初始化为空
printf（＂请输入约瑟夫环的长度：＂）；//输出提示信息
scanf（＂%d＂，&n）；
printf（＂请输入密码：＂）； //输出提示信息
scanf（＂%d＂，&m）；
rear=Creat（n）； //函数调用，返回的尾指针赋给rear
Joseph（rear，m）； //函数调用，实参rear是尾指针
return0； //将0返回操作系统，表明程序正常结束
}
//以下是其他函数定义
Node*Creat（intn） //函数定义，返回值是循环单链表的尾指针
{
Node*rear=NULL，*s； //定义尾指针rear并初始化为空
inti；
rear=（Node*）malloc（sizeof（Node））;//申请结点，rear指向该结点
rear-＞data=1； //结点rear的数据域为1
rear-＞next=rear； //建立长度为1的循环单链表
for（i=2；i＜=n；i++） //依次插入数据域为2，3，…，n的结点
{
s=（Node*）malloc（sizeof（Node））;//申请结点，s指向该结点
s-＞data=i； //结点s的数据域为i
s-＞next=rear-＞next； //将结点s插入尾结点rear的后面
rear-＞next=s；
rear=s； //指针rear指向当前的尾结点
}
returnrear； //结束函数的执行，并将尾指针rear返回到调用处
}
voidJoseph（Node*rear，intm）
{ //函数定义，形参rear为循环单链表的尾指针，形参m为密码
Node*pre=rear，*p=rear-＞next，*q； //初始化工作指针p和pre
intcount=1； //初始化计数器count
printf（＂出环的顺序是：＂）；
while（p-＞next！=p） //循环，直到循环链表中只剩一个结点
{
if（count＜m） //计数器未累加到密码值
{
pre=p；p=p-＞next； //将工作指针pre和p分别后移
count++； //计数器加1
}
else //计数器已经累加到密码值
{
printf（＂%-3d＂，p-＞data）； //宽度3位左对齐打印出环的编号
q=p； //指针q暂存即将删除的结点
pre-＞next=p-＞next； //将结点p摘链
p=pre-＞next； //工作指针p后移，但pre不动
free（q）； //释放指针q指向的存储单元
count=1； //计数器从1开始重新计数
}
}
printf（＂%-3d\n＂，p-＞data）； //宽度3位左对齐输出最后一个结点的编号
free（p）； //释放最后一个结点
return； //结束函数Joseph的执行
}
3.4.2 一元多项式求和
【问题】 设A（x）=a0+a1x+a2x2+…+anxn，B（x）=b0+b1x+b2x2+…+bmxm，并且多项式的指数可能很高且变化很大，例如：A（x）=7+12x3-2x8+5x12，B（x）=4x+6x3+2x8+5x20+7x28，求两个一元多项式的和，即求A（x）+B（x）。
【想法】 由于一元多项式A（x）=a0+a1x+a2x2+…+anxn由n+1个系数唯一确定，因此，可以用一个线性表（a0，a1，a2，…，an）来表示，每一项的指数i隐含在其系数ai的序号里。如果多项式的指数可能很高且变化很大，则一元多项式对应的线性表中就会存在很多零元素。一个较好的存储方法是只存储非零项，但是需要在存储非零系数的同时存储相应的指数。这样，一元多项式的每一个非零项可由系数和指数唯一表示。例如，一元多项式A（x）=7+12x3-2x8+5x12就可以用线性表（（7，0），（12，3），（-2，8），（5，12））来表示。
由数学知识，一元多项式求和实质上是合并同类项的过程，也就是将两个一元多项式对应的线性表进行合并的过程。例如，A（x）=7+12x3-2x8+5x12和B（x）=4x+6x3+2x8+5x20+7x28的求和，即是将线性表（（7，0），（12，3），（-2，8），（5，12））和（（4，1），（6，3），（2，8），（5，20），（7，28））进行合并，结果为（（7，0），（4，1），（18，3），（5，12），（5，20），（7，28））。
【算法】 如何存储多项式对应的线性表呢？对于指数相差很多的两个一元多项式，相加会改变多项式的系数和指数。若相加的某两项的指数不等，则两项应分别加在结果中，将引起线性表的插入；若某两项的指数相等，则系数相加，若相加结果为零，将引起线性表的删除。由于在线性表的合并过程中需要频繁地执行插入和删除操作，因此考虑采用单链表存储。
在表示一元多项式的单链表中，每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。结点结构如图3-34所示。其中
图3-34 一元多项式链表的结点结构
coef：系数域，存放非零项的系数；
exp：指数域，存放非零项的指数；
next：指针域，存放指向下一结点的指针。
下面分析多项式求和的执行过程。设单链表A和B分别存储两个多项式，求和结果存储在单链表A中，设两个工作指针p和q分别指向两个单链表的开始结点。两个多项式求和实质上是对结点p的指数域和结点q的指数域进行比较，有下列三种情况：
（1）若p-＞exp小于q-＞exp，则结点p应为结果链表中的一个结点，将指针p后移，如图3-35所示。
图3-35 第一种情况示意图
（2）若p-＞exp大于q-＞exp，则结点q应为结果中的一个结点，将q插入到第一个单链表中结点p之前，并将指针q指向单链表B中的下一个结点，如图3-36所示。为此，在单链表A中应该设置两个工作指针pre和p，使得pre指向p的前驱结点。
图3-36 第二种情况示意图
（3）若p-＞exp等于q-＞exp，则p与q所指为同类项，将q的系数加到p的系数上。若相加结果不为0，则将指针p后移，并删除结点q，为此，在单链表B中应该设置两个工作指针qre和q，使得qre指向q的前驱结点，如图3-37（a）所示；若相加结果为0，则表明结果中无此项，删除结点p和结点q，并将指针p和指针q分别后移，如图3-37（b）所示。
图3-37 第三种情况示意图
综合上述三种情况，一元多项式相加算法用伪代码描述如下 ：
算法：AddPolynomial（A，B）
输入：两个单链表A和B
输出：单链表A和B的合并结果
1.初始化工作指针pre，p，qre，q；
2.while（p存在且q存在）执行下列三种情形之一：
2.1 如果p-＞exp小于q-＞exp，则指针pre和p后移；
2.2 如果p-＞exp大于q-＞exp，则：
2.2.1 将结点q插入到结点p之前；
2.2.2 指针q指向原指结点的下一个结点；
2.3 如果p-＞exp等于q-＞exp，则：
2.3.1 p-＞coef=p-＞coef+q-＞coef；
2.3.2 如果p-＞coef等于0，则执行下列操作，否则，指针p后移；
2.3.2.1 删除结点p；
2.3.2.2 使指针p指向它原指结点的下一个结点；
2.3.3 删除结点q；
2.3.4 使指针q指向它原指结点的下一个结点；
3.如果q不为空，将结点q链接在第一个单链表的后面；
【程序】 主函数首先接收从键盘输入的一元多项式各项的系数和指数，分别建立多项式A（x）和B（x），然后调用函数AddPolynomial实现两个一元多项式相加，最后调用函数Print打印相加结果。程序如下：
#include＜stdio.h＞ //使用库函数printf和scanf
#include＜malloc.h＞ //使用malloc等库函数实现动态存储分配
typedefstructNode //定义单链表结点
{
intcoef，exp； //coef表示系数，exp表示指数
structNode*next；
}Node；
Node*AddPolynomial（Node*A，Node*B）； //函数声明，多项式相加
Node*Creat（）； //函数声明，建立单链表表示一元多项式
voidPrint（Node*first）； //函数声明，打印一元多项式
//空行，以下为主函数
intmain（）
{
Node*A=NULL，*B=NULL；
A=Creat（）；Print（A）； //输入多项式A（x）建立单链表，头指针为A
B=Creat（）；Print（B）； //输入多项式B（x）建立单链表，头指针为B
A=AddPolynomial（A，B）； //相加结果为头指针A指示的单链表
printf（＂结果是：＂）；
Print（A）； //输出单链表A，即相加结果
return0； //将0返回操作系统，表明程序正常结束
}
//以下是其他函数定义
Node*Creat（） //建立单链表，返回头指针
{
Node*first=NULL，*r=NULL，*s=NULL；
intcoef，exp；
first=（Node*）malloc（sizeof（Node））;//申请头结点
r=first； //尾插法建立单链表
printf（＂请输入系数和指数：＂）；
scanf（＂%d%d＂，&coef，&exp）； //输入第一项的系数和指数
while（coef！=0） //循环结束的条件是输入系数为0
{
s=（Node*）malloc（sizeof（Node））；
s-＞coef=coef；s-＞exp=exp；
r-＞next=s；r=s； //将结点s插入单链表的尾部
printf（＂请输入系数和指数：＂）；
scanf（＂%d%d＂，&coef，&exp）；
}
r-＞next=NULL； //置单链表的尾标志
returnfirst； //结束函数的执行并返回头指针
}
Node*AddPolynomial（Node*A，Node*B）
{ //多项式相加，头指针分别为A和B
Node*pre=A，*p=pre-＞next； //工作指针pre和p初始化
Node*qre=B，*q=qre-＞next； //工作指针qre和q初始化
Node*v=NULL；
while（p！=NULL&&q！=NULL）
{
if（p-＞exp＜q-＞exp） //第1种情况
{
pre=p；p=p-＞next；
}
elseif（p-＞exp＞q-＞exp） //第2种情况
{
v=q-＞next；
pre-＞next=q； //将结点q插入到结点p之前
q-＞next=p；
q=v；
}
else //第3种情况
{
p-＞coef=p-＞coef+q-＞coef； //系数相加
if（p-＞coef==0） //系数为0
{
pre-＞next=p-＞next； //则删除结点p
free（p）；
p=pre-＞next；
}
else //系数不为0
{
pre=p；p=p-＞next；
}
qre-＞next=q-＞next； //第3种情况都要删除结点q
free（q）；
q=qre-＞next；
}
}
if（q！=NULL）pre-＞next=q； //将结点q链接在第一个单链表的后面
free（B）； //释放第二个单链表的头结点所占的内存
returnA；
}
voidPrint（Node*first）
{
Node*p=first-＞next；
if（p！=NULL） //输出第一项
printf（＂%dx%d＂，p-＞coef，p-＞exp）；
p=p-＞next；
while（p！=NULL）
{
if（p-＞coef＞0） //输出系数的正号或负号
printf（＂+%dx%d＂，p-＞coef，p-＞exp）；
else
printf（＂%dx%d＂，p-＞coef，p-＞exp）；
p=p-＞next；
}
printf（＂\n＂）；
}