当前位置：文档之家 › 第四章 数组

第四章 数组

  • 格式：ppt
  • 大小：147.51 KB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

数据结构第四章 数组

数据结构第四章 数组

4.2
数组的存储结构
通常采用顺序存储结构 顺序存储结构 以二维数组Amn为例
行优先 a00 a01 … a0(n-1) a10 a11 … a1(n-1) … a(m-1)0 a(m-1)1 … a (m-1)(n-1) 列优先
Loc(aij)=Loc(a00)+(i×n+j)×k
a00 a10 … a (m-1)0 a01 a11 … a (m-1) 1 … a0(n-1) a1(n-1) … a (m-1)(n-1)
0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 14 0 0 0
（以转置运算为例） 以转置运算为例）
0 0 0 0 0 0
M
转置后
0 12 9 0 0 0
0 0 0 0 0 0
–3 0 0 0 14 0
0 0 15 0 18 0 24 0 0 0 0 -7 0 0 0 0 0 0
思路：反复扫描a.data中的列序，从小到大依次进行转置。 思路：反复扫描a.data中的列序，从小到大依次进行转置。 a.data中的列序
col
三 元 组 表 a.data (0, 1, 12) ③ 1 (0, 2, 9 ) ⑤ 0 (2, 0, -3) ① (2, 4, 14) (3, 2, 24) 1 (4, 1, 18) 0 (5, 0, 15) (5, 3, -7)
其中，sb[n(n+1)/2]中存放着常数 中存放着常数。 其中，sb[n(n+1)/2]中存放着常数。
三、稀疏矩阵的压缩存储
稀疏矩阵：设矩阵A中有s个非零元素， 稀疏矩阵：设矩阵A中有s个非零元素，若 远远小于矩阵元素的总数（ s远远小于矩阵元素的总数（即s≦m×n）， 则称A为稀疏矩阵。 则称A为稀疏矩阵。

数组

数组

C语言程序设计
20/60
【例4.4】
编写程序，将一个二维数组中行和列元素互换， 存到另一个二维数组中。设数组
1 a= 2 5 9 6 8
1 2 b= 5 6 9 8
C语言程序设计
21/60
main() { int a[2][3]={{1,5,9},{2,6,8}}; int b[3][2],i,j; printf("Array a:\n"); /* 输入原来数组的数据 */ for(i=0;i<2;i++) { for(j=0;j<3;j++) { printf("%4d",a[i][j]); b[j][i]=a[i][j]; /* 将两个数组元素相互交换 */ } printf("\n")； }
10/60
冒泡法排序
例如：int a[5]={4，7，3，9，1}；则对数组 的排序过程如图所示。
第一次遍历 4 7 3 9 1 4 7 3 9 1 4 3 7 9 1 4 3 7 9 1 4 3 7 1 9 第二次遍历 4 3 7 1 3 4 7 1 3 4 7 1 3 4 1 7 第三次遍历 3 4 1 3 4 1 3 1 4 第四次遍历 3 1 1 3
18/60
2．二维数组元素的输入和输出
二维数组元素同以前学习过的普通变量一样，可 以通过格式输入和输出函数来进行输入和输出。 例如： scanf("%d,%d",&a[0][1],&a[2][1]);
/*从键盘上输入值赋给了数组元素a[0][1]和a[2][1]*/
printf("%d,%d",a[0][0],a[2][2-1]); /*输出数组元素a[0][0]和a[2][1]*/

DS第四章 数组

DS第四章 数组

起始位置，亦称为基地址。
1
2
i 1
k i 1

练习1：


数组A[0..5,0..6]，每个元素占5个字节，首地 址为1000，按列优先存储，则A[5,5]的存储地 址是 （ ）。 分析： 因为是按列优先，所以在A[5,5] 前已经 存储了0～4列共5列，每列有6个元素，所以共 5×6＝30个元素。在第5列上， A[5,5]之前有 5个元素，则A[5,5]之前共有30+5=35个元素， 所以其地址为： 1000+35*5=1175

矩阵中元素已经按行和按列排好序，要求查找的时间复杂度为 O(m+n)，因此不能采用常规的二层循环的查找。 方法：从B的右上角元素开始比较，每次比较有3种可能的结果： 1) B[i,j]=x ，查找成功； 2) B[i,j]>x，则向j小的方向（即向左）继续查找（减少一列）； 3) B[i,j]<x，则向i大的方向（即向下）继续查找（减少一行）； 这样：每次比较可以使得搜索范围减少一行或一列，最多经过 m+n次比较就可以找到。 若下标超出范围，则查找失败。
(i 1) * (2n i 2) (n p 1) 2 p 1
i 1
个元素，而在第i行上aij之前有j-i个元素，它是所 在行的第（j-i+1）个元素，所以，它是数组a的第 (i-1)*(2n-i+2)/2+(j-i+1)个元素。 注意到B的 下标从0开始：

