第1章基本概念 pi &i: 则返问1的地址并把它赋值给p1。要为1赋值，可以写 1=10: 或者 4pi=10: 以上两条赋值语句都把整数值10存储在1之中。第二条赋值语句P前的·是上引 用，10并未存入指针里，而是存入指针p1指向的存储单元之中 对指针还可以做其它挨作。指针的值可以用米赋值给指针变量。指针是一个非负整数， 因而C允许指针做算术运算，包括加、减、乘、除。指针之间可以做比较，结果返可人于、小 于、相等三者之一。指针还可以通过强制显式地转换成整数。 指针变量的长度在不同的计算机中可以取不同值。有时，指针变量的长度在同一台计算 机中也会不同。例如，指向char的指针变量长度也许比指向E1oat的指针变量长度更长。C 用特殊的值L表示空指针。空指针不指向变量，也不指向函数。对丁具体系统，空指针用 整数值0表示，C中ULL是一个宏，具体实现就定义为常革值0。空指针可川在关系表达式 中，表示布尔量“假”，因而，测试空指针的语句可以是： if (pi -NULL) 或者可以是更简洁的形式： if (pi) S1.2.2动态存储分配 程序在运行时需要中请存储空间，用米存放信息，但在编程阶段，我们并不知道程在 运行时需要多人空间（例如，数组人小可能依赖于输入数据），也不想步先预留一块非常人 的区域，因为其中很多空间也许根本就不会用到。针对这个问题，C语言提供了一套机制， 可以在程序运行时分配存储空间，这块区域称为系统堆(heap)。如果需要新的存储空间，我 可以调用函数ma11oc申请所需大小的一块内存空间。如果当前系统存在空闲内存，那么 ma11oc函数返问指向这块空闲内存起始地址的指针：反之，如果当前系统没有空闲内存，则 函数ma1loc返同指针NUL。以后如果不再需要这块存储空间，可以调用函数free把它释 放，交还给系统。一口一块存储空间被释放，就不应再用它。程序1.1是中请、释放存储空间 的例子，注意指针的用法 程疗1.1调用ma11oc的参量分别对应类型1nt和类型f1oat的存储空间人小，返同值是 指向这块存储空间第一个字节的指针。这个函数的返同类型对不同的系统可能不同，有些系 统返问char+,即指向char的指针。但ANSIC返同void*。标i记(int+)和(float+) 是类型强制转换表达式，在程序11中本米可以缺省，这两个标记把返同类变换为正确的 类型。free函数把以前用ma1loc申请的存储空间释放。在：有些版本的C语音中，free要 求的参量类型是char·,而ANSIC要求的参量类型是void·,通常，free的参址类刊转 换都是缺省的
第 Ι章 基本概念 p土 = &土 ; 则 &⊥返冂 ⊥的地址并把它赋值给 p土。要为 i赋 值,可 以写 △ =△ 0氵 或者 以上两条赋值语句都把整数值 10存 储在 土之 中。第工条赋值语句 p⊥前的 ★足上引 用,10并 未存入指针里,而 是存入指针 pi指 向的存储单元之中。 对指针还可以做其它操作。指针的值可以用来赋值给指针变蚩。指针足 一个△负整数, 冈而 C允 许指针做算术运算,包 括加、减、乘、除。指针之间可以做比较,结 呆返回人 J=、小 于、相等二者乏一。指针还可以通过强制显式地转换成整数。 指针变蚩的κ度在不同的计算机中可以取不同值。有时,指 针变 筻的 K度 在同 一台计算 机中也会不同。例如,指 向char的 指针变量 长度也许比指 向 n。 a△的指针变蚩长度更 κ。C 用特殊的值 NuLL表 示空指针。空指针不指向变董,也 不指 向函数。对 1·贝体系统,空 指针川 整数值 0表 示,C中 bluLL是 一个宏,具 体实现就定义为常鞋值 0。空指针可川在关系表达式 中,表 示布尔童 “假 ”,因 而,测 试空指针的语句可以是: 土￡ (p土 == NULL) 或者可以是更简洁的形式: 土￡ (!p土 ) §1.2.2 动 态存储分配 程序在运行时需要 中请存储空间,用 来存放信息,但 在编程阶段,我 们并不知道稆序在 运行时需耍多人空问 (例如,数 组大小可能依赖 丁输入数据 ),也 不想韦先预留一块△常人 的区域,冈 为其中很多空间也许根本就不会用到。针对这个问题,C语 言捉供丁 一套机制, 可以在程序运行时分配存储空间,这 块区域称为系统堆 (heap)。 如呆需耍新的存储空问,我 们可以调用函数 ma11。 c中 请所需大小的一块内存空间。如呆当前系统存在空闲内存,那 么 ma11oc函 数返冂指向这块空闲内存起始地址的指针 ;反 乏,如 果当前系统没有空闲内存,则 函数 ma11。 c返 冂指针 NuLL。 以后如果不再需耍这块存储空问,可 以调用函数 free把 它释 放,交 还给系统。一 口^一块存储空间被释放,就 不应再用它。程序 1.1是 中请、释放存储空间 的例 Lf,注 意指针的用法。 稆序 1.1凋 用 ma11。 c的 参章分别对应类型 ht和 类型 ⒒oa△的存储空闸人小,返 冂值楚 指 向这块存储空间第一个字节的指针。这个函数的返冂类型对不同F向系统可能不同,有 些系 统返冂 char★ ,即 指 向 char的 指针。但 ANSI C返 冂vo土d★ 。标记 (土n△ *)和 "⒒ oa△ *) 足类型强制转换表达式,在 程序 1.1中 本来可以缺省,这 两个标记把返冂类型变换为正确的 类型。free函 数把以前用 ma11。 c申 请的存储空间释放。在有些版本的 C语 亩中,free耍 求的参董类型是 char★ ,而 ANSI C要 求的参蚩类型足 vo土d★ 。通常,￡ree的 参耄类型转 换都是缺省的
51.2指针和动态存储分配 int i,tpi; float f,.pf; pi (int )malloc(sizeof(int)); pf。(E1oat+ma1loc(aizeof(f1oat) *p1=1024: +pf=3.14: printf("an_integer_-td,_a_float_f\n",pi,pf)i tree(pi); free(pf】i 程序11分配、释放存储空间 如果存储空间不足，调用a11oc会使巾请尖败，以下给出的代码吏可靠，可以用米替 换程序1.1中调用ma11oc的相应代码。 ig ((pi (int +)malloc(aizeof(int)))==NULL (pf (float .)malloc(aizeof(float)))==NULL){ fprintf(stderr,Insufficient_memory"); exit (EXIT_PAILURE) 或使用以下等价的代码 if (!(pi (int .)malloc(sizeof(int))) :(pf =(float .)malloc(sizeof(float)))){ fprintf(stderr,Insufficient_memory") exit (EXIT FAILURE); 因为ma11oc在程序中经常出现，方使的做法是定义宏语句，在宏语句中调州ma11oc, 如果ma11oc失败则退出。以下是这种宏语句的一种实现： #define MALLOC(p,s)\ 1f(！(p)=ma11oc(8)))[\ fprintf(stderr,"Insufficient_memory");\ exit (EXIT_PAILURE);\ 现在，我可以用两条语句替换程序1.1中调用ma11oc的语句。 MALLOC(pi aizeof(int)): MALLOC(pf,sizeof(float)): 在序1.1中紧接printf语句之后桶入如下一行： pf=(float .malloc(siseof(float))
Ⅲ.2指 针和动态存储分配 int i, *Pi; float f, *Pf; pi = (int *)mall-oc (sizeof (int) ) ; pf = (fIoat *)malloc (sizeof (ftoat) ) ; *pi 1024; *pf = 3.L4; printf ( "an-integer-=-?d, -a-f1oat,=-?f\n", *pi, *Pf) ; f r e e (pi) ; f raa lnf \ \L-/, 程序 1.1分 配、释放存储空间 如杲存储空问不足,调 川 ma11⊙c会 使 巾活失败,以 卜给出的代码 吏可车,可 以用来替 换稆{1,1中 调川 ma11。c的 相应代码。 土￡ ((p土 = (土 nt *)ma11OC(g土 zeo￡ (土 nt))) == NULL || (p￡ = (￡ △° at ★ )ma11○ c(臼 土zeof(f1oa△ ))) == NULL) ( fprintf(stderr` "Insu￡ ￡土c土 ent凵 mem0ry")` ex土 t(EXIT FAILURE)氵 ) 或使用 以 卜等价的代码 土f (!(p土 = (土 nt ★ )ma11OC(臼 土zeo￡ (土n△ ))) || !(pf = (￡ 1° at ★ )ma11。 C(臼 土zeof(￡ △。at)))) ( ￡pr土 ntf(stderr` "Insuffic土 ent凵 mem⊙ ry")` exit(EX工 T FAILURE)` ) 囚为 ma1·1Oc在 程序 中经常 出现 ,方 便 的做法 楚定 义宏语 句,在 宏评扌句 中 调用 ma11。 c, 如 呆 ma11oc失 败则退 出。以 卜是这种宏讶i句 的 一种实现 : #de￡ 土 ne rˇ 】ALLoc(p`s) \ 土f (!(p) = ma11⊙ C(s))) (\ ￡pr⊥ nt￡ (stderr` "Insuff土 c⊥ ent凵 mem○ ry")氵 \ ex土 t(EXIT FAILURE)` \ ) 现在 ,我 们可 以川两条语句替换稆序 1,1屮 凋川 ma11。 c的 语句 。 MALLOC(p土 ` g土 zeof(土 n△ ))` MALL⊙ C(pf` s土 zeo￡ (f△ oat))氵 在稆序 1.1中 紧接 print￡ 语句之后插入如 卜 一行: pf = (f1° at ★ ) ma11⊙ C(臼 土zeof(f1。 a△ ))氵
6 第1章基本概念 这时，现指针指向的存储空间，不再是存放3.14的存储单元。现在无法再访问原米那块存储 空间。这是悬空引用(dangling reference)的一个例子。只要指向动态#储区域的指针丢掉 了，原存储区域对程序而言，就丢掉了。在程序中使用指针和动态存储分配时，应牢记一点， 如果不再需要一块动态存储空间，那么一定要把它还给系统。 51.2.3指针隐患 C程序中让所有尚未指向实际日标的指针都取L值是好习惯。这样做，可以尽量道 免访问一块尚未申请的空间，或访问一块我们并无权限访问的空间。有些计算机在涉及空指 针操作时，返同LL,能够接着执行，而另一些系统，将直接对地址单元0操作，引发严重 错课。 另一个好习惯是，在转换指针类型时，显式地使用强制类型转换，例如： pi malloc(sizeof(int)) /assign to pi a pointer to int/ pf=(float+）pi: /casts an int pointer to a float pointer + 需要指出，在很多系统中，指针类型的人小和1nt类型的人小相同。由于1nt是函数 返可的约定类刑， 一些序员定义函数时会省略返类型。数的返同类型如果没有显式定 义，那么这个约定的1t返同类型以后可能被解释为指针。事实证明，这种习惯对某些系统 是很危险的，因而，程序员应该明确指定函数的返同类型。 51.3算法形式规范 1.3.1综论 算法是计算机科学的基本概念。诈多问题都有现成的求解算法，对于人规模计算机系 统，设计高效算法是解决问题的核心。有鉴丁此，我必须片先米详细讨论算法概念。以卜 从算法定义开始。 定义算法是指令的有限集合，颜序执行这些指令，可以完成特定的任务。同时，所有算法 都遵循以卜判据。 ()输入从外界获取零个或多个苹。 (2)输出产生至少一个革。 (3)确定性每条指令清晰、无二义性。 (④)有限性算法对所有情形都能在执行有限步之后结束。 (⑤)有效性每条指令都是基本可执行的，意为借助纸、笔即可完成。判据(3)要求的确定性 并不充分，每条指令还必须是能行的(feasible)
第 】章 基本概念 这时,现 指针指向的存储空间,不 再足存放 3,14的 存储 弟元。现在无法再访问原来那块存储 空间。这是悬空引用 (dangling reference)的 一个例 fr。只要指向动态存储区域的指针丢掉 了,原 存储区域对稆序而言,就 丢掉了。在稆序中使用指针和动态存储分配时,应 牢记一点, 如呆不再需要一块动态存储空间,那 么一定要把它还给系统。 §1.2.3 指 针隐患 C程 序中让所有尚未指向实际 日标的指针都取 NuLL值 是好习惯。这样做,可 以尽董避 免访问一块 尚未中请的空问,或 访 问一块我们并无权限访问的空问。有些计算机在涉及空指 针操作时,返 冂 NuLL,能 够接着执行,而 另 一些系统,将 直接对地址单元 0操 作,引 发严重 错误。 另 一个好习惯是,在 转换指针类型时,显 式地使用强制类I刂转换,例 如: p土 = ma1△ oc(吕 土zeo￡ (土nt)); /★ aSs工 gn L。 pェ a po立 nter ε o 1nt ★ / pf = (￡ △。at ★ ) p土 氵 /★ caStS an Ⅰ nt poInter ε o a f王 oat po立 nter ★ / 需耍指出,在 很多系统中,指 针类型的人小和 主nt类 型的大小相同。由于 土n△是函数 返冂的约定类型,一 些稆序员定义函数时会省略返冂类型。函数的返回类型如呆没有显式定 义,那 么这个约定的 土nt返 冂类型以后可能被解释为指针。芋实证明,这 种习惯对某些系统 足很危险的,l,xl而,稆 序员应 该明确指定函数的返冂类型。 §1。3 算 法形式规范 § 1.3.1 综 论 算法是计算机利'丫的基本概念。许多问题都有现成的求解算法 ,对 △人规模计算机系 统,设 计高效算法是解决问题的核心。有鉴 T此 ,我 们必须首先来详细讨论算法概念。以 卜 从算法定义开始。 定义 算法足指令的有限集合,顺 序执行这些指令,可 以完成特定的任务。同时,所 有算法 都递循以 卜判据。 (1)输 入 从外界获取零个或多个蚩。 ⑵ 输出 产生至少 一个鞋。 (3)确 定性 每条指令清晰、无工义性。 (4)有 限性 算法对所有情形都能在执行仃限步之后纬束。 (5)有 效性 每条指令都是基本可执行的,意 为借助纸、笔即可完成。判据 lS)要 求的确定性 并不充分,每 条指令还必须足能行的 (feasible)。 □
51.3算法形式规范 7 计算理论范畴中的算法'与程序有不同含义，计算理论中的程序无需满足以上的判据(4) 例如，操作系统的工作模式是一个无限循环，无终止地等待为所有任务服务，这个系统程序 从不结米，除非系统出错而崩遗。本书讨论的程序总会结米，因而，本书不区分算法和程序。 这两个名词可以互换。 算法的描述方式可以多种多样，比如可以用白然语言，如英语，们这时必须保证每条指 令都是确定的。借助图形也可以表示算法，称为流程图，但只适用小而简单的算法。本描 述算法都用C语言，不过有时会用英语马C语言的组合表示算法。以下给出两个例子，说明 从问题描述到算法形成的转换过程。 例1.1（选择排序）设计程序，将n≥1个整数排序。以下是简单的求解过程： From those integers that are currently unsorted, find the smallest and place it next in the sorted list. (在当前所有未排序的整数中，找出最小的一个，把它放在当前有序表的后一个住置。) 丘然这句话充分描述了排序问题，但它并不是算法，因为其中有儿处疑问。例如，这句 话没告诉我们这些整数开始时如何存放，也没告诉我们结果存放在哪里，更没告诉我们存放 形式是什么。假定整数存放企数组中，数组名为113，那么第1个整数应存放在第i个位置， 即1ist),0≤i<n。程序1.2是构建算法的第一次尝试，注意它部分是C语言，部分是英 语。 for (i-0;isn;i++)( Examine list[i]to list [n-1]and suppose that the smallest integer is at list[min]; Interchange list [i]and list [min]; 程序1.2选择排序算法 要把程序12转换成真正的C语言，还必须实现两个已明确定义的子任务：一个是找出 最小整数，一个是将当前最小值马11t们交换。后一个子任务可以用函数（见程序1.3）实 现，也可以用宏实现。 void swap(int x,int ty) (/both parameters are pointers to ints + int temp -+x;/declares temp as an int and assignes to it the contents of what x points to/ *x=+y: /stores what y points to into the location where x points ty temp; places the contents of temp in location pointed to by y+/ 程序1.3swap函数
§】。3算 法形式规范 7 计算理论范畴中的算法Jj程 序有不同含义,计 算理论中的稆序无需满足以上的判据 ⑷ 。 例如,操 作系统的I作 模式足一个无限循环,无 终 l卜地等待为所有任务服务,这 个系统程序 从不结束,除 非系统出错而崩溃。本书讨论的程序总会结束,因 而,本 {氵不区分算法和程序, 这两个名词可以互换。 算法的描述方式可以多种多样,比 如可以用 白然语 亩,如 英语,但 这时必须保证每条指 令都是确定的。借助图形也可以表示算法,称 为流程图,但 只适用小而简单的算法。本书描 述算法都用 C语 言,不 过有时会用英语与 C语 言的组合表示算法。以 卜给出两个例子,说 明 从问题描述到算法形成的转换过程。 例 1.1(选 择排序)设 计稆序,将 彳≥1个 整数排序。以 卜足简单的求解过程: From those △ ntegers that are current△ y unsorted` f土nd the sma11est and p1ace 土 t next 土 n △ he sorted 1ist. (在当前所有未排序的整数中,找 出最小的一个,把 它放在当前有序表的后一个位置。) 虽然这句话充分描述了排序问题,但 它并不足算法,冈 为其中有儿处疑问。例如,这 句 话没告诉我们这些整数开始时如何存放,也 没告诉我们结呆存放在哪里,更 没告诉我们存放 形式足什么。假定整数存放在数组中,数 组名为 1土st,那 么第 J个 整数应存放在第 j个 位置, 即 1土st[j],0兰 j<彳 。程序 1.2是 构建算法的第一次尝试,注 意它部分足 C语 言,部 分是英 语。 for (i=0; i<n; i++) t Examine list til to l-ist [n-1] and suppose that the smallest int.eger is at list [min] ; rnterchange list Ii] and Iist [min] ; ) 程序 1.2选 择排序算法 耍把程序 1.2转 换成萁正的 C语 言,还 必须实现两个 已明确定义的1f任 务:一 个是找出 最小整数,一 个是将当前最小值 与 1土st[氵]交 换。后一个子任务可 以用函数 (见稆序 1.3)实 现,也 可 以用宏实现。 void swap(int *X, int *Y) {/* both parameters are pointers to ints */ int temp = *x; /* decTares temp as an int and assignes to it the contents of what x points to */ *x = *y; /* stores what y points to into the Tocation where x Points */ *y = temp; /* pTaces the contents of temp in Tocation pointed to bY Y */ ) 程 序 1.3swap函 数
8 第1章基本概念 以卜是这个函数swap的用法。假定a和b都声明为1t类型，要交换存放在两者中的 值，调用： swap(&a,&b): 传给awap的参数是a和b的地址。以下是交换两变革值的宏语句： #define SwAP(x,y,t)((t)-(x),(x)-(y),(y)-t) 两种实现各有优点，函数实现更易读，宏实现适用丁所有变量类型 现在，我转向第一个子任务。假定当前的最小值在1it的中，把它和1iti+1], 1sti+2,1istn-1山比较，只要找到更小值.就用它作最小值。这样，到11t[n-1 整个工作就完成了。把所有这些作组织在一起，就是函数soxt(见程序14)。程序1.4是 一个完整的程序，可以在计算机上运行。程序中用到定义在<st1ib.h>中的函数rand,它 产生一系列随机数传给8oxt。现在我价们要问这个函数是否正确。 定理1.1对于n≥1个元素的整数合，函数soxt(1ist,m)排序的结宋是正确的。数据 最后存放在在1ist[0],·,1ist[n-1)中，H1ist[0]<1ist[1]≤.<1istn-1]。 证明当最外层or循环结米第i=q次循环时，我们有11st[q1≤1ist[1,9<r<n。接 着，执行后续循环到i>q,此时从1ist[o]到1ist[q]的内容不变。因此，当最外层or执 行到最后一个循环时（即i=n-2之斤），有1ist[o]≤1ist【1]≤.≤1iat[m-1]。 例1.2（折半查找）假定n≥1个有序整数存储在数组11st之中，1ist[o]≤1ist[11≤.≤ list[n-1】。我们想知道整数searchnum是否出现在这个表中，如果是，则返问下标i, searchnum-1iat[：否则返可-l。由于这个表有序，可以用以卜方法在找给点值。 令1eft、right分别表示表中待香范阁的左、端点，初值为：1eft-0,right-n-1。 令mida1e=(1eft+right)/2,是表的中点下标值。searchnum和1ist[midd1e】比较的 果，有三种可能： (l)searchnume<list[middle],此时，如果searchnum在表中，它一定在位置0与middle-1 之间，因此，把right。设成midd1e-1. (2)searchnuma=1 ist [midd1e】。此时，返间midd1e (3)searchnum>list[middle】。此时，如果searchnum在表中，它一定在位置middle-1与 n-1之间，因此，把right设成mida1e-1。 当searchnum还没被在创，同时尚有没检查的其它整数，我们重新计算middle,重复上述 查找过程。程序1.5是这种查找策略的实现。算法包括两个子任务：()表中是否还有木查找 过的整数，(2)比较searchnum和1ist【midd1e】, 比较揉作既可以用函数实现，也可以用宏实现。尤论采用哪种实现，都需要分别为小于 等于、人」指定数值。我们遵循C语言库函数的习惯 ·若前者小于后者，则返同负数()
第 】章 基本概念 以 卜是这个函数 swap的 用法。假定 a和 b都 声明为 ht类 氵l刂,要 交换存放在两者中的 值,调 用: swap(&a` &b)' 传给 swap的 参数足 a和 b的 地址。以 卜是交换两变鞋值的宏语句: #de￡ 主ne SWAP(x`y`t) ((t) = (x)` (x) = (y)` (y) = t) 两种实现各有优点,函 数实现更易读,宏 实现适用 T、所有变章类型。 现在,我 们转 向第一个子任务。假定肖窝I的 最小值在 1主st[j]叶 I,把 它和 1土st[j+1]' 1土st[氵+2]`· .'1土s乜[彳-1]比 较,只 耍找到更小值,就 用它作最小值。这样,到 1土st[彳 一" 整个 I∶作就完成了。把所有这些 匚作组织在一起,就 是函数 sort(见 程序 1.4)。 稆序 1。4是 一个完整的稆序,可 以在计算机上运行。稆序屮用到定义在 <stⅡ b.h)中 的函数 rand,它 产生一系列随机数传给 sort。 现在我们耍问这个函数楚否正确。 定理 1.1对 Tˉ彳≡1个 元素的整数集合,函 数 sort(1ist`″ )引卜序的结呆足正确的。数据 最 后 存 放 在 在 1土 st[0]'. · '1土 st[″ -1]中 ,且 △土st[Ol兰 1土 st⒒ ]兰 . ·兰 1iSt!″ -1]。 证 明 当 最 外 层 ￡or循 环 结 束 第 j=呷 次 循 环 时 ,我 们 有 1主 st[叼 ]兰 1主 st[r]'呷 <r(″ 。 接 着,执 行后续循环到 j)呷 ,此 日寸从 1土st[O]到 1⊥st[q]的 内容不变。lAl此,当 最外层 for执 行 到 最 后 一 个 循 环 时 (即 j=彳 -2之 后 ),有 1⊥ st[0]兰 1iSt[△ ]兰 . ·兰 1土 st[彳 -11。 □ 例 1.2(折 半查找)假 定 刀≥1个 有序整数存储在数细^Ⅱ st之 中,1ist[0]兰 1土st⒒ ]兰 .·兰 1立st【彳-1]。 我们想知道整数 searchnum楚 否出现在这个表屮,如 呆足,则 返冂下标 j, searchnum=Ⅱ st[j];否 则返冂 -1。由 「这个表仃序,可 以川以 卜方法今找给点值。 令 1eft、 r土 ght分 别 表 示 表 中 待 杏 范 l+l的 左 、 亻 f端 点 ,初 值 为 :1eft=O'r土 ght=彳 -1。 令 m主 ddle=(1eft+r土 ght)/2,足 表 的 中 点 卜 标 值 。 searchnum和 1⊥ st[m土 dd1e]比 较 的 结 果 ,有 三 种 可 能 : (1)searchnum(1土 st[m土 dd1e]。 此 时 ,如 呆 searchnum在 表 中 ,它 一 定 在 位 置 0与 碱 dd1e-1 之 间 ,冈 此 ,把 right。 设 成 m土 dd1e1。 (2) Searchnum〓 △土st[m土 dd1e]。 此 日寸 , 返 「冂 midd1e。 ⑶ searChnum>1土 st[m土 dd1e]。 此 时 ,如 果 searchnum在 表 中 ,它 一 定 在 位 置 呐 dd1e-1与 ″ -1乏 间 ,冈 此 ,把 r土 gh匕 设 成 m土 dd1e-1。 当 searchnum还 没被兖到,同 时尚有没检兖的其它整数,我 们重新计算 m土ddle,重 复上述 杏找过稆。稆序 1.5足 这种杏找策略的实现。算法包括两个子任务:(1)表 中是否还有未杏找 过的整数, (2)比较 searchnum和 1土st[m土dd1e]。 比较操作既可以用函数实现,也 可以用宏实现。尢论采用哪种实现,都 需要分别为小于、 等丁:←人 l=指定数值。我们遵循 C语 占库函数的习惯: ·若前者小 丁:后者,则 返冂负数 ←1)