質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.49%

c言語 二分探索のInsert 二重登録されてしまう

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 1,461

score 14

二分探索のSearch,Insert,Deleteを作成しています.
Search,Deleteはうまく作動しています.
Insertの仕様が,二重登録はしないなのですが二重登録されてしまいます.
色々試してみたのですがうまくできません.
アドバイスお願いします.


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

#define dTextSize (1000000)
#define dLineSize (100000)
#define dBuffSize (1024)
#define dTrue (1)
#define dFalse (-1)

void InitText(char *text);
void InitLine(char *x[]);
int TextSet(char *text, FILE *fp1);
int LineSet(char *text, char *x[], int n);
void Sort(char *x[],int n);
int Search(char *x[], char *key, int n, int *pos);
int Delete(char *x[], char *key, int *n, int *pos);
int Insert(char *x[], char *key, int *n, int pos, char *text);
void Dump(char *x[]);

int sum=0;
int q = 0;

int main(int argc, char *argv[]){
    FILE *fp1, *fp2;
    int i, n1, n2, pos;
    int log, ave, command, sift, tmp, sumsift;
    char text1[dTextSize];
    char text2[dTextSize];
    char *x[dLineSize];
    char *key[dLineSize];
    
    InitText(text1);
    InitText(text2);
    InitLine(x);
    InitLine(key);
    
    fp1 = fopen(argv[1],"r");
    fp2 = fopen(argv[2],"r");
    
    n1 = TextSet(text1, fp1);
    n2 = TextSet(text2, fp2);
    
    if(LineSet(text1, x, n1) != dTrue){
        printf("LineSet Error\n");
        exit(1);
    }
    Sort(x, n1);
    if(LineSet(text2, key, n2) != dTrue){
        printf("LineSet Error\n");
        exit(1);
    }
    
    if(strcmp(argv[3], "-s") == 0)
        command = 1;
    if(strcmp(argv[3], "-i") == 0)
        command = 2;
    if(strcmp(argv[3], "-d") == 0)
        command = 3;
    
    switch(command){
        
        case 1:
            for(i = 0; key[i] != NULL; i++){
                if(Search(x, key[i], n1, &pos) == dFalse)
                    printf("%d\n",++q);
            }
            printf("%d\n",sum);
            ave = sum/n2;
            printf("%d\n",ave);
            break;
        
        case 2:
            for(i = 0; key[i] != NULL; i++){
                if(Search(x, key[i], n1, &pos) == dFalse){
                    sift = Insert(x, key[i], &n1, pos, text1);
                    sumsift +=  sift;
                }
            }
            printf("%d\n",sumsift);
            ave = sumsift/n2;
            break;
            
        case 3:
            for(i = 0; key[i] != NULL; i++){
                if((sift = Delete(x, key[i], &n1, &pos)) != dFalse)
                    sumsift += sift;
            }
            printf("%d\n",sumsift);
            break;
    }
            
    fclose(fp1);
    fclose(fp2);
    
    return 0;
}    

void InitText(char *text){
    int i;
    for(i = 0; i < dTextSize; i++)
        text[i] = '\0';
}

void InitLine(char *x[]){
    int i;
    for(i = 0; i < dLineSize; i++)
        x[i] = NULL;
}

int TextSet(char *text, FILE *fp1){
    char buff[dBuffSize];
    int i;
    
    for(i = 0; fgets(buff, dBuffSize, fp1) != NULL; text = text + (strlen(buff) + 1), i++)
        strcpy(text, buff);
        
    return i;
}

int LineSet(char *text, char *x[], int n){
    int i;
    for(i = 0; i < n; i++, text = text + (strlen(text) + 1))
        x[i] = text;
    
    return dTrue;
}

void Sort(char *x[],int n){
    int i, j;
    char *tmp;
    
    for(i = 0; i < n; i++){
        for(j = n-1; j > 0; j--){
            if(strcmp(x[j], x[j-1]) < 0){
                tmp = x[j];
                x[j] = x[j-1];
                x[j-1] = tmp;
            }
        }
    }
}

