Двухсвязный список, обработка и сортировка

  • Автор темы aaaleks
  • Дата начала
Статус
Закрыто для дальнейших ответов.
A

aaaleks

#1
В университете дали задание сделать двухсвязный линейный список, над которым можно было бы выполнять определенные действия.
-------
Задание
Реализовать линейный двухсвязный список для хранения следующих данных:
- фамилия,
- год поступления,
-средний балл.
Обеспечить выполнение операций:
- добавление элемента в неупорядоченный список,
- удаление элемента с заданным полем «фамилия» в неупорядоченном списке,
- сортировка списка по полю «фамилия»,
- добавление и удаление заданного элемента из упорядоченного списка с поиском «слева» и «справа»,
- распечатка содержимого списка.

Структура моего списка:

Код:
struct Elem 
{
char surname[30];
int year;
double avg;
Elem * next;
Elem * prev;
......................
};
class List
{
Elem *head;
Elem *tail;
А вот функции обмена элементов сортировки, причем в функции сортировки "вылетает" внутренний цикл и выдается ошибка выполнения.

Код:
void List::swapitem(Elem* a,Elem* B)
{
cout<<"Changing "<<a->surname<<" and "<<b->surname<<"\n";
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(strcmp(p->next->surname,p->surname)>0)
{
swapitem(p,p->next);
}
else cout<<"Change not needed\n";
}
end=p;
}
}
Вот полная программа
Код:
#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()
{
cout<<"Printing\n";
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)
{
cout<<"Changing "<<a->surname<<" and "<<b->surname<<"\n";
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(strcmp(p->next->surname,p->surname)>0)
{
swapitem(p,p->next);
}
else cout<<"Change not needed\n";
}
end=p;
}
}
void main() {
List l1;
Elem *e1 = new Elem;
strcpy(e1->surname,"Someone");
e1->year=1997;
e1->avg=15;
l1.AddToHead(*e1);
Elem *e2 = new Elem;
strcpy(e2->surname,"Fedor");
e2->year=1953;
e2->avg=16;
l1.AddToHead(*e2);
Elem *e3 = new Elem;
strcpy(e3->surname,"Maxxx");
e3->year=1964;
e3->avg=16;
l1.AddToHead(*e3);
Elem *e4 = new Elem;
strcpy(e4->surname,"Baloo");
e4->year=1955;
e4->avg=16;
l1.AddToHead(*e4);
Elem *e5 = new Elem;
strcpy(e5->surname,"Aleks");
e5->year=1955;
e5->avg=16;
l1.AddToHead(*e5);
Elem *e6 = new Elem;
strcpy(e6->surname,"Fill");
e6->year=1955;
e6->avg=16;
l1.AddToHead(*e6);
cout<<l1.HowMany()<<"\n";
l1.bublesortlist();
l1.Print();
getch();
}
Посмотрите, плиз, почему "вылетает" программа. Весь код не надо рассматривать, только верхние отрывки...
 
Статус
Закрыто для дальнейших ответов.