VPF::Двухсвязный линейный список на C

Arks

Дата 6.12.2006, 07:14 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 197
Регистрация: 7.5.2006
Где: Барнаул

Репутация: нет
Всего: нет

Для начала поправь то, на что я тебе в предыдущем посте указал. Особенно в AddToHead - это ведь ведёт к будущим ошибкам.
Касательно, нового кода в проге, могу сказать, что функцию List::DelNum лучше спрятать подальше от глаз людских и никогда не использовать smile

Она во-первых, жутко медленная - список от начала и до нужного элемента проходится аж ТРИ РАЗА! Во-вторых, я так понял она должна бы удалять элемент в i-ой позиции, а похоже удаляет в i+1 -ой. Отсюда может и быть ошибка. Чтобы точно узнать, оттрасируй.
В любом случае, эту функцию следует переписать, т.к. ты сейчас работаешь со списком, будто он односвязный. У двусвязного списка перед односвязным преимущество в том, что нам не требуется проходить его когда нужно добавить (если мы знаем после/перед каким эл-м добавлять) или удалить элемент, где-то в середине. Нам достаточно знать адрес элемента для этого.
Т.е. вместо удаления по номеру, нужно написать удаление по адресу:

Код

void List::DelElem(Elem *ptr)
{
 if(!ptr)
   return;
 if(ptr->prev)
   ptr->prev->next = ptr->next;
 if(ptr->next)
   ptr->next->prev = ptr->prev;
 if(ptr==head)
   head = ptr->next;
 if(ptr==tail)
   tail = ptr->prev;
 delete ptr;
}

И ещё, когда работаешь со списками, рисуй наброски на бумаге - здорово поможет избагать ошибок.

Это сообщение отредактировал(а) Arks - 6.12.2006, 07:22

lesha_od

Дата 6.12.2006, 08:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 3.12.2006

Репутация: нет
Всего: нет

До того, как я прочитал последнее сообщение, я наладил ту программу, которая была. Потом добавил деструктор List и заменил удаление на показанное тобой. Сейчас она выглядит так:

Код


 #include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;

struct Elem 
{
    char surname[30];
    int year;
    double avg;
    Elem * next;
    Elem * prev;
    Elem(char * sn,int y, double a)
    {
        strcpy(surname,sn);
        year = y;
        avg = a;
        next=NULL;
        prev=NULL;
    }
    Elem()
    {
        year = 0;
        avg=0;
        strcpy(surname,"");
        next=NULL;
        prev=NULL;
    }
};

class List
{
    Elem *head;
    Elem *tail;
public:
    List():head(NULL),tail(NULL){}
    virtual ~List()
    {
        ClearAll();
    }
    void Print();
    void AddToHead(Elem &value);
    void DelSurname(const char *name);
    int HowMany();
    void DelNum(const int & position);
    void DeleteFromHead();
    void ClearAll();
    void DeleteFromTail();
    void DelElem(Elem *ptr);
};

void List::ClearAll()
{
    int size = HowMany();
    for (int i = 0;i<size;i++)
    {
        DeleteFromHead();
    }
}


void List::Print()
{
    Elem * ptr = head;
    if (head==NULL)
        cout<<endl<<" List is Empty"<<endl;
    cout<<endl;
    while(ptr)
    {
        cout<<ptr->surname<<endl;
        cout<<ptr->year<<endl;
        cout<<ptr->avg<<endl;
        if (ptr->next !=NULL) cout<<"Next El: "<<ptr->next->surname<<endl;
        if (ptr->prev !=NULL) cout<<"Prev El: "<<ptr->prev->surname<<endl;
        ptr = ptr->next;
    }

}

void List::AddToHead(Elem & value)
{
    Elem * newvalue = new Elem;
    strcpy(newvalue->surname,
        value.surname);
    newvalue->year = value.year;
    newvalue->avg = value.avg;
    if (head == NULL)
    {
        head = tail = newvalue;
    }
    else{
        newvalue->next = head;
        head = newvalue;
        newvalue->next->prev = head;
    }
}

