Двусвязный Список Реализации [С++]


C++ в отчетности нуб. Я работаю на реализации двусвязный список с использованием двух отдельных классах: один класс, называется node, содержащие стандартные двусвязный список параметров, и другого класса, называется dList, который содержит функции, чтобы изменить мою двусвязный список. Вот мой node класс:

class node {
  public:
    node *prev;
    node *next;
    int key;
    char type;
};

и вот мой dList класс:

class dList {
  private:
    node *head; // dummy head
    node *tail; // dummy tail

  public:
    dList() { // default constructor, creates empty list
      cout << "in default constructor" << endl; // to debug
      head = nullptr;
      tail = nullptr;
    }
    // destructor
    ~dList() {
      cout << "in destructor" << endl; // to debug
      node *ptr = head;
      while (ptr != nullptr) {
        delete ptr;
        ptr = ptr->next;
      }
      tail = nullptr;
    }

    // searches list for occurence of int parameter and returns pointer to node containing key
    node *search(int k);

    // outputs all keys that have type equal to character parameter, front to back
    void find(char t);

    // parametrized constructor, initialize list w/ contents of arrays
    dList(int arrayNums[], char arrayChars[], int size);

    // creates new node at front of list
    void addFront(int k, char t);

    // creates new node at back of list
    void addBack(int k, char t);

    // moves node pointed to by parameter to front of list
    void moveFront(node* ptr);

    // moves node pointed to by parameter to back of list
    void moveBack(node* ptr);

    // outputs first int elements of list, starting at front or back depending on char parameter
    void out(int num, char = 'f');

    // splits list in two
    node *split(node* headRef);

    // merges two linked lists
    node *mergeLists(node* first, node* second);

    // performs mergeSort on linked list
    node *mergeSort(node* headRef);

    // peforms an O(NlogN) sort on list; list should be in increasing order based on integer key
    void sort();
};

У меня все мои функциями разобрался, кроме sort() функция и все функции связанные с ней (split, mergeLists, mergeSort). Я в основном ищу критики и усовершенствования. Если вы могли бы взглянуть на мой код и помочь мне оптимизировать его (конденсации и удаления ненужных линий), а также помочь мне убедиться, что я правильно используя указатели, это будет высоко ценится!

Ниже мои заявленных функций (за исключением sort связанные с):

// parametrized constructor, initialize list w/ contents of arrays
dList::dList(int arrayNums[], char arrayChars[], int size) {
  node *newNode = nullptr;
  //cout << "parametrized constructor called" << endl;
  for (int i = 0; i < size; i++) {
    //cout << "in for loop" << endl;
    if (head == nullptr) {
      //cout << "in first if statement" << endl;
      newNode = new node;
      newNode->key = arrayNums[i];
      newNode->type = arrayChars[i];
      newNode->prev = nullptr;
      newNode->next = nullptr;
      head = newNode;
      tail = head;
    }

    else {
      //cout << "in else statement" << endl;
      newNode = new node;
      newNode->key = arrayNums[i];
      newNode->type = arrayChars[i];
      newNode->prev = tail;
      tail->next = newNode;
      tail = newNode;
    }
  }
}

void dList::addFront(int k, char t) { // creates new node at front of list
  node *newNode = new node;
  newNode->key = k;
  newNode->type = t;

  if (head != nullptr) {
    newNode->next = head;
    head->prev = newNode;
    head = newNode;
  }
  else {
    newNode->prev = nullptr;
    newNode->next = nullptr;
    head = newNode;
    tail = nullptr;
  }
}

void dList::addBack(int k, char t) { // creates new node at back of list
  node *newNode = new node;
  newNode->key = k;
  newNode->type = t;

  node *ptr = head;

  if (ptr != nullptr) {
    while (ptr->next != nullptr) {
      ptr = ptr->next;
    }
    ptr->next = newNode;
    newNode->next = nullptr;
    newNode->prev = ptr;
  }
  else {
    newNode->next = nullptr;
    newNode->prev = nullptr;
    ptr = newNode;
    tail = ptr;
  }
}

void dList::moveFront(node *ptr) { // moves node pointed to by parameter to front of list
  //node *tempHead = head;
  //node *tempTail = tail;

  if (ptr == head) {
    return;
  }
  else if (ptr == tail) {
    ptr->prev->next = nullptr;
    tail = ptr->prev;
  }
  else {
    ptr->prev->next = ptr->next;
    ptr->next->prev = ptr->prev;
  }

  head->prev = ptr;
  ptr->next = head;
  ptr->prev = nullptr;
  head = ptr;
}

void dList::moveBack(node *ptr) { // moves node pointed to by parameter to back of list
  //node *tempHead = head;
  //node *tempTail = tail;

  if (ptr == tail) {
    return;
  }
  else if (ptr == head) {
    head = ptr->next;
    tail->next = ptr;
    ptr->prev = tail;
    ptr->next = nullptr;
    tail = ptr;
  }
  else {
    ptr->prev->next = ptr->next;
    ptr->next->prev = ptr->prev;
    tail->next = ptr;
    ptr->prev = tail;
    tail = ptr;
  }
}
// searches list for occurence of int parameter and returns pointer to node containing key
node *dList::search(int k) {
  node *ptr = head;
  while (ptr->next != nullptr) {
    if (ptr->key == k) {
      return ptr;
    }
    else {
      ptr = ptr->next;
    }
  }

  return nullptr;
}
// outputs all keys that have type equal to character parameter, front to back
void dList::find(char t) {
  node *ptr = head;
  while (ptr->next != nullptr) {
    if (ptr->type == t) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->next;
    }
    else {
      ptr = ptr->next;
    }
  }
}
// outputs first num elements of list, starting at front or back depending on char parameter
void dList::out(int num, char side) {
  cout << "out() called" << endl;
  if (side == 'b') {
    node *ptr = tail;
    for (int i = 0; i < num; i++) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->prev;
    }
  }
  else {
    node *ptr = head;
    for (int i = 0; i < num; i++) {
      cout << ptr->key << " " << ptr->type << "   ";
      ptr = ptr->next;
    }
  }
}

И вот мой файл main.cpp я использую для проверки:

#include <iostream>
using namespace std;
#include "dList.cpp"
#define SMALL 200
#define MAX 100000
#define ROUNDS 100
int main(){
    int i, x[MAX];
    char ch[MAX];

    for(i=0;i<SMALL;i++) {
      x[i] = (2*SMALL)-i;
      ch[i] = 'a' + (i % 26);
    }
    dList A(x,ch,SMALL), B;
    A.out(10);
    node *tmp = A.search(2*SMALL-8);
    A.moveFront(tmp);
    A.out(10);
    A.moveBack(tmp);
    A.out(10);
    A.find('b');
    A.sort();
    A.out(10);
    A.out(10,'b');
    A.addBack(500,'d');
    A.addFront(501,'z');
    A.out(10);
    A.out(10,'b');
    B.addFront(1,'a');
    B.addBack(2,'b');
    B.out(2);

    for(int j=0; j<ROUNDS; j++){
      cout << endl << "round " << j << endl;
      for(i=0;i<MAX;i++) {x[i] = 2*MAX-i; ch[i] = 'a'+ (i%26);}
      dList A(x,ch,MAX);
      node *tmp = A.search(2*MAX-8);
      A.moveFront(tmp);
      A.moveBack(tmp);
      A.sort();
      A.out(10);
      A.out(10,'b');
    }
}

(В качестве бонуса, если вы могли бы дать мне советы о том, как реализовать сортировка слиянием для двусвязный список, я люблю его!)

Спасибо вам!



Комментарии
3 ответа

Просто короткий запустить на рассмотрении:


  1. Вы нарушаете правила-три / правило пяти:

    dList()
    ~dList()

    Вы, по крайней мере, отсутствует:

    dlist(const dlist&)
    dlist& operator=(const dlist&)

    По умолчанию предусмотрено стандартной смертельно неправильно.

    Хотя предполагаю, по крайней мере в C++11 вы хотите:

    dlist(dlist&&)
    dlist& operator=(dlist&&)

  2. Престижность для удаления узлов в dtor итерационно вместо recusively. Но тогда вы совершите использования после освобождения преступление. Исправить, что, прочитав указатель на следующий узел перед освободив узел. Кроме того, нет смысла красить стены только до сноса дома.

Я не просмотрев остальные ваши интерфейса и реализации, помимо сказав, что это, кажется, очень дырявой абстракцией. Может, поработать над этим?

2
ответ дан 6 марта 2018 в 05:03 Источник Поделиться

Дизайн

Я бы поставил Node внутри dList как отдельный класс. Его деталь реализации, что никто не должен знать не только свой класс.

Я хотел бы посмотреть, как использовать объект Сентинел. Страж фальшивый объект в свой список, который действительно упрощает код, как вы никогда не иметь дело с головы/хвоста быть null. Взгляните на это: https://codereview.stackexchange.com/a/126007/507

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