因此aij和B[k]之间的对应关系为：
i (i 1) j 1 2 k j ( j 1) i 1 2
当i j j
= LOC(B[0])+K*L=LOC(B[0])+[I*(I-1)/2+J-1]*L

数据结构第4章数组和串

数据结构第4章数组和串
1
● 教学目的：理解抽象数据类型数组的概念， 掌握数组的不同存储结构的实现及应用，了 解广义表的相关概念，掌握串的逻辑结构、 存储结构及其基本运算。
● 教学重点：数作在不同 存储结构上的实现。 ● 教学难点：带状矩阵的压缩存储；稀疏矩 阵的三元组表实现及其转置算法，堆结构的 串操作实现；串的模式匹配算法。
矩阵的压缩存储
printf("Array a:\n"); k=0; for(i=0;i<N;i++)//输出矩阵A { for(j=0;j<N;j++) if(i<j)printf("%5d",sa[M-1]); else printf("%5d",sa[i*(i+1)/2+j]); printf("\n"); } printf("Array b:\n"); k=0; for(i=0;i<N;i++)//输出矩阵B { for(j=0;j<N;j++) if(i>j)printf("%5d",sb[M-1]); else printf("%5d",sb[j*(j+1)/2+i]); printf("\n"); }}
矩阵的压缩存储
由此可见，要唯一表示一个稀疏矩阵，在存储三 元组表的同时还需存储该矩阵总的行数、列数及非 零元个数。 练习：写出图4-9(a)所示稀疏矩阵的三元组表。
三元组表（也是线性表）的存储方式主要有两种： 顺序存储和链式存储，从而可引出稀疏矩阵的两种 压缩存储方法：三元组顺序表和十字链表。 3、三元组顺序表
矩阵的压缩存储

《C语言程序设计课件》第四章-数组