void List::DelElem(Elem *ptr)
{
 if(!ptr)
   return;
 if(ptr->prev)
   ptr->prev->next = ptr->next;
 if(ptr->next)
   ptr->next->prev = ptr->prev;
 if(ptr==head)
   head = ptr->next;
 if(ptr==tail)
   tail = ptr->prev;
 delete ptr;
}

void List::DelSurname(const char *name)
{
    Elem * ptr=head;
    int i=0;
    for (int k=0; k<this->HowMany();k++)
    {
        if (!strcmp(ptr->surname,name))
        {    
            cout<<"Equals: "<<name<<" and "<<ptr->surname<<"\n";
            DelElem(ptr);
            break;
        }
        else
        {
            ptr=ptr->next;
        }
    }

};

int List::HowMany()
{
    Elem * ptr = head;
    int counter = 0;
    while (ptr)
    {
        ptr = ptr->next;
        counter++;
    }
    return counter;
}

void List::DeleteFromHead()
{
    if(NULL==head)
    {
        cout<<endl<<"\tList Is Empty !!!!!"<<endl;
        return;
    }
    Elem * ptr = head; 
    head = head->next; 
    if(head)
        head->prev = NULL;  
    delete ptr;
}

void List::DeleteFromTail()
{
    if(NULL==tail)
    {
        cout<<endl<<"\tList  Is Empty !!!!! \t\t\t"<<endl;
        return;
    }
    Elem * ptr = tail; 
    tail = tail->prev; 
    if(tail)
        tail->next = NULL;  
    delete ptr;
}

/*void List::DelNum(const int & position)
{
    int temp = HowMany();
    if (position>=0 && position<=temp-1)
    {
        if (0==position)
            DeleteFromHead();
        else if (HowMany()-1==position)
            DeleteFromTail();
        else
        {
            int count=0;
            Elem * ptr=head;
            while (position-1!=count)
            {
                ptr=ptr->next;
                count++;
            }
            Elem * temp=ptr->next;
            ptr->next=ptr->next->next;
            if (ptr->next->next != NULL) ptr->next->next->prev=ptr;
            else ptr->next->prev=ptr;
            delete temp;
            return;
        }
    }else
    {
        cout<<endl<<"\t Wrong index !!!!! \t\t\t"<<endl;    
        return;
    }
    
}*/

void main() {
List l1;
Elem e1;
strcpy(e1.surname,"aaa");
e1.year=1997;
e1.avg=15;
l1.AddToHead(e1);
Elem e2;
strcpy(e2.surname,"bbb");
e2.year=1953;
e2.avg=16;
l1.AddToHead(e2);
Elem e3;
strcpy(e3.surname,"ccc");
e3.year=1964;
e3.avg=16;
l1.AddToHead(e3);
Elem e4;
strcpy(e4.surname,"ddd");
e4.year=1955;
e4.avg=16;
l1.AddToHead(e4);
Elem e5;
strcpy(e5.surname,"eee");
e5.year=1955;
e5.avg=16;
l1.AddToHead(e5);
Elem e6;
strcpy(e6.surname,"fff");
e6.year=1955;
e6.avg=16;
l1.AddToHead(e6);
l1.Print();
cout<<"\n"<<l1.HowMany()<<"\n";
l1.DelSurname("aaa");
l1.Print();

}

Если все это соответствует заданию, то мне сейчас осталось:
1)- сортировка списка по полю «фамилия»,
2)- добавление и удаление заданного элемента из упорядоченного списка с поиском «слева» и «справа»

Для сортировки, наверное, имеет смысл выбрать самую простую (пузырьковую) и написать функцию Change (Elem *one, Elem *two).
А что значит 2-ое, то есть работа с упорядоченным списком?

Добавлено @ 08:34
Нашел в форуме такую сортировку:

Код


void swapitem(item*&a,item*&b)
{
    item c;
    c.element=b->element;
    b->element=a->element;
    a->element=c.element;
}
void bublesortlist(void)
{
   item *p,*q,*end=NULL;
   q=list->next;
   while( q->next!=end)
   {
       for(p=q;p->next!=end;p=p->next)
       {
           if(p->element>p->next->element)
           {
               swapitem(p,p->next);
           }
       }
       end=p;
   }
}

