我的Online Judge账号还没有这道题的访问权限（1172），这让我情何以堪，好在还是找到了题目，题目想做的比较好还是需要一些功底的。
做一下，马上就复试了，注释也没时间写，代码能看清楚：
1 /* 2 * author: xuangong 3 * time: 2013-4-9 21:42 4 */ 5 #include <stdio.h> 6 #include <stdlib.h> 7 8 typedef struct _huffmannode 9 { 10 int data; 11 struct _huffmannode *lchild; 12 struct _huffmannode *rchild; 13 }huffmannode, *phuffmannode; 14 15 typedef struct _list 16 { 17 phuffmannode node; 18 struct _list * next; 19 }list, *plist; 20 21 plist init_list() 22 { 23 plist head = (plist)malloc(sizeof(struct _list)); 24 head->next = head->node = NULL; 25 return head; 26 } 27 28 void add_list(plist head, phuffmannode node) 29 { 30 plist insert = (plist)malloc(sizeof(struct _list)); 31 insert->node = node; 32 insert->next = NULL; 33 if(head==NULL) 34 printf("head is null\n"); 35 if(head!=NULL) 36 { 37 plist pre = head; 38 head = head->next; 39 while(head!=NULL && node->data > head->node->data) 40 { 41 pre = head; 42 head = head->next; 43 } 44 insert->next = pre->next; 45 pre->next = insert; 46 } 47 } 48 49 void display(plist head) 50 { 51 head = head->next; 52 while(head!=NULL) 53 { 54 printf("%d ", head->node->data); 55 head = head->next; 56 } 57 printf("\n"); 58 } 59 60 phuffmannode get_list(plist head) 61 { 62 plist temp = head->next; 63 phuffmannode top = head->next->node; 64 head->next = head->next->next; 65 free(temp); 66 return top; 67 } 68 69 phuffmannode create_huffmannode(plist li) 70 { 71 phuffmannode lchild, rchild, node; 72 if(li->next!=NULL && li->next->next == NULL) 73 return get_list(li); 74 while(li->next!=NULL && li->next->next!=NULL) 75 { 76 lchild = get_list(li); 77 rchild = get_list(li); 78 node = (phuffmannode)malloc(sizeof(struct _huffmannode)); 79 node->data = lchild->data + rchild->data; 80 node->lchild = lchild; 81 node->rchild = rchild; 82 add_list(li, node); 83 } 84 return get_list(li); 85 } 86 87 int traversetree(phuffmannode root, int level) 88 { 89 if(root==NULL) 90 return 0; 91 if(root->lchild==NULL && root->rchild==NULL) 92 return root->data*level; 93 return traversetree(root->lchild ,level+1) + traversetree(root->rchild, level+1); 94 } 95 96 void destorytree(phuffmannode root) 97 { 98 if(root==NULL) 99 return; 100 if(root->lchild==NULL && root->rchild==NULL) 101 { 102 free(root); 103 root = NULL; 104 return; 105 } 106 destorytree(root->lchild); 107 destorytree(root->rchild); 108 } 109 110 int main() 111 { 112 int count, i, data, level; 113 phuffmannode node; 114 level = 0; 115 plist head = init_list(); 116 while(scanf("%d", &count)!=EOF) 117 { 118 for(i=0;i<count;i++) 119 { 120 scanf("%d", &data); 121 node = (phuffmannode)malloc(sizeof(struct _huffmannode)); 122 node->data = data; 123 node->lchild = node->rchild = NULL; 124 add_list(head, node); 125 } 126 phuffmannode root = create_huffmannode(head); 127 printf("This huffman tree is value is:%d\n", traversetree(root, level)); 128 destorytree(root); 129 } 130 return 0; 131 }
上面是链表建树的办法，如果不建树，不用链表，仅仅为了完成这道题，今天看的方法真是帅呆了！
View Code
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int val[1001]; 5 6 int cmp(const void * a,const void * b) //when the result is true "a>b" , a is after b 7 { 8 return *(int *)a - *(int *)b; 9 } 10 11 int main() 12 { 13 int n; 14 int i; 15 int ans; 16 while(scanf("%d",&n) != EOF) 17 { 18 ans = 0; 19 for(i = 0;i < n;i++) 20 scanf("%d",&val[i]); 21 for(i = 1;i < n;i++) 22 { 23 qsort(&val[i - 1], n - i + 1, sizeof(val[0]), cmp); 24 ans += val[i - 1] + val[i]; 25 val[i] += val[i - 1]; 26 } 27 printf("%d\n",ans); 28 } 29 return 0; 30 }