こんにちは。

フリーのC言語のライブラリを紹介してください。

ファイル同士のマッチングやら、あるレコードの検索などC言語で
開発することになりました。

大量のデータで行なうため、なるたけ早いロジックを組まないといけません。
検索方法については、よく情報処理試験等で出てくる2分探索とか
ハッシュ法などを使用したいと思うのですが。

いちから作成するのは大変なので、市販で出回っているライブラリなど
ありましたらご紹介していただけないでしょうか?
できたら、フリーソフトがいいのですが(安価であれば購入も考えています)、どなかたか知り得ているかたよろしくお願いします。

環境はUNIXなのですが、Windows版でもかまいません。

このQ&Aに関連する最新のQ&A

A 回答 (3件)

UNIXってことはGCCですか?



ハッシュ検索も2分探索もGCCのライブラリに標準で含まれます。

2分検索;bsearch
ハッシュ:hsearsh,hcreate,hdestroy

使い方はmanで調べてください。
    • good
    • 0
この回答へのお礼

ライブラリにあるなんて知りませんでした。
どうもありがとうございます。

専門的な方だと思われますので、もうひとつお願いします。m(__)m

テーブルサイズを小さくすると、既存のレコードが上書き(なくなる)のような
動きを見せます。テーブルを大きくすればいいんでしょうが、若干ハッシュテーブルの仕様がわからないのが心配です。

そのあたりの仕様がmanでみると
hsearch() is a hash-table search routine generalized from
Knuth (6.4) Algorithm D.
とあります。

Knuth (6.4) Algorithm D.ってどこに出てるかご存知ですか?

お礼日時:2002/04/16 14:29

前記回答がリンクされ損ねていたので


下のURLから
左上の
[解説(良本紹介など)]→”アルゴリズムとデータ構造”
で、また左上の
[アルゴリズムとデータ構造書籍一覧  目次へ]
から

参考URL:http://www.yfcbookshelf.com/
    • good
    • 0

本屋の本を1冊持っとくと便利じゃないかと。


「C言語による最新アルゴリズム事典」
  技術評論社 奥村 晴彦 著
「C言語で書くアルゴリズム」
  ソフトバンクパブリッシング
  Andrew Binstock/John Rex 著
  岩谷 宏 訳
とか、いろいろあるみたいです。
詳しくは参考URLを。


WEB上で直接ソースを探すなら、

[YAHOO>コンピュータとインターネット > ソフト
ウェア > プログラミングツール > プログラミング言
語 > CとC++] 下で
「The Collection Of Algorithms」



「C言語によるアルゴリズム(コメント付き)」(この
まんまのキーワードでYAHOO検索)
なんてのもありました
(誰かの保管サイトらしいので、ほどほどのところに。
 txtがもし見れなければ保存してからブラウザに放り
 込めばOK)

など『2分探索 C』あたりで検索かけたりすると
いくつかあるみたいです。

フリーウェア...ではあるかどうか知りませんが、
サンプルを探して使う程度で良いんじゃないでしょうか。

参考URL:http://www.yfcbookshelf.com/algorithms%20mokuji. …
    • good
    • 0
この回答へのお礼

どうもありがとうございました

お礼日時:2002/04/30 15:38

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qハッシュ(オープンアドレス法) C言語の課題

努力はしてみたのですが、C言語の課題ができません。教えていただけないでしょうか。

問:名前と年齢を入力し、名前をキーとしてハッシュ(オープンアドレス法)に登録する。'-'が入力されると登録を終了し、次に入力された名前をハッシュ法で検索し、あればその人のデータをハッシュから削除する、その後、ハッシュ表の内容を出力するプログラムを作成せよ。ただしハッシュ表の大きさは5とする。


koizumi  入力
1     入力
fukuda  入力
2  入力
aso 入力
3     入力
-     入力
koizumi  入力
fukuda(2) 出力
aso(3) 出力



ハッシュ関数は
int hash(char *name)
{
int ret=0;
while (*name)ret += *name++;
return ret%5;
}

再ハッシュ関数は
int rehash(int h)
{
return (h+1)%5;
}
を使おうと考えています。


内容を理解できないと困るので簡単なプログラムをお願いします。
よろしくお願いします。

努力はしてみたのですが、C言語の課題ができません。教えていただけないでしょうか。

問:名前と年齢を入力し、名前をキーとしてハッシュ(オープンアドレス法)に登録する。'-'が入力されると登録を終了し、次に入力された名前をハッシュ法で検索し、あればその人のデータをハッシュから削除する、その後、ハッシュ表の内容を出力するプログラムを作成せよ。ただしハッシュ表の大きさは5とする。


