1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
| /**********************************************************************
* laba9_string.c 15.11.2016
*
* Пользователь вводит с клавиатуры строку с разделителями в виде ' '.
* Надо выделить слова в предложении. Далее у пользователя запрашивается
* комбинация символов.
* Нужно методом двоичного поиска выяснить, есть ли это слово в строке.
**********************************************************************/
#include <stdio.h> /* printf, putchar, puts, gets */
#include <string.h> /* strcmp */
#include <stdlib.h> /* calloc, free */
#define WORDS 10 // максимум слов в предложении
#define SYMBOLS 10 // максимум символов в слове
int MyGetStr(char **);
void MySort(char **, int);
void MyBinarySearch(char **, int);
int main(void)
{
int i, all_words;
char **p;
// выделение памяти для вспомогательного массива указателей
p = calloc(WORDS, sizeof(char *));
// выделение памяти под каждое слово в предложении
for(i = 0; i < WORDS; i++) {
p[i] = calloc(SYMBOLS, sizeof(char));
}
printf("\n----- Введите слова (не более %d символов):\n", (WORDS * SYMBOLS) - 1);
// каждое слово в отдельный массив символов (создание словаря)
all_words = MyGetStr(p);
printf("\n----- Введены слова:\n");
for(i = 0; i < all_words; i++) {
putchar(' ');
puts(p[i]);
}
// сортировка массива указателей на слова
MySort(p, all_words);
printf("\n----- Указатели на слова отсортированы:\n");
for(i = 0; i < all_words; i++) {
putchar(' ');
puts(p[i]);
}
// запрос произвольного слова и поиск его в словаре
MyBinarySearch(p, all_words);
// освобождение памяти
for(i = 0; i < WORDS; i++)
free(p[i]);
free(p);
return 0;
}
/* Cчитывание потока символов и распределение по словам,
* пока не встретим символ конец строки '\n' */
int MyGetStr(char **p) {
const int OUT = 0;
const int IN = 1;
int state = OUT;
int c, j = 0, i = 0;
while((c = getchar()) != '\n') {
if(c == ' ') {
if(state == IN)
p[i][j] = '\0';
state = OUT; // устанавливаем состояние вне слова
} else if(state == OUT) {
state = IN;
j = 0;
p[i][j] = c; // первый символ слова
i++;
j++;
} else {
p[i-1][j] = c; // последующие символы слова
j++;
}
}
p[i][j] = '\0'; // признак конца строки для каждого слова
return i;
}
// сортировка массива указателей на слова
void MySort(char **p, int all_words)
{
size_t i, j;
for(i = 0; i < all_words - 1; i++) {
for(j = 0; j < all_words - 1 - i; j++){
if(strcmp(p[j], p[j+1]) > 0) {
char *tmp = p[j];
p[j] = p[j + 1];
p[j + 1] = tmp;
}
}
}
}
// поиск слова в массиве методом двоичного поиска
void MyBinarySearch(char **p, int all_words)
{
char find_word[SYMBOLS];
size_t left, right, flag, index = 0;
printf("\n Введите слово для поиска или '.' для завершения: ");
gets(find_word);
while(46 - find_word[0]) { // 46 - это код символа '.'
left = flag = 0;
right = all_words - 1;
while(left <= right) {
index = (left + right) >> 1;
if(strcmp(find_word, p[index]) < 0)
right = --index;
else if(strcmp(find_word, p[index]) > 0)
left = ++index;
else{
flag = 1;
break;
}
}
if(flag)
printf("\n\tСлово есть в словаре\n");
else
printf("\n\tСлова в словаре нет\n");
printf("\n Введите слово для поиска или '.' для завершения: ");
gets(find_word);
}
} |