（*A）.data[m++]=（*A）.data[i++];/*需保留的元素移动到新位置*/
while（i<（*A）.length&&（*A）.data[i]==same）i++;/*跳过相同的元素*/
}
}/*while*/
while（i<（*A）.length）
（*A）.data[m++]=（*A）.data[i++];/*A的剩余元素重新存储*/
（*A）.length=m;
}/*SqList_Intersect_Delete*/
习题3
1．
参考答案：
栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。
最后插入的元素最先删除，故栈也称后进先出表。
队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。
最先插入队的元素最先离开（删除），故队列也常称先进先出表。
2．
参考答案：
输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素4356得到后，栈中元素剩余12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。
得到135426的过程如下：
1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
3．
参考答案：
设顺序队列用一维数组Q[m]表示，其中m为队列中元素个数，队列中的元素下标从0到m﹣1。
设队头指针为front，队尾指针是rear，约定front指向队头元素，rear指向队尾元素的下一位置。
当front=rear=0时，表示队空，当rear=m﹣1时，表示队满。
由于队列的性质，在队头进行出队操作，而在队尾进行入队操作，所以当队尾指针rear=m﹣1时，若front不为0，则队列中仍有空闲单元，即队列的实际可用空间并未占满，这时若有入队操作，会造成“假溢出”。
解决“假溢出”的办法有两种，一是将队列元素向前“平移”，占用0至rear-front-1号单元；二是将队列看成一个首尾相接的环状空间，即循环队列。
在循环队列下，当front=rear时，仍表示队空，而表示队满，则有两种办法，一是牺牲一个单元，即（rear+1）%m=front时，表示队满。
另一种方法是设一个标志tag，若tag=0且front=rear时，表示队空；若tag=1且front=rear时，表示队满。
4．
算法代码：
voidEnQueue（LinkListrear,ElemTypex）
{/*rear是带头结点的循环链队列的尾指针,本算法将元素x插入到队尾*/
LinkLists;
s=（LinkList）malloc（sizeof（LNode））;/*申请结点空间*/
s->data=x;
s->next=rear->next;/*将s结点链入队尾*/
rear->next=s;
rear=s;/*rear指向新队尾*/
}
voidDeQueue（LinkListrear）
{/*rear是带头结点的循环链队列的尾指针,本算法执行出队操作,操作成功输出队头元素;否则给出出错信息*/
LinkLists;
if（rear->next==rear）{printf（"队空\n"）;return;}
s=rear->next->next;/*s指向队头元素*/
rear->next->next=s->next;/*队头元素出队*/
printf（"出队元素是:
%d",s->data）;
if（s==rear）rear=rear->next;/*空队列*/
free（s）;
}
5．
算法代码：
intMaxValue（inta[],intn）
{/*设整数序列存于数组a中,共有n个,本算法求解其最大值*/
intmax;
if（n==1）max=a[1];
elseif（a[n]>MaxValue（a,n-1））max=a[n];
elsemax=MaxValue（a,n-1）;
return（max）;
}
6．
算法代码：
voidconversion（intN）{
SqStacks;
intx;
Init_SqStack（&s）;
if（N<0）return;
while（N）{
Push_SqStack（&s,N%16）;/*余数入栈*/
N=N/16;/*商作为被除数继续*/
}
while（!
Empty_SqStack（&s））
{
x=Pop_SqStack（&s）;
if（x>=10）
printf（"%c",'A'+x-10）;
else
printf（"%d",x）;
}
}
7．
算法代码：
voidreverse（SqStack*s）{
SqStacks1,s2;/*s,s1,s2均为栈类型*/
ElemTypex;/*栈中元素的类型,用于存储从栈中取出元素的临时变量*/
Init_Stack（&s1）;/*栈的初始化*/
Init_Stack（&s2）;
while（!
Empty_Stack（s））/*如果栈不空,将s栈中的内容移到s1栈中*/
{
x=Pop_Stack（s）;/*取栈顶元素放入变量x中*/
Push_Stack（&s1,x）;/*将变量x入栈*/
}
while（!
Empty_Stack（&s1））/*如果栈不空,将s1栈中的内容移到s2栈中*/
{
x=Pop_Stack（&s1）;
Push_Stack（&s2,x）;
}
while（!
Empty_Stack（&s2））/*如果栈不空,将s2栈中的内容移到s栈中*/
{
x=Pop_Stack（&s2）;
Push_Stack（s,x）;
}
}
8．
算法代码：
#defineMAXSIZE100/*最大队列长度*/
typedefintElemType;
typedefstruct{
ElemTypedata[MAXSIZE];/*队列存储空间*/
intrear;/*尾指针,若队列不空,指向队列尾元素*/
intlength;/*队列中元素的个数*/
}CyQueue;
intFullQueue（CyQueue*Q）{/*判队满,队中元素个数等于空间大小*/
returnQ->length==MAXSIZE;
}
voidEnQueue（CyQueue*Q,ElemTypex）{/*入队*/
if（FullQueue（Q））{printf（"队已满,无法入队"）;return;}
Q->data[Q->rear]=x;
Q->rear=（Q->rear+1）%MAXSIZE;/*在循环意义上的加1*/
Q->length++;
}
ElemTypeDeQueue（CyQueue*Q）{/*出队*/
intfront;/*设一个临时队头指针*/
if（Q->length==0）
printf（"队已空,无元素可出队"）;
front=（Q->rear+MAXSIZE-Q->length）%MAXSIZE;
Q->length--;
returnQ->data[front];
}
9．
算法代码：
voidInitStack（DuStack*S）/*初始化双向栈*/
{
S->top[0]=-1;
S->top[1]=STACKSIZE;
}
intEmptyStack（DuStack*S,inti）/*判栈空（栈号i）*/
{return（i==0&&S->top[0]==-1||i==1&&S->top[1]==STACKSIZE）;}
intFullStack（DuStack*S）/*判栈满*/
{return（S->top[0]==S->top[1]-1）;}
voidPush（DuStack*S,inti,ElemTypex）/*进栈（栈号i）*/
{
if（FullStack（S））/*若上溢,则退出*/
printf（"Stackoverflow"）;
if（i==0）S->data[++S->top[0]]=x;/*栈0入栈*/
if（i==1）S->data[--S->top[1]]=x;/*栈1入栈*/
}
ElemTypePop（DuStack*S,inti）/*出栈（栈号i）*/
{
if（EmptyStack（S,i））/*若下溢,则退出*/
printf（"Stackunderflow"）;
if（i==0）
return（S->data[S->top[0]--]）;/*返回栈顶元素,指针值减1*/
if（i==1）
return（S->data[S->top[1]++]）;/*该栈是以另一端为底的,所以指针加1*/
}
10．
算法代码：
voidsympthy（LinkListhead,intn,SqStack*s）/*长度为n的字符串存于单链表head中*/
{
inti=1;
LinkListp=head->next;
while（i<=n/2）/*前一半字符进栈*/
{
Push_Stack（s,p->data）;
p=p->next;
}
if（n%2!
=0）p=p->next;/*奇数个结点时跳过中心结点*/
while（p&&p->data==Pop_Stack（s））p=p->next;
if（p==NULL）
printf（"链表中心对称"）;
else
printf（"链表不是中心对称"）;
}/*算法结束*/
11．
算法代码：
#defineMAXSIZE100/*最大队列长度*/
typedefintElemType;
typedefstruct{
ElemTypedata[MAXSIZE];/*队列存储空间*/
intfront;/*头指针,若队列不空,指向队列头元素*/
intrear;/*尾指针,若队列不空,指向队列尾元素的下一个位置*/
inttag;
}CyQueue;
voidenqueue（CyQueue*Q,ElemTypex）
{/*将x插入循环队列Q中,Q具有队头和队尾指针*/
if（（Q->tag==1）&&（Q->rear==Q->front））/*判断队满*/
printf（"queueisfull!
\n"）;
else
{
Q->data[Q->rear]=x;
Q->rear=（Q->rear+1）%MAXSIZE;
}
if（Q->front==Q->rear）Q->tag=1;
}
ElemTypedequeue（CyQueue*Q）/*删除队列Q的队头元素,并返回该元素*/
{
ElemTypex;
if（（Q->tag==0）&&（Q->rear==Q->front））
printf（"queueisempty!
\n"）;/*判断队空*/
else
{
Q->front=（Q->front+1）%MAXSIZE;
x=Q->data[Q->front];
}
if（Q->front==Q->rear）Q->tag=0;
returnx;
}
习题4
1．
参考答案：
空格是一个字符，其ASCII码值是32。
空格串是由空格组成的串，其长度等于空格的个数。
空串是不含任何字符的串，即空串的长度是零。
2．
参考答案：
设数组元素A[i][j]存放在起始地址为Loc（i,j）的存储单元中。
Loc（2,2）=Loc（0,0）+2*n+2=644+2*n+2=676
n=（676-2-644）/2=15
Loc（3,3）=Loc（0,0）+3*15+3=644+45+3=692
3．
参考答案：
（1）数组B共有1＋2+3++n=（n+1）*n/2个元素。
（2）只存下三角部分时，若i≥j，则数组元素A[i][j]前面有i﹣1行（1～i﹣1），第1行有1个元素，第2行有2个元素，，第i﹣1行有i﹣1个元素。
在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为：
1+2++（i﹣1）+j=（i﹣1）*i/
升级会员 