Двусвязный список и манипуляции с ним

[Solidera]

Доброго времени суток.

Задача такая:
Разработать и отладить программу. Предусмотреть:
- ввод данных из файла
- вывод результатов на экран в виде таблицы
Список школ имеет следующую структуру: номер школы – район - количество учеников начальных классов - количество учеников среднего звена – количество старшеклассников - общее количество учеников. При вводе рассчитайте общее количество учеников и выведите информацию о школах в виде таблицы.
1) Вывести номера школ и район, в которых учеников начальных классов минимально (таких может быть несколько).
2) Вывести всю информацию о школах заданного района (название района ввести с клавиатуры).
3) Выполнить сортировку списка по общему количеству учеников, вывести отсортированный список.
_______
Какие-то наброски уже написала.
Собственно описание класса списка и методов:

#include <iostream>
#include <string>
using namespace std;

typedef unsigned short int USI;

struct School
{
  USI number,primary,middle,senior;
  string district;

  struct School *next;
  struct School *prev;
} info;

class List
{
public:
	School *pHead; // указатель на первый элемент списка
	School *pTail; // указатель на последний элемент списка
	int countElem; // количество элементов в списке

	List();  // конструктор
	~List(); // деструктор

	void addToList(USI number,USI primary,USI middle,USI senior,string district);
	// функция добавки школы в список
	void printList();       // функция вывода на экран всех элементов списка
	void delAllList();	    // функция удаления всех элементов списка
	void delElem(int numb); // удаление одного элемента
};

List::List()
{
	pHead=NULL;
	pTail=NULL;
	countElem=0;
};

List::~List()
{
	delAllList();
};

void List::addToList(USI number,USI primary,USI middle,USI senior,string district)	//реализация функции добавления
{
	School *temp=new School; // создается временный элемент
	if(pHead==NULL)		     // если это первый элемент
	{
		temp->prev=NULL; // обнуляем указатель на предшествующий элемент
		temp->next=NULL; // то же самое с последующим элементом
		pHead=temp;	     // "голова" указывает на созданный элемент
	}
	else // если не первый
		pTail->next=temp; // предыдущий указывает на него

	temp->number=number; // копируем данные
	temp->primary=primary;
	temp->middle=middle;
	temp->senior=senior;
	temp->district=district.c_str();
	temp->next=NULL;  // последующего элемента нет (добавляем же в конец)
	temp->prev=pTail; // указываем на предыдущий элемент, на который нацелен pTail
	pTail=temp;	      // а теперь хвостовой элемент указывает на последний (добавленный)
	countElem++;	  // увеличиваем счетчик элементов в списке
};

void List::delAllList() // реализация удаления всех элементов списка
{
	while(pHead!=NULL) // пока не указываем на хвост
    {
		School *pTemp=pHead; // создаем временный элемент
		pHead=pHead->next;   // присваиваем ему указатель на следующий
		delete pTemp;		 // и удаляем его
    }
 
	pHead=NULL;
	pTail=NULL;
	countElem=0;
};

void List::delElem(int numb) // функция удаления элемента
{
	School *pTemp=pHead; // создаем временный элемент

	if((numb>countElem)||(numb<1)) // если указанный элемент не существует
		std::cout<<"There is no such element in the list!"; // выводим предупреждение на экран
	else
	{
		for(int i=1; i!=numb; i++) // переходим до этого элемента
			pTemp=pTemp->next;
 
		if(pTemp->prev==NULL) // если удаляем первый элемент
		{
			if(countElem==1) // если этот элемент единственный
			{
				pHead=NULL;
				pTail=NULL;
			}
			else // если он первый, но не единственный
			{
				pTemp->next->prev=NULL;
				pHead=pTemp->next;
			}
 
			delete pTemp;
			countElem--;
			std::cout<<"Element was deleted from the list";
			return;
		}
 
		if(pTemp->next==NULL) // если удаляем последний элемент
		{
			pTemp->prev->next=NULL; // предыдущий элемент указывает на NULL
			pTail=pTemp->prev;	  // указатель на последний элемент указывает на предпоследний

			delete pTemp;
			countElem--;
			std::cout<<"Element was deleted from the list";
			return;
		}		

		if(pTemp->next!=NULL&&pTemp->prev!=NULL) // если элемент находится в центре списка
		{
			pTemp->prev->next=pTemp->next; // предыдущий элемент указывает на следующий
			pTemp->next->prev=pTemp->prev; // следующий указывает на предыдущий
			delete pTemp;
			countElem--;
			std::cout<<"Element was deleted from the list";
			return;
		}
	}
};

[Solidera]

Целиком не помещается.
________
С первым заданием вроде справилась. С остальными проблемы.
Хочу, чтобы во втором задании данные о каждой новой школе района, указанного в Edit, добавлялись в message.
Последний элемент списка не воспринимает. Где я накосячила?

AnsiString message;
	School *pTemp=NewList.pHead;
	message="Район ";
	if(NewList.countElem>1)
	{
		do
		{
			if(pTemp->district.data()==Edit7->Text)
			{
				message += pTemp->district.data();
				message+="\nШкола №"+IntToStr(pTemp->number);
				message+="\nВ начальных классах - "+IntToStr(pTemp->primary)+" человек";
				message+="\nСреднее звено - "+IntToStr(pTemp->middle)+" человек";
				message+="\nСтаршеклассники - "+IntToStr(pTemp->senior)+" человек";
			}
			pTemp=pTemp->next;
		}
		while(pTemp->next!=NULL);
	}

	ShowMessage(message);
	Edit7->Clear();

Попробовала написать ещё что-то типа сортировки списка пузырём к третьему заданию. Для вывода отсортированного списка StringGrid должен очищаться, а потом туда загоняются данные из обновлённого списка.
Во-первых, очень медленно. Три элемента "отсортировал" секунд за пять (может, из-за того, что машина слабая), на четырёх уже подвис. Ну, раз пузырьком, то так, по идее, и должно быть, но скорее всего, это я где-то напортачила. Как быстрее всего список можно отсортировать?

Во-вторых, вернусь к трём "типа отсортированным" элементам: наименьший элемент, который изначально был в начале, просто продублировался в конце, заменив средний по размеру элемент, стоявший там изначально. Ошибка в самой сортировке или в выводе?

School *pTemp=NewList.pHead;
	bool isDone=false;

	while(pTemp->next)
	{
		while(!isDone)
		{
			isDone=true;
			if((pTemp->primary+pTemp->middle+pTemp->senior)>(pTemp->next->primary+pTemp->next->middle+pTemp->next->senior))
			{
				isDone=false;
				School *temp=new School;
				temp=pTemp;
				pTemp=pTemp->next;
				pTemp->next=temp;
				delete temp;
			}
		}
		pTemp=pTemp->next;
	}

	StringGrid1->ColCount=NewList.countElem+2;
	StringGrid1->Cols[1]->Clear();

	int currentCol=1;
	StringGrid1->ColCount=NewList.countElem+1;
	{
		StringGrid1->Cells[currentCol][0]=pTemp->number;
		StringGrid1->Cells[currentCol][1]=pTemp->district.data();
		StringGrid1->Cells[currentCol][2]=pTemp->primary;
		StringGrid1->Cells[currentCol][3]=pTemp->middle;
		StringGrid1->Cells[currentCol][4]=pTemp->senior;
		StringGrid1->Cells[currentCol][5]=pTemp->primary+pTemp->middle+pTemp->senior;

		currentCol++;
	}
	while(pTemp->next!=NULL);

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

[BizCray]

Более компактно опишите проблему. Не воспринимается.
Да и что не выходит? Все задание не выходит?

[Vzlom]

где код скатали? Если вы это смогли написать, думаю дальше с выводом проблем не должно быть у вас, вы бы и вывод дописали. И ввод из файла

[Nuklon]

Три элемента "отсортировал" секунд за пять (может, из-за того, что машина слабая)

Боже упаси! Скорее не машина, а код
Я укажу вектор в какую сторону двигаться, остальное сами...

#include <iostream>
#include <string>
using std::string;
using std::cout;



// сортировка слиянием
template<typename T>
T* merge_sort(T* lst, T** ptail, bool (*pred_cmp)(const T*, const T*)) {

   if((lst == NULL) || (lst->next == NULL))
        return lst;

   T* ptr, *next, *tail;
   T* iter = lst;
   T* last = lst;

   ptr = next = tail = NULL;
   for(T* tmp = lst; (tmp != NULL) && (tmp->next != NULL); tmp = tmp->next->next) {
        last = iter;
        iter = iter->next;
   }
   last->next = NULL;

   lst  = merge_sort(lst,  ptail, pred_cmp);
   iter = merge_sort(iter, ptail, pred_cmp);

   for(; (lst != NULL) || (iter != NULL); ) {
       if(iter == NULL) {
           next = lst;
           lst  = lst->next;
       } else if(lst == NULL) {
           next = iter;
           iter = iter->next;
       } else if((*pred_cmp)(lst, iter)){
           next = lst;
           lst  = lst->next;
       } else {
           next = iter;
           iter = iter->next;
       }

       if(ptr == NULL) 
            ptr = next;
       else 
            tail->next = next;
 
       next->prev = tail;
       tail = next;
   }	
   *ptail = tail;
    return ptr;
}





// здесь кусок кода для наглядности сортировки

typedef unsigned short int USI;

struct School {
  USI number,primary,middle,senior;
  string district;

  School *next;
  School *prev;
} info;


// добавление в хвост
void AddBack(School** head, School** tail, USI number, USI primary, 
             USI middle, USI senior, const string& district) {

  School* snew   = new School();
  snew->number   = number;
  snew->primary  = primary;
  snew->middle   = middle;
  snew->senior   = senior;
  snew->district = district;

  if(*head != NULL) {
      snew->next = snew;
      snew->prev = *tail;
      snew->prev->next = snew;
      *tail = snew;
  } else {
     *head = snew;
      snew->next = *head;
      snew->prev = NULL;
      *tail = *head;
   }
   (*tail)->next = NULL;
}


// удаление из головы
void  PopHead(School** head, School** tail) {
    if(*head == NULL)
         return;
    if(*head == *tail) {
         delete *head;
         *head = *tail = NULL;
         return;
    }
    School* tmp = *head;
    *head = (*head)->next;
    (*head)->prev = NULL;
    delete tmp;
}



// 
bool func_cmp(const School* a, const School* b) {
   return (a->primary+a->middle+a->senior) > (b->primary+b->middle+b->senior);
}



int  main(void) {
	School* head = NULL;
	School* tail = NULL;

	//...
	for(int i = 1; i <= 255; i++) {
		AddBack(&head, &tail, (USI)i, (USI)(rand()%255), 
                        (USI)(rand()%255), (USI)(rand()%255), "Sample");
	}

	// отсортируем список
	head = merge_sort(head, &tail, &func_cmp);

	//...
	for(;head != NULL; PopHead(&head, &tail))
             cout << "sum: " << (head->primary+head->middle+head->senior) << std::endl;
	return 0;
}

Пример работы кода

[Solidera]

Сообщение от Vzlom

где код скатали? Если вы это смогли написать, думаю дальше с выводом проблем не должно быть у вас, вы бы и вывод дописали. И ввод из файла

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

Nuklon, Вам спасибо. Буду разбираться сейчас.