[Algorithm]栈和队列

一.栈和队列综合(算法)

1.判断单链表(带头结点)的结点值(字符型)是否中心对称

 1 bool IsSymmetry( LinkList& L )

 2 {

 3     char S[MAXSIZE];

 4     int top = -1, len = 0, i;

 5     LinkList p;

 6     p = L->next;

 7     while ( p ) { p = p->next; len++; }

 8     p = L->next;

 9     for (i=0;i<len/2;i++)

10     {

11         S[++top] = p->data;

12         p = p->next;

13     }

14     i--;

15     if ( len % 2 )

16         p = p->next;

17     while ( top != -1 )

18     {

19         if ( p->data != S[top] )

20             return false;

21         top--;

22         p = p->next;

23     }

24     return true;

25 }

2.共享栈由两个顺序栈S1,S2构成,总大小为100,请设计S1,S2入栈,出栈的算法

 1 #define MAXSIZE 100

 2 ElemType S[MAXSIZE];

 3 int top[2] = { -1,MAXSIZE };

 4 bool Push( int i, ElemType x )

 5 {

 6     if ( i < 0 || i>1 || top[1] - top[0] == 1 )

 7         return false;

 8     if ( i == 0 ) S[++top[0]] = x;

 9     else S[--top[1]] = x;

10     return true;

11 }

12

13 bool Pop( int i, ElemType x )

14 {

15     if ( i < 0 || i>1

16          || ( i == 0 && top[0] == -1 )

17          || ( i == 1 && top[1] == MAXSIZE ) )

18         return false;

19     if ( i == 0 ) x = S[top[0]--];

20     else x = S[top[1]++];

21     return true;

22 }

3.如果希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0或1来区分队头指针front和队尾rear相同时的队列状态是"空"还是"满",编写与此结构相应的入队和出队算法

 1 ElemType Q[MAXSIZE];

 2 int front = -1, rear = -1;

 3 // 队空条件:    front==rear&&tag==0

 4 // 队满条件:    front==rear&&tag==1

 5 // 进队操作:    rear=(rear+1)%MAXSIZE;

 6 //            Q[rear]=x;

 7 //            tag=1;

 8 // 出队操作:    front=(front+1)%MAXSIZE;

 9 //            x=Q[front];

10 //            tag=0;

11

12 // 1)"tag"法循环队列入队算法

13 bool EnQueue( ElemType x )

14 {

15     if ( front == rear && tag == 1 )

16         return false;

17     rear = ( rear + 1 ) % MAXSIZE;

18     Q[rear] = x;

19     tag = 1;

20     return true;

21 }

22

23 // 2)"tag"法循环队列出队算法

24 bool DeQueue( ElemType& x )

25 {

26     if ( front == rear && tag == 0 )

27         return false;

28     front = ( front + 1 ) % MAXSIZE;

29     x = Q[front];

30     tag = 0;

31     return true;

32 }

4.Q是一个队列,S是一个空栈,实现将队列中的元素逆置的算法

 1 ElemType S[MAXSIZE], Q[MAXSIZE];

 2 int top = -1, front = -1, rear = -1;

 3 void Inverse(ElemType S[], ElemType Q[])

 4 {

 5     ElemType x;

 6     while ( front != rear )

 7     {

 8         x = Q[++front];

 9         S[++top] = x;

10     }

11     while ( top != -1 )

12     {

13         x = S[top--];

14         Q[++rear] = x;

15     }

16 }

5.利用两个栈S1,S2模拟一个队列,已知栈的4个运算如下:

 1 // 已知:

 2 void Push(Stack& S, ElemType x);

 3 void Pop(Stack& S, ElemType& x)

 4 bool IsEmpty(Stack& S);

 5 bool IsOverflow( Stack& S );

 6

 7 bool EnQueue( Stack& S1, Stack& S2, ElemType x )

 8 {

 9     if ( !IsOverflow( S1 ) )

10     {

11         Push( S1, x );

12         return true;

13     }

14     if ( !IsEmpty( S2 ) )

15         return false;

16     while (!IsEmpty(S1))

17     {

18         Pop( S1, t );

19         Push( S2, t );

20     }

21     Push( S1, x );

22     return true;

23 }

24

25 bool DeQueue( Stack& S1, Stack& S2, ElemType& x )

26 {

27     if (!IsEmpty(S2))

28     {

29         Pop( S2, x ); return true;

30     }

31     if ( IsEmpty( S1 ) )

32         return false;

33     while (!IsEmpty(S1))

34     {

35         Pop( S1, t );

36         Push( S2, t );

37     }

38     Pop( S2, x );

39     return true;

40 }

41

42 bool IsEmpty( Stack& S1, Stack& S2 )

43 {

44     if ( IsEmpty( S1 ) && IsEmpty( S2 ) )

45         return true;

46     return false;

47 }

6.括号匹配问题:判别表达式中括号是否匹配(只含有$(),[],\{\}$)

 1 bool IsBracketMatch( char*str )

 2 {

 3     char S[MAXSIZE];

 4     int top = -1;

 5     for ( int i = 0; str[i]; i++ )

 6     {

 7         char c = str[i];

 8         switch ( c )

 9         {

10         case '(':

11         case '[':

12         case '{':

13             S[++top] = c;

14             break;

15         case ')':

16             c = S[top--];

17             if ( c != '(' )return false;

18             break;

19         case ']':

20             c = S[top--];

21             if ( c != '[' )return false;

22             break;

23         case '}':

24             c = S[top--];

25             if ( c != '{' )return false;

26             break;

27         default:

28             break;

29         }

30     }

31     return top == -1;

32 }

7.利用栈实现以下递归函数的非递归计算:

$$P_{n}(x)=
\cases{
1 & n=0\cr
2x & n=1\cr
2x\cdot{P_{n-1}(x)}-2(n-1)\cdot{P_{n-2}(x)} & n>1
}$$

 1 double P( int n, double x )

 2 {

 3     struct Stack

 4     {

 5         int n;        // 层

 6         double val;    // 数值结果

 7     }S[MAXSIZE];

 8     int top = -1, fv1 = 1, fv2 = 2 * x;

 9     for ( int i = n; i > 1; i-- )

10         S[++top].n = i;

11     while ( top != -1 )

12     {

13         S[top].val = 2 * x*fv2 - 2 * ( S[top].n - 1 )*fv1;

14         fv1 = fv2;

15         fv2 = S[top--].val;

16     }

17     if ( n == 0 ) return fv1;

18     return fv2;

19 }

巴特西

[Algorithm]栈和队列

最新文章

热门文章