#c #pointers #hashtable
#c #указатели #хэш-таблица
Вопрос:
Вот мой код,
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct DF
{
char str[101];
int D;
struct DF *next;
} DF;
DF *df[5];
int hash (char str[])
{
int sum=0, len=strlen (str);
for (int x=0; x<len; x ) sum =str[x];
return sum%5;
}
DF* ND (char str[])
{
DF *node=(DF*) malloc (sizeof (DF));
strcpy (node->str, str); node->D=1;
node->next=NULL;
return node;
}
void add (char str[])
{
int idx=hash (str);
if (df[idx])
{
DF *temp=df[idx];
while (temp) temp=temp->next;
temp=ND (str);
}
else df[idx]=ND (str);
}
int main (void)
{
char str1[]="The"; add (str1);
char str2[]="App"; add (str2);
if (df[4])
{
printf ("[4] %s", df[4]->str);
DF *temp=df[4]->next;
while (temp)
{
printf (" -> %s", temp->str);
temp=temp->next;
}
puts ("");
}
return 0;
}
Пожалуйста, обратите внимание на void add (char[])
, почему вывод не [4] The -> App
? Даже когда я изменил DF *temp=df[idx];
на DF *temp=df[idx]->next;
, это не имеет значения. Но если я изменю его, функция станет такой,
void add (char str[])
{
int idx=hash (str);
if (df[idx])
{
DF *temp=df[idx];
while (temp->next) temp=temp->next;
temp->next=ND (str);
}
else df[idx]=ND (str);
}
Он выводится [4] The -> App
. Итак, в чем разница между этими двумя алгоритмами?
Комментарии:
1. Лично мне очень трудно понять / прочитать ваш код. Не могли бы вы добавить несколько строк комментариев, чтобы другие люди знали, что должна делать программа?
2. @BlayerBond это не нужно, достаточно прочитать код, чтобы увидеть проблему
3. @бруно, чтобы быть уверенным, что я решаю правильную проблему, было бы неплохо узнать, что такое
DF
(dataframe?),D
(data?) иND
(new data?), не просматривая для этого весь код, но, возможно, это просто потому, что я сам не создавал хэш-таблицу на C :/4. @BlayerBond Я согласен, что поле D неясно / бесполезно, потому что установлено только в 1. В остальном да, реализовать хэш-таблицу — хорошее упражнение, и есть много способов сделать это (например, когда элементов слишком много, массив списка синонимов может увеличиваться, производя перефразирование)
5. Когда мы делаем,
int i = 4; int j = i; j = j 1;
этоi
4 или 5?
Ответ №1:
первым способом :
temp=ND (str);
просто назначьте локальную переменную, чтобы она не оказывала влияния за пределами функции из-за того, что у вас утечка памяти (но список не изменен, элемент не добавлен)
но вторым способом :
temp->next=ND (str);
изменяет связанный список
Для работы вы можете изменить первый способ сделать :
void add (char str[])
{
int idx=hash (str);
if (df[idx])
{
DF **temp=amp;df[idx];
while (*temp) temp=amp;(*temp)->next;
*temp=ND (str);
}
else df[idx]=ND (str);
}
но это ни для чего не сложно, за исключением того, что вы хотите удалить if
:
void add (char str[])
{
DF ** temp=amp;df[hash(str)];
while (*temp)
temp=amp;(*temp)->next;
*temp=ND (str);
}
Примечание добавлять новую ячейку в конец списка синонимов бесполезно, у вас нет глобального порядка, вы можете напрямую сделать :
void add (char str[])
{
DF * temp=ND (str);
int idx=hash (str);
temp->next = df[idx];
df[idx] = temp;
}
В ND :
strcpy (node->str, str); node->D=1;
опасно, потому что str может быть слишком длинным для сохранения в node->str
, вы можете использовать strncpy
Напротив, когда строка для сохранения маленькая, вы потеряли память.
Как насчет того, чтобы использовать не массив для поля str, а char*
а strdup
и дублировать строку (к примеру)?
В хэше вы просматриваете строку два раза, вам не нужно вычислять strlen и можете использовать
for (int x=0; str[x] != 0; x ) sum =str[x];
Комментарии:
1. Можете ли вы объяснить утечку памяти, о которой вы говорите?
2. Итак,
temp->next=ND (str)
изменяет связанный список, потому что он указывает наnext
, я прав? Потому что это то же самое, что(*temp).next=ND (str)
верно?3. @LastSecond959 temp если значение NULL не получено из предыдущего добавления, поэтому
temp->next=ND (str)
изменяет поле рядом со старой ячейкой. Да,temp->
и(*temp).
идентичны, первый является сокращением второго