&&/&&&&/&&
一维数组只有一个下标，称为一维数组，其数组元素也称为单下标变量。在实际问题中有很多量是二维的或多维的，因此C语言允许构造多维数组。多维数组元素有多个下标，以标识它在数组中的位置，所以也称为多下标变量。本节只介绍二维数组，多维数组可由二维数组类推而得到。
二维数组的定义
二维数组定义的一般形式是：
& & 类型说明符 数组名[常量表达式1][常量表达式2]
其中常量表达式1表示第一维下标的长度，常量表达式2 表示第二维下标的长度。例如：
int a[3][4];
说明了一个三行四列的数组，数组名为a，其下标变量的类型为整型。该数组的下标变量共有3&4个，即：
& & a[0][0], a[0][1], a[0][2], a[0][3]
&&& a[1][0], a[1][1], a[1][2], a[1][3]
&&& a[2][0], a[2][1], a[2][2], a[2][3]
二维数组在概念上是二维的，即是说其下标在两个方向上变化，下标变量在数组中的位置也处于一个平面之中，而不是象一维数组只是一个向量。但是，实际的硬件存储器却是连续编址的，也就是说存储器单元是按一维线性排列的。如何在一维存储器中存放二维数组，可有两种方式：一种是按行排列， 即放完一行之后顺次放入第二行。另一种是按列排列， 即放完一列之后再顺次放入第二列。
在C语言中，二维数组是按行排列的。即，先存放a[0]行，再存放a[1]行，最后存放a[2]行。每行中有四个元素也是依次存放。由于数组a说明为int类型，该类型占两个字节的内存空间，所以每个元素均占有两个字节。
二维数组元素的引用
二维数组的元素也称为双下标变量，其表示的形式为：
& & 数组名[下标][下标]
其中下标应为整型常量或整型表达式。例如：
& & a[3][4]
表示a数组三行四列的元素。
下标变量和数组说明在形式中有些相似，但这两者具有完全不同的含义。数组说明的方括号中给出的是某一维的长度，即可取下标的最大值；而数组元素中的下标是该元素在数组中的位置标识。前者只能是常量，后者可以是常量，变量或表达式。
【例7-6】一个学习小组有5个人，每个人有三门课的考试成绩。求全组分科的平均成绩和各科总平均成绩。
可设一个二维数组a[5][3]存放五个人三门课的成绩。再设一个一维数组v[3]存放所求得各分科平均成绩，设变量average 为全组各科总平均成绩。编程如下：
#include &stdio.h&
int main(void){
int i,j,s=0,average,v[3],a[5][3];
printf(&input score\n&);
for(i=0;i&3;i++){
for(j=0;j&5;j++){
scanf(&%d&,&a[j][i]);
s=s+a[j][i];
average =(v[0]+v[1]+v[2])/3;
printf(&math:%d\nc languag:%d\ndbase:%d\n&,v[0],v[1],v[2]);
printf(&total:%d\n&, average );
程序中首先用了一个双重循环。在内循环中依次读入某一门课程的各个学生的成绩，并把这些成绩累加起来，退出内循环后再把该累加成绩除以5送入v[i]之中，这就是该门课程的平均成绩。外循环共循环三次，分别求出三门课各自的平均成绩并存放在v数组之中。退出外循环之后，把v[0]、v[1]、v[2]相加除以3即得到各科总平均成绩。最后按题意输出各个成绩。
二维数组的初始化
二维数组初始化也是在类型说明时给各下标变量赋以初值。二维数组可按行分段赋值，也可按行连续赋值。
例如对数组a[5][3]：
按行分段赋值可写为：
int a[5][3]={ {80,75,92}, {61,65,71}, {59,63,70}, {85,87,90}, {76,77,85} };
按行连续赋值可写为：
int a[5][3]={ 80,75,92,61,65,71,59,63,70,85,87,90,76,77,85};
这两种赋初值的结果是完全相同的。
【例7-7】求各科平局分和总成绩平均分。
#include &stdio.h&
int main(void){
int i,j,s=0, average,v[3];
int a[5][3]={{80,75,92},{61,65,71},{59,63,70},{85,87,90},{76,77,85}};
for(i=0;i&3;i++){
for(j=0;j&5;j++)
s=s+a[j][i];
average=(v[0]+v[1]+v[2])/3;
printf(&math:%d\nc languag:%d\ndFoxpro:%d\n&,v[0],v[1],v[2]);
printf(&total:%d\n&, average);
对于二维数组初始化赋值还有以下说明：
1) 可以只对部分元素赋初值，未赋初值的元素自动取0值。例如：
int a[3][3]={{1},{2},{3}};
是对每一行的第一列元素赋值，未赋值的元素取0值。 赋值后各元素的值为：
& & 1 &0 &0
& & 2 &0 &0
& & 3 &0 &0
int a [3][3]={{0,1},{0,0,2},{3}};
赋值后的元素值为：
& & 0 &1 &0
& & 0 &0 &2
& & 3 &0 &0
2) 如对全部元素赋初值，则第一维的长度可以不给出。例如：
int a[3][3]={1,2,3,4,5,6,7,8,9};
可以写为：
int a[][3]={1,2,3,4,5,6,7,8,9};
3) 数组是一种构造类型的数据。二维数组可以看作是由一维数组的嵌套而构成的。设一维数组的每个元素都又是一个数组，就组成了二维数组。当然，前提是各元素类型必须相同。根据这样的分析，一个二维数组也可以分解为多个一维数组。C语言允许这种分解。
如二维数组a[3][4]，可分解为三个一维数组，其数组名分别为：
对这三个一维数组不需另作说明即可使用。这三个一维数组都有4个元素，例如：一维数组a[0]的元素为a[0][0],a[0][1],a[0][2],a[0][3]。必须强调的是，a[0],a[1],a[2]不能当作下标变量使用，它们是数组名，不是一个单纯的下标变量。
推荐文章 TOP10c语言怎样能连续输入多个一维数组
我用C语言编了个计算程序,要输入三个数组,语句是这样写的:           printf(&k[%d]=&,n);           scanf(&%f&,&k[n]);           printf(&s[%d]=&,n);           scanf(&%f&,&s[n]);           printf(&d[%d]=&,n);           scanf(&%f&,&d[n]);但输入第一组数组后,光标就指向最后一个数组,且光标不能移动,所以第二个数组就没法输入,这是为什么?怎样解决?请各位大侠高手赐教!
09-12-17 &匿名提问
您好把具有相同数据类型的若干变量按有序的形式组织起来， 以便于程序处理，这些数据元素的集合就是数组，按照数组 元素的类型不同，可分为：数值数组、字符数组、指针数组 结构数组等各种类别。 数组说明的一般形式为： 类型说明符 数组名[常量表达式]，......; 其中类型说明符可以是任一种基本数据类型或构造数据类型 数组名是定义的数组标识符。常量表达式表示数据元素的个 数，也就是数组的长度。 对数组类型的说明应注意： 1）数组的类型实际上是数组元素的取值类型。 2）数组名的书写应符合标识符的书写规范。 3）数组名不能与其他变量名相同。 4）常量表达式表示数组元素的个数，但是其下标从0开始计算 5）不能在方括号中用变量来表示元素的个数，但是可以用符号 常数或常量表达式。 6）允许在同一个类型说明中，说明多个数组和多个变量。 数组元素的表示方法 一般比较简单就是数组名[下标]来引用，先定义后用，如果 是小数的话，直接自动取整。 数组赋值分为：初始化赋值和动态赋值 初始化赋值一般形式为： static 类型说明符 数组名[常量表达式]={值，值......}; static表示静态存储类型，c语言规定只有静态存储数组和外部数组 才可做初始化赋值。 c语言对数组的初始化赋值还有几个规定： 1）可以只给部分元素赋值。 2）只能给元素逐个赋值，不能给数组整体赋值。 3）如不给可初始化的数组赋初值，在在数组说明中，可以不给出数组 元素的个数。 下面看一下多维数组 主要看一下二维数组，其他的就可以用二维数组类推得到 二维数组的类型说明的一般形式是： 类型说明符 数组名[常量表达式1][常量表达式2]...； 在c语言中二维数组是按行排列的 二维数组的表示方法： 数组名[下标][下标] 二维数组的初始化 二维数组初始化也是在类型说明时给各下标变量赋以初值。 二维数组可 按行分段赋值，也可按行连续赋值。 二维数组的初始化还应该注意： 1）可以只对部分元素赋初值，未赋初值的元素自动取为0。 2）如对全部元素赋初值，则第一维的长度可以不给出。 字符数组： 用来存放字符变量的数组称为字符数组。 C语言允许用字符串的方式对数组作初始化赋值。例如： static char c[]={'c', ' ','p','r','o','g','r','a','m'}; 可写为： static char c[]={&C program&}; 或去掉{}写为： sratic char c[]=&C program&; 用字符串方式赋值比用字符逐个赋值要多占一个字节， 用于存放字符串结 束标志'\0'。上面的数组c在内存中的实际存放情况为： C program\0`\0'是 由C编译系统自动加上的。由于采用了`\0'标志，所以在用字符串赋初值时一 般无须指定数组的长度， 而由系统自行处理。在采用字符串方式后，字符数 组的输入输出将变得简单方便。 除了上述用字符串赋初值的办法外，还可用 printf函数和scanf函数一次性输出输入一个字符数组中的字符串， 而不必 使用循环语句逐个地输入输出每个字符。 void main() { static char c[]=&BASIC\ndBASE&; printf(&%s\n&,c); } printf(&%s\n&,c); 注意在本例的printf函数中，使用的格式字符串为&%s&， 表示输出的是一 个字符串。而在输出表列中给出数组名则可。 不能写为： printf(&%s&,c[]);
请登录后再发表评论!
用unsigned char code table[]={0x06,0x5b,0x4f,0x66,0x6d,0x7d,0x07,0x7f,0x6f,0xc0};这个句式
请登录后再发表评论!c语言中数组名a和&a详细介绍
字体：[ ] 类型：转载 时间：
其实这两个东西挺难理解的，应该也没有那么重要，了解一下好了，主要还是要多多理解数组指针的运算
最近又把学习c语言提上日程上来了~~~先把我打算看的书都写下来吧，&C语言深度剖析&，&c和指针&系类，&c语言陷阱和缺陷&
先说说a和&a的区别(有三点，三个方向)：1.是a和&a的本质，都是什么类型的。2.从2维数组的角度看。3.从指针运算的角度看。
声明：虽然数组名不是指针，但是用的很像指针，我们暂且把它叫做一个指针吧。
第一个问题：int a[10];& a ，&a和&a[0] 都是分别是什么？先说明a ，&a和&a[0]三个值是的相等哈。
a叫做数组名，是数组首元素的地址，也就是&a[0]的值。像是一个指针类型，是一个int型的指针类型，int *，先理解成指针吧。
&a这才是一个真正的指针，是一个数组指针。是数组的地址。
切记：&a不是指向指针的指针，因为&a和a的值相等，但是*&a和*a的值不相等。*&a和a的值一样，说明*&a仅仅是对这个数组指针进行了取值，取得的是数组的值，即数组首元素的地址，而不是对&a这个地址进行了取值。这个应该是c语言中针对数组指针运算的规定。&这里的数组指针&a取值之后，变成了a，是a，不是*a，变成了这个数组的数组名，或者说是数组首元素的地址。
我做了如下实验： 代码如下:#include&stdio.h&&int main()&{&&&&&&&& int a[5]={1,2,3,4,5};&&&&&&&& printf("a=%x\n",a);&&&&&&&& printf("&a=%x\n",&a);&&&&&&&& printf("*(int*)&a=%x\n",(*((int *)(&a))));&&&&&&&& printf("*&a=%x\n",(*(*(&a))));&&&&&&&& printf("&a[0]=%x\n",&a[0]);&&&&&&&& printf("*&a[0]=%x\n",*(&a[0]));&&&&&&&& return 0;&} 代码如下:printf("*(int*)&a=%x\n",(*((int *)(&a))));这句没有像常规的一样对&a进行取值，而是强制类型转换了一下，可见这个不是一个指向指针的指针。 第二个问题：二维数组中的利用指针来遍历的方式，也不是一个指向指针的指针（2级指针） ，这句printf("%d\n", *(*(a+i) + j));&&*(a+i)也就是将数组指针取值获得数组的首元素地址，常常的误区就是数组指针的取值运算和普通的指针取值运算不一样。数组指针取值运算类似一个强制类型转换的过程。&&&&
注意：二维数组的数组名a，是第一个一维数组的数组指针，*a就是第一个一维数组的数组名。也可以直接用tpye *强制类型转换。 代码如下:&#include &stdio.h&&int main(int argc, char* argv[], char* env[])&{&&& int a[3][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}};&&& int i = 0;&&& int j = 0;&&& for(i=0; i&3; i++)&&& {&&&&&&&& for(j=0; j&3; j++)&&&&&&&& {&&&&&&&&&& //& printf("%d\n", *((int *)(a+i) + j));&&&&&&&&&&&&&&&&& printf("%d\n", *(*(a+i) + j));&&&&&&&& }&&&& }其实这两个东西挺难理解的，应该也没有那么重要，了解一下好了，主要还是要多多理解数组指针的运算。因为我看了好多文章都是通过对&a和a的运算角度来说明两者不是一个东西的。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具C引用数组名时的含义与数组元素访问 - 博客频道 - CSDN.NET
《西决》 —— 克里斯·保罗 [笑]
分类：-[小西南]-
数组名在纯被引用时它的含义是指向数组第一个元素的指针常量。
1 一维数组
1.1 表达式中的数组名
当定义一个一维数组后，元素以地址连续的形式存储在内存中。当在程序的表达式中引用数组名时它被当成指向数组第一个元素的指针常量。
Figure1：一维数组名在被引用时的含义
TYPE 表示C语言中的一种数据类型。当定义一个维数为7每个元素的类型为TYPE的数组a之后，系统会为其分配一段内存，假设首地址为0x。当数组名a用在表达式中时，a就是指向数组a中的第一个元素a[0]，它是一个指向类型为TYPE的指针常量即0x。a + 1表示下一个元素的地址，a + 1的具体值得根据TYPE类型在内存中所在大小来决定。当TYPE为char 类型时，a就是指向类型为char的a[0]元素的指针常量，a + 1的值就是0x。当TYPE为int时，a就是一个指向类型为int的a[0]元素的指针常量，a+1的值就有可能（不同系统int所占字节有可能不同）为0x。
不同类型元素的有效地址（大地址或者小地址）细节不需要用户关心。
1.2一维数组名的特殊含义
在程序中定义char &a[7];
(1) sizeof(a)
printf(&sizeof(a):%d\n&, sizeof(a)); 语句输出的值为7。按理说，数组名作为一个指针常量，它的值应该为4字节（32位系统之上常见的指针变量所占内存大小）。说明在这样的方式下引用数组名时数组名不再是指针常量的含义，sizeof(a)将返回整个数组a的长度，此时数组名a方显出几分数组的气息。
printf(&sizeof(&a):%d\n&, sizeof(&a));&& 在Debian& GNU/Linux(关于sizeof(&a)的值还得看具体的编译器)下的输出来的值为4，这倒是挺符合分析结果。&a表示取a（不管a的类型如何）的指针，所以它占4字节内存。&a是一个指向类型为TYPE的整个数组的指针常量，而非指向一个指针的指针。
2 二维数组
2.1 表达式中的二维数组名
二维数组跟一维数组一样，其数组名都是指向数组的第一个元素的指针常量。跟一维数组不同的是，二维数组的第一维的元素其实是另一个数组。在C语言中，多维数组可以被看作一维数组，如char m[2][7];创建了数组m，它可以被看作是一个一维数组，一共有两个元素，只是每个元素是包含7个char型元素的数组。以m数组图示笔记，
Figure2：二维数组名被引用时的含义
二维数组m的第一维为二维数组的元素，每个元素是包含7个char类型元素的数组。数组名m为指向二维数组第一个元素的指针常量，假设为此二维数组分配内存的首地址为0x，m就代表0x常量。是一个指向一个类型为char维数为7的一维数组的指针常量。m + 1的值视m的类型，是一个指向一个类型为char维数为7的一维数组的指针常量，则m + 1就是下一个类型为char维数为7的一维数组的地址。
2.2 二维数组名的特殊含义
(1) sizeof(m)
printf(&sizeof(m):%d\n&, sizeof(m));的值为14，虽然m本身为指向m[0]的指针常量，但sizeof(m)返回整个二维数组m的在内存中所占的字节数。
在Debian GNU/Linux下，printf(&sizeof(&m): %d\n&,sizeof(&m));&&&&& 输出的值为4，因为此时的编译器将&m视为一个指针。不过此值还得看具体的编译器。&m是指向整个二维数组m的指针常量。不过这些结论都最好在对应的编译器下测试一下。
3 访问数组元素
在程序中除了要用到数组名之外，很多时候也需要访问元素。数组元素的访问有间接访问和直接访问两种方式。
3.1 间接访问
间接访问数组元素的方式就是通过数组名加下标的方式。如a[2]访问数组a的下标为2即数组中的第三的一个元素。m[1][2]表示访问第二个元素（数组）的第三个元素。
3.2 直接访问
所有的间接访问形式都会被编译器转换为直接访问的方式。直接的访问形式都是通过地址访问的。
(1) 一维数组
如间接访问数组元素a[2]的直接访问方式为*(a +2)。
(2) 二维数组
理解二维数组的直接访问形式需要理解针对于二维数组来说元素的含义，二维数组中只具有第一维下标的元素是二维数组的一个元素。m[1][2]直接访问形式为*( *(m + 1) + 2)，m是二维数组m第一个元素的指针常量，m + 1是二维数组m第二个元素的指针常量。此时m + 1指向类型为char、元素个数为7的一维数组，相当于&a。*(m + 1)表示取得这个一维数组中第一个元素的地址，( *(m + 1) + 2)表示在一维数组首元素地址的基础之上偏移两个元素的地址，得到第三个元素的地址，从而*(
*(m + 1) + 2)取得了对应位置上的数组元素。
直接和间接访问的区别不仅在于形式，有时候数组元素的直接访问形式的程序效率会更高。在程序花大部分时间运行在访问数组元素代码时，这样的优化就会显现效果。
SMBox Note OVER.
排名：第592名
（2）（416）
--------老师--------
--------室友--------C语言关于数组的常见操作汇总
C语言关于数组的常见操作汇总
数组是最基本的数据结构，关于数组的操作是程序员最经常用到的。这里将一些常用的操作写成函数。
给定一个含有n个元素的整型数组a，求a中所有元素的和。可能您会觉得很简单，是的，的确简单，但是为什么还要说呢，原因有二，第一，这道题要求用递归法，只用一行代码。第二，这是我人生中第一次面试时候遇到的题，意义特殊。
简单说一下，两种情况：
如果数组元素个数为0，那么和为0。
如果数组元素个数为n，那么先求出前n - 1个元素之和，再加上a[n - 1]即可。 // 数组求和
int sum(int *a, int n)
return n == 0 ? 0 : sum(a, n - 1) + a[n - 1];
求数组的最大值和最小值
给定一个含有n个元素的整型数组a，找出其中的最大值和最小值。
常规的做法是遍历一次，分别求出最大值和最小值，但我这里要说的是分治法(Divide and
couquer)，将数组分成左右两部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后综合起来求总体的最大值及最小值。这是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素。// 求数组的最大值和最小值，返回值在maxValue和minValue
void MaxandMin(int *a, int l, int r, int& maxValue, int& minValue)
if(l == r)
// l与r之间只有一个元素
maxValue = a[l] ;
minValue = a[l] ;
if(l + 1 == r) // l与r之间只有两个元素
if(a[l] &= a[r])
maxValue = a[l] ;
minValue = a[r] ;
maxValue = a[r] ;
minValue = a[l] ;
int m = (l + r) / 2 ; // 求中点
// 左半部份最大值
// 左半部份最小值
MaxandMin(a, l, m, lmax, lmin) ;
// 递归计算左半部份
// 右半部份最大值
// 右半部份最小值
MaxandMin(a, m + 1, r, rmax, rmin) ;
// 递归计算右半部份
maxValue = max(lmax, rmax) ; // 总的最大值
minValue = min(lmin, rmin) ; // 总的最小值
求数组的最大值和次大值
给定一个含有n个元素的整型数组，求其最大值和次大值。
思想和上一题类似，同样是用分治法，不多说了，直接看代码：// 求数组的最大值和次大值，返回值在max和second中
void MaxandMin(int *a, int left, int right, int &max, int &second)
if(left == right)
max = a[left] ;
second = a[left] ;
else if(left + 1 == right)
max = a[left] & a[right] ? a[left] : a[right] ;
second = a[left] & a[right] ? a[left] : a[right] ;
int mid = left + (right - left) / 2 ;
MaxandMin(a, left, mid, leftmax, leftmin) ;
MaxandMin(a, mid + 1, right, rightmax, rightmin) ;
max = leftmax & rightmax ? leftmax :
second = leftmax & rightmax ? leftmax :
求数组中出现次数超过一半的元素
给定一个n个整型元素的数组a，其中有一个元素出现次数超过n / 2，求这个元素。据说是百度的一道面试题。
设置一个当前值和当前值的计数器，初始化当前值为数组首元素，计数器值为1，然后从第二个元素开始遍历整个数组，对于每个被遍历到的值a[i]。
如果a[i]==currentValue，则计数器值加1。
如果a[i] != currentValue， 则计数器值减1，如果计数器值小于0，则更新当前值为a[i]，并将计数器值重置为1。 // 找出数组中出现次数超过一半的元素
int Find(int* a, int n)
int curValue = a[0] ;
int count = 1 ;
for (int i = 1; i & ++i)
if (a[i] == curValue)
if (count & 0)
curValue = a[i] ;
count = 1 ;
return curV
另一个方法是先对数组排序，然后取中间元素即可，因为如果某个元素的个数超过一半，那么数组排序后该元素必定占据数组的中间位置。
求数组中元素的最短距离
给定一个含有n个元素的整型数组，找出数组中的两个元素x和y使得abs(x - y)值最小。
先对数组排序，然后遍历一次即可：int compare(const void* a, const void* b)
return *(int*)a - *(int*)
void MinimumDistance(int* a, int n)
qsort(a, n, sizeof(int), compare) ;
// Index of number 1
// Index of number 2
int minDistance = numeric_limits&int&::max() ;
for (int k = 0; k & n - 1; ++k)
if (a[k + 1] - a[k] & minDistance)
minDistance = a[k + 1] - a[k] ;
i = a[k] ;
j = a[k + 1] ;
cout && "Minimum distance is: " && minDistance &&
cout && "i = " && i && " j = " && j &&
求两个有序数组的共同元素
给定两个含有n个元素的有序（非降序）整型数组a和b，求出其共同元素，比如：a = 0, 1, 2, 3, 4和b = 1, 3, 5, 7, 9，输出
充分利用数组有序的性质，用两个指针i和j分别指向a和b，比较a[i]和b[j]，根据比较结果移动指针，则有如下三种情况：
a[i] & b[j]，则i增加1，继续比较
a[i] == b[j]，则i和j皆加1，继续比较
a[i] & b[j]，则j加1，继续比较
重复以上过程直到i或j到达数组末尾。// 找出两个数组的共同元素
void FindCommon(int* a, int* b, int n)
int i = 0;
int j = 0 ;
while (i & n && j & n)
if (a[i] & b[j])
else if(a[i] == b[j])
cout && a[i] &&
else// a[i] & b[j]
这到题还有其他的解法，比如对于a中任意一个元素，在b中对其进行Binary Search，因为a中有n个元素，而在b中进行Binary
Search需要logn。所以找出全部相同元素的时间复杂度是O(nlogn)。
另外，上面的方法，只要b有序即可，a是否有序无所谓，因为我们只是在b中做Binary
Search。如果a也有序的话，那么再用上面的方法就有点慢了，因为如果a中某个元素在b中的位置是k的话，那么a中下一个元素在b中的位置一定位于k的右侧，所以本次的搜索空间可以根据上次的搜索结果缩小，而不是仍然在整个b中搜索。也即如果a和b都有序的话，代码可以做如下修改，记录上次搜索时b中元素的位置，作为下一次搜索的起始点。
求三个数组的共同元素
给定三个含有n个元素的整型数组a,b和c，求他们最小的共同元素。
如果三个数组都有序，那么可以设置三个指针指向三个数组的头部，然后根据这三个指针所指的值进行比较来移动指针，直道找到共同元素。// 三个数组的共同元素-只找最小的
void FindCommonElements(int a[], int b[], int c[], int x, int y, int z)
for(int i = 0, j = 0, k = 0; i & x && j & y && k &)
if(a[i] & b[j])
else // a[i] &= b[j]
if(b[j] & c[k])
else // b[j] &= c[k]
if(c[k] & a[i])
else // c[k] &= a[i]
cout && c[k] &&
cout && "Not found!" &&
如果三个数组都无序，可以先对a, b进行排序，然后对c中任意一个元素都在b和c中做二分搜索。// Find the unique common element in 3 arrays
// O(NlogN)
int UniqueCommonItem(int *a, int *b, int *c, int n)
// sort array a
qsort(a, n, sizeof(int), compare) ; // NlogN
// sort array b
qsort(b, n, sizeof(int), compare) ; // NlogN
// for each element in array c, do a binary search in a and b
// This is up to a complexity of N*2*logN
for (int i = 0; i & i++)
if(BinarySearch(a, n, c[i]) && BinarySearch(b, n, c[i]))
return c[i] ;
return - 1 ; // not found
也可以对a进行排序，然后对于b和c中任意一个元素都在a中进行二分搜索。// Find the unique common element in 3 arrays
// O(NlogN)
int UniqueCommonItem1(int *a, int *b, int *c, int n)
// sort array a
qsort(a, n, sizeof(int), compare) ; // NlogN
// Space for time
bool *bb = new bool[n] ;
memset(bb, 0, n) ;
bool *bc = new bool[n] ;
memset(bb, 0, n) ;
// for each element in b, do a BS in a and mark all the common element
for (int i = 0; i & i++)
if(BinarySearch(a, n, b[i]))
// for each element in c, do a BS only if b[i] is true
for (int i = 0; i & i++)
if(b[i] && BinarySearch(a, n, c[i]))
return c[i] ;
return - 1 ; // not found
排序和二分搜索代码如下：// Determine whether a contains value k
bool BinarySearch(int *a, int n, int k)
int left = 0 ;
int right = n - 1 ;
while (left &= right)
int mid = (left + right) ;
if(a[mid] & k)
left = mid + 1 ;
if(a[mid] == k)
right = mid - 1 ;
// Compare function for qsort
int compare(const void* a, const void* b)
return *(int*)a - *(int*)
总结一下，对于在数组中进行查找的问题，可以分如下两种情况处理：
如果给定的数组有序，那么首先应该想到Binary Search，所需O(logn)。
如果给定的数组无序，那么首先应该想到对数组进行排序，很多排序算法都能在O(nlogn)时间内对数组进行排序，然后再使用二分搜索，总的时间复杂度仍是O(nlogn)。
如果能做到以上两点，大多数关于数组的查找问题，都能迎刃而解。
找出数组中唯一的重复元素
给定含有1001个元素的数组，其中存放了1-1000之内的整数，只有一个整数是重复的，请找出这个数。
求出整个数组的和，再减去1-1000的和即可，代码略。
找出出现奇数次的元素
给定一个含有n个元素的整型数组a，其中只有一个元素出现奇数次，找出这个元素。
因为对于任意一个数k，有k ^ k = 0，k ^ 0 =
k，所以将a中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，只留下了个数为奇数的那个元素。int FindElementWithOddCount(int *a, int n)
int r = a[0] ;
for (int i = 1; i & ++i)
r ^= a[i] ;
求数组中满足给定和的数对
给定两个有序整型数组a和b，各有n个元素，求两个数组中满足给定和的数对，即对a中元素i和b中元素j，满足i + j = d(d已知)。
两个指针i和j分别指向数组的首尾，然后从两端同时向中间遍历，直到两个指针交叉。// 找出满足给定和的数对
void FixedSum(int* a, int* b, int n, int d)
for (int i = 0, j = n - 1; i & n && j &= 0)
if (a[i] + b[j] & d)
else if (a[i] + b[j] == d)
cout && a[i] && ", " && b[j] &&
else // a[i] + b[j] & d
最大子段和
给定一个整型数组a，求出最大连续子段之和，如果和为负数，则按0计算，比如1， 2， -5， 6， 8则输出6 + 8 = 14。
编程珠玑上的经典题目，不多说了。// 子数组的最大和
int Sum(int* a, int n)
int curSum = 0;
int maxSum = 0;
for (int i = 0; i & i++)
if (curSum + a[i] & 0)
curSum = 0;
curSum += a[i] ;
maxSum = max(maxSum, curSum);
return maxS
最大子段积
给定一个整型数足a，求出最大连续子段的乘积，比如 1， 2， -8， 12， 7则输出12 * 7 = 84。
与最大子段和类似，注意处理负数的情况。// 子数组的最大乘积
int MaxProduct(int *a, int n)
int maxProduct = 1; // max positive product at current position
int minProduct = 1; // min negative product at current position
int r = 1;
// result, max multiplication totally
for (int i = 0; i & i++)
if (a[i] & 0)
maxProduct *= a[i];
minProduct = min(minProduct * a[i], 1);
else if (a[i] == 0)
maxProduct = 1;
minProduct = 1;
else // a[i] & 0
int temp = maxP
maxProduct = max(minProduct * a[i], 1);
minProduct = temp * a[i];
r = max(r, maxProduct);
数组循环移位
将一个含有n个元素的数组向右循环移动k位，要求时间复杂度是O(n)，且只能使用两个额外的变量，这是在微软的编程之美上看到的一道题。
比如数组 1 2 3 4循环右移1位 将变成 4 1 2 3， 观察可知1 2 3 的顺序在移位前后没有改变，只是和4的位置交换了一下，所以等同于1 2
3 4 先划分为两部分 1 2 3 | 4，然后将1 2 3逆序，再将4 逆序 得到 3 2 1 4，最后整体逆序 得到 4 1 2 3。// 将buffer中start和end之间的元素逆序
void Reverse( int buffer[], int start, int end )
while ( start & end )
int temp = buffer[ start ] ;
buffer[ start++ ] = buffer[ end ] ;
buffer[ end-- ] =
// 将含有n个元素的数组buffer右移k位
void Shift( int buffer[], int n, int k )
Reverse( buffer, 0, n - k - 1) ;
Reverse( buffer, n - k, n - 1 ) ;
Reverse( buffer, 0, n - 1 ) ;
字符串逆序
给定一个含有n个元素的字符数组a，将其原地逆序。
可能您觉得这不是关于数组的，而是关于字符串的。是的。但是别忘了题目要求的是原地逆序，也就是不允许额外分配空间，那么参数肯定是字符数组形式，因为字符串是不能被修改的（这里只C/C++中的字符串常量），所以，和数组有关了吧，只不过不是整型数组，而是字符数组。用两个指针分别指向字符数组的首位，交换其对应的字符，然后两个指针分别向数组中央移动，直到交叉。// 字符串逆序
void Reverse(char *a, int n)
int left = 0;
int right = n - 1;
while (left & right)
char temp = a[left] ;
a[left++] = a[right] ;
a[right--] =
给定一个含有n个元素的整型数组a，从中任取m个元素，求所有组合。比如下面的例子：a = 1, 2, 3, 4, 5
输出：1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5
典型的排列组合问题，首选回溯法，为了简化问题，我们将a中n个元素值分别设置为1-n。// n选m的所有组合
int buffer[100] ;
void PrintArray(int *a, int n)
for (int i = 0; i & ++i)
cout && a[i] && " ";
bool IsValid(int lastIndex, int value)
for (int i = 0; i & lastI i++)
if (buffer[i] &= value)
void Select(int t, int n, int m)
if (t == m)
PrintArray(buffer, m);
for (int i = 1; i &= i++)
buffer[t] =
if (IsValid(t, i))
Select(t + 1, n, m);
合并两个数组
给定含有n个元素的两个有序（非降序）整型数组a和b。合并两个数组中的元素到整型数组c，要求去除重复元素并保持c有序（非降序）。例子如下：a = 1, 2, 4, 8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8
利用合并排序的思想，两个指针i,j和k分别指向数组a和b，然后比较两个指针对应元素的大小，有以下三种情况：
a[i] & b[j]，则c[k] = a[i]。
a[i] == b[j]，则c[k]等于a[i]或b[j]皆可。
a[i] & b[j]，则c[k] = b[j]。
重复以上过程，直到i或者j到达数组末尾，然后将剩下的元素直接copy到数组c中即可。// 合并两个有序数组
void Merge(int *a, int *b, int *c, int n)
int i = 0 ;
int j = 0 ;
int k = 0 ;
while (i & n && j & n)
if (a[i] & b[j])// 如果a的元素小，则插入a中元素到c
c[k++] = a[i] ;
else if (a[i] == b[j])// 如果a和b元素相等，则插入二者皆可，这里插入a
c[k++] = a[i] ;
else // a[i] & b[j] // 如果b中元素小，则插入b中元素到c
c[k++] = b[j] ;
if (i == n) // 若a遍历完毕，处理b中剩下的元素
for (int m = m & ++m)
c[k++] = b[m] ;
else//j == n,
若b遍历完毕，处理a中剩下的元素
for (int m = m & ++m)
c[k++] = a[m] ;
给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：
排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变。
不能使用额外存储空间。
例子如下：输入 0, 3, 0, 2, 1, 0, 0，输出 0, 0, 0, 0, 3, 2, 1。
此排序非传统意义上的排序，因为它要求排序前后非0元素的相对位置不变，或许叫做整理会更恰当一些。我们可以从后向前遍历整个数组，遇到某个位置i上的元素是非0元素时，如果a[k]为0，则将a[i]赋值给a[k]，a[k]赋值为0。实际上i是非0元素的下标，而k是0元素的下标。void Arrange(int* a, int n)
int k = n - 1 ;
for (int i = n - 1; i &= 0; --i)
if (a[i] != 0)
if (a[k] == 0)
a[k] = a[i] ;
a[i] = 0 ;
本文地址：，欢迎访问原出处。
发表评论：
馆藏&14087
TA的推荐TA的最新馆藏[转]&