| 这个作业属于哪个班级 |

| ---- | ---- | ---- |
| 这个作业的地址 |
| 这个作业的目标 | 学习数组相关内容 |
| 姓名 | 黄静 |

0. 展示PTA总分

1. 本章学习总结

1.1 学习内容总结

1.1.1 基础知识

数组定义

int a[10];//定义一个一维数组a，并在内存中开辟了十个连续单元，用于存放数组a中的十个元素
int a[4][4];//定义一个二维数组a，存放四行四列的元素
char a[10];//定义一个字符数组a，实际存放九个字符，还有一个用于存放字符串结束符号'\0'

数组赋值

• 一维数组

for(i=0;i<n;i++)
{
   scanf("%d",&a[i]);
}

• 二维数组

for(i=0;i<n;i++)
{
   for(j=0;j<n;j++)
   {
       scanf("%d",&a[i][j]);
   }
}

• 字符数组

//第一种:只能输入不含空格的字符串
      scanf("%s",str)；

//第二种:循环输入，直到输入到结束标志后还得输入'\0'
      while ((str[i] = getchar()) != '\n') i++;      //结束标志'\n'可为其它字符
      str[i] = '\0';      //'\0'等同于0

或    while ((str[i] = getchar()) != '\n') i++;
      str[i] = 0;      //  0等同于'\0'

//第三种:接受带空格字符串，输入长度少于n-1，会多带一个换行符

fgets(str,7,stbin);      //数组名+数组长度+stbin，stbin表示标准输入流

数组初始化

static int a[10];      //全初始化为0

int a[10]={"1,2,3"}      //自定义初始化为多少，初始化几个数

static char s[]={"Happy"};
static char s[]="Happy";

数组输出

• 一维数组

for(i=0;i<n;i++)
{
   printf("%d",&a[i]);
}

• 二维数组

for(i=0;i<n;i++)
{
   for(j=0;j<n;j++)
   {
       printf("%d",&a[i][j]);
   }
   printf("\n");
}

• 字符数组

//第一种:只能输出不含空格的字符串
      printf("%s",str)；

//第二种:循环输出
      for (i = 0; i < k; i++)
      {
	 printf("%c", str[i]);
      }

//第三种:接受带空格字符串