int Search(char *x[], char *key, int n, int *pos){
    int low = 0, high = n - 1;
    int cnt = 1;
    while(low <= high){
        int middle = (low + high) / 2;
        if(strcmp(key, x[middle]) < 0){
            high = middle - 1;
            cnt++;
        }
        else if(strcmp(key, x[middle]) > 0){
            low = middle + 1;
            cnt++;
        }
        else{
            sum += cnt;
            return middle;
        }
    }
    *pos = low;
    sum += cnt;
    return dFalse;
}

int Delete(char *x[], char *key, int *n, int *pos){
    int target;
    int i;
    int cnt = 0;

    if((target = Search(x, key, *n, pos)) != dFalse){
        for(i = target; i < (*n -1); i++){
            x[i] = x[i+1];
            cnt++;
        }
        x[i] = NULL;
        *n = *n - 1;
        return cnt;
    }
    return dFalse;
}
    
int Insert(char *x[], char *key, int *n, int pos, char *text){
    int i, sift;
    char *tmp;
    
    text = x[(*n)-1];
    text = text + (strlen(text) + 1);
    strcpy(text, key);
    tmp = text;
    for(i = *n, sift = 0; i > pos; i--, sift++){
        x[i] = x[i-1];
    }
    x[i] = tmp;
    *n = *n + 1;
    return sift;
}    

    

void Dump(char *x[]){
    int i;
    for(i = 0; x[i] != NULL; i++)
         printf("%d %s",i+1,x[i]);
}         
>
コード
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

複数の単語がAに追加されるようにしたところ、重複が発生しました。
原因は、追加する文字列の格納に使用されるバッファが、xの末尾が指す領域の次を使用するためです。
しかし、xはソートされているため、xの順序とバッファ内の並びは異なるので、意図せぬバッファ領域にkeyの文字列がコピーされてしまいます。
試しに、keyの文字列をコピーせずにそのままxの指定場所に代入するようにコードを修正したところ、重複は解消しました。
int Insert(char *x[], char *key, int *n, int pos){
    int i, sift;
    char *tmp;

    //text = x[(*n) - 1];
    //text = text + (strlen(text) + 1);
    //strcpy_s(text, dBuffSize, key);
    //tmp = text;
    tmp = key;
    for (i = *n, sift = 0; i > pos; i--, sift++){
        x[i] = x[i - 1];
    }
    x[i] = tmp;
    *n = *n + 1;
    return sift;
}
この場合、コピー先のバッファ領域textは不要になります。
と言うか、xの末尾が指す領域をまず代入してしまうので(text = x[(*n) - 1];)、最初から不要な引数でした。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/02/17 17:44

    ありがとうございます.
    解決しました.
    仰る通りで,textは不要でした.

    キャンセル

+1

まず、main関数の中で宣言している変数が一つも初期化されていないのが気になります。特に、sumsiftはそのまま値が加算されているので、予期しない値となりえます。
次に、text1,text2の配列を自力でポインタ演算を使って切り分けてx,keyに格納していますが、かなり危険なやり方です。読み込む文字列の最大長をdBuffSizeで指定しているのなら、下記のように2次元配列にした方が確実で、コードも読みやすくなるはずです。
char text1[dTextSize][dBuffSize];
...
for(i=0;fgets(&text1[i][0], dBuffSize, fp1)!=NULL;i++){
...
x[i] = &text1[i][0];
それから、肝心の二重登録ですが、どのようなデータファイルを使った時に起こるのかが分らないと調べようがありません。こちらで適当なファイルを作って試してみましたが、そうした現象は再現しませんでした。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/02/15 22:11

    ありがとうございます.
    2次元配列も試してみたいと思います.
    しかし,やはり二重登録されてしまいます...
    具体的には,Bの最後の単語が何回も挿入されています.

    キャンセル

  • 2015/02/15 22:53

    この場合、AとBの単語の重なり具合はどの程度でしょうか?
    単語数を減らしても再現するのか、重複が発生する閾値があるのかが知りたいところです。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.49%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る