#include <stdio.h>
#include "stdlib.h"
#include <conio.h>
#include <string.h>
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF *2-1
typedef struct {
int weight;
int parent;
int lchild;
int rchild;
} HNode, HuffmanTree[MAXNODE];
typedef struct codenode {
char ch; /*存放要表示的符號*/
char* code; /*存放相應的代碼*/
} CodeNode;
typedef CodeNode HuffmanCode[MAXLEAF];
void CrtHuffmanTree(HuffmanTree& ht, int w[], int n) {
int i, j, m1, m2, x1, x2;
for (i = 0; i < 2 * n - 1; i++) { /*ht初始化*/
ht[i].weight = 0;
ht[i].parent = -1;
ht[i].lchild = -1;
ht[i].rchild = -1;
}
for (i = 0; i < n; i++)
ht[i].weight = w[i];
for (i = 0; i < n - 1; i++) { /*構造哈夫曼樹*/
m1 = m2 = MAXVALUE;
x1 = x2 = 0;
for (j = 0; j < n + i; j++) {
if (ht[j].weight < m1 && ht[j].parent == -1) {
m2 = m1; x2 = x1; x1 = j;
m1 = ht[j].weight;
}
else if (ht[j].weight < m2 && ht[j].parent == -1) {
m2 = ht[j].weight;
x2 = j;
}
}
/*將兩棵子樹合并成一棵子樹*/
ht[x1].parent = n + i; ht[x2].parent = n + i;
ht[n + i].weight = ht[x1].weight + ht[x2].weight;
ht[n + i].lchild = x1; ht[n + i].rchild = x2;
}
}
/*從葉子結點到根，逆向搜索求每個葉子結點對應符號的哈夫曼編碼*/
void CrtHuffmanCode(HuffmanTree ht, HuffmanCode& hc, int n) {
char* cd;
int i, c, p, start;
cd = (char*)malloc(n * sizeof(char)); /*為當前作業區分配空間*/
cd[n - 1] = '\0';
printf("請依次輸入待編碼字符：\n");
for (i = 0; i < n; i++) {
start = n - 1;
c = i; p = ht[i].parent;
while (p != -1) {
if (ht[p].lchild == c) cd[--start] = '0';
else cd[--start] = '1';
c = p; p = ht[p].parent;
}
hc[i].code = (char*)malloc((n - start) * sizeof(char)); /*為第i個編碼分配空間*/
fflush(stdin);
scanf_s("%c", &(hc[i].ch));
strcpy_s(hc[i].code,10,&cd[start]);
}
free(cd);
}
int main() {
HuffmanTree ht;
int w[MAXLEAF], i, n;
HuffmanCode hc;
printf("請輸入葉子結點數個數：");
scanf_s("%d", &n);
printf("請依次輸入權值：\n");
for (i = 0; i < n; i++)
scanf_s("%d", &w[i]);
CrtHuffmanTree(ht, w, n);
CrtHuffmanCode(ht, hc, n);
printf("哈夫曼編碼的結果為：\n");
for (i = 0; i < n; i++)
printf("%c, %s\n", hc[i].ch, hc[i].code);
}
用dev試了試……成功運行了……不清楚是哪里出了問題……求助 謝謝各位大佬
uj5u.com熱心網友回復：
復制下來跑了下沒出問題呀，環境vs2019uj5u.com熱心網友回復：
申請的記憶體過大，申請不出來，斷言了？uj5u.com熱心網友回復：
誒？我也是2019……就顯示這個……試了好幾次都這樣
uj5u.com熱心網友回復：
那該怎么辦呀
uj5u.com熱心網友回復：
頂頂，等一個大佬回復uj5u.com熱心網友回復：
我也跑出來沒問題，2019和2017都試了
uj5u.com熱心網友回復：
我和我同學試著都是一樣的問題
uj5u.com熱心網友回復：
1、首先，scanf_s如果讀取字符或字串，需要指定 接收地址 的大小，避免scanf_s讀取數量大于你接識訓沖區的大小，寫入到了不該寫的記憶體地址。這就是帶_s 和不帶_s的區別。 它是safe安全的，但前提 當然還是需要程式員的配合。 所以請不要忽略編譯器的警告。
所以修改如下：
scanf_s("%c",&hc[i].ch, sizeof(hc[i].ch));2、其次，strcpy_s 還是類似的問題。 該函式將源緩沖區字串內容拷貝至目標緩沖區，直到源緩沖區字串遇到'\0',或者拷貝位元組數大于等于用戶給定的目標緩沖區大小（也是微軟推出_s系列函式的原因。多了一個引數，用于指定目標緩沖區大小）。
這里需要注意的是：
a、目標緩沖區的大小需要足以容納末尾的'\0'。
b、如果目標緩沖區的大小不足。程式會直接例外退出。在debug模式下，程式會斷言報錯。
c、如果用戶指定的大小實際比目標緩沖區的大小還要大（你實際申請了5，但卻指定了10）。那也就失去了_s的作用，與不帶_s一樣，有溢位風險，一旦發生這種情況（拷貝了過多的源緩沖區內容到目標緩沖區，寫入到了不該寫的記憶體地址），你就徹底失去了對程式的掌控，程式立即崩潰反倒是最好的情況（這也是帶_s版本所做的事情），最怕的是程式雖然沒有崩潰，但是卻改寫了不該寫的內容，接下來在任何時候，都有可能引起例外，排查問題非常困難，就是你目前遇到的問題。
你這里就犯了 c 的錯誤。你固定給了10位元組的大小。
strcpy_s(hc[i].code, 10 , &cd[start]);
你應該改成這樣：
strcpy_s(hc[i].code, n - start, &cd[start]);
誠然，你給的輸入樣本中，節點個數輸入的是5，也就是說n - start 不可能大于5，一定會比10小。但你也不可能知道strcpy_s它會拿你給的這個 10 去給hc[i].code做些什么騷操作吧？ 你能知道的只是你的 hc[i].code 緩沖區內容大小一定是 n - start。
實際上，debug模式下，strcpy_s確實會做一些操作，以一些奇怪的值，用你給定的大小，去初始化你傳入的目標緩沖區。所以你就gg了。
3、最后還有一個問題，C標準里從來沒有定義過 fflush(stdin)的行為，也就是說，fflush(stdin) 這樣呼叫會產生什么效果是未知的，取決于編譯器的實作。你在 vs2019上 寫這樣的呼叫 很可能達不到你要的 “清空標準輸入緩沖區”的效果。 你的每次輸入都會有換行符遺留。從而被下一次scanf_s %c 捕獲。你可以改成使用rewind(stdin)替代fflush(stdin)，來達到目的。
rewind(stdin);
4、最后，沒有細看你的業務邏輯，就不做評價了。改掉上面的問題，程式起碼不會報錯了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/60170.html
標籤：C語言
上一篇：請教關于二叉樹交換的問題
下一篇：大神求帶！