report3.md · bzu-c/cp-reports

# 实验三：数组的应用

**1. 实验目的与要求**

（1）学会一维数组、二维数组的定义、引用；

（2）理解字符串的存储与处理；

（3）理解并能够将数组信息传递给函数；

（4）能在实际应用中使用基于数组的一些算法。

**2. 实验内容**

（1）数组的定义与初始化；

（2）数组元素的输入/输出；

（3）字符数组与字符串的相关操作；

（4）查找算法；

（5）排序算法。

## 问题1：数组算法经典

### 1. 问题陈述

以函数形式实现下列算法。
```c
// 找出数组 a[n] 中的最大值并返回
int find_largest(int a[], int n);
// 找出数组 a[n] 中的最小值并返回
int find_smallest(int a[], int n);
// 在数组 a[n] 中查找 x，若找到则返回 x 的下标，找不到时返回 -1
int find(int a[], int n, int x);
// 对数组 a[n] 按从小到大选择排序
void selection_sort(int a[], int n);
// 对数组 a[n] 按从大到小冒泡排序
void bubble_sort_desc(int a[], int n);
```
为方便测试还可以编写输入输出数组数据的函数：
```c
// 输入数组中的数据
void input_array(int a[], int n);
// 打印数组元素
void print_array(int a[], int n);
```
程序运行效果：
```
Enter n: 10
Enter 10 integer numbers: 3 1 4 1 5 9 2 6 5 3
a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}
The largest number is 9
The smallest number is 1
Enter a number to find: 5
Found a[4] = 5
Enter a number to find: 0
Not found
After selection sort:
a[] = {1, 1, 2, 3, 3, 4, 5, 5, 6, 9}
After bubble sort:
a[] = {9, 6, 5, 5, 4, 3, 3, 2, 1, 1}
```

### 2. 输入输出描述

#### （1）求最大值 `int find_largest(int a[], int n)`

- 输入：数组 `a[n]`
- 输出：数组元素的最大值

### 3. 演算示例

#### （1）求最大值 `int find_largest(int a[], int n)`

示例1：数组内容 `a[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}`，则函数返回其中的最大值 9。

### 4. 算法设计

#### （1）求最大值 `int find_largest(int a[], int n)`

算法伪代码如下：
```
// 找出数组 a[n] 中的最大值并返回
FUNCTION find_larges(a, n)
    INPUT: 数组 a[n]
    OUTPUT: 数组元素的最大值 largest

// 先设第一个元素为最大值
    largest = a[0]

// 与数组中其余元素逐个比较，并更新最大值
    FOR i = 1 to n-1 DO
        IF a[i] > largest THEN
            largest = a[i]  // 更新最大值
        END IF
    END FOR
END FUNCTION
```

```
// 找出数组 a[n] 中的最大值并返回
Function find_largest (Integer Array a, Integer n)

// 先设第一个元素为最大值
    largest = a[0]
    
    // 与数组中其余元素逐个比较，并更新最大值
    For i = 1 to n - 1
        If a[i] > largest
            largest = a[i]
        End
    End
Return largest
```

![输入图片说明](imgfindlargest.png)

程序代码：
```c
// 找出数组 a[n] 中的最大值并返回
int find_largest(int a[], int n)
{
    int largest = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > largest)
            largest = a[i];
    return largest;
}
```

### 5. 测试

结果与演算示例一致，测试通过。

### 总结

## 问题1：数组计数器

### 1. 问题陈述

利用数组，以函数形式实现下列算法。
```
// 判断正整数 n （的十进制表示）中是否存在重复的数字
bool has_repeat_digit(int n);
// 判断两个正整数 m 和 n （的十进制表示）是否由相同的数字组成
bool is_similar(int m, int n);
// 判断 n 个学生成绩中是否存在相同的分数（0 到 100 之间的整数）
bool has_same_score(int score[], int n);
```

### 2. 输入输出描述

#### （1）判断重复数字 `bool has_repeat_digit(int n)`

- 输入：正整数 n
- 输出：如果 n 的十进制表示中存在重复的数字，则返回 true，否则返回 false

### 3. 演算示例

#### （1）判断重复数字

示例1：$n=12345$，其十进制表示中没有重复数字，返回结果 `false`。

示例2：$n=12321$，其十进制表示中有重复数字 1 和 2，函数返回 `true`。

### 4. 算法设计

#### （1）判断重复数字

算法伪代码如下：
```
// 判断正整数 n （的十进制表示）中是否存在重复的数字
FUNCTION has_repeat_digit(n)
    INPUT: 正整数 n
    OUTPUT: 如果 n 的十进制表示中存在重复的数字，则返回 true，否则返回 false

// 初始化标记数组为 0
    digit_seen[10] = { 0 }

// 逐个取出 n 的十进制数字，并判断是否存在重复数字
    WHILE n != 0 DO
        // 取个位数字 digit
        digit = n % 10
        // 判断数字 digit 是否出现过
        IF digit_seen[digit] == 1 THEN // 数字 digit 已经出现过
            RETURN true              // 有重复数字
        ELSE // 数字 digit 第一次出现
            digit_seen[digit] = 1    // 在标记数组中做标记
        END IF
        // n 缩小 10 倍
        n /= 10;
    END WHILE

// 未发现重复数字
    RETURN false
END FUNCTION
```
程序代码：
```c
// 判断正整数 n （的十进制表示）中是否存在重复的数字
bool has_repeat_digit(int n)
{
    // 初始化标记数组为 0
    int digit_seen[10] = { 0 };

// 逐个取出 n 的十进制数字，并判断是否存在重复数字
    while (n != 0) {
        // 取个位数字 digit
        int digit = n % 10;
        // 判断数字 digit 是否出现过
        if (digit_seen[digit] == 1)  // 数字 digit 已经出现过
            return true;             // 有重复数字
        else // 数字 digit 第一次出现
            digit_seen[digit] = 1;    // 在标记数组中做标记
        // n 缩小 10 倍
        n /= 10;
    }

// 未发现重复数字
    return false;
}
```

### 5. 测试

结果与演算示例一致，测试通过。

### 总结

bzu-c/cp-reports

简介

发行版

贡献者

近期动态

bzu-c/cp-reports .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

bzu-c/cp-reports