Удалить дубликаты в связанном списке перед добавлением - C

Question

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

struct myStr{int number; mystr *next;}
void append(mystr **q,int item)
{
myStr *temp;
temp = *q;
myStr *newone;
if(*q==NULL)// There should be control of previous elements. Call of keysearch function.
     {   temp = (myStr *)malloc(sizeof(myStr));

          temp->number =size;
          temp->next=NULL;
          *q=temp;
     }
     else //And also here
     {  temp = *q;
         while(temp->next !=NULL)
         {  temp=temp->next;
         }
         newone = (myStr *)malloc(sizeof(myStr));
         newone->count = size;
         newone->next=NULL;
         temp->next=newone;

     }
}
int keysearch (myStr *p)
{
struct myStr *temp = p;
int found = 0;
int key= p->number;
while (temp->next != NULL) 
 {
 if(temp->number == key)
    {
   return 1;
//break;
        }
     temp = temp->next;   
     }
    return 0;
    }

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

Answer 1

Что вы подразумеваете под "его неправильно"?

Кроме этого:

Во-первых. temp-> number является целым числом, и вы можете проверить наличие следующего указателя в вашем операторе while.

Во-вторых. если вы назначите temp = p и введете значение p-> number, то проверка в цикле while всегда будет истинной для первой итерации.

В-третьих. Это может привести к сбою, если временная переменная недопустима в вашем операторе while.

Answer 2

В вашем коде у вас есть 2 комментария, где вы ожидаете вызова keySearch. На самом деле это нужно только в 1 месте - второй комментарий. Это потому, что первое место - это то, где вы создаете новый список, поэтому, конечно, в нем не будет ничего, о чем вам нужно беспокоиться.

Во втором случае вы хотите вызвать этот keySearch метод. Есть 3 типа keySearch методов, которые, я думаю, будут полезны:

1. Вызвать метод int keySearch(mystr *p, int value), который просматривает p для value и, если найден, возвращает true (ненулевое число)
2. Вызовите метод int keySearch(mystr *p), который просматривает p на наличие дубликатов и удаляет их. Это не будет вызываться при каждом добавлении, и приведенная выше реализация предполагает, что это не то, что вы пытаетесь сделать. В любом случае, для этого нужно сделать намного больше.
3. Вызовите метод int keySearch(mystr *p), который просматривает p, чтобы увидеть, дублируется ли первое значение в q, и возвращает true, если оно есть. Похоже, именно это пытается сделать ваш метод.

Основываясь на сигнатуре метода, вы пытаетесь сделать # 2 или # 3. Но оба они ошибочны - они предполагают, что вы уже добавили дубликат в список. Вместо этого вы должны попытаться предотвратить добавление дубликата. Однако сам по себе метод не обладает достаточной информацией для этого. Требуется значение элемента, который еще не был добавлен.

Я бы предложил изменить метод на метод № 1 и передать значение, которое вы хотите добавить. Если он найден, верните 1. В методе append, если эта функция имеет значение 1, ничего не добавляйте. В противном случае добавьте новый элемент.

int keysearch(struct myStr *p, int value)
{
   if(p == NULL) return 0;
   // reusing p is fine - it's a local variable
   while(p != NULL)
   {
      if(p->number == value) return 1;  // return if value exists already
      p = p->next;                      // go to next element
   }
   return 0;
}

Теперь, когда вы собираетесь добавить элемент, сначала запустите его этим методом. Если метод возвращает 1, немедленно оставьте свой метод append - ничего не поделаешь. Если он возвращает 0, тогда malloc ваш новый узел и установите его в конец списка.

---

РЕДАКТИРОВАТЬ : Предприимчивый кузнец может захотеть немного оптимизировать, чтобы на каждом append мы не делали 2 цикла по всему списку (один для keySearch, а затем один, чтобы найти последний элемент для фактического добавления). Вы можете сделать это, слегка изменив keySearch ...

// returns NULL if p is empty / value exists; otherwise returns the last element
struct myStr *keysearch(struct myStr *p, int value)
{
   // same logic, different return values; integration into append changes too!
}

Answer 3

Это выглядит довольно сомнительно:

 if(temp->number == key)
    {
   found = 1;
    }
 temp = temp->next;   
 }
return found;
}

Почему бы не просто return 1, как только tmp->number == key? Нет смысла продолжать цикл (или, по крайней мере, оставшаяся часть кода, который вы вставили, не показывает причины), как только найдено совпадение.

Другое дело, я думаю, вы хотите протестировать while (temp->next != NULL) вместо сравнения целого с NULL, особенно перед присвоением temp temp->next.

Вы также захотите использовать что-то более похожее на:

int keysearch (myStr *p, int key)

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