Форматирование текстового файла

Размещено на http://www.allbest.ru/

Кафедра автоматики и вычислительной техники

Курсовая работа

Форматирование текстового файла

по дисциплине «Информатика»

Содержание

1. Постановка задачи

2. Содержательное описание структур данных и алгоритмы

2.1 Алгоритм разбора строки на слова

2.2 Алгоритм подсчета повторяющихся слов

3. Основные алгоритмы



1. Постановка задачи

алгоритм структура данные динамический

Выходной файл представляет собой HTML-документ, с требуемым по заданию табличным представлением данных, либо наличием ссылок на выделяемые фрагменты. Входной файл - txt файл. Для сохранения данных об исходном тексте (слова, частоты их появления, номера абзацев) использовать динамические структуры данных (динамические массивы, массивы указателей, списки).

Программа подсчитывает частоты появления слов в тексте. Формируется таблица из первых n наиболее часто встречающихся слов, в таблице содержится само слово и ссылки на все абзацы, где оно появляется.

2. Содержательное описание структур данных и алгоритмов

Все слова из текстового файла загружаются в односвязный список, структура которого выглядит следующим образом:

struct all_words {

char *str; //Указатель на слово

int num; //Номер абзаца, где находится данное слово

struct all_words *next; //Указатель на следующий элемент списка

};

После загрузки всех слов в память, начинается подсчет частоты появления слов в тексте, в результате строится еще один односвязный список со следующей структурой:

struct povtor_words {

char *str; //Указатель на слово

int num[500]; //Массив номеров абзацев, где встречается слово

int ab; //Число уникальных абзацев

int povtor; //Число повторов

struct povtor_words *next; //Указатель на следующий элемент //списка

};

· Алгоритм sword - разбор строки на слова

· Алгоритм load - Читает строки из текстового файла

· Алгоритм save - Сохраняет результаты работы программы в HTML файле

· Алгоритм povtor - Составляет список повторяющихся слов

· Алгоритм sort - сортировка списка повт слов (быстрая)



3. Результаты работы программы

В ходе выполнения работы были произведены тесты программы с разным количеством слов. По результатам тестов можно сделать вывод, что быстрая сортировка при больших текстах становится очень трудоемкой и количество действий возрастает (в частной случае, перестановок). Это может быть из-за малого количества слов.



N	T,с	Уник. сл
1000	0	150
50000	1	978
100000	3	2456
250000	6	5964
500000	12	6987
1000000	24	7582
2000000	35	10963

N	P	Уник. сл
1000	288	150
50000	989	978
100000	5499	2456
250000	8756	5964
500000	11897	6987
1000000	12458	7582
2000000	17986	10963

4. Доработки

Из-за трудоемкого перебора повт. знаков од (не перебираем хвост из уникальных слов)

//В качестве медианы - среднее арифметическое

void sort(word in[], int a, int b, int cut[]) {

int i, j, mode;

double sr = 0;

if (a >= b) return; // Размер части =0

for (i = a; i <= b; i++)

{sr += in[i].n;}

sr = sr / (b - a + 1);

for (i = a, j = b; i <= j;)

{

if (in[i].n> sr) { i++; continue; } // Слева - меньше, пропустить

if (in[j].n <= sr) { j--; continue; } // Справа - больше, пропустить

word c = in[i]; in[i] = in[j]; in[j] = c;

i++, j--; // Поменять местами и пропустить

}

if (i == a) return; // все равны и в правой части

sort(in, a, j, cut); sort(in, i, b, cut); // рекурсивный вызов для двух частей

}

После доработки, количество перестановок заметно уменьшилось (можно увидеть, что уменьшилось именно на количество уникальных слов)

А также время работы программы сократилось в среднем на 2-3 секунды.

N	P	Уник. сл
1000	138	150
50000	711	278
100000	3043	2456
250000	2792	5964
500000	4910	6987
1000000	4876	7582
2000000	7023	10963

N	T
1000	0
50000	1
100000	2
250000	4
500000	10
1000000	21
2000000	29

5. Приложение

Текст программы:

void main()