lesha_od

Дата 6.12.2006, 09:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 3.12.2006

Репутация: нет
Всего: нет

Я попытался сделать хотя бы смену элементов, но она не работает. Почему- пока не разобрался, наверное я меняю копии объектов. Вот так это выглядит:

Код


    void swapitem(Elem *a,Elem *b);
    void bublesortlist();

Код


void List::swapitem(Elem *a,Elem *b)
{
    cout<<"changing elements "<<a->surname<<" and "<<b->surname<<"\n";
        Elem c;
    strcpy(c.surname,b->surname);
    c.avg=b->avg;
    c.year=b->year;
    strcpy(b->surname,a->surname);
    b->avg=a->avg;
    b->year=a->year;
    strcpy(a->surname,c.surname);
    a->avg=c.avg;
    a->year=c.year;
}

Код


void List::bublesortlist()
{
   Elem *p,*q,*end=NULL;
   q=head;
   while( q->next!=end)
   {
       for(p=q;p->next!=end;p=p->next)
       {
           if(p->surname>p->next->surname)
           {
               swapitem(p,p->next);
           }
       }
       end=p;
   }
}

Код


l1.swapitem(&e1,&e2);

Убирал указатели (то есть swapitem(Elem a,Elem b)) - ничего не дало.

Полный текст программы:

Код


 #include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;

struct Elem 
{
    char surname[30];
    int year;
    double avg;
    Elem * next;
    Elem * prev;
    Elem(char * sn,int y, double a)
    {
        strcpy(surname,sn);
        year = y;
        avg = a;
        next=NULL;
        prev=NULL;
    }
    Elem()
    {
        year = 0;
        avg=0;
        strcpy(surname,"");
        next=NULL;
        prev=NULL;
    }
};

class List
{
    Elem *head;
    Elem *tail;
public:
    List():head(NULL),tail(NULL){}
    virtual ~List()
    {
        ClearAll();
    }
    void Print();
    void AddToHead(Elem &value);
    void DelSurname(const char *name);
    int HowMany();
    void DelNum(const int & position);
    void DeleteFromHead();
    void ClearAll();
    void DeleteFromTail();
    void DelElem(Elem *ptr);
    void swapitem(Elem *a,Elem *b);
    void bublesortlist();
};

void List::ClearAll()
{
    int size = HowMany();
    for (int i = 0;i<size;i++)
    {
        DeleteFromHead();
    }
}


void List::Print()
{
    Elem * ptr = head;
    if (head==NULL)
        cout<<endl<<" List is Empty"<<endl;
    cout<<endl;
    while(ptr)
    {
        cout<<ptr->surname<<endl;
        cout<<ptr->year<<endl;
        cout<<ptr->avg<<endl;
        if (ptr->next !=NULL) cout<<"Next El: "<<ptr->next->surname<<endl;
        if (ptr->prev !=NULL) cout<<"Prev El: "<<ptr->prev->surname<<endl;
        ptr = ptr->next;
        cout<<endl;
    }

}

void List::AddToHead(Elem & value)
{
    Elem * newvalue = new Elem;
    strcpy(newvalue->surname,
        value.surname);
    newvalue->year = value.year;
    newvalue->avg = value.avg;
    if (head == NULL)
    {
        head = tail = newvalue;
    }
    else{
        newvalue->next = head;
        head = newvalue;
        newvalue->next->prev = head;
    }
}

void List::DelElem(Elem *ptr)
{
 if(!ptr)
   return;
 if(ptr->prev)
   ptr->prev->next = ptr->next;
 if(ptr->next)
   ptr->next->prev = ptr->prev;
 if(ptr==head)
   head = ptr->next;
 if(ptr==tail)
   tail = ptr->prev;
 delete ptr;
}

void List::DelSurname(const char *name)
{
    Elem * ptr=head;
    int i=0;
    for (int k=0; k<this->HowMany();k++)
    {
        if (!strcmp(ptr->surname,name))
        {    
            cout<<"Equals: "<<name<<" and "<<ptr->surname<<"\n";
            DelElem(ptr);
            break;
        }
        else
        {
            ptr=ptr->next;
        }
    }

};

