#include<stdlib.h>
#define MAXSIZE 20
typedef struct TreeNode *HuffmanTree
typedef HuffmanTree ElemType
typedef struct code Code
struct TreeNode{
char c
int Weight
HuffmanTree Left,Right
}
typedef struct Heap{
ElemType Data[MAXSIZE]
int Size
int Capacity
}*MinHeap
struct code{
char c
char code[10]
}
struct TNode{
int Data
struct TNode* lchild
struct TNode* rchild
}
MinHeap BuildHeap()
{
MinHeap tmpH
tmpH=(MinHeap)malloc(sizeof(struct Heap))
ElemType Min=(ElemType)malloc(sizeof(ElemType))
Min->Weight=-1,Min->Left=Min->Right=NULL
tmpH->Size=0
tmpH->Capacity=MAXSIZE
tmpH->Data[0]=Min
return tmpH
}
int isFull(MinHeap H)
{
return H->Size>=H->Capacity
}
int isEmpty(MinHeap H)
{
return H->Size==0
}
void Insert(MinHeap H,ElemType T)
{
int i
if(isFull(H)){
printf("MinHeap is Full")
return
}
i=++H->Size
for(H->Data[i/2]->Weight>T->Weighti/=2)
H->Data[i]=H->Data[i/2]
H->Data[i]=T
}
ElemType DeleteMin(MinHeap H){
int Parent,child
ElemType min,tmp
if(isEmpty(H)){
printf("The Heap is Empty")
return NULL
}
min=H->Data[1]
tmp=H->Data[H->Size--]
for(Parent=1Parent*2<H->SizeParent=child)
{
child=Parent*2
if(child!=H->Size-1&&H->Data[child]->Weight>H->Data[child+1]->Weight)
child++
if(tmp->Weight>H->Data[child]->Weight)
{
H->Data[Parent]=H->Data[child]
}else break
}
H->Data[Parent]=tmp
return min
}
void InitHeap(MinHeap H,int n)
{
ElemType tmp
for(int i=0i<ni++)
{ getchar()
tmp=(ElemType)malloc(sizeof(ElemType))
scanf("%c,%d",&tmp->c,&tmp->Weight)
tmp->Left=tmp->Right=NULL
Insert(H,tmp)
}
}
HuffmanTree Huffman(MinHeap H)
{
int i
HuffmanTree T
for(i=1i<H->Sizei++)
{
T=(HuffmanTree)malloc(sizeof(HuffmanTree))
T->Left=DeleteMin(H)
T->Right=DeleteMin(H)
T->Weight=T->Left->Weight+T->Right->Weight
Insert(H,T)
}
T=DeleteMin(H)
return T
}
int main()
{
int n
scanf("%d",&n)
Code ans[n]
MinHeap H=BuildHeap()
HuffmanTree T
InitHeap(H,n)
T=Huffman(H)
return 0
}
哈夫曼树的构造,编码有01左右子树之分,稍微复杂
二叉树是采用递归定义的,实现起来代码简洁(也许并不简单)。并且它在具体的计算机科学中有很重要的运用,是一种很重要的数据结构,二叉树有三种遍历和建立的方式。今天先学习一下它的建立和打印。以下代码在Win-Tc1.9.1下编译通过。
#include <stdio.h>
#define ElemType char
//节点声明,数据域、左孩子指针、右孩子指针
typedef struct BiTNode{
char data
struct BiTNode *lchild,*rchild
}BiTNode,*BiTree
//先序建立二叉树
BiTree CreateBiTree(){
char ch
BiTree T
scanf("%c",&ch)
if(ch=='#')T=NULL
else{
T = (BiTree)malloc(sizeof(BiTNode))
T->data = ch
T->lchild = CreateBiTree()
T->rchild = CreateBiTree()
}
return T//返回根节点
}
//先序遍历二叉树
void PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data)
PreOrderTraverse(T->lchild)
PreOrderTraverse(T->rchild)
}
}
//中序遍历
void InOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild)
printf("%c",T->data)
PreOrderTraverse(T->rchild)
}
}
//后序遍历
void PostOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild)
PreOrderTraverse(T->rchild)
printf("%c",T->data)
}
}
void main(){
BiTree T
T = CreateBiTree()//建立
PreOrderTraverse(T)//输出
getch()
}
2. &和scanf里面的&一样是为了取地址。1. 传入二级指针是为了修改左右孩子。 createbintree(&(*t)->lchild)和createbintree(&(*t)->rchild)这里如果不用二级指针,那就只能传入左右孩子的值,无法无法修改它们的值。
一般情况下(不用引用的情况下),函数传变量的值的时候就是使用变量的值,也就是变量的一个临时拷贝;而传它的地址的时候一般是为了修改此变量(在函数内可以通过地址找到变量位置,进而修改它)。想想交换变量值的函数为什么要写成 void switch(int *a,int* b)这种形式,就能够明白了。
3. 第一个问题说这么多,第三个就可以简单地说了。void initstack(Stack st) 这种写法,是把一个外部的Stack类的变量拷贝给了st,而那个变量的确是没有初始化的,所以编译错误(应该是警告吧)。而void initstack(Stack *st)这种方式就是传进了那个变量的地址,这样就能在函数内部修改它从而对其初始化了,当然也不会提示错误了。
说这么多,不知说的是否清晰,有什么问题可以继续问