0

我正在尝试编写一个霍夫曼编码程序来压缩文本文件。完成后,程序将在 return 语句处终止,或者当我尝试关闭正在读取的文件时。我假设我有内存泄漏,但我找不到它们。如果你能发现它们,请告诉我(以及修复它们的方法将不胜感激!)。

(注意:small1.txt 是任何标准文本文件)

这是主程序

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define ASCII 255

struct link {
 int freq;
 char ch[ASCII];
 struct link* right;
 struct link* left;
};

typedef struct link node;
typedef char * string;
FILE * ofp;
FILE * ifp;
int writebit(unsigned char);
void sort(node *[], int);
node* create(char[], int);
void sright(node *[], int);
void Assign_Code(node*, int[], int, string *);
void Delete_Tree(node *);

int main(int argc, char *argv[]) {
 //Hard-coded variables
 //Counters

 int a, b, c = 0;
 //Arrays
 char *key = (char*) malloc(ASCII * sizeof(char*));
 int *value = (int*) malloc(ASCII * sizeof(int*));

 //File pointers

 FILE *fp = fopen(argv[1], "r");
 if (fp == NULL) {
  fprintf(stderr, "can't open %s\n", argv[1]);
  return 0;
 }
 //Nodes
 node* ptr;//, *head;
 node* array[ASCII];

 //
 int u, carray[ASCII];
 char str[ASCII];

 //Variables
 char car = 0;
 int inList = 0;
 int placeinList = -1;
 int numofKeys;

 if (argc < 2) {
  printf("Usage: huff <.txt file> \n");
  return 0;
 }

 for (a = 0; a < ASCII; a++) {
  key[a] = -1;
  value[a] = 0;
 }

 car = fgetc(fp);
 while (!feof(fp)) {
  for (a = 0; a < ASCII; a++) {
   if (key[a] == car) {
    inList = 1;
    placeinList = a;
   }
  }
  if (inList) {
   //increment value array
   value[placeinList]++;
   inList = 0;
  } else {
   for (b = 0; b < ASCII; b++) {
    if (key[b] == -1) {
     key[b] = car;
     break;
    }
   }
  }
  car = fgetc(fp);
 }
 fclose(fp);
 c = 0;
 for (a = 0; a < ASCII; a++) {
  if (key[a] != -1) {
   array[c] = create(&key[a], value[a]);
   numofKeys = c;
   c++;
  }
 }

 string code_string[numofKeys];

 while (numofKeys > 1) {
  sort(array, numofKeys);
  u = array[0]->freq + array[1]->freq;
  strcpy(str, array[0]->ch);
  strcat(str, array[1]->ch);
  ptr = create(str, u);
  ptr->right = array[1];
  ptr->left = array[0];
  array[0] = ptr;
  sright(array, numofKeys);
  numofKeys--;
 }

 Assign_Code(array[0], carray, 0, code_string);

 ofp = fopen("small1.txt.huff", "w");

 ifp = fopen("small1.txt", "r");

 car = fgetc(ifp);
 while (!feof(ifp)) {
  for (a = 0; a < ASCII; a++) {
   if (key[a] == car) {
    for (b = 0; b < strlen(code_string[a]); b++) {
     if (code_string[a][b] == 48) {
      writebit(0);
     } else if (code_string[a][b] == 49) {
      writebit(1);
     }
    }
   }
  }
  car = fgetc(ifp);
 }
 writebit(255);
 fclose(ofp);
 ifp = fopen("small1.txt", "r");
 fclose(ifp);
 free(key);
 //free(value);
 //free(code_string);
 printf("here1\n");
 return 0;
}

int writebit(unsigned char bitval) {

 static unsigned char bitstogo = 8;
 static unsigned char x = 0;

 if ((bitval == 0) || (bitval == 1)) {
  if (bitstogo == 0) {
   fputc(x, ofp);
   x = 0;
   bitstogo = 8;
  }
  x = (x << 1) | bitval;
  bitstogo--;
 } else {
  x = (x << bitstogo);
  fputc(x, ofp);
 }

 return 0;
}
void Assign_Code(node* tree, int c[], int n, string * s) {
 int i;
 static int cnt = 0;
 string buf = malloc(ASCII);
 if ((tree->left == NULL) && (tree->right == NULL)) {
  for (i = 0; i < n; i++) {
   sprintf(buf, "%s%d", buf, c[i]);
  }
  s[cnt] = buf;
  cnt++;
 } else {
  c[n] = 1;
  n++;
  Assign_Code(tree->left, c, n, s);
  c[n - 1] = 0;
  Assign_Code(tree->right, c, n, s);
 }
}
node* create(char a[], int x) {
 node* ptr;
 ptr = (node *) malloc(sizeof(node));
 ptr->freq = x;
 strcpy(ptr->ch, a);
 ptr->right = ptr->left = NULL;
 return (ptr);
}

