Array
Weng Kai
2020 Fall
• How do we write a program to calculate the average of all
the numbers user inputs?
• It is not needed to record every number that user inputs.
• How do we write a program to calculate the average of all
the numbers user inputs, and all the numbers that are
greater than the average?
• Every number inputed has to be recorded and be
compared with the average after the end of the input.
How to record many numbers?
• int num1,num2,num3…..?
数组array
• int number[100];
• scanf(“%d”, &number[i]);
Iteration of an Array
define an array
assignment
for element
sa f e . W hy ?
ra m i s n o t
This prog
to use
element
iteration of
the array
Define Arrays
• <type> name[number of elements];
• int grades[100];
• double weight[20];
• Number of elements has to be an integer
• Before C99: the number has to be a literal
array数组
• is a kind of container (thing that hold things):
• All elements are of the same type;
• Once created, it is not allowed to change the
size(capacity)
• *（数组中的元素在内存中是连续依次排列的）
int a[10]
• An array of int
• 10 elements: a[0],a[1],…,a[9]
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
• Each element is a variable of int
• Can be used at the left side or right side of an assignment operator
• a[2] = a[1]+6;
• The one at the left is called left value
Element数组的单元
• Each element is a variable of the type of that array
• The number in [] is called 下标subscript or 索引index, that
begins from 0:
• grades[0]
• grades[99]
• average[5]
several peoples’ heights in inches.
In Java, array indexes always begin at zero. Therefore the value stored at i
5 is actually the sixth value in the array. The array shown in Figure 8.1 ha
element of an array
values, indexed from 0 to 10.
406 CH APT ER 8 Arrays
To access a value in an array, we use the name of the array
K EY C O N C EPT
lowed by the index in square brackets. For example, the follo
An array of size N is indexed from
0 to N–1.
expression refers to the ninth value in the array height:
8.1 Array Elements
height[8]
According to Figure 8.1, height[8] (pronounced height-sub-eight) con
An array is a simple but powerful programming language constr
the value 79. Don’t confuse the value of the index, in this case 8, with the v
group and organize data. When writing a program that manages a l
stored in the array at that index, in this case 79.
• each element is a variable of the type of information, such as a list of 100 names, it is not practical to dec
variables for each piece of height
data. Arrays solve this problem by lettin
one variable that can hold
0
multiple,
69
individually accessible values.
An array is a list of values. Each value is stored at a specific, numbe
• index or subscript starts from 0
1 61
in the array. The number corresponding to each position is called a
2 70
Figure 8.1 shows an array of integers and the indexes tha
subscript. index
to each position. The 3array is 74
called height; it contains integers th
•
several peoples’ heights4 in inches.
62
grades[0] 5 always
In Java, array indexes value of height[5]
69 begin at zero. Therefore the value sto
5 is actually the sixth 6value in
66 the array. The array shown in Figur
values, indexed from 07 to 10.73
• grades[99] K E Y C O N C EP T
To access
8 a value
79
lowed by9the index
in an array, we use the name of t
62 in square brackets. For example, t
An array of size N is indexed from
0 to N–1.
expression
10
refers70to the ninth value in the array height
• average[5] height[8]
F IG URE 8 . 1 An array called height containing integer values
According to Figure 8.1, height[8] (pronounced height-sub-eig
the value 79. Don’t confuse the value of the index, in this case 8, w
stored in the array at that index, in this case 79.
height
0 69
1 61
to each position. The array is called height; it contains integers that represent
several peoples’ heights in inches.
In Java, array indexes always begin at zero. Therefore the value stored at index
5 is actually the sixth value in the array. The array shown in Figure 8.1 has 11
values, indexed from 0 to 10.
To access a value in an array, we use the name of the array fol-
Question
K EY C O NCE P T
lowed by the index in square brackets. For example, the following
An array of size N is indexed from
0 to N–1.
expression refers to the ninth value in the array height:
height[8]
According to Figure 8.1, height[8] (pronounced height-sub-eight) contains
• Based on the array shown at right, what are each of the following?
the value 79. Don’t confuse the value of the index, in this case 8, with the value
stored in the array at that index, in this case 79.
height
1. height[1] 0 69
1 61
2. height[2] + height[5] index
2 70
3 74
4 62
3. height[2 + 5] 5 69 value of height[5]
6 66
7 73
4. the value stored at index 8 8 79
9 62
10 70
5. the fourth value
F IG U RE 8 .1 An array called height containing integer values
valid range of index
• Either the compiler or the run-time is not going to check wether the index is out-
of-range or not, whatever at reading from or writing to an element.
• In run-time, it is possible the out-of-range index causes severe program and
makes the program crashed.
• segmentation fault
• However it is possible nothing serious happens at good luck. However, it is still
dangerous.
• A program can compile —> may not be a program can run.
• A program can run this time —> may not be a program runs every time.
• It is your responsibility to make sure your program uses index with the range: [0,
the size of the array -1]
• This program is not safe because the number inputed may
exceed 100.
Average
• Using C99, it is possible that the use inputs the number of
numbers first.
Lab 1
• PTA 7-1 输出所有⼤于平均数的值
Iteration of Array
• The for loop is usually used to let i from 0 to <size of the array,
that the biggest i in the loop is the biggest valid index.
• Common pitfalls:
• The condition for the loop is : <= size of the array, or
• i is to be used as an index after loop!
Max or Min
• Use the first element as the seed for min or max
Lab 2
• PTA 7-2 求最⼩值及其下标
Insert and remove
• Array is a fixed-size container
• Inserting and removing data inside an array, is to move
data in the elements
Lab 3
• PTA 7-3
aggregate initialization
• Put all the init values in {}
• The size is not needed, because the compiler can count for you.
• However if the size of provided, but not all the init value,
the rest of the elements will be init with 0.
• It does not work for array sized with a variable.
集成初始化时的定位
• ⽤[n]在初始化数据中给出定位
• 没有定位的数据接在前⾯的位置后⾯
• 其他位置的值补零
• 也可以不给出数组⼤⼩，让编译器算
• 特别适合初始数据稀疏的数组
Size of an Array
• sizeof returns the number of bytes the whole array
occupies
可 扩 展 性 ！
• sizeof(a[0]) returns the size of one single element, so a
division gives the number of elements
• Code like this does not need to be modified when the init
data for array is to be changed.
assignment of arrays
• Array variable can not be assigned.
• To assign all elements of one array to another, an iteration
is a must.
数组的例⼦：素数
从2到x-1测试是否可以整除
• 对于n要循环n-1遍
• 当n很⼤时就是n
遍
去掉偶数后，从3到x-1，每次加2
• 如果x是偶数，⽴刻
• 否则要循环(n-3)/2+1遍
• 当n很⼤时就是n/2遍
⽆须到x-1，到sqrt(x)就够了
• 只需要循环sqrt(x)遍
sqrt
判断是否能被已知的且<x的素数整除
to construct a prime table
• To construct a prime table under n
1. let x = 2
2. mark 2x, 3x, 4x until ax<n as non-prime
3. make x the next non-marked number, go back to 2,
until all the numbers have beed tried
构造素数表
• 欲构造n以内（不含）的素数表
1. 开辟prime[n]，初始化其所有元素为1，prime[x]为1表示x是素数
2. 令x=2
3. 如果x是素数，则对于(i=2;x*i<n;i++)令prime[i*x]=0
4. 令x++，如果x<n，重复3，否则结束
构造素数表
• 算法不⼀定和⼈的思考⽅式
相同