循環左移數組

1.        算法要求

設将n(n>1)個整數存放到一維數組R中，試設計一個在時間和空間兩方面盡可能有效的算法，将R中保有的序列循環左移P（0﹤P﹤n）個位置，即将R中的資料由（X0 X1 ……Xn-1）變換為（Xp Xp+1 ……Xn-1  X0  X1 ……Xp-1）。

2.        算法思想

考慮使用隊列來實作，将隊列前面p個元素依次出隊列，再從隊尾部依次進隊列，即可實作該算法。使用資料結構：

[cpp]  view plain copy

1. typedef struct qnode{  
2.     elemtype        *base;  
3.     int         front;  
4.     int         rear;  
5. }sqqueue;  

3.        算法實作

[cpp]  view plain copy

1. int in_sqqueue(sqqueue *sq, elemtype e)  
2. {  
3.     if ((sq->rear + 1) % MAXQSIZE == sq->front)  
4.         return ERROR;  
5.     sq->base[sq->rear] = e;  
6.     sq->rear = (sq->rear + 1) % MAXQSIZE;  
7.     return OK;  
8. }  

[cpp]  view plain copy

1. int out_sqqueue(sqqueue *sq, elemtype *e)  
2. {  
3.     if (sq->front == sq->rear)  
4.         return NULL_QUEUE;  
5.     *e = sq->base[sq->front];  
6.     sq->front = (sq->front + 1) % MAXQSIZE;  
7.     return OK;  
8. }  

[cpp]  view plain copy

1. void circle_left_shift_queue(sqqueue *sq, int n)  
2. {  
3.     int         i;  
4.     elemtype        e;  
5.     for (i=0; i<n; ++i) {  
6.         out_sqqueue(sq, &e);      
7.         in_sqqueue(sq, e);        
8.     }  
9. }  

算法實作源碼： http://download.csdn.net/detail/algorithm_only/3892452