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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 121, средняя оценка - 4.88
Diplomat
0 / 0 / 0
Регистрация: 11.06.2011
Сообщений: 33
15.06.2012, 13:53     Связанные списки #1
Составить программу, работающую со связанными списками. Мы будем рассматривать связанный список как объект, содержащий связанный список данных и операций (методов), которые вы можете с ними выполнять. Связанный список данных состоит из указателей на начало («голову») и конец («хвост») связанного списка (в нашем примере из-за его гибкости используется двунаправленный связанный список). Каждый элемент связанного списка представляет собой реализацию отдельного объекта. Возможности, необходимые для использования связанного списка, предоставляют следующие операции:
• создание связанного списка (выделение для него памяти);
• уничтожение связанного списка (освобождение используемой памяти);
• инициализация связанного списка;
• деинициализация связанного списка;
• вставка элемента в середину списка перед существующим элементом;
• присоединение элемента к концу связанного списка;
• удаление элемента из связанного списка;
• возвращение первого элемента связанного списка;
• возвращение последнего элемента связанного списка.
Необходимо иметь в виду, что создание и инициализация, а также уничтожение и деинициализация методов — это не синонимы. При создании и уничтожении методы create и destroy выделяют и освобождают память для объекта (связанного списка), а методы инициализации и деинициализации initialize и deinitialize только инициализируют и деинициализируют ранее выделенные экземпляры объекта. Вы можете видеть, как объект связанного списка наследуется объектами стека или очереди, поскольку очередь и стек можно реализовать как связанный список с ограниченным числом операций. Например, можно реализовать очередь в виде связанного списка, в котором элементы могут добавляться к концу и извлекаться из начала. Если вы таким образом реализуете очередь, то нужно запретить наследуемые методы связанного списка, которые для очереди недопустимы (например, вставку в середину списка).

Добавлено через 2 часа 22 минуты
По ходу никто не сможет помочь
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
15.06.2012, 15:18     Связанные списки #2
Вот тебе возьми за основу связный список, ничего не хватает добавишь сам
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
95
96
97
98
99
100
101
#include <iostream> 
using namespace std;
 
typedef int newtp;
struct node 
{ 
    newtp data; //  данные 
    node* next; // указатель на следующий
    node* pred; // указатель на предыдущий
}; 
 
class linklist // класс связный список
{ 
private: 
    node* first; // указатель на начало
public: 
    linklist() { first = NULL; } // в конструкторе инициализируем его, он указывает в 
                                 // в место где нет полезной информации
 
    void push( newtp d, int pos); // метод добавления элемента
    int pop( int pos);  // метод удаления элемента
    void clean(); // удаление всех элементов
    void view(); // вывод на экран
}; 
 
void linklist::push( newtp d, int pos) // метод добавления элемента
{ 
 
    node* newnode = new node; // создаём новый элемент
    newnode->data = d; // вводим в него данные
    if(first == NULL)   // если это первый элемент в списке                                   
    { 
        newnode->next = newnode; 
        newnode->pred = newnode; 
        first = newnode; // first  указывает на него
    } 
    else 
    {
        node* temp = first; // создаём времменный указатель
        for ( int i = pos; i > 1; i--,temp=temp->next); // цикл
            temp->pred->next = newnode; 
            newnode->pred = temp->pred; 
            newnode->next = temp; // добавляем перед времменным
            temp->pred = newnode;  
    }
}  
 
int linklist::pop( int pos) // удаляем элемент из списка по индексу
{ 
  if(first == NULL)  return 0; // если список пуст
  int val;  
  if(first == first ->next) // если это последний элемент в списке
  { 
      val = first->data; 
      delete first; 
      first = NULL; 
  } 
  else  
 { 
      node* temp = first; 
      for ( int i = pos; i > 1; i--, temp = temp->next); 
          if( temp == first) first = temp->next; 
              temp->pred->next = temp->next; // удаляем temp элемент
              temp->next->pred = temp->pred; 
              val = temp->data; 
              delete temp;   
  } 
  return val; 
} 
 
void linklist::clean() // удалить все элементы из списка
{  
    if(first == NULL) return ; 
    for ( node* newnode = first->next; newnode!=first; newnode = newnode->next) delete newnode; 
    delete first; 
    first = NULL; 
}
 
void linklist::view() // просмотр элементов в списке
{  
    if(first == NULL) return ; 
    node* newnode = first; 
    do 
    { 
        cout << newnode->data << endl; 
        newnode = newnode->next; 
    } while(newnode!=first); 
}
 
int main() 
{ 
    linklist li; 
    
    li.push(12,1); 
    li.push(13,2); 
    li.push(14,2); 
 
    li.view();
 
    
}
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
25.09.2012, 23:40     Связанные списки #3
Всем привет. ребят подскажите плз., где косяк допустил в листинге, уже голову сломал.
Смысл такой, надо создать метод для добавления элемента в конец связанного списка.
при компиляции возникает сообщение о прекращении работы программы
вот мой листинг:

