当前位置:威尼斯 > jave > 【威尼斯】按树的结点的深浅,1号成分存储9

【威尼斯】按树的结点的深浅,1号成分存储9

文章作者:jave 上传时间:2019-09-29

#0 为什么称作玩具程序?
1、实现简单,也就是效率一般。
2、只具备无符号数的加、乘运算功能。

1.问题描述:

    1 .由已经给出的二叉树的先序(后序)和中序遍历的结果构造二叉树。遍历的结果以数组的方   式输入。

     2.给定任意一棵二叉树,使用队列作为辅助储存,按树的结点的深度,从根开始依次访问所有结点.

#1 如何实现
以1792为例,用数组0号元素存储2,1号元素存储9,依此类推...
下面是大整数的存储结构图。

设计用例:

威尼斯 1

                                                                                  先序:abdecfg                           中序:dbeafcg

威尼斯 2

设计代码:

#defineLEN20

typedefcharElementtype;

typedefstructTreeNode*T;

typedefstructTreeNode*Position;

typedefstructQueueRecord*Queue;

structTreeNode

{

Elementtypedata;

Positionlchild;

Positionrchild;

};

structQueueRecord

{

intCapacity;

intFront;

intRear;

intSize;

PositionnodeArr[LEN];

};

intmain() {

voidinput (char*preArr,char*midArr);

voidbuildTree(Tt,char*preArr,char*midArr,intlength);

PositioncreateNode();

voidinitQueue(QueueQ);

voidoutputQueue(QueueQ);

charpreArr[LEN],midArr[LEN];

Ttree = createNode();

Queuequeue = (Queue)malloc(sizeof(structQueueRecord));

voidtree_to_queue(Tt,QueueQ);

input(preArr, midArr);

buildTree(tree, preArr, midArr,strlen(preArr));

initQueue(queue);

tree_to_queue(tree,queue);

outputQueue(queue);

getchar(); getchar();

return;

}

voidinput(charpreArr[],charmidArr[]) {

scanf_s("%s",preArr);

scanf_s("%s",midArr);

}

voidbuildTree(Tt,char*preArr,char*midArr,intlength)//t需要有明确的指向

{

intindexOf(char*arr,charx);

PositioncreateNode();

if(0 == strlen(preArr) || 0 == strlen(midArr))

{

t=NULL;

return;

}

Ttree =t;

tree->data =preArr[0];

intindex =

indexOf(midArr,preArr[0]);

intl_length =index;

intr_length =length- 1 - index;

if(l_length >0)

{

tree->lchild = createNode();

buildTree(tree->lchild,preArr+ 1,midArr, l_length);//midArr只是用了一部分;

}

else{

tree->lchild =NULL;

}

tree =t;

if(r_length >0)

{

tree->rchild = createNode();

buildTree(tree->rchild,preArr+ l_length+1,midArr+ 1 + l_length, r_length);

}

else{

tree->rchild =NULL;

}

tree =t;

}

voidpre_travel(Tt)

{

if(t==NULL) {

return;

}

else{

printf("%c",t->data);

pre_travel(t->lchild);

pre_travel(t->rchild);

}

}

voidmid_travel(Tt) {

if(t==NULL) {

return;

}

else{

mid_travel(t->lchild);

printf("%c",t->data);

mid_travel(t->rchild);

}

}

voidtree_to_queue(Tt,QueueQ)

{

intenterQueue(QueueQ,Positionp);

intl_index,r_index;

l_index = 1;

r_index = 1;

intf=enterQueue(Q,t);

while(l_index <=r_index)

{

if(enterQueue(Q, (Q->nodeArr[l_index])->lchild))

{

r_index++;

}

if(enterQueue(Q, (Q->nodeArr[l_index])->rchild))

{

r_index++;

}

l_index++;

}

}

PositioncreateNode()

{

return(Position)malloc(sizeof(structTreeNode));

}

intindexOf(char*arr,charx)

{

intindex = -1;

for(inti = 0; i < strlen(arr); i++)

{

if(x==arr[i])

{

index = i;

break;

}

}

returnindex;

}

voidinitQueue(QueueQ) {

Q->Capacity =50;

Q->Size = 0;

Q->Front = 1;

Q->Rear = 0;//从索引1开始存储

}

intenterQueue(QueueQ,Positionp)