int List::HowMany()
{
    Elem * ptr = head;
    int counter = 0;
    while (ptr)
    {
        ptr = ptr->next;
        counter++;
    }
    return counter;
}

void List::DeleteFromHead()
{
    if(NULL==head)
    {
        cout<<endl<<"\tList Is Empty !!!!!"<<endl;
        return;
    }
    Elem * ptr = head; 
    head = head->next; 
    if(head)
        head->prev = NULL;  
    delete ptr;
}

void List::DeleteFromTail()
{
    if(NULL==tail)
    {
        cout<<endl<<"\tList  Is Empty !!!!! \t\t\t"<<endl;
        return;
    }
    Elem * ptr = tail; 
    tail = tail->prev; 
    if(tail)
        tail->next = NULL;  
    delete ptr;
}

/*void List::DelNum(const int & position)
{
    int temp = HowMany();
    if (position>=0 && position<=temp-1)
    {
        if (0==position)
            DeleteFromHead();
        else if (HowMany()-1==position)
            DeleteFromTail();
        else
        {
            int count=0;
            Elem * ptr=head;
            while (position-1!=count)
            {
                ptr=ptr->next;
                count++;
            }
            Elem * temp=ptr->next;
            ptr->next=ptr->next->next;
            if (ptr->next->next != NULL) ptr->next->next->prev=ptr;
            else ptr->next->prev=ptr;
            delete temp;
            return;
        }
    }else
    {
        cout<<endl<<"\t Wrong index !!!!! \t\t\t"<<endl;    
        return;
    }
    
}*/


void List::swapitem(Elem *a,Elem *b)
{
    cout<<"changing elements "<<a->surname<<" and "<<b->surname<<"\n";
    Elem c;
    strcpy(c.surname,b->surname);
    c.avg=b->avg;
    c.year=b->year;
    strcpy(b->surname,a->surname);
    b->avg=a->avg;
    b->year=a->year;
    strcpy(a->surname,c.surname);
    a->avg=c.avg;
    a->year=c.year;
}

void List::bublesortlist()
{
   Elem *p,*q,*end=NULL;
   q=head;
   while( q->next!=end)
   {
       for(p=q;p->next!=end;p=p->next)
       {
           if(p->surname>p->next->surname)
           {
               swapitem(p,p->next);
           }
       }
       end=p;
   }
}

void main() {
List l1;
Elem e1;
strcpy(e1.surname,"aaa");
e1.year=1997;
e1.avg=15;
l1.AddToHead(e1);
Elem e2;
strcpy(e2.surname,"bbb");
e2.year=1953;
e2.avg=16;
l1.AddToHead(e2);
Elem e3;
strcpy(e3.surname,"ccc");
e3.year=1964;
e3.avg=16;
l1.AddToHead(e3);
Elem e4;
strcpy(e4.surname,"ddd");
e4.year=1955;
e4.avg=16;
l1.AddToHead(e4);
Elem e5;
strcpy(e5.surname,"eee");
e5.year=1955;
e5.avg=16;
l1.AddToHead(e5);
Elem e6;
strcpy(e6.surname,"fff");
e6.year=1955;
e6.avg=16;
l1.AddToHead(e6);
l1.Print();
cout<<"\n"<<l1.HowMany()<<"\n";
l1.swapitem(&e1,&e2);
//l1.DelSurname("aaa");
l1.Print();

}

Это сообщение отредактировал(а) lesha_od - 6.12.2006, 09:24

Annihilator

Дата 6.12.2006, 09:32 (ссылка)

(нет голосов)

Загрузка ...

bytegrinder

Профиль
Группа: Участник
Сообщений: 493
Регистрация: 21.11.2006
Где: Омск

Репутация: 1
Всего: 3

Цитата(lesha_od @ 6.12.2006, 01:35

)

в C++ я ничего не понимаю в указателях

А вот это оччччень зря, друг! Обязательно разберись! Без них какой смысл??

--------------------

Если вы не можете сделать хоpошyю пpогpаммy, сделайте, чтобы она по кpайней меpе выглядела хоpошо

Arks

Дата 6.12.2006, 11:06 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 197
Регистрация: 7.5.2006
Где: Барнаул

