Cで多項式計算

Table of Contents

1 データ構造

まず,整数リストのデータ構造を定義する.

typedef struct node_struct NODE;
struct node_struct {
  int elem;
  NODE *next;
};

2 リストの作成

リストセルを作成するための関数を定義する.

1:  NODE *new_node(int elem, NODE *next) {
2:    NODE *p;
3:    p = (NODE*)malloc(sizeof(NODE));
4:    p->elem = elem;
5:    p->next = next;
6:    return p;
7:  }

たとえば,以下のようにするとリスト 3, 2, 1 が作成できる.

NODE *p;
p = new_node(1, NULL);
p = new_node(2, p);
p = new_node(3, p);

あるいは,以下のようにしても良い.

NODE *p;
p = new_node(3, new_node(2, new_node(1, NULL)));

3 リストの印刷

デバッグのため,リストを印刷するプログラムを作成しておく.

1:  void print(NODE *p) {
2:    for (; p != NULL; p = p->next) {
3:      printf("%d ", p->elem);
4:    }
5:    printf("\n");
6:  }

下のように記述したプログラムで確認する.

NODE *p;
p = new_node(3, new_node(2, new_node(1, NULL)));
print(p);

以下のように出力される.

3 2 1

4 定数倍

多項式を定数倍した新しい多項式を求める関数 imul は以下のように定義できる.

1:  NODE *imul(int b, NODE *p) {
2:    if (p == NULL) {
3:      return NULL;
4:    } else {
5:      return new_node(b * p->elem, imul(b, p->next));
6:    }
7:  }

5 加算

二つの多項式の和になっている新しい多項式を求める関数 add を作成する.

add(p, q)の動作は,以下のように再帰的に定義できる.

  • pが空リストの場合qが答えであり,qが空リストの場合pが答えである.
  • どちらも空リストでない場合,p->nextとq->nextに対して 再帰的にaddを実行した結果のリストの前に, 双方の先頭要素の和を付け加えたリストが答えである.

これをプログラムとして記述すると,以下のようになる.

 1:  NODE *add(NODE *p, NODE *q) {
 2:    if (p == NULL) {
 3:      return q;
 4:    } else if (q == NULL) {
 5:      return p;
 6:    } else {
 7:      return new_node(p->elem + q->elem, 
 8:                      add(p->next, q->next));
 9:    }
10:  }

6 乗算

二つの多項式の積になっている新しい多項式を求める関数 mul を作成する.

mul(p, q)の動作は,以下のように再帰的に定義できる.

  • pが空リストの場合,空リストが答えである.
  • pが空リストでない場合,p->nextとqに対して 再帰的にmulを実行した結果のリストの前に0を付け加えたリストと, qをp->elem倍 (imul)したリストとの和 (add)が答えである.

これをプログラムとして記述すると,以下のようになる.

1:  NODE *mul(NODE *p, NODE *q) {
2:    if (p == NULL) {
3:      return NULL;
4:    } else {
5:      NODE *r = mul(p->next, q);
6:      return add(imul(p->elem, q), new_node(0, r));
7:    }
8:  }

7 プログラム全体

プログラム全体は,以下のようになる.

 1:  #include <stdio.h>
 2:  #include <stdlib.h>
 3:  
 4:  typedef struct node_struct NODE;
 5:  struct node_struct {
 6:    int elem;
 7:    NODE *next;
 8:  };
 9:  
10:  NODE *new_node(int elem, NODE *next) {
11:    NODE *p;
12:    p = (NODE*)malloc(sizeof(NODE));
13:    p->elem = elem;
14:    p->next = next;
15:    return p;
16:  }
17:  
18:  NODE *imul(int b, NODE *p) {
19:    if (p == NULL) {
20:      return NULL;
21:    } else {
22:      return new_node(b * p->elem, imul(b, p->next));
23:    }
24:  }
25:  
26:  NODE *add(NODE *p, NODE *q) {
27:    if (p == NULL) {
28:      return q;
29:    } else if (q == NULL) {
30:      return p;
31:    } else {
32:      return new_node(p->elem + q->elem, 
33:                      add(p->next, q->next));
34:    }
35:  }
36:  
37:  NODE *mul(NODE *p, NODE *q) {
38:    if (p == NULL) {
39:      return NULL;
40:    } else {
41:      NODE *r = mul(p->next, q);
42:      return add(imul(p->elem, q), new_node(0, r));
43:    }
44:  }
45:  
46:  void print(NODE *p) {
47:    for (; p != NULL; p = p->next) {
48:      printf("%d ", p->elem);
49:    }
50:    printf("\n");
51:  }
52:  
53:  int main(int argc, char *argv[]) {
54:    NODE *p, *q, *r;
55:    p = new_node(1, NULL);
56:    p = new_node(2, p);
57:    p = new_node(3, p);
58:    print(p);
59:    p = new_node(1, new_node(-1, new_node(0, new_node(2, new_node(-3, NULL)))));
60:    q = imul(2, p);
61:    print(q);
62:    p = new_node(1, new_node(2, new_node(3, NULL)));
63:    q = new_node(1, new_node(-2, new_node(3, new_node(-4, NULL))));
64:    r = add(p, q);
65:    print(r);
66:    p = new_node(1, new_node(2, new_node(3, NULL)));
67:    q = new_node(1, new_node(-2, new_node(3, NULL)));
68:    r = mul(p, q);
69:    print(r);
70:    return 0;
71:  }

実行結果は,以下のようになる.

3 2 1 
2 -2 0 4 -6 
2 0 6 -4 
1 0 2 0 9 

7.1 注意

ここでは,malloc した領域の free を全く考慮していない. 特に add は,領域の共有が生じる可能性があるプログラムコードになっているため, 単純に free することが難しくなっている点に注意すること.

Lisp, Prolog, Java, Scala等の場合,処理系が自動的にゴミ集め(Garbage Collection)を 行うため,このような問題は生じない.

8 練習問題

  1. 二つの多項式の差を求める関数 sub を作成せよ.
  2. 多項式と整数bが与えられた時, 多項式が単項式 x-b で割り切れるかどうか調べる関数 divisible を作成せよ.
  3. 多項式を微分した新しい多項式を求める関数 deriv を作成せよ.

Date: 2017-09-29 21:45:26 JST

Author: 田村直之

Validate XHTML 1.0