文档介绍:课程名称
数据结构
教学对象
新华软工
教材
数据结构(C语言)
授课内容
第五章数组
课时
1
教学目的
与要求
了解数组的定义、运算;掌握数组的存储;掌握特殊矩阵的概念和存储等
重点、难点
重点:数组的存储
难点:特殊矩阵的存储
课型
电脑+理论
教学方法
投影、讨论、板书
教学过程
设计
(包括讲授知识、演示内容及案例、提问及学生演示内容)
任务一、数组的定义、运算
前言:(用时10分钟)
前4章介绍的数据结构共同特点:
(1)都属于线性数据结构;
(2)每种数据结构中的数据元素,都作为原子数据,不再进行分解;
本章讨论的两种数据结构:数组和广义表,其共同特点是:
1)从逻辑结构上看它们,可看成是线性结构的一种扩展;
2)数据元素本身也是一个数据结构;
一、数组的概念(用时10分钟)
数组是由一组个数固定,类型相同的数据元素组成阵列。
以二维数组为例:二维数组中的每个元素都受两个线性关系的约束
安徽新华电脑专修学院课堂教学教案
(电脑应用课使用)
教
学
过
程
设
计
(续表)
即行关系和列关系,在每个关系中,每个元素aij都有且仅有一个直接前趋,都有且仅有一个直接后继。
在行关系中
aij直接前趋是 aij-1
aij直接后继是 aij+1
在列关系中
aij直接前趋是 ai-1j
aij直接后继是 ai+1j
二维数组也可看作这样的线性表:其每一个数据元素也是一个线性表
A=(a0 ,a1 ,a2 ,a3 , a4 ,……,ap )
其中每一个数据元素 aj 是一个列向量的线性表
aj=(a0j , a1j ,a2j , a3j ,……,am-1j )
或 ai 是一个行向量的线性表
ai=(ai0 ,ai1 ,ai2 , ai3 ,……,ain-1 )
二、数组的基本操作(用时10分钟)
读元素操作
写元素操作
操作方法根据其存储结构决定
任务二、数组的顺序存贮结构(用时20分钟)
一维数组在内存中的存放很简单,只要顺序存放在连续的内存单元即可。
二维数组,如何用顺序结构表示?内存地址是一维的,而数组是二维的,要将二维数组挤入一维的地址中,有两个策略:
以行为主序(C语言使用)
以列为主序
数组元素存储地址的计算:
假设二维数组A每个元素占用s 个存储单元, Loc(aij )为元素aij 的存储地址,Loc(a00 ) 是a00存储位置, 也是二维数组A的基址。
若以行序为主序的方式存储二维数组,则元素aij 的存储位置可由下式确定: Loc(aij ) = Loc(a00 ) +(n´ i+j ) ´s
教
学
过
程
设
计
(续表)
若以列序为主序的方式存储二维数组,则元素aij 的存储位置可由下式确定: Loc(aij ) = Loc(a00) +(m´ j+i ) ´s
一般在程序设计过程中,一维数组和二维数组使用较普遍,超过二维以上的多维数组使用相对较少,对于高维数组的顺序存储方法,可以将二维的情形加以推广便能够得到。
复****思考题
作业
上机任务
案例分析:
以二维数组形式为例
参考文献
《数据结构》(C语言版) 扬振生中国科学技术大学出版社
课后记
(或归纳小结)
本小节主要介绍数组的定义,存储(以行为序或以列为序)等等
课程名称
数据结构
教学对象
新华软工
教材
数据结构(C语言)
授课内容
第五章数组
课时
2
教学目的
与要求
了解数组的定义、运算;掌握数组的存储;掌握特殊矩阵的概念和存储等
重点、难点
重点:数组的存储
难点:特殊矩阵的存储
课型
电脑+理论
教学方法
投影、讨论、板书
教学过程
设计
(包括讲授知识、演示内容及案例、提问及学生演示内容)
课题引入(用时10分钟)
任务三、矩阵的压缩存储
(用时20分钟)
矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。一个m行n列的矩阵是一平面阵列,有m´n个元素。可以对矩阵作加、减、乘等运算。
只有少数程序设计语言提供了矩阵运算。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素,因而能较为容易地实现矩阵的各种运算。
应用中常遇到一些阶数很高的矩阵,矩阵中有许多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。
安徽新华电脑专修学院课堂教学教案
(电脑应用课使用)
教
学
过
程
设
计
(续表)
例如,设一个1000 ´ 1000的矩阵中有800个非零元素,若用二维数组存储需要1