koizumi  入力
1     入力
fukuda  入力
2  入力
aso 入力
3     ...続きを読む

Aベストアンサー

ちょっと難しくなったかもしれませんが
質問者さんなら解かると思います。

ずらし処理を抜いてシンプルにしています。

補足なのですが、氏名をキーにすると氏名そのものを
直接、照合すればいいのでキーの意味を持ちません。
本来はハッシュキー値をキーにして照合させ、候補される
複数の氏前をユーザ選択させる方式の方が妥当かと思いますが
以下リストは、あえて氏名文字列を利用した冗長処理にしています。

<リスト>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int hash(char *name)
{
int ret=0;

while (*name)ret += *name++;
return ret%5;
}

int rehash(int h)
{
return (h+1)%5;
}

void err_disp()
{
printf("\n別キーが使用済みです。\n");
}

int main()
{
int key[5],age[5],i,k,c=0,err;
char name[5][15],temp[15];

for (i=0;i<5;i++) key[i]=-1,age[i]=0,name[i][0]=0;
i=0;
while (1)
{
printf("氏名?");
scanf("%s15",temp);
if (*temp=='-' && !*(temp+1)) break;
k=i=hash(temp),err=0;
if (*name[i] && key[i]!=k) {err_disp();break;}
while (*name[i] && key[i]==k)
{
if (k==(i=rehash(i)) || *name[i] && key[i]!=k) err=1;
}
if (err) {err_disp();break;}
strcpy(name[i],temp);
key[i]=k;
printf("年齢?");
scanf("%3d",&age[i]);
if (++c>=5) break;
}

printf("\n検索氏名?");
scanf("%s15",temp);
printf("\n");
for (k=i=hash(temp);k==key[i];i=++i%5)
{
if (!strcmp(temp,name[i])) *name[i]=0;
}
for (i=0;i<5;i++)
{
if (*name[i]) printf("%s %d歳\n",name[i],age[i]);
}
return 0;
}

ちょっと難しくなったかもしれませんが
質問者さんなら解かると思います。

ずらし処理を抜いてシンプルにしています。

補足なのですが、氏名をキーにすると氏名そのものを
直接、照合すればいいのでキーの意味を持ちません。
本来はハッシュキー値をキーにして照合させ、候補される
複数の氏前をユーザ選択させる方式の方が妥当かと思いますが
以下リストは、あえて氏名文字列を利用した冗長処理にしています。

<リスト>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int...続きを読む

QC言語 探索に関して

C言語探索プログラムについて質問です。

#include <stdio.h>
#define MAXSIZE 100

void swapData(int *x, int *y){
int tmp;

tmp = *x;
*x = *y;
*y = tmp;
}

void simpleSort(int data[], int first, int last)
{
int i, j;
for(i = first; i < last; i++){
for(j = i+1; j <= last; j++){
if(data[i] > data[j]) {
swapData(&data[i], &data[j]);

}
}
}
}

int ArrayBinarySearch(int data[], int n, int x)
{
int left = 0, right = n - 1, center;

while(left <= right){
center = (left + right)/2;
if(data[center]=x){
return center;
}else if(x > data[center]){
left = center + 1;
}else if(x < data[center]){
right = center - 1;
}
}

return -1;
}

int main(int argc, char *argv[])
{

int data[MAXSIZE];
int i, x;
FILE *fp;

scanf("%d", &x);

fp = fopen(argv[1], "r");

for(i = 0; i < MAXSIZE; i++)
{
if (fscanf(fp,"%d", &data[i]) == EOF)
break;
}

simpleSort(data, 0, i-1);
printf("%d", ArrayBinarySearch(data, i, x ));

return 0;
}

数値が書かれたファイルを読み込んでソートした後に二分探索を行うプログラムをつくったのですが、うまく動きません。
どこがおかしいか教えてください。
お願いいたします。
ちなみに関数ArrayBinarySearchは目的の値が見つかれば配列中でのインデックスを、見つからない場合は-1を返す関数にしているつもりです。

C言語探索プログラムについて質問です。

#include <stdio.h>
#define MAXSIZE 100

void swapData(int *x, int *y){
int tmp;

tmp = *x;
*x = *y;
*y = tmp;
}

void simpleSort(int data[], int first, int last)
{
int i, j;
for(i = first; i < last; i++){
for(j = i+1; j <= last; j++){
if(data[i] > data[j]) {
swapData(&data[i], &data[j]);

}
}
}
}

