IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Односвязные линейные списки, Си
сообщение
Сообщение #1


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Дан текстовый файл. Строки этого файла расположить в порядке убывания их длины и удалить пять самых коротких из них.
Для размещения в памяти содержимого файлов использовать односвязные линейные списки.

Предполагаю заносить каждую строку в одно поле списка, но не знаю, как это сделать именно со строкой и сколько выделять памяти.

Сообщение отредактировано: 18192123 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






После прочтения строки из файла, проверяй ее длину (strlen) и выделяй под информационное поле в списке на 1 байт больше (для хранения завершающего '\0')
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


хочу сделать функцию для расположения строк в порядке убывания их длины.
пусть до этого у меня есть ф-я, которая формирует список (ф-я возвращает указатель на голову списка). тогда в ф-ю упорядочения передаём указатель на голову списка. а дальше я не разберусь , как с помощью списка собственно упорядочить строки....
помогите пожалуйста!

Сообщение отредактировано: 18192123 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Ты какой путь выбираешь, сразу заносить очередной элемент на соответствующее место, или сначала занести ВСЕ элементы, а потом - сортировать?

Скорее всего, второй? Тогда я уже выкладывал где-то переведенную на Паскаль рекурсивную функцию сортировки списка вставками (из книги Sedgewick-а "Fundamental C++"), если надо - выложу оригинал на С ...

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Цитата(volvo @ 1.05.2007 17:30) *

Ты какой путь выбираешь, сразу заносить очередной элемент на соответствующее место, или сначала занести ВСЕ элементы, а потом - сортировать?

Скорее всего, второй? Тогда я уже выкладывал где-то переведенную на Паскаль рекурсивную функцию сортировки списка вставками (из книги Sedgewick-а "Fundamental C++"), если надо - выложу оригинал на С ...


да, второй. только это не должна быть рекурсивная ф-я....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Ну, тогда тебе и карты в руки... Опять изобретение велосипеда? Что же за преподаватели-то такие? Они же просто угробят все, что только можно!!! С одной стороны они ограничили тебя односвязным списком, то есть, у тебя только последовательный проход по списку (про сотню проходов по списку из 100 элементов я не говорю - это вообще полный бред), а с другой стороны - те методы, которые эффективны при последовательном доступе (в частности - mergesort) - они рекурсивные... А рекурсия запрещена. Замкнутый круг...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Цитата(volvo @ 1.05.2007 18:46) *

Ну, тогда тебе и карты в руки... Опять изобретение велосипеда? Что же за преподаватели-то такие? Они же просто угробят все, что только можно!!! С одной стороны они ограничили тебя односвязным списком, то есть, у тебя только последовательный проход по списку (про сотню проходов по списку из 100 элементов я не говорю - это вообще полный бред), а с другой стороны - те методы, которые эффективны при последовательном доступе (в частности - mergesort) - они рекурсивные... А рекурсия запрещена. Замкнутый круг...

ээээ...и как быть?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


попыталась написать ф-ю, которая формирует список (ф-я возвращает указатель на голову списка).
но насчёт занесения строки в информационное поле элемента списка - ???

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <alloc.h>
typedef struct list {
char number[50];
struct list *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;
} else break;
}
p->next=NULL;
}
else printf("Файл пустой\n");
fclose(f);
return lst;
}



 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <alloc.h>

typedef struct list {

char number[50];
struct list *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(strcmp(L -> number, p -> number) > 0) {
strcpy(s, L -> number);
strcpy(L -> number, p -> number);
strcpy(p -> number, s);
}
}

}


int main() {
struct list *p;
p = read_list();
sort(&p);
for(; p; p = p -> next)
printf("%s\n", p -> number);

return 0;
}

Так работает?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Цитата(volvo @ 1.05.2007 21:48) *


strcpy(p -> number, s);




да, работает!
А что значит эта строка?

if(!lst) lst = p;
else final -> next = p;



