环形数组逆向遍历

60 阅读 0 评论 40 点赞

我是靠谱客的博主忧伤太阳，最近开发中收集的这篇文章主要介绍环形数组逆向遍历，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

环形数组逆向遍历

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 #define shell_printf_greep(format,...) printf("33[42;37m"format"33[0m",  ##__VA_ARGS__) 
  5 #define shell_printf_red(format,...) printf("33[41;37m"format"33[0m",  ##__VA_ARGS__) 
  6 
  7 typedef struct _latest_pushid{
  8 #define POOL_LATEST_PUSHID_MAX   10
  9     unsigned int is_full; // 是否已完成环形数组的第一遍存储
 10     unsigned int next_index;
 11     unsigned int pushid[POOL_LATEST_PUSHID_MAX];
 12 }latest_pushid_t;
 13 
 14 latest_pushid_t g_latest_pushid = {0};
 15 
 16 
 17 #if 0
 18 /* 
 19    新来一条消息, 查询是否曾经收过该pushid消息, 未收过则将此pushid放入池中
 20    return 1: 曾经收过此pushid消息
 21 0: 未曾收过此pushid消息
 22 */
 23 int is_message_repeat(const unsigned int pushid){
 24     int index = 0;
 25 
 26     int index_begin = (0 >= g_latest_pushid.next_index) ? (POOL_LATEST_PUSHID_MAX - 1) : (g_latest_pushid.next_index - 1);
 27     int index_end = (0 == g_latest_pushid.is_full) ? 0 : g_latest_pushid.next_index;
 28 
 29     //printf("index_begin=%d, index_end=%drn", index_begin, index_end);
 30 
 31     if (0 == g_latest_pushid.is_full && POOL_LATEST_PUSHID_MAX - 1 == index_begin)
 32     {
 33         //        printf("empth arrayrn");
 34     }
 35     else if (1 == g_latest_pushid.is_full && POOL_LATEST_PUSHID_MAX - 1 == index_begin)
 36     {
 37         for (index = POOL_LATEST_PUSHID_MAX - 1; index >=0; index--)
 38         {
 39             //            printf("for index=%drn", index);
 40             if (pushid == g_latest_pushid.pushid[index]){
 41                 return 1;
 42             }
 43         }
 44     }
 45     else
 46     {
 47         int touch_begin = 0;
 48 
 49         for (index = index_begin; (0 == touch_begin) || (1 == touch_begin && index >= index_end); ){
 50             //            printf("for index=%d, touch_begin=%drn", index, touch_begin);
 51             if (pushid == g_latest_pushid.pushid[index]){
 52                 return 1;
 53             }
 54 
 55             if ( 0 == index ){
 56                 touch_begin = 1;
 57             }
 58 
 59             index--;
 60             if (0 > index)
 61             {
 62                 if (0 == g_latest_pushid.is_full)
 63                     break;
 64                 else
 65                     index = POOL_LATEST_PUSHID_MAX - 1;
 66             }
 67 
 68             //            usleep(100 * 1000);
 69 
 70         }
 71     }
 72 
 73     g_latest_pushid.pushid[g_latest_pushid.next_index] = pushid;
 74 
 75     g_latest_pushid.next_index++;
 76 
 77     if(POOL_LATEST_PUSHID_MAX <= g_latest_pushid.next_index){
 78         g_latest_pushid.is_full = 1;
 79     }
 80 
 81     g_latest_pushid.next_index = g_latest_pushid.next_index % POOL_LATEST_PUSHID_MAX;
 82 
 83     return 0;
 84 }
 85 
 86 #elif 1  // 此方法最好
 87 int is_message_repeat(const unsigned int pushid){
 88     int index = 0;
 89     int index_array = 0;
 90 
 91 
 92     int index_max = (0 == g_latest_pushid.is_full) ? g_latest_pushid.next_index : POOL_LATEST_PUSHID_MAX;
 93     for (index = 0; index < index_max; index++){
 94         index_array = (g_latest_pushid.next_index - 1 - index + POOL_LATEST_PUSHID_MAX) % POOL_LATEST_PUSHID_MAX;
 95         printf("for index=%d, index_array=%drn", index, index_array);
 96         if (pushid == g_latest_pushid.pushid[index_array]){
 97             return 1;
 98         }
 99     }
100 
101     g_latest_pushid.pushid[g_latest_pushid.next_index] = pushid;
102 
103     // make the next_index
104     g_latest_pushid.next_index++;
105 
106     if(POOL_LATEST_PUSHID_MAX <= g_latest_pushid.next_index){
107         g_latest_pushid.is_full = 1;
108     }
109 
110     g_latest_pushid.next_index = g_latest_pushid.next_index % POOL_LATEST_PUSHID_MAX;
111 
112     return 0;
113 }
114 #else
115 int is_message_repeat(const unsigned int pushid){
116     int index = 0;
117     int index_array[POOL_LATEST_PUSHID_MAX];
118 
119     for (index = 0; index < POOL_LATEST_PUSHID_MAX; index++){
120         index_array[index] = (g_latest_pushid.next_index - 1 - index + POOL_LATEST_PUSHID_MAX) % POOL_LATEST_PUSHID_MAX;
121     }
122 
123     int end_index_of_index_array = (0 == g_latest_pushid.is_full) ? g_latest_pushid.next_index : POOL_LATEST_PUSHID_MAX;
124     for (index = 0; index < end_index_of_index_array; index++){
125         if (pushid == g_latest_pushid.pushid[index_array[index]]){
126             return 1;
127         }
128     }
129 
130     g_latest_pushid.pushid[g_latest_pushid.next_index] = pushid;
131 
132     // make the next_index
133     g_latest_pushid.next_index++;
134 
135     if(POOL_LATEST_PUSHID_MAX <= g_latest_pushid.next_index){
136         g_latest_pushid.is_full = 1;
137     }
138 
139     g_latest_pushid.next_index = g_latest_pushid.next_index % POOL_LATEST_PUSHID_MAX;
140 
141     return 0;
142 }
143 
144 #endif
145 
146 int print_circle_array(){
147     int index = 0;
148 
149     for (index = 0; index < POOL_LATEST_PUSHID_MAX; index++)
150         printf("%u, ", g_latest_pushid.pushid[index]);
151 
152     printf("rn");
153 
154 }
155 
156 int main(int argc, char *argv[])
157 {
158     int index = 0;
159 
160     int a[POOL_LATEST_PUSHID_MAX] = {0}; 
161 
162     for ( index = 100; ; index++){
163         int is_in = 0;
164         int j = 0;
165 
166         int ask = index;
167         is_in = is_message_repeat(index); 
168         printf("ask=%d, is_in=", ask);
169         
170         if (1 == is_in)
171             shell_printf_greep("Yes.");
172         else
173             shell_printf_red("No");
174 
175         printf("rn");
176 
177         print_circle_array();
178 
179         for (j = 0; j<POOL_LATEST_PUSHID_MAX; j++)
180         {
181             ask = g_latest_pushid.pushid[j];
182             is_in = is_message_repeat(ask); 
183         //    printf("ask=%d, is_in=%s.rn", ask, 1 == is_in ? "Yes" : "No");
184             printf("ask=%d, is_in=", ask);
185 
186             if (1 == is_in)
187                 shell_printf_greep("Yes.");
188             else
189                 shell_printf_red("No");
190 
191         printf("rn");
192             print_circle_array();
193 
194         }
195 
196         sleep(1);
197     }
198     return 0;
199 }