数据结构树的变成习题.docx
- 文档编号:8964544
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:25
- 大小:20.59KB
数据结构树的变成习题.docx
《数据结构树的变成习题.docx》由会员分享,可在线阅读,更多相关《数据结构树的变成习题.docx(25页珍藏版)》请在冰点文库上搜索。
数据结构树的变成习题
实验题目(共6题,第1题)
标题:
Huffman树
时 限:
1000 ms
内存限制:
10000 K
总时限:
3000 ms
描述:
Huffman树
对输入的英文大写字母进行统计概率然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码。
输入:
大写字母个数n
第一个字母第二个字母第三个字母... 第n个字母
输出:
字母1出现次数Huffman编码
字母2出现次数Huffman编码
字母3出现次数Huffman编码
…
字母n出现次数Huffman编码
输入样例:
10
IIUUUIUNUU
输出样例:
U61
I301
N100
提示:
参见教材144页
来源:
#include
#include
#include
#define MAX 27
#define MAX_INT 99999
typedef struct
{
int weight;
int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct Charnode
{
char c;
int weight;
} CharNode,*CharNodePtr;
CharNode *b;
int Chat_get()
{
char c;
int j=0;
int m;
int i;
scanf("%d",&m);
getchar();
b=(CharNodePtr)malloc(sizeof(CharNode)*MAX);
int a[MAX];
for(i=0; i { a[i]=0; } for(i=0; i { scanf("%c",&c); getchar(); a[c-'A']++; } for(i=0; i<26; i++) { if(a[i]! =0) { b[j].c=char(i+'A'); b[j].weight=a[i]; j++; } } return j; } int min(HuffmanTree t,int i) { int j,flag; int k=MAX_INT; for(j=1; j<=i; j++) if(t[j].weight k=t[j].weight,flag=j; t[flag].parent=1; return flag; } void select(HuffmanTree t,int i,int &s1,int &s2) { s2=min(t,i); s1=min(t,i); } void PrintHuffmanTree(HuffmanTree &HT,HuffmanCode &HC, int n) { int i, c, cdlen; char *cd; HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); c=2*n-1; cdlen=0; for(i=0; i<=c; ++i) HT[i].weight=0; while(c) { if(HT[c].weight==0) { HT[c].weight=1; if(HT[c].lchild==0 && HT[c].rchild==0) { HC[c]=(char *)malloc((cdlen+1)*sizeof(char)); cd[cdlen]='\0'; strcpy(HC[c],cd); } if(HT[c].lchild! =0) { c=HT[c].lchild; cd[cdlen++]='1'; } } else if(HT[c].weight==1) { HT[c].weight=2; if(HT[c].rchild! =0) { c=HT[c].rchild; cd[cdlen++]='0'; } } else { HT[c].weight=0; c=HT[c].parent; --cdlen; } } free(cd); } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) { int m,i,s1,s2; HuffmanTree p; if(n<=1) exit(0); m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1; i<=n; ++i,++p,++w) { (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(; i<=m; ++i,++p) (*p).parent=0; for(i=n+1; i<=m; ++i) { select(HT,i-1,s1,s2); HT[s1].parent=HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } PrintHuffmanTree(HT, HC, n); } void sort_b(int k) { int n; char c; int i,j; for(i=0; i { for(j=k-1; j>=i; j--) { if(b[j].weight>b[j-1].weight) { n=b[j].weight; b[j].weight=b[j-1].weight; b[j-1].weight=n; c=b[j].c; b[j].c=b[j-1].c; b[j-1].c=c; } } } } int main() { int k; int j; int i; HuffmanTree HT; HuffmanCode HC; k=Chat_get(); int *w; w=(int *)malloc(sizeof(int)*k); sort_b(k); for(i=0; i { w[i]=b[i].weight; } HuffmanCoding(HT,HC,w,k); for(i=0,j=1; i { printf("%c %d %s\n",b[i].c,b[i].weight,HC[j]); } return 0; } 实验题目(共6题,第2题) 标题: 从先序中序重建二叉树输出层序后序 时 限: 5000 ms 内存限制: 20000 K 总时限: 3000 ms 描述: 由树的先序和中序遍历生成树的层序遍历后序遍历 给定一个树的先序和中序的遍历结果,构建一棵树,并输出这个棵树的层序遍历和后序遍历结果 注: 这棵树的结点是由整数描述 输入: 树结点总数m 先序输出序列 中序输出序列 输出: 层序输出序列 后续输出序列 输入样例: 10 12510361371415 21051613314715 输出样例: 12356710131415 10521361415731 提示: 先序遍历的第一个输出是根结点 来源: #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 int *pre; int *in; typedef struct BiTNode { int data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree; struct SqStack { BiTree *base; BiTree *top; int stacksize; }; typedef struct QNode { BiTree data; QNode *next; }*QueuePtr; struct LinkQueue { QueuePtr front,rear; }; void LevelOrderTraverse(BiTree T); void PostOrderTraverseNonRecursive(BiTree T); void InitStack(SqStack &S); void Pop(SqStack &S,BiTree &e); void Push(SqStack &S,BiTree e); int GetTop(SqStack S,BiTree &e); int StackEmpty(SqStack S); void DeQueue(LinkQueue &Q,BiTree &e); void EnQueue(LinkQueue &Q,BiTree e); int QueueEmpty(LinkQueue Q); void InitQueue(LinkQueue &Q); BiTree restore(int *pre,int *in,int n); int main() { BiTree T; int n,i; scanf("%d",&n); pre=(int *)malloc(n*sizeof(int)); in=(int *)malloc(n*sizeof(int )); for(i=0;i { scanf("%d",pre+i); } for(i=0;i { scanf("%d",in+i); } T=restore(pre,in,n); LevelOrderTraverse(T); printf("\n"); PostOrderTraverseNonRecursive(T); free(pre); free(in); return 0; } BiTree restore(int *pre,int *in,int n) { if(n==0) return 0; BiTree p; int *rpos; int k; p=(BiTree)malloc(sizeof(BiTNode)); if(! p) { printf("out of space! \n"); exit(0); } p->data=*pre; for(rpos=in;rpos { if(*rpos==*pre) break; } k=rpos-in; p->lchild=restore(pre+1,in,k); p->rchild=restore(pre+1+k,rpos+1,n-1-k); return p; } void LevelOrderTraverse(BiTree T) { LinkQueue q; BiTree a; if(T) { InitQueue(q); EnQueue(q,T); while(! QueueEmpty(q)) { DeQueue(q,a); printf("%d ",a->data); if(a->lchild! =NULL) EnQueue(q,a->lchild); if(a->rchild! =NULL) EnQueue(q,a->rchild); } } } void PostOrderTraverseNonRecursive(BiTree T) { BiTree p; if(T==NULL) return; SqStack S1, S2; InitStack(S1); InitStack(S2); Push(S1, T); while (! StackEmpty(S1)) { Pop(S1, p); Push(S2, p); if (p->lchild ! = NULL) Push(S1, p->lchild); if (p->rchild ! = NULL) Push(S1, p->rchild); } while (! StackEmpty(S2)) { Pop(S2, p); printf("%d ",p->data); } } void InitStack(SqStack &S) { if(! (S.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree)))) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE; } int StackEmpty(SqStack S) { if(S.top==S.base) return 1; else return 0; } int GetTop(SqStack S,BiTree &e) { if(S.top>S.base) { e=*(S.top-1); return 1; } else return 0; } void Push(SqStack &S,BiTree e) { if(S.top-S.base>=S.stacksize) { S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree)); if(! S.base) exit(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *(S.top)++=e; } void Pop(SqStack &S,BiTree &e) { if(S.top==S.base) exit(0); e=*--S.top; } void InitQueue(LinkQueue &Q) { if(! (Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) exit(0); Q.front->next=NULL; } int QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear) return 1; else return 0; } void EnQueue(LinkQueue &Q,BiTree e) { QueuePtr p; if(! (p=(QueuePtr)malloc(sizeof(QNode)))) exit(0); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; } void DeQueue(LinkQueue &Q,BiTree &e) { QueuePtr p; if(Q.front==Q.rear) exit(0); p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); } 实验题目(共6题,第3题) 标题: 由顺序方式存储的完全二叉树进行重建 时 限: 1000 ms 内存限制: 3000 K 总时限: 3000 ms 描述: 按顺序方式存储的一棵完全二叉树的结点记录,结点个数为n。 根据所输入的顺序结构的结点记录建立二叉树,输出树的先序,中序和后序遍历结果。 注: 数字“0”表示不存在此结点,没有孩子结点 输入: 树结点个数n 顺序方式存储的完全二叉树 输出: 先序遍历输出 中序遍历输出 后序遍历输出 输入样例: 10 1 2 0 3 4 0 0 5 6 7 输出样例: 1235647 5362741 5637421 提示: 数字“0”的孩子结点全部为“0” 来源: #include #include typedef struct _TreeNode { int key; struct _TreeNode *LC; struct _TreeNode *RC; }TreeNode; void CreatFromSqList(TreeNode* &node,int *array,int i,int n) { if(n<=0) exit(0); if(i>n) exit(0); if(array[i]! =0) { node=(TreeNode*)malloc(sizeof(TreeNode)); node->key=array[i]; node->LC=NULL;node->RC=NULL; if(2*i<=n) CreatFromSqList(node->LC,array,2*i,n); if((2*i+1)<=n) CreatFromSqList(node->RC,array,2*i+1,n); } return; } int RepreOrder(TreeNode *T) { if(T) { printf("%d ",T->key); RepreOrder(T->LC); RepreOrder(T->RC); } return 0; } int ReInOrder(TreeNode *T) { if(T) { ReInOrder(T->LC); printf("%d ",T->key); ReInOrder(T->RC); } return 0; } int RePostOrder(TreeNode *T) { if(T) { RePostOrder(T->LC); RePos
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 树的变成习题 变成 习题
![提示](https://static.bingdoc.com/images/bang_tan.gif)