и что это?

*final - указатель на конец списка, да?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Цитата
А что значит эта строка?
Эта строка значит следующее: если lst == NULL (или, как я написал, отрицание lst не равно нулю, что одно и то же для С), значит в список пока ничего не было добавлено, в таком случае в lst надо записать значение p, поскольку в данный момент добавляется первый элемент...

А по ветке else - если список уже НЕ пуст, то в указатель next последнего поля надо записывать p, связывая выделенную память с собственно списком...

Цитата
*final - указатель на конец списка, да?
Именно... Это указатель на тот элемент списка, к которому будет присоединяться новый при добавлении его в конец списка...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


А как будет выглядеть удаление 5 нужных элементов? ( тогда это ещё одна ф-я, куда, наверно, нужно передать указатель на голову списка...а что-то кроме этого нужно передавать?)

А когда всё необходимое выполнено, нам ведь нужно освободить занятые участки памяти и указателям, ссылающимся на них, присвоить NULL? (т.е. я так понимаю - отсортировали, удалили лишнее, выводим на экран содержимое оставшихся информационных полей и попутно освобождаем занятые участки.... а как это выполняется?)

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Цитата
А как будет выглядеть удаление 5 нужных элементов?
А по какому признаку будешь удалять?

Цитата
А когда всё необходимое выполнено, нам ведь нужно освободить занятые участки памяти
Нужно... Пробежаться по всему списку, и сделать free для каждого узла списка. Алгоритм - точно такой же, как и в FAQ по Паскалю -> "Все о динамических структурах данных".
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Цитата(volvo @ 2.05.2007 12:35) *

А по какому признаку будешь удалять?


удалять 5 самых коротких, т.е. вроде как после сортировки стоящих в конце
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гость






Будет гораздо проще сделать наоборот: отсортировать слова по возрастанию длины, а потом удалить 5 первых, поскольку у тебя односвязный список, и работать от "головы" к "хвосту" легче, чем от "хвоста" к "голове"... Смотри:

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <alloc.h>

typedef struct list {

char number[50];
struct list *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() {
struct list *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;
return 0;
}

Вот и все...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


вот такие тестовые данные ввожу в исходный файл:
qwerty
asdf
qwertyu
qwertyqwerty
qwertyuioop
zxcvbnmjhy
qw
q
zxcvfgh

результат в прикреплённом файле.
не пойму, почему строчка zxcvfgh выводится 2 раза?

Сообщение отредактировано: 18192123 -


Прикрепленные файлы
Прикрепленный файл  Новый_рисунок__2_.bmp ( 75.76 килобайт ) Кол-во скачиваний: 609
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гость






Потому что из списка удаляется всего 5 элементов, а не все элементы, с 5-ю наименьшими длинами...

Добавлено через 3 мин.
А, так он у тебя именно дублируется? Интересно... У меня - нет...


Эскизы прикрепленных изображений
Прикрепленное изображение
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Цитата(volvo @ 8.05.2007 22:47) *

Потому что из списка удаляется всего 5 элементов, а не все элементы, с 5-ю наименьшими длинами...

Добавлено через 3 мин.
А, так он у тебя именно дублируется? Интересно... У меня - нет...

именно дублируется....и при сортировке выводится 2 раза и после удаления 5-ти самых коротких строк тоже 2 раза...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






Так... Кажется мне удалось повторить проблему, которая есть у тебя...

Убедись, что после последней строки файла данных НЕТ перевода строки, т.е., последняя строка - НЕ пустая... Если она будет пустой - то получишь то, что ты сказала...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Цитата(volvo @ 8.05.2007 23:24) *

Так... Кажется мне удалось повторить проблему, которая есть у тебя...

Убедись, что после последней строки файла данных НЕТ перевода строки, т.е., последняя строка - НЕ пустая... Если она будет пустой - то получишь то, что ты сказала...

да, действительно. спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 1:15
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name