第一讲线性表及其应用.ppt

2009年江苏省信息学奥林匹克夏令营（C层次）线性表及其应用 一、知识回顾 1 数据类型 2 子界类型 type agetype=1..150； chtype=a..z； var a1,a2:agetype； ch:chtype； {定义了a1、a2为子界类型agetype的两个变量，ch为子界类型chtype的变量。} 也可将类型定义与变量定义合并起来在变量说明中进行定义： var a1,a2:1..150； ch:a..z； 判断下列类型定义哪些是正确的，哪些是错误的。 (1)type atype=10..10*10； (2)type atype=1.2..2.0； (3)type atype=a..z； (4)type atype=1..5； (5)type atype=k..e； 引例： 输入50名学生某门课程的成绩，要求把高于平均分的那些成绩打印出来。 第一讲 数组 1 一维数组的定义 当数组中每个元素只带有一个下标时,我们称这样的数组为一维数组 1.1 数值数组 数组元素的类型是数值类型的一维数组。 1.2 字符数组 数组元素的类型是字符类型的一维数组。 2 数组的基本操作 2.1 数组的输入、输出 2.2 数组元素的查找 2.3 数组元素的移动 2.4 数组元素的插入 2.5 数组元素的删除 2.6 排序 2.7 应用举例 2.1 数组元素的输入、输出 字符数组应用举例： 程序： 2.2数组元素的查找 2.4 数组元素的插入 2.5 数组元素的删除 注意： 2.6 排序 冒泡排序法图示： 待排序数据：53 33 19 53 3 63 82 20 19 39 ? 第一趟排序：3 53 33 19 53 19 63 82 20 39 第二趟排序：3 19 53 33 19 53 20 63 82 39 第三趟排序：3 19 19 53 33 20 53 39 63 82 第四趟排序：3 19 19 20 53 33 39 53 63 82 冒泡排序法代码： 选择法排序法图示： 选择法排序法： 插入排序法图示 插入排序法代码： 快速排序法图示： 快速排序法： 2.7 应用举例 程序分析： 1）选取一种合适的方法排序 2）采用二分查找 3）进行插入或删除操作 3 二维数组及其存储方式 二维数组存储举例: 已知数组A中，每个元素A[I,J]在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A[5,8]的起始地址为（　　）? A.SA+141 B.SA+144 C.SA+222 D.SA+225 3.1 二维数组元素的输入、输出 3.2 数组基本操作举例 3.2.1 鞍点 3.2.2 回形方阵 3.2.3 螺旋方阵 3.2.1 鞍点 鞍点程序： program ex1; var a:array[1..5,1..5] of integer; i,j,min,minj:integer; flag:boolean; begin for i:=1 to 5 do for j:=1 to 5 do read(a[i,j]); for i:=1 to 5 do begin min:=a[i,1]; minj:=1; for j:=2 to 5 do if a[i,j]min then begin min:=a[i,j]; minj:=j; end; flag:=true; for j:=1 to 5 do if a[i,minj]a[j,minj] then flag:=false; if flag then write(a[,i,,,minj,]=,a[i,minj]); end; end. 3.2.2 回形方阵 任给n，试输出如下方阵，例如： N=7： 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 2 3 3 3 2 1 1 2 3 4 3 2 1 1 2 3 3 3 2 1 1 2