1. Пользуйтесь тегами кода. - [code] ... [/code] 2. Точно указывайте язык, название и версию компилятора (интерпретатора). 3. Название темы должно быть информативным. В описании темы указываем язык!!!
Дан текстовый файл. Строки этого файла расположить в порядке убывания их длины и удалить пять самых коротких из них. Для размещения в памяти содержимого файлов использовать односвязные линейные списки.
Предполагаю заносить каждую строку в одно поле списка, но не знаю, как это сделать именно со строкой и сколько выделять памяти.
После прочтения строки из файла, проверяй ее длину (strlen) и выделяй под информационное поле в списке на 1 байт больше (для хранения завершающего '\0')
хочу сделать функцию для расположения строк в порядке убывания их длины. пусть до этого у меня есть ф-я, которая формирует список (ф-я возвращает указатель на голову списка). тогда в ф-ю упорядочения передаём указатель на голову списка. а дальше я не разберусь , как с помощью списка собственно упорядочить строки.... помогите пожалуйста!
Ты какой путь выбираешь, сразу заносить очередной элемент на соответствующее место, или сначала занести ВСЕ элементы, а потом - сортировать?
Скорее всего, второй? Тогда я уже выкладывал где-то переведенную на Паскаль рекурсивную функцию сортировки списка вставками (из книги Sedgewick-а "Fundamental C++"), если надо - выложу оригинал на С ...
Ты какой путь выбираешь, сразу заносить очередной элемент на соответствующее место, или сначала занести ВСЕ элементы, а потом - сортировать?
Скорее всего, второй? Тогда я уже выкладывал где-то переведенную на Паскаль рекурсивную функцию сортировки списка вставками (из книги Sedgewick-а "Fundamental C++"), если надо - выложу оригинал на С ...
да, второй. только это не должна быть рекурсивная ф-я....
Ну, тогда тебе и карты в руки... Опять изобретение велосипеда? Что же за преподаватели-то такие? Они же просто угробят все, что только можно!!! С одной стороны они ограничили тебя односвязным списком, то есть, у тебя только последовательный проход по списку (про сотню проходов по списку из 100 элементов я не говорю - это вообще полный бред), а с другой стороны - те методы, которые эффективны при последовательном доступе (в частности - mergesort) - они рекурсивные... А рекурсия запрещена. Замкнутый круг...
Ну, тогда тебе и карты в руки... Опять изобретение велосипеда? Что же за преподаватели-то такие? Они же просто угробят все, что только можно!!! С одной стороны они ограничили тебя односвязным списком, то есть, у тебя только последовательный проход по списку (про сотню проходов по списку из 100 элементов я не говорю - это вообще полный бред), а с другой стороны - те методы, которые эффективны при последовательном доступе (в частности - mergesort) - они рекурсивные... А рекурсия запрещена. Замкнутый круг...
попыталась написать ф-ю, которая формирует список (ф-я возвращает указатель на голову списка). но насчёт занесения строки в информационное поле элемента списка - ???
#include <stdio.h>#include <conio.h>#include <string.h>#include <alloc.h>typedefstructlist {
char number[50];
structlist *next;
} LIST;
LIST *read_list(LIST *lst)
{
LIST *p;
FILE *f;
f=fopen("rg.txt","r");
if (!feof(f))
{
lst=(LIST *)malloc(sizeof(LIST));
p=lst;
while (1)
{
fscanf(f,"%s",p->number[50]);
if (!feof(f))
{
p->next=(LIST *)malloc(sizeof(LIST));
p=p->next;
} elsebreak;
}
p->next=NULL;
}
else printf("Файл пустой\n");
fclose(f);
return lst;
}
Эта строка значит следующее: если lst == NULL (или, как я написал, отрицание lst не равно нулю, что одно и то же для С), значит в список пока ничего не было добавлено, в таком случае в lst надо записать значение p, поскольку в данный момент добавляется первый элемент...
А по ветке else - если список уже НЕ пуст, то в указатель next последнего поля надо записывать p, связывая выделенную память с собственно списком...
Цитата
*final - указатель на конец списка, да?
Именно... Это указатель на тот элемент списка, к которому будет присоединяться новый при добавлении его в конец списка...
А как будет выглядеть удаление 5 нужных элементов? ( тогда это ещё одна ф-я, куда, наверно, нужно передать указатель на голову списка...а что-то кроме этого нужно передавать?)
А когда всё необходимое выполнено, нам ведь нужно освободить занятые участки памяти и указателям, ссылающимся на них, присвоить NULL? (т.е. я так понимаю - отсортировали, удалили лишнее, выводим на экран содержимое оставшихся информационных полей и попутно освобождаем занятые участки.... а как это выполняется?)
А как будет выглядеть удаление 5 нужных элементов?
А по какому признаку будешь удалять?
Цитата
А когда всё необходимое выполнено, нам ведь нужно освободить занятые участки памяти
Нужно... Пробежаться по всему списку, и сделать free для каждого узла списка. Алгоритм - точно такой же, как и в FAQ по Паскалю -> "Все о динамических структурах данных".
Будет гораздо проще сделать наоборот: отсортировать слова по возрастанию длины, а потом удалить 5 первых, поскольку у тебя односвязный список, и работать от "головы" к "хвосту" легче, чем от "хвоста" к "голове"... Смотри:
#include <stdio.h>#include <conio.h>#include <string.h>#include <alloc.h>typedefstructlist {
char number[50];
structlist *next;
} LIST;
LIST *read_list() {
char s[255];
LIST *p, *lst, *final;
FILE *f;
f=fopen("rg.txt","r");
lst = NULL;
while(!feof(f)) {
fscanf(f, "%s", s);
p = (LIST*)malloc(sizeof(list));
strcpy(p -> number, s);
if(!lst) lst = p;
else final -> next = p;
final = p;
}
fclose(f);
if(!lst) {
printf("empty file\n");
return NULL;
}
final -> next = NULL;
return lst;
}
void sort(LIST **first) {
LIST *L, *p;
char s[255];
for(L = *first; L -> next; L = L -> next)
for(p = L -> next; p; p = p -> next) {
if(strlen(L -> number) > strlen(p -> number)) { /* сортируем по длине */
strcpy(s, L -> number);
strcpy(L -> number, p -> number);
strcpy(p -> number, s);
}
}
}
int main() {
structlist *root, *p, *T;
int n;
/* читаем список из файла */
root = read_list();
/* сортируем его по возрастанию длин строк */
sort(&root);
/* и печатаем ... */for(p = root; p; p = p -> next)
printf("%s\n", p -> number);
/* теперь удаляем первые 5 элементов */
n = 0;
for(p = root; p && n < 5; n++) {
p = (T = p) -> next; /* запоминаем текущее P в переменной T, для того чтобы потом удалить */
free(T);
}
/* и устанавливаем новое начало списка */
root = p;
/* еще раз проходим, и печатаем весь список, сразу удаляя все узлы, которые уже распечатаны */for(p = root; p; ) {
printf("%s\n", p -> number);
p = (T = p) -> next;
free(T);
}
root = NULL;
return0;
}
Так... Кажется мне удалось повторить проблему, которая есть у тебя...
Убедись, что после последней строки файла данных НЕТ перевода строки, т.е., последняя строка - НЕ пустая... Если она будет пустой - то получишь то, что ты сказала...
Так... Кажется мне удалось повторить проблему, которая есть у тебя...
Убедись, что после последней строки файла данных НЕТ перевода строки, т.е., последняя строка - НЕ пустая... Если она будет пустой - то получишь то, что ты сказала...