{

char file_txt[50]; //Хранит имя текстового файла

char file_html[50];//Хранит имя HTML-файла

int n_max; //Хранит число требуемых наиболее часто встречаемых слов

FILE *fd = fopen("text2.txt", "r");

//Создаем пустой элемент списка со всеми словами

struct all_words *as = create();

//Загружаем все слова в память

load(file_txt, as);

//Создаем пустой элемент списка повторяющихся слов

struct povtor_words *pov = create2();

povtor(as, pov, pr);

//Выбираем наиболее часто встречающиеся слова и сохраняет в HTML файл

save(pov, file_html, n_max, file_txt);

getch(); /

return;

//Конец программы

}

//Загрузка строк из файла

void load(char file[], struct all_words *as)

{

//Открываем файл для загрузки строк

FILE *fp;

if ((fp = fopen(text2, "r")) == NULL) {

print("\a\nОШИБКА при открытии файла.\n");

fclose(fp);

exit(0);

}

char ch[3000], oe[3000], *st;

int ex = 0;

int num = 1; //Номер абзаца

do {

fgets(ch, 3000, fp); //Читает строки

ex = feof(fp); //Находит конец файла

if (ex != 0) break;

if (ch[0] == '\n') continue; //Если строка пустая

sword(oe, num, as);

num++;

} while (ex == 0);

fclose(fp);

print("\nВсе слова из файла %s успешно загружены в память.\n", file);

}

//Генерирует HTML файл с результатами работы

void save(struct povtor_words *pov, char file_name[], int n_max, char file_txt[])

{//Создаем текстовый файл

FILE *fp;

if ((fp = fopen(file_name, "w")) == NULL) {

print("Ошибка при создании файла!\n");

return;

}//Записываем html код в файл

FILE *fdo = fopen("Результат работы программы.htm", "w");

fprintf(fdo, "<html><body><table border=1>\n");

for (i = 0; i < MM && i < n; i++) {

fprintf(fdo, "<tr><td>%s</td><td>%d</td><td>", WD[i].wd, WD[i].n);

for (int j = 0; j<WD[i].n; j++) fprintf(fdo, "<a href=\"#m%d\">%d</a> ", WD[i].abz[j], WD[i].abz[j]);

fprintf(fdo, "</td></tr>\n", na);

}

fprintf(fdo, "</table>\n");

na = 1;

fprintf(fdo, "<a name=\"m1\"><pre>%d\t", na);

while ((k = getw(fd, c, 1, cut)) != -1) {

cut[1] ++;

if (k == 1) {

na++;

fprintf(fdo, "<br><a name=\"m%d\"><pre>%d\t", na, na);

}

else fprintf(fdo, "%s ", c);

}

fprintf(fdo, "</body></html>\n");

fclose(fd);

fclose(fdo);

---------Выделение слов из строки-------------

void sword(char string[], int num, struct all_words *as)

{

char *pb; //Указатель на начало слова

char *pe; //Указатель на конец слова

char *temp = string;

char str[50];

struct all_words *df = as;

----------Разбор строки на слова-------------

for (; *temp != '\0'; temp++) {

//Ищем начало слова (любой символ)

for (; *temp == ' ' && *temp != '\0'; temp++);

pb = temp;

//Ищем конец слова (пробел или ,.?!:;)

for (; *temp != '\0'; temp++)

{

//Если слово заканчивается пробелом

if (*temp == ' ') { pe = temp; break; }

//Если слово заканчивается одним из символов ,.?!"):;

if (*temp == '.' || *temp == ',' || *temp == '?' || *temp == '!' || *temp == ':' || *temp == ';' || *temp == ')' || *temp == '"')

{ //найден конец слова,

pe = temp; // теперь необходимо найти символ пробела

for (; *temp != ' ' && *temp != '\0'; temp++);

break;

}

}

int f = pe - pb; //f - Длина выделенного слова

//Копируем слово в переменную str

for (int h = 0; h < f; h++) str[h] = pb[h];

str[f] = '\0'; //Добавляем в слово символ конца строки

//Добавляем слово в список

if (df->str == NULL) //Если список всех слов пуст

{

df->num = num;

df->str = strdup(str);

continue;

}

else

{

//Находим конец списка

for (; df->next != NULL; df = df->next);

//Создаем новый элемент списка

struct all_words *pv = new struct all_words;

pv->str = strdup(str);

pv->num = num;

pv->next = NULL;

df->next = pv;

}

if (*temp == '\0') break;

Размещено на Allbest.ru