Репутация: нет
Всего: нет

Для начала советую подумать, что случится с указателем ptr после его удаления. Понял? Так вот, а ты его после этого используешь! Если не понял о чём, я можешь глянуть листинг ниже. Там новая правильная версия функции DelElem.

Когда же ты обмениваешь элементы списка между собой в сортировке, то вовсе ненужно физически их содержимое обменивать местами, достаточно просто поменять соответсвующие связи. Разбираться, что у тебя там не так с сортировкой не охото, сам немного подумай ;)
Единственное скажу, что это не лучший метод. Для не очень длинных списков (<20) эффективно будет применять сортировку вставками (InsertSort), а для длинных списков сорт. слияниями (MergeSort).

Код


Elem* List::DelElem(Elem *ptr)
{
 if(!ptr)
   return;
 if(ptr->prev)
   ptr->prev->next = ptr->next;
 if(ptr->next)
   ptr->next->prev = ptr->prev;
 if(ptr==head)
   head = ptr->next;
 if(ptr==tail)
   tail = ptr->prev;
 Elem *resptr = prt->next;
 delete ptr;
 return resptr;
}

П.С.: Почитай про указатели. Да же на этом форуме (в этом разделе) кое-что есть.

lesha_od

Дата 6.12.2006, 13:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 3.12.2006

Репутация: нет
Всего: нет

Про указатели я знаю в общих чертах. Когда долго программируешь на Java, совсем не охота запутываться с ссылками\указателями на C.

Я пробовал и ссылки поменять на элементы. Но по неизвестной мне причине они не меняются местами, хоть убей. Сортировку-то я сделаю, любым способом.

Код


void swapitem(Elem *a,Elem *b);

void List::swapitem(Elem *a,Elem *b)
{
Elem * c;
c=a;
a=b;
b=c;
}

Должно работать?

Arks

Дата 6.12.2006, 21:58 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 197
Регистрация: 7.5.2006
Где: Барнаул

Репутация: нет
Всего: нет

Неа, не должно. smile

Ты обмениваешь значения указателей, а не тех элементов на которые они указывают.
Тоже самое, что и в ссылках Java, там таким присваиванием ты обменяешь ссылки, а не сами объекты.
Указатели Си и ссылки Java по сути одно и тоже (попровте меня кто-нибудь, если ошибаюсь), по-крайней мере я не вижу между ними никакой разницы, кроме синтаксиса.
Т.е. тебе нужно так:

Код

void List::swapitem(Elem *a,Elem *b)
{
 Elem c=*a;
 *a = *b;
 *b = c;
}

В Java ты бы делал это через клонирование.

Но это не эффективно. То что я предлагал, это изменения соответсвующих указателей a->next; a->prev; b->next; b->prev.
Итак, берёшь бумагу. Рисуешь прямоугольники-кирпичи, которые будут обозначать элементы. Рисуешь связи, и смотришь как надо изменить (рисуя эти изменения на бумаге) эти связи. Вперёд и с песней smile

lesha_od

Дата 7.12.2006, 09:35 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 3.12.2006

Репутация: нет
Всего: нет

Arks,
твой код меняет сами элементы, но не меняет указатели на них соседних элементов... то есть функция Print() выдает то же самое и до, и после обмена.

Тогда я попробовал с указателями.... вроде бы связи правильные, но не работает из-за синтаксиса.

Код


void List::swapitem(Elem *a,Elem *b)
{
 a->next=b->next;
 b->next=b->prev;
 b->prev=a->prev;
 a->prev=b;
}

и плюс в эту функцию нужно добавить

Код


 if (a->prev!=NULL) a->prev->next=b;
 else head=b;
 if (b->next!=NULL) b->next->prev=a;
 else tail=a;

(связи с предыдущими элементами)

Но не работает.

Это сообщение отредактировал(а) lesha_od - 7.12.2006, 09:36

Arks

Дата 7.12.2006, 11:57 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 197
Регистрация: 7.5.2006
Где: Барнаул

Репутация: нет
Всего: нет

Проверил все рассмотренные варианты.

