LNode *head,*front; head= rear->next;
if (head== rear) /*队列为空,出队列操作失败*/ return 0;
front =head->next; /*队列头结点为循环链表头结点后一个结点*/ data= front ->data; head->next= front ->next; if (front ==rear)/*队列中只有一个结点,则释放后,将为空,所以让队尾指针指向头结点*/ rear= head; free front; /*释放队列头结点*/ return 1; }
5. 分析：该题目主要考查栈的应用。假定表达式存放在字符串数组str中，对表达式字符进行扫描，遇到左括号则进栈，遇到右括号则判栈是否空；若空，说明圆括号不配对，若不空则出栈，最后，若栈空，说明圆括号配对，否则不配对。 算法描述如下：
void pair(char str[ ]) { PSeqStack S; char ch ,ch1;
int k=0 ;
S=Init_SeqStack( );
while( ( ch=str[k])!= ′\\0 ′) /*扫描表达式，直到′\\0 ′结束*/
{ if (ch= =′( ′) Push_SeqStack(S,ch); else if(ch==′)′)
{ if (Empty_SeqStack (S))
{ printf(“圆括号不配对”)； return; }
else Pop_SeqStack(S,&ch1)； /*栈顶的左括号出栈*/ } k++;
}
if (Empty_SeqStack(S)) printf(“圆括号配对”); else printf(“圆括号不配对”); }
6. 分析：设置两个指针分别指向两个栈顶。push(i,x)，i等于0时，指针要加1，而i等于1时，指针要减1；pop(i)，i等于0时，指针要减1，而i等于1时，指针要加1。另外，要注意判空和判满。 算法描述如下： #define m 100 typedef struct {
int v[m]; /*两个栈共用的连续存储区域*/ int top0, top1; /*分别为两个栈的栈顶位置*/ }BSeqStack, *PBSeqStack;
BSeqStack S;
int push(int i, int x)
{ if (S.top0+1= = S.top1) /*栈满不能入栈*/
return 0; /* 入栈失败 */ else
{ if (i==0) /*0号栈入栈*/
{ S.top0++; /*0号栈顶位置加1*/ S.v[S.top0]=x;
return 1; /* 入栈成功 */
}else if (i==1) /*1号栈入栈*/
{ S.top1--; /*1号栈顶位置减1*/
S.v[S.top1]=x;
return 1; /* 入栈成功 */
}
} }
int pop(int i)
{ if (i==0) /*0号栈出栈*/
{ if (S.top0= = -1) /*栈空不能出栈*/
{ printf(“栈空不能出栈”);
return 0;
}
else
return S.v[S.top0--]; /*返回栈顶元素，栈顶位置减1*/
}else if (i==1) /*1号栈出栈*/
{ if (S.top1= = m) /*栈空不能出栈*/ { printf(“栈空不能出栈”);
return 0; }
else
return S.v[S.top1++]; /*返回栈顶元素，栈顶位置加1*/
}
}
7. 分析：递归终止条件为只有一个元素时，最大和最小元素就为该元素；或没有元素时，没有最大和最小元素。递归式为GetMaxMin(A(0,..n))=max/min(GetMaxMin (A(n)), GetMaxMin(A(0,..n-1)))。 算法描述如下：
void GetMaxMin(int A[], int n, int &max, int &min) { if (n==0) { /*只有一个元素时，最大和最小元素就为这个元素 */ max=A[0];
min=A[0]; }
else {
/有n+1个元素时,先获得前n个数中的最大元素max,和最小元素min*/
GetMaxMin(A, n-1, max, min);
/*如果第n+1个元素大于max,则这n+1个元素中的最大元素为max*/
if (A[n]>max) max=A[n];
/*如果第n+1个元素小于min,则这n+1个元素中的最小元素为min*/
if (A[n] 8. 分析：(1)这是求最大公因子的辗转相除法。 算法描述如下： int gcd(int m, int n) /*求两个正整数的最大公因子的递归函数*/ { int temp; if (n= =0 ) return m; if (m (2)根据3.2.2判断题第1题，这是一个尾递归函数，消除递归可以不用栈，求解该递归函数gcd (int m,int n)的非递归算法描述如下： int gcd1(int m, int n) /*求两个正整数的最大公因子的非递归函数*/ { int temp; if (m m=n; n=temp; } while (n!=0) { temp=m; m=n; /*除数作为下次运算的被除数*/ n=temp% n; /*余数作为下次运算的除数*/ } return m; }