新規記事の投稿を行うことで、非表示にすることが可能です。
2017年12月02日
《その160》 マージソート & p.129演習3-9，演習3-10，演習3-11
マージソートの概略
・ 配列を、先ず、バラバラに分解します。
・ 次に２個の要素を、各値が昇順になるようにして統合します。
・ 統合してできた部品どうしをさらに統合していきますが、統合の際は、必ず値が昇順になるようにします。
・ 最終的に、全てを統合したらソート終了です。
マージソートの詳細は、次回《161》にチェックしたいと思います。
下図は、マージソートのイメージ図です。
新版明解C++中級編 p.129 演習3-9
※本ブログの《その153》のプログラムが、解答です。
新版明解C++中級編 p.129 演習3-10
※本ブログの《その155》のプログラムが、解答です。
新版明解C++中級編 p.129 演習3-11
※本ブログの《その156》のプログラムが、解答です。
 | 新品価格 |  | 新品価格 |
《その159》 配列の型について & p.129演習3-8
配列の型について
次のプログラムで、配列の型について、いくつか確認してみます。
// ------------------------------------
#include <iostream>
int main() {
char a[][3][4]
= {
{ "aaa", "bbb", "ccc" },
{ "abc", "bca", "cba" },
{ "aab", "bbc", "cca" },
{ "abb", "bcc", "caa" },
};
// typeid演算子を用いて型名を調べてみます。
std::cout << typeid(&a[0][0][0]).name() << '\n';
// 結果は「 char * 」
std::cout << typeid(&a[0][0]).name() << '\n';
// 結果は「 char (*)[4] 」
std::cout << typeid(&a[0]).name() << '\n';
// 結果は「 char (*)[3][4] 」
void* v1 = (void*)&a[0][0][0];
// &a[0][0][0]へのポインタを void* 型にキャストして void* v1 に代入。
// ポインタ v1 は配列の型としての情報を失います。
void* v2 = (void*)&a[3][0][0];
// &a[3][0][0]へのポインタを void* 型にキャストして void* v2 に代入。
// ポインタ v2 は配列の型としての情報を失います。
std::cout << (char*)v2 - (char*)v1 << '\n';
// v1, v2 を char*型にキャストして減算
// 結果は「 36 」
// この型の配列要素の序数差に一致します。
std::cout << (char(*)[4])v2 - (char(*)[4])v1 << '\n';
// v1, v2 を char(*)[4]型にキャストして減算
// 結果は「 9 」
// この型の配列要素の序数差に一致します。
std::cout << (char(*)[3][4])v2 - (char(*)[3][4])v1 << '\n';
// v1, v2 を char(*)[3][4]型にキャストして減算
// 結果は「 3 」
// この型の配列要素の序数差に一致します。
}
// ------------------------------------
新版明解C++中級編 p.129 演習3-8
次の関数 seqsearch を利用するプログラムを作成せよ。
// -- seqsearch -----------------------
// 汎用線形探索関数
void* seqsearch(
const void* key, // キー値へのポインタ
const void* base, // 配列へのポインタ
size_t nmemb, // 要素の個数
size_t size, // 要素１つ分の大きさ
int(*compar)(const void*, const void*)
) {
const char* x
= reinterpret_cast<const char*>(base);
for (size_t i = 0; i < nmemb; i++)
// 比較関数 compar の返却値が
// 0 でなければ検索成功
if (!compar(
key,
reinterpret_cast<const void*>
(&x[i * size])
)
)
// ポインタ値を void*型にして返却
return
const_cast<void*>(
reinterpret_cast<const void*>(
&x[i * size]
)
);
// 検索値が存在しなければ NULL を返却
return NULL;
}
// ------------------------------------
// p129_演習3-8
#include <string>
#include <iostream>
void* seqsearch(
const void* key, // キー値へのポインタ
const void* base, // 配列へのポインタ
size_t nmemb, // 要素の個数
size_t size, // 要素１つ分の大きさ
int(*compar)(const void*, const void*)
) {
const char* x
= reinterpret_cast<const char*>(base);
for (size_t i = 0; i < nmemb; i++)
// 比較関数 compar の返却値が
// 0 でなければ検索成功
if (!compar(
key,
reinterpret_cast<const void*>
(&x[i * size])
)
)
// ポインタ値を void*型にして返却
return
const_cast<void*>(
reinterpret_cast<const void*>(
&x[i * size]
)
);
// 検索値が存在しなければ NULL を返却
return NULL;
}
int acmp(char* x, char* y) { // 比較関数
return strcmp(x, y);
}
int pcmp(char* x, char** y) { // 比較関数
return strcmp(x, *y);
}
int ncmp(int* x, int* y) { // 比較関数
return *x < *y ? -1 : *x > *y ? 1 : 0;
}
void existence(int n) {
std::cout << n << "番目\n";
}
void non_existence() {
std::cout << "該当なし\n";
}
int main() {
const char a[][5]
= { "cba", "cabd", "abc", "bcd",
"cab", "b", "a", "cba", "aa" };
const char* p[]
= { "cba", "cabd", "abc", "bcd",
"cab", "b", "a", "cba", "aa" };
int num[]
= { 25, 21, 16, 12, 17, 11, 23,
19, 28, 17, 22, 24, 11, 18 };
// ------------------------------------
std::cout << "◆";
for (int i = 0; i < 9; i++)
std::cout << a[i] << ' ';
std::cout << '\n';
char key1[10];
std::cout << " 探索する文字列は？ : ";
std::cin >> key1;
std::cout << " " << key1 << " → ";
void* f = seqsearch(
key1,
a,
sizeof(a) / sizeof(a[0]),
sizeof(a[0]),
reinterpret_cast<int(*)(
const void*,
const void*
)>(acmp)
);
if (f == 0) non_existence();
else existence((char(*)[5])f - a + 1);
// ------------------------------------
std::cout << "\n◆";
for (int i = 0; i < 9; i++)
std::cout << p[i] << ' ';
std::cout << '\n';
char key2[10];
std::cout << " 探索する文字列は？ : ";
std::cin >> key2;
std::cout << " " << key2 << " → ";
f = seqsearch(
key2,
p,
sizeof(p) / sizeof(p[0]),
sizeof(p[0]),
reinterpret_cast<int(*)(
const void*,
const void*
)>(pcmp)
);
if (f == 0) non_existence();
else existence((char**)f - p + 1);
// ------------------------------------
std::cout << "\n◆";
for (int i = 0; i < 14; i++)
std::cout << num[i] << ' ';
std::cout << '\n';
int key;
std::cout << " 探索する整数値は？ : ";
std::cin >> key;
std::cout << " " << key << " → ";
f = seqsearch(
&key,
num, sizeof(num) / sizeof(num[0]),
sizeof(num[0]),
reinterpret_cast<int(*)(
const void*,
const void*
)>(ncmp)
);
if (f == 0) non_existence();
else existence((int*)f - num + 1);
}
| 新品価格 | | 新品価格 |