《C语言程序设计课件》第四章-数组
提示：程序在读入数时将其存储在一个数组中， 然后通过数组反向开始一个接一个地显示出数组 元素。
#include <stdio.h> #define N 10 int main(void)
{ int a[N], i; printf("Enter %d numbers: ", N);
for (i = 0; i < N; i++)
for(i=0;i<1;i++) if (a[i]>a[i+1]) { t=a[i];a[i]=a[i+1];a[i+1]=t; }
a[0]
20
a[1]
02
a[2]
44
a[3]
55
a[4]
88
a[5]
99
for(i=0;i<5;i++) if (a[i]>a[i+1]) { ……}
for(i=0;i<4;i++) if (a[i]>a[i+1]) { ……}
4.2 一维数组
一维数组主要用来存储一组类型相同并且数量一定 的数据。其中，每个数据称为数组的一个元素。
4.2.1 一维数组定义 一维数组的定义形式如下： 类型名 数组名[常量表达式]; int x[100]; char string[10]; double data[10];
常量表达式给出了数组的长度，在C语 言中定义数组时必须确定数组的长度。
600
xxx[[[654]]]
700
xxx[[[765]]]
800
xxx[[[876]]]
900
xxx[[[987]]]

第04章 数组

第04章 数组
高 级 语 言 程 序 设 计 与 应 用 教 程
第4章
数
组
第 四 章
数 组
1
高 级 语 言 程 序 设 计 与 应 用 教 程
第4章：数 组
学习的意义
到目前为止，我们已经讨论了C语言中的基本数据类型， 如果用基本数据类型来定义某些变量，那么这些变量在内存 中将占用各自的内存单元，变量之间的制约关系无法体现， 不能表现出这些变量之间的关联性，看不出它们之间有任何 构造数据类型之一 有没有更好的方法来 的联系，我们把这些变量称之为‚离散变量‛，对它们的访 数组:把具有相同类型的若干变量按有序的形式 问只能通过变量名逐一进行 。 解决呢？ 组织起来的集合，用数组名标识。 有！就是用数组来编程。 下面来思考一个问题：如何编程来实现对100个数进行排序呢？ 数组元素:数组中的变量。用数组名和下标确定， 具有相同的名字，但有不同的下标。 解题思路： 太复杂了！ 定义100个整型变量来 晕！！！ 分别存放这100个整数，然 后再对这些变量的值进行比 较、交换等操作 。
//超出了数组的大小
(3) 只能给元素逐个赋值，不能给数组整体赋值。 例 int a[5] = {1, 1, 1, 1, 1}; 不能简化为: int a[10] = 1; ×
第 四 章
数 组
14
高 级 语 言 程 序 设 计 与 应 用 教 程
初始化赋值说明：
(4) 如果表达式的个数小于数组的大小，则未指定值的 数组元素被赋值为0；
4
高 级 语 言 程 序 设 计 与 应 用 教 程
第 四 章
4. 类型名int说明a数组中的10个数组元素都是整型，在每个 数组元素中只能存放整型数据。数组的类型实际上是指数 组元素的取值类型。对于同一个数组，其所有元素的数据 类型都是相同的。 5. 数组定义后， C语言的编译系统将给其分配一定大小的内 再例如： 存单元，其所占内存单元的大小与数组元素的类型和数组 float f[20]; //定义了有20个数据元素的float型数组f 的长度有关。上例中，系统为a数组在内存中开辟一段连 char str1[10], str2[20]; //定义了有10个和20个数据元素的char型 续的存储单元，如图所示。在图中标明了每个存储单元的 数组str1和str2 名字，可以用该名字直接引用每个存储单元。a数组在内 存中一共分配了10个int型的存储单元，而每个int型数据 占用4个字节（VC6.0），所以，a数组一共占用了40个字 节的连续存储单元。

第4章：数组和字符串

【真题练习】设有以下代码： String s l="123"； String s2="123"； String s3=new String("123")； 则表达式s1==s2和s1==s3的值分别是( A.true，true B.false，false C.true，false D.false，true )
4.1.1一维数组
2． 创建一维数组
创建一维数组就是为数组分配存储空间，需指定数组长度。 数组创建后，数组名就标识用于存储数组元素的存储空间(引用)。 创建一维数组的３种方法：
（1） 先声明后创建
数组元素类型 数组名[]; 数组名 ＝ new 数组元素类型[元素个数] ； 如：int intArray []; intArray = new int[5];4.2.3 字符串基本操作
字符串比较的注意事项：
表达式 str1.equals(str2)与表达式 str1==str2 的差异 在于：
• 前者表示所引用的两个字符串的内容是否相同， • 后者表示str1 与 str2是否引用同一个对象。 【实战编程技巧：如何避免潜在的空指针异常】
练习题
4.1 数组
4.2 字符串
4.1 数组
数组是将一组相同类型的数据顺序存储，组成的一 种复合数据类型。 数组的特点：
数组中的所有元素的数据类型相同。 数组中的元素连续顺序存储。 数组中每个元素按存储顺序对应一个下标，下标从０开始顺序编号 ，引用数组元素通过数组名和它的下标确定。 数组有一维数组和多维数组之分，数组元素的下标个数确定数组的 维数。
练习题
【真题练习】设有数组a和b的定义如下： int[]a={1,2,3}; int[]b={4,5,6} …… 执行以下代码“a=b；”,除了完成赋值操作之外，引起 系统额外要做的工作是_________。

《c++程序设计》第4章 数组

； （2）字符数组1必须足够大，以便容纳被复制的字符串； （3）字符串2后的'\0'也一起复制到字符数组1中； （4）在赋值运算符“=”没有重载之前，不能用赋值语句将一个字符串常量或字符数组
赋给另一个字符数组，只能用字符串复制函数来处理。例如下面操作是非法的： str2="C++ program"; str1=str2;
4.1 数组的定义与使用
4.1.1 一维数组的定义和使用
1.一维数组的定义与初始化赋值 （1）一维数组的定义
定义格式为：
〔存储类型〕 <类型> <数组名>[<常量表达式>]; 例：int a[10];
表示定义一个名为a的整型数组，有10个元素，分别为a[0]、a[1]、 a[2]、a[3]、a[4]、a[5]、a[6]、a[7]、a[8]、a[9] 。
int a[ ][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}}; 或： int a[ ][4]={1,2,3,4,5,6,7,8,9,10,11,12};
二维数组的初始化赋值
② 给数组的部分元素赋初值 给数组的部分元素赋初值的方法与给数组的所有元素赋初值的方法 类似。
3.字符串连接函数strcat()
格式：strcat(<字符数组1>，<字符串2>) 功能：将字符串2连接到字符数组1中的字符串后，其结果存放在字符数组1中。 例如：
char str1[30]="I am a "; char str2[]="student."; strcat(str1,str2); 则字符数组1的内容为"I am a student."。 说明： （1）字符数组1必须是字符数组名，字符串2可以是字符数组名，也可以是字符串常量； （2）字符数组1必须足够大，以便容纳连接后的新字符串； （3）连接时字符串1之后的'\0'取消，只在新字符串最后保留一个'\0'。

