S.elem[i]=*a;
returnOK;
}
}
2-21
/**********
【题目】链表的结点和指针类型定义如下
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
试写一函数，构建一个值为x的结点。
***********/
LinkListMakeNode（ElemTypex）
/*构建一个值为x的结点，并返回其指针。
*/
/*若构建失败，则返回NULL。
*/
{
LNodetemp={x,null};
LNode*node=&temp;
returnnode;
}
2-23
/**********
【题目】链表的结点和指针类型定义如下
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
试写一函数，构建长度为2且两个结点的值依次为x和y的链表。
**********/
LinkListCreateLinkList（ElemTypex,ElemTypey）
/*构建其两个结点的值依次为x和y的链表。
*/
/*若构建失败，则返回NULL。
*/
{
LNodenode2={y,null},node1={x,&node2};
LinkListlist=&node1;
returnlist;
}
2-25
/**********
【题目】链表的结点和指针类型定义如下
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
试写一函数，构建长度为2的升序链表，两个结点的值
分别为x和y，但应小的在前，大的在后。
**********/
LinkListCreateOrdLList（ElemTypex,ElemTypey）
/*构建长度为2的升序链表。
*/
/*若构建失败，则返回NULL。
*/
{
LNodenode2={x<=y?
y:
x,null};
LNodenode1={x<=y?
x:
y,&node2};
LinkListlist=&node1;
returnlist;
}
3-3
/**********
【题目】试写一算法，实现顺序栈的判空操作
StackEmpty_Sq（SqStackS）。
顺序栈的类型定义为：
typedefstruct{
ElemType*elem;//存储空间的基址
inttop;//栈顶元素的下一个位置，简称栈顶位标
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack;//顺序栈
***********/
StatusStackEmpty_Sq（SqStackS）
/*对顺序栈S判空。
*/
/*若S是空栈，则返回TRUE；否则返回FALSE*/
{
if（!
*S.elem）
returnTRUE;
else
returnFALSE;
}
3-5
/**********
【题目】试写一算法，实现顺序栈的取栈顶元素操作
GetTop_Sq（SqStackS,ElemType&e）。
顺序栈的类型定义为：
typedefstruct{
ElemType*elem;//存储空间的基址
inttop;//栈顶元素的下一个位置，简称栈顶位标
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack;//顺序栈
***********/
StatusGetTop_Sq（SqStackS,ElemType&e）
/*取顺序栈S的栈顶元素到e，并返回OK；*/
/*若失败，则返回ERROR。
*/
{
if（!
*S.elem）
returnERROR;
else
{
e=*（S.elem+S.top-1）;
returnOK;
}
}
3-7
/**********
【题目】试写一算法，实现顺序栈的出栈操作
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.elem）
returnERROR;
else
{
e=*（S.elem+S.top-1）;
--S.top;
returnOK;
}
}
3-11
/**********
【题目】若顺序栈的类型重新定义如下。
试编写算法，
构建初始容量和扩容增量分别为size和inc的空顺序栈S。
typedefstruct{
ElemType*elem;//存储空间的基址
ElemType*top;//栈顶元素的下一个位置
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack2;
**********/
StatusInitStack_Sq2（SqStack2&S,intsize,intinc）
/*构建初始容量和扩容增量分别为size和inc的空顺序栈S。
*/
/*若成功，则返回OK；否则返回ERROR。
*/
{
if（size<=0||inc<=0）
returnERROR;
else
{
S.top=++S.elem;
S.size=size;
S.increment=inc;
returnOK;
}
}
3-13
/**********
【题目】若顺序栈的类型重新定义如下。
试编写算法，
实现顺序栈的判空操作。
typedefstruct{
ElemType*elem;//存储空间的基址
ElemType*top;//栈顶元素的下一个位置
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack2;
***********/
StatusStackEmpty_Sq2（SqStack2S）
/*对顺序栈S判空。
*/
/*若S是空栈，则返回TRUE；否则返回FALSE*/
{
if（!
*S.elem）
returnTRUE;
returnFALSE;
}
3-15
/**********
【题目】若顺序栈的类型重新定义如下。
试编写算法，
实现顺序栈的入栈操作。
typedefstruct{
ElemType*elem;//存储空间的基址
ElemType*top;//栈顶元素的下一个位置
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack2;
***********/
StatusPush_Sq2（SqStack2&S,ElemTypee）
/*若顺序栈S是满的，则扩容，若失败则返回ERROR。
*/
/*将e压入S，返回OK。
*/
{
if（S.top-S.elem>=S.size）
{
S.size+=S.increment;
}
*S.top=e;
++S.top;
returnOK;
}
3-17
/**********
【题目】若顺序栈的类型重新定义如下。
试编写算法，
实现顺序栈的出栈操作。
typedefstruct{
ElemType*elem;//存储空间的基址
ElemType*top;//栈顶元素的下一个位置
intsize;//当前分配的存储容量
intincrement;//扩容时，增加的存储容量
}SqStack2;
***********/
StatusPop_Sq2（SqStack2&S,ElemType&e）
/*若顺序栈S是空的，则返回ERROR；*/
/*否则将S的栈顶元素出栈到e，返回OK。
*/
{
if（!
*（S.top-1））
returnERROR;
else
{
e=*（S.top-1）;
--S.top;
returnOK;
}
}
3-22
/**********
【题目】试写一算法，借助辅助栈，复制顺序栈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。
*/
{
ElemTypetemp;
SqStackS3;
InitStack_Sq（S2,S1.size,S1.increment）;
InitStack_Sq（S3,S1.size,S1.increment）;
while（!
StackEmpty_Sq（S1））
{
Pop_Sq（S1,temp）;
Push_Sq（S3,temp）;
}
while（!
StackEmpty_Sq（S3））
{
Pop_Sq（S3,temp）;
Push_Sq（S2,temp）;
}
DestroyStack_Sq（S3）;
returnTRUE;
}
3-33
/**********
【题目】试写一算法，求循环队列的长度。
循环队列的类型定义为：
typedefstruct{
ElemType*base;//存储空间的基址
intfront; //队头位标
intrear; //队尾位标，指示队尾元素的下一位置
intmaxSize;//最大长度
}SqQueue;
***********/
intQueueLength_Sq（SqQueueQ）
/*返回队列Q中元素个数，即队列的长度。
*/
{
return（Q.rear-Q.front+Q.maxSize）%Q.maxSize;
}
3-35
/**********
【题目】如果希望循环队列中的元素都能得到利用，
则可设置一个标志域tag，并以tag值为0或1来区分尾
指针和头指针值相同时的队列状态是"空"还是"满"。
试编写与此结构相应的入队列和出队列的算法。
本题的循环队列CTagQueue的类型定义如下：
typedefstruct{
ElemTypeelem[MAXQSIZE];
inttag;
intfront;
intrear;
}CTagQueue;
**********/
StatusEnCQueue（CTagQueue&Q,ElemTypex）
/*将元素x加入队列Q，并返回OK；*/
/*若失败，则返回ERROR。
*/
{
if（（Q.rear+MAXSIZE-Q.front）%MAXSIZE）
Q.elem[Q.rear++%MAXSIZE]=x;
else
{
if（Q.tag==0）
Q.elem[Q.rear++%MAXSIZE]=x;
else
returnERROR;
}
if（（Q.rear+MAXSIZE-Q.front）%MAXSIZE==0）
Q.tag=1;
returnOK;
}
StatusDeCQueue（CTagQueue&Q,ElemType&x）
/*将队列Q的队头元素退队到x，并返回OK；*/
/*若失败，则返回ERROR。
*/
{
if（（Q.rear+MAXSIZE-Q.front）%MAXSIZE）
x=Q.elem[Q.front++%MAXSIZE];
else
{
if（Q.tag==1）
x=Q.elem[Q.front++%MAXSIZE];
else
returnERROR;
}
if（（Q.rear+MAXSIZE-Q.front）%MAXSIZE==0）
Q.tag=0;
returnOK;
}
3-37
/**********
【题目】假设将循环队列定义为：
以域变量rear
和length分别指示循环队列中队尾元素的位置和内
含元素的个数。
试给出此循环队列的队满条件，并
写出相应的入队列和出队列的算法（在出队列的算
法中要返回队头元素）。
本题的循环队列CLenQueue的类型定义如下：
typedefstruct{
ElemTypeelem[MAXQSIZE];
intlength;
intrear;
}CLenQueue;
**********/
Status
升级会员 