{

if(NULL==p) {

return0;

}

else{

Q->Size++;

Q->Rear++;

Q->nodeArr[Q->Rear] =p;

return1;

}

}

voidoutputQueue(QueueQ)

{

for(inti = 1; i <=Q->Size; i++)

{

printf("%c", (Q->nodeArr[i])->data);

}

}

存储结构定义:

树的结构:

威尼斯 3

1#defineMAXDIGITS64
2
3typedefstruct{
4intlastdigit;
5chardigits[MAXDIGITS];
6}bigNum;

队列结构:

威尼斯 4

加法实现:按位相加,再加上进位carry。两个数长度未必相同,所以高位的处理需要特别对待。
乘法实现:乘法其实是用加法来实现的,下面列出了伪码实现。

       小节:有先序(后序)+中序,但是先序+后序不能确定一棵树

1intmultiplyBigNum(bigNum*src,bigNum*dst){
2bigNumresult;
3bigNumt;
4
5foreachdigitxindst{
6somebookkeeping;
7multiplyDigit(src,x,&t);
8addBigNum(&result,&t);
9}
10
11copyBigNum(&result,src);
12
13return0;
14}

#2 除了初始化bigInt外没有 除法、求余 运算:我构造了查找表,但这也使得程序代码变得更长了。
查找表的构造过程:写几行输出代码,控制台输入输出重定向,拷贝粘帖。如果是手工的话,很可能会出错。

1unsignedcharcacheMgr[96][2]={
20,0,0,1,0,2,0,3,0,4,
30,5,0,6,0,7,0,8,0,9,
41,0,1,1,1,2,1,3,1,4,
51,5,1,6,1,7,1,8,1,9,
62,0,2,1,2,2,2,3,2,4,
72,5,2,6,2,7,2,8,2,9,
83,0,3,1,3,2,3,3,3,4,
93,5,3,6,3,7,3,8,3,9,
104,0,4,1,4,2,4,3,4,4,
114,5,4,6,4,7,4,8,4,9,
125,0,5,1,5,2,5,3,5,4,
135,5,5,6,5,7,5,8,5,9,
146,0,6,1,6,2,6,3,6,4,
156,5,6,6,6,7,6,8,6,9,
167,0,7,1,7,2,7,3,7,4,
177,5,7,6,7,7,7,8,7,9,
188,0,8,1,8,2,8,3,8,4,
198,5,8,6,8,7,8,8,8,9,
209,0,9,1,9,2,9,3,9,4,
219,5
22};

#3 阶乘运算31!,改下参数运算256!也行的, 运行时间也会长些

1intmain(){
2bigNumsrc;
3bigNumdst;
4
5makeBigNum(1,&src);
6
7for(inti=1;i<32;i++){
8makeBigNum(i,&dst);
9multiplyBigNum(&src,&dst);
10printfBigNum;
11}
12
13getchar();
14return0;
15}

威尼斯 5

#4 更多参考

显然,高精度数值运算程序库的编写可以称得上相当professional的工作!如果你想动手,最好找些帮手。有递归实现。有四则运算的完整实现。有齐全的综述。没看过,但显然里面会有权威的描述,必然会有的,哈哈。
Eric S. Roberts. Programming Abstractions in C: A Second Course in Computer Science. Addison-Wesley Educational Publishers Inc.
Steven S. Skiena Miguel A. Revilla. Programming Challenges. Springer Verlag. Ch5.2 High-Precision Integers.
Steven S. Skiena. The Algorithm Design Manual, Second Edition. Springer-Verlag. Ch13.9 Arbitrary-Precision Arithmetic.
D. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Reading MA, third edition, 1997.

#5 代码参考,拍砖请轻点下手