C51-数组

int a［10］; int i,j,t; printf(″input 10 numbers :\n″); for (i=0;i<10;i++) scanf("%d"，&a[i]); printf("\n");
for(j=0;j<5;j++)
for(i=0;i<5-j;i++)
if (a［i］>a［i+1］)
2、一维数组元素引用的程序实例
以下程序运行后的输出结果是（ ）。
#include <stdio.h>
void main()
{
int a[5]={1,2,3,4,5},b[5]={0,2,1,3,0},i,s=0;
for(i=0;i<5;i++) s=s+a[b[i]] ;
printf("%d\n", s); }
第四章 数组
第四章 数组
本讲主要任务： 一维数组、二维数组；字符数组。
掌握要求： 掌握以上基本的编程流程、应用以及嵌套应 用。
考试题：一般出现在程序填空题、阅读程序以 及程序编程题中。(核心考试点)
问题：给一组数排序，这组 数该 如何存放呢
111 1 1
1
1
1
111 1
1
1
881 2 8 8
9
4
算法思想： ① 确定要插入数的位置， ② 然后将比这个数大的所有数后移一个位置， ③ 在空出的位置上将该数插入。
#include <stdio.h> void main() { int i, p; int a[11]={1，3，6，7，9，12，14，18，19，20};

第四章_数组

