Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.60
Uz
0 / 0 / 0
Регистрация: 05.07.2012
Сообщений: 22
11.07.2012, 00:06     Проход по элементам односвязного линейного списка #1
Допустим у меня существует класс линейного односвязного списка. Надо пройти по его элементам и присвоить каждому соответствующее хэш-значение. Но какой цикл для прохода по элементам списка мне для этого надо использовать? Я пробовал что-то вроде этого:
C++
1
while (z<elm.razmer && temp != NULL)
где razmer - размер списка (но он прайветовский так что не получается), а temp - элемент структуры, в которую по идее должны записываться элементы списка. Но так не работает! Как мне сделать, чтобы вызывались именно элементы списка, потом осуществлялся по ним проход, и чтобы можно было ещё этим самым элементам в цикле ставить в соответствие какие-нибудь значения, записывая потом эти значения в какой-нибудь массив.
Помогите пожалуйста! Очень нужно!
P.S.: если понадобиться - могу выложить описание своего списка.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2012, 00:06     Проход по элементам односвязного линейного списка
Посмотрите здесь:

Найти наименьший элемент односвязного линейного списка C++
Ввод вложенного односвязного линейного списка C++
Обращение к элементам линейного списка через элементы массива указателей C++
C++ Удалить из односвязного линейного списка определенный узел
Спроектировать шаблон класса spisok для реализации односвязного линейного списка. Не работает сортировка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
11.07.2012, 01:42     Проход по элементам односвязного линейного списка #2
Цитата Сообщение от Uz Посмотреть сообщение
P.S.: если понадобиться - могу выложить описание своего списка.
Лучше, конечно, выложить. В общих чертах, проход делается так. В каждом списке хранится указатель на начало списка. В каждом элементе линейного односвязного списка хранится указатель на следующий элемент списка. В последнем элементе списка это указатель на NULL. Например,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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
0 / 0 / 0
Регистрация: 05.07.2012
Сообщений: 22
11.07.2012, 09:49  [ТС]     Проход по элементам односвязного линейного списка #3
Спасибо! Только у меня возник ещё один вопрос: а если у меня есть два объекта класса список, например Spisok odin и Spisok dva, как мне обращаться к их элементам и устраивать по ним проход?
Вот описание моего класса:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
11.07.2012, 13:00     Проход по элементам односвязного линейного списка #4
Цитата Сообщение от 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++
1
2
3
4
5
6
7
8
9
10
11
12
class Spisok
{
    public:
    Element *Head; 
    Element *Tail;
    int razmer;
 
    Spisok():Head(NULL),razmer(0) {}; //Инициализация значений с помощью конструктора
    ~Spisok();
    void Add(int x); 
    void Show();   
};
А дальше, как я описывал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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
0 / 0 / 0
Регистрация: 05.07.2012
Сообщений: 22
11.07.2012, 15:57  [ТС]     Проход по элементам односвязного линейного списка #5
Спасибо огромное! Очень выручили! Сейчас буду разбираться.

Добавлено через 2 часа 45 минут
А для двусвязного списка также реализуется?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
11.07.2012, 16:15     Проход по элементам односвязного линейного списка #6
Цитата Сообщение от Uz Посмотреть сообщение
А для двусвязного списка также реализуется?
Да. Вот код попался в инете:
код
"Вобщем нужно реализовать основные функции для работы с двусвязанным списком (вставка элемента,удаление,печать,сортировка ).
вот что уже набросал:"
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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; // перейти к следующему узлу 
 }
 }
Yandex
Объявления
11.07.2012, 16:15     Проход по элементам односвязного линейного списка
Ответ Создать тему
Опции темы

Текущее время: 00:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru