未初始化变量的一种静态测试方法

第２８卷　第４期　ＶＯ１．２８　ＮＯ．４　计算机工程与设计　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｄｅｓｉｇｎ　２００７年２月　Ｆｅｂ．２００７　未初始化变量的一种静态测试方法　赵鹏宇，　万琳，　宫云战　（装甲兵工程学院信息工程系，北京１０００７２）　摘要：软件测试系统的研制是软件测试领域的一个研究热点。未初始化变量是ｃ／Ｃ抖程序中的常见故障，该类故障极　导　致计算结果错误或系统崩溃　针对ｃ／Ｃ抖语言中常见未初始化变量故障进行了分析研究，并从面向具体故障的测试思想出　发，建立了ｃ／Ｃ＋＋语言中未初始化变量的故障模型，结合静态测试的特点，给出了一种静态查找此类故障的方法。该方法已　实现，并已应用于面向故障的软件测试系统中。　关键词：软件测试；静态测试；未初化变量；语法树；控制流图　中图法分类号：ＴＰ３０２．８　文献标识码：Ａ　文章编号：１０００－７０２４（２００７）０４．０７５１－４　０Ｓｔａｔｉｃ　ｄｅｔｅｃｔｉｎｇ　ｍｅｔｈｏｄ　ｆｏｒ　ｕｎｉｎｉｔｉａｌｉｚｅｄ　ｖａｒｉａｂｌｅ　ＺＨＡＯ　Ｐｅｎｇ—ｙｕ，　ＷＡＮ　Ｌｉｎ，　ＧＯＮＧ　Ｙｕｎ—ｚｈａｎ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ａｒｍｏｒｅｄ　ｆｏｒｃｅｓ　Ｉｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ　１　０００７２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｕｎｉｎｉｔｉａｌｉｚｅｄ　Ｖａｒｉａｂｌｅ　ｉＳ　ａ　ｃｏｍｍｏｎ　ｋｉｎｄ　ｏｆｅｒｒｏｒ　ｉｎ　ｐｒｏｇｒａｍｓ　ｗｒｉｔｔｅｎ　ｉｎ　Ｃ，Ｃ＋＋．ｗｈｉｃｈ　ｏｆｔｅｎ　ｃａｕｓｃｓ　ｓｙｓｔｅｍ　ｃｏｌｌａｐｓｅ．Ｆｉｒｓｔｌｙ，　ｔｈｅ　ｃｌａｓｓｉｃａｌ　Ｃ／Ｃ＋＋ｕｎｉｎｉｔｉａｌｉｚｅｄ　ｖａｒｉａｂｌｅ　ｅｒｒｏｒｓ　ｉｓ　ａｎａｌｙｓｅｄ．ａ　ｄｅｆｅｃｔｍｏｄｅｌ　ｏｆｕｎｉｎｉｔｉａｌｉｚｅｄ　ｖａｒｉａｂｌｅ　ＯｆＣ／Ｃ＋＋ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｄｅｆｅｃｔ－ｏｒｉｅｎｔｅｄ　ｔｅｓｔｉｎｇ　ｓｔｒａｔｅｇｙ　ｉｓ　ｅｓｔａｂｌｉｓｈｅｄ，ｔｈｅｎ　ａ　ｄｅｔｅｃｔｉｎｇ　ｍｅ￣ｏｄ　ｏｆ　ｕｎｉｎｉｔｉａｌｉｚｅｄ　ｖａｒｉａｂｌｅ　ｅｒｒｏｒｓ　ｃｏｍｂｍｉｎｇ　ｔｈｅ　ａｄｖａｎｔａｇｅ　ｏｆ　ｓｔａｔｉｃ　ａｎａｌｙｓｉｓ　ｉｓ　ｄｅ－　ｓｃｒｉｂｅｄ．Ｔｈｉｓ　ｔｈｅｏｒｙ　ｉｓ　ｉｍｐｌｅｍｅｎｔｅｄ　ｉｎ　ａ　ｄｅｆｅｃｔ－ｏｒｉｅｎｔｅｄ　ｔｅｓｔｉｎｇ　ｓｙｓｔｅｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｏｆｔｗａｒｅ　ｔｅｓｔｉｎｇ；ｓｔａｔｉｃ　ｔｅｓｔｉｎｇ；ｕｎｉｎｉｔｉａｌｉｚｅｄ　ｖａｒｉａｂｌｅ；ｓｙｎｔａｘ　ｔｒｅｅ；ｃｏｎｔｒｏｌｌｎｇ　ｉｓｔｒｅａｍ　ｒａｐｈ　ｇＯ引　言　软件测试可以分为静态测试方法和动态方法。软件测试　的目的在于发现错误，进一步可以针对某一种或者某几种错　误进行专门的测试，这种测试叫做面向具体错误类型的测试。　Ｃ／Ｃ抖对变量的声明、初始化和引用都非常灵活，给程序员写　程序带来极大的方便和效率。但是，由于程序员的理解偏差　和粗心，在编写程序时，程序员往往对没有初始化的变量进行　引用，从而导致程序的输出结果错误或死机。虽然有些工具能　够检测出简单的未初始的变量的错误，但是对于较复杂的变量　称。它的主要特点是不利用计算机运行被测试的程序，而是　采用其它手段达到检测的目的。有人认为静态分析只是动态　分析的预处理工作，认为静态分析并不是要找出程序中的错　误，因为编译系统已经能够做到这一点了。实际上，这种看法　是片面的，尽管编译系统也能发现某些程序错误，但这远非软　件中存在的大部错误。静态分析的查错功能是编译程序不能　代替的。　１．２未初始化变量错误　未初始化变量顾名思义就是变量在声明以后，没有对其　初始化赋值就进行引用，导致了程序出错或死机。　例如：　ｌ２　ｌ　ｃｈａｒ　ｒｅａｄｌｉｎｅ（ｃｈａｒ＊ｂｕ０　ｆ　１２２　１２３　ｃｈａｒｃ；　ｃｈａｒ　ｓａｖｅｂｕｆ＝ｂｕｆ；　类型（结构体变量、指针变量、数组等），这些工具的检测结果却　不尽人意。另外这些工具也检测不出程序中每条执行路径上　的未初始化变量的错误。解决上述问题恰恰是静态软件测试　方法所擅长的。然而静态方法由于不实际执行被测程序所以　在找到一个潜在的错误后还需要人工确认是否是真正的错误。　１２４　１２５　ｗｈｉｌｅ（ｃ！＝ＥＯＦ＆＆（ｃ＝ｇｅｔｃｈａｒＯ）！＝’、Ｉｌ’）　ｂｕ　斗＝ｃ：　１基本概念　１．１静态分析　静态分析是对被测程序进行特征分析的一些方法的总　收稿日期：２００６－０１—１６　Ｅ－ｍａｉｌ：ｚｈａｏｐｅｎｇｙｕ００６＠１６３．Ｇｏｒｅ　１２６　ｂｕｆ＝　＼０’：　１２７　１２８　ｉｆ（ｃ—ＥＯＦ＆＆ｂｕｔ＂一ｓａｖｅｂｕｆ）　ｉｅｔｕｒｎ　ＮＵＬＬ；　基金项目：总装备部十五预研基金项目（４１３１５０５０１０７）。　作者简介：赵鹏宇（１９８１一），男，河北唐山人，硕士研究生，研究方向为软件工程、软件测试等；　万琳（１９７４一），女，山西太原人，博士，研　究方向为软件工程、软件测试等；　宫云战（１９６１－－），男，山东威海人，博士，教授，博士生导师，研究方向为软件工程、软件测试、集成电路　测试等。　一７５ｌ一　维普资讯 http://www.cqvip.com