fputs(str）

注意
字符数组中：'a'与"a"不同，"a"代表'a'和'\0' 字符数组最后必须要有结束符'\0'

1.1.2 查找数据

1.1.2.1 顺序查找

代码思路
按一定顺序将数组中各个数据与待查数据进行比较，看是否有与要查数据相等的数据

典型例题
7-2 查找整数 (10分)题目详情
本题要求从输入的N个整数中查找给定的X。如果找到，输出X的位置（从0开始数）；如果没有找到，输出“Not Found”。
输入格式：输入在第一行中给出两个正整数N（≤20）和X，第二行给出N个整数。数字均不超过长整型，其间以空格分隔。
输出格式：在一行中输出X的位置，或者“Not Found”。

1.1.2.2 二分查找

代码思路
一个有序数组中，假设为升序排列，如果查找的数字在数组范围内，第一个数下标设为low，最后一个数下标设为high，中间元素下标设为mid=(low+high)/2,比较x与a[mid]的大小，若a<a[mid],则下标范围变成low~mid-1，执行high=mid-1，如果a>a[mid],则下标范围变成mid+1~high,执行low=mid+1，重复查找，直到x==a[mid]或low>high。

伪代码

定义：数组a[]，查找的数 number ，下界下标 low ，上界下标 high ，下标中间值 mid ，表示是否存在的状态 flag = 0 ；
low = 0，high = n - 1 ；
if number 比 a[0] 小或比 a[n - 1]大  //number不在数组范围内 
    flag = -1 ；
    end if

    while (flag == 0 && low不超过high)
        min = low与high之和 / 2；
        if number等于a[mid]   
                flag = mid;
                输出：是该数组中第flag + 1个数
                break；
        end if
        else if number 小于 a[mid]  high = mid - 1；//在mid左半边找
        else low = mid + 1；//在mid右半边找
    end while；

if(flag==-1||low大于high)   输出：该数不在数组中；

1.1.3 插入数据

1.1.3.1 数组右移

代码思路

假设在一个从小到大排列的有序数组中：
输入一个数据，将数组中的数据与x逐一比较，直到x小于某个数，此数下标和其后下标都加一，相当于向后挪动一位，然后将x赋值给数组那个下标。

典型例题
简化的插入排序 题目详情
本题要求编写程序，将一个给定的整数插到原本有序的整数序列中，使结果序列仍然有序。
输入格式：输入在第一行先给出非负整数N（<10）；第二行给出N个从小到大排好顺序的整数；第三行给出一个整数X。
输出格式：在一行内输出将X插入后仍然从小到大有序的整数序列，每个数字后面有一个空格。

1.1.4 数组中删除数据

1.1.4.1 数组左移

代码思路

遍历数组，在找到要删除的数据后，将该数据后的每个数据向左移动一位，从而达到删除此数据的目的。

经典例题
数组元素的删除 题目详情
完成数组元素的移动功能：假设数组有n个元素，输入一个数x，把数组的第x个位置的元素删除了，后面的元素依次前进一个位置。 重复若干次这样的删除，得到最后的结果。
输入格式:第一行包括一个整数n（1<=n<=100），表示数组元素的个数。 第二行输入n个数组元素，均为整数，用空格隔开。 第三行输入一个数k（1<=k<=100），表示要进行k次删除。 接下来k行，每行一个数x，表示要删除第x个元素。
输出格式:输出经过k次删除后的数组，每两个元素之间用空格隔开。

1.1.4.2 重构数组

代码思路

在原先的数组上重新定义一个循环变量j，当数组str[i]!='\0'时，如果str[i]不等于需要被删除的数，那么重构的这个数组就等于这个数，从而使不需要被删除的数重新单独储存到以j为变量的str数组内。

伪代码

定义：数组 str[100]，循环变量 i，j；
给数组 str 赋值；
i=j=0；
while str[i]不等于'\0'
      if str[i]不等于需要被删除的数据
            str[j++] 等于 str[i]；      //使用循环变量 j 将数组重构
      end if
i++；
end while
str[j]等于结束符'\0' ；      //最后输入结束符,重构完成

1.1.5 数据排序

1.1.5.1 选择排序

代码思路

以从小到大排列为例：
第 1 趟循环：n-k 个数   在(a[0]到a[n-1]中找最小数   与a[0]交换
第 2 趟循环：n-1 个数   在(a[1]到a[n-1]中找最小数   与a[1]交换
第 k 趟循环：n-k 个数   在(a[k]到a[n-1]中找最小数   与a[k]交换
      ···      ···      ···
第 n-2 趟循环：2个数    在(a[n-2]到a[n-1])中找最小数   与a[n-2]交换
注意：n个数需要n-1轮循环嵌套

伪代码

for i=0 to n-2 do      //循环第i趟
      index=i;  //记录最小下标
            for j=i to n-1 do  //找最小值min对应下标      
                    if a[index]大于a[j]
                          index=i;
                     end if
             end for
      交换a[index]和a[i]
end for

典型例题

选择法排序 题目详情
本题要求将给定的n个整数从大到小排序后输出。
输入格式：输入第一行给出一个不超过10的正整数n。第二行给出n个整数，其间以空格分隔。
输出格式：在一行中输出从大到小有序的数列，相邻数字间有一个空格，行末不得有多余空格。

1.1.5.2 冒泡排序法

代码思路

以从小到大排列为例：
将相邻两个数比较,把小的数调到前头。经过第一趟比较，最大的数已沉底，在最后面，a[n-1]处，然后再在a[0]到a[n-2]之间两两比较，最大的数沉底，在a[n-2]，以此类推。
i=0      a[0]~a[n-1]两两比较
i=1      a[0]~a[n-2]两两比较
i        a[0]~a[n-i-1]两两比较
i=n-2    a[0]~a[1]两两比较

伪代码

for i=0 to n-2 do
      for j=0 to n-i-1 do
          if  a[j]大于a[j+1]    //相邻的数两两比较大小
                  交换a[j]与a[j+1]
           end if
      end for
end for

典型例题

冒泡法排序 题目详情
将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。通过一遍扫描，则最后一个元素必定是最大的元素。然后用同样的方法对前N−1个元素进行第二遍扫描。依此类推，最后只需处理两个元素，就完成了对N个数的排序。
本题要求对任意给定的K（<N），输出扫描完第K遍后的中间结果数列。
输入格式：输入在第1行中给出N和K（1≤K<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔。
输出格式：在一行中输出冒泡排序法扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。

1.1.6 数组枚举

枚举法：数组存放所有可能值，枚举值；可使代码更加简洁。

1.1.6.1 日期计算

计算并返回年，月，日所对应的是该年的第几天；

代码思路

定义一个两行十三列的二维数组，进行数组初始化，将闰年和非闰年每月的天数赋给数组，判断是否闰年，计算天数。

代码

int k, leap;
int tap[2][13] =
{
      {0,31,28,31,30,31,30,31,31,30,31,30,31},//初始化，非闰年
      {0,31,29,31,30,31,30,31,31,30,31,30,31}//初始化，闰年
};

leap = (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)//判断是否闰年

for (k = 1;k < month;k++)//计算天数
{
    day = day + tap[leap][k];
}
return day;

1.1.7 哈希数组

1.1.7.1 删除重复字符

代码思路

定义一个哈希数组hush[256]，初始化为0 
数组str[i]的值全部作为哈希数组的下标，给哈希数组赋值hush[str[i]]=1；
这样使得重复的数据只在哈希数组中储存一份
最后输出哈希数组等于 1 的下标，就删除了数据中重复的数据

注意：只得使用在范围小于256的情况下，且若有出现小数与负数不得使用

经典例题

删除重复字符 题目详情
本题要求编写程序，将给定字符串去掉重复的字符后，按照字符ASCII码顺序从小到大排序后输出。
输入格式：输入是一个以回车结束的非空字符串（少于80个字符）。
输出格式：输出去重排序后的结果字符串。

2. PTA实验作业

2.1 数组循环左移

数组循环左移 题目详情
本题要求实现一个对数组进行循环左移的简单函数，将每个整数循环向左移m个位置。

2.1.1 伪代码

定义一个数组a[100];
输入n个整数，移动m位；
if n大于等于m
      loc=n-m;
else
      loc= n - m % n;
for i=0 to n do
      m = loc % n;
      输入一个数，赋值给a[m];
      loc++;
end for
输出数组a;

2.1.2 代码截图

2.1.3 代码对比分析

二者不同

• 我是根据采用寻找数据之间的关系来找到与移动的数字有关系的下标loc，然后根据取余等操作使赋值从移动到的位置开始，到最后，再到零下标开始赋值
• 她是将数值统一向前移动，然后把第一位赋值到最后一位
• 她的代码比较好理解，而且简洁明了，使用数组移动完成；而我的代码比较繁杂，需要多次scanf，而且关键下标loc需要大量数据推测找出
• 我的代码最困难的是寻找关键的下标loc，使其可以令移动到后面的数值赋值到后面，而且后面的数值下标取余到前面

2.2 找鞍点

2.2.1 伪代码

输入二维数组数据
for i=0 to n do
      for j=0 to n do
            for k=j+1 to n do
                  比较第i行中数据大小，找到最大的数的列下标maxindex；
             end for
      end for
      同理，比较第maxindex列中数据大小，找到最小的数的行下标minindex；
      if minindex 与 此时的i相等   找到鞍点flag=1；
end for
if flag=1  输出鞍点的行下标，列下标
if flag=0  输出NONE

2.2.2 代码截图

2.2.3 两种代码对比分析

两种做法是一致的，超星视频中把整个寻找过程放在一个函数中，我把寻找行下标的过程放在一个函数中调用到寻找列下标之后。
超星视频中优点有：
* 使用break，提前退出循环，使程序更加有效率

知识点

• 使用break可提前退出循环，提高程序效率
• 灵活表示二维数组元素

if (a[i][j] >= a[i][maxindex] //同一行，行标相同
if (a[j][maxindex] < a[i][naxindex])  //同一列，列标相同

• 二维数组：两层循环操作

2.3 切分表达式

2.3.1 代码思路

需要思考以下几种情况
* 数字与数字一起时，不换行
* 小数点与前面的数字一起输出，不换行
* 数字后是运算符时，换行
* 当加减运算符在前面没有字符时或前面是'('时，为正负号，与数字一起输出不换行
* 其余情况都换行

2.3.2 伪代码

for(i=0; str[i]!='\0';i++)
      if str[i] 是数字或小数点
            输出str[i]
            if str[i+1]不是数字，不是小数点      //数字后为运算符
                  输出换行符
      else
            if str[i]为'+'或'-'
                  if str[i-1]为'('或i=0      //加号或者减号前面出现（ 或者什么都没有
                        输出str[i]      //为正负号
                  else  输出str[i]和换行符      //为加减号
             else 输出str[i]和换行符
end for

2.3.3 代码截图

2.3.4 两种代码对比分析

做法总题思路差不多，我的代码是先考虑特殊情况，再一般情况直接输出，超星视频里是先考虑一般情况，再考虑特殊情况
超星视频使用while循环来遍历数组，而我采用for循环来遍历数组，二者皆可实现遍历数组的目的
超星视频中优点有：
* 使用函数分装结构，使代码更加简洁明了
* 使用continue提前结束本次循环，提高程序效率

知识点

• 字符数组输入方式有三种，使用情况各不相同
• 字符数组循环停止条件可用 str[i]!='\0' 来表示
• 字符数组可通过控制下标来表示想表示的字符，如 str[i+1],str[i-1]
• 可使用continue提前结束本次循环，提高程序效率；