为什么使用malloc函数一次却开辟了两个空间?急,高分悬赏!!

Question

我用C语言编写哈夫曼编码的程序时遇到了这样的问题:当使用malloc开辟结点空间时,每次用malloc后,系统自动给开辟了两个结点的空间,导致做出来的单链表每隔一个结点才有一个数据.这到底是怎么回事?我把源程序给出如下:(出问题的地方在void Inithuffmantree()中)

http://hi.baidu.com/1%B6%AB%B6%AB1/creat/blog/

请各位C语言达人给出解释~~:)
http://hi.baidu.com/1%B6%AB%B6%AB1 这个网址是正确的,上面的不对

Answer 1

＃i nclude

或

＃i nclude

函数声明(函数原型)：

void *malloc(int size);

说明：malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定，void* 类型可以强制转换为任何其它类型的指针。
从函数声明上可以看出。malloc 和 new 至少有两个不同: new 返回指定类型的指针，并且可以自动计算所需要大小。比如：

int *p;

p = new int; //返回类型为int* 类型(整数型指针)，分配大小为 sizeof(int);

或：

int* parr;

parr = new int [100]; //返回类型为 int* 类型(整数型指针)，分配大小为 sizeof(int) * 100;

而 malloc 则必须由我们计算要字节数，并且在返回后强行转换为实际类型的指针。

int* p;

p = (int *) malloc (sizeof(int));

第一、malloc 函数返回的是 void * 类型，如果你写成：p = malloc (sizeof(int)); 则程序无法通过编译，报错：“不能将 void* 赋值给 int * 类型变量”。所以必须通过 (int *) 来将强制转换。

第二、函数的实参为 sizeof(int) ，用于指明一个整型数据需要的大小。如果你写成：

int* p = (int *) malloc (1);

代码也能通过编译，但事实上只分配了1个字节大小的内存空间，当你往里头存入一个整数，就会有3个字节无家可归，而直接“住进邻居家”！造成的结果是后面的内存中原有数据内容全部被清空。

malloc 也可以达到 new [] 的效果，申请出一段连续的内存，方法无非是指定你所需要内存大小。

比如想分配100个int类型的空间：

int* p = (int *) malloc ( sizeof(int) * 100 ); //分配可以放得下100个整数的内存空间。

另外有一点不能直接看出的区别是，malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的。

除了分配及最后释放的方法不一样以外，通过malloc或new得到指针，在其它操作上保持一致。

Answer 2

你的malloc应该是没错的，单链表每隔一个结点才有一个数据，应该是你给单链表赋值的时候逻辑错误，中间多next了一个。

建议用单步调试看看，或者简化代码，分理出最小单元来调试一下

Answer 3

//给你个哈夫曼编码的 不明白可以加我QQ问我 21100432
/******************************************************************************************************
* 哈夫曼编/译码器 *
* author: *
* email:[email protected] *
* data: *
* desciption: 用哈夫曼码实现 编码 和 译码的 任务 *
* *
* 备注： *
*******************************************************************************************************/
#include<string.h>
#include<conio.h>
#include<stdio.h> //输入和输出函数的头文件
#include<stdlib.h> //exit函数的头文件
#include<malloc.h> //malloc函数的头文件
#include<iostream.h>
//**********************************************************

#define OVERFLOW -2 //溢出时的值为-2
#define OK 1 //成功时时的值为1
#define ERROR 0 //不成功时时的值为0

//**********************************************************
typedef int ElemType; //ElemType 任意的数据类型
typedef int Status; //ElemType 任意的数据类型
//
//**********************************************************

//********************Huffmantree的结点结构***************************

