| ← Июнь 2012 → | ||||||
|
1
|
||||||
|
5
|
6
|
|||||
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
|
19
|
20
|
21
|
22
|
23
|
24
|
|
|
25
|
26
|
27
|
28
|
29
|
30
|
|
За последние 60 дней ни разу не выходила
Сайт рассылки:
http://prog.rusfaq.ru/C
Открыта:
14-03-2002
Статистика
0 за неделю
RFpro.ru: Программирование на C / C++
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты по данной тематике
/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++
Консультация # 186334: Здравствуйте, уважаемые эксперты! Прошу помочь с последней работой в семестре! Требуется составить программу на языке Си с использованием процедур и функций для сортировки таблицы заданным методом и двоичного поиска по ключу в таблице. Программа должна вводить значения элементов неупорядоченной таблицы и проверять работу процедуры сортир... Здравствуйте, уважаемые эксперты! Прошу помочь с последней работой в семестре! Код : #ifndef _TABLE_ELEMENT_H_
#define _TABLE_ELEMENT_H_
struct s_table_element {
char key[3];
int val_size;
char* val;
};
typedef struct s_table_element TableElement;
int cmp_elements(TableElement, TableElement);
int read_element(TableElement*);
int read_key(TableElement*);
void print_element(TableElement);
void print_key(TableElement e);
void clone_element(TableElement, TableElement*);
#endiftable_element.c Код : #include "table_element.h"
#include <stdio.h>
#include <stdlib.h>
int cmp_elements(TableElement a, TableElement b) {
int i;
for (i = 0; i < 3; i++) {
if (a.key[i] < b.key[i]) {
return -1;
} else if (a.key[i] > b.key[i]) {
return 1;
}
}
return 0;
}
int is_space(char c) {
return c == ' ' || c == '\n';
}
int read_key(TableElement* e) {
int i;
char c;
/* key does not begin with space */
do {
if (scanf("%c", &c) != 1) {
return 0;
}
} while (is_space(c));
e->key[0] = c;
/* read rest of key's symbols */
for (i = 1; i < 3; i++) {
if (scanf("%c", &(e->key[i])) != 1) {
return 0;
}
}
return 1;
}
int read_value(TableElement* e) {
int i;
char c;
e->val_size = 8;
e->val = malloc(sizeof(char)*e->val_size);
/* value can begin with anything */
i = 0;
while (1) {
c = getchar();
if (i == e->val_size) {
e->val_size *= 2;
e->val = realloc(e->val, sizeof(char)*e->val_size);
}
if (c == EOF || c == '\n' || c == '\0') {
e->val[i] = '\0';
e->val_size = i + 1;
e->val = realloc(e->val, sizeof(char)*e->val_size);
return i;
}
e->val[i] = c;
i++;
}
}
int read_element(TableElement* e) {
/*Expect that key and value are divided with
some space simbol, but only one*/
return read_key(e) && getchar() && read_value(e);
}
void print_key(TableElement e) {
int i;
for (i = 0; i < 3; i++) {
printf("%c", e.key[i]);
}
}
void print_value(TableElement e) {
printf("%s", e.val);
}
void print_element(TableElement e) {
print_key(e);
putchar(' ');
print_value(e);
printf("\n");
}
void clone_element(TableElement e, TableElement* new) {
int i;
for (i = 0; i < 3; i++) {
new->key[i] = e.key[i];
}
new->val_size = e.val_size;
new->val = malloc(sizeof(char)*new->val_size);
for (i = 0; i < new->val_size; i++) {
new->val[i] = e.val[i];
}
}table.h Код : #ifndef _TABLE_H_
#define _TABLE_H_
#include "table_element.h"
struct s_table {
TableElement* elements;
int size;
};
typedef struct s_table Table;
int read_table(Table*);
void print_table(Table);
int search_binary(Table, TableElement, TableElement*);
int sort_table(Table*, int* n_swaps, int* n_cmps);
#endiftable.c Код : #include "table.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int read_table(Table* t) {
int i;
if (scanf("%d", &(t->size)) != 1) {
return 0;
}
if (t->size < 0) {
return 0;
}
t->elements = malloc(sizeof(TableElement)*t->size);
for (i = 0; i < t->size; i++) {
read_element(&(t->elements[i]));
}
return t->size;
}
void print_table(Table t) {
int i;
for (i = 0; i < t.size; i++) {
print_element(t.elements[i]);
}
}
int search_binary(Table t, TableElement key, TableElement* result) {
int l = 0;
int r = t.size - 1;
int m;
int cmp;
if (t.size < 1) {
return 0;
}
while (l <= r) {
m = (r + l) / 2;
cmp = cmp_elements(key, t.elements[m]);
if (cmp == 0) {
clone_element(t.elements[m], result);
return 1;
} else if (cmp > 0) {
l = m + 1;
} else {
r = m - 1;
}
}
return 0;
}
int is_sorted(Table* t, int* n_cmps) {
int i;
for (i = 0; i < t->size - 1; i++) {
(*n_cmps)++;
if (cmp_elements(t->elements[i], t->elements[i + 1]) == 1) {
return 0;
}
}
return 1;
}
int sort_table(Table* t, int* n_swaps, int* n_cmps) {
srand ( time(NULL) );
while (!is_sorted(t, n_cmps)) {
int i1 = rand() % t->size;
int i2 = rand() % t->size;
TableElement e;
(*n_swaps)++;
/* swap random elements */
clone_element(t->elements[i1], &e);
clone_element(t->elements[i2], &(t->elements[i1]));
clone_element(e, &(t->elements[i2]));
}
return 1;
}
main.c Код : #include "table.h"
#include "table_element.h"
#include <stdio.h>
int main() {
Table t;
int res;
TableElement e;
TableElement key;
int swaps, cmps;
swaps = cmps = 0;
read_table(&t);
printf("===Считанная таблица===\n");
print_table(t);
sort_table(&t, &swaps, &cmps);
printf("===Отсортированная таблица===\n");
print_table(t);
printf("Sorted in %d cmps and %d swaps\n", cmps, swaps);
printf("===Поиск ключей===\n");
while (1) {
res = read_key(&key);
if (!res) {
break;
}
res = search_binary(t, key, &e);
if (res) {
print_element(e);
} else {
printf("err\n");
}
}
return 0;
}Makefile Код : CC = gcc LD = gcc CFLAGS = -ansi -Wall -pedantic -c LFLAGS = -o $(PROGRAMM) PROGRAMM = prog FILES = main.o table.o table_element.o all: $(PROGRAMM) $(PROGRAMM): $(FILES) $(LD) $(LFLAGS) $(FILES) clean: rm -f *.o $(PROGRAMM) c.o: $(CC) $(CFLAGS) $< test: all ./$(PROGRAMM) < test1 ./$(PROGRAMM) < test2 table.o: table.h table_element.h table_element.o: table_element.h main.o: table.h table_element.h test1 Код : 7 123 --- 234 | | 345 --- 456 | | 567 --- 678 факультет 789 МЭИ 1__ 123 234 345 456 567 678 789 890 346 test2 Код : 7 234 | | 235 --- 456 факультет 123 --- 125 --- 789 МЭИ 124 | | 1__ 123 234 345 456 567 678 789 890 346 Уважаемые эксперты, я уже много раз обращался с помощью на Ваш портал в тему программированния.Но не потому, что я ленивый бездарь, а потому, что я многое упустил и запустил, я понимаю программы, но для меня затруднительно их писать. Этот вопрос - последний, который я собираюсь задавать, и ответ на него напрямую влияет на допуск к экзамену, который будет через 2 дня. Прошу еще раз выручить меня, как вы неоднократно уже это делали. Заранее огромное спасибо тем экспертам, которые отреагируют на этот вопрос! С уважением, Иван.
Дата отправки: 06.06.2012, 23:29 Консультирует Киселёва Алёна aka Verena (Академик): Здравствуйте, Барс Иван! Код : int sort_table(Table* t, int* n_swaps, int* n_cmps) {
int i, j;
for(i = 0 ; i < t->size ; i++) {
// сравниваем два соседних элемента.
for(j = 0 ; j < t->size - i - 1 ; j++) {
(*n_cmps)++;//увеличиваем число сравнений
if(cmp_elements(t->elements[j], t->elements[j + 1]) == 1) {
// если они идут в неправильном порядке, то
// меняем их местами.
TableElement e;
(*n_swaps)++;//увеличиваем число обменов
clone_element(t->elements[j], &e);
clone_element(t->elements[j+1], &(t->elements[j]));
clone_element(e, &(t->elements[j+1]));
}
}
}
return 1;
}2. Комментарии, немножко. Код : int cmp_elements(TableElement a, TableElement b) { //сравнение двух эл-в таблицы
int i;
for (i = 0; i < 3; i++) { //посимвольнок сравнение ключа
if (a.key[i] < b.key[i]) {
return -1; //если а меньше
} else if (a.key[i] > b.key[i]) {
return 1; //если а больше
}
}
return 0; //если ключи совпали
}
int is_space(char c) { //проверка символа на пробел или перенос строки
return c == ' ' || c == '\n';
}
int read_key(TableElement* e) {//заполнение ключа элемента с клавиатуры
int i;
char c;
/* key does not begin with space */
do {
if (scanf("%c", &c) != 1) {
return 0;
}
} while (is_space(c));
e->key[0] = c;
/* read rest of key's symbols */
for (i = 1; i < 3; i++) {
if (scanf("%c", &(e->key[i])) != 1) {
return 0;
}
}
return 1;
}
int read_value(TableElement* e) { //заполнение значения элемента с клавиатуры
int i;
char c;
e->val_size = 8;
e->val = malloc(sizeof(char)*e->val_size); //выделение памяти
/* value can begin with anything */
i = 0;
while (1) {
c = getchar();
if (i == e->val_size) {
e->val_size *= 2;
e->val = realloc(e->val, sizeof(char)*e->val_size); //перевыделение памяти
}
if (c == EOF || c == '\n' || c == '\0') {
e->val[i] = '\0';
e->val_size = i + 1;
e->val = realloc(e->val, sizeof(char)*e->val_size);
return i;
}
e->val[i] = c;
i++;
}
}
int read_element(TableElement* e) { //чтение всего элемента
/*Expect that key and value are divided with
some space simbol, but only one*/
return read_key(e) && getchar() && read_value(e);
}
void print_key(TableElement e) { //печать ключа
int i;
for (i = 0; i < 3; i++) { //посимвольно, потому что у него нет 0 на конце
printf("%c", e.key[i]);
}
}
void print_value(TableElement e) { //печать значения
printf("%s", e.val);
}
void print_element(TableElement e) { //печать элемента
print_key(e);
putchar(' ');
print_value(e);
printf("\n");
}
void clone_element(TableElement e, TableElement* new) {//копирование элемента
int i;
for (i = 0; i < 3; i++) {
new->key[i] = e.key[i];
}
new->val_size = e.val_size;
new->val = malloc(sizeof(char)*new->val_size);
for (i = 0; i < new->val_size; i++) {
new->val[i] = e.val[i];
}
}Код : int read_table(Table* t) { //чтение таблицы
int i;
if (scanf("%d", &(t->size)) != 1) {//получаем размер
return 0;
}
if (t->size < 0) {
return 0;
}
t->elements = malloc(sizeof(TableElement)*t->size); //выделяем память
for (i = 0; i < t->size; i++) {
read_element(&(t->elements[i]));
}
return t->size;
}
void print_table(Table t) { //вывод таблицы в консоль
int i;
for (i = 0; i < t.size; i++) {
print_element(t.elements[i]);
}
}
int search_binary(Table t, TableElement key, TableElement* result) { //бинарный поиск
int l = 0; //левая граница
int r = t.size - 1; //правая
int m;
int cmp;
if (t.size < 1) {
return 0;
}
while (l <= r) { //пока не дойдём до правой
m = (r + l) / 2; //находим середину
cmp = cmp_elements(key, t.elements[m]); //сравниваем с ключом
if (cmp == 0) { //нашли
clone_element(t.elements[m], result); //копируем
return 1; //выходим
} else if (cmp > 0) { //не нашли и ключ больше
l = m + 1; //сдвигаем левую границу в середину
} else { //ключ меньше
r = m - 1; //правую границу
}
}
return 0;
}
int is_sorted(Table* t, int* n_cmps) { //проверка на упорядоченность
int i;
for (i = 0; i < t->size - 1; i++) {
(*n_cmps)++;
if (cmp_elements(t->elements[i], t->elements[i + 1]) == 1) { //если хоть одна пара не упорядочена
return 0;
}
}
return 1;
}
Удачи!
Оценить выпуск | Задать вопрос экспертам
главная страница
|
стать участником
|
получить консультацию
© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Версия системы: 2011.6.36 от 26.01.2012 |
| В избранное | ||
