이재규님 책
C언어로 배우는 알고리즘에 자세한 알고리즘 구현법이 있습니다.
다른 부분과는 다르게 이부분은 트리만 알면 쉽게 이해할수 있을 겁니다.
쉽게 설명이 되어 있습니다.
그럼
한불새 님이 쓰신 글 :
: #include<iostream>
: #include<vector>
: #include<string>
: using namespace std;
: struct node
: {
: node * leftChild;
: node * rightChild;
: double frequency;
: string content;
: string code;
: };
: vector<node> nodeArray;// Use nodeArray to record all the nodes that may be created in the whole process
: node extractMin()
: {
: double temp = (double) INT_MAX;
: vector<node>::iterator i1,pos;
: for(i1 = nodeArray.begin();i1!=nodeArray.end();i1++)
: {
:
: if(temp>(*i1).frequency)
: {
: pos = i1;
: temp = (*i1).frequency;
: }
: }
: node tempNode = (*pos);
: nodeArray.erase(pos);
: return tempNode;
: }
: node getHuffmanTree()
: {
: while(!nodeArray.empty())
: {
: node * tempNode = new node;
: node * tempNode1 = new node;
: node * tempNode2 = new node;
: *tempNode1 = extractMin();
: *tempNode2 = extractMin();
: tempNode->leftChild = tempNode1;
: tempNode->rightChild = tempNode2;
: tempNode->frequency = tempNode1->frequency+tempNode2->frequency;
: nodeArray.push_back(*tempNode);
: if(nodeArray.size() == 1)//only the root node exsits
: {
: break;
: }
: }
: return nodeArray[0];
: }
: void BFS(node * temproot,string s)
: {
: node * root1 = new node;
: root1 = temproot;
: root1->code = s;
: if(root1 == NULL)
: {
:
: }
: else if(root1->leftChild == NULL && root1->rightChild == NULL)
: {
:
: cout<<root1->content<<endl;
: cout<<"부호"<<root1->code<<endl;
: }
: else
: {
:
: root1->leftChild->code = s.append("0");
: s.erase(s.end()-1);
: root1->rightChild->code = s.append("1");
: s.erase(s.end()-1);
:
:
: BFS(root1->leftChild,s.append("0"));
: s.erase(s.end()-1);
: BFS(root1->rightChild,s.append("1"));
: s.erase(s.end()-1);
: }
:
: }
:
: void getHuffmanCode()
: {
: int size,i;
: double tempDouble;
: string tempString = "";
:
: cout<<"글자수를 입력하시오. "<<endl;
: cin>>size;
:
: for(i = 0;i<size;i++)
: {
: cout<<"알파벳 순서대로 값 입력하시오. "<<endl;
: node tempNode;
: cin>>tempString;
: cin>>tempDouble;
:
:
: tempNode.frequency = tempDouble;
: tempNode.content = tempString;
: tempNode.leftChild = NULL;
: tempNode.rightChild = NULL;
: nodeArray.push_back(tempNode);
: }
:
: node root = getHuffmanTree();
:
: BFS(&root,"");
:
: }
:
: int main()
: {
:
: vector<int> test;
: test.push_back(1);
: test.push_back(2);
: test.push_back(3);
: test.push_back(4);
: vector<int>::iterator i1 = test.begin();
: test.erase(i1);
:
: getHuffmanCode();
: return 0;
: }
|