１２９　ｅｌｓｅ　１３０　ｒｅｔｕｒｎ　ｓａｖｅｂｕｆ；　利用ＬＥＸ和ＹＡＣＣ来进行。　１．４符号表　变量名字分析与变量名字的使用和变量声明有着密切的　关系。为了得到很好名字分析的效果，在生成语法树的同时　生成了一个符号表。这个符号表为每个被声明的变量建立一　个表项，描述了变量的作用域和它是如何被嵌套声明的。变　量名字的分析结果就是为每个变量在符号表中生成一个表项。　１３１｝　在上面的程序中在变量Ｃ被赋为下一值前要判断变量Ｃ　的值是否为ＥＯＦ。由于变量Ｃ在１２２行被声明，而在１２４行第　一次循环前没有被赋初值，就产生了未初始化变量的错误。　再如：　１００　ｉｎｔｂ，ｃ；　１０１　ｓｃａｎｆ（”％ｄ．－’ｂ）；　１０２　ｉｆ（ｂ＞０）　１０３　ｃ＝２５；　１０４　ｃ＝ｃ＋ｂ：　在上述程序第１００行声明了两个变量ｂ和ｃ，在第１０１行变　量ｂ被初始化。在程序的１０４行，变量ｃ要被变量ｃ和变量ｂ的　和赋值。但是如果变量ｂ的值小于或等于０，则第１０３行将不　会被执行到，在１４０行仍然会出现未初始化变量的错误。Ｗｈｉｌｅ，　ｄｏｗｈｉｌｅ，ｆｏｒ等语句同样会出现上述情况。而程序员在编写出　上述程序时，编译器不会报出任何错误或警告。　Ｃ，Ｃ斗＿卜语言提供的变量类型非常丰富。基本类型有整型　变量、字符型变量、实型变量、枚举型变量，指针类型变量；构　造类型变量有数组类型变量、结构体变量、共用体类型变量等。　程序员在编写程序时由于其粗心或理解偏差，往往在声　明变量后不加以初始化就对其进行引用或者程序在真正执行　时，从程序的入口到程序的出口可以有多条路径，有时变量只　在某条路径上被初始化，而在其它路径上，程序员却忽略了对　变量的初始化，而在随后的变量引用时导致了程序的出错。　１．３语法树　语法分析主要是将输入字符串识别为单词符号流，这里　主要是找出变量声明语句，并相应的分离出各种类型的变量。　按照标准的Ｃ斗＿卜语法规则，对源程序作进一步分析，比如什么　是变量定义，什么是赋值语句，什么是函数。语法分析的结果　是生成语法树，它被保存在内存中，是源代码的内部表示。其　它模块可以方便地访问语法树来完成各种各样的任务如：源　代码分析、Ｃ，Ｃ斗＿卜源代码到其它源代码的翻译等。源代码的任　何一条语句在语法树上都有一个节点与其相对应，例如声　明语句：　ｓｔａｔｉｃ　ｕｎｓｉｇｎｅｄ　ｉｎｔ　ａ【５】，ｂ－－－ｌ；　这条声明语句在语法树中对应的结点如图１所示。　构造程序完整的语法树和编译系统前端工作相同，可以　图１　声明语句在语法树上的结点结构　一７５２一　例如程序：　ｃｌａｓｓ　Ｃ｛　ｉｎｔｆｌｉｎｔｘ１）｛　ｉｎｔ　ｘ２．ｘ３；　｛Ｉｎｔ　ｘ３，ｘ４；）　｛ｉｎｔ　ｘ２，ｘ４；）　）　ｎｉｔｇ（ｎｉｔｘ１）：　）；　这段程序的符号表的结构如图２所示。　图２类Ｃ符号表　构造程序完整的符号表和编译系统前端工作相同，也可　以利用ＬＥＸ和ＹＡＣＣ来进行。　１．５程序控制流图　程序的控制流图是对程序控制结构的图形表示，它是一　种有向图。控制流图中的节点表示程序的语句，边表示控制　流。另外对于每个函数的控制流它还包含一个惟一的入口结　点和惟一的出口节点。在每个函数调用的地方存在一个调用　节点和返回节点，如图３所示。　Ｖｏｉｄｆｕｎｃｔｉｏｎ（ｉｎｔＸ，ｎｉｔｙ）　｛　ｉｆ（ｘ＞ｙ）　图３程序控制流　维普资讯 http://www.cqvip.com