typedef struct{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;
//**********************************************************

#define CHLENGTH 27 //8

#define WLENGTH 27 //8

void HuffmanCoding(HuffmanTree &,HuffmanCode &,int *,int );

void Select(HuffmanTree ,int ,int &,int &);

void HuffmanDecoding(char *,HuffmanTree ,HuffmanCode ,int *,int *,int );

void Treeprinting(char *,HuffmanTree ,HuffmanCode ,int *,int *,int );

void preorder(HuffmanTree HT,int root,int i,int sum,int *,int *,FILE *);

void main(void){
int ch[CHLENGTH]={' ','A','B','C','D','E','F','G',
'H','I','J','K','L','M','N',
'O','P','Q','R','S','T','U',
'V','W','X','Y','Z'}; //
int w[WLENGTH]={186,64,13,22,32,103,21,15,47,57,
1,5,32,20,57,63,15,1,48,51,80,
23,8,18,1,16,1}; //

/* int ch[CHLENGTH]={'T','H','I','S',' ','P','R','O','G','R','A','M',' ',
'I','S',' ','M','Y',' ','F','A','V','O','R','I','T','E'};
int w[WLENGTH]={80,47,57,51,186,15,48,63,15,48,64,20,186,57,51,186,20,16,21,
64,8,63,48,57,80,103};
*/
int i=1;
// int ch[CHLENGTH]={5,29,7,8,14,23,3,11};
char buff[1025];
// int w[WLENGTH]={500,2900,700,800,1400,2300,300,1100};
char c,ch1;
FILE *fp_1,*fp_2;
int flag=1,legth=0;
HuffmanTree HT;
HuffmanCode HC;
while(1){
printf("*********************************************************\n");
printf("(1) e 进行编码\n");
printf("(2) d 译码 工作\n");
printf("(3) p 打印CodeFile.txt\n");
printf("(4) t 打印HuffmanTree \n");
printf("(5) q 退出程序\n");
printf("*********************************************************\n");
scanf("%c",&c);
getchar();
switch(c){
case 'e':
HuffmanCoding(HT,HC,w,WLENGTH); //进行编码
if((fp_1=fopen("CodeFile.txt","w")) == NULL){
printf("can not open the file\n");
getch();
exit(0);
}
for(i=1;i<WLENGTH+1;i++){
printf("%c",ch[i-1]);

//putchar(ch[i-1]);
printf(" ");
fputs(HC[i],fp_1); //存储在文件中
puts(HC[i]); //打印在屏幕上
}

fclose(fp_1);//

break;

case 'd':
if((fp_1=fopen("CodeFile.txt","r")) == NULL){//此处 以只读方式 打开 是 "r "
printf("can not open the file\n");
getch();
exit(0);
}
i=0;
while( !feof(fp_1) ){
fgets(buff,1024,fp_1);
//legth=strlen(buff);//求出这个串的长度
HuffmanDecoding(buff,HT,HC,w,ch,WLENGTH);
}
break;//译码 工作

case 'p':
i=0;//每50行 打印的
if((fp_1=fopen("CodeFile.txt","r")) == NULL){//此处 以只读方式 打开 是 "r "
printf("can not open the file\n");
getch();
exit(0);
}
if((fp_2=fopen("CodePin.txt","w")) == NULL){//
printf("can not open the file\n");
getch();
exit(0);
}
ch1=fgetc(fp_1);

while( !feof(fp_1) ){ //让读者看一遍这个文件 也方便我 调试时的检查
i++;
putchar(ch1);
fprintf(fp_2,"%c",ch1);
if(i%50 == 0) {
printf("\n");
fprintf(fp_2,"%c",'\n');
}

ch1=fgetc(fp_1);
}
printf("\n");
//打印CodeFile.txt
break;

case 't': Treeprinting(buff,HT,HC,w,ch,WLENGTH);

//打印HuffmanTree
break;

case 'q': exit(0);

}
}

/*
i=1;
//HuffmanDecode
while( !feof(fp_1) ) {
buff[i]=fgetc(fp_1);
i++;
}

fclose(fp_1);
*/
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {
// 算法6.12
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j, m, s1, s2, start;
char *cd;
int c, f;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("\n哈夫曼树的构造过程如下所示：\n");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
// printf(" 按任意键，继续 ...");
//getch();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
// printf(" 按任意键，继续 ...");
//getch();
}

//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1] = '\0'; // 编码结束符。
for (i=1; i<=n; ++i) { // 逐个字符求哈夫曼编码
start = n-1; // 编码结束符位置
for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
// 从叶子到根逆向求编码
if (HT[f].lchild==c) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = (char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
printf("\n");
free(cd); // 释放工作空间
} // HuffmanCoding

void Select(HuffmanTree HT,int x,int &s1,int &s2){
int firstmin=HT[1].weight,secondmin=HT[1].weight; //第一个权值
int firstnummin=1,secondnummin=1;
int i=1,count=1,j=1;
while(1){
if(HT[i].parent == 0){
//为其赋初值
firstmin=HT[i].weight;
secondmin=HT[i].weight;
firstnummin=i;
secondnummin=i;
j=i;
break;
}
i++;
}
/*
for(i=1;i<x;i++){
if(HT[i].weight < firstmin && HT[i].parent == 0){
firstmin=HT[i].weight;
firstnummin=i;
if(secondmin < firstmin){

secondmin = firstmin;
secondnummin=i;

}

}*/
for(++i;i<=x;i++){
//取出最小值
if(HT[i].weight < firstmin && HT[i].parent == 0){
firstmin=HT[i].weight;
firstnummin=i;//返回号
}
}

i=j;

for(++i;i<=x;i++){
//取出次小值

if(HT[i].weight > firstmin && HT[i].weight < secondmin && HT[i].parent == 0){
//if( HT[i].parent == 0){
//if( i< (int)(WLENGTH/2) ){
secondmin=HT[i].weight;
secondnummin=i;//返回号
//}
//}
}

else if(secondmin == firstmin && HT[i].parent == 0){
//特殊情况 给与考虑 (就是当这俩权值相等的时候)
secondnummin=i;
break;
}

}

s1=firstnummin;
s2=secondnummin;

}

void HuffmanDecoding(char *buff,HuffmanTree HT,HuffmanCode HC,int *w,int *ch,int n){
int root=0,i=0,j=0,lchild=0,rchild=0,k=1;
char result[100];
FILE *fp;

root=2*n-1;

if((fp=fopen("TextFile.txt","w")) == NULL){
printf("can not open the file\n");
exit(0);
}

while(buff[i]!='\0'){

if(buff[i] == '0' ){
result[j]=buff[i];//把编码存入这个 结果的数组中
j++;
root=HT[root].lchild;//一种递归的方法 把左子树的root
//更新成新的root
if( HT[root].lchild == 0 ){
//。。当左子树等于空时找到了
// j=0;
/* while(w[j] != HT[root].weight) {

j++;
}*/
result[j]='\0';

while( strcmp(HC[k],result) != 0) k++;

printf("%c",ch[k-1]);

fprintf(fp,"%c",ch[k-1]);//写入文件
j=0;
k=1;
root=2*n-1;
++i;

}

else if(root != 2*n-1) ++i;
}

else if(buff[i] == '1' ){
root=HT[root].rchild;
result[j]=buff[i];
j++;

if(HT[root].rchild == 0 ){
//j=0;
/*while(w [j] != HT[root].weight) {

j++;
}
*/
result[j]='\0';
while( strcmp(HC[k],result) != 0) k++;
printf("%c",ch[k-1]);

fprintf(fp,"%c",ch[k-1]);
j=0;k=1;
root=2*n-1;
++i;

}

else if(root != 2*n-1) ++i;

}
}

fclose(fp);
printf("\n---------------------------------------------\n");
}

void Treeprinting(char *buff,HuffmanTree HT,HuffmanCode HC,int *w,int *ch,int n){
int root=0,i=1,j=0,lchild=0,rchild=0,k=1,space=0;//space是空格数
// char result[100];
FILE *fp;

if((fp=fopen("TextFile.txt","w")) == NULL){
printf("can not open the file\n");
exit(0);
}

root=2*n-1;

preorder(HT,root,i,i,ch,w,fp);

fclose(fp);

printf("\n---------------------------------------------\n");
}

void preorder(HuffmanTree HT,int root,int i,int sum,int *ch,int *w,FILE *fp){
int lchild=0,rchild=0;

if(HT == NULL){

return;
}
if(i == 1) {
sum=sum+i;
while(i<sum){
printf(" ");
fprintf(fp," ");
i++;
}
i=1;
if( HT[root].lchild == 0 && HT[root].rchild == 0 ){
fprintf(fp,"*%d\n",HT[root].weight);
printf("*%d\n",HT[root].weight);

}
if( HT[root].lchild != 0 || HT[root].rchild != 0 ){
fprintf(fp,"%d\n",HT[root].weight);
printf("%d\n",HT[root].weight);
}
}
if(i == 2) {
sum=sum+i;
while(i<sum){
printf(" ");
fprintf(fp," ");
i++;
}
i=2;
if( HT[root].lchild == 0 && HT[root].rchild == 0 ){
fprintf(fp,"*%d\n",HT[root].weight);
printf("*%d\n",HT[root].weight);

}
if( HT[root].lchild != 0 || HT[root].rchild != 0 ){
fprintf(fp,"*%d\n",HT[root].weight);
printf("%d\n",HT[root].weight);
}

}

if(HT[root].lchild != 0){
lchild=HT[root].lchild ;
i=1;
preorder( HT,lchild,i,sum,ch,w,fp);

}

if(HT[root].rchild != 0){
rchild=HT[root].rchild ;
i=2;
preorder( HT,rchild,i,sum,ch,w,fp);
}

}本回答被提问者采纳

Answer 4

```

Answer 5

我都是用C++的 用new就够了 那么麻烦 我拿分闪