void sort(node* a[], int n) {
 int i, j;
 node* temp;
 for (i = 0; i < n - 1; i++)
  for (j = i; j < n; j++)
   if (a[i]->freq > a[j]->freq) {
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
   }
}

void sright(node* a[], int n) {
 int i;
 for (i = 1; i < n - 1; i++)
  a[i] = a[i + 1];
}
4

5 回答 5

3

如果您的程序在其他有效操作上崩溃(例如从函数返回或关闭文件),我几乎可以保证这是缓冲区溢出问题而不是内存泄漏问题。

内存泄漏通常意味着您的 malloc 最终会失败,并不意味着其他操作会受到影响。堆栈上的一个项目的缓冲区溢出(例如)很可能会破坏它附近的堆栈上的其他项目(例如文件句柄变量或来自 的返回地址main)。

最初最好的选择可能是在写入文件句柄时设置条件断点。fopen这应该发生在对其他地方的调用中。如果您在调用完成fopen检测到写入,那将是您的问题发生的地方,因此只需检查堆栈和执行行以找出原因。


你的第一个问题(这不一定是唯一的)在于:

c = 0;
for (a = 0; a < ASCII; a++) {
    if (key[a] != -1) {
        array[c] = create(&key[a], value[a]);
        numofKeys = c;  // DANGER,
        c++;            //   WILL ROBINSON !!
    }
}

string code_string[numofKeys];

您可以看到您在递增之前c设置了键的数量。这意味着键的数量比您实际需要的少一个,因此,当您访问 的最后一个元素时code_string,您实际上正在访问其他内容(这不太可能是有效指针)。

numofKeys = c;左右交换c++;。当我这样做时,我至少可以在here1没有核心转储的情况下进行位打印并退出。我不能保证您的其余代码的正确性,但这解决了分段违规,因此您的下一个问题可能应该包含其他任何内容(如果需要)。

于 2010-12-01T04:40:50.133 回答
1

我可以看到一个问题:

strcpy(str, array[0]->ch);
strcat(str, array[1]->ch);

ch字段struct link是一个char大小数组255。它没有NUL终止。所以你不能使用复制它strcpy

你还有:

ofp = fopen("small1.txt.huff", "w");
ifp = fopen("small1.txt", "r");

如果small1.txt.huff不存在,将被创建。但是如果small1.txt它不会被创建并且fopen会返回NULL,你必须fopen在你去从文件中读取之前检查返回值。

于 2010-12-01T04:51:09.760 回答
0

仅从计数,您有 4 个单独的malloc呼叫,但只有一个free呼叫。

我也会警惕你的sprintf电话,以及你的实际情况malloc

你做了一个,但如果你的最终字符串比字节sprintf(buf, "%s%d", buf, c[i])长,那可能是缓冲区溢出。ASCII

我建议您使用调试器逐步检查它在哪里引发分段错误,然后从那里进行调试。

于 2010-12-01T04:42:32.527 回答
0

我编译了程序并使用它的源作为该文件运行它,如果文件不存在或文件存在并且你在命令上给出它,就像程序崩溃small1.txt一样,得到“无法打开(null)” :./huf small1.txt

Program terminated with signal 11, Segmentation fault.
#0  0x08048e47 in sort (a=0xbfd79688, n=68) at huf.c:195
195    if (a[i]->freq > a[j]->freq) {
(gdb) backtrace
#0  0x08048e47 in sort (a=0xbfd79688, n=68) at huf.c:195
#1  0x080489ba in main (argc=2, argv=0xbfd79b64) at huf.c:99

从你运行的 gdb 得到这个

ulimit -c 100000000
./huf
gdb --core=./core ./huf

并输入回溯

于 2010-12-01T04:48:26.877 回答
0

您的代码中有各种问题:

1.- malloc(必须):

//Arrays
char *key = (char*) malloc(ASCII * sizeof(char));
int *value = (int*) malloc(ASCII * sizeof(int));

sizeof(char) == 1, sizeof(char *) == 4 or 8 (if 64 bits compiler is used).

2.- 缓冲区大小 255 (ASCII) 太短,无法接收 array[0]->ch + array[1]->ch + '\0' 的内容。

3.- 使用 strncpy 代替 strcpy 和 strncat 代替 strcat。

4.- key 是个人字符数组还是以空字符结尾的字符串?,因为您在代码中以两种方式使用此变量。在字符计数循环中,您将此变量用作单个字符的数组,但在创建节点时,您将传递数组的指针并复制为空终止数组。

5.- 最后总是在使用之前检查你的参数,你在尝试打开 argv[1] 后检查 argc < 2。

于 2010-12-01T05:55:58.223 回答