循环行列的元素倒置。求指点

循环队列的元素倒置。求指点。
本帖最后由 whdugh 于 2013-01-30 12:29:48 编辑 编写一个算法，将一个循环队列（容量为n，元素下标从1~n）的元素倒置。

/*
算法思想: 使用一个栈起到过渡作用。先将sq队列中元素出队并将其入栈ss，直到队列空为止；
然后初始化队列，将sq->front=sq->rear=n;再出栈并将其入队列，直到栈空为止。
*/void Reverse(SqQuene *sq)
{
    ELEMTYPE x;
    SqStack *ss;
    ss = (SqStack *)malloc(sizeof(SqStack)); //栈初始化
    ss->top = -1;
    while(sq->front != sq->rear)             //队不空时，出队并入栈
    {
        sq->front = (sq->front + 1) % MAXSIZE;
        if(sq->front == 0)                    //队列元素下标从1到n
            sq->front = n;   //dgh  n 这里是什么意思  front和rear 指向的位置变化了?
        x = sq->data[sq->front];
        ss->top++;
        ss->data[ss->top] = x;                //将x入栈
    }                                         /*sq栈中从栈顶到栈底的元素为f,e,d,c,b,a*/
    sq->front = sq->rear = n;                 /*队列初始化 为何初始化为n*/  ?
    while(ss->top >= 0)                       /*栈不空时，出栈并将元素入队 */
    {
        x = ss->data[ss->top];
        ss->top--;
        sq->rear = (sq->rear + 1) % n;
        sq->data[sq->rear] = x;
    }
}

有两个问题：1.为什么要在第一个循环里面加if判断语句 if(sq->front==0),然后赋为n？
2.将sq->front=sq->rear=n，这又是为何？菜鸟刚自学数据结构 求高手指点 谢谢
循环队列
[解决办法]
这个程序应该有一个隐含条件：
第一个while循环之前，应该是sq->front = 0; sq->rear = n;
楼主的问题：
1. sq->front = (sq->front + 1) % MAXSIZE;这句的含义就是队头指针顺序后移，直到队尾
MAXSIZE应该是n，那么当sq->front = n - 1的时候，经过这句赋值，sq->front就成了0， 而此时
n - 1的下一个元素应该是n；所以有下面的if判断语句。
2. 经过上一个循环，实际上已经满足sq->front=sq->rear=n，所以此处是多此一举。
这句的作用是为后面把栈中的元素弹出到原队列中作初始化，为n是因为循环中会先进行下标移动，再进行数据处理, (n + 1) % n 就是 1 了。
整个程序就是利用了栈先入后出的性质实现逆序。
个人认为程序改为这样比较合适：

/*
算法思想: 使用一个栈起到过渡作用。先将sq队列中元素出队并将其入栈ss，直到队列空为止；
然后初始化队列，将sq->front=sq->rear=n;再出栈并将其入队列，直到栈空为止。
*/void Reverse(SqQuene *sq)
{
    ELEMTYPE x;
    SqStack *ss; 
 
    ss = (SqStack *)malloc(sizeof(SqStack)); //栈初始化
    ss->top = -1;
    sq ->front = 0;
    sq->rear = n; //如果程序外已经满足次条件，这两句也可以省去
    while(sq->front != sq->rear)             //队不空时，出队并入栈
    {
        sq->front = (sq->front + 1) % MAXSIZE;
        if(sq->front == 0)                    //队列元素下标从1到n
            sq->front = n;
        x = sq->data[sq->front];
        ss->top++;
        ss->data[ss->top] = x;                //将x入栈
    }                                         /*sq栈中从栈顶到栈底的元素为f,e,d,c,b,a*/
    //这里删除了一句
    while(ss->top >= 0)                       /*栈不空时，出栈并将元素入队 */
    {
        x = ss->data[ss->top];
        ss->top--;
        sq->rear = (sq->rear + 1) % n;
        sq->data[sq->rear] = x;
    }
}

查看更多 下一篇