数组和广义表.

数组和广义表.Tag内容描述：<p>1、,第5章 数组和广义表,5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储 5.3.1 三角矩阵 5.3.2 带状矩阵 5.3.3 稀疏矩阵 5.4 广义表,返回主目录,5.1 数组的定义和运算,数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组可以看成是线性表的线性表。例如：,返回主目录,我们可以把二维数组看成一个线性表： A=( 1 2 j n)，其中j（1j n）本身也是一个线性表，称为列向量。,矩阵Amn看成n个列向量的线性表,即j=(a1j,a2j, ,amj),返回主目录,我们还可以将数组Amn看成另外一个线性表: B=(1，,2,。</p><p>2、第5章 数组和广义表,5.1 数组的定义与运算 5.2 数组的顺序存储结构 5.3 矩阵的压缩存储 5.4 广义表 习题,5.1 数组的定义与运算,数组定义：类似于线性表，一个两维数组的逻辑结构可形式地表示为 2_Array=(D,R) 其中D=aij|i=0,1,m-1,j=0,1,n-1，aij是同类型数据元素的集合。 R=ROW,COL是数据元素上关系的集合。 ROW=|0im-1,0jn-2每一行上的列关系。 COL=|0im-2,0jn-1每一个列上的行关系。 行列关系跟线性表已经大不相同了,见图5.1所示。,a01 a02 a0n-1 a11 a12 a1n-1 am-11 am-12 am-1n-1 图5.1 二维数组元素关系 二维数组中的每一个元素aij。</p><p>3、第五章 数组和广义表重点难点理解数组和广义表两种数据结构的特点，并掌握数组在以行为主的存储表示中的地址计算方法；掌握特殊矩阵的存储压缩表示方法；了解广义表的两种链式存储结构。典型例题 1. 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量B0.3n-3中，使得Bk=aij,求：(1)用i , j 表示k的下标变换公式。(2)用 k 表示 i,j 的下标变换公式。【解】(1)要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为：(i*3。</p><p>4、5.1 数组的类型定义,5.3 稀疏矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,5.5 广义表的表示方法,5.6 广义表操作的递归函数,5.1 数组的类型定义,ADT Array 数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,n 数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array,基本操作:,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,基本操作：,InitArray(&A, n, bound1, ., boundn),DestroyArray(&A),Val。</p><p>5、1,第四章 数组、串与广义表,一维数组与多维数组 特殊矩阵 稀疏矩阵 字符串 广义表,2,一维数组,定义 数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标（index）和值（value）组成。 一维数组的示例 在高级语言中，一维数组只能按元素的下标直接存取数组元素的值。,3,一维数组的定义和初始化,#include main ( ) int a3 = 3, 5, 7 , *elem, i; /静态数组 for (i = 0; i elemi; while (elem) cout *elem endl; elem+; ,4,多维数组,多维数组是一维数组的推广。 多维数组的特点是每一个数据元素可以有多个直接前驱。</p><p>6、第四章 多维数组及广义表,前几章介绍的数据结构都是线性结构，数据元素都属于原子类型，其值不分解使用。 本章讨论的多维数组和广义表是线性结构的推广，从整体上看它们是多个元素组成的线性表，而从局部上看线性表中的数据元素不一定是原子类型，即数据元素又可以具有某种数据结构。,主要内容：,41 多维数组 多维数组的逻辑结构特征及存储方式 42 矩阵的压缩存储 特殊矩阵和稀疏矩阵的压缩存储 43 广义表 广义表的定义和运算,41 多维数组,一、多维数组的逻辑结构特征 数组中的元素具有相同类型，且下标一般具有固定的上界和下界。 数组可。</p><p>7、第五章 数组和广义表,5.1 数组的类型定义,5.3 稀疏矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,5.5 广义表的表示方法,5.6 广义表操作的递归函数,5.1 数组的类型定义,ADT Array 数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,n 数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array,基本操作:,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW = | 0ib1-1, 0| 0ib1-1, 0 jb2-1,基本操作：,InitArray(&A, n, bound1, ., boundn),DestroyArray。</p><p>8、第五章 数组和广义表,一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作 二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。 n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。 因此，多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。,5.1 数。</p><p>9、1,第四章 串,4.1 串类型的定义,4.2 串的表示和实现,4.3 串的模式匹配算法,2,4.1 串类型的定义 一、串的基本概念 1.串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,3,串与线性表 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。,4,基本操作：,StrAssign ( &T, chars ),StrCopy ( &T, S ),DestroyString ( &S ),StrEmpty ( S ),St。</p><p>10、 数据结构 实验报告 实验序号 7 实验项目名称 数组和广义表 学 号 姓 名 专业班级 实验地点 指导教师 实验时间 一 实验目的及要求 本次实验目的是通过上机练习 熟悉和掌握课堂所讲授的基本知识点 要求上机以前要认真。</p>