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

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

Войти
Регистрация
Восстановить пароль
 
Codewriter
0 / 0 / 0
Регистрация: 15.05.2010
Сообщений: 9
#1

Проблема с классом для линейного списка - C++

15.05.2010, 12:42. Просмотров 592. Ответов 10
Метки нет (Все метки)

Доброго времени суток!
Начал писать класс для организации хранения данных в виде линейного списка, вот Header file:
//---------------------------------------------------------------------------------------------------
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <stdexcept>
typedef int value_type;
typedef unsigned int size;
class Node
    {
      public:
      Node *next;
      Node *prev;
      value_type d;
    };
 
 
class list
{
    private:
    Node *pbeg; //указатель на начало списка
    Node *pend; //указатель на конец списка
    size count;
    public:
    list();
    list(const value_type &r, size n); 
    bool IsEmpty()const{return (pbeg==0);} //проверка на пустоту
    void push_back(value_type d);             //добавление элементов с конца
    void push_front(value_type d);             //добавление элементов с начала 
    Node *operator[](int i)throw(std::out_of_range); //доступ к элементу по номеру
    Node *find(value_type d);                  //поиск по информационной части
    bool remove(value_type key);             //удаление по ключу
    long Size()const{return count;};         //возвращает кол-во элементов
    Node *insert(int key, int d);                //вставка элемента 
    void print();
};
 
 void list::push_back(value_type d)
 {
     if(!pbeg)
     {
         Node *pv=new Node;
         pv->d=d; pv->next=0;
         pv->prev=0;
         pbeg=pv;
         pend=pbeg;
         count=1;
     }
     else
     {
         Node *pv=new Node;
         pv->d=d; pv->next=0;
 
         pv->prev=pend;
         pend->next=pv;                                                              // (1)
         pend=pv;
         count++;
     }
 }
 
 void list::push_front(value_type d)
 {
     if(!pbeg)
     {
         Node *pv=new Node;
         pv->d=d; pv->prev=0;
         pv->next=0;
         pbeg=pv;
         pend=pbeg;
         count=1;
     }
     else
     {
         Node *pv=new Node;
         pv->d=d; pv->next=0;
 
         pv->next=pbeg;
         pbeg->prev=pv;                                                  //(2)
         pbeg=pv;
         count++;
     }
 }
 
list::list()
{
    pbeg=0;
    pend=pbeg;
}
 
