Связанные списки в C++

[Rembo]

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

Когда элемент вставляется в конец списка, то за ним следующего элемента нет, поэтому pNext надо занулить.



Разумеется, ведь вы каждый новый элемент вставляете в начало списка. Т.е. по мере заполнения у вас список изменяется так (если заполнять числами [1;5] в прямом порядке):

_____  _  _  _  _  _  1
_____  _  _  _  _  1  2
_____  _  _  _  1  2  3
_____  _  _  1  2  3  4
pHead->  1  2  3  4  5

И вывод начинается с pHead.

А это пример, когда мы добавляем элементы в конец? получается, что если ввести 1, потом 2, то 1 уйдет как бы назад, а 2 встанет в конец, и если чтение происходит и pHead, то и числа выводятся в том порядке, в котором мы вводили? Или я что-то не догоняю? Тогда график добавления элемента в начал списка будет так выглядеть?

_____  _  1  _  _  _  
_____  _  2  1 _  _  
_____  _  3  2  1 _  
_____  _  4  3  2  1 
pHead->  5  4  3  2  1

Это правильный график добавления в начало списка? и если снова начать выводить с pHead, то числа будут выводится в обратном порядке: 5 4 3 2 1. Если я все правильно понял, то есть еще один вопрос: А можно ли сделать так, что вывод начинался не с pHead, а с конца, тоесть с pLast наверно... Подскажите пожалуйста.

[filosof_x86]

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

А это пример, когда мы добавляем элементы в конец?

Нет, это был график добавления в начало. Для добавления в конец будет так:

pHead-> 1 1 1 1 1
_______ _ 2 2 2 2
_______ _ _ 3 3 3
_______ _ _ _ 4 4
_______ _ _ _ _ 5

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

получается, что если ввести 1, потом 2, то 1 уйдет как бы назад...

Нет, если мы добавляем элемента в конец, то pHead не изменяется, он будет также указывать на первый элемент в списке, а новый элемент пойдет в самый конец.

[Rembo]

filosof_x86, а все, разобрался с графиками, спасибо! Если не сложно ответьте пожалуйста еще на один вопрос из предыдущего поста:

А можно ли сделать так, что вывод начинался не с pHead, а с конца, тоесть с pLast наверно...

Ну что бы все таки при выводе чисел, добавленных в начало списка, они следовали в той же последовательности, что и при вводе...

[MaTBeu]

То filosof_x86
Благодарю за разъяснение.
То Rembo
В обратном порядке можно выводить. Для этого существуют двусвязные списки. В таком списке у каждого элемента есть указатель на следующий элемент и указатель на предыдущий элемент. Тоесть у первого элемента указатель на предыдущий элемент равен 0, а у последнего указатель на следующий элемент равен 0.

ПыСы: существуют также кольцевые списки. Тоесть это такой список у которого последний элемент хранит в качестве указателя на следующий первый элемент. В таком списке необходимо указывать и первый элемент и последний, чтобы не попасть в вечный цикл, при поиске определенного элемента. Есть и двусвязный кольцевой список. У него первый элемент в качестве указателя на предыдущий элемент хранит последний элемент. А последний элемент в качестве указателя на следующий элемент хранит первый элемент. Тоесть вот так.
Двусвязный список

class TwoLinksList
{
     public:
            int value;
            TwoLinksList *nextPtr;
            TwoLinksList *prevPtr;
};

Кольцевой двусвязный

pHead->prevPtr=LastPtr;
LastPtr->nextPtr=pHead;

Тоесть для реверсивного вывода нужно начинать с LastPtr и "идти" по предыдущим элементам, пока не дойдем до pHead.

[Rembo]

Вот, снова начал разбираться со списками, возник маленький вопрос: есть код, написанный мною:

#include <cstdio>  
#include <cstdlib>  
#include <iostream>  
using namespace std;  
  
class NameDataSet  
 { 
   public: 
    int chislo; 
    NameDataSet* pNext;    
 };  
                                
NameDataSet* pHead = 0;          
NameDataSet* pNew;               
NameDataSet* pLast = 0;                
  
void zapolnenie(NameDataSet *pNew)  
{ 
  cout << "Введите число: "; 
  cin >> pNew->chislo;   
  return; 
   }  
   void displayData(NameDataSet* pNew)  
   {  
    cout << pNew->chislo <<endl; 
   }    
  
 int main(int nNumberofArgs, char* pszArgs[])  
 { 
 for (int i = 0; i<5; i++) 
      { 
 pNew = new NameDataSet; 
 pNew->pNext = pHead; 
 pHead = pNew; 
  zapolnenie(pNew);  
       }    
  pNew = pHead; 
 while(pNew)  
 { 
    displayData(pNew);  
       pNew = pNew->pNext;     
            }  
 system("PAUSE");  
 return 0;   
 }

У меня возник вопрос со строчкой номер 37. Объясните пожалуйста, нужна ли она вообще? Раньше я думал, что эта строчка как бы сохранение связанного списка, а щас скомпилировал без этой строчки, тоже работает... Подскажите пожалуйста, нужно ли писать эту строку? (pNew = pHead; )

[Rembo]

Помогите пожалуйста! Правда ли, что эта строчка (предыдущий пост) как бы сохранение списка? Тоесть, чтобы новый объект указывал на начало списка? Или ее вообще можно не писать?

[filosof_x86]

Да, эту строчку можно опустить в данному случае, т.к. на последней итерации цикла выполняется pHead = pNew, а в zapolnenie() эти переменные не изменяются. Поэтому строчку после цикла pNew = pHead можно опустить, т.к. pNew==pHead и без нее.

[Rembo]

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

[filosof_x86]

На предыдущий пост отвечаю Rembo в icq.

[Rembo]

Все, вроде разобрался! Уж решил не соваться глубже, главное, что понял как добавлять и заполнять элементы в линейном связанном списке. Что-то мне это тема трудно далась. Спасибо большое всем, кто проявил внимание к моим вопросам!