C ++ - Вставка в связанный список без использования конструктора узла.Является ли это возможным? - PullRequest
Новая
       24

C ++ - Вставка в связанный список без использования конструктора узла.Является ли это возможным?

0 голосов
/ 15 апреля 2019

Я работаю над реализацией Шаблонного связанного списка в C ++, который будет использоваться для имитации поезда, движущегося через многочисленные остановки, где и добавляются, и удаляются поезда. Traincar - это собственный класс, и каждому объекту должен быть присвоен уникальный идентификатор, начиная с 1, и увеличивается при добавлении автомобиля. Однако при запуске моего кода идентификатор увеличивается больше, чем предполагалось.

После некоторых экспериментов и с помощью предыдущих ответов я определил, что именно операторы new node в моих методах класса LinkedList вызывают увеличение идентификатора больше, чем хотелось бы. Однако я не вижу способа реализации insertion методов без создания new node. Есть ли способ обойти это?

Вот мой TrainCar класс: 

class TrainCar {
public:
  static int nextID;
  int id;
  char typeOfCar;
  int numberOfStops;
  node<char>* car;

  TrainCar();
};

int TrainCar::nextID = 1;

TrainCar::TrainCar() {
  cout << "id++" << endl;
  id = nextID++;
  int i = (rand() % 3);//gives a random number 0 - 2, used to determine what
                       //type of car to add
  if(i == 0) {
    typeOfCar = 'P';
  }
  else if(i == 1) {
    typeOfCar = 'C';
  }
  else {
    typeOfCar = 'M';
  }
  car = new node<char>(typeOfCar);
  numberOfStops = (rand() % 5) + 1;//gives a random number 1 - 5;
}

Вот моя main() функция 

int main() {
  LinkedList<TrainCar> train;
  int addCargoCar = 0;

  for(int i = 0; i < 10; i++) {
    TrainCar newCar;
    if(newCar.typeOfCar == 'P') {
      train.AddToFront(newCar);
      addCargoCar++;
    }
    else if(newCar.typeOfCar == 'C') {
      train.AddAtIndex(newCar, addCargoCar);
    }
    else {
      train.AddToEnd(newCar);
    }
  }

  cout <<"Welcome to the Train Station! Here is your train!" << endl;
  char type;
  int id, numberOfStops, i, j;
  for(i = 0; i < train.size; i++) {
    type = train.Retrieve(i).typeOfCar;
    id = train.Retrieve(i).id;
    numberOfStops = train.Retrieve(i).numberOfStops;
    cout << "[" << id << ":" << type << ":" << numberOfStops << "] ";
  }
}

На выходе должно быть что-то похожее на 

[5:P:1][6:P:4][8:P:2][3:P:2][10:C:3][2:C:3][4:C:1][1:M:1][7:M:3][9:M:2]

Но мой вывод: 

[17:P:2][9:P:2][5:C:2][19:C:1][15:C:2][1:M:5][3:M:4][7:M:1][11:M:3][13:M:1]

Редактировать: вот метод AddToFront(): (все другие методы добавления похожи по своей природе). Проблема с выводом - new node<T>(d) операторов 

template <class T>
void LinkedList<T>::AddToFront(T d) {
  node<T>* newNode = new node<T>(d);

  if(head == NULL) {
    head = newNode;
    tail = newNode;
    size++;
  }

  else {
    newNode->next = head;
    head = newNode;
    size++;
  }
}

Edit2: вот моя функция Retrieve (теперь исправлена, она больше не использует оператор new node): 

template <class T>
T LinkedList<T>::Retrieve(int index) {
  node<T>* cur = head;
  for(int i = 0; i < index; i++) {
    cur = cur->next;
  }
  return(cur->data);
}

1 Ответ

1 голос
/ 15 апреля 2019

У вас есть правильная идея использовать static переменную-член для отслеживания идентификаторов. Но вы не можете использовать только , что.

Переменная-член static является членом класса а не какой-то конкретный объект.Поэтому все объекты имеют один и тот же id.

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

Что-то вроде 

class TrainCar {
public:
    static int next_id;  // Used to get the id for the next object
    int id;  // The objects own id
    ...
};

TrainCar::TrainCar() {
    id = next_id++;  // Get next id and save it
    ...
}

Вероятно, у вас также должны быть операторы копирования и конструирования, иначе вы можете получить два объекта с одинаковымid.

Относительно

Почему значения id так высоки и почему они увеличиваются более чем на один раз?

Это потому, что вы, вероятно, создаете больше объектов, чем ожидаете.С помощью показанного вами кода, а также с предложенным выше изменением вы создадите новый идентификатор для каждого объекта, созданного по умолчанию.И в зависимости от того, что делает ваш шаблонный класс LinkedList (почему бы вам не использовать std::vector), могут быть созданы новые объекты.

Обоснованное предположение состоит в том, что функция Retreive вашего списка классаdefault создает объект, который в нем содержится.Вот почему вы получаете три объекта при печати, как вы вызываете Retrieve три раза.Возможно, похожая история о ваших Add функциях.

...