1) У тебя swapitem, кстати, был совершенно корректно написан ещё в этом посте.
Если ты запустишь сортировку, она должна отработать верно, если ещё где-нибудь не закосячил.
Просто, когда меняешь местами e1 и e2, ты меняешь местами именно их, а не то, что содержится в списке. Посмотри адреса в указателях, они разные. Причина в том, что ты копируешь элементы при добавлении. Если их не копировать, то всё ок:

Код

void List::AddToHead(Elem & value)
{
    if (head == NULL)
    {
        head = tail = &value;
    }
    else{
        value.next = head;
        head = &value;
        value.next->prev = head;
        value.prev = NULL;
    }
}

Правда в этом случае, придётся немного изменить ф-цию main, чтобы не вылетало ошибок (ведь список удаляет свои элементы):

Код

void main() {
List l1;
Elem *e1 = new Elem;
strcpy(e1->surname,"aaa");
e1->year=1997;
e1->avg=15;
l1.AddToHead(*e1);
Elem *e2 = new Elem;
strcpy(e2->surname,"bbb");
e2->year=1953;
e2->avg=16;
l1.AddToHead(*e2);
Elem *e3 = new Elem;
strcpy(e3->surname,"ccc");
e3->year=1964;
e3->avg=16;
l1.AddToHead(*e3);
Elem *e4 = new Elem;
strcpy(e4->surname,"ddd");
e4->year=1955;
e4->avg=16;
l1.AddToHead(*e4);
Elem *e5 = new Elem;
strcpy(e5->surname,"eee");
e5->year=1955;
e5->avg=16;
l1.AddToHead(*e5);
Elem *e6 = new Elem;
strcpy(e6->surname,"fff");
e6->year=1955;
e6->avg=16;
l1.AddToHead(*e6);
l1.Print();
cout<<"\n"<<l1.HowMany()<<"\n";
l1.swapitem(e2,e1);
//l1.DelSurname("aaa");
l1.Print();
getch();
}

2)Твой вариант, как я и сказал не работает. Вот этот:

Код

void List::swapitem(Elem *a,Elem *b)
{
Elem * c;
c=a;
a=b;
b=c;
}

3) Мой вариант тоже не катит smile

Связи портятся.

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

Код

    a->next=b->next;
    b->next=a;
    b->prev=a->prev;
    a->prev=b;
    if(a->next)
        a->next->prev=a;
    else
        tail = a;
    if(b->prev)
        b->prev->next=b;
    else
        head = b;

Ещё элементы должны следовать в правильном порядке, т.е. чтобы работало должно быть так:

Код

...
l1.swapitem(e2,e1);
...

lesha_od

Дата 7.12.2006, 14:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 3.12.2006

Репутация: нет
Всего: нет

Спасибо за такой подробный ответ! Я уже начинаю понимать, как эти указатели работают smile

Программа работает, выполняет требуемое от нее. Единственное, что не работает - если вручную запустить смену элементов, и до или после нее попытаться удалить "хвостовой" элемент с фамилией "ааа", то выдается ошибка.

Update: оказалось, сравнение строк не работает по знаку ">". Видимо, надо сравнивать по-другому.

Вот код работающей программы:

Код


#include <iostream>
#include <conio.h>
#include <windows.h>
using namespace std;
struct Elem 
{
    char surname[30];
    int year;
    double avg;
    Elem * next;
    Elem * prev;
    Elem(char * sn,int y, double a)
    {
        strcpy(surname,sn);
        year = y;
        avg = a;
        next=NULL;
        prev=NULL;
    }
    Elem()
    {
        year = 0;
        avg=0;
        strcpy(surname,"");
        next=NULL;
        prev=NULL;
    }
};
class List
{
    Elem *head;
    Elem *tail;
public:
    List():head(NULL),tail(NULL){}
    virtual ~List()
    {
        ClearAll();
    }
    void Print();
    void AddToHead(Elem &value);
    void DelSurname(const char *name);
    int HowMany();
    void DelNum(const int & position);
    void DeleteFromHead();
    void ClearAll();
    void DeleteFromTail();
    void DelElem(Elem *ptr);
    void swapitem(Elem* a,Elem* b);
    void bublesortlist();
};
void List::ClearAll()
{
    int size = HowMany();
    for (int i = 0;i<size;i++)
    {
        DeleteFromHead();
    }
}
void List::Print()
{
    Elem * ptr = head;
    if (head==NULL)
        cout<<endl<<" List is Empty"<<endl;
    cout<<endl;
    while(ptr)
    {
        cout<<ptr->surname<<endl;
        cout<<ptr->year<<endl;
        cout<<ptr->avg<<endl;
        if (ptr->next !=NULL) cout<<"Next El: "<<ptr->next->surname<<endl;
        if (ptr->prev !=NULL) cout<<"Prev El: "<<ptr->prev->surname<<endl;
        ptr = ptr->next;
        cout<<endl;
    }
}