#include <iostream>
using namespace std;
////////////////////////////////////////////////////////////////////////////////
struct link
{
int data;
link* next;
};
////////////////////////////////////////////////////////////////////////////////
class linklist
{
private:
link* first;
public:
linklist()
{ first = NULL; }
void additem(int d)
{
link *newlink = new link;
if(first==NULL)
{
newlink -> data = d;
newlink -> next = first;
first = newlink;
}
else
{
link *temp = first;
while(temp)
temp = temp -> next;
temp -> next = newlink;
newlink -> data = d;
newlink -> next = NULL;
}
}
void display()
{
link *temp = first;
while(temp)
{
cout << temp -> data << endl;
temp = temp -> next;
}
}
};
////////////////////////////////////////////////////////////////////////////////
int main()
{
linklist m;
m.additem(10);
m.additem(20);
m.additem(30);
m.additem(40);
m.display();
cout << endl;
system("pause");
return 0;
}
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
25.09.2012, 23:44     Связанные списки #4
Sher_vud, у вас получается петля при добавлении первого элемента в список.
newlink -> next = first; не надо. надо занулять
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
25.09.2012, 23:56     Связанные списки #5
I.M. попробовал проставить NULL, к сожалению работать метод по прежнему отказывается.
больше всего сомнений в этих строках:
else
{
link *temp = first;
while(temp)
temp = temp -> next = newlink;
//temp -> next = newlink;
newlink -> data = d;
newlink -> next = NULL;
}
вот не могу не много понять. по идее когда завершается цикл указатель темп глядит на последний элемент списка. ну и я логично пытаюсь в поле next этого элемента изменить указатель со значения NULL на новоявленый элемент. Вешаться начало все после написания строки:
temp -> next = newlink;
я ее закоментил и попробовал по другому, что так же привело к аварийному завершению
temp = temp -> next = newlink; ( добавил =newlink)
вот и не пойму где я не правильно понял работу метода
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 00:19     Связанные списки #6
Sher_vud, вот, чуть подкорректировал функцию добавления:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void additem(int d)
{
 link *temp;
 link *newlink=first;
 if(first==NULL)
  {
   temp = new link;
            temp -> data = d;
   temp -> next = first;
   first = temp;
  }
 else
 {
  temp = newlink;
  while(temp->next)
   temp = temp -> next;
  temp->next = new link;
  temp = temp -> next;
  temp -> data = d;
 }
 temp-> next = NULL;
 newlink=temp;
}
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
26.09.2012, 00:44     Связанные списки #7
BumerangSP спасибо большое, все работает. сей час попробую разобраться где допустил ошибку.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 00:45     Связанные списки #8
Можно и так сделать:
C++
1
2
3
4
5
6
7
8
void additem(int d)
{
     link *newlink = new link;
 
     newlink -> data = d;
     newlink -> next = first;
     first = newlink;
}
Тут ещё всё зависит от того, по какому принципу список строится. Самый простой - по принципу стека, т.е. последний по времени создания элемент будет в голове списка. Мой метод именно для него. Можно и по другому, чтобы в голове списка был первый по времени создания элемент.
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
26.09.2012, 01:01     Связанные списки #9
alsav22 такой метод я как раз использовал, изучая главу "указатели". в задании к этой главе было необходимо как раз изменить данный метод, так что бы элементы вставали не в начала списка, а с конца.
если честно, пока тяжело понять каким образом описать метод с привязкой по времени создания элемента. наверное должна использоваться какая то библиотечная функция, если alsav22 Вы расскажете подробнее, буду рад узнать что то новое.
BumerangSP никак не могу понять вот эту строчку:

while(temp->next)

делаем, пока указатель содержит не NULL? я в правильную сторону мыслю?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 01:26     Связанные списки #10
Цитата Сообщение от alsav22 Посмотреть сообщение
Можно и по другому, чтобы в голове списка был первый по времени создания элемент.
Тогда вот так:
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
#include <iostream>
using namespace std;
 
struct link
{
    int data;
    link* next;
};
 
class linklist
{
 private:
    link* first; // начало списка
    link* rear; // конец списка
 
 public:
    linklist()
    { 
        first = NULL;
        rear = NULL;
    }
    
    void additem(int d)
    {
       link *newlink = new link; // новый элемент списка
       newlink -> data = d;
       newlink -> next = NULL;
        
       if (first == NULL) // если список пустой, то в начало
            first = newlink; // first начало списка
       else  rear -> next = newlink; // если список не пустой, то в конец
       
       rear = newlink; // rear конец списка
    }
    
    void display()
    {
        link *temp = first;
        while(temp)
        {
            cout << temp -> data << endl;
            temp = temp -> next;
        }
    }
};
 
 
int main()
{
 linklist m;
 m.additem(10);
 m.additem(20);
 m.additem(30);
 m.additem(40);
 m.display();
 cout << endl;
 
 system("pause");
 return 0;
 }
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 01:34     Связанные списки #11
Sher_vud, вот у Вас было так:
C++
1
2
3
while(temp)
 temp = temp -> next;
...
т.е. пока текущий указатель temp не будет равен NULL. В моем же случае (temp->next) пока указатель на следующий элемент не будет = NULL. Т.е. тем самым мы смещаем указатель temp на последний элемент в списке. Если мы будем смещать указатель только текущего элемента, мы в итоге встретим null, цикл завершится, указывая на null, а не на последний элемент.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 01:54     Связанные списки #12
Удалил.
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
26.09.2012, 01:56     Связанные списки #13
BumerangSP спасибо огромное, теперь понял
alsav22 спасибо, я понял суть метода, но вот механизм пока не удается осмыслить.
запутался в этих строках:
C++
1
2
else  rear -> next = newlink; // если список не пустой, то в конец
rear = newlink; // rear конец списка
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 02:09     Связанные списки #14
Мне кажется, что вариант BumerangSP не очень рационален. Из за того, что нет указателя на конец очереди, приходится каждый раз, при добавлении нового элемента, пробегать по очереди от первого элемента до последнего.
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
26.09.2012, 02:19     Связанные списки #15
alsav22, BumerangSP, еще раз Вам спасибо. может тороплюсь, но все же. переработал свой метод, на основании Ваших замечаний и поправок. все заработало
вот что у меня получилось:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
      void additem(int d)
             {
                  link *temp = first;
                  link *newlink = new link;
                  if(first==NULL)
                  {
                  newlink -> data = d;
                  newlink -> next = NULL;
                  first = newlink;
                  }
                  else
                  {
                  while(temp->next)
                  temp = temp -> next;
                  temp -> next = newlink;
                  newlink -> data = d;
                  newlink -> next = NULL;
                  }
             }
делаю вывод, что грубая ошибка крылась в цикле, а именно:
while(temp)
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 02:23     Связанные списки #16
alsav22, я просто чуть исправил готовую функцию. Это односвязный линейный список, не очередь.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 02:42     Связанные списки #17
Цитата Сообщение от Sher_vud Посмотреть сообщение
alsav22 спасибо, я понял суть метода, но вот механизм пока не удается осмыслить.
запутался в этих строках:
else rear -> next = newlink; // если список не пустой, то в конец
rear = newlink; // rear конец списка
Два указателя first и rear. Один указывает на начало списка, другой на конец. Сначала оба на NULL. Создаётся новый элемент, на него указывает newlink. Если список пустой, то значение newlink присваивается указателю на начало списка - first. Это произойдёт одни раз. В следующие разы заход будет уже только в else. То есть first в дальнейшем меняться не будет, и он будет указывать на начало списка. В первый раз else пропускается, после него указателю rear присваивается значение newlink, то есть, пока элемент в списке один, начало и конец списка совпадают. При добавлении следующего элемента заход только в else. После этого элемент, который до этого был в конце списка, будет содержать указатель на добавляемый элемент (rear -> next = newlink), а rear присваивается адресс нового элемента (rear = newlink), т.е. новый элемент становится концом списка, адресс которого находится в rear.

Добавлено через 6 минут
Цитата Сообщение от BumerangSP Посмотреть сообщение
Это односвязный линейный список, не очередь.
Я и имел ввиду список. Просто в разных источниках это всё по разному называется, где очередь, где список. Односторонняя очередь, двусторонняя. Односвязанный список, двусвязанный список. Сути это не меняет. Я не спорю, просто поясняю. Тут можно увязнуть в определениях.
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
26.09.2012, 02:47     Связанные списки #18
Цитата Сообщение от alsav22 Посмотреть сообщение
В первый раз else пропускается, после него указателю rear присваивается значение newlink
alsav22 спасибы, наконец то дошло. я видимо пересидел уже.. смотрел и представлял:
C++
1
2
3
4
5
else  
{
rear -> next = newlink; 
rear = newlink;
}
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 03:08     Связанные списки #19
Хитрость этой конструкции в том, чтобы при первом проходе выполнилось только rear = newlink; , а при втором и далее - и rear -> next = newlink;, и rear = newlink;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2012, 12:24     Связанные списки
Еще ссылки по теме:

Подскажите как отладить код (связанные списки) C++
Связанные списки C++
Списки, как склеить списки между собой? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 12:24     Связанные списки #20
Просто в разных источниках это всё по разному называется, где очередь, где список
alsav22, это да. Но у меня именно односвязный список Просто делая функцию, я ни о каком другом виде не думал. И, опять же: будь это очередь, ее элементы при выборке исчезали бы (как в стеке или деке). Исправьте, если неправ.
Yandex
Объявления
26.09.2012, 12:24     Связанные списки
Ответ Создать тему
Опции темы

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