كسي نيست يه كمك كنه
Printable View
كسي نيست يه كمك كنه
بابا يه راهنماي كنيد خواهش مي كنم
بچه ها کسی کد هافمن رو نداره؟؟
من معمولا خودم پروژه هام رو مینویسم ، ولی واسه این یکی مثل اینکه اصلا وقت ندارم
خواهش می کنم:-(
هافمن چیه؟ میشه بیشتر توضیح بدید
با یه سرچ ساده میتونستی پیدا کنی.نقل قول:
اینکه چقدر خوب نوشته شده رو نمیدونم ضمنا اینجا از نوع های تعریف شده ی ویندوز به جای استاندارد ++C استفاده شده(DWORD بجای unsigned long و BYTE بجای unsigned char).کد:class CHuffmanNode
{
public:
CHuffmanNode() { memset(this, 0, sizeof(CHuffmanNode)); }
int nFrequency; // must be first for byte align
BYTE byAscii;
DWORD dwCode;
int nCodeLength;
CHuffmanNode *pParent, *pLeft, *pRight;
};
int __cdecl frequencyCompare(const void *elem1, const void *elem2 )
{
CHuffmanNode *pNodes[2] = { (CHuffmanNode*)elem1, (CHuffmanNode*)elem2 };
if(pNodes[0]->nFrequency == pNodes[1]->nFrequency)
return 0;
return pNodes[0]->nFrequency < pNodes[1]->nFrequency ? 1 : -1;
}
int __cdecl asciiCompare(const void *elem1, const void *elem2 )
{
return ((CHuffmanNode*)elem1)->byAscii > ((CHuffmanNode*)elem2)->byAscii ? 1 : -1;
}
CHuffmanNode* PopNode(CHuffmanNode *pNodes[], int nIndex, bool bRight)
{
CHuffmanNode* pNode = pNodes[nIndex];
pNode->dwCode = bRight;
pNode->nCodeLength = 1;
return pNode;
}
void SetNodeCode(CHuffmanNode* pNode)
{
CHuffmanNode* pParent = pNode->pParent;
while(pParent && pParent->nCodeLength)
{
pNode->dwCode <<= 1;
pNode->dwCode |= pParent->dwCode;
pNode->nCodeLength++;
pParent = pParent->pParent;
}
}
int GetHuffmanTree(CHuffmanNode nodes[], bool bSetCodes = true)
{
CHuffmanNode* pNodes[256], *pNode;
// add used ascii to Huffman queue
int nNodeCount = 0;
for(int nCount = 0; nCount < 256 && nodes[nCount].nFrequency; nCount++)
pNodes[nNodeCount++] = &nodes[nCount];
int nParentNode = nNodeCount, nBackNode = nNodeCount-1;
while(nBackNode > 0)
{
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;
// insert parent node depending on its frequency
for(int i = nBackNode; i >= 0; i--)
if(pNodes[i]->nFrequency >= pNode->nFrequency)
break;
memmove(pNodes+i+2, pNodes+i+1, (nBackNode-i)*sizeof(int));
pNodes[i+1] = pNode;
nBackNode++;
}
// set tree leaves nodes code
if(bSetCodes)
for(nCount = 0; nCount < nNodeCount; nCount++)
SetNodeCode(&nodes[nCount]);
return nNodeCount;
}
bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen)
{
CHuffmanNode nodes[511];
// initialize nodes ascii
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
// get ascii frequencies
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
// sort ascii chars depending on frequency
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
// construct Huffman tree
int nNodeCount = GetHuffmanTree(nodes);
// construct compressed buffer
int nNodeSize = sizeof(DWORD)+sizeof(BYTE);
nDesLen = nSrcLen+nNodeCount*nNodeSize;
pDes = (BYTE*)malloc(nDesLen);
BYTE *pDesPtr = pDes;
memset(pDesPtr, 0, nDesLen);
// save source buffer length at the first DWORD
*(DWORD*)pDesPtr = nSrcLen;
pDesPtr += sizeof(DWORD);
// save Huffman tree leaves count-1 (as it may be 256)
*pDesPtr = nNodeCount-1;
pDesPtr += sizeof(BYTE);
// save Huffman tree used leaves nodes
for(nCount = 0; nCount < nNodeCount; nCount++)
{ // the array sorted on frequency so used nodes come first
memcpy(pDesPtr, &nodes[nCount], nNodeSize);
pDesPtr += nNodeSize;
}
// sort nodes depending on ascii to can index nodes with its ascii value
qsort(nodes, 256, sizeof(CHuffmanNode), asciiCompare);
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
// update destination length
nDesLen = (pDesPtr-pDes)+(nDesIndex+7)/8;
pDes = (BYTE*)realloc(pDes, nDesLen);
return true;
}
bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen)
{
// copy destination final length
nDesLen = *(DWORD*)pSrc;
// allocate buffer for decompressed buffer
pDes = (BYTE*)malloc(nDesLen+1);
int nNodeCount = *(pSrc+sizeof(DWORD))+1;
// initialize Huffman nodes with frequency and ascii
CHuffmanNode nodes[511], *pNode;
int nNodeSize = sizeof(DWORD)+sizeof(BYTE), nSrcIndex = nNodeSize;
for(int nCount = 0; nCount < nNodeCount; nCount++)
{
memcpy(&nodes[nCount], pSrc+nSrcIndex, nNodeSize);
nSrcIndex += nNodeSize;
}
// construct Huffman tree
GetHuffmanTree(nodes, false);
// get Huffman tree root
CHuffmanNode *pRoot = &nodes[0];
while(pRoot->pParent)
pRoot = pRoot->pParent;
int nDesIndex = 0;
DWORD nCode;
nSrcIndex <<= 3; // convert from bits to bytes
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft) // if node has pLeft then it must has pRight
{ // node not leaf
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}
return true;
}
--
در مورد Huffman :
من يه مشكل برنامه نويسي تو C داشتم
برنامه مربوط مي شه به LDU
اينكه از كاربر يه ماتريس n در n بگيره سپس اون رو به يه ماتريس بالا مثلثي ،ماتريس قطري وماتريس پايين مثلثي تبديل كنه !!! بهاين ميگن LDU
به خدا كارم خيلي گيره
هر كس تونست اون رو برام ميل كنه ،ممنون مي شم
اجازه بدید ما هم یکی از این سوالات عجیب استادمون رو این وسط مطرح کنیم ، شاید کسی باشه که قبلا" با این مسئله برخورد کرده باشه یا بدونه چه جوری حل میشه و به ما بگه. :11:
سوال اینه که:
کاربری یک عدد بین 1 تا 256 به دلخواه انتخاب می کنه ، شما باید با پرسیدن حداکثر 8 سوال به عدد مورد نظر برسید. (طوریکه جوابها فقط بله و یا خیر باشند)
برنامه اش رو خودم می نویسم ، فقط یکی بیاد راه حل بده !!
منم یه مقدار روش فکر کردم ، ولی خیلی بیشتر از 8 سوال میشه !!
این که مثلا" بپرسیم عدد مورد نظر اول هست ؟! یا مثلا" بپرسیم عدد مورد نظر آخرش 0 داره (یا به زبون دیگه بر 10 بخش پذیر هست یا نه ) ؟! و از این قبیل سوال ها به ذهنم رسید که خواهش می کنم علم بی پایان خودتون رو از ما دریغ نکنید !! :5:
بهتر بود خودت فکر میکردی و راه حل رو پیدا میکردی اونطوری جالب تر بود برات.
روش اینه که با هر سوال نصف جواب های ممکن رو حذف میکنیم.سوال هم ساده هستش.کافیه هر بار وسط بازه اعدادت( یعنی اولین بار 2 / 256) رو در نظر بگیری و بپرسی که آیا عدد مورد نظر ازین عدد بزرگ تره یا نه.اینطور نصف جواب ها حذف میشه مثلا اگه برای اولین بار بگه نه, میفهمی که عدد مورد نظر یکی از اعداد 1 تا 128 هست و بار دیگه سوال میکنی که آیا عدد مورد نظر از 64 (2/128) بزرگتره.مثلا اگه گفت نه عدد مورد نظر یکی از عداد 1 تا 64 هست و یا اگه گفت بله عدد مورد نظر بین 64 تا 128 هست و الی آخر.
در واقع هر دفعه بازه رو نصف میکنی.حداکثر تعداد سوال های لازم هم log تعداد اعداد در مبنای 2 هست که اینجا میشه 8.
آقا مخلصیم.... :11:نقل قول:
پس بگو جریان این 256 چی بوده... خیلی مشکوک میزد که چرا 256 !
ظاهرا" که درست میزنه ، امیدوارم باطنا" هم درست باشه.
مثل اینکه یه 4 نمره ای هم داره این پروژه که یادم باشه 2 نمرشو برات کنار بذارم ، 2 نمره دیگه رو هم بدم به بقیه گروهمون ( خیر سرم سرگروهم !!! :27:)
آره خوب این قضیه اساس روش Binary Search هست.فکر کنم استادتون هم واسه همین گفته..
آره اون دو نمره رو هم انتقالی ش کن بفرست واسه من (آدرس بدم؟ :D)