软件设计师考试 | 第十二章软件系统分析与设计 | 算法分析与设计

不念不忘少年蓝@ 2022-10-06 12:51 178阅读 0赞

### 文章目录 ###

*   *  （一）C程序设计语言与实现
     *   *  1. 指针类型
         *   *  （1）变量和指针
             *  （2）通过指针访问数组中的元素
             *   *  1）指针变量与一维数组
                 *  2）指针变量与二维数组
             *  （3）指针与函数
             *   *  1）函数参数为指针
                 *  2）函数返回值为指针
                 *  3）指针变量
         *  2. 指针与数据结构
     *  （二）算法设计与实现
     *   *  1. 算法设计过程
         *  2. 算法问题类型

## （一）C程序设计语言与实现 ##

指针是`C`语言的精华部分，它极大地丰富了`C`语言的功能。通过利用指针，可以描述复杂的数据机构，在编程时能很好地利用内存资源，使其发挥最大的效率。

### 1. 指针类型 ###

#### （1）变量和指针 ####

**变量：** 是内存单元的抽象。变量具有类型、值、地址、作用域和生存期等属性。

变量的本质是程序中用来存放数据的一段存储空间。一般情况下，变量所对应的存储空间在内存区域，在`C`语言中程序员可以通过关键字`register`声明变量的存储单元是`CPU`中的寄存器。

变量的数据类型不同，它所占的内存单元数也不同。

在访问变量时，首先应找到其在内存的地址。如果在程序中将变量的地址保持在另一个变量中，则形成指针变量，通过指针对所指向变量的访问是一种对变量的“间接访问”。

例如：

定义了两个变量：
    整形变量 a 和指针变量 ptr ，
    在存取变量 a 中的数据时，
    可通过变量 a 或指向变量 a 的指针来进行，
    分别称为直接访问和间接访问。
    //a是整形变量，其值为整数
    int a;
    /*
    ptr是指针变量，
    其值为一个整型变量的地址
    */
    int *ptr;
    
    （1）直接访问变量 a 中的数据
    a = 5;
    a + 10;
    （2）简介访问变量 a 中的数据
    /*
    将变量 a 的地址赋值给指针变量 ptr ，
    称 ptr 指向变量 a
    */
    ptr = &a;
    /*
    指针变量 ptr 指向的对象用 *ptr 表示
    等价于 a=5; ，
    通过指针变量 ptr 访问变量 a
    */
    *ptr = 5;

经过上述定义和处理后，变量`a`和指针变量`ptr`之间的关系如下图所示：  
![指针变量ptr与指针变量指向的对象\*ptr(a)][ptr_ptr_a]

#### （2）通过指针访问数组中的元素 ####

`C`程序中常利用指针对数组和字符串进行处理。

一个数组由连续的一块内存单元组成，数组名就是这块连续内存单元的首地址（起始地址）。一个数组是由各个数组元素组成的，每个数组元素按其类型不同占有若干个连续的内存单元。

##### 1）指针变量与一维数组 #####

指针变量指向一维数组的方法如下所示：

定义一个整型数组 st 
    和指向数组元素的指针 ptr。
    //定义包含10个整型数据的数组
    int st[10];
    /*
    定义 ptr 为指向整型变量 st[0] 的指针，
    等价于 int *ptr = st
    */
    int *ptr = &st[0];

若`ptr`指向数组的第一个元素（即下标为`0`的元素），则`*(p+i)`指向数组的第`i+1`个元素（即下标为`i`的元素）。

##### 2）指针变量与二维数组 #####

指针变量指向二维数组的情形比较复杂，举例说明：  
定义`int a[3][4]`，其元素布局如下图所示：  
![二维数组a\[3\]\[4\]元素布局][a_3_4]

数组`a[3][4]`可看作是由`3`个一维数组（`a[0]`、`a[1]`、`a[2]`）构成的一维数组，每个一维数组的元素是`4`个。`a`是二维数组名，它代表整个二维数组的首地址。

`a[0]`是第`0`个一维数组的数组名和首地址。`*(a+0)`、`*a`和`a[0]`是等效的，它们都表示一维数组`a[0]`的`0`号元素的首地址。`&a[0][0]`表示`a`的第`0`行和第`0`列元素的首地址。因此，`a`、`a[0]`、`*(a+0)`、`*(a+1)`和`&a[0][0]`所表示的内容相同。

对于二维数组`a[m][n]`、`a+i`、`a[i]`、`*(a+i)`和`&a[i][0]`是相同的。

#### （3）指针与函数 ####

`C`程序中将指针与函数结合使用的常见方式有函数参数为指针、函数返回值为指针及通过函数指针变量调用函数（函数指针变量）。

##### 1）函数参数为指针 #####

参数使用指针类型的作用是将一个变量的地址传送到另一个函数中。

`C`语言中实参向形参传值，反之则不行。

例如：

定义函数 swap(a,b)的功能是
    交换 a 和 b 的值，代码如下：
    void swap(int a,int b){
      int temp;
      temp = a;
      a = b;
      b = temp;
    }

如果发生函数调用`swap(x,y)`，则系统将`x`的值传给`a`、`y`的值传给`b`，在函数中实现了`a`和`b`的值的交换，但是`x`和`y`的值并没有发生交换。

为实现将函数中对形参的修改结果返回给调用函数，可使用指针参数。

对上个例子进行修改，代码如下：

void swap_1(int *a,int *b){
      int temp;
      temp = *a;
      *a = *b;
      *b = temp;
    }

当形参为指针类型时，传递给形参的应该是地址信息，因此调用`swap_1`的形式为`swap_1(&x,&y)`。这样通过“间接访问”，实现了在被调用函数中修改实参所对应的变量。

##### 2）函数返回值为指针 #####

函数类型是指函数返回值的类型。返回指针的函数称为指针型函数。需要注意的是，不能返回局部数据的指针。

例如下面的函数，函数`get_str`虽然返回了局部数组`str`的首地址，但调用`get_str`的其他函数并不能通过此地址访问字符串`testing local pointer`。

char* get_str(void){
      char str[] = {"testing local pointer"};
      return str;
    }
    
    int main(){
      char *p;
      int i;
      p = get_str();
      for(i = 0; *(p+i); i++)
        putchar(*(p+i));
      return 0;
    }

将函数`get_str`中的`char str[] = {"testing local pointer"};`改成`char *str = {"testing local pointer"};`即可。

##### 3）指针变量 #####

程序中的一个函数总是占用一段连续的内存区，而函数名就是该函数所占内存区的首地址。可以把函数的首地址（或称入口地址）赋给一个指针变量，使指针变量指向该函数，然后通过指针变量就可以找到并调用这个函数。

指针函数的指针变量称为“函数指针变量”。

函数指针变量定义的一般形式为：

类型说明符 (*指针变量名)();

其中，“类型说明符”表示被指明函数的返回值的类型；“(`*`指针变量名)”表示`*`后面的变量是指针变量；最后的一对空括号表示指针变量所指向的对象是一个函数。

例如，下面定义了一个函数指针变量`funptr`。

int (*funptr)();

### 2. 指针与数据结构 ###

随着软件开发环境的不断完善和程序语言的抽象程度不断提高，数据结构的内部设计细节被封装和屏蔽起来，在很多应用软件的开发中没有必要也不再涉及底层细节，但是在系统级程序设计或嵌入式应用的软件设计中，指针及相关机制的应用仍然是十分必要的。

--------------------