Проход по элементам односвязного линейного списка

@Uz · Регистрация: 05.07.2012

Допустим у меня существует класс линейного односвязного списка. Надо пройти по его элементам и присвоить каждому соответствующее хэш-значение. Но какой цикл для прохода по элементам списка мне для этого надо использовать? Я пробовал что-то вроде этого:

C++

1	while (z<elm.razmer && temp != NULL)

где razmer - размер списка (но он прайветовский так что не получается), а temp - элемент структуры, в которую по идее должны записываться элементы списка. Но так не работает! Как мне сделать, чтобы вызывались именно элементы списка, потом осуществлялся по ним проход, и чтобы можно было ещё этим самым элементам в цикле ставить в соответствие какие-нибудь значения, записывая потом эти значения в какой-нибудь массив.
Помогите пожалуйста! Очень нужно!
P.S.: если понадобиться - могу выложить описание своего списка.

alsav22 · 11.07.2012, 01:42

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

P.S.: если понадобиться - могу выложить описание своего списка.

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

C++

#include <iostream>
 
struct node  // элемент спсиска.
{
    int x;
    node *next; // указатель на следующий эл. списка.
};
 
int main()
{
node *begin; // указатель на начало списка. В нём должен быть адресс начала списка.
node *ptr = begin; 
while ( ptr != NULL)
{
    ptr -> x = 5; // присвоение значения переменной элемента списка. 
    ptr = ptr -> next; // в ptr адресс следующего элемента списка.
}
}

@Uz · 11.07.2012, 09:49 **[ТС]**

Спасибо! Только у меня возник ещё один вопрос: а если у меня есть два объекта класса список, например Spisok odin и Spisok dva, как мне обращаться к их элементам и устраивать по ним проход?
Вот описание моего класса:

C++

struct Element //Структура с инфополями и адресным полем
{
 int x; //Инфополе. Значения из x будут передаваться в список
 Element *Next; //Адресное поле
};
class Spisok
{
    Element *Head; 
    Element *Tail;
    int razmer;
public:
    Spisok():Head(NULL),razmer(0) {}; //Инициализация значений с помощью конструктора
    ~Spisok();
    void Add(int x); 
    void Show();   
};
Spisok::~Spisok() //Деструктор 
{
    while (Head!=NULL)  //Пока по адресу не пусто 
     {    
        Element *temp=Head->Next; //Временная переменная для хранения адреса следующего элемента
        delete Head; //Освобождаем адрес, обозначающий начало
        Head=temp; //Меняем адрес на следующий
     }
}
void Spisok::Add(int x) //Функция добавления элементов в список
{ 
Element *temp=new Element; //При каждом вызове выделяется память
 if(Head == NULL)
        Head = temp;
  else
        Tail->Next = temp;
    temp->x=x;
    temp->Next = NULL;
    Tail=temp;
    ++razmer;
}

alsav22 · 11.07.2012, 13:00

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

Только у меня возник ещё один вопрос: а если у меня есть два объекта класса список, например Spisok odin и Spisok dva, как мне обращаться к их элементам и устраивать по ним проход?

У вас список немного другого вида, чем я описал, есть ещё указатель на конец списка (Element *Tail), но в принципе, это ничего не меняет. Если есть два списка, Spisok odin и Spisok dva, то доступ к переменным объекта класса, как обчно:

C++

1
2

Element *ptr1 = odin.Head; // ptr1 указывает на начало первого списка.
Element *ptr2 = dva.Head;  // ptr2 указывает на начало второго списка.

Только перед этим, вам необходими переместить переменные-члены класса Spisok в public раздел, иначе у вас к ним доступа из main() не будет, или нужно создать метод, который будет выдавть указатель на начало списка.

C++

class Spisok
{
    public:
    Element *Head; 
    Element *Tail;
    int razmer;
 
    Spisok():Head(NULL),razmer(0) {}; //Инициализация значений с помощью конструктора
    ~Spisok();
    void Add(int x); 
    void Show();   
};

А дальше, как я описывал:

C++

#include <iostream>
using namespace std;
 
int main()
{
  Spisok odin;
  Spisok dva;
  Element *ptr1 = odin.Head; // ptr1 указывает на начало первого списка.
  Element *ptr2 = dva.Head;  // ptr2 указывает на начало второго списка.
 
while ( ptr1 != NULL) // обход первого списка.
{
    ptr1 -> x = 5; // присвоение значения переменной элемента списка. 
    ptr1 = ptr1 -> Next; // в ptr1 адресс следующего элемента списка.
}
 while ( ptr2 != NULL) // обход второго списка.
{
    ptr2 -> x = 10; 
    ptr2 = ptr2 -> Next; 
} 
    system("pause");
    return 0 ;
}

Добавлено через 17 минут
Если же проблема в том, чтобы оставить переменные-члены класса Spisok в приватном разделе, то тогда так:

C++

class Spisok
{
    Element *Head; 
    Element *Tail;
    int razmer;
    
    public:
    Spisok():Head(NULL),razmer(0) {}; //Инициализация значений с помощью конструктора
    ~Spisok();
    void Add(int x); 
    void Show();
    Element* getHead(); // метод для получения указателя на начало списка.  
};
 
