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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

1845閲覧

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

naruakimizuno

総合スコア12

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2015/02/13 20:00

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

lang

1#include<stdlib.h> 2#include<string.h> 3 4#define dTextSize (1000000) 5#define dLineSize (100000) 6#define dBuffSize (1024) 7#define dTrue (1) 8#define dFalse (-1) 9 10void InitText(char *text); 11void InitLine(char *x[]); 12int TextSet(char *text, FILE *fp1); 13int LineSet(char *text, char *x[], int n); 14void Sort(char *x[],int n); 15int Search(char *x[], char *key, int n, int *pos); 16int Delete(char *x[], char *key, int *n, int *pos); 17int Insert(char *x[], char *key, int *n, int pos, char *text); 18void Dump(char *x[]); 19 20int sum=0; 21int q = 0; 22 23int main(int argc, char *argv[]){ 24 FILE *fp1, *fp2; 25 int i, n1, n2, pos; 26 int log, ave, command, sift, tmp, sumsift; 27 char text1[dTextSize]; 28 char text2[dTextSize]; 29 char *x[dLineSize]; 30 char *key[dLineSize]; 31 32 InitText(text1); 33 InitText(text2); 34 InitLine(x); 35 InitLine(key); 36 37 fp1 = fopen(argv[1],"r"); 38 fp2 = fopen(argv[2],"r"); 39 40 n1 = TextSet(text1, fp1); 41 n2 = TextSet(text2, fp2); 42 43 if(LineSet(text1, x, n1) != dTrue){ 44 printf("LineSet Error\n"); 45 exit(1); 46 } 47 Sort(x, n1); 48 if(LineSet(text2, key, n2) != dTrue){ 49 printf("LineSet Error\n"); 50 exit(1); 51 } 52 53 if(strcmp(argv[3], "-s") == 0) 54 command = 1; 55 if(strcmp(argv[3], "-i") == 0) 56 command = 2; 57 if(strcmp(argv[3], "-d") == 0) 58 command = 3; 59 60 switch(command){ 61 62 case 1: 63 for(i = 0; key[i] != NULL; i++){ 64 if(Search(x, key[i], n1, &pos) == dFalse) 65 printf("%d\n",++q); 66 } 67 printf("%d\n",sum); 68 ave = sum/n2; 69 printf("%d\n",ave); 70 break; 71 72 case 2: 73 for(i = 0; key[i] != NULL; i++){ 74 if(Search(x, key[i], n1, &pos) == dFalse){ 75 sift = Insert(x, key[i], &n1, pos, text1); 76 sumsift += sift; 77 } 78 } 79 printf("%d\n",sumsift); 80 ave = sumsift/n2; 81 break; 82 83 case 3: 84 for(i = 0; key[i] != NULL; i++){ 85 if((sift = Delete(x, key[i], &n1, &pos)) != dFalse) 86 sumsift += sift; 87 } 88 printf("%d\n",sumsift); 89 break; 90 } 91 92 fclose(fp1); 93 fclose(fp2); 94 95 return 0; 96} 97 98void InitText(char *text){ 99 int i; 100 for(i = 0; i < dTextSize; i++) 101 text[i] = '\0'; 102} 103 104void InitLine(char *x[]){ 105 int i; 106 for(i = 0; i < dLineSize; i++) 107 x[i] = NULL; 108} 109 110int TextSet(char *text, FILE *fp1){ 111 char buff[dBuffSize]; 112 int i; 113 114 for(i = 0; fgets(buff, dBuffSize, fp1) != NULL; text = text + (strlen(buff) + 1), i++) 115 strcpy(text, buff); 116 117 return i; 118} 119 120int LineSet(char *text, char *x[], int n){ 121 int i; 122 for(i = 0; i < n; i++, text = text + (strlen(text) + 1)) 123 x[i] = text; 124 125 return dTrue; 126} 127 128void Sort(char *x[],int n){ 129 int i, j; 130 char *tmp; 131 132 for(i = 0; i < n; i++){ 133 for(j = n-1; j > 0; j--){ 134 if(strcmp(x[j], x[j-1]) < 0){ 135 tmp = x[j]; 136 x[j] = x[j-1]; 137 x[j-1] = tmp; 138 } 139 } 140 } 141} 142 143int Search(char *x[], char *key, int n, int *pos){ 144 int low = 0, high = n - 1; 145 int cnt = 1; 146 while(low <= high){ 147 int middle = (low + high) / 2; 148 if(strcmp(key, x[middle]) < 0){ 149 high = middle - 1; 150 cnt++; 151 } 152 else if(strcmp(key, x[middle]) > 0){ 153 low = middle + 1; 154 cnt++; 155 } 156 else{ 157 sum += cnt; 158 return middle; 159 } 160 } 161 *pos = low; 162 sum += cnt; 163 return dFalse; 164} 165 166int Delete(char *x[], char *key, int *n, int *pos){ 167 int target; 168 int i; 169 int cnt = 0; 170 171 if((target = Search(x, key, *n, pos)) != dFalse){ 172 for(i = target; i < (*n -1); i++){ 173 x[i] = x[i+1]; 174 cnt++; 175 } 176 x[i] = NULL; 177 *n = *n - 1; 178 return cnt; 179 } 180 return dFalse; 181} 182 183int Insert(char *x[], char *key, int *n, int pos, char *text){ 184 int i, sift; 185 char *tmp; 186 187 text = x[(*n)-1]; 188 text = text + (strlen(text) + 1); 189 strcpy(text, key); 190 tmp = text; 191 for(i = *n, sift = 0; i > pos; i--, sift++){ 192 x[i] = x[i-1]; 193 } 194 x[i] = tmp; 195 *n = *n + 1; 196 return sift; 197} 198 199 200 201void Dump(char *x[]){ 202 int i; 203 for(i = 0; x[i] != NULL; i++) 204 printf("%d %s",i+1,x[i]); 205} 206207コード

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

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

