Объединение упорядоченных списков
От: Аноним  
Дата: 03.05.14 14:44
Оценка:
Всем привет!
Пытаюсь реализовать алгоритм слияния упорядоченных списков из этой книги. Суть алгоритма в следующем. Вводим два списка и сортируем их по возрастанию. Затем реализуем объединение. Пока один из списков не окончен проверяем, если элемент первого списка меньше элемента второго, то записываем в новый список элемент первого списка и продвигаемся дальше по первому списку. Иначе проверяем, если элемент первого списка больше элемента второго списка, то записываем элемент второго списка и продвигаемся дальше по второму списку. Иначе элементы равны и записываем любой из них в новый список и продвигаемся по обоим спискам. После того как один из списков закончился, но не оба вместе, записываем элементы оставшегося списка в конец нового списка без проверки. В результате всего этого получаем новый упорядоченный список в котором ни один из элементов не повторяется.

Код программы:
#include <iostream>
using namespace std;

struct List
{
    int elem;
    List *next;
};

List *head1, *head2, *head3, *end3, *tail;

void add_elem1(int);
void add_elem2(int);
void show_list(List*);
void sort_elem(List*);
void conjunction(List*, List*);
void append(List*, List*, int);

int main()
{
    int num;
    cout<<"Ввод списка №1: ";
    cin>>num;
    while(num!=0)
    {
        add_elem1(num);
        cin>>num;
    }

    cout<<"Ввод списка №2: ";
    cin>>num;
    while(num!=0)
    {
        add_elem2(num);
        cin>>num;
    }
    
    sort_elem(head1);
    sort_elem(head2);
    
    cout<<"Список №1 = ";
    show_list(head1);
    
    cout<<"Список №2 = ";
    show_list(head2);
    
    conjunction(head1, head2);
    
    cout<<"Список №3 = ";
    show_list(head3);
    return 0;
}

void add_elem1(int num)
{
    List *begin1=new List;
    begin1->elem=num;
    begin1->next=head1;
    head1=begin1;    
}

void add_elem2(int num)
{
    List *begin2=new List;
    begin2->elem=num;
    begin2->next=head2;
    head2=begin2;    
}

void show_list(List *head)
{
    
    List *temp=head;
    cout<<"{ ";
    if(head==NULL)
    {
        cout<<"Список пуст! }"<<endl;
        cout<<endl;
        return;
    }
    while(temp!=NULL)
    {
        cout<<temp->elem<<" ";
        temp=temp->next;
    }
    cout<<"}"<<endl;
}

void sort_elem(List *head)
{
    List *current=head;
    List *i, *j;
    
    for (i=current; i; i=i->next)
        for (j=current; j; j=j->next)
        if (i->elem < j->elem)
        {
            int buf=i->elem;
            i->elem=j->elem;
            j->elem=buf;
        }    
}

void conjunction(List *head1, List *head2)
{
    List *begin1=head1;
    List *begin2=head2;
    List *buf;
    head3=NULL;
    end3=NULL;
    tail=NULL;
        
    while((begin1!=NULL)&&(begin2!=NULL))
    {
        if(begin1->elem < begin2->elem)
        {
            buf=begin1;
            begin1=begin1->next;
        }
        else if(begin1->elem > begin2->elem)
        {
            buf=begin2;
            begin2=begin2->next;
        }
        else
        {
            buf=begin1;
            begin1=begin1->next;
            begin2=begin2->next;
        }
        append(head3, end3, buf->elem);
    }
    
    if(begin1!=NULL) tail=begin1;
    if(begin2!=NULL) tail=begin2;
        
    while(tail!=NULL)
    {
        append(head3, end3, tail->elem);
        tail=tail->next;
    }

}

void append(List *head3, List *end3, int num)
{
    List *begin=new List;
    begin->elem=num;
    begin->next=NULL;
        
    if(head3==NULL) head3=begin;
    else end3->next=begin;
    end3=begin;
}


Программа не хочет записывать элементы в новый список. Пишет, что список пуст.

Ввод списка №1: 1 3 2 0
Ввод списка №2: 5 4 6 0
Список №1 = { 1 2 3 }
Список №2 = { 4 5 6 }
Список №3 = { Список пуст! }


При компиляции с отладкой вываливает такие ошибки (мне они малопонятны):

g++ main.cpp -o -g main

main: In function `_start':
(.text+0x0): multiple definition of `_start'
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 0 has invalid symbol index 11
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 1 has invalid symbol index 12
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 2 has invalid symbol index 2
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 3 has invalid symbol index 2
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 4 has invalid symbol index 11
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 5 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 6 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 7 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 8 has invalid symbol index 2
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 9 has invalid symbol index 2
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 10 has invalid symbol index 12
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 11 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 12 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 13 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 14 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 15 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 16 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 17 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 18 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 19 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 20 has invalid symbol index 20
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_line): relocation 0 has invalid symbol index 2
/usr/lib/gcc/x86_64-linux-gnu/4.7/../../../x86_64-linux-gnu/crt1.o:/home/aurel32/eglibc/eglibc-2.13/csu/../sysdeps/x86_64/elf/start.S:109: first defined here
main: In function `sort_elem(List*)':
(.text+0x370): multiple definition of `sort_elem(List*)'
/tmp/ccEDTgkN.o:main.cpp:(.text+0x264): first defined here
main: In function `_fini':
(.fini+0x0): multiple definition of `_fini'
/usr/lib/gcc/x86_64-linux-gnu/4.7/../../../x86_64-linux-gnu/crti.o:(.fini+0x0): first defined here
main: In function `show_list(List*)':
(.text+0x2c4): multiple definition of `show_list(List*)'
/tmp/ccEDTgkN.o:main.cpp:(.text+0x1b8): first defined here
main: In function `add_elem2(int)':
(.text+0x286): multiple definition of `add_elem2(int)'
/tmp/ccEDTgkN.o:main.cpp:(.text+0x17a): first defined here
main: In function `conjunction(List*, List*)':
(.text+0x3f4): multiple definition of `conjunction(List*, List*)'
/tmp/ccEDTgkN.o:main.cpp:(.text+0x2e8): first defined here
main:(.bss+0x248): multiple definition of `head3'
/tmp/ccEDTgkN.o:(.bss+0x10): first defined here
main:(.rodata+0x0): multiple definition of `_IO_stdin_used'
/usr/lib/gcc/x86_64-linux-gnu/4.7/../../../x86_64-linux-gnu/crt1.o:(.rodata.cst4+0x0): first defined here
main: In function `__data_start':
(.data+0x0): multiple definition of `__data_start'
/usr/lib/gcc/x86_64-linux-gnu/4.7/../../../x86_64-linux-gnu/crt1.o:(.data+0x0): first defined here
main: In function `append(List*, List*, int)':
(.text+0x554): multiple definition of `append(List*, List*, int)'
/tmp/ccEDTgkN.o:main.cpp:(.text+0x448): first defined here
main: In function `__data_start':
(.data+0x8): multiple definition of `__dso_handle'
/usr/lib/gcc/x86_64-linux-gnu/4.7/crtbegin.o:(.data+0x0): first defined here
main:(.bss+0x240): multiple definition of `head2'
/tmp/ccEDTgkN.o:(.bss+0x8): first defined here
main: In function `add_elem1(int)':
(.text+0x248): multiple definition of `add_elem1(int)'
/tmp/ccEDTgkN.o:main.cpp:(.text+0x13c): first defined here
main:(.bss+0x250): multiple definition of `end3'
/tmp/ccEDTgkN.o:(.bss+0x18): first defined here
main:(.bss+0x238): multiple definition of `head1'
/tmp/ccEDTgkN.o:(.bss+0x0): first defined here
main:(.bss+0x258): multiple definition of `tail'
/tmp/ccEDTgkN.o:(.bss+0x20): first defined here
main: In function `main':
(.text+0x10c): multiple definition of `main'
/tmp/ccEDTgkN.o:main.cpp:(.text+0x0): first defined here
main: In function `_init':
(.init+0x0): multiple definition of `_init'
/usr/lib/gcc/x86_64-linux-gnu/4.7/../../../x86_64-linux-gnu/crti.o:(.init+0x0): first defined here
/usr/lib/gcc/x86_64-linux-gnu/4.7/crtend.o:(.tm_clone_table+0x0): multiple definition of `__TMC_END__'
main:(.data+0x10): first defined here
/usr/bin/ld: error in main(.eh_frame); no .eh_frame_hdr table will be created.
collect2: ошибка: выполнение ld завершилось с кодом возврата 1


Подозреваю, что дело в функции append, т. к. элементы в новый список пишет именно она. Помогите разобраться. Буду очень благодарен.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.