void List::AddToHead(Elem & value)
{
    if (head == NULL)
    {
        head = tail = &value;
    }
    else{
        value.next = head;
        head = &value;
        value.next->prev = head;
        value.prev = NULL;
    }
}

void List::DelElem(Elem *ptr)
{
 if(!ptr)
   return;
 if(ptr->prev)
   ptr->prev->next = ptr->next;
 if(ptr->next)
   ptr->next->prev = ptr->prev;
 if(ptr==head)
   head = ptr->next;
 if(ptr==tail)
   tail = ptr->prev;
 delete ptr;
}

void List::DelSurname(const char *name)
{
    Elem * ptr=head;
    int i=0;
    for (int k=0; k<this->HowMany();k++)
    {
        if (!strcmp(ptr->surname,name))
        {    
            cout<<"Equals: "<<name<<" and "<<ptr->surname<<"\n";
            DelElem(ptr);
            break;
        }
        else
        {
            ptr=ptr->next;
        }
    }
};

int List::HowMany()
{
    Elem * ptr = head;
    int counter = 0;
    while (ptr)
    {
        ptr = ptr->next;
        counter++;
    }
    return counter;
}
void List::DeleteFromHead()
{
    if(NULL==head)
    {
        cout<<endl<<"\tList Is Empty !!!!!"<<endl;
        return;
    }
    Elem * ptr = head; 
    head = head->next; 
    if(head)
        head->prev = NULL;  
    delete ptr;
}
void List::DeleteFromTail()
{
    if(NULL==tail)
    {
        cout<<endl<<"\tList  Is Empty !!!!! \t\t\t"<<endl;
        return;
    }
    Elem * ptr = tail; 
    tail = tail->prev; 
    if(tail)
        tail->next = NULL;  
    delete ptr;
}

void List::swapitem(Elem* a,Elem* b)
{
    a->next=b->next;
    b->next=a;
    b->prev=a->prev;
    a->prev=b;
    if(a->next)
        a->next->prev=a;
    else
        tail = a;
    if(b->prev)
        b->prev->next=b;
    else
        head = b;
}

void List::bublesortlist()
{
   Elem *p,*q,*end=NULL;
   q=head;
   while( q->next!=end)
   {
       for(p=q;p->next!=end;p=p->next)
       {
           if(p->surname>p->next->surname)
           {
               swapitem(p,p->next);
           }
       }
       end=p;
   }
}

void main() {
List l1;
Elem *e1 = new Elem;
strcpy(e1->surname,"aaa");
e1->year=1997;
e1->avg=15;
l1.AddToHead(*e1);
Elem *e2 = new Elem;
strcpy(e2->surname,"bbb");
e2->year=1953;
e2->avg=16;
l1.AddToHead(*e2);
Elem *e3 = new Elem;
strcpy(e3->surname,"ccc");
e3->year=1964;
e3->avg=16;
l1.AddToHead(*e3);
Elem *e4 = new Elem;
strcpy(e4->surname,"ddd");
e4->year=1955;
e4->avg=16;
l1.AddToHead(*e4);
Elem *e5 = new Elem;
strcpy(e5->surname,"eee");
e5->year=1955;
e5->avg=16;
l1.AddToHead(*e5);
Elem *e6 = new Elem;
strcpy(e6->surname,"fff");
e6->year=1955;
e6->avg=16;
l1.AddToHead(*e6);
l1.Print();
cout<<"\n"<<l1.HowMany()<<"\n";
l1.DelSurname("aaa");
l1.Print();
l1.bublesortlist();
l1.Print();
getch();
}

