我是靠谱客的博主 感性西装,这篇文章主要介绍C语言--数组~~段首鸣谢好久没有整整个了。0. PTA上数组题目的截图:1. 本章学习总结:2. PTA实验作业(7分),现在分享给大家,希望可以做个参考。
| 这个作业属于哪个班级 | C语言–网络2011/2012 |
|---|---|
| 这个作业的地址 | C语言博客作业04–数组 |
| 这个作业的目标 | 学习数组相关内容 |
| 姓名 | 骆锟宏 |
文章目录
- ~~段首鸣谢好久没有整整个了。
- 0. PTA上数组题目的截图:
- 1. 本章学习总结:
- 1.1 数组中查找的方法
- 1.1.1 顺序查找法:
- 1.1.2 二分查找法:
- 1.2 数组中插入数据的方法
- 1.3 数组中删除数据的方法
- 1.3.1 简单地删除某几个数:
- 1.4 数组中目前学到的排序方法及其主要思路
- 1.4.1 选择排序法:
- 1.4.2 冒泡排序法:
- 1.5 数组做枚举用法及其案例
- 1.6 哈希数组用法及其案例
- 1.7 字符数组、字符串特点及编程注意事项
- 1.7.1 字符数组的输入:
- 1.7.2 字符数组的函数接口设计:字符数组的数组名本身就代表了字符数组的首地址。所以在传参的时候,只需要把字
- 1.7.3 字符串的输出:
- 1.7.4 字符串的转换:
- 2. PTA实验作业(7分)
- 2.1 判断上三角矩阵(3分)
- 2.1.1 伪代码
- 2.1.2 代码截图
- 2.1.3 代码比较(感谢陈剑同学的大力支持!)
- 2.2 找鞍点
- 2.2.1 伪代码
- 2.2.2 代码如下:
- 2.2.3 请说明和超星视频做法区别,各自优缺点。
- 2.2.4 或许这道题目可能存在测试数据的不够丰富:
- 2.2.5
- 2.3 切分表达式(2分)
- 2.3.1 伪代码
- 2.3.2 代码截图
- 2.3.3 请说明和超星视频做法区别,各自优缺点。
~~段首鸣谢好久没有整整个了。
- 感谢这篇文章的作者,这里引用过来作为拓展资料。浅谈排序算法
0. PTA上数组题目的截图:
数组:

字符数组:

1. 本章学习总结:
1.1 数组中查找的方法
1.1.1 顺序查找法:
- 以PTA题目查找整数为例:核心思想就是,遍历数组,然后让数组中的每一个数与目的数进行比较,如果存在相同的情况,那就记下数组当中该数的下标,
记下下标也就算是找到了该数。
//顺序查找法,实质是遍历数组一一比较;
for (Index = 0; Index < N; Index++)
{
if (a[Index] == X)
{
flag = 1;//此时表示已经找到
loc = Index;
}
}
//为了输出方便一般会另设一个标记变量来标记找到与否。
1.1.2 二分查找法:
- 以课堂派的测试题为例:核心思想就是,让这个数不断和已知数组中的中间数进行比较,每次比较过后缩减一半的范围,直到最后无法再缩减,找到数字,或者
数组中不存在该数字,找不到。
//假设存在数组a[],find表示要找的数,left表示左界的下标,right表示右界的下标。
while (left <= right)
//这种情况下相等的情况也要考虑,而且往往找到的情况是left = right = middle的情况!
{
middle = (left + right) / 2;
if (find == a[middle])
{
printf("这个数是第%d个数", middle + 1);
break;
}
else if (find > a[middle])
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}
if (left > right)
{
printf("找不到这个数");
}
1.2 数组中插入数据的方法
- 数组当中插入数据的办法:往往是先找到需要插入的位置,然后从最后一个数字开始,
慢慢地把数字一个一个,往后移动,最后空出插入的目的位置给需要插入的数字。 - 但是要求是,数组的长度要足够长,必须要大于已经存在的数字和想要插入的数字的个数之和。
- 如果要插入多个数字,只需要对要点一进行重复操作就行。
以PTA中简化的插入方式这道题为例可知:
//判断代码可以插入的位置;
for (count = 0; count < numbN; count++)
{
if (numbX > a[count])
{
loc = count + 1;
}
}
//将数组中从这个位置开始向后移;
for (countChange = numbN; countChange > loc; countChange--)
{
a[countChange] = a[countChange - 1];
}
a[loc] = numbX;
1.3 数组中删除数据的方法
1.3.1 简单地删除某几个数:
- 一种比较常见的方法就是 重构数组,那就是先找到需要删除的那个数的位置,然后从这个数的下一位开始,
逐个往前移动,直接覆盖前面的数据,最后输出的时候记得数组长度进行相应的减少即可。 - 如果需要多次删除的话,那就需要多次重构数组。
- 以PTA题目数组元素的删除为例:
scanf("%d", &k);//这里的k表示删除的次数;
for (i = 0; i < k; i++)
{
scanf("%d", &order);//order表示想删除的数的位置;
for (j = order - 1; j < n; j++)
{
array[j] = array[j + 1];
}
n--;
}
1.4 数组中目前学到的排序方法及其主要思路
1.4.1 选择排序法:
- 主要思路:选择排序法的主要思路是先找出一段范围内的最值(最大值和最小值都可以),然后将他们先
放在一边(习惯上统一先放左边,所以我们以此方法为例),也就是说找到最值的位置后,让最值的数的位置
和最左边的数的位置进行交换,让最左边的空间存放的是最值,然后再在除去左边的值的剩下的值的范围中一
次一次不断地重复前面的操作直到倒二个数,这是第一层循环的终点,第二层循环的终点一般都是数组长度,
但是它的初值在不断地从第二个数组元素的下标开始直到数组长度停止,最终如果排序完整个数组的话,往往可
以得到一个从小到大或者从大到小排列的数组。其它情况根据具体情况去改变循环条件去具体分析。 - 以PTA的题目选择法排序为例:
//数据表达
unsigned int n;
int a[11];//数组a;
int Index = 0;//控制数组输入的下标;
int count = 0;//计数当前刷过几遍;
int temp;//用于存储暂时的变量;
int bigIndex;//用来表示更大数的下标;
//选择法排序1;
for (count = 0; count < n - 1; count++)
{
bigIndex = count;//表示最大数的下标 并在每一轮先表示那一轮内循环的第一个数;
for (Index = count; Index < n - 1; Index++)
{
if (a[bigIndex] < a[Index + 1])//以本循环内的第一个数为起始点,不断与下一个数进行大小比较;
{
bigIndex = Index + 1;//用一个下标变量来定位最大的那个数;
}
else;
}
//将最大数交换到当前的第一个数的位置来,然后把当前第一个数的换到原本最大数的那个位置;
temp = a[count];
a[count] = a[bigIndex];
a[bigIndex] = temp;
}
//细心的读者会发现,哎呀怎么给的代码和思路中描述的不太一样,其实他们表达的本质都是一样的,之所以
会有循环条件控制的这两种不同的写法,最主要的目的还是为了去避免数组下标的溢出。
- 非常非常非常需要注意的一点就是,在数组问题当中循环上下限的设置,不仅仅要满足逻辑上效果的满足,更
重要的是,它还要保障跑的过程中,每一个作为数组下标的量或表达式值的结果都不能越界!!
所以我们再放一种写法它也能过:
//选择法排序2;
for (count = 0; count < n - 1; count++)
{
bigIndex = count;//表示最大数的下标再每一轮先表示那一轮内循环的第一个数;
for (Index = count + 1 ; Index < n; Index++)
{
if (a[bigIndex] < a[Index])//以本循环内的第一个数为起始点,不断与下一个数进行大小比较;
{
bigIndex = Index;//用一个下标变量来定位最大的那个数;
}
else;
}
//将最大数交换到当前的第一个数的位置来,然后把当前第一个数的换到原本最大数的那个位置;
temp = a[count];
a[count] = a[bigIndex];
a[bigIndex] = temp;
}
1.4.2 冒泡排序法:
- 实验思路:冒泡排序法的思路是一种临近元素两两满足条件不断交换的思路,同样设置两层循环,外层循环控制
的范围是从数组中的第一个元素开始,不断得去提取元素,直到提取到最后一个元素,而内层循环控制的是每次交换
的一个范围,它的每次循环的范围会向一个方向缩减,缩减的数量就是已经排序完成,成功冒泡的元素的个数(常
见的是往右边冒泡),然后内循环的右界不断缩减直到为零,而左界保持不变一直都是第一个元素的下标。通过这
样的过程,如果最后完全排序完成的话,也可以得到一个从小到大排序或者从大到小排序的数组,具体情形自己分
析。 - 具体的实例代码可以参考PTA的题目冒泡排序法:
//数据表达
unsigned long int N;
unsigned long int K;
int a[101];//数组a;
int Index = 0;//控制数组的下标;
int count = 0;//计数当前刷过几遍;
int temp;//用于存储暂时的变量;
//冒泡法排序;
for (count = 0; count < K ; count++)//这里表示一共做冒泡法的轮数,K的表达形式与count的初值有关!
{
for (Index = 0; Index < N - count-1; Index++)//这里面的 N - count-1 很重要!!!-1是保证数组下标不越界;
{
if (a[Index] > a[Index + 1])
{
temp = a[Index + 1]; a[Index + 1] = a[Index]; a[Index] = temp;//做交换;
//要记住交换的 传递性 写法!!
//这样写一是可以的: temp = a[Index]; a[Index] = a[Index + 1]; a[Index] = temp;
//记住一个看起来的特点那便是:首 尾 顶 真 !
}
}
}
- 这里就分析一下选择排序法和冒泡排序法的区别:
**你会发现,选择排序法的交换是放在第一层循环中,而冒泡排序法是放在第二层循环中,所以相对来说
选择排序法的代码的结构性会比冒泡排序法的更好,效率会更高。 - 更深入的理解请访问该文章:浅谈排序算法
1.5 数组做枚举用法及其案例
- 用数组来做枚举的话,一般要求数与数之间存在一定的逻辑关系,我们通过其逻辑关系来表示他们可以省力很多。
这种情况下,一般是要先将特殊的情况另外表示出来,有规律的再用数组进行枚举表示。 - 案例如下:
PTA题目 杨辉三角:
代码如下:
#include<stdio.h>
int main()
{
int n;
int i, j;
scanf("%d", &n);
int array[9][9];
for (i = 0; i < n; i++)
{
for (j = 0; j <= i; j++)
{
if (i == j || j == 0)
{
array[i][j] = 1;
}
else
{
array[i][j] = array[i - 1][j - 1] + array[i - 1][j];
}
}
}
for (i = 0; i < n; i++)
{
for (j = 0; j <= i; j++)
{
printf("%4d", array[i][j]);
}
printf("n");
}
return 0;
}
1.6 哈希数组用法及其案例
- 哈希数组的主要思想是用空间换时间,它巧妙地运用了数学中复合函数的思想,正好数组的下标和它对应的元素
也在某种程度上反映了一种一一对应的映射关系,所以它让一个数组去当另外一个数组的下标,让内数组对应的元素
去充当外数组的下标,不过要求的是,内数组对应的元素的取值范围要在外数组下标的有效范围之内,这同样也和数学
上复合函数的对应思路一致。 - 以PTA中有重复的数据I为例:
//这是过不了审的用了循环嵌套的做法:
int main()
{
//数据表达
int n, i, k;
int numbers[100000];
int numbers1[100000];
int count = 0;
//流程设计
//input
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &numbers[i]);
}
for (i = 0; i < n; i++)
{
for (k = i; k < n; k++)
{
if (numbers[i] == numbers[k])
{
count++;
}
}
}
if (count >= 2)
{
printf("YES");
}
else
{
printf("NO");
}
return 0;
}
/* 用这种方法来解决 有重复的数据I 过不了数字很大的 测试点。但是这个方法是有值得学习的地方的
那就是对数组的一种思考方式:==那就是可以通过定义两个在改变的不同变量来当作同一数组的下标使用
数组。== */
- 其实可以把数组想象成数学中的函数关系,下标就是自变量,支持 复合函数 的思想 所以也就支持数组嵌套。
//于是有了哈希数组的方法:
int main()
{
//数据表达
int n, i;
int numbers[100000];//内数组用来存放实际元素;
static int numbers1[100001];//外数组用来统计个数。
int flag = 1;
//流程设计
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &numbers[i]);
}
for (i = 0; i < n; i++)
{
numbers1[numbers[i]]++;
}
for (i = 0; i < n; i++)
{
if (numbers1[numbers[i]] >= 2)
{
flag = 0;
}
}
if (flag)
{
printf("NO");
}
else
{
printf("YES");
}
return 0;
}
- 值得注意的是使用了哈希数组之后,后期对外数组计数的统计,你所使用的下标也应该
是数组下标,这样才能够既解决计数统计的需要又不至于要遍历整个外数组,浪费时间。 - 要注意外数组的长度和内数组元素数据取值范围的一一对应,避免下标越界!
1.7 字符数组、字符串特点及编程注意事项
1.7.1 字符数组的输入:
- scanf类型的输入方法:支持中间没有空格的输入类型,因为一遇到空格或者回车就会立刻
停止输入。另外这种方法会自动补充字符数组的结束标志,不需要另外自己赋值。
//假设此刻有一个字符数组为a
scanf("%s",a);
//其中字符数组的变量名本身就代表首地址所以不需要 & ,其次不需要[]。
- while类型的输入:这种做法就像是把字符数组拆分成一个一个的字符,它是相当于在循环中
一个一个把字符给输入到字符数组当中,可以应对有空格或者回车的输入环境,但是缺点是,它
并不会自动补充字符数组的结束符号 ‘ ’ (也就是 0 );所以往往需要在循环结束时在循环外
对数组的已输入元素的后一位手动赋值来封尾,这样,字符数组的输入才算成功输入。另外,输
入循环结束的条件往往需要自己设置,这个根据题目来具体分析。
//这里假设输入一串字符并用 回车 来结束输入:
while ((str[i]=getchar()) != 'n')
{
i++;
}
str[i] = '