Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 121, средняя оценка - 4.88
Diplomat
0 / 0 / 0
Регистрация: 11.06.2011
Сообщений: 33
#1

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

15.06.2012, 13:53. Просмотров 18587. Ответов 44
Метки нет (Все метки)

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

Добавлено через 2 часа 22 минуты
По ходу никто не сможет помочь
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2012, 13:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Связанные списки (C++):

связанные списки - C++
плиз помогите написать задачку: Запросить у пользователя число n. Построить связный список из n элементов, заполненный случайными...

Связанные списки - C++
Вопросы в комментариях #include <iostream> #include <conio.h> #include <string.h> using namespace std; class NameDataSet { ...

Связанные списки - C++
Здравствуйте! Не очень сложное задание, но так как я начинающий, запуталась немного... особенно с указателями и ссылками. В общем...

Связанные списки С++ - C++
Здравствуйте, изучаю С++ и возникли проблемы с пониманием как работают списки. Вот код: #include <cstdio> #include <cstdlib> ...

Связанные списки (переделать программу) - C++
Как переделать программу, чтобы можно было вводить самому ключи и не было Access Violation? #include <iostream> #include <time.h> ...

Односвязанные и двух-связанные списки - C++
Должны быть следующие функции: 1) Ввод количества элементов и заполнение списка случайными значениями 2) Вывод списка на экран 3)...

44
David Sylva
1290 / 952 / 51
Регистрация: 17.05.2012
Сообщений: 2,687
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();
 
    
}
2
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;
}
0
I.M.
565 / 548 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
25.09.2012, 23:44 #4
Sher_vud, у вас получается петля при добавлении первого элемента в список.
newlink -> next = first; не надо. надо занулять
0
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)
вот и не пойму где я не правильно понял работу метода
0
BumerangSP
4287 / 1409 / 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;
}
0
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
26.09.2012, 00:44 #7
BumerangSP спасибо большое, все работает. сей час попробую разобраться где допустил ошибку.
0
alsav22
5426 / 4821 / 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;
}
Тут ещё всё зависит от того, по какому принципу список строится. Самый простой - по принципу стека, т.е. последний по времени создания элемент будет в голове списка. Мой метод именно для него. Можно и по другому, чтобы в голове списка был первый по времени создания элемент.
0
Sher_vud
4 / 4 / 1
Регистрация: 25.09.2012
Сообщений: 42
26.09.2012, 01:01 #9
alsav22 такой метод я как раз использовал, изучая главу "указатели". в задании к этой главе было необходимо как раз изменить данный метод, так что бы элементы вставали не в начала списка, а с конца.
если честно, пока тяжело понять каким образом описать метод с привязкой по времени создания элемента. наверное должна использоваться какая то библиотечная функция, если alsav22 Вы расскажете подробнее, буду рад узнать что то новое.
BumerangSP никак не могу понять вот эту строчку:

while(temp->next)

делаем, пока указатель содержит не NULL? я в правильную сторону мыслю?
0
alsav22
5426 / 4821 / 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;
 }
0
BumerangSP
4287 / 1409 / 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, а не на последний элемент.
0
alsav22
5426 / 4821 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 01:54 #12
Удалил.
0
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 конец списка
0
alsav22
5426 / 4821 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 02:09 #14
Мне кажется, что вариант BumerangSP не очень рационален. Из за того, что нет указателя на конец очереди, приходится каждый раз, при добавлении нового элемента, пробегать по очереди от первого элемента до последнего.
0
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)
0
26.09.2012, 02:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2012, 02:19
Привет! Вот еще темы с ответами:

Подскажите как отладить код (связанные списки) - C++
условие закомментировано в коде, подскажите, в чём ошибка? функция Sum Должна возвращать требуемое число // ВЫЧИСЛЯЕТ СУММУ ТЕХ ЭЛЕМЕНТОВ...

Списки, как склеить списки между собой? - C++
Ребят, привет всем, есть код, в классе которого описаны несколько методов: добавление элемента в список, удаление и просмотр списка, дак...

Связанные классы - C++
Есть несколько классов,каждый объект которого имеет объект другого класса в качестве элемента данных Это класс Dictionary,в состав...

Ошибки связанные с wininet - C++
Здравствуйте. Проект выглядит так: #include &quot;stdafx.h&quot; #include &lt;windows.h&gt; #include &lt;stdio.h&gt; #include &lt;fstream&gt; #include...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru