![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
はじめまして
DHCPのような動作をするアルゴリズムを考えている最中なのですが…
その案の中でどうしてもクリア出来ない課題があります。
「配列で作られたテーブルにユーザ名の一覧があり、
そのユーザ名をキーワードとして配列のインデックスを抽出したい」
というもので、これだけなら簡単なのですが、以下3つの条件の提示により、無理ではないかと思えて仕方がないです。
・ユーザ名は何らかのルールに則って作られた文字列ではない。
・キーワードを頭から順に比較して探していく方法を使ってはいけない。
・ユーザの追加・削除がある度にソートし直さなければならないような構造にしてはいけない。
2分探索法などの検索回数を減らす方法はソートされてることが前提条件ですし、
ユーザ名から配列のインデックスに使える数値に変換できるような都合のいい関数なんて存在しないように思えるのですが、いかがでしょう?
ちなみに開発言語はCです。
![](http://oshiete.xgoo.jp/images/v2/common/profile/M/noimageicon_setting_16.png?e8efa67)
No.1ベストアンサー
- 回答日時:
どうしてそのような制約があるのか理解できませんが、
ユーザ名をキーワードとした配列があるとして、
それとは別にユーザ名から配列のインデクスが引ける
ハッシュ表を用意すればできますね(領域の無駄ですけど)。
ユーザ名の削除はあり、既登録のユーザ名のインデクスは
変えたくなく、削除であいた配列要素の再利用をしたい場合には、
フリーインデクスのフリーリストを作っておけばいいですね(これにも
また無駄に領域を使わないとなりませんが)。
もちろん、配列がいっぱいになったら、realloc() しないと
いけませんが、インデクスで管理しているから更新部分は
配列のみでOKでしょう。
しかし、そもそも、掲出の制約がなぜあるのか。。。
ダメなデータ構造をテクニックでカバーしようとしないで、
データ構造とアルゴリズムを同時に設計したほうがいいのではないですか?^^;
![](http://oshiete.xgoo.jp/images/v2/common/profile/M/noimageicon_setting_16.png?e8efa67)
No.5
- 回答日時:
こんな感じでいいのかしら?ハッシュ表やフリーリスト操作が面倒だったので、C++の map(バランス木だけど^^)やstackを使っちゃってますが、
ほかのところは、C言語っぽく書いてます(笑)
レコードの構造体は、プログラマが勝手にいじれないと仮定しました。
登録レコードは name が NULL でないので、レコードの配列を
直接たどって、登録レコードか空きレコードかがわかるようにしてます。レコードの構造体とフリーリストのためのリンクとを共用体にしてやれば、フリー領域管理のためのメモリは節約できるでしょうね。
====
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
/* ユーザのレコード: 今は名前のポインタのみ */
struct Record { char *name; };
#include <stack>
struct Table
{
struct Record *prec;/* レコードの配列 */
size_t nrec;/* 登録レコード数 */
size_t sz;/* 配列の大きさ */
std::stack<size_t> flist;/* 空いているレコードのインデクスのリスト */
} table;
void iniTable()
{
const size_t init_size = 3;
size_t i;
table.prec = (struct Record *)malloc(sizeof(Record) * init_size);
table.nrec = 0;
table.sz = init_size;
for (i = 0; i < table.sz; ++i) {
table.prec[i].name = NULL;
table.flist.push(i);/* インデクスをフリーリストへ登録 */
}
}
/* 配列を m だけ大きくする */
void growTable(size_t m)
{
size_t i;
table.prec =
(struct Record *)realloc(table.prec, sizeof(Record) * (table.sz + m));
for (i = table.sz; i < table.sz + m; ++i) {
table.prec[i].name = NULL;
table.flist.push(i);/* インデクスをフリーリストへ登録 */
}
table.sz += m;
}
#include <map>
#include <string>
typedef std::map<std::string, size_t> map_t;
map_t indexMap;/* 配列のインデクス管理マップ */
void finTable()
{
map_t::iterator i;
for (i = indexMap.begin(); i != indexMap.end(); ++i)
free(table.prec[i->second].name);
free(table.prec);
while (!table.flist.empty()) table.flist.pop();
indexMap.clear();
}
const size_t errSz = (size_t)-1;/* エラー報告用インデクス値 */
size_t put(const char *user)
{
const int grow_size = 3;
size_t idx;
map_t::iterator iter = indexMap.find(user);
/* user のレコードがすでにあれば何もしない */
if (iter != indexMap.end()) return iter->second;
/*... user は存在しないのでレコードを作る ...*/
/* フリーリストが空なら配列を大きくする */
if (table.flist.empty()) growTable(grow_size);
/* フリーリストから空きインデクスをもらう */
idx = table.flist.top(); table.flist.pop();
/* user のレコード設定 */
table.prec[idx].name = strcpy((char *)malloc(strlen(user) + 1), user);
indexMap[user] = idx;/* インデクスをマップに登録 */
++table.nrec;
return idx;
}
size_t get(const char *user)
{
map_t::iterator iter = indexMap.find(user);
if (iter == indexMap.end()) return errSz;
else return iter->second;
}
size_t del(const char *user)
{
size_t idx = errSz;
map_t::iterator iter = indexMap.find(user);
if (iter != indexMap.end()) {
/* user は存在した */
idx = iter->second;/* user のインデクスを得る */
/* user のレコードを消去 */
indexMap.erase(iter);
table.flist.push(idx);
free(table.prec[idx].name);
table.prec[idx].name = NULL;
--table.nrec;
}
return idx;
}
#include <stdio.h>
int main()
{
size_t idx;
iniTable();
idx = put("saito");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = put("yamada");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = put("tanaka");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = put("suzuki");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = del("tanaka");
if ((idx = get("takana")) == errSz) printf("OK\n");
idx = put("sato");
printf("%d %s\n", (int)idx, table.prec[idx].name);
idx = put("takahashi");
printf("%d %s\n", (int)idx, table.prec[idx].name);
finTable();
}
=======
% ./a.out
2 saito
1 yamada
0 tanaka
5 suzuki
OK
0 sato
4 takahashi
No.4
- 回答日時:
服飾デザイナでプログラマではありませんが・・・。
どんなアルゴリズムを構想するにしろ、データの件数という量は無視できないと思います。
対象が1000レコードと10万レコードじゃ話が違ってくるのじゃないですかね。
実テーブルの制約が絶対条件であれば、仮想テーブルを用意して解決するしかないでしょう。
が、これも量次第では、ユーザ名を仮想テーブル管理アプリーケーションに投げる策も考えることに。
量次第では、構造体変数をバイナリで記録しておいてセーブとロードを繰り返しても良いような気がします。
いずれにしろ、アルゴリズムの問題というよりも、データ量と逃げの関係だと思いますが・・・。
No.3
- 回答日時:
2分探索または探索用の独自インデックスを作ったら良いんじゃない?
配列をアドレスとして置き換え表現して インデックスにアドレスがかかれてれば値を挿入するときに探索インデックスに適合するようにしたら良いのでは?
・・・要するに他の人と言ってる事が同じかな
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語初心者 構造体 課題について 2 2023/03/10 19:48
- その他(Microsoft Office) Excelでユーザ名を入力すればそのユーザの最大、平均が表示されるようにする、何も入力されてなければ 1 2022/07/28 00:31
- その他(プログラミング・Web制作) プログラムの起動、利用について、使用期間を設定する方法 3 2023/08/06 21:03
- Access(アクセス) AccessVBAで降順にするテーブル作成クエリを使用して作成したテーブルを削除し同一のテーブル作成 1 2023/01/06 11:17
- サーバー Windowsサーバでグループを検索したい 1 2023/04/17 15:30
- Visual Basic(VBA) 特定の文字を簡単な操作で半角スペースに変換するか削除したい 2 2022/11/01 10:35
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- Java Java 南京錠 2 2023/02/04 11:46
- Excel(エクセル) エクセルで重複データから重複を削除して指定の列に抽出したい 11 2022/05/11 11:26
- Excel(エクセル) エクセルの大きなシートでグラフを見つける 4 2022/07/28 10:07
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
関数から配列を返すには?
-
構造体のextern方法
-
C言語において、 配列要素をひ...
-
C言語の2次元配列 容量が大き...
-
プログラム 数列の和
-
配列の要素数に変数を入れたい...
-
5人分の氏名と英語、国語、数...
-
MFCのCArrayを使った二次元配列
-
Winsockを用いてデータを交互に...
-
C#で配列が空かを判定するには?
-
fclose()でセグメンテーション違反
-
C#で構造体の配列を持った構造...
-
C言語から質問です。
-
MFC - ダイアログボックスのPic...
-
コンボボックスでデフォルト値...
-
無作為に選択
-
「互換でない型変換」というエ...
-
define で 配列
-
c言語 構造体
-
C#でのフィボナッチ数列
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
関数から配列を返すには?
-
C言語において、 配列要素をひ...
-
配列の要素数に変数を入れたい...
-
構造体のextern方法
-
define で 配列
-
c言語
-
C#で構造体の配列を持った構造...
-
C言語の2次元配列 容量が大き...
-
c言語 構造体
-
C言語 ファイルの指定された行...
-
C言語についてです 5人のテスト...
-
int i, int i[1];
-
fclose()でセグメンテーション違反
-
char型配列をint型に代入するには
-
C言語から質問です。
-
Cのエラー
-
コンボボックスでデフォルト値...
-
C言語の課題が出たのですが自力...
-
MFCのCArrayを使った二次元配列
-
[C++]const int と配列
おすすめ情報