Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Образовательный студенческий форум _ Информатика / Программирование _ Упорядочивание односвязного списка (С)

Автор: Nikgamer 5.5.2010, 12:24

Привет. Вот дали на мою голову такую задачку, с условием, что реализую на СИ (без ++-ов). Задача формулируется так. На вход подается произвольное кол-во натуральных чисел (не по порядку, с повторами etc.). Нужно, используя односвязный список, отсортировать эти числа по возрастанию, удалить повторы и распечатать, собственно, получившийся список.
Ну-с, проблемы с реализацией. Ниже будет приаттачен мой индусский быдлокод. Вопросов 2. Первый - правильно ли сортируется? Второй - как реализовать печать?

Код

#include <stdio.h>
#include <stdlib.h>
int main () {
int a;
struct list {int data; struct list *next;};
struct list *h, *t, *p,*r,*c=NULL,*d;
h=(struct list*)malloc(sizeof(struct list));
h->data=0;
h->next=NULL;
while (scanf("%d", &a)==1){
    p=(struct list*)malloc(sizeof(struct list));
    p->data=a;
    p->next=NULL;
    if(h->data==0){
        h->data=p->data;
        continue;
    }
    if(p->data<h->data){
        p->next=h;
        h=p;
    }
    if(p->data>h->data){
        for(t=h;t->next!=NULL;t=t->next){
            if(p->data<t->next->data){
                c=t->next;
                t->next=p;
                p->next=c;
            }
        }
        t->next=p;
    }
}
return 0;
}

Автор: Vahappaday 5.5.2010, 15:43

Блочок добавления в серёдку/конец надо доработать....
Во внутреннем if надо break поставить, а то он будет один элемент перед всеми добавлять...

ну а вывод... Не знаю, с самым сложным справились, а вывод не можете?

Код

while(h)
{
printf("%d\n",h->data);
h=h->next;
}

Как-то так))

Автор: Nikgamer 6.5.2010, 8:15

Спасибо за отклик. А куда этот блок печати пихать? Дело в том, что если закончится ввод с клавиатуры, то он не выйдет из

Код

while (scanf("%d", &a)==1)

а затребует еще чисел. Вследствие чего и возникает вопрос. Ведь если

Код

while(h)
{
printf("%d\n",h->data);
h=h->next;
}

ставить внутрь

Код

while (scanf("%d", &a)==1)

то ничего не выйдет, потому что в промежуточных шагах список еще не будет упорядоченный. Да и вообще, он много раз выведет одно и тоже.
А что не так с блоком, начинающимся с

Код

if(p->data>h->data)

Ткните пальцем, я просто может не вижу чего. Да, break нужно добавить, это я не углядел.

Автор: Vahappaday 6.5.2010, 11:50

мой цикл надо ставить после Вашего, то есть вот так:

Код

while (scanf("%d", &a)==1){...}
while(h) {...}

И нужно предусмотреть конец ввода. Я завершал ввод, когда это отлаживал, комбинацией Ctrl+Z, но можно, например, выходить из цикла при a=0 или -1.

Автор: Nikgamer 6.5.2010, 11:58

Цитата(Vahappaday @ 6.5.2010, 11:50)

мой цикл надо ставить после Вашего, то есть вот так:

Код

while (scanf("%d", &a)==1){...}
while(h) {...}

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

Автор: Vahappaday 6.5.2010, 12:03

пожалуйста)

Ctrl+Z - это в общем-то комбинация, эквивалентная EOF для файла, так что тут всё корректно, если потом запустить экзешник вот так:
myexe.exe << input.txt
где input.txt содержит входные числа, то всё будет отлично работать.

Русская версия Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)