我正在尝试编写一个函数来清理该代码生成的哈希表
/*
* Markov chain random text generator.
*/
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "eprintf.h"
enum {
NPREF = 2, /* number of prefix words */
NHASH = 4093, /* size of state hash table array */
MAXGEN = 10000 /* maximum words generated */
};
typedef struct State State;
typedef struct Suffix Suffix;
struct State { /* prefix + suffix list */
char* pref[NPREF]; /* prefix words */
Suffix* suf; /* list of suffixes */
State* next; /* next in hash table */
};
struct Suffix { /* list of suffixes */
char* word; /* suffix */
Suffix* next; /* next in list of suffixes */
};
State* lookup(char *prefix[], int create);
void build(char *prefix[], FILE*);
void generate(int nwords);
void add(char *prefix[], char *word);
State* statetab[NHASH]; /* hash table of states */
char NONWORD[] = "n"; /* cannot appear as real word */
/* markov main: markov-chain random text generation */
int main(void)
{
int i, nwords = MAXGEN;
char *prefix[NPREF]; /* current input prefix */
int c;
long seed;
setProgName("markov");
seed = time(NULL);
srand(seed);
for (i = 0; i < NPREF; i++) /* set up initial prefix */
prefix[i] = NONWORD;
build(prefix, stdin);
add(prefix, NONWORD);
generate(nwords);
return 0;
}
const int MULTIPLIER = 31; /* for hash() */
/* hash: compute hash value for array of NPREF strings */
unsigned int hash(char* s[NPREF])
{
unsigned int h;
unsigned char *p;
int i;
h = 0;
for (i = 0; i < NPREF; i++)
for (p = (unsigned char *) s[i]; *p != ' '; p++)
h = MULTIPLIER * h + *p;
return h % NHASH;
}
/* lookup: search for prefix; create if requested. */
/* returns pointer if present or created; NULL if not. */
/* creation doesn't strdup so strings mustn't change later. */
State* lookup(char *prefix[NPREF], int create)
{
int i, h;
State *sp;
h = hash(prefix);
for (sp = statetab[h]; sp != NULL; sp = sp->next) {
for (i = 0; i < NPREF; i++)
if (strcmp(prefix[i], sp->pref[i]) != 0)
break;
if (i == NPREF) /* found it */
return sp;
}
if (create) {
sp = (State *) emalloc(sizeof(State));
for (i = 0; i < NPREF; i++)
sp->pref[i] = prefix[i];
sp->suf = NULL;
sp->next = statetab[h];
statetab[h] = sp;
}
return sp;
}
/* addsuffix: add to state. suffix must not change later */
void addsuffix(State *sp, char *suffix)
{
Suffix *suf;
suf = (Suffix *) emalloc(sizeof(Suffix));
suf->word = suffix;
suf->next = sp->suf;
sp->suf = suf;
}
/* add: add word to suffix list, update prefix */
void add(char *prefix[NPREF], char *suffix)
{
State *sp;
sp = lookup(prefix, 1); /* create if not found */
addsuffix(sp, suffix);
/* move the words down the prefix */
memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
prefix[NPREF-1] = suffix;
}
/* build: read input, build prefix table */
void build(char *prefix[NPREF], FILE *f)
{
char buf[100], fmt[10];
/* create a format string; %s could overflow buf */
sprintf(fmt, "%%%ds", sizeof(buf)-1);
while (fscanf(f, fmt, buf) != EOF)
add(prefix, estrdup(buf));
}
/* generate: produce output, one word per line */
void generate(int nwords)
{
State *sp;
Suffix *suf;
char *prefix[NPREF], *w;
int i, nmatch;
for (i = 0; i < NPREF; i++) /* reset initial prefix */
prefix[i] = NONWORD;
for (i = 0; i < nwords; i++) {
sp = lookup(prefix, 0);
if (sp == NULL)
eprintf("internal error: lookup failed");
nmatch = 0;
for (suf = sp->suf; suf != NULL; suf = suf->next)
if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
w = suf->word;
if (nmatch == 0)
eprintf("internal error: no suffix %d %s", i, prefix[0]);
if (strcmp(w, NONWORD) == 0)
break;
printf("%sn", w);
memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
prefix[NPREF-1] = w;
}
}
这是我到目前为止的清洁功能
/*Clean Function*/
void clean_up(State *sp)
{
State *temp;
Suffix *temp2, temp3;
for(int h = 0; h < NHASH; h++)
{
for (sp = statetab[h]; sp != NULL; sp = sp->next)
{
while(sp->suf != NULL)
{
temp2= sp->suf;
temp3= *temp2->next;
free(temp2);
sp->suf= &temp3;
}
}
}
}
我认为我在正确的轨道上，我要浏览哈希表中的每个索引，然后从状态到状态并释放后缀。我不确定该如何处理前缀，因为我必须在释放每个状态之前释放它们。任何帮助将不胜感激。
在您的代码中，您正在复制到一个temp3节点，该节点生活在自动内存（"堆栈"）中，将sp-> suf指向此内存（在下一次迭代中循环）使该对象的地址免费调用（该对象的地址不是由Malloc获得的，因此无法通过Free（））
释放。void clean_up(State *sp)
{
State *temp;
Suffix *temp2, **pp;
for(int h = 0; h < NHASH; h++)
{
for (sp = statetab[h]; sp != NULL; sp = sp->next)
{
for (pp = &sp->suf; *pp; *pp = temp2)
{
temp2 = (*pp)->next;
free(*pp);
}
}
}
}
示例代码是由马尔可夫程序派生的，在编程的实践中，克尼原和派克（一本最出色的书）。
鉴于您正在尝试清理statetab，因此主要的清理功能不需要任何参数。您必须小心不要直接在statetab中释放状态，但是您确实需要释放statetab[i].next链接的辅助状态。
typedef struct State State;
typedef struct Suffix Suffix;
struct State { /* prefix + suffix list */
char* pref[NPREF]; /* prefix words */
Suffix* suf; /* list of suffixes */
State* next; /* next in hash table */
};
struct Suffix { /* list of suffixes */
char* word; /* suffix */
Suffix* next; /* next in list of suffixes */
};
State* statetab[NHASH]; /* hash table of states */
static void free_state(State *state);
static void free_suffix(Suffix *suffix);
static void cleanup(void)
{
for (int i = 0; i < NHASH; i++)
free_state(statetab[i]);
}
static void free_state(State *state)
{
if (state != 0)
{
for (int i = 0; i < NPREF; i++)
free(state->pref[i]);
free_suffix(state->suf);
if (state->next != 0)
{
free_state(state->next);
free(state->next);
}
}
}
static void free_suffix(Suffix *suffix)
{
if (suffix != 0)
{
free(suffix->word);
free_suffix(suffix->next);
free(suffix);
}
}
您是否看到我如何根据xxxx结构的设计设计free_xxxx()代码？
警告Lector ：未编译的代码，测试的代码少。
我从TPOP站点挖掘了代码，并尝试将其应用。我对上面的免费代码进行了一些修复（语法错误已修复，在free_state()和free_suffix()中进行了null检查），但整个代码并非旨在允许释放数据。
有几个问题。首先，一些前缀未分配（非单词）。有可能通过测试前缀是否是非单词来避免释放这些内容的，但这很讨厌。也可能也可以分配这些前缀（estrdup(NONWORD)替换非单词）。我认为在某个地方还有另一个地方，一个未分配的指针被藏在状态表的前缀中。我在malloc()中崩溃，抱怨"释放非分配内存"（我相信这与"双重释放分配的内存"不同），但是我尚未设法解决。
但是，这会改变到另一个问题。前缀是重复使用的。也就是说，系统中几乎每个前缀都用作一个前缀的第二个单词，然后用作下一个前缀的第一个单词。因此，您不能轻易释放前缀。
如果您要设计它以便可以发布内存，那么您可能会设计它，以便有一个"原子"（不变的字符串）系统，使每个单词一次分配一次，并像必要的（请参阅C接口和实现：D Hanson为术语来源创建可重复使用的代码的技术）。然后，释放状态表的代码将仅集中在非单词数据上。还会有代码发布完整的原子集。
我在valgrind下运行了Markov计划，而无需清理；没有内存访问问题，也没有泄漏的数据；在程序退出时，所有这些都仍然可以访问。我正在使用大约15,000个单词（约有2900个不同单词）的数据文件，统计数据为：
==9610== HEAP SUMMARY:
==9610== in use at exit: 695,269 bytes in 39,567 blocks
==9610== total heap usage: 39,567 allocs, 0 frees, 695,269 bytes allocated
==9610==
==9610== LEAK SUMMARY:
==9610== definitely lost: 0 bytes in 0 blocks
==9610== indirectly lost: 0 bytes in 0 blocks
==9610== possibly lost: 0 bytes in 0 blocks
==9610== still reachable: 695,269 bytes in 39,567 blocks
所以，您为自己设定了一个有趣的练习。但是，我认为如果不重新处理某些内存分配机制，以便可以清晰释放数据是无法实现的。
（在BSD上，因此在Mac OS X上，<stdlib.h>中有一对函数称为setprogname()和getprogname()。在BSD上，setprogname()在main()进行之前自动称为（我相信argv[0]）。声明。在eprintf.h与<stdlib.h>中的声明发生冲突中，这可能就是为什么问题中的代码使用setProgName()而不是原始setprogname()。我选择在eprintf.h中修复setprogname()，以便进行const char *参数，从而匹配<stdlib.h>中的声明。）<<）<）<）。/p>
tpop以前在http://plan9.bell-labs.com/cm/cs/tpop和http://cm.bell-labs.com/cm/cm/cs/tpop现在（2015-08-10）破裂。另请参见TPOP上的Wikipedia。