C++, реализация списка и операции над его элементами.

суббота, 27 октября 2012

18:15

C++, реализация списка и операции над его элементами.

все записи пользователя в сообществе Trinity Soul

Здравствуйте.
Вот написанный код, и я уже не совсем его понимаю. Помогите разобраться, исправить ошибки.
В общем, нужно было создать список с возможностью добавления нового элемента в конец списка, удаление первого/последнего элемента, поиск и возвращение элемента с заданным id.
При попытке компиляции под gcc, много ошибок, мол, многие переменные не заданы и видимо совсем не распознает структуру Link в других функциях(нет декларации first, last, некорректная инициализация внутри класса статического элемента данных нецелочисленного типа «link*», ISO C++ запрещает инициализацию элемента «last» [-fpermissive], ошибка: в результате которой «first» становится статическим [-fpermissive] и тд)
Очень хотелось бы разобраться.

UPD
читать дальше

#include <iostream>
using namespace std;

class ListItem {
public:
  int d;
  ListItem *next;
};

class MyClass {
public:
  ListItem *first, *last;
  MyClass();
  int len; //длина списка
  void Add(int d);
  void RemFirst();
  void RemLast();
  int GetItem(int id);
  int Show();
};


MyClass::MyClass() {
  first=NULL;
  last=NULL;
  len=0;
}

void MyClass::Add(int d) {
  ListItem *newlink = new ListItem;
  newlink->next=NULL;
  newlink->d=d;
  if(first==NULL) {
    last=newlink;
    first=newlink;
  } else {
    last->next=newlink;
    last=newlink;
  }
  len++;
}

void MyClass::RemFirst() {
  if(first==NULL) {
  cout<<"List is Empty"<<endl;
  } else {
    delete first;
    first=first->next;
    len--;
    cout<<"First item remove successfully"<<endl;
  }
}

void MyClass::RemLast() {
  if (first==NULL) {
  cout<<"List Is Empty"<<endl;
  return;
  }
  if(first->next==NULL) {
    delete first;
    first=last=NULL;
    len=0;
    cout<<"Last item remove successfully"<<endl;
  } else {
    ListItem *p=first;
    while(p!=0) {
    if(p->next==last) {
    last=p;
    delete p->next;
    p->next=NULL;
    len--;
    cout<<"Last item remove successfully"<<endl;
    break;
    } 
    p=p->next;
  }
}
}

int MyClass::GetItem(int id) {
  ListItem* Item=first;
  if(id>len) {
    cout<<"ERR"<<endl;
  }
  for(int k=0;k<id;k++) {
    Item=Item->next;
  }
  return Item->d;
}



int MyClass::Show() {
  ListItem *current=first;
  while(current!=NULL) {
    cout<<current->d<<endl;
    current = current->next;
  }
}

int main() {
  MyClass item;
  item.Add(15);
  item.Add(101);
  item.Add(24);
  item.Add(42);
  item.Add(7);
  item.RemLast();
  item.Show();
 }

@темы: C++

URL

Какой, однако, продвинутый у нас аэрофлот! Встреча с ним ... Прошел AvP Отстой :( но местами страшно ;) Жду SS2... Масса приятных неожиданностей подстерегает докторов в бес...

Маше 12. - Чем птичка отличается от самолета? - Ничем... Все-таки моя нерешительность - мой крест. Она мне всю жиз... http://www.landofsmile.ru/fotoproj/colors/yellow-mid.jpg ...

Комментарии

27.10.2012 в 18:53

И тесно облакам.

Код совершенно безумный, синтаксису C++ он не соответствует абсолютно. Почитайте о том, как создавать и использовать классы в C++. Вот часть ошибок:

"class ListItem {static:" - такой конструкции, по-моему, вообще нет. После "class MyClass {" надо добавить модификатор доступа "public: ". В перечислении методов пропущены точки с запятыми. Пропущена точка c запятой после объявления класса. Не указано имя класса при определении методов. Методы Add, Remove объявлены как возвращающие int, хотя они ничего не возвращают (надо void). Функция main вообще неправильная.

И на будущее: не надо пересказывать ошибки компилятора своими словами.

URL

27.10.2012 в 20:12

Trinity Soul

Ri, спасибо за отклик.
В оп-посте теперь слегка подправленная версия.

>>Не указано имя класса при определении методов.
Это где объявлять и как?
Как должна выглядеть main, в таком случае?
И в какой части кода лучше объявлять len, id?

URL

27.10.2012 в 20:23

И тесно облакам.

Переменную len нужно перенести внутрь класса MyClass. Значение 0 ей нужно ставить в конструкторе, который придется для этого создать. В конструктор также нужно перенести инициализацию переменных first, last. В теле класс инициализировать поля нельзя.

Глобальная переменная id вам не нужна.

Вместо "void RemLast() { ..." надо писать "void MyClass::RemLast() {".

Структура link у вас внутри класса ListItem, это совершенно излишне. В C++ структура - это простейший класс, поэтому struct можно заменить на class и добавить "public:", а внешний класс ListItem нужно убрать. Соответственно, обращение "struct link" изменится на "link".

Функция main может выглядеть так:

int main() {
MyClass object;
object.Add(15);
object.Add(24);
object.Add(7);
object.Show();
}

Ваш список хранит целые числа. Вам это и нужно? Бывает, что нужно написать список, который может хранить объекты любого типа. Там задействуется шаблонная магия и всё становится немного по-другому.

URL

27.10.2012 в 21:42

Trinity Soul

С конструктором не все понятно. Какой тип должен стоять для *first, *last?

Да, здесь список с целыми числами. Хотя про список с объектами любого типа тоже хотелось бы узнать.

