计算机系统概论十六章.doc

第十六章 指针和数组16.1 介绍在这一章，我们介绍（实际上是重新介绍）两个简单但是功能强大的程序设计概念：指针和数组。在我们写LC-3的汇编代码时，我们已经使用了指针和数组。现在，我们使用C语言来研究它们。指针就是一个如变量之类的存储对象的地址。使用指针，我们可以间接地访问这些提供了非常有用的功能的对象。例如，使用指针，我们可以构建一个修改被调用者传递的参数的函数。使用指针，我们可以构建一些复杂的在程序执行过程中可以增长和缩短的数据组织。数组是在存储器中被连续排列的一列数据。例如，在本书前半部分的LC-3的几个例子中，我们把一个字符文档表示成在存储器中连续排列的字符序列。这些连续排列的字符被称为字符数组。为了访问数组中的一个特定项，我们需要指明我们要访问的是哪个元素。正如我们即将看到的，一个像a4这样的表达式将访问名为a的数组中的第五个元素因为我们从元素0开始为数组计数，所以它是第五个元素。数组很有用，因为它们允许我们方便地处理一组数据，诸如向量、矩阵、列表和字符串，这些都自然的表示了现实世界的某些特定的对象。16.2 指针我们以一个经典的例子来讨论指针的用途。在图16.1所示的C程序中，函数Swap被设计用来交换它的两个参数的值。函数Swap被main函数调用，它的变元ValueA在这个程序中的值是3， 变元ValueB的值为4。一旦Swap将控制返回给main，我们期望ValueA和ValueB的值被交换。但是，编译并执行这段代码，你会发现传给Swap的两个变元仍然保留着原来的值。我们来检查一下在Swap函数执行时的运行时栈，分析一下这到底是为什么。图16.2显示的是函数完成之前，就在第25行的语句执行之后，但是控制还没有返回到main函数之前的运行时栈的状态。注意，Swap函数已经在它自己的活动记录中修改了参数firstValue和secondValue的局部副本的值。当Swap完成并将控制返回给main时，当Swap的活动记录从栈中弹出时，这些被修改的值就被丢掉了。main中的两个值没有被交换。我们的程序出现了错误。在C中，变元总是以值的形式从调用函数传递到被调用函数。C将出现在函数调用中的每个变元都作为表达式来计算，然后将表达式的值压入运行时栈中，以便将它们传递给被调用函数。Swap要修改调用者传递给它的变元，它就必须访问调用函数的活动记录为了修改变元的值，它必须访问它们存储的单元。Swap函数需要main中的ValueA和ValueB的地址，以便改变它们的值。正如我们将在下面几节看到的一样，指针及其相关运算使这些成为可能。16.2.1 声明指针变量一个指针变量包含了一个存储对象的地址，比如一个变量的地址。一个指针指向了它包含的地址中的变量。与指针变量有关的是它所指的对象的类型。所以，比如，一个整数指针变量指向一个整数变量。为了用C声明一个指针变量，我们使用下面的语法：int *ptr;这里，我们声明了一个名为ptr的变量，它指向一个整数。星号（*）表明后面的标识符是一个指针变量。C程序员经常说ptr是int星号类型。类似的，我们可以声明char *cp;double *dp;变量cp指向一个字符，dp指向一个双精度浮点数。指针变量的初始化方式与所有其他变量类似。如果一个指针变量被声明为一个局部变量，它就不会被自动初始化。使用*来声明指针变量的语法可能起初看起来有点奇怪，但是一旦我们学习了指针运算符，这种语法后面的基本原理就会变得更清楚。16.2.2 指针运算符C有两种与指针操作有关的运算符，地址运算符“&”和间接运算符“*”。地址运算符&地址运算符，它的符号是&，生成了它的操作数的存储地址，操作数必须是像一个变量那样的存储对象。在下面的代码序列中，指针变量ptr将指向整数变量object。第二个赋值语句的右手边的表达式生成了object的存储地址。int object;int *ptr;object = 4;ptr = &object;让我们查看一下这个序列的LC-3代码。两个声明的变量都是局部的，被分配到栈中。回忆栈底指针R5指向第一个被声明的局部变量，也就是这个例子中的object。ANDR0,R0,#0; 清空R0 ADDR0,R0,#4; R0 = 4STRR0,R5,#0; object = 4;ADDR0,R5,#0; 生成object的存储地址STRR0,R5,#-1; ptr = &object;图16.3显示了在语句ptr = &object;被执行以后，包含这段代码的函数的活动记录。为了让事情更具体，每个存储单元都标记了一个地址，这些地址是我们任意在xEFF0范围内选择的。栈底指针R5当前指向xEFF2。注意，object中包含了整数值4，prt中包含了object的存储地址。间接运算符*第二种指针运算符称为间接或者解除引用运算符，它的符号是星号，*（在这里发音为star）。这个运算符允许我们间接操作一个存储对象里的值。例如，表达式*ptr指的是被指针变量ptr指向的值。回忆前面的例子：*ptr指的是存储在变量object中的值。这里，*ptr和object可以互换使用。添加到前面的C代码的例子中，*ptr=*ptr+1;本质上，*ptr=*ptr+1;是object=object+1;的另一种方式。就像我们所见过的其他类型的变量，*ptr根据它出现在赋值运算符的哪一边来表示不同的意思。在赋值运算符的右边，它指的是出现在那个单元中的值（这个例子中是数值4）。在赋值运算符的左边，它指明了要作修改的单元（这个例子中是object的地址）。让我们查看一下前面代码中的最后一条语句的LC-3代码。注意，这段代码不同于假如最后一条C语句是object=object+1;而生成的代码。使用指针的间接引用，编译器为右边的间接运算符生成2条LDR指令，一个用来加载包含在ptr中的存储地址，另一个用来取出存在那个地址中的值。对左边的间接引用，编译器生成一条STR R1,R0,#0。如果那条语句变为object=*ptr+1;，编译器将会生成STR  R1,R5,#0。16.2.3 使用指针传递引用使用地址和间接运算符，我们可以修正图16.1中的不能实现两个参数交换的Swap函数。图16.4列出了一个被称为NewSwap的Swap的修正版本的程序。我们做的第一处修改是NewSwap的参数不再是整数，而是整数指针（int *）。这两个参数是要交换的两个变量的存储地址。在NewSwap的函数体的内部，我们使用间接运算符*获得这些指针所指的值。现在，当我们从main中调用NewSwap时，我们需要为我们想交换的两个变量提供存储地址，而不是像我们在前面的代码版本中提供变量的值。为了提供地址，&运算符实现这个目的。图16.5显示了当NewSwap函数中的不同语句被执行时的运行时栈。三个子图（A-C）对应于23、24和25行被执行后的运行时栈。通过设计，C按数值把信息从调用函数传递到被调用函数：也就是说，计算调用语句中的变元表达式的值，其结果通过运行时栈被传给被调用函数。然而，在NewSwap中，我们通过使用地址运算符&构建了一个对于变元的按引用的调用。当按引用传递变元时，其地址被传给被调用函数为了使其有效，变元必须是变量或其他存储对象（即，必须有个地址）。被调用函数就能使用间接运算符*来访问（以及修改）其对象的原来的值。16.2.4 空指针有时我们说指针不指向任何东西很有用。当我们讨论诸如在19章中的链表的动态数据结构时，你将会对为什么这个概念很有用的原因更加清楚。从现在开始，我们称那个不指向任何东西的指针叫做空指针。在C语言中，我们用下面的赋值语句指明这一点：int *ptr;ptr=NULL;这里，我们将NULL的值赋值给指针变量ptr。在C中，NULL是一个特别定义的预处理宏，它包含一个没有任何指针可以包含的值，除非指针包含空值。例如，在一个特定的系统中，NULL可能等于0，因为没有一个有效的存储对象可以存储在单元0中。16.2.5 阐明语法现在我们回顾在11章介绍的一些符号。既然我们知道如何传递一个引用，让我们重新查看I/O库函数scanf：scanf ("%d", &input );因为函数scanf需要使用从键盘读入的十进制数值更新变量input，所以scanf需要input的地址而不是它的值。这样，就需要地址运算符&。如果我们省略地址运算符，这个程序就会以一个错误结束。你是否能为发生这个的原因提出一个可能的理由？为什么没有引用，scanf就不可能正确的工作？在我们完成对于指针的介绍之前，让我们尝试搞清楚指针声明的语法。为了声明一个指针变量，我们使用下面的形式声明：type *ptr;在这里，type可以是任何预定义（程序定义的）的类型，诸如int、char、double等。名字ptr可以为任何合法的变量标识符。使用这个声明，当应用*（解除引用）运算符时，我们便能声明一个type类型的变量。也就是说，*ptr是type类型的。我们也能够声明一个返回指针类型的函数（我们为什么这么做将在后面的章节中变的更明显）。例如，我们能使用形如int *MaxSwap()的声明，声明一个函数。与所有其他的运算符一样，地址和间接运算符根据C语言中的优先级与结合性规则进行计算。这些运算符和其他所有运算符的优先级和结合性规则都被列于表12.15中。注意，两种指针运算符都有很高的优先级。16.2.6 一个包含指针的例子让我们查看一个包含了指针的例子。假设我们要编一个程序，给定一个整数除数与一个整数被除数，计算商与余数。也就是说，程序将计算都是整数的divident/divisor和divident%divisor。这个程序的结构非常简单，只需要顺序结构也就是说，不需要重复。然而，难点是我们想通过一个C函数计算商和除数。我们可以容易的构建一个函数产生单个输出结果（比如说，商），我们可以使用返回值机制返回调用者。一个只能计算商的函数由一条语句组成，如return divident/divisor;。然而，为了给调用函数提供多个值，我们将使用指针变量，通过引用机制进行调用。图16.6的代码中包含了实现这个工作的函数。函数IntDivide接受4个参数，两个是整数类型，另外两个是指向整数的指针。函数IntDivide用第二个参数y去除第一个参数x。结果的整数部分被赋值给指针quoPtr 所指向的存储单元，而余数部分被赋值给指针remPtr所指向的存储单元。请注意，函数IntDivide还返回了一个值来指明它的状态：如果除数为0，它返回一个-1，告诉调用者有错误产生。否则就返回一个0，告诉调用者计算已无故障完成。在返回之后，main函数检查返回值来判断商和余数中的值是否正确。利用返回值来标记在调用者和被调用者之间调用函数时发生的问题，对于传达调用时的错误情况是一种很好的保护性程序设计实践。16.3 数组 考虑一个程序，它保存在一次计算机工程课程考试中50个学生的期末成绩。最方便的存储这些数据的方法是声明一个单独的对象，比如examScore，我们把50个不同的整数值存储在其中。我们可以使用一个下标访问这个对象中的某个特定的考试成绩，下标是从这个对象顶部开始的偏移量。例如，examScore32提供了第33个学生的考试成绩（第一个学生的考试成绩存储在examScore0中）。这个例子中的对象examScore就是一个整数数组。一个数组就是一个类似的数据项的集合，顺序存储在存储器中。特别的，数组中所有的元素都必须是同一类型的（例如，int，char等等）。当程序运算的数据被自然的表达为一个连续的数值序列时，数组是最有用的。因为许多现实世界的数据属于这个类别（比如某门课程的学生考试成绩），数组是有用得令人不可思议的数据结构。例如，当我们想写一个程序使得接受从键盘输入的100个数字序列，并对它们按升序排列，这时，数组就会是对于在存储器中存储这些数字的自然的选择。如果我们使用在这之前用过的简单变量来写这个程序几乎是不可能的。16.3.1 数组的声明和使用 首先，让我们看看在C程序中怎样声明一个数组。和其他变量一样，数组必须有一个相关的类型。这个类型表明了存储在数组里的数值的属性。下面是对一个包含10个整数的数组的声明：int grid10; 关键词int表明我们声明的是整数类型的事物。这个数组的名称是grid。中括号表明我们声明的是一个数组，10则表示这个数组包含10个将被按顺序放在存储器中的整数。图16.7显示了grid如何被分配空间的图形表示。第一个元素，grid0被分配在最低的存储地址，而最后一个元素，grid9在最高的地址。如果数组grid是一个局域变量，那么它的存储空间将被分配于运行时栈上。 让我们来看看怎样访问数组中的不同的值。注意在图16.7中数组的第一个元素实际上编号为0，这表示最后一个元素编号为9。为了访问某一特定元素，我们在中括号中提供了一个下标，例如：grid6=grid3+1; 这条语句读出存储在grid的第四个（记住，我们从0开始编号）元素中的值，把它加上1，并把结果存储进grid的第七个元素中。让我们看看这个例子的LC-3代码。我们假设grid是分配在运行时栈中的唯一局域变量。这就意味着栈底指针R5将指向grid9。ADDR0,R5,# -9; 将grid的基址给R0 LDRR1,R0,#3; R1¬grid3 ADDR1,R1,#1; R1¬grid3+1STRR1,R0,#6; grid6 = grid3+1;注意到第一条指令计算出数组的基址，也就是grid0的地址，然后将其传给R0。数组的基址通常是数组的第一个元素的地址。我们可以通过将要访问的元素的下标加上基址，访问数组中的任意元素。数组的强大功能来自于数组的下标可以是任意的合法的C语言整数表达式这一事实。下面的例子显示了这点：gridx+1=gridx+2; 让我们看看这条语句的LC-3代码。假设x是被直接分配到运行时栈中的数组grid顶上的局部变量。 LDRR0,R5,# -10; 加载x的值 ADDR1,R5,# -9; 将grid的基址给R1 ADDR1,R0,R1; 计算gridx的地址 LDRR2,R1,#0; R2¬gridx ADDR2,R2,#2; R2¬gridx+2 LDRR0,R5,# -10; 加载x的值 ADDR0,R0,#1; R0¬x+1 ADDR1,R5,# -9; 将grid的基址给R1 ADDR1,R0,R1; 计算gridx+1的地址 STRR2,R1,#0; gridx+1=gridx+2;16.3.2 使用数组的例子我们从一个简单的C程序开始，此程序将两个数组的每个对应元素相加，得到两个数组的和。每个数组表示某门课程中的学生考试成绩列表。每个数组元素都包含一个学生的成绩。为了生成每个学生的累积点，我们想执行Totali=Exam1i+Exam2i。图16.8包含了读出两个10个元素的整数数组，把它们加为另一个10个元素的数组，并打印出这个和的C代码。一个风格上的注意：注意表示输入集合大小的常数值的预处理宏NUM_STUDENT的使用。这是预处理宏的通常的用途，通常它位于源文件的开头（或位于C的头文件中）。现在，如果我们想增加数组的大小，例如学生注册人数发生变化，我们只需改变宏的定义（一个改变），并重新编译该程序。如果我们不使用宏，那么改变数组的大小就需要在很多处修改代码。这些改变可能很难跟踪，忘记一处就可能导致程序无法正确运行。对于数组的大小，使用预处理宏是好的程序设计实践。现在来看一个包含数组的更复杂一些的例子。图16.9列出了一个从键盘输入一个十进制数的序列（总个数为MAX_NUMS），然后判断这个序列中的每个输入的数字重复出现的次数的C程序。然后，程序输出每个数字，以及它重复的次数。在这个程序里，我们使用了两个数组，numbers和repeats。它们被声明为包含MAX_NUMS个整数值。数组numbers存储输入的序列。数组repeats在程序中用来计算numbers中的元素在输入序列中重复出现的次数。例如，如果number3等于115，并且在输入序列中共有4个115（即，在数组numbers中有4个115），那么repeats3将等于4。这个程序由3个循环组成，中间的循环实际上是一个由两个循环组成的嵌套循环。第一个和第三个for循环是从键盘输入和产生程序输出的简单循环。中间的for循环包含嵌套循环。代码体判断每个元素在整个输入数组内重复的次数。外面的循环将变量index从0重复至MAX_NUMS；我们使用index从第一个元素numbers0到最后一个元素numbersMAX_NUMS扫描整个数组。内部循环也从0重复至MAX_NUMS，我们使用这个循环再次扫描整个数组，这次是判断与外部循环选择的元素（即，numbersindex）匹配的元素数目。每检测到重复一次(即，numbersrepIndex= =numbersindex)，数组repeats中的相应元素递加1（即，repeatsindex+）。16.3.3 数组作为参数在函数之间传递数组是十分有用的，因为它允许我们构建出能对数组进行运算的函数。假设我们想构建出能计算一个整数数组的平均值和中值的一系列函数。我们需要（1）把数组中的所有值从一个函数传递到另一个函数中，或（2）传递一个数组的引用。如果数组包含有大量元素，把每个元素从一个活动记录复制到另一个活动记录中可能非常花费执行时间。幸运的是，C语言本质上是通过引用传递数组的。图16.10是一个包含有一个函数Average的C程序，Average的一个参数是一个整数数组。当从main中调用函数Average时，我们传递给它的值与数组标识符numbers有关。注意，在这里我们没有使用我们在使用数组时经常用的包含有中括号 的标准符号。在C语言中，一个数组的名字指的是数组的基址。名字numbers等价于&numbers0。numbers的类型与int*类似。它是包含了一个整数的存储单元的地址。使用numbers作为传递给函数Average的变元，我们就是将数组numbers的地址压入栈中，并传递给函数Average。在函数Average内部，参数inputValues就被赋值为数组的首地址。在Average中，我们可以用标准的数组符号来访问原数组中的元素。图16.11显示了在从Average执行return（程序中的第34行）前的运行时栈。注意在函数Average的声明中输入参数inputValues是如何被指定的。括号 向编译器表明相关的参数将会是特定类型的数组的基址，在这个例子中是一个整数数组。因为在C语言中，数组是通过引用来传递的，所以一旦被调用函数将控制返回到调用函数，任何在被调用函数中对数组值的修改都是可见的。如果我们通过数值只传递一个数组中一个元素会是怎样？如果是通过引用呢？16.3.4 C中的字符串在C语言中，数组最通用的用途是字符串。字符串是表示文本的字符序列。字符串是简单的字符数组，它的每个后面的元素都包含字符串的下一个字符。例如char word 10;声明一个最多可以存储10个字符的数组。更长的字符串则需要更大的数组。如果字符串少于10个字符会怎样呢？在C语言及其他很多现代程序设计语言中，字符串的结尾用ASCII码值为0的空字符标记。它是标识字符串结尾的一个标记。那样的字符串也被称为以空结尾的字符串。'0'是对应于空字符的特殊序列。继续我们前面的声明：char word10;word0 = 'H'word1 = 'e'word2 = 'l'word3 = 'l'word4 = 'o'word5 = '0'printf ("%s", word);在此，我们为数组的每个元素一一赋值。数组将包含字符串“Hello”。注意字符串尾部的字符本身也是占用一个数组元素的字符。即使这个数组被声明为可以有十个元素，我们必须为空字符留下一个元素，因此比九个字符长的字符串不能被存储在这个数组中。在这个例子中，我们还使用了一个新的printf格式说明%s。这个说明从对应的参数所指的字符开始，以字符串末尾字符'0'结尾，打印出一个字符串。ANSI C编译器也允许在声明内被初始化。例如，前面的例子也可以被重新写成如下：char word10="Hello"printf("%s",word);要注意两点：第一，字符串使用双引号" "与单个字符区分开来。单引号用于单个字符，像'A'。第二，注意，编译器会在字符串的末尾自动加上一个空字符。字符串的例子图16.12是对字符串执行一个很简单但是很有用的基本操作的程序：计算字符串的长度。由于包含字符串的数组的大小并没有指明字符串的真实长度（然而，它指明了字符串的最大长度），我们需要查看字符串来计算它的长度。确定字符串长度的算法很简单。从第一个元素开始，到我们遇到空字符之前，计算出字符的数目。图16.12的代码中函数StringLength执行这个计算。注意在scanf语句中我们使用格式说明%s。这个说明让scanf从键盘上读入一串字符，直到遇到第一个空白字符。在C中，空格、制表符、新行、回车、垂直制表符，或换页字符都被视为空白。所以如果用户输入（摘自 The New Colossus，作者Emma Lazarus) Not like the barzen giant of Greek fame, With conquering limbs astride from lang to land;只有单词Not 被存进数组input中。文本行中余下的被保留，用于后面的scanf来读入。所以如果我们执行另一个scanf("%s",input)，单词like会被存入数组input中。注意空白是被说明%s自动丢弃的。我们将在18章，当我们更深入的查看C里的I/O时，我们再更进一步检查这个I/O的行为。注意单词最大长度是20个字符。那么如果第一个词更长一些会发生什么呢？函数scanf并不会检验数组input的大小，而是把字符存储进它提供的数组地址中，直到遇到空白为止。如果第一个词长度超过20个字符，那么会发生什么呢？被分配在main函数中的数组input后面的局部变量将会被改写。画出调用scanf前后的活动记录，看看为什么。在本章后面的习题中，我们给出了问题，你需要修改这段程序，以便在用户输入的单词长于数组input长度时给出提示。现在让我们查看一个使用先前的例子中的StringLength函数的更复杂一些的例子。这个例子列于图16.13中，在例子中，我们使用scanf从键盘中读入一个输入字符串，然后调用一个函数来反转该字符串。然后，被反转的字符串被显示在输出设备上。为了正确的反转字符串，函数Reverse执行了两项任务。首先它使用前面的代码例子中的StringLength函数来判断字符串的长度。然后它通过交换第一个和最后一个字符，第二个和倒数第二个字符，第三个和倒数第三个字符等等，来执行反转。为了执行交换，它使用了图16.4中的NewSwap函数的一个修改版本。重复对成对的字符调用CharSwap函数。首先，对第一个和最后一个字符调用CharSwap，然后对第二个和倒数第二个字符，依次进行。C的标准库提供了很多关于数组的预先写好的函数。例如，复制字符串的函数，结合字符串的函数，比较字符串的函数，或者计算字符串长度的函数都可以在C的标准库中找到，对这些函数的声明可以通过头文件<string.h>被包含进来。关于这些字符串函数的更多信息可以在附录 D.9.2中找到。16.3.5 C中数组与指针之间的关系你可能已经注意到在数组的名称和与数组相同类型的指针变量之间的相似之处。例如，char word10;char *cptr;cptr = word;是合法的，并且有时候是有用的代码序列。在这里，我们为指针变量cptr赋值为指向数组word的基址。因为它们都是字符指针，所以cptr和word可以交换使用。例如，我们可以通过使用word3或*（cptr+3）访问字符串中的第四个字符。尽管如此，二者之间的一个区别就是cptr是一个变量，从而可以被重新赋值。而另一方面，数组标识符word不能被重新赋值。例如，下面的表达式是非法的：word=newArray。标识符总是指向存储器中的一个被编译器放置数组的固定点。它一经分配，就不能再移动。表16.1显示了几个等价的包含数组和指针符号的表达式。表格中每一行都是相同含义的表达式。16.3.6解决问题：插入排序有了对数组的初步研究，我们现在可以尝试解决一个相当大的有趣（而且很有用处）问题：我们要写一个C程序，将一个整数数组按升序排列。也就是说，这段代码将数组a排列为如a0a1a2的顺序。为了完成这个任务，我们要使用一种被称为插入排序的排序算法。排序是一种重要的基本操作，从事计算的人们已经投入了大量的时间去理解，分析和完善排序过程。结果，有很多种排序算法，你会在接下来的计算课程中看到一些基本的技术。我们在这里使用插入排序，是因为它与我们现实世界中如何为事物排序相仿。它非常简单。插入排序最好是通过实例来描述。假设你想要把你的CD集按照艺术家的字母顺序排序。如果你使用插入排序对CD排序，你会把这些CD分成两组，一组是排好了序的，另外一组是没有排好的。一开始的时候，排好序的一组可能是空的，因为你所有的CD都还没有排好序。排序的过程通过从没有排好序的CD中拿出一张来，然后把它插入到排好序的CD中的合适的位置。比方说。如果已经排好序的组中有3张CD，一张是John Coltrane的，一张是Charles Mingus的，还有一张是Thelonious Monk的，然后插入一张Miles Davis的CD就意味着把它插在Coltrane的CD和Mingus的CD中间。你一直这样做下去，直到未排序的组中所有的CD都被插入到排好序的组内。这就是插入排序。我们如何把相同的技术应用于为一个整数数组排序？对前面的算法进行系统分解，我们可以看到程序的核心包括对整个数组元素进行重复，把每一个元素都插入到一个新的所有元素按升序排列的数组的合适位置中。这个过程将一直进行，直到原始数组的所有元素都被插入到了新的数组中。一旦完成，新的数组中就包含了和原来的数组里面相同的元素，只不过是按顺序排列而已。对于这个技术，我们主要需要表示两组元素，原来的未排序的元素，和已经排序的元素。为此，我们可以使用两个不同的数组。然而，事实上，我们可以用原来的数组来表示两组元素。这样做，可以减少存储空间的使用，并且更加紧凑，只是比我们第一眼所看到的要复杂一些。数组的最初部分包含已经排好序的元素，数组的其余部分包含未排好序的元素。我们取出下一个未排好序的元素，把它插入到排好序的部分中的正确位置上。我们一直这样做下去，直到遍历整个数组。实际的InsertionSort程序（如图16.14所示）包含一个嵌套循环。外层循环扫描所有未排好序的元素（类似于一个一个的遍历未排好序的CD）。内层循环扫描已经排好序的元素，从而扫描到插入新元素的位置。一旦我们检测到一个已排序的元素比我们要插入的元素大，我们就把那个新元素插入这个更大的元素和它前面的一个元素之间。让我们通过检查在一次插入排序过程中发生了什么，来进一步观察。假设我们查看当变量unsorted等于4时的插入排序过程（3343行），数组list包含以下10个元素：2 16  69  92  15  37  92  38  82  19在这一次中，代码把list4，或15插入数组中已经排好序的那部分，从list0到list3中去。内层循环在已排好序的元素中重复变量sorted。它从编号最高的元素重复到0（即从3降到0）。注意，一旦发现某个元素小于当前的元素15，for循环的条件将终止这个循环。在每个内层循环（3841行）中，数组里已排好序部分中的一个元素被复制到数组的下一个位置。在第一次重复里，list3被复制到list4。于是经过内层循环的第一次重复后，数组list将包含2 16  69  92  92  37  92  38  82  19注意我们已经覆盖了15（list4）。这样做是可以的，因为我们已经把这个值复制到变量unsortedItem中了（在34行）。第二次重复对list2执行同样的操作。经过第二次重复后，list将包含2 16  69  69  92  37  92  38  82  19经过第三次重复后，list将包含2 16  16  69  92  37  92  38  82  19这时这个for循环将终止，因为计算出的条件不再为真。更确切地说，listsorted>unsortedItem不为真。当前的已排好序的元素list0为2，不大于当前的未排序的元素unsortedItem，其值为15。现在，内层循环终止，它后面的一条语句listsorted+1=unsortedItem;被执行。现在数组的已排好序的部分多包含了一个元素，并且list包含2 15  16  69  92  37  92  38  82  19这个过程一直继续下去，直到所有元素都被排好序，这也就意味着外层循环已经重复了数组list里的所有元素。16.3.7 C中数组的常见错误不像其他的一些现代程序设计语言，C语言不提供防止超出数组大小（或边界）的保护措施。这是C语言程序设计用到数组时常见的一个错误。C对确保一个数组下标位于数组内部没有提供任何支持。编译器盲目的为表达式ai生成代码，即使下标i访问了一个超出数组尾部的存储单元。为了显示这一点，图16.15的代码给出了一个关于超过数组边界是如何导致一个严重的调试工作的例子。输入一个比数组大小大的数字之后，这个程序表现出了某种特殊的行为。通过画出运行时栈来分析这个程序，你会对为什么这个错误造成了这种结果更加清楚。C在访问数组时并不进行范围检测。因为这样的话，数组访问导致更少的开销，C代码趋于更快。这也是C比其他语言为程序员提供了更多的控制能力的另一种方式。然而，如果你在编码时不小心，这种基本原理却能够导致在调试上花费力气。为了防止这一点，当使用数组时，有经验的C程序员经常使用一些特殊的保护性程序设计技术。另一个C语言中常犯的错误总与一个事实有关，那就是数组（特别是像我们已经见过的静态声明的数组）必须有一个固定的大小。当我们编译这个程序时我们必须知道数组的大小。C不支持使用变量表达式的数组声明。以下的这段C代码是非法的。当编译器分析源代码时，数组temp的大小必须是已知的。void SomeFunction(int num_elements) int tempnum_elemments; /*生成语法错误*/为了处理这个限制，C程序员仔细分析他们的代码将要被使用的情形，然后为数组分配足够的空间。为了在他们的代码中补充这个固有的假设，范围检查被加入到程序中来，以警告数组的大小是否足够。另一个可选择的方法就是使用动态存储分配，在运行时为这个数组分配空间。更多有关方面内容将在19章介绍。16.4 总结在这一章中，我们介绍了两种重要的高级语言的结构：指针和数组。这两种结构都能使我们间接访问存储单元。我们在这一章中介绍的关键概念是：² 指针指针是包含其它存储对象（比如其它变量）的地址的变量。通过指针我们可以间接的访问和操作这些对象。一个非常简单的指针应用就是使用它们按引用传递参数。指针还有更多重要的应用，我们会在下面的章节中看到。² 数组数组是被连续分配在存储器中的相同类型的元素集合。我们可以通过提供一个下标访问数组中的某个特定元素，下标是该元素相对数组开头的偏移量。许多现实世界中的对象在计算机程序中最好的表示是作为数组元素，因此对于组织数据，数组是一个重要的结构。例如，使用数组，我们能够表示包含文本数据的字符串。我们看过几个重要的数组操作，包括通过插入排序进行排序操作。习题16.1 写一个C函数，把一个未知长度的字符串作为参数，函数将字符串的第一个字符移到字符串末尾，再与“ay”相连接。例如，如果传递的字符串是“Hello”，则函数返回后，原字符串变为“elloHay”。假设数组包括足够的空间，可以将额外的字符添加进去。16.2 写一个C程序，接受用户输入的一列数，直到用户输入的数字与前一次输入相同结束。程序输出数字的个数及总和（不包括最后一个数）。当程序运行时，提示和响应情况如下所示：Number: 5Number: -6Number: 0Number: 45Number: 454 numbers were entered and their sum is 44.16.4 写一个函数，比较两个输入的字符串stringA和stringB。如果二者相同，返回0；如果stringA按照字典顺序，出现在stringB之前，返回1；否则，返回2。16.6 将如下C函数翻译为LC-3汇编语言。16.7 在如下程序中，ind是一个指向指针的指针，在C中是合法的。请画出在语句apple+;执行之后的运行时栈。16.8 如下代码包含一个对函数triple的调用，triple的活动记录至少有多大？16.9 写一个C程序，将一列数中重复出现的数字的副本移走。例如，如果对于一列包含5、4、5、5和3的数字，程序的输出是5、4和3。16.10写一个C程序，找出一列数的中值。中值是指在数列中，有一半数字比它大，另一半比它小。提示：需要先对数列排序。16.11 对于如下C程序：a) main函数和FindLen函数的活动记录的大小分别是多少？b) 如果输入的字符串是apple，请描述FindLen函数返回之前的栈中的内容。c) 在程序运行时，如果用户输入的字符串多于10个字符，活动记录的状态如何？程序将出现什么情况？16.12 如下代码从键盘读入一个字符串，将其中的大写字母转换为小写字母后输出。但是代码中有一个问题，请指出。16.13 对于如下声明：a 声明的函数Push将item的值压入堆栈顶部。如果堆栈已满，就不能再增加元素，函数返回一个1。如果该元素被成功压入，函数则返回一个0。b 写一个函数Pop，从栈顶取出一个元素。与Push类似，如果堆栈为空，Pop操作不成功，函数返回一个1。如果操作成功，则返回一个0。提示：如何将取出的元素返回给调用者？