22
4.2
多维数组
下列程序段实现对数组 int s[3][5]的动态赋值： 4.2.3 二维数组元素的引用 for(i=0; i<=2; i++) /* 行标i从0开始变化到2*/ 二维数组的元素也称为双下标变量，其表示的形式为： for(j=0; j<=4; j++) /* 列标j从0开始变化到4*/ 数组名 ][ 列下标 ] scanf( “%d”[ , 行下标 &s[i][j]) ； /*二维数组元素如同普通 其中下标应为整型常量或整型表达式，其取值范围从 整型变量操作*/ 0开始，分别到行数 -1和列数-1。 例如： a[3][4] 通过前面的学习，对数组也可以这样理解：单个变量描述 了空间中‚点‛的概念，一维数组是对单个变量的扩展，它描 表示a数组中行标为3,列标为4的元素。 述了空间中‚线‛的概念，而二维数组又对一维数组做了扩展， 如果要引用数组中的全部元素，只要利用循环语句即 描述了空间中‚平面‛的概念。人们可以模仿二维数组的使用 可实现，这是对数组中元素进行操作的基本算法。对于一 方法来实现多维数组等各种数据容器。例如，可用如下方法定 维数组，只需用单重循环就可完成；而对于二维数组则需 义三维数组: int a[2][3][4]； 要使用两重循环来完成，外循环控制行标变化，内循环控 多维数组元素在内存中的排列顺序为：第一维的下标变化 制列标变化。 最慢，最右边的下标变化最快。
20
s[0][3]
s[1][1] s[1][2]
……
4.2
多维数组
4.2.2 二维数组的初始化 二维数组初始化也是在类型说明时给各下标变量赋以初值。 二维数组可按行分段赋值，也可按行连续赋值。 例如对数组int s[3][5]： (1)按行分段赋值可写为: int s[3][5]={{80,75,92,61,65},{71,59,63,70,85},{87,90,76, 77,85}}； (2)按行连续赋值可写为: int s[3][5]={ 80,75,92,61,65,71,59,63,70,85,87,90,76,77, 85}； 这两种赋初值的结果是完全相同的。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

4.1 一维数组
5 数组越界
在给数组元素赋值或对数组元素进行引用时，一 定要注意下标的值不要超过数组的范围，否则会
产常生用数下组面越界的问式题子。确因定为数当组数的组下大标小越，界预时防，数编 译组器越并界不情认为况它的是发一生个。错误，但这往往会带来非 常假严定重对的于后果一。个整型数组a，它的大小为： 例如：定义了s一iz个eo整f型（数a）组a/：sizeof（int） sizeof（intaa）[1表0];示求数组a在内存中所占字 数节组数a的，合s法iz下eo标f（为0i~n9t。）如表果示程求序整要型求给数a据[10内]赋 值存，中将所可占能导字致节程数序。出错，甚至系统崩溃。
例如前当：面初对的始上元化面素定值按义的顺的个序数数组初少a始进于化行数相初组始应元化的素。值个，数后时， 面ch不ar足a的[5部]分={由’a系’,统’b自’,动’c初’,始’d化’,为’e零’};
或：（对数值数组）或空字符‘\0’（对字符 数ch组ar）a。[ ]={’a’,’b’,’c’,’d’,’e’};
4.2 二维数组
1 二维数组的定义
a[0]
a[1]
a[2]
a[3]
a[4]
图4-1 一维数组的存储
4.1 一维数组
2.一维数组的初始化 在定义在数对组时数对组其初中始的化全时部，或部也分可指以定只初对始数值组，中这 称为数的值组部的的分个初元 数始素 可化指 以。只定 少有初 于存始 或储值 等类。 于别数也为组即静态定，的义初或的始外元化部 的数组素才的可个以数进，行但初始不化可。以初多始于化数的组语法元格素式的为个： 类型数数，组否名则[ 数会组引范起围编]译={错值误1，。值2，…，值n}
第四章
数组
第四章 数 组
本章内容主要有: 一维数组 多组
学习的目标 掌握一维数组 掌握多维数组 掌握字符数组和字符串
第四章 数 组
一种最简单的构造型（复合型）数据类型。 由类型相同的元素组成的有序的数据集合。 可以存储基本数据类型或对象。 通过数组名和下标可以访问各元素。 构成数组的这组元素在内存中占用一组连续
cin>>a;
int i; for (i=0;i<5,i++) cin>>a[i];
4.1 一维数组
4 数组元素的引用 数组在定义后即可引用。其引用形式为： 数组名[下标] 指明了引用数组名的数组中下标所标识的元 素注。意下：标可以是整常数或整型表达式。例如 a能不[此现对是2时错+数对1用误组整]、。a的个=a因1某 数0[i为这+一 组数样j个 。]等组的元 如（a语素 ：不i句和进 例能引j行 如代为用单 ：表整数独整型组的个变，引数量则用组）会，，。出而只 a[它2]=只1代0; 表数/组/将的1首0赋地给址数组，中即的代a[2表]元数素组。 元素 a[a5[]=0]a[在2]内; 存中//的将a地[2址]元，素数的值组赋名给在a[5程]元序素中不 cao[能2u]t=<改a<变[a0[]5，+]a;即[1不]; //能//打a有[印0]aa元+[5+素]之元和类素a[的1的]值元语素句之和赋给a[2]
const int size=10; int b[size]; 注意：在定义数组时，不能用变量来描述数组定 义中的元素个数。例如，下面的定义方式是不合 法的：
int b[n];
4.1一维数组
下标指明了数组中每个元素的序号，下标值 为整数，用数组名加下标值就可以访问数组 中对应的某个元素。
下标值从0开始，因此对于一个具有n个元 素的一维数组来说，它的下标值是0~ n-1。
常量表达式又称下标表达式，表示一维数组中元 素的个数，即数组长度（也称为数组大小），用 一对
方括号“[ ]”括起来。方括号“[ ]”的个数代表数 组
4.1一维数组
例如：下面分别定义了一个具有5个元素的字符型 数组a和一个具有10个元素的整型数组b：
char a[5]; int b[10]; 对上面定义的数组b，也可以采用下面这种定义方 法：
4.1 一维数组
3 数组的赋值
1) 用“=”赋值 与数组的初始化不同，在给数组元素进行赋值
时，若必要须在逐数一组赋之值间。进行赋值，也只能一个 例如一：个对元于素下地述赋的值数组。初始化： 其等例样价如大的：小ii赋nn将 的tt值上 数aa形[[述 组式33]]数b如;=，{下组1可：,a2的以,3值利};赋用给下另面一的个循同环
完成赋a[值0]操=1作; ： a[1]=f2o;r (i=0;i<3;i++)
b[i]=aa[[2i]]=;3;
4.1 一维数组
2) 用流命令赋值
其语法格式为：
cin>>数组名；或
cin>>数组名[下标]；
例如：对一个大小为5的字符型数组a赋值， 可以用下列两种方式：
char a[5]; 或
char a[5];
的存储单元。 根据数组的维数，分为一维数组、二维数组
和多维数组，常用的是一维和二维数组。
4.1一维数组
1.一维数组的定义格式为： 类型 数组名[常量表达式]； 其中，类型是数组类型，即数组中各元素的数据
类型，可以是整型、浮点型、字符型等基本类型。
数组名是一个标识符，代表着数组元素在内存中 的起始地址，它的命名规则与变量名的命名一样。
4.1 一维数组
例如：
int c[5]={1,2};
定义整型数组c有5个元素，但只初始化前两个元 素：c[0]=1，c[1]=2。对于后面的三个元素没 有定义初始值，此时由系统自动给它们赋0。 当数组长度与初始化元素的个数不相等时，数组 长度不能省去不写，如上例不能写为：
int c[ ]={1，2}； 否则编译器会认为数组c只有2个元素而不是5个 元素。
例如，对上例中定义的数组b来说，b[0]是 数组中的第一个元素，b[1]是数组中的第二 个元素，…，b[9]是数组中的最后一个元素， 而不包含b[10]。
4.1一维数组
数组元素在内存中是顺序存储的。对于 一维数组，就是简单地按下标顺序存储。 例如，对上面定义的整型数组a，在内存 中的存放顺序如图4-1所示：