1#include<stdio.h>
2#include"bigInt.h"
3#defineMAXDIGITS64
4
5typedefstruct{
6intlastdigit;
7chardigits[MAXDIGITS];
8}bigNum;
9
10intmakeBigNum(intsrc,bigNum*bn){
11bn->lastdigit=-1;
12while(src!=0){
13bn->lastdigit++;
14bn->digits[bn->lastdigit]=src%10;
15src=src/10;
16}
17
18return0;
19}
20
21intprintfBigNum(bigNum*bn){
22for(inti=bn->lastdigit;i>=0;i--){
23printf("%u",bn->digits[i]);
24if(i%3==0)printf("");
25}
26
27printf("n");
28
29return0;
30}
31
32intaddBigNum(bigNum*src,bigNum*dst){
33unsignedcharcacheMgr[20][2]={
340,0,0,1,0,2,0,3,0,4,
350,5,0,6,0,7,0,8,0,9,
361,0,1,1,1,2,1,3,1,4,
371,5,1,6,1,7,1,8,1,9
38};
39
40bigNum*longNum=src;
41intshortLength=dst->lastdigit;
42if(dst->lastdigit>src->lastdigit){
43longNum=dst;
44shortLength=src->lastdigit;
45}
46intlength=longNum->lastdigit;
47
48intcarry=0;
49for(inti=0;i<=shortLength;i++){
50unsignedchart=src->digits[i]+dst->digits[i]+carry;
51src->digits[i]=cacheMgr[t][1];
52carry=cacheMgr[t][0];
53}
54
55for(inti=shortLength+1;i<=length;i++){
56unsignedchart=longNum->digits[i]+carry;
57src->digits[i]=cacheMgr[t][1];
58carry=cacheMgr[t][0];
59}
60
61if(carry==1){
62src->lastdigit=longNum->lastdigit+1;
63src->digits[src->lastdigit]=1;
64}
65elsesrc->lastdigit=longNum->lastdigit;
66
67return0;
68}
69
70//src=====>dst
71intcopyBigNum(bigNum*src,bigNum*dst){
72intlength=src->lastdigit;
73
74dst->lastdigit=length;
75
76for(inti=0;i<=length;i++)
77dst->digits[i]=src->digits[i];
78
79return0;
80}
81
82intmultiplyDigit(bigNum*src,unsignedchardigit,bigNum*t){
83unsignedcharcacheMgr[96][2]={
840,0,0,1,0,2,0,3,0,4,
850,5,0,6,0,7,0,8,0,9,
861,0,1,1,1,2,1,3,1,4,
871,5,1,6,1,7,1,8,1,9,
882,0,2,1,2,2,2,3,2,4,
892,5,2,6,2,7,2,8,2,9,
903,0,3,1,3,2,3,3,3,4,
913,5,3,6,3,7,3,8,3,9,
924,0,4,1,4,2,4,3,4,4,
934,5,4,6,4,7,4,8,4,9,
945,0,5,1,5,2,5,3,5,4,
955,5,5,6,5,7,5,8,5,9,
966,0,6,1,6,2,6,3,6,4,
976,5,6,6,6,7,6,8,6,9,
987,0,7,1,7,2,7,3,7,4,
997,5,7,6,7,7,7,8,7,9,
1008,0,8,1,8,2,8,3,8,4,
1018,5,8,6,8,7,8,8,8,9,
1029,0,9,1,9,2,9,3,9,4,
1039,5
104};
105
106intcarry=0;
107intlength=src->lastdigit;
108intx;
109
110for(inti=0;i<=length;i++){
111x=src->digits[i]*digit+carry;
112t->lastdigit++;
113t->digits[t->lastdigit]=cacheMgr[x][1];
114carry=cacheMgr[x][0];
115}
116
117if(carry>0){
118t->lastdigit=t->lastdigit+1;
119t->digits[t->lastdigit]=carry;
120}
121
122return0;
123}
124
125intmultiplyBigNum(bigNum*src,bigNum*dst){
126bigNumresult;
127bigNumt;
128
129makeBigNum(0,&result);
130
131intlength=dst->lastdigit;
132for(inti=0;i<=length;i++){
133t.lastdigit=i-1;
134for(ints=1;s<=i;s++)
135t.digits[s-1]=0;
136multiplyDigit(src,dst->digits[i],&t);
137addBigNum(&result,&t);
138}
139
140copyBigNum(&result,src);
141
142return0;
143}
144
145intmain(){
146bigNumsrc;
147bigNumdst;
148
149makeBigNum(1,&src);
150
151for(inti=1;i<32;i++){
152makeBigNum(i,&dst);
153multiplyBigNum(&src,&dst);
154printfBigNum;
155}
156
157getchar();
158return0;
159}

本文由威尼斯发布于jave,转载请注明出处:【威尼斯】按树的结点的深浅,1号成分存储9

关键词: