C++实现oj算法代码-贪心算法.zip

//#define _CRT_SECURE_NO_WARNINGS 1 //#include<stdio.h> //#include<stdlib.h> //#include <iostream> //http://oj33.cn/contest.php?cid=1075 //https://blog.csdn.net/qq_37482202/article/details/89513877 // //typedef struct //{ // int weight; // int left; // int right; // int parent; //}Node, * HuffmanTree; // ////存储哈夫曼编码 //typedef char* HuffmanCode; //void CreateHuffmanTree(HuffmanTree* T, int w[], int n); //void select(HuffmanTree* T, int n, int* m1, int* m2); //void CreateHuffmanCode(HuffmanTree* T, HuffmanCode* C, int n); ///*创建哈夫曼树*/ ////传入n个权重，作为哈夫曼树的n个叶子结点 //void CreateHuffmanTree(HuffmanTree* T, int w[], int n) //{ // int m = 2 * n - 1;//n个叶子结点，共m个结点 // int m1, m2;//用于建立下一个结点的两结点，值为最小的两个 // *T = (HuffmanTree)malloc((m + 1) * sizeof(Node)); // //初始化前n个结点（叶子结点），权重赋值，暂时没有左右孩子与父亲 // for (int i = 1; i <= n; i++) // { // (*T)[i].weight = w[i]; // (*T)[i].left = (*T)[i].right = (*T)[i].parent = 0; // // } // //初始化[n+1,m]个结点(非叶子结点) // for (int i = n + 1; i <= m; i++) // { // (*T)[i].weight = (*T)[i].left = (*T)[i].right = (*T)[i].parent = 0; // // } // // //开始建树，第i个结点的两孩子为m1,m2，权重为两孩子结点权重之和 // for (int i = n + 1; i <= m; i++) // { // select(T, i - 1, &m1, &m2); // (*T)[i].left = m1; // (*T)[i].right = m2; // (*T)[m1].parent = i; // (*T)[m2].parent = i; // (*T)[i].weight = (*T)[m1].weight + (*T)[m2].weight; // // /*printf("%d (%d %d)\n", (*T)[i].weight, (*T)[m1].weight, (*T)[m2].weight);*/ // } // printf("\n"); //} // ///*选取得到n个无父节点的两最小结点*/ //void select(HuffmanTree* T, int n, int* m1, int* m2) //{ // int m;//存储最小值的数组下标 // // //给m赋初值 // for (int i = 1; i <= n; i++) // { // if ((*T)[i].parent == 0) // { // m = i; // break; // } // } // //找到当前最小的权重（叶子结点） // for (int i = 1; i <= n; i++) // { // if ((*T)[i].parent == 0 && (*T)[i].weight < (*T)[m].weight) // { // m = i; // } // } // //先赋给m1保存一个，再去寻找第二小的值 // *m1 = m; // for (int i = 1; i <= n; i++) // { // if ((*T)[i].parent == 0 && i != *m1) // { // m = i; // break; // } // } // for (int i = 1; i <= n; i++) // { // if ((*T)[i].parent == 0 && i != *m1 && (*T)[i].weight < (*T)[m].weight) // { // m = i; // } // } // //保存第二小的数 // *m2 = m; // // if(*m1>*m2) // { // int a=*m1; // *m1=*m2; // *m2=a; // } //} // ///*创建哈夫曼编码*/ ////从n个叶子结点到根节点逆向求解 //void CreateHuffmanCode(HuffmanTree* T, HuffmanCode* C, int n) //{ // //编码长度为s-1,第s位为\0 // int s = n - 1; // //当前结点的父节点数组下标 // int p = 0; // //为哈夫曼编码分配空间 // C = (HuffmanCode*)malloc((n + 1) * sizeof(char*)); // //临时保存当前叶子结点的哈夫曼编码 // char* cd = (char*)malloc(n * sizeof(char)); // //最后一位为\0 // cd[n - 1] = '\0'; // // for (int i = 1; i <= n; i++) // { // s = n - 1; // //c指向当前结点,p指向此结点的父节点,两者交替上升，直到根节点 // for (int c = i, p = (*T)[i].parent; p != 0; c = p, p = (*T)[p].parent) // { // //判断此结点为父节点的左孩子还是右孩子 // if ((*T)[p].left == c) // cd[--s] = '0';//左孩子就是编码0 // else // cd[--s] = '1';//右孩子就是编码1 // } // //为第i个编码分配空间 // C[i] = (char*)malloc((n - s) * sizeof(char)); // //将此编码赋值到整体编码中 // strcpy(C[i], &cd[s]); // } // //释放 // free(cd); // //打印编码序列 // for (int i = 1; i <= n; i++) // { // printf("%s",C[i]); // printf("\n"); // } //} // //int main() //{ // HuffmanTree T; // HuffmanCode C; // int n, w1, * w; // scanf_s("%d", &n); // w = (int*)malloc((n + 1) * sizeof(int)); // for (int i = 1; i <= n; i++) // { // scanf_s("%d", &w1); // w[i] = w1; // } // printf("\n"); // CreateHuffmanTree(&T, w, n); // CreateHuffmanCode(&T, &C, n); // return 0; //} //} #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include <iostream> typedef struct HTNode { int left; int right; int parent; int weight; }*HuffmanTree; //typedef char* HuffmanCode; int m; //void minnum(int *min1,int *min2,HuffmanTree &T,int n,int a) //{ // for (int i = 1; i < n; i++) // { // if (T[i].parent==0&&T[a].weight > T[i].weight) // { // a = i; // } // } // *min1 = a; // for (int i = 1; i <n; i++) // { // if ((T)[i].parent == 0 && i != *min1) // { // a = i; // break; // } // } // for (int i = 1; i <n; i++) // { // if (i!=*min1&&T[i].parent == 0 && T[i].weight < T[a].weight) // { // a = i; // } // } // *min2 = a; // if (*min1 > *min2) // { // a = *min1; *min1 = *min2; *min2 = a; // } //} void minnum(int* min1, int* min2, HuffmanTree& T, int n) { int a;//存储最小值的数组下标 for (int i = 1; i <= n; i++) { if (T[i].parent == 0) { a = i; break; } } for (int i = 1; i < n; i++) { if (T[i].parent == 0 && T[a].weight > T[i].weight) { a = i; } } *min1 = a; for (int i = 1; i < n; i++) { if ((T)[i].parent == 0 && i != *min1) { a = i; break; } } for (int i = 1; i < n; i++) { if (i != *min1 && T[i].parent == 0 && T[i].weight < T[a].weight) { a = i; } } *min2 = a; if (*min1 > *min2) { a = *min1; *min1 = *min2; *min2 = a; } } void print(int to,int n,char **a) { for (int i = to; i < n; i++) { printf("%c", (*a)[i]); } printf("\n"); } void CreatHuffmanCode(HuffmanTree* T, char** Code, int n) { int p;//父节点 Code = (char**)malloc((n+1) * sizeof(char*)); char* a =(char*) malloc((n)*sizeof(char)); a[n-1] = '\0'; for (int i = 1 ;i <=n; i++) { int to = n - 1; for (int j = i, p = (* T)[j].parent;p!=0&&p<m; j = p, p = (*T)[p].parent) { if (( * T)[p].left == j) { a[to]='0'; to--; } else { a[to]='1'; to--; } } print(to+1,n,&a); } } void creat(int n, HuffmanTree&T) { for (int i = n + 1; i < m; i++) { int a1, a2; minnum(&a1, &a2, T, i); T[i].left = a1; T[i].right = a2; T[i].weight = T[a1].weight + T[a2].weight; T[a1].parent = T[a2].parent = i; } } int main() { HuffmanTree T; char* c; int n=0; scanf("%d", &n); int wi; int* node =(int *) malloc((n+1) * sizeof(int));//节点数组 for (int i = 1; i < n+1; i++) { scanf("%d", &wi); node[i] = wi; } int totalnode = 2 * n ; m = totalnode; T = (HTNode*)malloc(m * sizeof(HTNode)); for (int i = 1; i < m; i++) { if (i <=n) { T[i].weight = node[i]; T[i].parent = T[i].left = T[i].right = 0;; } else { T[i].parent = T[i].left = T[i].right = 0;; T[i].weight = 0; } } creat(n, T); //for(int i=n+1;i<m;i++) // { // int a1, a2; // minnum(&a1,&a2, T, i); // T[i].left = a1; // T[i].right = a2; // T[i].weight = T[a1].weight + T[a2].weight; // T[a1].parent = T[a2].parent = i; // } CreatHuffmanCode(&T,&c ,n); return 0; } //} //#include<iostream> //#include<algorithm> //#include<vector> //#include<string> //#include<limits.h> //INT_MAX的头文件，不包含编译可能不会通过 //using namespace std; // //struct huffman_node { // int weight;//权值 // int lchild, rchild;//左右子树 // int parent;//父结点 //}; // // ////************************************ //// Method: select_tow_min 找出集合中两个最小的值 //// FullName: select_tow_min //// Access: public //// Returns: void //// Qualifier: //// Parameter: vector<huffman_node> & huffman_tree 存放哈夫曼树的集合 //// Parameter: int n 当前哈夫曼树共有多少结点 //// Parameter: int & first_min 第一个最小结点 //// Parameter: int & second_min 第二个最小结点 ////************************************ //void select_tow_min(vector<huffman_node>& huffman_tree, int n, int& first_min, int& second_min) //{ //