Нажатие на стек, содержащий ТОЛЬКО уникальные значения в C

Question

Я реализовал стек с указателями, который работает так, как предполагается. Теперь мне нужно, чтобы он нажимал на стек, не нажимая дубликат. Например, если я нажимаю «2» в стек, нажатие другого «2» по-прежнему будет иметь только один «2» в стеке, поскольку он уже существует.

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

typedef struct Node { 
     void *content; 
     struct Node *next; 
    } Node; 

    typedef struct Stack { 
     Node *head; 
     int count; 
    } Stack; 

    void push(Stack *stack, void *newElem) { 
     Node *newNode = (Node*) malloc(sizeof(Node)); 
     if (stack->count > 0) { 
      int i; 
      for (i = 0, newNode = stack->head; i < stack->count; i++, newNode = 
       newNode->next) { 
        if (newNode->content == newElem) return; 
      } 
     } else { 
      newNode->next = stack->head; 
      newNode->content = newElem; 
      stack->head = newNode; 
      stack->count++; 
     } 
    } 

Answer 1

У вас уже есть рабочая

void push(Stack *stack, void *newElem); 

правильно?

Итак, почему бы не написать новую функцию

int push_unique(Stack *stack, void *newElem) { 
    if (find_value(stack, newElem) != NULL) { 
     return 1; // indicate a collision 
    } 
    push(stack, newElem); // re-use old function 
    return 0; // indicate success 
} 

Теперь вы свели задачу к написанию

Node *find_value(Stack *stack, void *value); 

... Вы можете сделать это?

Answer 2

if (newNode->content == newElem) 

Вы сравниваете два указатели. Я предполагаю, что вы хотите проверить, является ли их содержание равно:

#include <string.h> 

if (memcmp(newNode->content, newElem, size) == 0) 

Значения size может быть указан абонентом. В вашем случае это должно быть sizeof(int).

Кроме того, как только вы пройдете стек, вы не добавите элемент в свою структуру данных.

Answer 3

Проблема заключается в том, что если ваш стек не пуст, а вы не найдите элемент, уже находящийся в стеке, вы ничего не делаете. Вам нужно избавиться от ключевого слова else и сделать этот код безусловным. Затем вы выделяете место для нового узла, прежде чем знаете, если вам это нужно или нет, и, что еще хуже, перезапишите вновь выделенный указатель с вашей итерацией по стеку, чтобы увидеть, нужно ли его нажимать или нет. Так переместить таНос вниз после } Концовка if

Answer 4

Я не уверен, что вы это осознали, но предлагаемая реализация выполняет линейный поиск по связанному списку. Если вы нажимаете 2000 элементов в стеке со средним количеством двух дубликатов каждого значения элемента, это 2 000 поисков связанного списка в среднем между 500-750 ссылками (это зависит от того, когда IE: какой порядок, дубликаты представлены функция поиска в. Для этого требуется 1 млн. + Сравнение. Не очень.

МНОГО более эффективное обнаружение дубликатов в find_value() выше может использовать хеш-таблицу со временем поиска O (1) или деревом со временем поиска O (log N). Первый, если вы знаете, сколько значений вы потенциально нажимаете на стек, а второе, если число неизвестно, например, при получении данных из сокета в режиме реального времени. (Если бы вы могли реализовать ваш стек в массиве вместо гораздо более медленного и более подробного связанного списка)

В любом случае case, чтобы правильно поддерживать хеш-таблицу, ваша функция pop() должна быть сопряжена с функцией hashpop() хэш-таблицы, которая удаляет соответствующее значение из хеш-таблицы.

С помощью Hashtable ваш стек может указывать на значение элемента, сидящего в его хэш-местоположении, - возвращается из find_value(). Однако с помощью дерева с балансировкой местоположение узла и, следовательно, значение элемента будет меняться все время, поэтому вам нужно будет сохранить значение элемента в стеке и дерево. Если вы не пишете в очень плотной среде памяти, производительность, которую могла бы обеспечить вторая структура данных, стоила бы скромной стоимости в памяти.