-1-
リストⅢ
０．目次
３．応用
３．１ マージソート
３．２ グラフ表現
３．３ 問題
問題１：素数生成
問題２：素数生成（高速化）
問題３：双方向リストの作成
リストⅢ
-2-
３．応用
３．１ マージソート
考え方●
（手順１）n個のデータを読み込み、要素数1のn個のリストを作成する。
（手順２）隣接する２つのリストを併合し、１つの昇順リストを作成する。
（手順３）リスト数が１つになるまで （手順２）を繰り返す。、
（１.１）
head[1] 55 NULL
head[2] 33 NULL
head[3] 66 NULL
head[4] 11 NULL
head[5] 77 NULL
head[6] 22 NULL
head[7] 44 NULL
（１.２）
head[1] 55 NULL
head[2] 33
head[3] 66 NULL
head[4] 11 NULL
head[5] 77 NULL
head[6] 22 NULL
head[7] 44 NULL
リストⅢ
-3-
リストⅢ
（１.３）
head[1] 55 NULL
head[2] 33
head[3] 66 NULL
head[4] 11
head[5] 77 NULL
head[6] 22 NULL
head[7] 44 NULL
（１.４）
head[1] 55 NULL
head[2] 33
head[3] 66 NULL
head[4] 11
head[5] 77 NULL
head[6] 22
head[7] 44 NULL
（１.５）
head[1] 55 NULL
head[2] 33
head[3] 66 NULL
head[4] 11
head[5] 77 NULL
head[6] 22
head[7] 44 NULL
-4-
リストⅢ
（２.１）
head[1] 33 55 NULL
head[2] 11 66 NULL
head[3] 22 77 NULL
head[4] 44 NULL
head[5]
head[6]
head[7]
（２.２）
head[1] 33 55
head[2] 11 66 NULL
head[3] 22 77 NULL
head[4] 44 NULL
head[5]
head[6]
head[7]
（２.３）
head[1] 33 55
head[2] 11 66 NULL
head[3] 22 77 NULL
head[4] 44
head[5]
head[6]
head[7]
-5-
リストⅢ
（３.１）
NULLhead[1] 11 33 55 66
NULLhead[2] 22 44 77
head[3]
head[4]
head[5]
head[6]
head[7]
（３.２）
head[1] 11 33 55 66
NULLhead[2] 22 44 77
head[3]
head[4]
head[5]
head[6]
head[7]
プログラム●
1 /* << f311.c >> */
/* マージソート */2
3 #include <stdio.h>
4 #include <stdlib.h>
5 struct NODE {
6 int info;
7 struct NODE *next;
8};
9 main() {
10 int data,i,j,n;
11 struct NODE *head[999],*p,*p1,*p2,*q,*temp;
/* 初期リストの作成。要素数1のリストを配列として作成する。*/12
/* 配列の要素数。*/13 n=0;
14 while(1){
15 scanf("%d",&data); if( data <= 0 ) { break; }
16 n++;
17 head[n] = (struct NODE *)malloc(sizeof(struct NODE));
18 p = (struct NODE *)malloc(sizeof(struct NODE));
19 p->info = data; p->next = NULL;
20 head[n]->next = p;
21 }
评论0