URL

27.10.2012 в 21:48

И тесно облакам.

С конструктором не все понятно.

class MyClass { 
  MyClass();
  ...
};

MyClass::MyClass() {
  first = NULL;
  Last = NULL;
  len = 0;
}

Какой тип должен стоять для *first, *last?
Раз уж вы убрали link и оставили вместо него ListItem, то вам нужно везде заменить link на ListItem (в т.ч. внутри ListItem).

URL

27.10.2012 в 22:07

Trinity Soul

Теперь так?

URL

27.10.2012 в 22:17

И тесно облакам.

gist.github.com/3965572
Я тут вам исправил остальное. Не ручаюсь, что всё правильно, но оно хотя бы компилится и пишет то, что надо.

URL

27.10.2012 в 22:51

Trinity Soul

Ri, спасибо большое за помощь и разъяснения =)

И у меня еще вопрос будет: что нужно, чтобы все функции заработали из консоли?

URL

27.10.2012 в 22:54

И тесно облакам.

И у меня еще вопрос будет: что нужно, чтобы все функции заработали из консоли?
Не понял вопрос, поясните.

URL

27.10.2012 в 22:59

Trinity Soul

Показать как они работают.
Добавить, удалить, найти элемент.

URL

27.10.2012 в 23:07

И тесно облакам.

Это нетривиально. Можно сделать так, например: сначала спрашиваем тип операции (1 - добавить, 2 - удалить, 3 - найти), потом в зависимости от введенной цифры действуем дальше, запрашиваем у юзера значение (если нужно), выполняем операцию и отображаем результат. А вам это точно нужно? Обычно, чтобы показать, как всё работает, достаточно в main написать соответствующие команды.

URL

27.10.2012 в 23:14

Trinity Soul

Понятно. Думаю, что не нужно все же.
Еще раз спасибо за помощь)

URL

28.10.2012 в 12:48

Trinity Soul

Корректно работает только Add(хотя в этом тоже нет особой уверенности).
После попытки изменения RemFirst при пустом списке возникает ошибка сегментирования.

void MyClass::RemFirst() {
  if(len=0) {
  cout<<"List is Empty"<<endl;
  } else {
    first=first->next;
    len--;
    cout<<"First item remove successfully"<<endl;
  }
}

URL

28.10.2012 в 13:42

Trinity Soul

Исправилось изменением условия if(first==NULL).
Хотя все еще непонятно почему возникала ошибка.

А как переработать две другие функции, чтобы все заработало я вообще не знаю.

URL

28.10.2012 в 14:51

И тесно облакам.

Вообще, тут всё еще много ошибок, сразу так всё и не перечислишь. Что конкретно у вас сейчас не работает и как именно оно не работает? И дайте ваш текущий код.

URL

28.10.2012 в 15:15

Trinity Soul

Ошибки логического характера?
RemLast() удаляет все элементы кроме первого в списке.
При GetItem() просто выводится список. Ее действие заметно только если id>len - здесь все правильно, выдает ошибку.
Текущий код опять в оп-посте.

URL

30.10.2012 в 10:31

void MyClass::RemLast() {

  if(first == NULL)
    return;

  if(first->next==NULL) {
    //assert(first==last);
    delete first;
    first=last=NULL;
    len=0;

  } else {
    ListItem *p=first;
    while(p!=NULL)
    {
        if(p->next==last)
        {
            last=p;
            delete p->next;
            p->next = NULL;
            len--;

            break;
        }
        p=p->next;
    }
    //assert(p!=NULL);
  }
}

В RemFirst тоже память течёт, но это уже сами. Чтобы собиралось с ассертами, подключай assert.h и снимай с них комменты.
А "удаляло" оно весь список потому, что за ифами нужно следить:
if(first->next=NULL)

URL

30.10.2012 в 21:49

Trinity Soul

.Седьмой, спасибо, теперь RemLast работает. Не поясните вот эту строчку в конце: p=p->next; ?

>>память течёт
Здесь тоже не совсем понимаю.

URL

30.10.2012 в 22:05

И тесно облакам.

Не поясните вот эту строчку в конце: p=p->next; ?
Это просто проход по списку, переход к следующему элементу. У вас то же самое в Show() написано: " current = current->next;".

память течёт
У вас создаются объекты ListItem через new. Соответственно, вам их надо через delete удалить, чтобы память освободилась. А у вас просто зануляется указатель на объект. Указатель потеряли, delete не сделали - память осталась занятой. Это и есть утечка памяти.

URL

30.10.2012 в 22:10

Trinity Soul

Ri, понятно.
И еще, вы говорили, что здесь по-прежнему много ошибок. Не укажете где?

И с GetItem не все ясно.

URL

02.11.2012 в 18:51

Trinity Soul

GetItem, не выводится значение элемента.

int MyClass::GetItem(int id) {
  int n=1;
  ListItem* Item=first;
  if(id>len) {
    cout<<"ERR"<<endl;
    } while(n<id) {
      if(n==id){
      cout<<"Element = "<<Item->d;
      break;
      } else {
        Item=Item->next;
        n++;
      }
   }
}

URL

08.11.2012 в 19:05

Trinity Soul

Вижу свою ошибку ^^"

int MyClass::GetItem(int id) {
  int n=1;
  ListItem *Item=first;
  if(id>len) {
    cout<<"ERR"<<endl;
  }
    while(n<=len) {
    if(n==id){
    cout<<"Element = "<<Item->d<<endl;
    break;
    } else {
      Item=Item->next;
      n++;
  }
}
}

Не посмотрите, что в общем коде еще можно доработать/исправить?

URL


Запомнить

C++, реализация списка и операции над его элементами.

ru_programming