ｐｒｉｎｔｆ（“％ｄ，’，ｘ）；　ｅｌｓｅ　分析，查出其中的错误是我们所关心的。　在程序的执行中所使用的集合有：　ｂｌｅ｛）：用来记录被测程序中的出现的所有变量。　Ｖｅｘ｛｝：控制流图的所有结点集合。　ＤｅｌＮｏｄｅ｛）：用来记录程序中出现的每个变量在程序控制　流图中被声明节点号。　ＩｎｉＮｏｄｅ｛）：用来记录程序中出现的每个变量在程序控制　流图中的被初始化的所有结点号。　ＵｓｅｄＮｏｄｅ｛）：用来记录程序中出现的每个变量在程序控　ＴｅｍｐＮｏｄｅ｛）：用来记录经过ＣｕｔＮｏｄｅ操作的被删除的结　ｐｒｉｎｔｆ（“％ｄ，’，ｙ）；　）　２以语法树和控制流图为基础的未初始化变量　错误分析　２．１系统设计　构建错误类型模型查找测试的核心是对源程序进行词法　分析和语法分析，生成被测程序的语法树和控制流图。系统　设计如图４所示。　一一一　一一一　制流图中被使用到的结点号。　源程序　预编译　生成数据库　文件　至　图４故障检查流程　（１）预编译：由于源程序中存在宏定义、文件包含和条件编　译等预处理命令，因此在进行词法分析前必须进行宏展开等　预编译工作。　（２）词法分析：将预编译阶段产生的中间代码分解成单独　的词的表示，形成各种符号表、类型表、关键字表、常数表、运　算符表和分界符表。符号表中包含有利于错误查找的一些相　关信息，如：位置、行号、错误类型，这些信息对于错误的查找　和定位都有十分重要的作用。　（３）语法分析：这一步主要是将输入字符串识别为单词符　号流，这里主要是找出变量声明语句，并相应的分离出各种类　型的变量。按照标准的Ｃ＋＋语法规则，对源程序作进一步分　析，比如什么是变量定义，什么是赋值语句，什么是函数。语　法分析的结果是生成语法树，每一个语法规则对应一个相应　的处理函数，并作为语法树的一个结点挂在语法树上，提供对　外的接口。　（４）生成控制流图：以语法树为基础，根据程序的控制结　构，用递归的算法在遍历语法树时生成程序的控制流图。控　制流图中的每个节点表示程序的一条语句，与语法树上相应　的语句结点相对应。另外对每个函数的控制流图它还包含一　个惟一入口结点和惟一的出口结点。在函数的调用的地方存　在一个调用节点和一个返回结点。　（５）以第３步和第４步生成的语法树和控制流图为基础，　根据算法分析程序控制流图和语法树，在这过程中对变量进　行分析，找出未始化的变量。　（６）如果找到相匹配的错误，则将错误信息记录到数据库文　件中，最后得到数据库文件。数据库文件是得到的最终的结果，　其中包括经过测试得到的一些相关信息，如未初始化变量名、　该变量被定义的行号、该变量被使用的行号、错误类型等。最　终由数据库文件生成错误信息报表，将错误信息反馈给用户。　２．２算法设计　错误的查找是系统设计的目标，如何对源代码进行静态　点号和该结点的所有入边和出边。　所用到的操作有：　Ａｄｄ（Ｓ，Ｅｌｅｍ）：将元素Ｅｌｅｍ加入到集合Ｓ。　Ｋｉｌｌ（Ｓ，Ｅｌｅｍ）：将元素Ｅｌｅｍ从集合Ｓ删除。　ＣｕｔＮｏｄｅ（Ｇ，ｎｏｄｅ）：在程序控制流图Ｇ中将结点ｎｏｄｅ删除，　并将该结点的所有入边和出边一同删除。　ＲｅｆｒｅｓｈＧｒａｐｈ（Ｇ）：把经过ＣｕｔＮｏｄｅ操作的程序控制流图Ｇ　还原为进行ＣｕｔＮｏｄｅ前的状态。　算法描述：　（１）遍历被测程序语法树，收集被测程序中出现的所有变　量的信息，生成变量表ＶａｒＴａｂｌｅ｛），生成该程序的控制流图Ｇ：　（　Ｅ），Ｖ为图中结点集，Ｅ为有向边集；ｅ　Ｔ（ｅ），Ｈ（ｅ））表示相邻　结点对，其中边ｅ离开Ｔ（ｅ）结点，进入Ｈ（ｅ）结点。　（２）广度优先遍历程序的控制流图Ｇ，在遍历过程中如果　遇到变量ｖａｔ的声明结点，则将该变量的声明结点号加入该变　量的声明结点集合中，即执行Ａｄｄ（ＤｅｌＮｏｄｅ，ｖ）操作；如果遇到　变量ｖａｔ的初始化结点，则将该变量的初始化节点号加入该变　量的初始化结点集合中，即执行Ａｄｄ（ＩｎｉＮｏｄｅ，ｖ）操作；如果遇　到变量ｖａｒ被使用的结点，则将该变量的被使用节点号加入该　变量的被使用结点集合中，即执行Ａｄｄ（ＵｓｅｄＮｏｄｅ，ｖ）操作。　（３）顺次扫描被测程序的变量表，对该表中的每个变量进　行如下操作：　如果该变量的初始化集合ＩｎｊＮ０ｄｅ非空，则遍历被测程序　的控制流图，在被测程序的控制流图中删除该结点及其连接　边ｅ，ｅ满足ａＸｅ￣ｎ或Ｈ（ｅ）＝＝ｎ；得Ｇ　Ⅳ　’；即对该变量ＩｎｉＮｏｄｅ　集合中的所有结点进行ＣｕｔＮｏｄｅ（Ｇ，ｖｅｘ）操作。　如果该变量的ＵｓｅｄＮｏｄｅ集合非空，则顺次取出该变量的　使用结点，在被测程序的控流图中寻找是否存在一条该变量　的声明节点到该变量的使用节点的通路。如果存在，则检测　出了未初始化变量错误，将这条错误记录写入到数据库中。否　则，ｇｏｔｏ（４）。　（４）检查变量表岫ｂｌｅ，如果变量表ＶａｒＴａｂｌｅ中尚有未被　扫描过的变量，则恢复被测程序的控制流图Ｇ，即执行Ｒｅｆｒｅｓｈ．　Ｇｒａｐｈ（Ｇ），ｇｏｔｏ（３）；否则退出测试程序。　２．３算法分析　（１）当变量作为参数时，有可能在函数内初始化，再传递出　来，对于该情况，全部报出ＩＰ，再判断是否误报；　（２）条件内初始化（ｉｆ，ｗｈｉｌｅ等）：如果条件始终成立（恒真，　或ｉｆ，ｅｌｓｅ分支都有初始化），则不报，否则全部报出Ｉｌ＇，再判定　・——７５３－——　维普资讯 http://www.cqvip.com

是否误报；　（３）ｃａｓｅ结构中的初始化（包含ｉｆ嵌套结构）：确定是否有　ｄｅｆａｕｌｔ分支，且在该分支内有初始化，有则不报，否则全部报　出ＩＰ，再判断是否误报；　（４）静态或全局变量定为误报。　项目　编号　ｌ　２　３　４　表２测试结果比较　本文所述方法　Ｒｅａｓｏｎｉｎｇ工具　ＩＰ总数　故障总数　准确率　ＩＰ总数　故障总数　准确率　７３　ｌ１５　１１３　４ｌＯ　１２　５６　３３　ｌ３Ｏ　ｌ６．４％　４８．６％　２４．８％　３１．７％　ｌＯ３　ｌ１２　１６５　３５ｌ　２２　４８　３２　６６　８．４％　４８．２％　１７．９％　ｌ８．４％　３实验结果和对比分析　我们以不同大小的程序模块来检测我们开发的未初始化　合计　７ｌ１　２３ｌ　３２．４％　７３ｌ　ｌ６８　２２．９％　变量的静态软件测试系统。具体的作法是：首先运用软件测　试工具对软件进行测试，标记出测试工具认为可能出现的错　误点来，称之为检测点ＩＰ，经检测后提供一个中间文件给测试　人员，由测试人员再对照这些ＩＰ，复查源代码，最终确定这些　ＩＰ点是否是一个Ｄｅｆｅｃｔ。表ｌ给出了对些项目进行测试得出　的ＩＰ数和经人工确认后的对比结果。　保证找出程序中所有的此类错误，但是找到的确实是实实在在　的错误，仅这一点就足以说明这种分析方法的有效性。当然，　该工具还有很多需要扩展和改进的地方。如：引入简单的符号　执行处理多个判断条件组合的问题等。在以后的工作中还要　考虑空指针引用、数组越界、内存泄漏等错误类型的分析。　参考文献：　表ｌ　ＩＰ数和确认以后结果对比　Ｆｉｌｅ　Ｓｉｚｅ／Ｍ　４＿３８　ｌ２４　［１】Ｂｕｓｈ　Ｗ　Ｒ，Ｐｉｎｃｕｓ　Ｊ　Ｄ，ＳｉｅｌａｆｆＤ　Ｊ．Ａ　ｓｔａｔｉｃ　ａｎａｌｙｚｅｒ　ｆｏｒ　ｉｆｎｄｉｎｇ　ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｅｒｒｏｒｓ－【Ｒ］Ｓｏｆｔｗａｒｅ－Ｐｒａｃｔｉｃｅｎｄ　ａＥｘｐｅ—　ｒｉｅｎｃｅ，２０００，３０（７）：７７５－８０２．　３　５　Ｉｎｓｐｅｃｔｉｏｎ　Ｐｏｉｎｔｓ　１２　ｌＯ　Ｉ￣ｆｃｃｔｓ　［２】　宫云战．一种面向故障的软件测试新方法［Ｊ］．装甲兵工程学院　学报，２００４，（１）：２　１－２５．　３０．５　６２　ｌ７２　４５　８２　ｌ２３　２６　３９　４３　［３】Ｌｏｕｄｅｎ　Ｋ　Ｃ编译原理及实践［Ｍ】．北京：机械工业出版社，２０００．　［４】　张威．基于指针映射集的动态内存故障测试方法研究［Ｊ］．计算　Ｆｉｌｅ　Ｓｉｚｅ指被测试程序的大小，以Ｍ为单位；Ｉｎｓｐｅｃｉｔｏｎ　Ｐｏｉｎｔｓ指软件测试工具检测出的ＩＰ总数；Ｄｅｆｅｃｔｓ指经人工复　查后确定的错误总数，这是最后要提交给客户的最终结果。由　上面的实验结果可知，软件中存在的错误与文件大小成一定　相关性。该测试软件能够找出被测程序的大部分未初始化变　量的错误。　机学报，２００３，（２）：２５－２７。　［５】　Ｂｅｒｎｈａｒｄ　Ｓｃｈｏｌｚ，Ｊｏｈａｎｎ　Ｂｌｉｅｂｅｒｇｅｒ，Ｔｈｏｍａｓ　Ｆａｈｒｉｎｇｅｒ．Ｓｙｍ－　ｂｏｌｉｃ　ｐｏｉｎｔｅｒ　ｎａｌａｙｓｉｓ　ｏｒｆ　ｄｅｔｅｃｔｎｉｇ　ｍｅｍｏｒｙ　ｌｅａｋｓ［Ｒ］．Ｔｏ　ａｐｐｅａｒ　ｎ　ｉＲｅａｌ－Ｔｉｍｅ　Ｓｙｓｔｅｍｓ　Ｊｏｕｒｎａｌ，２００２．　［６】Ｅｍａｍｉ　Ｍ，Ｇｈｉｙａ　Ｈｅｎｄｒｅｎ　Ｌ　Ｊ．Ｃｏｎｔｅｘｔ－ｓｅｎｓｉｉｔｖｅ　ｉｎｔｅｒｐｒｏｃｅ．　ｄｕｒａｌｐｏｉｎｓｔ－ｔｏａｎａｌｙｓｉｓｉｎｔｈｅｐｒｅｓｅｎｃｅｏｆｆｕｎｃｔｉｏｎｐｏｉｎｔｅｒｓ［Ｍ］．　ＡＣＭ　ＳＩＧＰＬＡＮ　Ｎｏｔｉｃｅｓ，２０００，２９（６）：２４２—２５６．　与Ｒｅａｓｏｎｉｎｇ公司的测试结果进行了对比，如表２所示。　４结束语　软件测试的目的是为了发现更多的错误，面向具体错误类　［７】　古乐，史九林．软件测试技术概论［Ｍ】．北京：清华大学出版社，　２ｏ０３．　［８】Ｔｅｒｒｅｎｃｅ　Ｗ　Ｐｒａｔｔ．程序设计语言：设计与实现［Ｍ】．第４版．北京：　电子工业出版社，２００１．　型的测试方法使这一点更加突出。经过工具分析，虽然也不能　（上接第７５０页）　３．Ｒｅｔｎｒｎ　ＳＥ　ｌｉｓｈｉｎｇ　Ｈｏｕｓｅ　ｏｆＴｓｉｎｇｈｎａ　Ｕｎｉｖｅｒｓｉｔｙ，２００５．　｝　３．３　Ａｄｖａｎｔａｇｅｓ　［２】　Ｗｉｌｌｉｍ　ａＦｏｒｄ，Ｗｉｌｌｉｍ　ａＴｏｐｐ．Ｄａｔａ　ｓｔｒｕｃｔｕｒｅｓ　ｗｉｈｔ　Ｃ＋＋［Ｍ】．Ｂｅｉ—　ｊｉｎｇ：ｈｅＴ　ｕｂｌＰｉｓｈｉｎｇ　Ｈｏｕｓｅ　ｏｆＴｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｙｔ，２０００．　［３】Ｙｕ　Ｘｉｎｇ－ａｘｕａｎ．Ｃｏｍｐｕｔｅｒ　ａｌｇｏｒｉｔｈｍ［Ｍ】．ｈｅ　ＴｕｂｌＰｉｓｈｉｎｇ　Ｈｏｕｓｅ　ｏｆ　Ｃｈｉｎｅｓｅ　Ｃｅｎｔｒａｌ　Ｓｃｉｅｎｃｅ　ｎｄ　Ｔｅｃｈｎｏｌａｏｇｙ　Ｕｎｉｖｅｒｓｉｙ，２０００．ｔ　（１）ｈｅ　Ｔｔｈｏｕｇｈｔ　ｉｓ　ｓｉｍｐｌｅ　ｎｄ　ａｉｔ　ｉｓ　ｖｅｙ　ｒｅａｓｙ　ｔｏ　ｂｅ　ｉｍｐｌｅｍｅｎｔｅｄ　ｎｄ　ｃｏｄｅｄ．ａ　（２）Ｉｆｔｈｅ　ｎｕｍｂｅｒｏｆｐｏｉｎｔｓｉｎ　Ｓｉｓ　ｖｅｒｙｂｉｇ，ｓｔｅｐ　２ａｎｄ　ｓｔｅｐ　３ｉｎ　ｈｅ　ｍａｉｔｎ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｅｘｅｃｕｔｅｄ　ｉｎ　ｔｗｏ　ｃｏｍｐｕｔｅｒｓ　ｓｙｎｃｈｒｏｎｏｕｓｌｙ．　【４］　Ｌ　Ｊｉｎ－ｙｉ．Ｄｉｓｃｕｓｓｉｏｎ　ｏｎ　ｎ　ａＯ（ｎ）ｔｉｍｅ　ａｌｇｏｒｉｔｈｍ　ｏｒｆ　ｈｅｔ　ｃｏｎｖｅｘ　ｈｕｌｌｏｆａｐｌａｎａｒｐｏＩｎｔ　ｓｅｔ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｊｏｕｒｌａ，２００２，（６）：６７１—６７２．　【５】Ｗｅｉ　Ｘｉａｏ－ｌｉｎｇ．Ｔａｈｅ　ｖａｒｉａｔｉｏｎ　ｎｄ　ａａｐｐｌｉｃａｔｉｏｎｓ　ｏｆｔｈｅ“ｇｉｉｔ　ｗｒａｐｐｉｎｇ”ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆｔｈｅ　ＣＵＮ，２０００，（１）：８—１０．　４　Ｃｏｎｃｌｕｓｉｏｎ　ｈｅｔＴｈｏｕｇｈｔｓｏｆｔｈｅｔｗｏ　ａｌｇｏｒｉｔｍｓ　ａｒｅｖｅｒｈｙ　ｓｉｍｐｌｅａｎｄ　ｅａｓｙｔｏ　ｂｅ　ｉｍｐｌｅｍｅｎｔｅｄ　ｎｄ　ａｃｏｄｅｄ．Ｉｆｔｈｅ　ｎｕｍｂｅｒ　ｏｆｐｏｉｎｔｓ　ｉｎ　Ｓ　ｉｓ　ｖｅｒｙ　ｂｉｇ，　【６】Ｃｈｅｎｇ　Ｘｉａｏ－ｊｕｎ．Ｔｈｅ　ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　ｅｓａｔｂｌｉｓｈｉｎｇ　ＴＩＮ　ｂａｓｅｄ　ｏｎ　ｏｎｖｅｘ　ｃｓｈｅｌｌ［Ｃ］．Ｎｏｒｔｈ　Ｅａｓｔ　Ｍａｐｐｉｎｇ，２００　１．６—９．　［７】　ＹａｎＷｅｉ－ｍｉｎ．Ｄａｔａ　ｓｔｒｕｃｔｕｒｅ　ｎｄ　ａｌａｇｏｒｉｔｈｍ［Ｍ】．Ｂｅｉｊｉｎｇ：Ｔｈｅ　ｕｂｌＰｉｓｈｉｎｇＨｏｕｓｅｏｆＴｓｉｎｇｈｎａＵｎｉｖｅｒｓｉｙ，２００４．ｔ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｅｘｅｃｕｔｅｄ　ｓｙｎｃｈｒｏｎｏｕｓｌｙ．　Ｒｅｆｅｒｅｎｃｅ　Ｍａｔｅｒｉａｌｓ　【８】Ｊｉｎｇ　ａＨｏｎｇ－ｆｅｉ．Ｓｔｕｄｙ　ｏｎ　ｆｓｔａ　ｃｏｎｖｅｘ　ｈｕｌｌ　ａｌｇｏｒｉｔｈｍ　ｏｆｐｌｎｅｒａ　［１】Ｚｈｏｕ　Ｍｉｎｇ—ｄｅ．Ｃｏｍｐｕｔａｔｉｏｎａｌ　ｇｅｏｍｅｔｒｙ［Ｍ】．Ｂｅｉｊｎｇ：ｉｈｅＴ　Ｐｕｂ－　ｐｏ　ｓｅｔ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｐｒｏｊｅｃｔｓ　ｎｄ　ａＡｐｐｌｉｃａｔｉｏｎｓ，２００２，２０：４８－４９．　—７５４・——