填空题

[说明]
假定用一个整型数组表示一个长整数,数组的每个元素存储长整数的一位数字,则实际的长整数m表示为:
m=a[k]×10k-2+a[k-1]×10k-3+...+a[3]×10+a[2]
其中a[1]保存该长整数的位数,a[0]保存该长整数的符号:0表示正数、1表示负数。注:数组下标从0开始。
流程图用于计算长整数的加(减)法。运算时先决定符号,再进行绝对值运算。对于绝对值相减情况,总是绝对值较大的减去绝对值较小的,以避免出现不够减情况。注,此处不考虑溢出情况,即数组足够大。这样在程序中引进两个指针pA和pB,分别指向绝对值较大者和较小者。而对绝对值相加情况,让pA指向LA,pB指向LB,不区分绝对值大小。pA±pB可用通式pA+flag*pB来计算,flag为+1时即对应pA+pB,flag为-1时即对应pA-pB。需特别注意的是,对于相减,不够减时要进行借位,而当最高位借位后正好为0时,结果的总位数应减1;对于加法,有最高进位时,结果的总位数应加1。


流程图中涉及的函数说明如下:
(1)cmp(int *LA,int *LB)函数,用于比较长整数LA与LB的绝对值大小,若LA绝对值大于LB绝对值则返回正值,LA绝对值小于LB绝对值返回负值,相等则返回0。
(2)max(int A, int B)函数,用于返回整数A与B中较大数。
另外,对流程图中的写法进行约定:(1)“:=”表示赋值,如“flag:=LA[0]+LB[0]”表示将“LA[0]+LB[0]”的结果赋给flag,相当于C中的赋值语句:“flag=LA[0]+LB[0];”;(2)“:”表示比较运算,如“flag:1”表示flag与1比较。

【参考答案】

flag:=1
carry:=0
carry:0
LC[i+1]:0
LC[i+2]:0
热门 试题

填空题
[说明] Huffman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值w1,w2,…,wn构成n棵二叉树的集合F=T1,T2,…,Tn,其中每棵树Ti中只有一个带权为wi的根节点,其左右子树均空。 ②在F中选取两棵根节点的权值较小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左右子树根节点的权值之和。 ③从F中删除这两棵树,同时将新得到的二叉树加入到F中。 重复②③,直到F中只剩一棵树为止。 函数中使用的预定义符号如下: #define INT_MAX 10000 #define ENCODING LENGTH 1000 typedef enum(none,left_chiid, right chiid Which; *标记是左孩子还是右孩子* typedef char Elemtype; typedef struct TNode Huffman树节点 Elemtype letter; int weight; 权值 int parent; 父节点 Which sigh; char *code; 节点对应编码 HTNode,*HuffmanTree; int n; char coding[50]; 储存代码 [函数] void Select(HuffmanTree HT, int end, int *s1, int *s2) *在0~END之间, 找出最小和次小的两个节点序号,返回s1、s2* int i; int min1= INT_MAX; int min2 = INT_MAX; for (i = 0; i <= end; i++) *找最小的节点序号* if((______) && (HT[i].weight < minl1)) *s1 = i; min1 = HT[i].weight; for(i = 0; i <= end; i++) *找次小节点的序号* if((HT[i].parent == 0) && (______) && (min2 > HT[i].weight)) *s2 = i; min2 = HT[i].weight; void HuffmanTreeCreat(HuffmanTree &HT) *建立HUFFMAN树* int i; int m = 2 * n - 1; int s1,s2; for(i = n; i < m; i++) Select(______); HT[s1].parent = i; HT[s2].parent = i; HT[s1].sigh = left_child; HT[s2].sigh = right_child; HT[i].weight = ______; void HuffmanTreeEncoding(char sen[],HuffmanTree HT) *将句子进行编码* int i = 0; int j; while(sen[i] != ’ 0’) for(j = 0; j < n; j++) if (HT[j].letter == sen[i]) *字母匹配则用代码取代* strcat(coding, ______); break; i++; if (sen[i] == 32) i++; printf( n%s ,coding);