用数组解决问题(一)
2018-06-18 04:09:27来源:未知 阅读 ()
由于数组在编程中极为常见,并且数组技巧在非数组场合下也常常被使用,因此数组可以作为用数据结构解决问题的重要练兵场所。
一、基础知识概述
1,存储
这是最基本的操作。数组是一组变量的集合,我们可以对其中的每个变量进行赋值。
tenIntegerArray[0] = 5; //把整数5赋值给前面所声明的数组的第1个元素
int tenIntegerArray[10] = {1,2,3,6,12,-57,30987,0,-287,9}; //给数组中的每个元素赋一个特定的值
int tenIntegerArray[10]; for(int i = 0;i < 10;i++) tenIntegerArray[i] = -1; //把一个数组的10个元素都初始化为-1
2,复制
复制一个数组,只需要使用一个循环和一条赋值语句,就像初始化数值一样。
int tenIntegerArray[10] = {1,2,3,6,12,-57,30987,0,-287,9}; int secondArray[10]; for(int i = 0;i < 10;i++) secondArray[i] = tenIntegerArray[i];
3,提取和搜索
除了能够把值放入数组中之外,我们还需要能够把它们从数组中提取出来。
int num = tenIntegerArray[0];
但通常情况下并没有这么简单。我们常常不知道所需要的位置,必须通过对数组进行搜索才能找到一个特定值的位置。如果数组中的元素并没有特定的顺序,最好执行线性搜索,即从数组的一端开始查看每个元素,直到找到所需要的值。
const int ARRAY_SIZE = 10; //数组长度 int intArray[ARRAY_SIZE] = {4,5,9,12,-4,0,-57,30987,-287,1}; //数组本身 int targeValue = 12; //在数组中所找到的值 int targePos = 0; //所找到的值的位置 while((intArray[targetPos] != targeValue)&&(targePos < ARRAY_SIZE)) //使用ARRAY_SIZE常量限制这个数组的迭代次数 targePos++;
有时候,我们所搜索的并不是一个固定的值,而是一个与数组中的其他值存在关系的值。
例如,我们可能想要在数组中搜索最大值。我把完成这个任务的机制称为“山丘之王”,用一个变量表示数组到目前为止所找到的最大值。用一个循环遍历数组中的所有元素,每当遇到一个比当前最大值更大的值时,就把以前的国王从山丘上踢下去并取而代之:
const int ARRAY_SIZE = 10; //数组长度 int intArray[ARRAY_SIZE] = {4,5,9,12,-4,0,-57,30987,-287,1}; //数组本身 int highestValue = intArray[0]; //在声明之时,它被赋值为数组中的第一个元素的值 for(int i = 1;i < ARRAY_SIZE;i++){ //从数组的第二个元素开始循环 if(intArray[i] > highestValue) //把当前位置的值与highestValue进行比较 highestValue = intArray[i]; //适时替换highestValue的值
4,排序
按特定的顺序排列数据。
用qsort进行快速方便的排序
为了使用qsort,必须编写一个比较函数。这个函数被qsort函数调用,用于比较数组中的两个元素,判断哪个应该出现在排序序列中的更前面。这个函数应该返回一个整数,根据第一个元素是大于、小于或等于第二个元素,这个整数的值分别为正数、负数或零。具体返回的值无关紧要,重要的是它是大于、小于还是等于零。现在,我们通过采用qsort对一个包含10个整数的数组进行排序的简单例子来说明这种排序方法。先写出比较函数:
int compareFunc(const void * voidA,const void * voidB){ int * intA = (int *)(voidA); int * intA = (int *)(voidB); return *intA - *intB; }
有了比较函数之后,下面是qsort的一个示例用法:
const int ARRAY_SIZE = 10; int intArray[ARRAY_SIZE] = {87,28,100,78,84,98,75,70,81,68}; qsort(intArray,ARRAY_SIZE,sizeof(int),compareFunc);
但在有些情况下,需要自己编写排序代码。
我建议是使用一种插入排序算法。它的工作方式与人们在打桥牌时所使用的理牌方式相似:一次抓起一张牌,把它插入到手里这把牌中的适当位置以维持整体的顺序,并移动其余的牌以留出空间。
以下是整数数组的插入排序算法的基本实现:
int start = 0; //数组中的第一个元素 int end = ARRAY_SIZE - 1; //数组中的最后一个元素 for(int i = start + 1;i <= end;i++){ //外层循环选择下一张需要插入的牌,它被插入到当前按升序排列的一把牌中 for(int j = i;j > start&&intArray[j-1] > intArray[j];j--){ //不断地把当前值与它的前一个值进行交换,直到它到达正确的位置 int temp = intArray[j-1]; //把当前值交换到数组中的前一个位置 intArray[j-1] = intArray[j]; intArray[j] = temp; } }
5,计算统计数据
与提取操作相似。区别在于它是根据数组中的所有值进行计算所产生的统计数据。例如计算一组学生成绩的平均值:
const int ARRAY_SIZE = 10; int gradeArray[ARRAY_SIZE] = {87,76,100,97,64,83,88,92,74,95}; double sum = 0; for(int i = 0;i < ARRAY_SIZE;i++) sum += gradeArray[i]; double arerage = sum / ARRAY_SIZE;
另一个简单例子就是数据验证。假设有一个称为vendorPayments的包含double值的数组,表示向销售商的支付情况。
二、用数组解决问题
问题:寻找众数
在统计学中,一组值的众数就是最常出现的值。编写代码,处理一个包含了调查数据的数组,确定这个数据集的众数。在这个数组中,接受调查者用1~10范围内的一个数表示一个问题的答案。对于我们而言,如果存在多个众数,可以任选其一。
1,我们首先观察这个问题的一个示例数组以及它的长度常量:
const int ARRAY_SIZE = 12; int surveyData[ARRAY_SIZE] = {4,7,3,8,9,7,3,9,9,3,3,10};
简化后:
int surveyData[ARRAY_SIZE] = {4,7,7,9,9,9,8,3,3,3,3,10};
现在,2个7出现在一起,3个9也是如此,所有的3也都几张在一起。当数据按照这种方式排列之后,我们就能够线性地处理这个数组并找到众数了。
2,我们先编写一些伪码:(所谓伪码,就是与程序代码相似的语句,它可以提醒我们在编写每条语句时应该要完成什么任务)
int mostFrequent = ?; int highestFrequency = ?; int currentFrequency = 0; for(int i = 0;i < ARRAY_SIZE;i++){ //处理数组 currentFrequency++; //对当前值的出现次数进行计数的变量的值加1 if(surveyData[i] is last occurrence of a value){ //检查,观察是否到达了一个特定值的最后一次出现 if(currentFrequency > highestFrequency){ //如果是,这个值就成为新的最常见的值 highestFrequency = currentFrequency; mostFrequent = surveyData[i]; } currentFrequency = 0; //由于下一个被读取的值将是新值的第一次出现,因此我们把计数器重置为0 } }
,3,我们回到前面暂时跳过的if语句的逻辑。
怎么才能知道一个值在数组中最后一次出现呢?
由于数组中的值已经分组,因此当数组中的下一个值与当前值不同时(surveyData[i] 不等于 surveyData[i+1]),我们就知道现在是当前值的最后一次出现。
4,现在可以考虑变量初始值的问题。
现在,“当前的最常见”值用2个变量表示,mostFrequent表示值本身,highestFrequency表示它的出现次数。如果能把mostFrequent初始化为数组中所出现的第一个值并把highestFrequency初始化为这个值在数组中的出现次数当然是最好不过了,但在进入循环并开始计数之前,还没有办法确定第一个值的出现次数。此时,我们可能会想到,不管第一个值的出现次数是多少,它总是大于零。因此,我们把highestFrequency变量值初始化为零。当我们到达第一个值的最后一次出现时,这段代码就会把highestFrequency变量的值替换为第一个值的出现次数。完整代码如下:
int mostFrequent; int highestFrequency = 0; int currentFrequency = 0; for(int i = 0;i < ARRAY_SIZE;i++){ currentFrequency++; //if(surveyData[i] is last occurrence of a value) if(i == ARRAY_SIZE - 1 || surveyData[i] != surveyData[i+1]){ if(currentFrequency > highestFrequency){ highestFrequency = currentFrequency; mostFrequent = surveyData[i]; } currentFrequency = 0; } }
对数组进行排序的问题,我们只要在代码开始时调用qsort就可以了:
qosrt(surveyData,ARRAY_SIZE,sizeof(int),comareFunc);
5,重构
是不是存在这样一个数组,我们可以对它应用“寻找最大值”方法,从而得到调查数据的众数?答案是肯定的。
我们所需要的数组是surveyData数组的柱状图。柱状图就是显示在底层数据中的不同数据的出现频率的图形。我们所需要的数组就是表示这种柱状图的数据。换句话说,我们将在一个长度为10个元素的数组中存储1到10的每个值在surveyData数组中的出现频率。以下是创建柱状图的代码:
const int MAX_RESPONSE = 10; int histogram[MAX _RESPONSE]; //保存柱状图数据的数组 for(int i = 0;i < MAX_RESPONSE;i++){ //把数组的每个值初始化为0 histogram[i] = 0; } for(int i = 0;i < ARRAY_SIZE;i++){ //对surveyData数组中的每个值的出现次数进行计数 histogram[surveyData[i] - 1]++; }
(注意:柱状图代码是独立编写的,这样就可以对它进行单独的测试。)
对上面的代码进行了测试之后,现在就可以搜索histogram数组的最大值了:
int mostFrequent = 0; //初始化 for(int i = 1;i < MAX_RESPONSE;i++){ if(histogram[i] > histogram[mostFrequent]) mostFrequent = i; } mostFrequent++;
注意:mostFrequent将是histogram数组中最大值的位置,而不是最大值本身。 因此,我们把它初始化为0而不是location[0]的值;在if语句中,我们把它与histogram[mostFrequent]进行比较,而不是与mostFrequent本身进行比较。在找到一个更大值时,我们把mostFrequent赋值为1而不是histogram[i]。最后,我们把mostFrequent的值增加1,这正好与前一个循环中减去1得到正确的数组位置的操作相反。例如,如果把mostFrequent告诉我们最大的数组位置是5,表示调查数据中最常出现的项是6。
总结
柱状图解决方案的复杂度随着SurveyData数组的元素数量增加而线性增长,这也是我们能够期待的最好结果了。因此,相比原来的排序方法,它是更好的解决方案。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:C语言基础
- 纯虚函数与基类指针数组的运用 代码参考 2020-04-30
- STL之deque 2020-04-29
- C++基础 学习笔记六:复合类型之数组 2020-04-25
- 寻找两个有序数组的中位数 2020-04-09
- STL之vector 2020-04-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash