Форум::Улучшение программ::Односвязный список-реализация стека

Форум

Список форумов

Последние сообщения

Добро пожаловать Гость [Зарегистрироваться] Войти

Ответить

« ПерваяПредыдущая12Следующая Последняя »

Тема :Односвязный список-реализация стека.. 25-02-2010 21:38:43

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

Пишу реализацию класса стека через односвязный список. В C++Builder должен быть шаблон стандартный, но надо знать самому как это работает.
вот, то, что есть у меня:

Code:

struct node
{
int value;/
node *next;
};

class cList
{
public:
 cList();
 ~cList();

 void Add(int value);
 void Delete();
 void DeleteAll();
 void SortByValue();
 void Print();
 int GetCount() const;

private:
 node *top;
 node *bot;

 int itsCount;
};

cList::cList()
{
top=NULL;
bot=NULL;
itsCount=0;
}

cList::~cList()
{
DeleteAll();
}

void cList::Add(int value)
{
node *temp=new node;

temp->value=value;

if(top == NULL)
 {
 temp->next=NULL;
 top=bot=temp;
 }
else//иначе
 {
 top=temp;
 temp->next=bot;
 bot=temp;
 }

itsCount++;
}

void cList::Delete()
{
node *temp=top;

top=top->next;
delete temp;

itsCount--;
}

void cList::DeleteAll()
{
while(top!=NULL)
 {
 Delete();
 }
}

void cList::Print()
{
node *temp=top;
while(temp!=NULL)
 {
 coutnext;
  if(Next->value value)
   {
   int TmpValue=Current->value;
   Current->value=Next->value;
   Next->value=TmpValue;
   isChange=false;
   }
  Current=Current->next;
  }
 }
}

вот. Я хочу попросить автора этих статей http://www.trivialcoding.ru/Programs/Borland-C-Builder/ (а как я понимаю это Captain), что бы рассказал как изменить код, что бы он был более "элегантным" и "красивым". И еще, если не трудно, откомментировать функцию добавления.
И еще, я думаю, было бы полезно добавить подобную статью(реализацию стека, можно и очереди, ну вобщем по спискам) в раздел "Стандартный С++"

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 26-02-2010 00:00:40

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

Давайте посмотрим...
Во-первых, в стеке необходимо реализовать стандартный интерфейс - функции push и pop. Первая у вас реализована под именем Add, но я вам советую привести к общепринятому наименованию. Вторую можно сделать на основе вашей функции Delete, добавив только возвращение значения удаляемого элемента.
Во-вторых, в силу своей природы стек не может быть отсортирован и его значения не могут быть выведены на печать без освобождения всего стека (получение значения элемента неизбежно влечет за собой изъятие элемента из стека). Функции DeleteAll() и переменная itsCount не являются необходимыми для реализации стека, но, возможно, вы захотите их использовать где-то в программе.
Таким образом, интерфейс стека у нас будет выглядеть следующим образом:

Code:

struct node
{
int value;/
node *next;
};

class cList
{
public:
 cList();
 ~cList();

 void push(int value); //Добавляет элемент в стек
 int pop(); //Возвращает верхний элемент, извлекая его из стека
 void DeleteAll(); //Извлекает все элементы

private:
 node *top; //Верхний элемент, последним помещенный в стек, первым будет извлекаться
 node *bot; //Самый нижний элемент, будет извлечен в последнюю очередь

 int itsCount; //Возможно, вы захотите реализовать функцию GetCount()
};

Теперь пойдем по реализации. Первым делом предостерегу вас от использования макроса NULL. Как и любой макрос, он таит в себе потенциальную опасность и может привести к очень тонким и трудно уловимым ошибкам. Поскольку макрос представляет собой вставляемый фрагмент кода, то 0, который скрывается за ним, не имеет типа, поэтому его использование небезопасно с точки зрения типов. Лучше либо явно указывайте в коде 0, либо используйте константу навроде

Code:

const void* Null = 0;

Теперь по поводу конструктора. Лучше всего вместо вашего варианта

Code:

cList::cList()
{
top=NULL;
bot=NULL;
itsCount=0;
}

использовать список инициализации:

Code:

cList::cList():
 top(0), bot(0),
 itsCount(0)
 {
 }

поскольку ваш вариант равнозначен следующему:

Code:

cList::cList():
 top(), bot(), //Инициализация по умолчанию
 itsCount()
{
top=NULL;
bot=NULL;
itsCount=0;
}

Во-первых, переменным лишний раз присваивается значение (что для больших объектов в качестве членов класса чревато излишними накладными расходами), во-вторых, у некоторых из членов может не быть конструктора по умолчанию и тогда код, подобный вашему, не сработает.

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 26-02-2010 01:01:56

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

Теперь по поводу функции push. Тут вы, кажется, немного напутали. Поэтому сначала кратко опишу, как будет работать стек. В стеке нас интересует главным образом только самых верхний элемент (т.е. top). Функцией push мы будем добавлять новый элемент, превращая его в top, а бывший top станет next для нового. Функция pop удаляет верхний элемент, делая top'ом его next. Стало быть,

Code:

void cList::push(int val) //Лучше не давать переменным, пусть даже из разных областей видимости, одинаковые имена - value в нашем случае
{
node* temp = new temp;
temp -> value = val;
temp -> next = top; //Мы в любом случае добавляем новый элемент 
top = temp; //Если стек был пуст, то temp -> next == 0, ничего особенного
if (bot == 0) //Если до выполнения функции не было даже нижнего элемента (стек был пуст)
 bot = top;
}

Функция pop будет такой:

Code:

int cList::pop()
{
if (bot == 0) 
 {/*Ошибка! Стек пуст!*/} 
else
 {
 int val = top -> value;
 if (top != bot) //Если осталось больше одного элемента
  {
  node* temp = top;
  top = top -> next;
  delete temp;
  }
 else
  {
  delete top;
  top = bot = 0;
  }
 return val;
 }
}

Для сохранения единообразия это можно записать и так:

Code:

int cList::pop()
{
if (bot == 0) 
 {/*Ошибка! Стек пуст!*/} 
else
 {
 int val = top -> value;
 node* temp = top;
 top = top -> next;
 delete temp;
 if (temp == bot)
  bot = 0;
 return val;
 }
}

Функция DeleteAll, стало быть, извлекает элементы по одному до тех пор, пока не станет равным нулю bot:

Code:

void cList::DeleteAll()
 {
 while (bot) //Эквивалентно while (bot != 0), т.е. до тех пор, пока есть хоть один элемент
  pop();
 }

Вот вроде бы и все, что я хотел бы сказать по этому поводу!

Статью по спискам, возможно, добавлю как руки дойдут!

Удачного программирования!

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 27-02-2010 14:11:14

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

Спасибо, помогли.

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 27-02-2010 15:58:10

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

Я решил реализовать сортировку этого списка(я с вами согласен, что в стеке не должно быть сортировки, но все же по заданию надо), сортировку надо сделать 2умя способами перестоновки элементов: обмен адресами(1) и обмен значеиями(2).
Я начал пробывать реализовать второй способ, вот, что из этого вышло:

Code:

void cList::SortByValue()
{
node* next=new node;
node* temp=new node;
node* current=bot;

while(current->next)
 {
 next=current->next;
 if(current->value < previous->value)
  {
  temp=current;
  current=next;
  next=temp;
  }
 current=temp->next;
 }
}

но этот вариант не работает, хотя, мне кажется, что тут все верно.
Не могли бы указать на ошибку?

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 27-02-2010 19:40:08

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

Во-первых, не забывайте про парность new-delete. Любые выделенные ресурсы в конце концов должны быть освобождены когда в них отпадет нужда.
Во-вторых, у вас тут много лишнего и странного... Нам достаточно создать один объект типа node (тот самый temp).
Кроме того, не забываем, что в нашем стеке все начинается с top, от него мы и идем вглубь, а вовсе не от bot (поскольку bot -> next == 0, то цикл while вообще в вашем варианте не будет выполняться).
Также для сортировки одного прохода будет мало, нам нужно будет совершать проходы по списку до тех пор, пока не получим удовлетворительный результат. Таким образом, если мы используем метод пузырьковой сортировки с условием остановки что весь список отсортирован должным образом, то код будет примерно следующий:

Code:

void cList::SortByValue()
{
node* temp=new node; //Нам понадобится только один объект типа node
node* current; //И два указателя на объекты такого типа
node* currnext; //Следующий за current элемент
bool Sorted = false; //Отсортирован ли список

while (!Sorted)
 {
 Sorted = true; //Если в дальнейшем не случится неправильных расположений - значит отсортирован
 current = top; //Снова и снова начинаем проход с начала
 while(current->next) //Пока не дойдем до конца
  {
  currnext = current -> next;
  if(current -> value > currnext -> value)
   {
   Sorted = false; //Обнаружено неправильное расположение - значит все еще не отсортирован

   temp -> value = current -> value;
   temp -> next = current -> next;

   current -> value = currnext -> value;
   current -> next = currnext -> next; //Заодно теперь current указывает на следующий
     //элемент списка, что обеспечивает продвижение по списку

   currnext -> value = temp -> value;
   currnext -> next = temp -> next;
   }
  else
   current = current -> next;  //В этом случае мы вручную продвигаемся к следующему элементу
  }
 }
delete temp; //Не забываем освобождать память
}

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

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 28-02-2010 02:08:54

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

Спасибо, только после строк

Code:

temp->value=current->value;
current->next=current->next;

вы пропустили строку

Code:

currNext->value=temp->value;

И не могли бы вы объяснить, почему вы написали блок if именно так, как вы написали? Ведь можно было и так:

Code:

   Sorted=false;
   temp->value=current->value;
   current->value=currNext->value;
   currNext->value=temp->value;

в чем "приемущество"(если можно так выразиться) вашего кода?

IP сохранен

Последний раз редактировалось: 28-02-2010 02:08:54 Автор rudolf т.к. Добавление в сообщение новой информации

Цитировать

Тема :Re:Односвязный список-реализация стека.. 28-02-2010 04:26:45

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

Цитата:

пропустили строку

Почему же? Эти шесть строк (не считаю строки с Sorted) представляют собой функцию swap:

Code:

   temp -> value = current -> value; //Эти две строки присваивают значению temp
   temp -> next = current -> next; //значение current

   current -> value = currnext -> value; //Эти две - значению current
   current -> next = currnext -> next; //значение currnext

   currnext -> value = temp -> value; //А эти две - значению currnext
   currnext -> next = temp -> next; //значение temp

По поводу if: здесь я осуществлял обмен значениями - значения всех полей одного объекта копируются в соответствующие поля другого объекта. Это можно было реализовать и по-другому, присваивая сразу весь объект другому. В данном случае генерируемый компилятором operator= для структуры node сделал бы все правильно. Тогда бы вместо приведенных выше шести строк было бы следующее:

Code:

(*temp) = (*current);
(*current) = (*currnext);
(*currnext) = (*temp);

Разыменовывание здесь необходимо, чтобы копировалось именно все содержимое объекта. Если убрать звездочки - получится простое присваивание указателей и это будет уже обмен адресами.

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 28-02-2010 04:58:19

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

По поводу обмена адресами в метод.пособии написано:
Обмен адресами - перестановка адресов 2ух соседних элементов, следующих за элементом с известным указателем. Первый элемент стека в этом случае не сортируеться. Для того, что бы и первый элемент сортировался следует добавить, перед обращением к методу, один любой элемент в стек, а после сортировки его удалить.
В вашем методе вроде и первый элемент стека будет сортироваться.
По поводу моего замечения, извиняюсь, не заметил сначала этой строки.

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 28-02-2010 12:20:28

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

А, ну тоже вариант. Просто я делал исходя из своих соображений. А таким методом, действительно, будет хотя бы переход к следующему элементу прозрачнее. Тогда, скажем, первый элемент обзовем current, следующий за ним first, следующий за ним - second (чтоб не путаться), и каждый раз работать с ними: сравниваем их значения, по необходимости меняем. current используем только в начале каждой итерации цикла, заменяя его на current -> next.
Только нужно будет использовать operator* (оператор рызыменовывания) при обмене, чтобы это был именно обмен значениями. Если не использовать, то будет обмен адресами.
И еще, в качестве условия завершения внутреннего while будет уже не current -> next, а first -> next. Ну и вначале надо проверить, что first -> next не равен нулю (изначально есть хотя бы два элемента).

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

Выбирайте, который вам больше нравится!

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 03-03-2010 03:26:38

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

сделал так, как написано сверху(ну мне показалось, что так). Но в момент сортировки по адресу просто ничего не происходит
вот код:

Code:

void cList::SortByAdress()
{
node* temp=new node;
node* current,*first,*second;
bool isSorted=false;

while(!isSorted)
 {
 isSorted=true;
 current=top;
 first=current->next;

 while(first->next)
  {
  second=first->next;

  if(first->value > second->value)
   {
   isSorted=false;

   temp=first;
   current=first;
   first=second;
   second=temp;
   }
  else
   {
   first=first->next;
   }
  }
 }
delete temp;
}

где ошибка?"

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 03-03-2010 05:20:10

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

Первым делом вновь укажу вам на излишнее выделение памяти для temp.
а. К чему это приводит?

Code:

node* temp = new node;
//Здесь нигде temp не упоминается
temp = first;

Мы выделили память для объекта типа node и чтобы не потерять к нему доступ, сохранили адрес области памяти в указатель temp. Затем мы, не сохранив нигде этот адрес, затираем его другим адресом. И в результате мы уже никогда не сможем обратиться к этому объекту, он будет только где-то пылиться и занимать место. Это безотносительно к смыслу алгоритма. Просто запомните, что адрес созданного с помощью new объекта должен где-то храниться до тех пор, пока объект по этому адресу не будет уничтожен с помощью delete (в скобках напомню, что у вас опять непарный new. Здесь он не нужен вообще, но привыкайте к тому, что раз есть new, то должен где-то быть и delete. Утечки памяти могут иметь иногда очень неприятные последствия).

б. Каков сакральный смысл?
Когда мы создаем объект с помощью оператора new, это значит, что нам нужен именно сам объект - со всеми его полями и всей выделенной ему памятью. То есть мы будем оперировать с его содержимым - записывать что-то в его поля, что-то из них считывать, что-то с чем-то сравнивать...
Если же нам нужно только жонглировать с адресами, и единственное назначение указателя - принимать значения адресов каких-то уже созданных объектов (с последующим обращением к этим объектам через указатель), то мы просто объявляем указатель и не создаем по этому указателю никакого нового объекта (с помощью оператора new).

Чтобы как-то понагляднее представить вышесказанное в применении к текущей задаче, обрисую сортировку массива (отличие от списка не радикальное) с помощью обмена значениями и обмена указателями на таком примере.

Пусть в некую гостиницу приехали известные физики: Альфер, Бете, Гамов и так далее (вообще-то они приехали на конференцию, но жить им тоже где-то надо, поэтому они одновременно приехали и в гостиницу. Дуализм такой...) Неопытный клерк принимая такое количество столь почетных гостей, растерялся и потому расселил их как попало, каждого в первый попавшийся номер [инициализировал неупорядоченный еще массив]. Через полчаса пришел управляющий, узнал что случилось и начал рвать волосы на голове (у себя и у менеджера) и метать их себе под ноги. Ведь почетные гости должны были расположиться в строгом порядке! Альфер должен был жить в первом номере, Бете - во втором, Гамов - в третьем и так далее [номер номера (упс, тавтология!) - это номер элемента массива, возрастание определяется очередностью фамилий: Альфер-Бете-Гамов-и т.д.] Закончив рвать и метать, управляющий велел менеджеру немедленно расселить гостей как подобает [отсортировать массив]. И тот тотчас же принялся за дело.
Как он мог это сделать? Рассмотрим вариант номер один: обмен значениями.
Первым делом одна из многочисленных кладовок была временно переоборудована в номер [был объявлен новый элемент типа комната - статически простым объявлением или динамически с объявлением указателя на комнату и выделением памяти оператором new], и была пронумерована как temp. После этого менеджер пошел по номерам смотреть, кто же там живет. Зайдя в первый и во второй, он увидел, что в первом номере живет кто-то, кто вообще-то идет по списку позже того, что живет во втором [значение первого элемента больше второго], поэтому менеджер не говоря дурного слова взял под белы рученьки бедного обживающегося в своем номере великого физика, а также весь его багаж, меблировку номера и даже лампочку выкрутил и взял с собой. Потом он перенес все это в бывшую кладовку и расставил все так, как было в первом номере [присвоил временной переменной значение первого элемента массива], после чего пошел во второй номер, подобным же образом перенес еще одного великого физика и все содержимое номера в номер первый [присвоил первому элементу значение второго]. И наконец, перенес несчастного из кладовки-номера и всё-всё-всё в номер под номером два [угадайте что!

]. Оставив недоумевающих великих физиков в великом недоумении, менеджер спокойно прошел в третий номер, и посмотрел, кто же там живет. К счастью, в этот раз новый житель второго номера шел по списку раньше жителя номер три [второй элемент массива меньше третьего], поэтому на сей раз обошлось без перестановок. Но это было только начало... Таким же образом менеджер прошелся по всем номерам, время от времени меняя ближайших соседей местами. Но этого оказалось недостаточно. Все равно физики жили не в должном порядке [массив еще не был отсортирован]. Поэтому все началось по новой... Великие физики - народ терпеливый, поэтому менеджеру удалось совершать свои не слишком гуманные деяния до тех пор, пока он не разместил всех знаменитых постояльцев должным образом. Управляющий был доволен (на самом деле только потому, что воспитанные великие физики не пожаловались на менеджера). Поэтому он приказал временный номер отдать обратно под кладовку [автоматически уничтожить переменную при выходе ее из области видимости или явно удалить ее с помощью оператора delete, если она была создана при помощи new] и жить дальше.
Это была сортировка обменом значениями. А как же обмен адресами? А вот как!
Менеджер был ленив. Он не хотел носить туда-сюда и великих физиков, и их багаж, и всю мебель, и даже лампочку! Он решил сделать хитрее. Поэтому он взял номерок, такой же, что красовались на дверях гостиничных номеров [объявил временную переменную типа указатель на комнату] и пошел с ней к первому номеру. Заглянув туда, он прошел во второй номер и, увидев, что физик, проживающий под табличкой "1" идет по списку после физика под табличкой "2", переписал для памяти на свой временный номерок номер первой из комнат [присвоил временному указателю значение первого указателя], после чего на номерке первой из комнат написал то же, что было на номерке второй [присвоил первому указателю значение второго указателя], и наконец на номерке второй двери написал то, что было на первой. Теперь физик, проживавший когда-то в первом номере, оказался формально жителем второго, а физик из второго оказался по документам во втором! При этом ни один из них не оторвался от своих дел, и багаж их остался в неприкосновенности! Обрадованный плодами своей хитрости менеджер пошел смотреть, кто же живет в третьем номере... И вот так вот он бегал по всей гостинице, непрестанно меняя таблички на дверях номеров и несчастные великие физики, оказывается, совершили столько переездов из одной комнаты в другую, хотя сами этого не заметили! Правда, в дверь постоянно заглядывал какой-то сумасшедший с чем-то странным в руках, но, право слово, если бы это сумасшедший весь день таскал их самих туда-сюда, это было бы гораздо утомительней! Да и менеджеру было меньше работы. Конечно, в результате в гостинице наступила некоторая сумятица со взаимным расположением номеров, но зато формально все великие физики теперь жили каждый в своем номере!
Вот так и сортировал физиков наш менеджер, то меняя их значениями, то адресами!

