国家电网考试备考资料：计算机之数据结构与算法(一)
- 格式：docx
- 大小：32.14 KB
- 文档页数：5
国家电网考试备考资料：计算机之数据结构与算法
（一）
1.数据结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
记为：Data_Structure=(D,R)，其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。
数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。
逻辑结构包括：1.集合2.线性结构3.树形结构4.图形结构
2.数组 (Array)
在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。
这些按序排列的同类数据元素的集合称为数组。
在C语言中，数组属于构造数据类型。
一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。
因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。
数组类别：
多维数组
有时需要追踪记录数组中的相关信息。
例如，为了追踪记录计算机屏幕上的每一个像素，需要引用它的 X、Y坐标。
这时应该用多维数组存储值。
可用 Visual Basic 声明多维数组。
例如，下面的语句声明了一个过程内的 10 × 10 的二维数组。
Static MatrixA (9,9) As Double
可用显式下界来声明两个维数或两个维数中的任何一个：
Static MatrixA (1 To 10,1 To 10) As Double
可以将所有这些推广到二维以上的数组。
例如：
Dim MultiD (3,1 To 10,1 To 15)
这个声明建立了三维数组，大小为 4 × 10 × 15。
元素总数为三个维数的乘积，为 600。
注意
在增加数组的维数时，数组所占的存储空间会大幅度增加，所以要慎用多维数组。
使用 Variant 数组时更要格外小心，因为他们需要更大的存储空间。
用循环操作数组：
可以用 For循环嵌套有效的处理多维数组。
例如，在 MatrixA 中基于每个元素在数组中的位置为其赋值：
Dim I As Integer,J As Integer
Static MatrixA(1 To 10,1 To 10) As Double
For I = 1 To 10
For J = 1 To 10
MatrixA (I,J) = I * 10 + J
Next J
Next I
一维数组
定义
一维数组是最简单的数组，其逻辑结构是线性表。
要使用一维数组，需经过定义、初始化和应用等过程。
数组声明
在数组的声明格式里，"数据类型"是声明数组元素的数据类型，可以是java语言中任意的数据类型，包括简单类型和结构类型。
"数组名"是用来统一这些相同数据类型的名称，其命名规则和变量的命名规则相同。
数组声明之后，接下来便是要分配数组所需要的内存，这时必须用运算符new，其中"个数"是告诉编译器，所声明的数组要存放多少个元素，所以new运算符是通知编译器根据括号里的个数，在内存中分配一块空间供该数组使用。
利用new 运算符为数组元素分配内存空间的方式称为动态分配方式。
举例：
int[]x; //声明名称为x的int型数组
x=new int[10]; //x数组中包含有10个元素，并为这10个元素分配内存空间
在声明数组时，也可以将两个语句合并成一行，格式如下：
数据类型[]数组名= new 数据类型[个数];
利用这种格式在声明数组的同时，也分配一块内存供数组使用。
如上面的例子可以写成：
int[]x = new int [10];
等号左边的int[]x相当于定义了一个特殊的变量x，x的数据类型是一个对int 型数组对象的引用，x就是一个数组的引用变量，其引用的数组元素个数不定。
等号右边的new int[10]就是在堆内存中创建一个具有10个int型变量的数组对象。
int[]x = new int [10];就是将右边的数组对象赋值给左边的数组引用变量。
二维数组
定义
前面介绍的数组只有一个下标，称为一维数组，其数组元素也称为单下标变量。
在实际问题中有很多量是二维的或多维的，因此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数组三行四列的元素。
下标变量和数组说明在形式中有些相似，但这两者具有完全不同的含义。
数组说明的方括号中给出的是某一维的长度，即可取下标的最大值; 而数组元素中的下标是该元素在数组中的位置标识。
前者只能是常量，后者可以是常量，变量或表达式。
一个学习小组有5个人，每个人有三门课的考试成绩。
求全组分科的平均成绩和各科总平均成绩。
课程成绩姓名Math C DBASE
张80 75 92
王61 65 71
李59 63 70
赵85 87 90
周76 77 85
可设一个二维数组a[5][3]存放五个人三门课的成绩。
再设一个一维数组v[3]存放所求得各分科平均成绩，设变量l为全组各科总平均成绩。
编程如下：void main()
{
int i,j,s=0,l,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]);
s=s+a[j];}
v[i]=s/5;
s=0;
}
l=(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",l);
} for(i=0;j<3;i++)
for(j=0;j<5;j++)
{ scanf("%d",&a[j]);
s=s+a[j];}
v=s/5;
s=0;
}
l=(v[0]+v[1]+v[2])/3;
程序中首先用了一个双重循环。
在内循环中依次读入某一门课程的各个学生的成绩，并把这些成绩累加起来，退出内循环后再把该累加成绩除以5送入v之中，这就是该门课程的平均成绩。
外循环共循环三次，分别求出三门课各自的平均成绩并存放在v数组之中。
退出外循环之后，把v[0],v[1],v[2]相加除以3即得到各科总平均成绩。
最后按题意输出各个成绩。
