C to Java 自动自动转换转换转换系统系统系统中中C 指针的实现
严忠林
(上海师范大学信息与机电工程学院，上海 200234)
摘 要：C 指针的处理是C to Java 代码自动转换系统中一个重要而困难的问题。已有的方法大多不能处理含有技巧的指针代码，转换生成的代码难以理解，往往无法正确执行。基于此，提出一种可用Java 实现C 指针所有功能的方案，该方案在类型转换后不改变原程序结构，并保持尽可能高的运行效率。示例分析表明，运用该方法可使各种类型的C 指针运用都能自动转换为执行正确、结构清晰、修改方便、运行快捷的Java 代码。
关键关键词词：程序语言转换；C 指针；Java 引用；数据布局模型；类型转换
Realization of C Pointer
in C to Java Automatic Transformation System
YAN Zhong-lin
(College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai 200234, China)
【Abstract 】How to deal with C pointers is an important and difficult issue in C to Java automatic program transformation System. The existing methods are powerless for ingenious C codes. It is difficult to understand codes generated by some transformation system. These codes are not always correct. This paper presents a set of methods. They implements all the functions of C pointer by Java. This transformation keeps original program structure, and runs as fast as possible. Using it can automatically convert various C pointer applications into correct, clear, changeable and efficient Java code.
【Key words 】program language transformation; C pointer; Java reference; data layout model; type conversion
DOI: 10.3969/j.issn.1000-3428.2011.16.021
计 算 机 工 程 Computer Engineering 第37卷 第16期
V ol.37 No.16 2011年8月 August 2011 ·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)16—0062—03 文献标识码文献标识码：：A 中图分类号中图分类号：：TP311
1 概述
Java 是现代许多应用系统开发的首选平台。C 语言长久
以来已积累了大量优异代码，在Java 开发中如能妥善利用，
将非常有益于降低成本、提高效率和保证质量。通过程序语
言转换系统完成C to Java 代码的自动转换，是利用这些资源
最直接、有效的方法，由此获得的代码既可直接运行，也可
作进一步开发的基础。实现这种转换的最大障碍是对C 程序
中指针的处理。Java 仅提供简单的引用操作。而指针却是C
语言中最灵活的数据类型，在程序中用法巧妙、多样。追求
高效、灵活的代码一般都离不开指针，它们往往是最有价值、
项目开发时最期望获得的部分。但要将各种巧妙的指针运用
通过软件自动转换为等效的Java 代码，却是一件相当困难的
任务[1]。为此，本文提出一种用Java 实现C 指针所有功能的
方案，该方案在类型转换后不改变原程序结构，并能保证运
行高效。 2 C 指针指针的的特性 每个C 指针都有地址和类型双重属性。除了用于确定内存单元，地址还表示数据间的位置关系，可作加减、比较等运算。类型则决定了所访问单元的字节数和对其中二进制位的解释方法。需要时类型可强制转换，甚至能化作整数。这些特性意味着在程序中C 指针实际上可指向任何单元，按任
意类型模式处理其中的二进制位。这种超强能力结合程序员
对数据在内存中排列的准确掌控，能衍生出许多精妙的指针
运用。此外，C 语言还提供了极灵巧的指向函数的指针。
示例1是一段取自于实际系统的代码，struct Obj 是由多个嵌套成员构造的结构体，组成一个三维数组coll 。由于经常要对其中部分数据进行求和、求极值等运算，因此开发一个通用且高效的函数iter()。利用它，语句(1)对从coll[i][j][0]开始的N 个对象的x 求极值，语句(2)对数组中所有对象的y 求总和。代码只有4行，实现非常简练，但要转换为等效的Java ，显然不太容易。 示例1 struct Obj {… double y,z; struct Attr {… double w, x; } attr; } coll[L][M][N]; double sum(double x, double y){return x+y;} double max(double x, double y){return x>y?x:y;}
double iter(int n, double *d, double (*f)(double, double)){
double r=*d;
struct Obj *t=(struct Obj *)d;
while (--n>0) r=f(*(double *)(++t), r);
return r;
}
a=iter(N, &coll[i][j][0].attr.x, max); (1)
a=iter(L*M*N, &coll[0][0][0].y, sum); (2) 基金项目基金项目：：上海市教委基金资助项目(05DZ14) 作者简介作者简介：：严忠林(1964－)，男，讲师、硕士，主研方向：Java 应用，软件转换技术
收稿日期收稿日期：：2011-01-15 E-mail ：yan-zl@https://www.doczj.com/doc/b314489807.html,
第37卷 第16期 63
严忠林：C to Java 自动转换系统中C 指针的实现 已有的代码自动转换系统，如c2j 、C To Java Converter 、
Jazillian [2]等，在指针处理上大多仅作一些简单变换。如将*p
转换成p ，用p.x 替换p->x ；有时也用数组引用a 加下标i
来代替指针p ，这样p++就变成了i++，*p 可改写为a[i]。很
明显，这些方法仅能应付最基本的指针运用，对稍有技巧的
代码无能为力。也曾出现过一些复杂方案，如把所有变量都
分配在一个Object[]中，或专门定义一些能包容各类型数据，
描述它们嵌套关系的数据块类来支持指针运算[3]。它们能转
换更多的代码，但会破坏原程序的数据表示，给理解、修改
代码带来困难。而且依然存在着无法处理的C 指针应用。
本文提出的转换方案支持C 指针的所有功能，并尽可能
保持原程序的数据表示。数组用相同结构的Java 数组代替；
struct/union 型变量在定义相应的类后，用类实例表示；基本
类型变量保持不变，但需要通过指针访问的基本型变量，转
换为自定义的包装类的类实例；只有指针型变量要用到新的
数据类型，要为它引入反映位置关系的地址概念，并提供进
行数据访问、加减比较、类型转换等各种操作的能力。
3 变量位置变量位置关系的关系的关系的表示表示
指针的地址属性反映了程序运行时各数据在内存中的分
布。对复合数据，C 语言根据类型有不同的排列规则。数组
元素按下标顺序，无空隙地“连续”排列，用指针可方便地
遍历。struct 元素按定义的次序“顺序”排列，各元素距起始
位置有固定偏移量。union 最特殊，每个元素“重合”排列，
访问不同成员实际处理的是同一个二进制串。C 语言还规定
指向数组、struct 的指针指向它们首元素所在的位置，运行时
可转换为首元素类型的指针。许多指针代码的编写都依赖于
这些C 语言特有的数据布局模型[4]。
为在Java 中表示这些位置关系，专门定义了类Location 。
它采用“顶层数据块引用(Object base)+距顶层块起始位置的
偏移量(int offset)”来表示变量地址。顶层块可嵌套包含其他
构造块，各成员的位置关系用offset 表示。它按C 规则确定，
数组内元素由其下标推算，struct 中成员按定义次序确定，
union 的各成员总是与其首元素相同。在与struct 对应的类定
义中还有描述其全部成员组成的类变量，帮助实现成员和
offset 间的映射。对于Java 中没有对应结构的union ，通过定
义包含各成员的类来实现，并在对象中设置专门变量，记录
当前有效数据的对应情况。存取时参照该信息，如不一致，
就作必要的转换，确保总能获得正确的数据。
有时，要知道不属于同一顶层块的各变量间的位置关系，
或者要将一指针转化为整数，这都要求确定顶层数据块base
的起始地址。在与实现无关的程序中，该数值的实际大小是
无关紧要的，只需保证运行时不变，以后反转过来仍可得到
原对象即可。因此，在Java 中为有如此需求的base 任意指定
一整数区间作为其存储空间，该整数可以是除0以外的任何
值，但不和已分配的区间冲突。用一个键/值对记录这种对应
关系，为防止妨碍Java 自动回收无用对象，要使用弱引用
(Weak Reference)来连接base 。再用一容器保存所有的键/值
对，需要时既可从中获得base 对应的地址，也可作逆转换，
由地址求得对应的base +offset 。在这里，整数0仍然表示空
指针。这样，用base+offset 可完整地表示C 指针的位置信息，
Java 运行时可据此访问需要处理的数据。
4 强制强制类型转换类型转换类型转换的处理的处理
C 指针允许强制类型转换，它不改变指针所指向的位置，
但会导致+、-等运算处理的改变，其中最关键的是由*操作符
引起的存取操作。例如，任意指针转换为浮点数指针，就是要按照浮点数的阶码+尾数格式处理它所指向的字节块，而不管它本来的意义。因此，强制类型转换可以基于字节块实现，将原本任意类型的数据当作字节块，再转为需要的类型。 这种处理用Java 实现是低效的，但C 程序一般不会做毫无道理的转换。例如，程序中如要将指向结构体的指针转换为整数指针，该结构体的首元素通常就是一整数。这种转换不需特别处理，利用原有的位置信息就能得到希望的数据。因此，基于字节块的转换应尽量延迟。 如确有必要作这种转换，由base+offset 可获得相应数据，进而得到需要的字节，问题的关键是能按照不同类型对其进行正确的访问处理。对于基本数据类型指针，使用JavaAPI 就可直接实现。对于各种struct/union 型指针，要为每个类型定义一接口，其中包含成员存取、整体复制等C 程序对该型变量所有可能的操作。然后用Java 的Proxy 创建实现该接口的动态代理类。它对任一字节块，根据类型结构信息，用相应位置的字节数据来实现这些方法。通过这一接口，任何数据块，都可当作该struct/union 型变量使用，指向任意字节块的指针当然也都可转换为该类型的指针。类似地，对记录位置信息的Location 类，也定义一接口，参照整数和base+offset 间的关系作相似处理，这样，任意数据都可强制转换为指针，多级指针的处理也就实现了。指向数组的指针比较特别，使用*运算符，获得的是指向其下一维元素的指针，这本身就是一次指针类型转换。因此，对数组型指针不需特别处理，只要等到使用时再转换为需要的类型即可。综上所述，各种类型指针的强制转换都是可以实现的。 5 函数指针函数指针的的支持 C 语言中还有指向函数的指针，利用它能在运行时动态指定被调用的函数，给程序带来很大灵活性。但Java 代码中方法名必须在编程时确定，Java 中可以灵活处理的只有对象。为此，为每一类函数指针定义一个以调用该类型函数作为唯一方法的接口，再为相应函数定义并实例化一个以调用该函数来实现此接口的内部类对象。生成的函数指针类是通用指针类的子类，仍用base+offset 表示，但它的offset 永远为0，base 则在运行时动态地指向需调用函数的内部类对象，C 代码中利用指针执行的函数调用全都通过它完成。而赋值复制、等否比较、与整数相互转换等其他指针运算通过继承就可实现。如此处理，C 代码中的函数指针就得到了完全支持。 6 高效指针类高效指针类的的实现 代码转换时对遇到的各种指针类型都生成一个Java 类。因为所有指针都可转换为void *型指针，所以将它作为所有指针类的父类。这些类实现了所有的指针运算，包括存取所指单元、进行加减、比较、复制、转换等操作。 利用base+offset 信息，可完成所有的指针功能，但它的运行效率不高。程序中的指针操作，绝大多数可用更简单的方法实现。比如访问单个对象或对象内的固定成员，只要指出对象名或者再加上成员名即可，访问数组中元素也只要给出数组名和下标。这些操作都可以用Java 原生的访问方法直接快速地完成。为此，在指针类的实现中，通过一个私有内部类对象来具体完成指针操作。该对象有多种变体，有基于Java 原生方法的，遇到不能实现的运算，它们将抛出异常。也有基于base+offset 进行处理的。这个对象在运行时可进行切换。在初始构造时，生成的是基于原生方法的对象，期望尽可能简单快速地完成运算。只有在遇到无法完成的操作抛
64 计 算 机 工 程 2011年8月20日
出异常时，才会动态转换为基于base+offset 的对象。因此，
大多数情况下自动转换生成的代码相比于最快速直接的代
码，只多了这一内部类对象的间接，仍然能高效地完成。只
有在发生强制类型转换、对指向非数组元素的指针进行加减、
数组下标加减后出界、访问的union 成员不是有效成员等特
殊情况，才会使用基于base+offset 的方法。一般程序中这些
情况是很少发生的。
基于base+offset 进行的指针操作仍可设法提高效率。这
种操作首先要将base+offset 映射为相应的对象+域名或数组+
下标，然后进行存取。这一过程最慢的步骤是在求得域名后，
对对象成员的访问。Java 访问对象成员最直接的方法是通过
“对象·域名”进行，但其中的域名必须在编程时即已确定。
而在这里，域名不可能事先知道，因此只能使用慢速的“反
射(Reflection)”机制来实现。笔者做过测试，这2种方法速
度相差近百倍。如能避免使用反射，就可大大提高速度。但
另一方案要求域名事先已嵌入在类代码中，本文的解决方案
是自定义一个类装载器，能在运行时根据求得的域名即时生
成进行相应数据存取的类代码[5]。这只要在预定义的类代码
模板的常量池(Constant_Pool)中插入求得的域名串，并修改
与类型相关的2条bytecode 指令就可以了，它的生成速度很
快。用它构造对象，就可实现希望的快速数据访问。这样，
通过在bytecode 层面上的工作，即使是基于base+offset 的指
针操作，也能有较高的运行效率。
采用以上方法，可以用Java 类提供C 指针的所有功能。
对于采用了各种技巧的C 指针代码，它都能正确有效地进行
自动转换。示例2就是前面示例1中C 函数的转换结果，这
是以前的转换软件难以完成的。
示例2
static double iter(int n, P$double d, P$$$double$$double$$double
$$$ f){
double r=d.get();
P$Obj t=new P$Obj(P$Obj.cast (d));
while (--n>0) r=f.call(P$double.cast (t.mov(1)).get(), r); return r; } 7 结束语 本文介绍的转换方法，正确实现了C 指针的所有功能，使使用者无需担心转换获得的代码的可运行性和可靠性。只要原始的C 代码正确，就能生成可靠的Java 程序。使用者可以集中精力于更值得关注的地方，高效率地工作。这种转换尽可能保留了原代码的表示形式。除了指针类外，几乎没有引入新的数据结构。指针类的命名和方法调用，程序员可以很快熟悉。指针操作的底层代码封装于独立包中，除了struct/union 的对应类需要添加一些访问方法和结构信息外，原C 程序和新的Java 程序基本保持一一对应关系，非常便于阅读、理解，有利于作进一步的开发和人工优化。 转换获得的代码的运行效率，也是尽力追求的目标。由于内部机制不同，Java 代码不可能达到C 指针那样的效率，但这种差别应在合理范围内。这里生成的代码尽可能采用了Java 的原生方法，仅在别无他法的情况下才进行复杂处理，避免了“反射”等慢速操作。所以，从总体上看，自动生成的代码仍能高效率运行，其速度接近于Java 机制的极限。 运用本文方法，过去难以处理的各种类型的C 指针运用，都能自动转换为Java 代码。本文实现的指针类考虑了最困难的情况，虽然进行了很好的封装，但内部毕竟是复杂的。现实中，在人工指导下，很多元素都可以简化，如何使其能便捷高效地进行，是下一步工作的重点。 参考文献 [1] 孙洪浩, 王树义, 林晓斌, 等. 过程间指针分析算法的改进[J]. 计算机工程, 2009, 35(1): 90-92. [2] Jazillian Inc.. Jazillian[EB/OL]. (2010-07-10). http://www.jazillian. com/. [3] Demaine E D. C to Java: Converting Pointers into References[J]. Concurrency: Practice and Experience, 1998, 10(11-13): 851-861. [4] Prata S. C Primer Plus[M]. 5版. 云巅工作室, 译. 北京: 人民邮电出版社, 2005. [5] Lindholm T, Yellin F. The JavaTM Virtual Machine Specification [EB/OL]. (2010-07-10). https://www.doczj.com/doc/b314489807.html,/docs/ books/jvms/. 编辑 索书志~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (上接第61页)
改进后的XL 算法去除的冗余方程个数大于24||m D C T ?，减少的比例大于： 2424||1||(1)m D n D C T m mC T n n ???=? 对于给定的超定二次方程组来说，在变量个数不变的情况下，给出的方程越多，改进后的算法效果越明显。特别地，当方程个数m 接近变量个数2n C 时，扩展后方程个数减少近一半，用高斯消元法求解的计算复杂性降到原来的0.519ω≈%。 5 结束语 目前，XL 算法仍是求解多元二次方程组的典型方法之一，对该算法进行改进从而降低求解方程组的计算复杂性对代数攻击研究具有重要意义。本文从XL 算法产生方程的冗余问题出发，对XL 算法进行了改进，当给出的方程个数远小于单项式个数时，改进的效果并不明显，但当给出的方程个数接近于单项式个数时，改进后的算法的计算复杂性可降低到原来的1/5。 参考文献
[1] Faugere J C, Joux A. Algebraic Cryptanalysis of Hidden Field Cryptosystems Using Gr?bner Bases[C]//Proc. of CRYPTO’03.
Berlin, Germany: Springer-Verlag, 2003: 44-60.
[2] Kipnis A, Shamir A. Cryptanalysis of the HFE Public Key Crypto-
system[C]//Proc. of Crypto’99. [S. l.]: Springer-Verlag, 1999:
19-30.
[3] Courtois N, Patarin J, Shamir A, et al. Efficient Algorithms for
Solving Overdefined System of Multivariate Polynomial Equa-
tions[C]//Proc. of Eurocrypt’00. Berlin, Germany: Springer-Verlag,
2000: 392-407.
[4] Coppersmith D, Winograd S. Matrix Multiplication via Arithmetic
Progressions[J]. Journal Symbolic Computation, 1990, 9(3):
251-280.
[5] Courtois N T, Pieprzyk J. Cryptanalysis of Block Ciphers with
Overdefined Systems of Equations[C]//Proc. of ASIACRYPT’02.
Berlin, Germany: Springer-Verlag, 2002: 267-278.
[6] 左鑫平, 李俊全. 一种改进的XL 算法[J]. 计算机工程, 2008,
34(19): 157-159. 编辑 任吉慧
严忠林：C to Java自动转换系统中C指针的实现
第37卷第16期 1
栈的应用：C实现简单计算器（表达式的计算） 作为栈的著名应用，表达式的计算可以用下面方法实现： 首先建立两个栈，操作数栈NUM_S和运算符栈OPR_S。 其中，操作数栈用来存储表达式中的操作数；运算符栈用来存储表达式中的运算符。可以用字符‘=’来表示表达式结束符。 自左至右的扫描待处理的表达式，并假设当前扫描到的符号为W，根据不同的符号W 做如下不同的处理： 1.若W为操作数，则将W压入操作数栈NUM_S，且继续扫描下一个字符； 2.若W为运算符，则根据运算符的性质做相应的处理： （0）若符号栈为空，无条件入栈当前指针指向的字符 （1）若w为不大于运算符栈栈顶的运算符，则从操作数栈NUM_S中弹出两个操作数，设先后弹出的操作数为a、b，再从运算符栈 OPR_S中弹出一个运算符，比如为+，然后作运算a+b,并将运算结果压入操作数栈NUM_S。 （2）若w为左括号或者运算符的优先级大于运算符栈栈顶的运算符，则将运算符W 压入运算符栈OPR_S，并继续扫描下一个字符。 （3）若运算符W为右括号，循环操作（设先后弹出的操作数为a、b，再从运算符栈OPR_S中弹出一个运算符，比如为+，然后作运 算a+b, 并将运算结果压入操作数栈NUM_S），直到从运算符栈中弹出第一个左括号。 （4）若运算符W为表达式结束符‘=’，循环操作（设先后弹出的操作数为a、b，再从运算符栈OPR_S中弹出一个运算符，比如为 +，然后作运算a+b, 并将运算结果压入操作数栈NUM_S），直到运算符栈为空为止。此时，操作数栈栈顶元素即为表达式的 值。 ====================================================================== === 举例：计算3+(5-2*3)/4-2= （1）开始栈为空，3入栈，+入栈，（无条件入栈，5入栈，-号优先级比（高，所以-号入栈，2入栈，*优先级比目前栈顶的-号优先级高，所以*入栈，3入栈，接着扫描到）括号，）括号不入栈 | | | | --------- ---------- | 3 | | * | --------- ---------- | 2 | | - |
自动电源转换系统解决方案 atmt自动电源转换开关不仅提供双电源转换系统，还提供“两进线一母联”的进线电源转换系统，更可以提供独一无二的三电源转换系统。 atmt自动电源转换开关符合iec60947-1、iec60947-2 、 iec60947-6-1、gb14048.1-2008（总则）、gb14048.2-2008（断路器）、gb14048.11-2008（自动转换开关）。630a-6300a自动电源转换开关污染等级符合iec 60664-1 4级，已通过各种极限大气环境条件的实验，可以运行在iec 947规定的工业环境中，污染等级达到四级，建议安装在无过多灰尘且温度适宜的开关柜中。其电气和机械特性适用于环境温度-5ºc~+70 ºc，贮存条件是-25 ºc ~+85 ºc ，-35 ºc时可确保合闸。在emc 电磁兼容性方面，静电放电符合iec 61000-4-2，level2标准；射频电磁场-辐射抗扰度符合iec 61000-4-3 ，level3标准；电快速瞬变脉冲符合iec 61000-4-4，level3标准；浪涌冲击符合iec 61000-4-5，level4标准；射频电磁场-传导抗扰度符合iec 61000-4-6，level3标准。 atmt电源级自动转换开关由控制器、适配器和执行断路器构成。执行断路器选用masterpact mt或者mte抽屉式空气断路器，2台或3台断路器分别加装适配器。电源状况经适配器采样，控制器通过控制连接线与适配器连接，实现对供电电源的检测，通过可编程的操作流程完成电源间的转换。其中，控制器完成对常用电源、备
自动电源切换系统))维修指导ATS(自动电源切换系统 2008年5月
目录 ATS介绍及接线说明 ATS送电前常规检查 ATS技术操作规程 ATS常见故障及处理
ATS按采样电压等级可分为220V和380V两种. 按使用类型可分为UA系统和BA系统两种，UA适用于一路市电(N)和一路柴油发电机(R)，BA适用于两路市电。 ATS共由三部分组成: BA(UA)控制器,ACP，IVE，电源切换系统.
电源切换系统由下列组成： 断路器QN 带电动机构和辅助开关与主电路相连 断路器QR 带电动机构和辅助开关与主电路相连 安装和连锁用底板 电气连锁单元 IVE 电源切换系统 ACP 控制器
BA 控制器AC220V 接线方式: P25M(N)断路器: 端子1: 接常用电源中性线 端子5: 接常用电源相线P25M(R)断路器: 端子1: 接备用电源中性线端子5: 接备用电源相线 UA UA控制器控制器控制器AC220V AC220V 接线方式(A=0, (A=0, 无缺相保护无缺相保护无缺相保护))时接线方式同上
BA BA控制器控制器控制器AC380V AC380V AC380V接线方式接线方式接线方式: : P25M(N)P25M(N)断路器断路器断路器: : 端子端子1: 1: 1: 接常用电源相线接常用电源相线 端子端子5: 5: 5: 接常用电源相线接常用电源相线P25M(R)P25M(R)断路器断路器断路器::端子端子1: 1: 1: 接备用电源相线接备用电源相线端子端子5: 5: 5: 接备用电源相线接备用电源相线UA UA控制器控制器控制器AC380V AC380V (A=0, (A=0, 无缺相保护无缺相保护无缺相保护))时接线方式同上同上. .
目录 题目一.二叉树操作（1）二.算术表达式求 (1) 一、课程设计的目的 (1) 二、课程设计的内容和要求 (1) 三、题目一设计过程 (2) 四、题目二设计过程 (6) 五、设计总结 (17) 六、参考文献 (18)
题目一.二叉树操作（1）二.算术表达式求 一、课程设计的目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。 （1）题目一的目的： 1、掌握二叉树的概念和性质 2、掌握二叉树的存储结构 3、掌握二叉树的基本操作 （2）题目二的目的： 1、掌握栈的顺序存储结构和链式存储结构 2、掌握栈的先进后出的特点 3、掌握栈的基本运算 二、课程设计的内容和要求 （1）题目一的内容和要求： 1、编写已知二叉树的先序、中序序列，恢复此二叉树的程序 2、编写求二叉树深度的程序 （2）题目二的内容和要求： 1、算术表达式由操作数、运算符和界限符组成。操作数是正整数，运算符为 加减乘除，界限符有左右括号和表达式起始 2、将一个表达式的中缀形式转化为相应的后缀形式 3、依据后缀表达式计算表达式的值
三、题目一设计过程 1、题目分析 现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！ 由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后返回其中大的那个值加一，则求出数的高度。这里用递归实现！ 2、算法描述 main ( )（主函数） 先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。 void CreateBiTree(BiTree *T,char *pre,char *in,int len)（由先序序列和中序序列构造二叉树） 根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序列为左子树, 后边的序列为右子树。设根前边有n个元素，则又有, 在前序序列中，紧跟着根(root)的n个元素序列(即pre[1...n]) 为左子树, 在后边的为右子树，而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为pre[1...n]), 中序序列为in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现！ int Depth(BiTree T)（求树的深度） 当所给的参数T是NULL时，返回0。说明这个树只有一个叶子节点深度为0，当所给的参数不是NULL时，函数调用自己看看这个参数的左分支是不是NULL，
实验名称栈的基本操作 实验目的 掌握栈这种抽象数据类型的特点及实现方法。 实验内容 从键盘读入若干个整数，建一个顺序栈或链式栈，并完成下列操作： （1）初始化栈； （2）判栈为空； （3）出栈； （4）入栈。 算法设计分析 （一）数据结构的定义 struct stackNode{ int data; struct stackNode *nextPtr; }; typedef struct stackNode listStact; typedef listStact *stackNodePtr; （二）总体设计 程序由主函数、入栈函数，出栈函数，删除函数判官是否为空函数和菜单函数组成。 （1）主函数：调用各个函数以实现相应功能
（三）各函数的详细设计： Function1: void instruct() //菜单 （1）：使用菜单显示要进行的函数功能； Function2：void printStack(stackNodePtr sPtr) //输出栈 （1）：利用if判断栈是否为空； （2）：在else内套用while（头指针不为空条件循环）循环输出栈元素； Function3：void push(stackNodePtr *topPtr,int value //进栈 （1）：建新的头指针； （2）：申请空间； （3）：利用if判断newPtr不为空时循环进栈 （4）：把输入的value赋值给newPtr，在赋值给topPtr，再指向下一个位置； Function4：int pop(stackNodePtr*topPtr) //删除 （1）：建新的头指针newPtr； （2）：利用if判断newPtr是否为空，再删除元素。 （3）：把topPtr等于newPtr，把头指针指向的数据赋值给topValue，输出要删除的数据值，头指针指向下一个位置，并清空newPtr； （4）：完成上述步骤后，return toPvalue，返回；
收稿日期:2009-07-17作者简介:刘 庭(1977-),男,安全技术及工程专业硕士,主要从事电源系统设计及安全性研究。 文章编号:1009-3664(2009)06-0057-03技术交流 双电源自动转换开关的选用 刘 庭 (北京中网华通设计咨询有限公司,北京100027) 摘要:双电源系统是重要电力负荷安全运行的有效保障,而电源转换开关是连接两个电源的重要枢纽。由于双电源自动转换开关(A T SE)具有使用安全、转换迅速、无需值守的特点,近年来得到了广泛的应用。新建双电源系统基本都选用A T SE,一些早期的双电源系统也逐步将手动转换开关改造成了A T SE 。因电源系统容量、接地形式的不同,在对A T -SE 选型时也有所不同。文中阐述了A T SE 的概念、分类、性能特点以及为交换局双电源系统选择A T SE 时应考虑的因素,重点分析了三极开关和四极开关的适用范围和选择依据,并通过工程实例予以说明。 关键词:双电源;自动转换开关;三极开关;四极开关;安全中图分类号:T M 930.1文献标识码:A Selection of A utomat ic Transfer Sw itching Equipment for Dual Pow er Supply LI U T ing (Beijing China Co mmunication Design and Consulting Co.,L td.Beijing 100027,China) Abstr act:System of dual pow er supply is the effective guar antee o f safety operatio n fo r some impor tant po wer users.Pow er t ransfer switch is an impor tant co nnecting device betw een tw o po wer supplies.Recently,automatic transfer sw itc -hing equipment (A T SE)is widely a pplied because of its safety ,fast switching and w ithout man on dut y.Selectio n of A T SE is different because t he capacity and g ro unding for m o f po wer supply are different.In this paper,the definitio n,classifica -t ion and characterist ics o f A T SE are descr ibed and factor s influencing it s applicatio n in ex changing bur eaus are consider ed.T he application scope and gist o f three -pole and four -pole sw itch are emphasized with an engineer ing ex ample. Key wo rds:dual po wer supply;A T SE;thr ee -pole swit ch;four -pole sw itch;safety 0 概 述 根据5供配电系统设计规范6(GB 50052-1995)的 有关规定:/电力负荷根据对供电可靠性的要求及中断供电在政治、经济上所造成的损失或影响分为一级、二级和三级0,/一级负荷应由两个电源供电,当一个电源发生故障时,另一个电源应不致同时受到损坏0。根据这一规定,通信交换局的供电负荷属于一级负荷。通信行业标准5通信电源设备安装工程设计规范6(YD/T 5040-2005)4.1.1条也规定/市电发生异常情况时,为保证仍能对通信负荷和重要动力负荷可靠供电,应配置自备发电机组为自备电源。0电源转换开关是连接双电源的纽带,既要保证在双电源之间进行及时、准确地切换,又要防止双电源同时并列运行。5通信电源设备安装工程设计规范63.1.2条规定/低压市电间切换、市电与油机之间的切换应采用具有电气和机械联锁的切换开关。0 目前,各电信运营商早期局房大都配备了手动转换开关。近年来,随着配电自动化水平的提高,部分局房将手动转换开关更换成了自动转换开关,而各地后 期新建的局房(综合楼)也大多采用了自动转换开关,以减少维护工作量,提高供电安全系统。 自动转换开关电器(Auto matic tr ansfer sw itching equipment)简称为AT SE,有时也简称为AT S 。它由一个(或几个)转换开关电器和其它必需的电器(转换控制器)组成,用于检测电源电路,并将一个或多个负载电路从一个电源转换至另一个电源的自动电器。当存在常用电源和备用电源两个电源的情况时,AT SE 应指定一个常用电源位置,其操作程序则由两个自动转换过程组成。如果常用电源被检测到出现偏差时,则自动将负载从常用电源转换至备用电源;如果常用电源恢复正常时,则自动将负载返回换接到常用电源。换接时间可有预定的延时或无延时,并可处于一个断开位置。ATSE 主要适用于交流不超过1000V 的紧急供电系统。 表1 手动转换开关和自动转换开关综合比较表序号比较项目手动转换开关 自动转换开关 1结构简单复杂2可靠性很高较高3反应时间慢极快4自动化水平低高 5价格低较高 6 应用场合 任意 1000V 以下的供电系统 手动转换开关和自动转换开关各有其优缺点,其 # 57#
详解堆栈的几种实现方法——C语言版 基本的抽象数据类型（ADT）是编写C程序必要的过程，这类ADT有链表、堆栈、队列和树等，本文主要讲解下堆栈的几种实现方法以及他们的优缺点。 堆栈（stack）的显著特点是后进先出（Last-In First-Out, LIFO），其实现的方法有三种可选方案：静态数组、动态分配的数组、动态分配的链式结构。 静态数组：特点是要求结构的长度固定，而且长度在编译时候就得确定。其优点是结构简单，实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制，适用于知道明确长度的场合。 动态数组：特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活，缺点是由此会增加程序的复杂性。 链式结构：特点是无长度上线，需要的时候再申请分配内存空间，可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存，在链式结构中访问一个特定元素的效率不如数组。 首先先确定一个堆栈接口的头文件，里面包含了各个方案下的函数原型，放在一起是为了实现程序的模块化以及便于修改。然后再接着分别介绍各个方案的具体实施方法。 堆栈接口stack.h文件代码： [cpp]view plaincopy 1./* 2.** 堆栈模块的接口 stack.h 3.*/ 4.#include
C语言用栈实现进制转换 #include
使用C++中STL的stack，只有C++中有，C标准库没有STL。 程序：（单整数） #include
220kVXX变电站站用电系统培训 一、站用电系统供电方式 我站站用电系统分为两套，保护小室一和主控室各一套，保护小室一站用电系统电源为35kV3号站用变及35kV4号站用变供电，其中35kV3号站用变0.4kV侧进线为常用电源，35kV4号站用变0.4kV侧进线为备用电源；主控室站用电系统电源为35kV1号站用变及35kV2号站用变供电，其中35kV1号站用变0.4kV侧进线为常用电源，35kV2号站用变0.4kV侧进线为备用电源。 正常运行情况下，380V/220V馈电线路为常用电源（即35kV1号站用变、35kV3号站用变）供电。 二、站用电系统原理图
主控室站电用正常运行时： 400V Ⅰ段交流进线屏4011、4022开关合位，QS1 双电源自动转换开关在“常合”位置，380VⅠ段母线由35kV1号站用变供电。 400V Ⅱ段交流进线屏4012、4021开关合位，QS2 双电源自动转换开关在“常合”位置，380VⅡ段母线由35kV1号站用变供电。 保护小室一站用电正常运行时： 400V Ⅰ段交流进线屏4031、4042开关合位，QS3自动转换开关在“N 闭合”位置，380VⅠ段母线由35kV3号站用变供电。 400V Ⅱ段交流进线屏4032、4041开关合位，QS3自动转换开关在“N 闭合”位置，380VⅡ段母线由35kV3号站用变供电。 三、ATS自动转换开关原理
主控室站用电系统采用青岛施耐德成套设备有限公司生产的型号为DSMQ1-800/4P 800A 双电源ATS自动转换开关，主要由两台具有高分断能力的SMD1系统断路器及ATS控制器等组成。具有过载保护、短路保护、断相保护、过欠压保护等功能，可实现双回路供电系统的电源自动转换。 1、三种工作方式 （1）自动-自复：两路电源正常，常用电源供电，当常用电源故障，自动转换到备用电源供电，当常用电源恢复正常，返回常用电源供电。 （2）自动-不自复：两路电源正常，常用电源供电，当常用电源故障，自动转换到备用电源供电，当常用电源恢复正常，不返回常用电源供电。 （3）手动：两路电源正常，常用电源供电，当常用电源故障时，需要人为操作到备用电源，不会自动切换。 2、三种工作状态 （1）常用电源工作：常用电源合、备用电源分 （2）备用电源工作：常用电源分、备用电源合 （3）双分状态：常用电源分、备用电源分 3、双电源智能控制器按钮说明 （1）“常用”、“备用”、“双分”三个按钮仅在手动模式下有效。 按下“常用”按钮，当装置处于双分状态且常用电源正常，控制器发送合闸指令，驱动常用电源断路器合闸，此时由常用电源供电； 按下“备用”按钮，装置处于双分状态且备用电源正常，控制器发送合闸指令，驱动备用电源断路器合闸，此时由备用电源供电； 按下“双分”按钮，当负荷有输出，且两路供电电源中，其中一路正
数据结构与算法实验报告
基于栈的C语言迷宫问题与实现 一．问题描述 多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。 迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。 一个迷宫可用上图所示方阵[m,n]表示，0表示能通过，1 表示不能通过。现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[m,n] 出去的路径。下图是一个迷宫的示意图： 入口 出口
迷宫示意图 二．算法基本思想 迷宫求解问题是栈的一个典型应用。基本算法思想是：在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左）对周围的墙、路进行判断（在本程序中分别用1、0）代替，若周围某个位置为0，则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序。 要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置（在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路。 三．程序具体部分的说明 1.迷宫的生成 根据题目的要求，迷宫的大小是自定义输入的。所以在程序中用malloc申请动态二维数组。数组中的元素为随机生成的0、1。数组周围一圈的元素全部定义为1，以表示边界。 2.栈的C语言实现 为了实现栈的功能，即清空、压栈、弹出、返回栈顶元素，在程序中编写了相应的函数。 MakeNULL 清空栈 Push 将横、纵坐标压栈 Topx 返回栈顶存储的横坐标 Topy 返回栈顶存储的纵坐标 Pop 弹出栈顶元素 3.具体的判断算法
智能型双电源自动切换开关应用 来源：工控商务网 随着科学技术的进步，各行业对供电可靠性的要求越来越高。很多场合必须采用两路电源来保证供电的可靠性。过去的两路电源用户，在低压侧采用手动操作的双向隔离开关进行倒闸操作，因此常出现误操作而引起事故。随着供电可靠性要求的提高，反事故措施的日趋完善，越来越多的先进设备投入应用到供电系统中。 一、高可靠性双电源切换装置 一种能在两路电源之间进行可靠切换双电源的装置，不会出现误操作而引起事故的全系列智能化双电源自动切换开关，就是为了满足高可靠性要求。目前投入使用的专用智能化设备，具有自投自复、自投不自复和电网发电机三种切换功能，对两路供电电源的三相电压有效值及相位进行实时检测，当任一相发生过压、欠压、缺相，能自动从异常电源切换到正常电源，这是一种性能完善、安全可靠、操作方便、智能化程度高、使用范围广泛的双电源控制系统的设备。 全系列智能型双电源自动切换开关的紧急供电系统，可实现当一路电源发生故障时，可以自动完成常用与备用电源间切换，而无需人工操作，以保证重要用户供电的可靠性。其主要用于医院、商场、银行等不允许断电的重要场所。 二、智能型双电源自动切换开关 智能型双电源自动切换开关特点 智能型双电源自动切换开关是由两台三极或四极的塑壳断路器及其附件（辅助、报警触头）、机械联锁传动机构、智能控制器等组成。分为整体式与分体式两种结构。整体式是控制器和执行机构同装在一个底座上；分体式是控制器装在柜体面板上，执行机构装在底座上，由用户安装在柜体内，控制器与执行机构用约2m长的电缆连接。其特点是： 两台断路器之间具有可靠的机构联锁装置和电气联锁保护，彻底杜绝了两台断路器同时合闸的可能性； 智能化控制器采用以MOTOROLA单片机为控制核心，硬件简洁，功能强大，扩展方便，可靠性高； 具有短路、过载保护功能，过压、欠压、缺相自动切换功能与智能报警功能； 自动切换参数可在外部自由设定； 具有操作电机智能保护功能； 装置带有消防控制电路，当消防控制中心给一控制信号进入智能控制器，两台断路器都进入分闸状态； 留有计算机联网接口，以备实现遥控、遥调、遥信、遥测等四遥功能。
#define_CRT_SECURE_NO_WARNINGS #include
ATSE选用规范 一、建议双电源自动转换开关电器（ATSE）采用专用型PC级，驱动方式采用励磁驱动机构（专用型）。目前市场上性价比高。 专用型PC级产品是最新一代的双电源转换开关产品（业内称为第四代），是代表双电源产品发展的方向，这在最新版《民规》里专门做了说明。 1、双电源四代产品的划分：第一代为交流接触器型、第二代为电机驱动断路器型即派生型CB级产品、第三代为电机驱动隔离开关型即派生型PC级产品） 划分依据：《合理选择与使用自动转换开关电器（ATSE）》 （作者：曲德刚 GB14048.11国家标准首席起草人、上海电科所副总工、中国低压电器行业协会会长） 2、双电源产品的发展方向依据：国家JGJ 16-2008《民用建筑电气设计规范》2008版中首次对双电源自动转换开关进行了描述： 7．5 低压电器的选择 7．5．4 近几年，配电系统中采用的双电源转换技术，已经由电器元件组装式双电源自投箱过渡到一体化的自动转换开关电器(ATSE)。 注：组装式即是派生型拼装结构，一体化即是专用型励磁一体结构。
专用型PC级产品完全满足消防、应急负荷使用要求。 依据： GB 14048.11—2008《低压开关设备和控制设备第6-1部分：多功能电器--转换开关电器》（起草人：曲德刚）； JB/T 10980—2010《转换开关电器（TSE）选择和使用导则》（起草人：曲德刚）； GB/T 21208-2007《低压开关设备和控制设备-固定式消防泵驱动器的控制器》（起草人：曲德刚）； 这三个标准的要求是：消防泵负载及其它消防电器如消防电梯、正压送风机、排烟风机等消防设施选用TSE的原则是： 自动转换开关电器应符合GB/T 14048.11中PC级（见GB/T 14048.11中第3章）的要求，同时其操作机构应能保证负载电路不能长时间地与常用电源和备用电源断开1）。 1）是指ATSE仅具有二个工作位置。 应急负载停止运行后可能带来生命和财产的危害，因此，选用TSE 时应重视其可靠性、安全性。 除非另有规定，其他形式的应急负载选用TSE的原则应符合消防设施选用原则。 因此，消防及应急类负载应选用PC级，两段位产品。第二代电机驱动断路器型产品中的微断型双电源产品只符合民用标准，分断能
stack.h #ifndef _STACK_H_ #define _STACK_H_ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define STACK_INIT_SIZE 100 // 栈储存空间的初始分配量 #define STACKINCREMENT 10 // 储存空间分配增量 typedef int Status typedef char SElemType typedef struct { SElemType *base;// 储存数据元素的数组 SElemType *top; // 栈顶指针 int stacksize; // 当前分配的栈空间大小，以sizeof(SElemType)为单位 }SqStack;
//** 构造一个空栈 Status InitStack(SqStack *S); //** 销毁栈 Status DestroyStack(SqStack *S); //** 栈是否为空 Status StackEmpty(SqStack *S); //** 入栈 Status Push(SqStack *S,SElemType e); //**取栈顶 SElemType GetTop(SqStack *S); //** 出栈 SElemType Pop(SqStack *S); //** 栈长度 int StackLength(SqStack *S);
//** 遍历 Status StackTraverse(SqStack *S,Status( *visit)(SElemType)); Status visit(SElemType e); #endif stack.c #include
浙江科技学院学报,第19卷第4期,2007年12月 Journal of Zhejiang University of Science and Technology Vol.19No.4,Dec.2007 收稿日期:2007209205 基金项目:浙江省科技计划重点资助项目(2006C21023) 作者简介:项新建(1964— ),男,浙江永康人,教授,硕士,主要从事智能控制技术和装备研究。双电源自动切换系统的设计 项新建,胡剑挺 (浙江科技学院自动化与电气工程学院,杭州310023) 摘 要:双电源供电系统的自动切换是一个实时性和可靠性要求很高的控制系统。针对不间断供电的需求,运用采样、比较的工作原理和方法,提出了一种以P89c591微控制器为主控芯片的双电源供电自动切换系统的智能优化解决方案。根据不同的情况实现对电源故障状况的准确判断和快速切换,完成主、备电源间转换,以保持供电的连续性。文中给出了系统硬件电路框图和软件流程及试验结果。关键词:双电源供电;自动切换;智能控制 中图分类号:TP273.5 文献标识码:A 文章编号:167128798(2007)0420277204 Design of Double Pow er Supply Autom atic Switch System XIAN G Xin 2jian ,HU Jian 2ting (School of Automation and E lectrical Engineering ,Zhejiang University of Science and T echnology ,Hangzhou 310023,China ) Abstract :Double 2power supply automatic switch system requires high reliability and real 2time.According to need of non 2stop supplying ,an intelligent optimized scheme of double 2power supply automatic switch system is p ropo sed wit h microcont roller P89c591as main chip by sampling and comparing in t his system.System permit s users to have different settings according to distri 2bution network and load conditions ,to switch main power to reserve power according to different breakdowns.So t he continuity of power supply is ensured by correct evaluation and fast switch of power source conditions.System hardware diagrams ,software procedures and test result s are pro 2vided in t he paper. K ey w ords :double 2power supply ;automatic switch ;intelligent cont rol 作为对连续供电的一种保障,双电源自动切换开关电器(A TSE )已广泛应用于各种重要的场所,如电梯、消防、地铁、医院、邮电通讯、电视台、工业流水线等。以往的A TSE 一般都是由设计院设计、电气成套企业或用户直接用接触器、继电器、刀开关或 由断路器、机械联锁、模拟控制器构成。此类双电源 自动切换系统存在的主要问题:一是无缺相、欠压、过压、短路、过载、超频等保护功能;二是继电器的逻辑组合设置不灵活,功能单调;三是采用继电器逻辑控制电路实现,器件和电路的故障率高等。
实验报告 课程名称：数据结构 年级班级：计算机1712 学号姓名：查玉坤 2017116128 任课教师：康长青
实验目的 设计算法，把十进制整数转换为二至九进制之间的任一进制输出。 实验内容 代码如下： #include
for(i=S->top-1;i>=0;i--) printf("%d",S->base[i]); printf("\n"); } int main(){ int a,b,Jin,x,X,size; a=1; printf("输入一个十进制数\n"); scanf("%d",&x); X=x; printf("需要转化为多少进制数？\n"); scanf("%d",&Jin); sqstack S; initstack(&S); while(x>=Jin){ a=(x%Jin); b=(x/Jin); push(&S,a); x=b; } push(&S,x); printf("转换的%d进制数为:",Jin); list(&S); printf("验证:\n"); for(int i=S.top;i>0;i--){ if(i-1!=0) printf("%d*(%d^%d)+",S.base[i-1],Jin,i-1); else printf("%d*(%d^0)=%d\n",S.base[i-1],Jin,X); } return 0; }