list::list(const value_type &r, size n)
{
    list tmp;
    for(int i=1; i<=n; i++)
    tmp.push_front(r);
    *this=tmp;
}
 
 Node *list::operator[](int i)throw(std::out_of_range)
 {
   if(i<=count)
   {
       Node *pv=pbeg;
       int i=1;
       while(i<=count && pv)
       {
           pv=pv->next; i++;
 
       }
    return pv;
   }
   else throw std::out_of_range("Index out of range");
 }
 
  Node *list::find(value_type d)
 {
     Node *pv=pbeg;
     while(pv)
     {
         if(pv->d==d) break;
         pv=pv->next;
     }
     return pv;
 }
 
 bool list::remove(value_type key)
 {
     if(Node *pkey=find(key))
     {
         if(pkey==pbeg)
         {
             pbeg=pbeg->next;
             pbeg->prev=0;
         }
         else if(pkey==pend)
         {
             pend=pend->prev;
             pend->next=0;
         }
         else
         {
             (pkey->prev)->next=pkey->prev;
             (pkey->next)->prev=pkey->prev;
         }
         delete pkey;
         return true;
     }
     return false;
 }
 
 Node *list::insert(int key, int d)
 {
     if(Node *pkey=find(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 list::print()
 {
  Node *pv=pbeg;
  while(pv)
  {
   cout<<pv->d<<' ';
   pv=pv->next;
  }
  cout<<endl;
 }
//-----------------------------------------------------------------------------------------------------
проблемы возникают с функциями push_back и push_front в местах помеченных как (1) и (2), где компилятор выдает ошибку Access violation.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2010, 12:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Проблема с классом для линейного списка (C++):

Использование линейного списка для хранения последовательности - C++
Разработать программу, которая организует с использованием линейного списка хранение последовательности, а так же выполняет следующие...

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

Привести пример реализации любого линейного списка списка с использованием лишь структур - C++
Буду благодарен, если кто-нибудь сможет привести пример реализации любого линейного списка списка с использованием лишь структур (то есть...

Проблема с классом - C++
Доброе времени суток...у меня проблема в создании класса - динамического массива! проблема в изминении определённого элемента и вывода на...

Проблема с классом Вектор - C++
Здравствуйте! Не могу понять почему вместо значений вектора выводиться непонятные числа. Вот код: #include &lt;vector&gt; #include...

Проблема с классом и массивом char-ов - C++
Есть класс, содержащий одномерный массив из char-ов и методы для работы с ним. Проблема возникла в самом начале - не получается корректно...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Adler
78 / 78 / 3
Регистрация: 07.05.2009
Сообщений: 316
15.05.2010, 13:34 #2
C++
1
delete pkey;
попробуй заменить на:
C++
1
if(pkey==pbeg)pbeg=0;if(pkey==pend)pend=0;delete pkey;
1
Codewriter
0 / 0 / 0
Регистрация: 15.05.2010
Сообщений: 9
15.05.2010, 14:05  [ТС] #3
Цитата Сообщение от Adler Посмотреть сообщение
C++
1
delete pkey;
попробуй заменить на:
C++
1
if(pkey==pbeg)pbeg=0;if(pkey==pend)pend=0;delete pkey;
В функции remove ничего заменять не нужно, она корректна. Повторяюсь проблема с функциями push_back и push_front.
0
Adler
78 / 78 / 3
Регистрация: 07.05.2009
Сообщений: 316
15.05.2010, 15:46 #4
Codewriter
Цитата Сообщение от Codewriter
В функции remove ничего заменять не нужно, она корректна.
ну ну...

Добавлено через 20 минут
а если так?
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
void list::push_back(value_type d)
{
  if(!pend)
  {
    Node *pv=new Node; pv->d=d;
    pv->next=0; pv->prev=0;
    pbeg=pv; pend=pv;
    count=1;
  }else{
    Node *pv=new Node; pv->d=d; pend->next=pv;
    pv->next=0; pv->prev=pend;
    pend=pv;
    count++;
  }
 }
 
 void list::push_front(value_type d)
 {
  if(!pbeg)
  {
    Node *pv=new Node; pv->d=d;
    pv->next=0; pv->prev=0;
    pbeg=pv; pend=pv;
    count=1;
  }else{
    Node *pv=new Node; pv->d=d; pbeg->prev=pv;
    pv->next=pbeg; pv->prev=0;
    pbeg=pv;
    count++;
  }
 }
1
Codewriter
0 / 0 / 0
Регистрация: 15.05.2010
Сообщений: 9
15.05.2010, 16:42  [ТС] #5
В случае использования функции push_back компилятор все равно указывает Access violation для строки pend->next=pv в части else, даже если внести изменения, которые вы предлагаете, Adler. Вы вообще какой средой пользуетесь? Я пользуюсь C++Builder.
0
Adler
78 / 78 / 3
Регистрация: 07.05.2009
Сообщений: 316
15.05.2010, 18:09 #6
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
 bool list::remove(value_type key)
 {
         if(Node *pkey=find(key))
         {
                 if(pkey==pbeg)
                 {
                         pbeg=pbeg->next; //вот тут pbeg вполне может стать 0
                         pbeg->prev=0;//тогда тут выпадет AV
                 }
                 else if(pkey==pend) //ты пропустил случай pkey==pbeg==pend
                 {
                         pend=pend->prev; //вот тут pend вполне может стать 0
                         pend->next=0;//тогда тут выпадет AV
                 }
                 else
                 {
                         (pkey->prev)->next=pkey->prev;//тут тоже будет AV если pkey->prev==0
                         (pkey->next)->prev=pkey->prev;//а тут если pkey->next==0
                 }
                 delete pkey;//здесь ты освободил pkey, если у тебя ещё где-то есть на него указатели, то они больше не валидны
                 return true;
         }
         return false;
 }
ты всё ещё думаешь этот метод корректен?
1
Codewriter
0 / 0 / 0
Регистрация: 15.05.2010
Сообщений: 9
16.05.2010, 07:43  [ТС] #7
Ладно насчет метода remove я согласен, он не учитывает случай, когда в списке остался один элемент, но давай подумаем насчет методов push_back и push_front, ведь сначала нужно сформировать список.
0
Adler
78 / 78 / 3
Регистрация: 07.05.2009
Сообщений: 316
16.05.2010, 12:27 #8
ха, вот ещё один косяк:
C++
1
2
(pkey->prev)->next=pkey->prev;
(pkey->next)->prev=pkey->prev;
в этот кусок запарывает всё. т.к выглядеть он должен так:
C++
1
2
3
    Node *next=pkey->next,*prev=pkey->prev;
    if(next)next->prev=prev;
    if(prev)prev->next=next;
Добавлено через 39 секунд
полный вариант:
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <stdexcept>
#include <windows.h>
typedef int value_type;
typedef unsigned int size;
using namespace std;
class Node
{
  public:
  Node *next;
  Node *prev;
  value_type d;
};
 
class list
{
private:
  Node *pbeg; //указатель на начало списка
  Node *pend; //указатель на конец списка
  size count;
public:
  list();
  list(const value_type &r, size n); 
  bool IsEmpty()const{return (pbeg==0);} //проверка на пустоту
  void push_back(value_type d);             //добавление элементов с конца
  void push_front(value_type d);             //добавление элементов с начала 
  Node *operator[](int i)throw(std::out_of_range); //доступ к элементу по номеру
  Node *find(value_type d);                  //поиск по информационной части
  bool remove(value_type key);             //удаление по ключу
  long Size()const{return count;};         //возвращает кол-во элементов
  Node *insert(value_type key, value_type d);                //вставка элемента 
  void print();
};
 
void list::push_back(value_type d)
{
  if(!pend)
  {
    Node *pv=new Node; pv->d=d;
    pv->next=0; pv->prev=0;
    pbeg=pv; pend=pv;
    count=1;
  }else{
    Node *pv=new Node; pv->d=d; pend->next=pv;
    pv->next=0; pv->prev=pend;
    pend=pv;
    count++;
  }
 }
 
 void list::push_front(value_type d)
 {
  if(!pbeg)
  {
    Node *pv=new Node; pv->d=d;
    pv->next=0; pv->prev=0;
    pbeg=pv; pend=pv;
    count=1;
  }else{
    Node *pv=new Node; pv->d=d; pbeg->prev=pv;
    pv->next=pbeg; pv->prev=0;
    pbeg=pv;
    count++;
  }
 }
 
list::list()
{
  pbeg=0; pend=pbeg; count=0;
}
 
list::list(const value_type &r, size n)
{
  list tmp;
  for(int i=1; i<=n; i++)
  tmp.push_front(r);
  *this=tmp;
}
 
Node *list::operator[](int i)throw(std::out_of_range)
{
  if(i<=count)
  {
    Node *pv=pbeg;
    int i=1;
    while(i<=count && pv){pv=pv->next; i++;}
    return pv;
  }else throw std::out_of_range("Index out of range");
}
 
Node *list::find(value_type d)
{
  Node *pv=pbeg;
  while(pv)
  {
    if(pv->d==d) break;
    pv=pv->next;
  }
  return pv;
}
 
bool list::remove(value_type key)
{
  Node *pkey=find(key);
  if(!pkey)return false;
  if(pkey==pbeg)
  {
    pbeg=pbeg->next;
    pbeg->prev=0;
  }
  if(pkey==pend)
  {
    pend=pend->prev;
    pend->next=0;
  }else{  
    Node *next=pkey->next,*prev=pkey->prev;
    if(next)next->prev=prev;
    if(prev)prev->next=next;
  }
  if(pkey==pbeg)pbeg=0;if(pkey==pend)pend=0;delete pkey;
  count--;
  return true;
}
 
Node *list::insert(value_type key, value_type d)
{
  if(Node *pkey=find(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;
    count++;
    return pv;
  }
  return 0;
}
 
void list::print()
{
  Node *pv=pbeg;
  while(pv)
  {
    cout<<pv->d<<' ';
    pv=pv->next;
  }
  cout<<endl;
}
 
list l;
int main()
{
  for(int i=0;i<10;i++)l.push_back(i);
  l.remove(7);
  l.push_back(5);
  l.insert(5,0);
  l.print();
  system("pause");
}
1
Codewriter
0 / 0 / 0
Регистрация: 15.05.2010
Сообщений: 9
16.05.2010, 14:58  [ТС] #9
Спасибо, Adler!
0
Codewriter
0 / 0 / 0
Регистрация: 15.05.2010
Сообщений: 9
25.05.2010, 15:00  [ТС] #10
И все же функция remove не учитывает тот случай когда в списке один элемент.
0
Adler
78 / 78 / 3
Регистрация: 07.05.2009
Сообщений: 316
25.05.2010, 19:55 #11
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool list::remove(value_type key)
{
  Node *pkey=find(key);
  if(!pkey)return false;
  if(pkey==pbeg)
  {
    pbeg=pbeg->next;
    if(pbeg)pbeg->prev=0;
  }
  if(pkey==pend)
  {
    pend=pend->prev;
    if(pend)pend->next=0;
  }else{  
    Node *next=pkey->next,*prev=pkey->prev;
    if(next)next->prev=prev;
    if(prev)prev->next=next;
  }
  if(pkey==pbeg)pbeg=0;if(pkey==pend)pend=0;delete pkey;
  count--;
  return true;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2010, 19:55
Привет! Вот еще темы с ответами:

Доделать удаление элемента для линейного списка "Каталог файлов" - C++
В файловой системе каталог файлов организован как линейный список. Для каждого файла в каталоге содержатся следующие сведения: -&gt; имя...

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

Удаление элемента из односвязного списка, представленного классом - C++
Описание списка class link // один элемент списка { public: char* data; // некоторые данные link* next; // указатель на...

Создание линейного списка - C++
Здравствуйте!!!!!! Помогите пожалуйста написать программку создание линейного спискаи распечатка линейного списка.Очен надо!!!! Заранее...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.05.2010, 19:55
Ответ Создать тему
Опции темы

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