}
}
voidswap（int&a,int&b）
{
inttemp;
temp=a;
a=b;
b=a;
}
/**********
【题目】试编写算法求一元多项式
P（x）=a0+a1x+a2x^2+...+anx^n
的值P（x0），并确定算法中每一语句的执行次数和整个算法
的时间复杂度。
**********/
floatPolynomial（intn,inta[],floatx）
/*求一元多项式的值P（x）。
*/
/*数组a的元素a[i]为i次项的系数，i=0,...,n*/
{
floatanswer=a[0];
floattemp=1.0;
for（inti=1;i<=n;i++）
{
temp*=x;
answer+=a[i]*temp;
}
returnanswer;
}
/**********
【题目】已知k阶裴波那契序列的定义为
f（0）=0,f
（1）=0,...,f（k-2）=0,f（k-1）=1;
f（n）=f（n-1）+f（n-2）+...+f（n-k）,n=k,k+1,...
试编写求k阶裴波那契序列的第m项值的函数算法，
k和m均以值调用的形式在函数参数表中出现。
**********/
StatusFibonacci（intk,intm,int&f）
/*求k阶斐波那契序列的第m项的值f*/
{
if（k<=1||m<0）
returnERROR;
elseif（m==k-1）
f=1;
elseif（m==0）
f=0;
else
{
inti,j,sum;
int*t;
t=（int*）malloc（m*sizeof（int））;
for（i=0;i<=k-2;i++）
t[i]=0;
t[k-1]=1;
for（i=k;i<=m;i++）
{sum=0;
for（j=i-k;j<=i;j++）
sum+=t[j];
t[i]=sum;
}
f=t[m];
}
returnOK;
}
/**********
【题目】试编写算法，计算i!
×2^i的值并存入数组
a[0..n-1]的第i-1个分量中（i=1,2,…,n）。
假设计
算机中允许的整数最大值为MAXINT，则当对某个k
（1≤k≤n）使k!
×2^k>MAXINT时，应按出错处理。
注意
选择你认为较好的出错处理方法。
**********/
StatusSeries（inta[],intn）
/*求i!
*2^i序列的值并依次存入长度为n的数组a；*/
/*若所有值均不超过MAXINT，则返回OK，否则OVERFLOW*/
{
intt=1,p=1;
for（inti=1;i<=n;i++）
{
t*=i;
p*=2;
a[i-1]=t*p;
if（a[i-1]>MAXINT）
returnERROR;
}
returnOK;
}
/**********
【题目】假设有A、B、C、D、E五个高等院校进行田径对抗赛，
各院校的单项成绩均以存入计算机并构成一张表，表中每一行
的形式为：
项目名称性别校名成绩得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体
总分，并输出。
**********/
voidScores（ResultType*result,ScoreType*score）
/*求各校的男、女总分和团体总分,并依次存入数组score*/
/*假设比赛结果已经储存在result[]数组中,*/
/*并以特殊记录{"",male,'',"",0}（域scorce=0）*/
/*表示结束*/
{
inti=0;
while（result[i].sport!
=NULL）
{
switch（result[i].schoolname）
{
case'A':
score[0].totalscore+=result[i].score;
if（result[i].gender==male）
score[0].malescore+=result[i].score;
else
score[0].femalescore+=result[i].score;break;
case'B':
score[1].totalscore+=result[i].score;
if（result[i].gender==male）
score[1].malescore+=result[i].score;
else
score[1].femalescore+=result[i].score;break;
case'C':
score[2].totalscore+=result[i].score;
if（result[i].gender==male）
score[2].malescore+=result[i].score;
else
score[2].femalescore+=result[i].score;break;
case'D':
score[3].totalscore+=result[i].score;
if（result[i].gender==male）
score[3].malescore+=result[i].score;
else
score[3].femalescore+=result[i].score;break;
case'E':
score[4].totalscore+=result[i].score;
if（result[i].gender==male）
score[4].malescore+=result[i].score;
else
score[4].femalescore+=result[i].score;break;
}
i++;
}
}
/**********
【题目】试写一算法，对序列S的第i个元素赋以值e。
序列的类型定义为：
typedefstruct{
ElemType*elem;
intlength;
}Sequence;
***********/
StatusAssign（Sequence&S,inti,ElemTypee）
/*对序列S的第i个元素赋以值e，并返回OK。
*/
/*若S或i不合法，则赋值失败，返回ERROR*/
{
if（S.length<1||i>S.length）
returnERROR;
else
S.elem[i]=e;
returnOK;
}
/**********
【题目】试写一算法，由长度为n的一维数组a构建一个序列S。
序列的类型定义为：
typedefstruct{
ElemType*elem;
intlength;
}Sequence;
***********/
StatusCreateSequence（Sequence&S,intn,ElemType*a）
/*由长度为n的一维数组a构建一个序列S，并返回OK。
*/
/*若构建失败，则返回ERROR*/
{
if（n<1）
returnERROR;
else
{
S.elem=（ElemType*）malloc（n*sizeof（ElemType））;
S.elem[0]=a[0];
for（inti=1;iS.elem[i]=a[i];
S.length=n;
}
returnOK;
}
/**********
【题目】链表的结点和指针类型定义如下
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
试写一函数，构建一个值为x的结点。
***********/
LinkListMakeNode（ElemTypex）
/*构建一个值为x的结点，并返回其指针。
*/
/*若构建失败，则返回NULL。
*/
{
LNode*p;
p=（LNode*）malloc（sizeof（LNode））;
if（p==NULL）
returnNULL;
else
p->data=x;
returnp;
}
/**********
【题目】链表的结点和指针类型定义如下
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
试写一函数，构建长度为2且两个结点的值依次为x和y的链表。
**********/
LinkListCreateLinkList（ElemTypex,ElemTypey）
/*构建其两个结点的值依次为x和y的链表。
*/
/*若构建失败，则返回NULL。
*/
{
LNode*p;
p=（LNode*）malloc（sizeof（LNode））;
if（p==NULL）
returnNULL;
else
{
p->next=（LNode*）malloc（sizeof（LNode））;
if（p->next==NULL）
returnNULL;
p->data=x;
p->next->data=y;
p->next->next=NULL;
}
returnp;
}
/**********
【题目】链表的结点和指针类型定义如下
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
试写一函数，构建长度为2的升序链表，两个结点的值
分别为x和y，但应小的在前，大的在后。
**********/
LinkListCreateOrdLList（ElemTypex,ElemTypey）
/*构建长度为2的升序链表。
*/
/*若构建失败，则返回NULL。
*/
{
LNode*p;
p=（LNode*）malloc（sizeof（LNode））;
if（p==NULL）
returnNULL;
else
{
p->next=（LNode*）malloc（sizeof（LNode））;
if（p->next==NULL）
returnNULL;
p->data=（xx:
y;
p->next->data=（x>y）?
x:
y;
p->next->next=NULL;
}
returnp;
}
/**********
【题目】试写一算法，实现顺序栈的判空操作
StackEmpty_Sq（SqStackS）。
顺序栈的类型定义为：
typedefstruct{
ElemType*elem;//存储空间的基址
inttop;//栈顶元素的下一个位置，简称栈顶位标
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack;//顺序栈
***********/
StatusStackEmpty_Sq（SqStackS）
/*对顺序栈S判空。
*/
/*若S是空栈，则返回TRUE；否则返回FALSE*/
{
if（S.top==0）
returnTRUE;
returnFALSE;
}
/**********
【题目】试写一算法，实现顺序栈的取栈顶元素操作
GetTop_Sq（SqStackS,ElemType&e）。
顺序栈的类型定义为：
typedefstruct{
ElemType*elem;//存储空间的基址
inttop;//栈顶元素的下一个位置，简称栈顶位标
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack;//顺序栈
***********/
StatusGetTop_Sq（SqStackS,ElemType&e）
/*取顺序栈S的栈顶元素到e，并返回OK；*/
/*若失败，则返回ERROR。
*/
{
if（S.top==0）
returnERROR;
e=S.elem[S.top-1];
returnOK;
}
/**********
【题目】试写一算法，实现顺序栈的出栈操作
Pop_Sq（SqStack&S,ElemType&e）。
顺序栈的类型定义为：
typedefstruct{
ElemType*elem;//存储空间的基址
inttop;//栈顶元素的下一个位置，简称栈顶位标
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack;//顺序栈
***********/
StatusPop_Sq（SqStack&S,ElemType&e）
/*顺序栈S的栈顶元素出栈到e，并返回OK；*/
/*若失败，则返回ERROR。
*/
{
if（S.top==0）
returnERROR;
e=S.elem[--S.top];
returnOK;
}
/**********
【题目】若顺序栈的类型重新定义如下。
试编写算法，
构建初始容量和扩容增量分别为size和inc的空顺序栈S。
typedefstruct{
ElemType*elem;//存储空间的基址
ElemType*top;//栈顶元素的下一个位置
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack2;
***********/
StatusInitStack_Sq2（SqStack2&S,intsize,intinc）
/*构建初始容量和扩容增量分别为size和inc的空顺序栈S。
*/
/*若成功，则返回OK；否则返回ERROR。
*/
{
S.elem=（ElemType*）malloc（sizeof（ElemType））;
if（S.elem==NULL||size<=0||inc<=0）
returnERROR;
S.top=S.elem;
S.size=size;
S.increment=inc;
returnOK;
}
/**********
【题目】若顺序栈的类型重新定义如下。
试编写算法，
实现顺序栈的判空操作。
typedefstruct{
ElemType*elem;//存储空间的基址
ElemType*top;//栈顶元素的下一个位置
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack2;
***********/
StatusStackEmpty_Sq2（SqStack2S）
/*对顺序栈S判空。
*/
/*若S是空栈，则返回TRUE；否则返回FALSE*/
{
if（S.top==S.elem）
returnTRUE;
returnFALSE;
}
/**********
【题目】若顺序栈的类型重新定义如下。
试编写算法，
实现顺序栈的入栈操作。
typedefstruct{
ElemType*elem;//存储空间的基址
ElemType*top;//栈顶元素的下一个位置
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack2;
***********/
StatusPush_Sq2（SqStack2&S,ElemTypee）
/*若顺序栈S是满的，则扩容，若失败则返回ERROR。
*/
/*将e压入S，返回OK。
*/
{
ElemType*p;
if（S.top-S.elem>S.size）
{
p=（ElemType*）realloc（S.elem,（S.size+S.increment）*sizeof（ElemType））;
if（p==NULL）
returnERROR;
S.elem=p;
S.size+=S.increment;
}
*（S.top++）=e;
returnOK;
}
/**********
【题目】若顺序栈的类型重新定义如下。
试编写算法，
实现顺序栈的出栈操作。
typedefstruct{
ElemType*elem;//存储空间的基址
ElemType*top;//栈顶元素的下一个位置
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack2;
***********/
StatusPop_Sq2（SqStack2&S,ElemType&e）
/*若顺序栈S是空的，则返回ERROR；*/
/*否则将S的栈顶元素出栈到e，返回OK。
*/
{
if（S.elem==S.top）
returnERROR;
e=*（--S.top）;
returnOK;
}
/**********
【题目】试写一算法，借助辅助栈，复制顺序栈S1得到S2。
顺序栈的类型定义为：
typedefstruct{
ElemType*elem;//存储空间的基址
inttop;//栈顶元素的下一个位置，简称栈顶位标
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack;//顺序栈
可调用顺序栈接口中下列函数：
StatusInitStack_Sq（SqStack&S,intsize,intinc）;//初始化顺序栈S
StatusDestroyStack_Sq（SqStack&S）;//销毁顺序栈S
StatusStackEmpty_Sq（SqStackS）;//栈S判空，若空则返回TRUE，否则FALSE
StatusPush_Sq（SqStack&S,ElemTypee）;//将元素e压入栈S
StatusPop_Sq（SqStack&S,ElemType&e）;//栈S的栈顶元素出栈到e
***********/
StatusCopyStack_Sq（SqStackS1,SqStack&S2）
/*借助辅助栈，复制顺序栈S1得到S2。
*/
/*若复制成功，则返回TRUE；否则FALSE。
*/
{
if（StackEmpty_Sq（S1））
{
S2.top=0;
returnTRUE;
}
S2.elem=S1.elem;
S2.top=S1.top;
returnTRUE;
}
/**********
【题目】试写一算法，求循环队列的长度。
循环队列的类型定义为：
typedefstruct{
ElemType*base;//存储空间的基址
intfront;//队头位标
intrear;//队尾位标，指示队尾元素的下一位置
intmaxSize;//最大长度
}SqQueue;
***********/
intQueueLength_Sq（SqQueueQ）
/*返回队列Q中元素个数，即队列的长度。
*/
{
if（Q.rear-Q.front<0）
returnQ.maxSize-Q.front+Q.rear;
returnQ.rear-Q.front;
}
/**********
【题目】如果希望循环队列中的元素都能得到利用，
则可设置一个标志域tag，并以tag值为0或1来区分尾
指针和头指针值相同时的队列状态是"空"还是"满"。
试编写与此结构相应的入队列和出队列的算法。
本题的循环队列CTagQueue的类型定义如下：
typedefstruct{
ElemTypeelem[MAXQSIZE];
inttag;
intfront;
intrear;
}CTagQueue;
**********/
StatusEnCQueue（CTagQueue&Q,ElemTypex）
/*将元素x加入队列Q，并返回OK；*/
/*若失败，则返回ERROR。
*/
{
if（Q.front==Q.rear&&Q.tag==1）
returnERROR;
if（Q.rear==0）
{
Q.elem[0]=x;
Q.rear+=1;
}
else
{
Q.elem[Q.rear]=x;
Q.rear=（Q.rear+1）%MAXQSIZE;
}
Q.tag=1;
returnOK;
}
StatusDeCQueue（CTagQueue&Q,ElemType&x）
/*将队列Q的队头元素退队到x，并返回OK；*/
/*若失败，则返回ERROR。
*/
{
if（Q.front==Q.rear&&Q.tag==0）
returnERROR;
x=Q.elem[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
Q.tag=0;
returnOK;
}
/**********
【题目】假设将循环队列定义为：
以域变量rear
和length分别指示
升级会员 