C 語言練習程式(7) -- 直接改變陣列內容&利用指標達成回傳型態轉換 -- 指標相關程式集錦(6)

此篇為Pointers in C Programming A Modern Approach to Memory Management, Recursive Data Structures, Strings, and Arrays這本書第六章筆記其之一。

要說這兩個主題，可以用篩法的程式來解釋。篩法是可以列出n個數內所有質數的一個方法，原理很簡單，從2開始，，只要被2整除的(也就是2的倍數)都不是質數，全部去掉。去掉2的倍數後，除2以外最小的值是3，再把數列中3的倍數全部去掉，接下來的做法以此類推。

如果不用到指標，陣列版的程式如下:

int compact0(int n, int array[n])
{
  int m = 0;
  for (int i = 0; i < n; i++) {
    if (array[i] > 0)
      array[m++] = array[i];
  }
  return m;
}

int eratosthenes(int n, int buf[n - 2])
{
  // Init
  for (int i = 2; i < n; i++) {
    buf[i - 2] = i;
  }

  // Sieve
  for (int i = 0; i*i < n - 2; i++) {
    if (buf[i] == 0) continue;
    int p = buf[i];
    for (int j = p*p; j < n; j += p) {
      buf[j - 2] = 0;
    }
  }

  // Compact
  return compact0(n - 2, buf);
}

我們的main裡面有一個buf陣列，傳進去compact0跟eratosthenes後不需return，函式結束後都會使陣列的內容改變，所以只要return陣列中最後一個質數的位置即可。
而這裡的eratosthenes函式的做法，並不是把非質數去掉，而是歸零，所以需要compact0函式把0給去掉，並把數字擠在一起。

指標板就是重點了，其程式碼如下:

int *sieve_candidates_(int *from, int *to, int p)
{
  int *output = from;
  for (int *input = from ; input < to; input++) {
    if (*input % p != 0)
      *output++ = *input;
  }
  return output;
}

int eratosthenes__(int n, int buf[n - 2])
{
  // Init
  for (int i = 2; i < n; i++) {
    buf[i - 2] = i;
  }

  // Sieve
  int *candidates = buf;
  int *end = buf + n - 2;
  while (candidates < end) {
    int p = *candidates++; // Get prime and move it
    end = sieve_candidates_(candidates, end, p);
  }

  return end - buf;
}

最需要注意的是以下程式碼:

  for (int *input = from ; input < to; input++) {
    if (*input % p != 0)
      *output++ = *input;
  }

這一段就是直接把陣列裡的數字取代掉，原始陣列如下圖

那是怎麼把2的倍數通通消掉的?(如下圖)

假設目前p==2，*input==5，那麼目前的ouput在3這個位置上。*output++ = *input;這句話，會讓ouput往前一格跑到4上面，接下來*input的值會取代4。接下來的值都是以此類推。

至於回傳型態，可以參照下面程式碼:

void sieve_candidates__(int **from, int **to)
{
  int p = *(*from)++;
  int *output = *from;
  for (int *input = *from ; input < *to; input++) {
    if (*input % p != 0)
      *output++ = *input;
  }
  *to = output;
}

int eratosthenes___(int n, int buf[n - 2])
{
  // Init
  for (int i = 2; i < n; i++) {
    buf[i - 2] = i;
  }

  // Sieve
  int *candidates = buf;
  int *end = buf + n - 2;
  while (candidates < end) {
    sieve_candidates__(&candidates, &end);
  }

  return end - buf;
}

其實跟上面程式碼意思是一模一樣的，但可以發現根本就不用return，直接assign給一個指標就好，這算是把to宣告成雙重指標的好處吧。
完整程式碼如下:

#include <stdio.h>

int compact0(int n, int array[n])
{
  int m = 0;
  for (int i = 0; i < n; i++) {
    if (array[i] > 0)
      array[m++] = array[i];
  }
  return m;
}

int eratosthenes(int n, int buf[n - 2])
{
  // Init
  for (int i = 2; i < n; i++) {
    buf[i - 2] = i;
  }

  // Sieve
  for (int i = 0; i*i < n - 2; i++) {
    if (buf[i] == 0) continue;
    int p = buf[i];
    for (int j = p*p; j < n; j += p) {
      buf[j - 2] = 0;
    }
  }

  // Compact
  return compact0(n - 2, buf);
}

void sieve_candidates(int **from, int **to, int p)
{
  int *output = *from;
  for (int *input = *from ; input < *to; input++) {
    if (*input % p != 0)
      *output++ = *input;
  }
  *to = output;
}

int eratosthenes_(int n, int buf[n - 2])
{
  // Init
  for (int i = 2; i < n; i++) {
    buf[i - 2] = i;
  }

  // Sieve
  int *candidates = buf;
  int *end = buf + n - 2;
  while (candidates < end) {
    int p = *candidates++; // Get prime and move it
    sieve_candidates(&candidates, &end, p);
  }

  return end - buf;
}

int *sieve_candidates_(int *from, int *to, int p)
{
  int *output = from;
  for (int *input = from ; input < to; input++) {
    if (*input % p != 0)
      *output++ = *input;
  }
  return output;
}

int eratosthenes__(int n, int buf[n - 2])
{
  // Init
  for (int i = 2; i < n; i++) {
    buf[i - 2] = i;
  }

  // Sieve
  int *candidates = buf;
  int *end = buf + n - 2;
  while (candidates < end) {
    int p = *candidates++; // Get prime and move it
    end = sieve_candidates_(candidates, end, p);
  }

  return end - buf;
}

void sieve_candidates__(int **from, int **to)
{
  int p = *(*from)++;
  int *output = *from;
  for (int *input = *from ; input < *to; input++) {
    if (*input % p != 0)
      *output++ = *input;
  }
  *to = output;
}

int eratosthenes___(int n, int buf[n - 2])
{
  // Init
  for (int i = 2; i < n; i++) {
    buf[i - 2] = i;
  }

  // Sieve
  int *candidates = buf;
  int *end = buf + n - 2;
  while (candidates < end) {
    sieve_candidates__(&candidates, &end);
  }

  return end - buf;
}

void print_array(int *begin, int *end)
{
  while (begin < end) {
    printf("%d ", *begin++);
  }
  printf("\n");
}

int main(void)
{
  int n = 100;
  int buf[n - 2];

  int m = eratosthenes(n, buf);
  print_array(buf, buf + m);
  m = eratosthenes_(n, buf);
  print_array(buf, buf + m);
  m = eratosthenes__(n, buf);
  print_array(buf, buf + m);
  m = eratosthenes___(n, buf);
  print_array(buf, buf + m);

  return 0;
}