アルゴリズムとデータ構造

アルゴリズムと
データ構造
第13回
文字列処理
ソートの復習
名称
計算量
内部/外
部
安定/不安定
バブルソート
O(n2)
内部
安定
挿入ソート
O(n2)
内部
安定
選択ソート
O(n2)
内部
不安定
バケットソート O(n)
内部
安定
データに制限
有
基数ソート
O(n)
内部
安定
データに制限
有
シェルソート
O（n1.25）～
O（n1.5）
内部
不安定
内部
不安定
クイックソート O(n log n)
備考
最悪O(n2)
前回の演習問題
次の配列を、クイックソートにより並べ替える。
並べ替え領域の左端の添え字を pl、右端の添え字を pr と設定したとき、枢軸は
(pl+pr)/2（小数点以下切り捨て）で示される添え字の位置とする（この配列では添え字 5
の 59）。ここで
1. pl 位置の値が枢軸の値以上になるまで pl を右へずらす。
2. pr 位置の値が枢軸の値以下になるまで pr を左へずらす。
3. pl 位置の値と pr 位置の値を入れ替える。
4. pl と pr が交差して入れ替わるまで、1. から 3. までを繰り返す。
という操作を行うと、配列は
となり、添え字 0 から 5 までの集合と 6 から 11 までの集合に分割される。このとき、以下の問い
に答えよ。
(1) 添え字 0 から 5 までの集合において、pl、pr および枢軸の位置を再設定し、同様に分割したと
き、分割後の配列の並びと pl、pr の添え字位置を示せ。
(2) 添え字 6 から 11 までの集合において、pl、pr および枢軸の位置を再設定し、同様に分割した
とき、分割後の配列の並びと pl、pr の添え字位置を示せ。
解説
枢軸 =
34
76
0
1
2
3
4
5
25
14
34
40
28
32
pl
6
7
8
9
10
11
59
81
76
83
87
98
pl
答え：
pr
pr
C言語の文字列

文字列とは
 プログラム上で文字の並びを表す


中身が空でもよい
文字列リテラル
 文字の並びを2つの引用符で囲んだもの
 各文字は記憶域上で連続して配置
 終端にはナル文字が自動的に付加
 内容は基本的に書き換え不可
C言語の文字列

文字列リテラル
文字列リテラル“STRING”
01010011
文字’S’ (0x53)
S T R I N G \0
01010100
文字’T’ (0x54)
01010010
文字’R’ (0x52)
01001001
文字’I’ (0x49)
01001110
文字’N’ (0x5E)
01000111
文字’G’ (0x47)
00000000
ナル文字’\0’ (0)
C言語の文字列

文字列リテラルの特徴
 型と値

char *型・評価値は先頭文字へのポインタ
 記憶域期間

静的記憶域期間：プログラム開始から終了まで記憶域を占有
 同一つづりの文字列リテラル

格納領域が同一か別かは処理系依存
 定数性

文字列リテラルの記憶域への値の書き込みは定義なし：どうなる
かは処理系依存・やるべきではない
C言語の文字列

配列による文字列
 文字列をchar型配列に格納することで、値の読
み書きが可能
 終端にはナル文字が必要
ナル文字がないとプログラム暴走の恐れ
 ナル文字以降どのような内容があろうと無視

配列
S T R I N G \0
文字列
無視
C言語の文字列

文字列の初期化
 配列宣言の際に初期化可能
 代入式では初期化式無効
char st[10] = {‘S’, ‘T’, ‘R’, ‘I’, ‘N’, ‘G’, ‘\0’};
char st[10] = “STRING”;
/* 上の式と同等 */
char st[10];
st = {‘S’, ‘T’, ‘R’, ‘I’, ‘N’, ‘G’, ‘\0’};
st = “STRING”;
/* エラー */
/* エラー */
C言語の文字列

ポインタによる文字列
 文字列リテラルを指し示すのにポインタを使用
 各文字へのアクセスは配列へのアクセスと同様
pt
char *pt = “1234”;
ポインタ
1 2 3 4 \0
文字列リテラル
・仮に文字列リテラルが1000番地から格納されていれば、ptには1000が入る
文字列の基本操作