lang

1int Insert(char *x[], char *key, int *n, int pos){ 2 int i, sift; 3 char *tmp; 4 5 //text = x[(*n) - 1]; 6 //text = text + (strlen(text) + 1); 7 //strcpy_s(text, dBuffSize, key); 8 //tmp = text; 9 tmp = key; 10 for (i = *n, sift = 0; i > pos; i--, sift++){ 11 x[i] = x[i - 1]; 12 } 13 x[i] = tmp; 14 *n = *n + 1; 15 return sift; 16}

この場合、コピー先のバッファ領域textは不要になります。
と言うか、xの末尾が指す領域をまず代入してしまうので(text = x[(*n) - 1];)、最初から不要な引数でした。

投稿2015/02/15 14:29

shinosan

総合スコア209

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

naruakimizuno

2015/02/17 08:44

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

0

まず、main関数の中で宣言している変数が一つも初期化されていないのが気になります。特に、sumsiftはそのまま値が加算されているので、予期しない値となりえます。
次に、text1,text2の配列を自力でポインタ演算を使って切り分けてx,keyに格納していますが、かなり危険なやり方です。読み込む文字列の最大長をdBuffSizeで指定しているのなら、下記のように2次元配列にした方が確実で、コードも読みやすくなるはずです。

lang

1char text1[dTextSize][dBuffSize]; 2... 3for(i=0;fgets(&text1[i][0], dBuffSize, fp1)!=NULL;i++){ 4... 5x[i] = &text1[i][0];

それから、肝心の二重登録ですが、どのようなデータファイルを使った時に起こるのかが分らないと調べようがありません。こちらで適当なファイルを作って試してみましたが、そうした現象は再現しませんでした。

投稿2015/02/15 04:41

shinosan

総合スコア209

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

naruakimizuno

2015/02/15 13:11

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

2015/02/15 13:53

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問