Соглашения об именовании. Это более традиционные для использования прописной первую букву для пользовательских типов. Затем строчных букв для функции и объекты.

  Node(12, 'k');       // Uppercase letter therefore type.
// This is creating an object.

node(12, 'k'); // lowercase letter therefore function
// This is calling a function

Комментарий Код

Правило трех

Ты не выполнил Правило 3 (или пять).

{
dList x;
x.addBack(12, 'g');

dList y(x); // Woops shallow copy of x made
// Even though you did not define the copy constructor
}
// BOOM. Code blows up because of double delete on the same pointer.

Если вы определили конструктор копирования/оператор присваивания или деструктор, то вы, вероятно, следует определить все три.

Доступ через удаленные указатель

  while (ptr != nullptr) {
delete ptr;
ptr = ptr->next; // You just deleted ptr
// This is no longer yours to access and doing
// so is UB (the whole page may have been released
// back to the OS resulting in a page fault.

// Looking from a real world perspective the delete
// adds this block back to the memory management
// library and could easily overwrite parts of the
// block in the processes. So what you read here
// is potentially garbage.
}

Сухой код

Много этот код повторяется на обеих сторонах, если заявление. Почему не удалить дублирование кода, так случается в первую очередь?

if (head == nullptr) {
//cout << "in first if statement" << endl;
newNode = new node;
newNode->key = arrayNums[i];
newNode->type = arrayChars[i];
newNode->prev = nullptr;
newNode->next = nullptr;
head = newNode;
tail = head;
}

else {
//cout << "in else statement" << endl;
newNode = new node;
newNode->key = arrayNums[i];
newNode->type = arrayChars[i];
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}

Упростить код.

  node *newNode = new node;
newNode->key = k;
newNode->type = t;

Проще написать так:

    node* newNode = new node {nullptr, nullptr, k, t};

Печать

Нормальный способ печати в C++ использовать operator<<.

std::cout << 5 << "\n";

Вы можете реализовать это для своего класса путем определения этого оператора.

std::ostream& operator<<(std::ostream& s, dlist const& object)
{
object.print(s); // simplest way to ask object to print itself
// to the stream (pass the stream).
return s;
}

2
ответ дан 6 марта 2018 в 05:03 Источник Поделиться

Я согласен с тем, что говорили другие, но вот некоторые дополнительные замечания.


  1. Использование инициализации по умолчанию, когда это возможно

    class node {
    public:
    node *prev = nullptr;
    node *next = nullptr;
    int key;
    char type;
    };

  2. Предоставить конструктор для вашего класса узел, который передает ключ и тип

    class node {
    public:
    node(int Key, char Type)
    : key(Key)
    , type(Type)
    {}

    node *prev = nullptr;
    node *next = nullptr;
    int key;
    char type;
    };

    Давайте посмотрим на то, как это влияет на вас вспомогательные функции addFront первый

    void dList::addFront(int k, char t) { // creates new node at front of list
    node *newNode = new node(k, t);
    newNode->next = head;
    if (head != nullptr) {
    head->prev = newNode;
    }
    head = newNode;

    // If your list was constructed with empty arrays you need to set tail too
    if (tail == nullptr) {
    tail = newNode;
    }
    }

    Есть ли причины обход списка в addBack когда у вас есть указатель на хвост?

    void dList::addBack(int k, char t) { // creates new node at front of list
    // If there is no head create a shortcut to addFront
    if (head == nullptr) {
    addFront(k,t);
    }

    node *newNode = new node(k, t);
    tail->next = newNode
    newNode->prev = tail;
    tail = newNode;
    }


  3. Больше личные предпочтения, но я бы предпочел использовать структуру, отдельный список, чем полностью непрозрачный класса, но все.

  4. Вы вопрос помечен на C++, однако вы можете использовать простой c-массивы в конструкторе dList(int arrayNums[], char arrayChars[], int size);. Здесь std::vector было бы лучше. Также подумайте о том, что происходит, когда один из массивов меньше, чем размер?

    dList::dList(const std::vector<int>& arrayNums, const std::vector<char>& arrayChars) {
    if (arrayNums.size() != arrayChars.size()) {
    //Do something here, e.g. throw an exception or whatever you want
    }

    for (std::size_t i = 0; i < arrayNums.size(); ++i) {
    addBack(arrayNums[i], arrayChars[i]);
    }
    }


1
ответ дан 7 марта 2018 в 10:03 Источник Поделиться