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

> Внимание!

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

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

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


Профи
****

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

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


всё-таки хочу разобраться и таким вариантом : как, после сотировки строк по убыванию их длины, удалить самые короткие, идя к ним от головы списка? (т.е. считаем, что самые короткие в конце списка). Как предусмотреть, если самых коротких меньше 5? (например вывести сообщение о том, что нужного кол-ва строк нет)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #22


Гость






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

Но это делай сама, я ЭТО делать не буду.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #23


Профи
****

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

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


Я хочу добиться того, чтобы после удаления 5 элементов (остальные элементы расположены в порядке возрастания их длины), оставшиеся элементы были расположены в обратном порядке (т.е. в порядке убывания длины).
Как это будет выглядеть?
И куда в этом случае привязать проверку на наличие пяти самых коротких строк?

И ещё такой вопрос:
void sort(LIST **first) - почему мы в эту ф-ю передаём указатель на указатель на голову списка?


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


Профи
****

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

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


Цитата(18192123 @ 9.05.2007 16:55) *

Я хочу добиться того, чтобы после удаления 5 элементов (остальные элементы расположены в порядке возрастания их длины), оставшиеся элементы были расположены в обратном порядке (т.е. в порядке убывания длины).
Как это будет выглядеть?


Это я поняла.
А вот с остальными вопросами не разобралась....(про проверку на наличие 5 коротких и про void sort(LIST **first))

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


Гость






Цитата
почему мы в эту ф-ю передаём указатель на указатель на голову списка?
Потому, что если мы будем передавать просто указатель на голову списка, то изменить его (если это понадобится) мы не сможем... Это получается некоторый аналог Var-параметра в Паскале...

В С++ это очень просто решается с помощью ссылок, но в чистом С ссылки не введены, поэтому приходится передавать указатель на <что-то что может меняться>
 К началу страницы 
+ Ответить 
сообщение
Сообщение #26


Профи
****

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

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


объясните пожалуйста некоторые моменты:
1) о сортировке

for(L = *first; L -> next; L = L -> next)

for(p = L -> next; p; p = p -> next)


здесь L = *first - голова, p = L -> next - элемент, следующий за головой, а что подразумевается под L -> next и p?
Как я понимаю, операциями L = L -> next и p = p -> next мы переходим к следующим элементам,которые нужно сравнивать, да?

2)почему мы ставим здесь взятие адреса?

sort(&root);



3) здесь мы печатаем отсортированный по возрастанию длины список:

for(p = root; p; p = p -> next)
printf("%s\n", p -> number);




печатаем начиная с головы p = root и заканчивая р, в процессе передвигаясь от головы к концу списка, так?
тогда р - у нас последний элемент списка? или тут другое?

4)
момент с удалением 5-ти первых:

for(p = root; p && n < 5; n++)


почему у нас тут такое условие завершения цикла?

5) и последнее - почему при печати оставшегося списка мы использует таокй цикл

for(p = root; p; )


?

Объясните пожалуйста!


Добавлено через 19 мин.
2) вопрос отпал. а вот с остальным - объясните пожалуйста.

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


Гость






Давай по порядку:

1) организацию циклов в С знаешь? Я имею в виду, синтаксис оператора цикла?
for(начальное_присвоение;условие_окончания;и
зменение_на_каждой_итерации) {
собственно_операторы_тела_цикла;
}

где
начальное_присвоение - делается один раз перед началом цикла;
условие_окончания - проверяется после завершения каждой итерации
изменение_на_каждой_итерации - делается после завершения итерации ПЕРЕД проверкой условия_окончания

причем любой (!!!) из этих параметров может отсутствовать (моогут, кстати, отсутствовать и 2 и все 3 - тогда цикл будет "вечным", и выходе из него возможен будет только через break)...

А теперь с учетом этого - смотри, что происходит:


/*
ВНЕШНИЙ цикл

Поскольку first передается как указатель на указатель
(причину я объяснял выше), то L присваиваем значению
разыменованного first (т.е. изначально L = указателю на
голову списка)

Условие окончания внешнего цикла - (L->next) подразумевает НЕравенство
этого значения нулю... То есть, как только значение L->next станет NULL, цикл завершится...

После обработки одной итерации продвигаемся по списку, путем L = L -> next
*/
for(L = *first; L -> next; L = L -> next)

/*
ВНУТРЕННИЙ цикл
изначально p = L -> next
условие окончания: закончится цикл - когда p будет нулевым
продвижение - понятно как осуществляется...
*/
for(p = L -> next; p; p = p -> next)


2)
Цитата
почему мы ставим здесь взятие адреса?
Потому, что я объяснил, зачем передается указатель на указатель, а чтобы передать его - надо взять адрес указателя...

3)
Цитата
здесь мы печатаем отсортированный по возрастанию длины список:
Опять же - смотри комментарии, и постарайся разобраться в принципе работы оператора цикла, я не могу каждый раз писать такие объемные комментарии...

/*
изначально p = root
окончание - когда p = NULL
продвижение - p = p -> next
*/
for(p = root; p; p = p -> next)
printf("%s\n", p -> number);


4)
Цитата
почему у нас тут такое условие завершения цикла?

Условие завершения может быть любым правильным логическим условием, в отличие от оператора For в Паскале... Что делается здесь: предварительно я n установил в 0, правда? После каждой итерации (т.е., после удаления очередного элемента) n увеличивается на 1, а так как нам надо удалить ЛИБО первые 5 элементов, ЛИБО, если их всего меньше 5, то все - мы ставим операцию AND, и как только одно из условий НЕ выполняется (или уже удалили 5 элементов и n = 5, или достигли конца цикла, и p = NULL) - то цикл завершается...

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

  for(p = root; p; ) {
printf("%s\n", p -> number);
p = (T = p) -> next; /* <--- вот эту строку ты разобрала, как она работает? */
free(T);
}

в отмеченной строке происходит следующее: сначала выполняется действие в скобках, т.е. T = p, потом в p заносится новое значение, равное T -> next, то есть, фактически, старое p запоминается в переменной T, а потом p продвигается на следующий элемент списка...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #28


Профи
****

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

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


volvo, большое спасибо! теперь всё поняла! smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #29


Профи
****

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

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


Возник ещё вопрос:

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);
}
}



Здесь при сортировке строк по длине мы фактически работаем с содержимым информационных полей каждого элемента, верно?
а можно сделать так, чтобы не строки копировать из одной области памяти в другую, а вместо этого изменять указатели?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #30


Гость






Можно, только код будет больше по размеру... Не забывай, у тебя односвязные списки, то есть, для того, чтобы пройти к предыдущему (менять-то указатель с предыдущего на новое значение надо?) тебе придется пробегать еще раз по списку с самого начала...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #31


Профи
****

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

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


Цитата(volvo @ 14.05.2007 23:52) *

Можно, только код будет больше по размеру... Не забывай, у тебя односвязные списки, то есть, для того, чтобы пройти к предыдущему (менять-то указатель с предыдущего на новое значение надо?) тебе придется пробегать еще раз по списку с самого начала...

".....(менять-то указатель с предыдущего на новое значение надо?)" - думаю, надо.
Можешь объяснить, как тогда код изменится?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #32


Профи
****

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

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


Цитата(18192123 @ 14.05.2007 19:13) *

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

каков должен быть механизм таких действий?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #33


Гость






Ты сама просила smile.gif

void sort(LIST **first) {

LIST *L, *p, *pp, *T, *prv_L, *prv_p;
char s[255];

start_over:
;

for(L = *first; L -> next; L = L -> next)

for(p = L -> next; p; p = p -> next) {

if(strlen(L -> number) > strlen(p -> number)) {

// Вот тут раньше было 3 строки... Смотри теперь.

if(L == *first) {

for(pp = *first; pp -> next != p; pp = pp -> next);
pp -> next = *first;

T = (*first) -> next;
*first = p;

L -> next = p -> next;
p -> next = T;

}
else {
LIST *prv_L, *prv_p;
for(prv_L = *first; prv_L -> next != L; prv_L = prv_L -> next);
for(prv_p = *first; prv_p -> next != p; prv_p = prv_p -> next);

prv_L -> next = p;
prv_p -> next = L;
T = p -> next;
p -> next = L -> next;
L -> next = T;
}

goto start_over;
}
}

}

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


Профи
****

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

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


Цитата(volvo @ 15.05.2007 17:11) *

