Лучше использовать обоснованный список или нет? - PullRequest
Новая
       9

Лучше использовать обоснованный список или нет?

0 голосов
/ 07 февраля 2012

Я учусь в университете Колорадо Меса. Начальник отдела преподает обоснованный метод для связанных списков: 

struct nodeType
{
    int id;
    nodeType *link;
};

void createList(nodeType *&head, nodetype *&tail)
{
    head = new nodetype;
    tail = new nodetype;
    head->id=-1; //some initialize value
    head->link=tail;
    tail->link=NULL;
}

void insertList(nodeType *&head, nodeType *&tail)
{
    nodetype *knew,*prior, *next;
    knew = new nodetype;

    knew ->name = name

    prior = head;
    next = head->link;
    while(next != tail && knew->id > next->id)
    {
        prior = next;
        next = next->link;
    }

    prior->link = knew;
    knew->link = next;
}

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

Мой профессор алгоритмов говорит, что везде, где я сталкиваюсь со списками «в реальном мире», необоснованный список был бы лучше. На других языках, использующих STL и в Интернете, я не нашел бы список функций, которые реализуют голову и хвост.

Я просто хочу быть готовым к программированию в реальном реальном мире, а не в том, что мои профессора считают реальным миром, поэтому мой вопрос таков: лучше ли использовать один или другой, использовать то, что мне легче, или подходить к каждой проблеме с учетом обоих?

Заранее спасибо за то, что уделили мне время для разрешения этой вражды.

1 Ответ

0 голосов
/ 07 февраля 2012

В «реальном мире» вы будете использовать список, который другие программисты разработали, внедрили, оптимизировали и протестировали, и вы никогда не узнаете, является ли он «обоснованным», поскольку это всего лишь деталь реализации.

Что важно отнять у ваших курсов алгоритмов:

  • Характеристики производительности.Есть ли у связанного списка или вектора более быстрый произвольный доступ?Быстрее добавить?Ускорение удаления первого элемента?Использование правильного контейнера НЕ является преждевременной оптимизацией.

  • Просмотр достаточного количества различных стилей реализации, так что если вам когда-нибудь придется перебирать свой код с помощью отладчика, вы не будете по-королевски запутаны.Если вы увидели, что тест в конце списка возвращает true, но указатель следующего узла не равен NULL, вы, вероятно, будете в замешательстве, если никогда раньше не видели «обоснованную» реализацию списка.

...