а вот строчки, которые в любом порядке убивают программу:

Код


cout<<"\n"<<l1.HowMany()<<"\n"; //эта строка просто показывает, где начинается код
l1.DelSurname("aaa");
l1.swapitem(e3,e2);

Попробую сейчас разобраться, почему ошибка. Наверно какой-то указатель мы таки забыли поставить на место.
P.S. А в принципе, это неважно. Программа же должна быть инкаспулированной, и работать с (e3,e2) необязательно. А в остальных случаях она работает, что отлично.

Это сообщение отредактировал(а) lesha_od - 7.12.2006, 14:36

lesha_od

Дата 11.12.2006, 07:39 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 3.12.2006

Репутация: нет
Всего: нет

Я начал делать интерфейс ввода данных самим пользователем, и натолкнулся на ошибку. Когда делаю так:

Код


Elem *e1 = new Elem;
strcpy(e1->surname,"aaa");
e1->year=1997;
e1->avg=15;
l1.AddToHead(*e1);
Elem *e5 = new Elem;
strcpy(e5->surname,"bbb");
e5->year=1945;
e5->avg=1;
l1.AddToHead(*e5);
l1.Print();

то все работает нормально.
А как добавить созданный пользователем элемент? Когда я делаю так:

Код


char sname[20];
   int y;
double avg;
     cout<<"Surname: "; 
              cin>>sname;
               cout<<endl<<"Year: ";
               cin>>y;
cout<<endl<<"Average score: ";
              cin>>avg;
 l1.AddToHead(Elem(sname,y,avg));

то программа зависает при распечатке, либо при удалении - в общм, что-то с копиями и объектами не так smile

Arks

Дата 11.12.2006, 18:43 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 197
Регистрация: 7.5.2006
Где: Барнаул

Репутация: нет
Всего: нет

1) Разве p->surname - строка? Это всего лишь указатель на неё. Для строк есть свои функции. В том числе и для сравнения. Ты сравниваешь указатели. Кстати в DelSurname ты ведь нужную ф-цию используешь, а здесь забыл!

2)Ты память портишь, т.к. не создаёшь таким образом новый объект. Надо:

Код

l1.AddToHead(new Elem(sname,y,avg));

только AddToHead надо перекроить, т.к. сейчас ей параметр передаётся по ссылке, а нам надо по указателю:

Код

void List::AddToHead(Elem *value) {...};

Можно и не перекраивать, но имо, так даже правильнее будет.

3)

Код

cout<<"\n"<<l1.HowMany()<<"\n"; //эта строка просто показывает, где начинается код
l1.DelSurname("aaa");
l1.swapitem(e3,e2);

Таже рожа толька в профиль: смотри про правильный порядок smile

А ещё лучше посмотри, что со связями творится в этой функции, после её вызова в отсортированном списке.
Не хочешь париться с порядком. Проверяй в его в функции.

lesha_od

Дата 12.12.2006, 15:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 48
Регистрация: 3.12.2006

Репутация: нет
Всего: нет

Все отлично заработало, кроме сортировки... я к сожалению не умею нормально отлаживать. Надеюсь, преподаватель сможет помочь с ошибкой.

Как называется функция, проверяющая, является ли введенное значение числом? Скажем я пишу

Код


int i;
cin>>i;

И мне надо точно знать, что это число. А если не число, то выдать сообщение пользователю.

JackYF

Дата 12.12.2006, 15:27 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

lesha_od,

i в данном случае всегда будет целым числом со знаком.
А проверять придется флаги у cin.

--------------------

Пожаловаться на меня как модератора можно здесь.

Arks

Дата 12.12.2006, 16:33 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 197
Регистрация: 7.5.2006
Где: Барнаул

Репутация: нет
Всего: нет

Цитата

И мне надо точно знать, что это число. А если не число, то выдать сообщение пользователю.

Вот так:

Код

int i;
 if(!(cin >> i))
  cout << "not a number";

Я это кстати, где то на этом форуме нашёл. smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »