作者:命运之光 专栏:数据结构
实验五 数组 实验环境:Visual C++或Dev C++ 实验目的: 1、掌握C语言定义数组的方法; 2、掌握一维数组和二维数组的运算方法。 实验内容(二选一): 题一:设二维数组a[1…m,1…n]含有m*n个整数,写一个算法判断a中所有元素是否互不相同,输出相关信息(yes/no) 1.任务分析 判断二维数组中的元素是否互不相同,需要逐个比较,为了提高算法效率,应当避免重复的比较,确保每个元素同其他元素比较一次且只有一次。 2.程序构思 1) 依次遍历数组中每个元素,对于第i行的每个元素,先同本行后面的元素逐个比较,然后再同第i+1行及其后各行元素逐个比较; 2) 在比较过程中,只要找到一对相等的元素,就可断定不是互不相同,不必继续比较,返回0,否则继续比较,最后返回1,表明数组所有元素互不相同。 题二: 设任意n个整数存放于数组A[1…n]中,编写算法,将所有正数排在所有负数前面。 1.任务分析 本题属于数列的划分问题,将数组调整为左右两部分,每部分元素并不要求有序。 2.程序构思 1)可在数组首尾各设一个指针low和high,low从左至右搜索,遇到负数停止; 2)High从右至左搜索,遇到整数停止; 3)然后将low和high所指向的数据进行交换; 4)重复以上过程,直到low和high相等为止
选题一:设二维数组a[1…m,1…n]含有m*n个整数,写一个算法判断a中所有元素是否互不相同,输出相关信息(yes/no)。由于程序功能单一故直接将算法写入主函数中。
程序功能单一并未调用函数,直接写在了主函数里。 1.用#define max 100宏定义定义了max大小; 2.用a[max][max]定义了二维数组大小; 3.定义逐一遍历算法; 思路:挨个遍历,如果出现用cout来记录出现次数,我设计cout若是大于1则说明出现不止一次输出NO否则就是YES。
1.定义全局变量
#define max 100
int a[max][max];
int m, n;
int i, j;
int cout = 0;
2.主程序 在主程序中直接通过二重循环的暴力算法来直接查找二维数组中是否存在重复数。
简单分析:两个for循环进行二维数组挨个遍历搜索出现两次的值用cout来记录出现次数,步骤简单,主要就是二维数组的输入,并查找。 总结经验:一维数组我们用一个for循环就可以实现,二维数组相比于一维数组多了一次for循环的调用,遍历查找时也同样用两个for循环挨个遍历即可。 体会:这个二维数组的调用遍历查找对算法的要求相比与一维数组有了许多提高,再设计算法时要注意时间复杂度的问题,由于实验并未给出数据故我就直接用暴力遍历解决该问题。
输入 2 2 1 2 3 4 输出 YES
输入 3 3 1 1 2 2 3 3 4 4 5 输出 NO
#include<stdio.h>
#define max 100
int a[max][max];
int m, n;
int i, j;
int cout = 0;
int main()
{
printf("输入m,n的值定义二维数组大小:");
scanf_s("%d %d", &m, &n);
printf("输入数组m*n:");
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
scanf_s("%d", &a[i][j]);
}
}
int p, q;
p = m - 1;
q = n - 1;
while (p >= 0 && q >= 0)
{
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (a[p][q] == a[i][j])
{
cout++;
if (cout > 1)
{
printf("NO\n");
return 0;
}
}
}
}
cout = 0;
if (q >= 0)
{
if (q != 0)
{
q--;
}
else
{
p--;
}
}
}
printf("YES\n");
return 0;
}
适用于: 大一数据结构实验课实验报告——数组的练习(C语言版)