Element* Spisok::getHead()
{
    return Head; // возвращает указатель на начало списка.
}
.....................................

и так:

C++

#include <iostream>
using namespace std;
 
int main()
{
  Spisok odin;
  Spisok dva;
  Element *ptr1 = odin.getHead(); // ptr1 указывает на начало первого списка.
  Element *ptr2 = dva.getHead();  // ptr2 указывает на начало второго списка.
 
while ( ptr1 != NULL) // обход первого списка.
{
    ptr1 -> x = 5; // присвоение значения переменной элемента списка. 
    ptr1 = ptr1 -> Next; // в ptr1 адресс следующего элемента списка.
}
 while ( ptr2 != NULL) // обход второго списка.
{
    ptr2 -> x = 10; 
    ptr2 = ptr2 -> Next; 
} 
    system("pause");
    return 0 ;
}

По идее, такие же методы (как getHead()), нужно добавить и для извлечения razmer и Tail.

@Uz · 11.07.2012, 15:57 **[ТС]**

Спасибо огромное! Очень выручили! Сейчас буду разбираться.

Добавлено через 2 часа 45 минут
А для двусвязного списка также реализуется?

alsav22 · 11.07.2012, 16:15

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

А для двусвязного списка также реализуется?

Да. Вот код попался в инете:

код

"Вобщем нужно реализовать основные функции для работы с двусвязанным списком (вставка элемента,удаление,печать,сортировка ).
вот что уже набросал:"

C++

#include <iostream>
#include <conio.h>
using namespace std;
 
 struct Node
 {
 int d;
 Node *next;
 Node *prev;
 };
 Node * first(int d);
 void add(Node **pend, int d);
 Node * find(Node * const pbeg, int i);
 bool remove(Node **pbeg, Node **pend, int key);
 Node *insert(Node *const pbeg, Node **pend, int key, int d);
 void PrintList(Node *pbeg);
 void main()
 {}
 Node *first(int d)// Формирование первого элемента
 {
 Node *pv = new Node;
 pv->d = d; pv->next = 0; pv->prev = 0;
 return pv;
 }
 
 void add(Node **pend, int d)// Добавление в конец списка
 {
 Node *pv = new Node;
 pv->d = d; pv->next = 0; pv->prev = *pend;
 (*pend)->next = pv;
 *pend = pv;
 }
 Node *find(Node *const pbeg, int d)// Поиск элемента по ключу
 {
 Node *pv = pbeg;
 while (pv)
 {
 if(pv->d == d)break;
 pv = pv->next;
 }
 return pv;
 }
 bool remove(Node **pbeg, Node **pend, int key)// Удаление элемента
 {
 if(Node *pkey = find(*pbeg, key))
 { 
 if (pkey == *pbeg)// проверяется,находится ли удаляемый элемент в начале списка
 { 
 *pbeg = (*pbeg)->next;// если да,то надо скорректировать указатель pbeg на начало списка так, чтобы он указывал на следующий элемент в списке, адрес которого находится в поле next первого элемента
 (*pbeg)->prev =0;// обнуляется указатель на предыдущий элемент
 }
 else if (pkey == *pend)// если удаляемый элемент находится в конце списка, требуется сместить указатель pend конца списка на предыдущий элемент, адрес которого можно получить из поля prev последнего элемента
 { 
 *pend = (*pend)->prev;
 (*pend)->next=0;// обнуляется указатель на следующий элемент
 }
 else // Если удаление происходит из середины списка, то нужно лишь обеспечить двустороннюю связь предыдущего и последующего элементов
 {
 (pkey->prev)->next = pkey->next;
 (pkey->next)->prev = pkey->prev;
 }
 delete pkey;
 return true;
 }
 return false;
 }
 
 Node *insert (Node *const pbeg, Node **pend, int key, int d)// Вставка элемента
 {
 if(Node *pkey = find(pbeg, key))
 {
 Node *pv = new Node;
 pv->d = d;
 pv->next = pkey->next;// установление связи нового узла с последующим
 pv->prev = pkey;// установление связи нового узла с предыдущим
 pkey->next = pv;// установление связи предыдущего узла с новым
 if(pkey != *pend)(pv->next)->prev = pv;// установление связи последующего узла с новым
 // Обновление указателя на конец списка,
 // если узел вставляется в конец
 else *pend = pv;
 return pv;
 }
 return 0;
 }
 void PrintList(Node *pbeg)// Печать списка
 {
// pv пробегает по списку, начиная с головы
 Node *pv = pbeg;
 while(pv != NULL)// пока не конец списка, печатать значение данных текущего узла 
 {
 cout << pv->d << endl;
 pv = pv->next; // перейти к следующему узлу 
 }
 }

@Uz 0 / 0 / 1 Регистрация: 05.07.2012 Сообщений: 23
	11.07.2012, 15:57 [ТС]	5
	Спасибо огромное! Очень выручили! Сейчас буду разбираться. Добавлено через 2 часа 45 минут А для двусвязного списка также реализуется? 0

Опции темы