Ты сама просила smile.gif


Спасибо!
Общую идею поняла...Попробывала переделать на свой лад....Идея такая: по заданию мне нужно расположить строки по убыванию длины. Функцией sort1 я это и делаю. Вывожу результат. Одна часть задания выполнена. Теперь сортирую наоборот (sort), после удаляем 5 самых коротких(они теперь впереди), ещё раз сортируем (т.к. по заданию нужно получить строки, упорядоченные по убыванию длины). Вывожу конечный результат.
Проблема в том, что в файл выводится список отсортированный, но не тот, что нужен мне.....
Вот так, например:
Исходные данные

qwert tyuri vbncgf
aaaaaaaaaaaaaaaaaaaaa
zxc vbn fgh qwerty qwerty
zxc
sd
a
qwervbn
zasd
cvbnnnnnn qwe rty uioopl nm

Результат

qwert tyuri vbncgf

qwervbn

zasd

zxc

sd

a


---

--------
Не пойму, откуда такие результаты?!


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

typedef struct list {

char number[255];
struct list *next;

} LIST;

LIST *read_list() {
char s[255];

LIST *p, *lst, *final;
FILE *f;
f=fopen("rgz.txt","r");

lst = NULL;
while(!feof(f)) {

fgets(s,255, f);
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 *p1=first, *p2=p1->next, *prev,*temp1, *temp2;
int flag=1;
while (flag&&p2)
{
flag=0;
prev=first;
while (p2)
{

if (strlen(p1->number)>strlen(p2->number))
{
flag=1;
temp1=p1;
temp2=p2->next;
p1=p2;
p2=temp1;
p1->next=p2;
p2->next=temp2;
if (temp1==first) first=p1; else prev->next=p1;
}
prev=p1;
p1=p1->next;
p2=p2->next;
}
p1=first; p2=p1->next;
}
}

void *sort1(LIST *first)
{
LIST *p1=first, *p2=p1->next, *prev,*temp1, *temp2;
int flag=1;
while (flag&&p2)
{
flag=0;
prev=first;
while (p2)
{

if (strlen(p1->number) < strlen(p2->number))
{
flag=1;
temp1=p1;
temp2=p2->next;
p1=p2;
p2=temp1;
p1->next=p2;
p2->next=temp2;
if (temp1==first) first=p1; else prev->next=p1;
}
prev=p1;
p1=p1->next;
p2=p2->next;
}
p1=first; p2=p1->next;
}
}







void main() {
struct list *root, *p, *T;
int n;
FILE *f;
f=fopen("RGZ2.txt","w");

root = read_list();


sort1(root);

for(p = root; p; p = p -> next)
fprintf(f,"%s\n", p -> number);
fprintf(f,"\n---\n");
sort(root);

n = 0;
for(p = root; p && n < 5; n++) {

p = (T = p) -> next;
free(T);
}

root = p;
sort1(root);


for(p = root; p; ) {
fprintf(f,"%s\n", p -> number);
p = (T = p) -> next;
free(T);
}
root = NULL; fprintf(f,"\n--------\n");

}



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


Гость






Сорри, я больше в эту тему НЕ отвечаю! Я тебе привел работающую функцию сортировки, на отладку которой ушло больше 2-х часов, ты ее полностью перековеркала, и теперь тебя не устраивает результат? dry.gif

Извини, но функции твои, вот и разбирайся, как они работают сама (а они НЕ работают, чтобы в этом убедиться достаточно вывести на экран содержимое списка ПЕРЕД первой сортировкой, и ПОСЛЕ нее)...

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


Профи
****

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

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


Цитата(volvo @ 15.05.2007 17:11) *



LIST *prv_L, *prv_p;
for(prv_L = *first; prv_L -> next != L; prv_L = prv_L -> next);
for(prv_p = *first; prv_p -> next != p; prv_p = prv_p -> next);





И всё-таки...Объясни пожалуйста:
А для чего вводятся *prv_L, *prv_p?
И для чего эти два цикла?
Почему в циклах используется условие prv_L -> next != L и prv_p -> next != p?

И ещё: почему мы вновь должны возвращаться к началу циклов (goto start_over;
) и когда этот механизм возврата закончит свою работу?

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

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

 





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