文字列の長さ
 配列要素数と文字列長は必ずしも一致しない

配列全体を使い切っているとは限らない
 文字列先頭からナル文字を線形探索
最初に見つかったナル文字までが文字列
 ナル文字のある要素の添え字が文字列の長さ



ナル文字はカウントしない
必ずナル文字が存在：探索失敗を考慮する必要なし

ある意味番兵法ともいえる
文字列の基本操作

文字列の長さ
int str_len(const char *s) {
int len = 0;
while (s[len])
len++;
return (len);
}
文字列の基本操作

文字列の長さ
int str_len(const char *s) {
int len = 0;
while (*s++)
len++;
return (len);
}
文字列の基本操作

文字列の長さ
int str_len(const char *s) {
char *p = s;
while (*s)
s++;
return (s - p);
}
文字列の基本操作

文字列からの文字の探索
 文字列先頭から対象文字を線形探索
最初に見つかった位置が求める位置
 見つかる前にナル文字がきたら探索失敗

文字列の基本操作

文字列からの文字の探索
int str_chr(const char *s, int c) {
int i;
for (i = 0; s[i] != c; i++)
if (s[i] == ‘\0’)
return (-1);
return (i);
}
文字列の基本操作

文字列からの文字の探索
char *str_chr(const char *s, int c) {
for ( ; *s != c; s++)
if (*s == ‘\0’)
return (NULL);
return ((char *) s);
}
文字列の基本操作

文字列の比較
 2つの文字列を先頭から順に比較
すべての文字が等しかったら等しいと判断
 途中で違う文字列がきたら大小比較

違う部分の文字のそれぞれの文字コードの大小で比較
 文字コードの体系により比較結果に差異

文字列の基本操作

文字列の比較
int str_cmp(const char *s1, const char *s2) {
while (*s1 == *s2) {
if (*s1 == ‘\0’)
return (0);
s1++; s2++;
}
return ((unsigned char) *s1 - (unsigned char) *s2));
}
文字列探索

文字列探索とは
 文字列中に、別の文字列が存在するかを探索
探し出す文字列：パターン
 探索される文字列：テキスト

文字列探索

力まかせ法
 単純法・素朴法
 テキストの先頭から順次パターンと比較
 一致するまで、パターン位置を1文字ずつずらし
て再比較

最後まで一致しなかったら含まれない
文字列探索

力まかせ法
A
B
A
B
A
B
C
\0
C
D
\0
E
F
G
H
A
\0
文字列探索

力まかせ法
pt
A
B
A
B
A
B
C
\0
pp
C
D
\0
E
F
G
H
A
\0
文字列探索

KMP法
 Knuth-Morris-Pratt法
 不一致文字に出会ったときのそれまでの照合結
果を有効利用
 テキスト中とパターン中の重なり部分を見つけ、
パターンの移動を大きく
 テキスト走査位置が前進のみ
文字列探索

KMP法
Z
A
B
C
A
B
X
A
B
C
B
C
A
A
B
D
B
\0
D
A
C
C
A
D
E
F
\0
文字列探索

KMP法における照合再開位置
A
B
C
A
B
D
\0
A
B
C
A
B
D
\0
A
B
C
A
B
D
0
0
0
1
2
0
文字列探索

KMP法
pt
Z
A
B
C
A
B
X
A
C
C
A
B
C
B
C
A
A
B
D
B
\0
D
A
B
C
A
B
D
0
0
0
1
2
0
pp
A
D
E
F
\0
まとめ
文字列処理
 C言語の文字列
• 文字列とは
• 文字列リテラル
• 配列による文字列
• ポインタによる文字列
 文字列の基本操作
• 文字列の長さ
• 文字列からの文字の探索
• 文字列の比較
 文字列探索
• 力まかせ法（単純法）
• KMP法
演習問題
第1問
第２問
名前と学籍番号をご記入のうえ、解答用紙（A4）を提出する
提出先：
工学部電子情報実験研究棟５階
NO.5506室のドアのポストに入れてください
締め切り時間：
来週月曜日（7月14日）午前９時まで

Download Report