З.Ы. Извините за много букв, но не мог не развить тему вглубь и вширь!

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 03-03-2010 13:53:22

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

Теперь, собственно, по алгоритму.
Первое - это вы забыли добавить еще один дополнительный элемент, необходимый для того, чтоб первый элемент тоже был отсортирован.
Второе - это вы зачем-то все подряд местами меняете. Давайте я еще раз объясню алгоритм. Начинается все с элемента current, который мы используем только для перехода далее по списку, он следит только затем, чтобы мы всегда находились в нужном месте списка. Во всех прочих операциях по ходу сортировки он не участвует.
Для сортировки же у нас служат два элемента - first и second. Они представляют собой два элемента, следующие за current: first == current -> next, second == first -> next. И такое положение вещей сохраняется на протяжении всей операции сортировки (только время от времени first и second меняются местами), стало быть, в каждой из итераций внутреннего цикла current, first и second обновляются. Причем current каждый раз становится своим next, а из этого нового current каждый же раз получаются first и second. И еще - поскольку теперь у нас за продвижением по списку следит current, которого никак не затрагивает возможный обмен first и second местами, то связка if-else нам больше не нужна, мы в любом случае будем единообразно перемещаться по списку.
В итоге код должен быть где-то такой:

Code:

void cList::SortByAdress()
{
push(0); //Помещаем вперед временный элемент
node *current, *first, *second;
node *temp;
bool isSorted = false;

while(!isSorted)
 {
 isSorted = true;
 current = top;
 first = current -> next; //Для единообразия соберем current, first и second вместе
 second = first -> next;

 while(first->next)
  {
  if(first->value > second->value)
   {
   isSorted=false;

   temp=first;
   first=second;
   second=temp;
   }
  current = current -> next; //Опять же собираем вместе для лучшей читаемости
  first = current -> next; //next от нового current
  second = first -> next; //Если second == 0, то следующая итерация не выполнится
  }
 pop(); //Извлекаем временный элемент
 }

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 03-03-2010 15:26:03

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

Большое спасибо.
Почему-то когда все разжевано, то все кажеться простым, но, когда сам пробывал сделать, то что-то не получилось...
А посветуйте пожалуйста какх-нибудь учебников по Си++. Просмотрев название статей, которые находятся тут, в разделе "Учебник С++", я тут, как мне показалось, ничего новго для себя не нашел, весь этот материал я знаю(ну, по крайней мере я так считаю).

IP сохранен

Последний раз редактировалось: 03-03-2010 15:26:03 Автор rudolf т.к.

Цитировать

Тема :Re:Односвязный список-реализация стека.. 03-03-2010 18:43:23

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

Учебник пока находится в стадии написания, и пока там и в самом деле излагаются еще только самые основы.
Из книжек по C++ советую почитать Бьёрна Страуструпа "Язык программирования C++". Книгу именуют "Библией C++", что неудивительно - кому как не автору языка знать все его тонкости и аспекты использования.

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 04-03-2010 18:45:16

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

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

Code:

void cList::SortByAdress()
{
push(0);
node *current, *first, *second;
node *temp;
bool isSorted = false;

while(!isSorted)
 {
 isSorted = true;
 current = top;
 first = current -> next;
 second = first -> next;

 while(second->next)
  {
  if(first->value > second->value)
   {
   isSorted=false;

   current->next=second;
   first->next=second->next;
   second->next=first;
   second=first;
   }
  current = first;
  first = current->next;
  second = first -> next;
  }
 }
pop();
}

но такой вариант сортирует только первые встречные элементы и все, т.е. если у меня список 5 1 8 3, то местами поменяются только 5 и 1, а номера 8 и 3 остануться нетронутыми, и в итоге получиться 1 5 8 3.

Может есть какие идеи в чем проблема?

IP сохранен

Последний раз редактировалось: 04-03-2010 18:45:16 Автор rudolf т.к.

Цитировать

Тема :Re:Односвязный список-реализация стека.. 10-03-2010 23:46:55

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

Да, это я вам совсем неправильно сказал по поводу обмена адресами. На самом деле нам надо просто заставить current ссылаться как на следующий элемент на second, second - на first, first - на элемент, следовавший ранее за second.
Если условно рисовать фрагмент списка до и после такой замены, то структура его будет выглядеть так (простите за мой ASCII-шный):

До:

Code:

O->O->O->O

После:

Code:

   |-----v
O  O<-O  O
|-----^

Соответственно, код будет такой (привожу целиком код моего проекта с функцией SortByAddress):

Code:

#include <iostream>
#include <stdlib.h>
#include <conio.h>

struct node
{
int value;
node *next;
};

class cList
{
public:
 cList();
 ~cList();

 void push(int value); //Äîáàâëÿåò ýëåìåíò â ñòåê
 int pop(); //Âîçâðàùàåò âåðõíèé ýëåìåíò, èçâëåêàÿ åãî èç ñòåêà
 void DeleteAll(); //Èçâëåêàåò âñå ýëåìåíòû
 void SortByAddress();

private:
 node *top; //Âåðõíèé ýëåìåíò, ïîñëåäíèì ïîìåùåííûé â ñòåê, ïåðâûì áóäåò èçâëåêàòüñÿ
 node *bot; //Ñàìûé íèæíèé ýëåìåíò, áóäåò èçâëå÷åí â ïîñëåäíþþ î÷åðåäü

 int itsCount; //Âîçìîæíî, âû çàõîòèòå ðåàëèçîâàòü ôóíêöèþ GetCount()
};

cList::cList():
 top(0), bot(0),
 itsCount(0)
 {
 }

cList::~cList()
 {
 DeleteAll();
 }

void cList::push(int val) //Ëó÷øå íå äàâàòü ïåðåìåííûì, ïóñòü äàæå èç ðàçíûõ îáëàñòåé âèäèìîñòè, îäèíàêîâûå èìåíà - value â íàøåì ñëó÷àå
{
node* temp = new node;
temp -> value = val;
temp -> next = top; //Ìû â ëþáîì ñëó÷àå äîáàâëÿåì íîâûé ýëåìåíò
top = temp; //Åñëè ñòåê áûë ïóñò, òî temp -> next == 0, íè÷åãî îñîáåííîãî
if (bot == 0) //Åñëè äî âûïîëíåíèÿ ôóíêöèè íå áûëî äàæå íèæíåãî ýëåìåíòà (ñòåê áûë ïóñò)
 bot = top;
}

int cList::pop()
{
if (bot == 0)
 {/*Îøèáêà! Ñòåê ïóñò!*/ return -1;}
else
 {
 int val = top -> value;
 if (top != bot) //Åñëè îñòàëîñü áîëüøå îäíîãî ýëåìåíòà
  {
  node* temp = top;
  top = top -> next;
  delete temp;
  }
 else
  {
  delete top;
  top = bot = 0;
  }
 return val;
 }
}

void cList::DeleteAll()
 {
 while (bot) //Ýêâèâàëåíòíî while (bot != 0), ò.å. äî òåõ ïîð, ïîêà åñòü õîòü îäèí ýëåìåíò
  pop();
 }

void cList::SortByAddress()
{
push(0); //Ïîìåùàåì âïåðåä âðåìåííûé ýëåìåíò
node *current, *first, *second;
node *temp = new node;
bool isSorted = false;

while(!isSorted)
 {
 isSorted = true;
 current = top;
 first = current -> next; //Äëÿ åäèíîîáðàçèÿ ñîáåðåì current, first è second âìåñòå
 second = first -> next;

 while(second->next)
  {
  if(first->value > second->value)
   {
   isSorted=false;

   first -> next = second -> next;
   second -> next = first;
   current -> next = second;
   }
  current = current -> next; //Îïÿòü æå ñîáèðàåì âìåñòå äëÿ ëó÷øåé ÷èòàåìîñòè
  first = current -> next; //next îò íîâîãî current
  second = first -> next; //Åñëè second == 0, òî ñëåäóþùàÿ èòåðàöèÿ íå âûïîëíèòñÿ
  }
 }
pop(); //Èçâëåêàåì âðåìåííûé ýëåìåíò
}


int main()
{
cList List;
for (int i = 0; i < 10; i++)
   List.push(i);
List.SortByAddress();
for (int i = 0; i < 10; i++)
   std::cout << List.pop() << std::endl;
getch();
}

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 11-03-2010 01:52:27

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

Спасибо.

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 13-03-2010 03:42:59

rudolf

char

Онлайн с: 24-02-2010 11:03:24
Сообщения: 31
Среда обитания:

Задание: удалить элмент значение которого меньше среднего значения всех элементов.
Я пробывал решать таким образом:

Code:

void cList::Task()
{
double AvValue;
node *current=top;
int sum=0;

if(bot==0)
 {
 cout<<ToRus("Стек пуст.\n");
 return;
 }

for(int i=0;i<itsCount;i++)
 {
 sum+=current->value;

 current=current->next;
 }

AvValue=double(sum)/itsCount;

bool isDone=false;
node *temp;

while(!isDone)
 {
 isDone=true;
 current=top;

 while(current->next)
  {
  if(current->value < AvValue)
   {
   isDone=false;

   temp=current;
   current=current->next;
   delete temp;
   }
  else
   {
   current=current->next;
   }
  }
 }
}

не подскажите, в чем ошибка?

IP сохранен

Цитировать

Тема :Re:Односвязный список-реализация стека.. 13-03-2010 23:25:08

Captain

int main()

Онлайн с: 28-03-2009 11:37:34
Сообщения: 39
Среда обитания:

temp и current - это всего лишь указатели. Сами по себе они не несут в себе никакой информации. Мы можем делать с ними что угодно, присваивать им какие угодно значения, но до тех пор, пока мы не производим их разыменовывание с последующим изменением того, что мы получили в результате разыменовывания (собственно объект, на который они ссылаются); либо пока мы не присвоили их значения каким-либо другим объектам (над которыми потом тоже должно производиться разыменовывание) - ничего существенного с реальными данными не происходит.
Кроме того, удаление элемента из списка - это не просто применение оператора delete к объекту. Чтобы не нарушить целостность всего списка, мы должны прежде всего заставить элемент, предшествующий удаляемому, сослаться на объект, следующий за удаляемым как на теперь уже свой собственный next.
Т.е. удалить элемент, следующий за current можно так:

Code:

temp = current -> next;
current -> next = temp -> next;
delete temp;

IP сохранен

Цитировать

Ответить	« ПерваяПредыдущая12Следующая Последняя »
	Страница #

Главное меню

Авторизация

Счетчики

Обмен ссылками