int ArrayBinarySearch(int data[], int n, int x)
{
int left = 0, right = n - 1, center;

while(left <= right){
center = (left + right)/2;
if...続きを読む

Aベストアンサー

int ArrayBinarySearch(int data[], int n, int x)
{
int left = 0, right = n - 1, center;

while(left <= right){
center = (left + right)/2;
if(data[center]=x){ /* ココ */
return center;
}else if(x > data[center]){
left = center + 1;
}else if(x < data[center]){
right = center - 1;
}
}

これだとXの値を代入して、そのXの値でif文を判定してしまいます。
正しくは
if(data[center]==x){
です。まぁ、よくある間違いですね。

Q迷路を脱出する経路探索プログラムをC言語で作成するには?

迷路を脱出する経路を探索するプログラムを作成したいのですが、
何をすればいいのかまったくわかりません、
サンプルプログラムや解決ヒント等、
データの提供お願いします。
かなりこまってます。

Aベストアンサー

私も、部活で迷路脱出のプログラムを最近作りました。そのときには、本を参考に再起処理を使って作りました。
一応サンプルプログラムです。
#include<stdio.h>
int meiro[][]={{ 省略 }};

int Si,Sj,Ei,Ej,success,sp,ri[100],rj[100];

int tansaku(int,int);

main()
{
sp=0;
success=0;
Si=1; Sj=1; Ei=7; Ej=7;

printf("\n迷路の探索");
if(tansaku(Si,Sj)==0){
//出口が見つからなかった
}
}
int tansaku(int i,int j)
{
int k;
static int path=1;

meiro[i][j]=1;
ri[sp]=i; rj[sp]=j; sp++;

if(i==Ei && j==Ej){
//出口が見つかった時の処理
//この時点で、ri,rjに経路が記録されている
success=1;
}//全経路検索 一度通ったところは通らない
if(meiro[i][j+1]==0) tansaku(i,j+1);
if(meiro[i+1][j]==0) tansaku(i+1,j);
if(meiro[i][j-1]==0) tansaku(i,j-1);
if(meiro[i-1][j]==0) tansaku(i-1,j);

sp--;
meiro[i][j]=0; //別経路探索のため
return(success);
}

確か本を参考に、こんなプログラムを作ったはずです。
ソースは、学校のパソコンに保存されているので性格かはわかりませんが・・・。
一応再起処理で全経路を検索しますが、広い空間があるとうまくいかないことがありました。
meiro[][]の二次元配列は、0が通路、1が自分が通った通路、2が壁です。
このプログラムは、迷路を壁で囲ってある状態にしていないと無限ループになるので、そこも注意してください。
迷路が大きいと時間がかかってしまうので、途中で中断できるようになればそれなりのものができると思います。

この回答を、投稿の前に確認したところ、字下げしたのがすべて無視されてました。
字下げなしの見にくいプログラムになってしまい、すみません。

私も、部活で迷路脱出のプログラムを最近作りました。そのときには、本を参考に再起処理を使って作りました。
一応サンプルプログラムです。
#include<stdio.h>
int meiro[][]={{ 省略 }};

int Si,Sj,Ei,Ej,success,sp,ri[100],rj[100];

int tansaku(int,int);

main()
{
sp=0;
success=0;
Si=1; Sj=1; Ei=7; Ej=7;

printf("\n迷路の探索");
if(tansaku(Si,Sj)==0){
//出口が見つからなかった
}
}
int tansaku(int i,int j)
{
int k;
static int path=...続きを読む

Q文字列探索アルゴリズム(Aho Corasick法)をC言語で組みたい

はじめまして。

標題のとおり、
文字列探索アルゴリズム(Aho Corasick法)をC言語で組みたいと考えています。
簡単なコード例か、どこか情報元はありませんでしょうか?

文字列「あかさたなはまやらわ」から
キーワード「あか」・「たな」を探して
出力として、
「あか」…インデックス0
「たな」…インデックス3
となるようなイメージのプログラミングです。

詳しい方がおりましたら、何卒ご教授お願い致します。

Aベストアンサー

有名なので検索するといっぱい出てきます。探せば色々な言語で実装したものや、論文や書籍などの解説も見付かります。

とりあえずぱっと見まとまってそうなサイト、
http://d.hatena.ne.jp/naoya/20090405

最初はスクリプトで組むというのは楽でいいです。そのあとCに書き起こしてチューニングとかはありです。

QC言語 線形探索

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXBUFFERSIZE 256

struct LinkedListNode{

int data;
struct LinkedListNode *next;
};

struct LinkedList{

int node_num;
struct LinkedListNode *head;
};


LinkedList *LinkedListMake(char *filename)
{
FILE *fp;
LinkedList *list;
char buffer[MAXBUFFERSIZE];

/* ファイル有無のチェック */
if ((fp = fopen(filename, "r")) == NULL) {
fprintf(stderr, "No Such File : %s\n", filename);
exit (1);
}

list = LinkedListAlloc();
if (list == NULL) { /* 領域確保失敗 */
exit (0); /* 終了 */
}

while (fgets(buffer, MAXBUFFERSIZE, fp)) { /* ファイル終端に到達するまでループ */
buffer[strlen(buffer) - 1] = '\0'; /* 改行文字を削除 */
LinkedListDataAdd(list, atoi(buffer));
}
fclose(fp);

return (list);
}

LinkedList *LinkedListAlloc(void)
{
LinkedList *list;

list = (LinkedList *)malloc(sizeof(LinkedList));
if (list == NULL) { /* 領域確保失敗 */
return (NULL);
}
list->node_num = 0;
list->head = NULL;
return (list);
}

LinkedListNode *LinkedListDataAdd(LinkedList *list, int x)
{
LinkedListNode *ptr; /* 注目するノードへのポインタ */
LinkedListNode *prev;
LinkedListNode *new_node;

ptr = list->head;
prev = NULL;

while (ptr) { /* 終端ノードに到達するまでループ */
if (ptr->data < x) {
prev = ptr; /* 直前ノードの更新 */
ptr = ptr->next; /* 注目ノードの更新 */
} else if (ptr->data == x) { /* x は登録済み */
return (NULL);
} else { /* x を注目ノードの直前に追加 */
new_node = LinkedListNodeAlloc();
if (new_node == NULL) { /* 領域確保失敗 */
exit (0); /* 終了 */
}
new_node->data = x;
new_node->next = ptr; /* ポインタの付け替え(注目ノードの直前) */
if (prev != NULL) { /* 連結リストの先頭以降に追加 */
prev->next = new_node; /* ポインタの付け替え */
} else { /* 連結リストの先頭に追加 */
list->head = new_node;
}
list->node_num++; /* ノード総数の更新 */
return (new_node);
}
}
/* 終端ノードに到達 */
/* x を終端に追加 */
new_node = LinkedListNodeAlloc();
if (new_node == NULL) { /* 領域確保失敗 */
exit (0); /* 終了 */
}
new_node->data = x;
new_node->next = NULL; /* new_node は新たな終端ノード */
if (prev != NULL) { /* list は少なくともひとつのノードを有している */
prev->next = new_node; /* 更新前の終端ノードの直後が new_node となる */
} else { /* list は空(ノードがひとつも含まれない) */
list->head = new_node;
}
list->node_num++; /* ノード総数の更新 */
return (new_node);
}

LinkedList *LinkedListSearch(LinkedList *list, int x)←ここがわかりません★
{

for(i = 0; i < node_num)

     ???



int main(int argc, char *argv[])
{

int a, i, x;


printf("xの値を入力");
scanf("%d", &x);


LinkedListMake(argv[1]);
LinkedListSearch(list, x);


連結リストに格納されたint型データから目的の値を線形探索するプログラムをつくってます。
連結リスト作成関数まではできたので、あと連結リストにおいて目的の値を線形探索する関数LinkedListSearchをつくればだいたい完成だと思うのですが、関数LinkedListSearchの作り方がわかりません。
引数で連結リストのポインタと目的値をとって、目的値が存在すればそのノードのポインタ、存在しない場合はNULLを返すようにするつもりです。
わかる方、是非とも教えてください!
お願いいたします。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXBUFFERSIZE 256

struct LinkedListNode{

int data;
struct LinkedListNode *next;
};

struct LinkedList{

int node_num;
struct LinkedListNode *head;
};


LinkedList *LinkedListMake(char *filename)
{
FILE *fp;
LinkedList *list;
char buffer[MAXBUFFERSIZE];

/* ファイル有無のチェック */
if ((fp = fopen(filename, "r")) == NULL) {
fprintf(stderr, "No Such File : %s\n", filename);...続きを読む

Aベストアンサー

こんな感じでどないですか?

LinkedListNode *LinkedListSearch(LinkedList *list, int x)
{
for( LinkedListNode* pNode = list->head;
pNode;
pNode = pNode->next )
{
if( pNode->data == x )
return pNode;
}

return NULL;
}


人気Q&Aランキング

おすすめ情報