第5章 数组和广义表

数据结构(Java)(第三版) 课件

数据结构(Java版)

数据结构(Java)(第三版) 课件

《数据结构(Java版)》 第0章 Java程序设计基础 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 排序 第9章 查找 第10章 综合应用设计

数据结构(Java)(第三版) 课件

第5章 数组和广义表 5.1 数组 5.2 特殊矩阵的压缩存储 5.3 广义表

数据结构(Java)(第三版) 课件

本章学习目标 目的：了解包含子结构的线性结构。 要求：理解多维数组的存储结构，了解 特殊矩阵压缩存储，了解广义表。 重点： 难点：广义表的表示和实现。

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

5.1 数组5.1.1 一维数组5.1.2 多维数组

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

5.1.1 一维数组

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

数组(array)是一种数据结构，数组元素具有相同的数 据类型。数组的内存分配有静态和动态两种方式。静态数组在声明 时给出数组元素个数；动态数组在声明时不指定数组长度， 当程序运行中需要使用数组时，向系统申请数组的存储单 元空间，并给出数组长度。

在Java中，数组元素既可以简单数据类型，也可以是引用 类型。而且Java中的数组都是动态数组。静态数组和动态数组都是定长的，当数组容量不够时，都 不能就地扩容。因此，数组只能进行赋值、取值两种随机 存取操作，不能进行插入、删除操作。 一维数组的逻辑结构是线性表，多维数组是线性表的扩展。 一维数组采用顺序存储结构，数组元素的存储地址为 Loc(ai)= Loc(a0)+i ×c

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

5.1.2

多维数组

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

1. 多维数组的逻辑结构

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

2. 多维数组的遍历二维数组进行遍历的操作有两种次序：行主序和列主序。

(1)行主序 以行序为主序，按行递增访问数组元素，访问完第i行 的所有元素之后再访问第i+1行的元素，同一行上按列递增 访问数组元素。(2)列主序 以列序为主序，按列递增访问数组元素，访问完第j列 的所有元素之后再访问第j+1行的元素，同一列上按列递增 访问数组元素。

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

3. 多维数组的存储结构(1)静态多维数组的顺序存储结构

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

(2)动态多维数组的存储结构

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

【例】 矩阵类。

Am n

a 00 a1 0 … a m 1, 0

a 01 a1 1 … a m 1,1

a 0 , n 1 … a1, n 1 … … … a m 1, n

1 …

矩阵运算主要有矩阵加、矩阵减、矩阵乘、矩阵转 置等。矩阵加(C=A+B)定义为

c ij a ij bij

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

public class Matrix{ private int value[][]; //存储矩阵元素的二维数组 public Matrix(int m, int n) { //构造m行n列的空矩阵 this.value=new int[m][n]; } public Matrix(int n) { //构造n行n列的空矩阵 this(n,n); } public Matrix(){ this(10,10); } public Matrix(int mat[][]) { //构造矩阵，由数组mat提供矩阵元素 this(mat.length,mat[0].length); for (int i=0; i<mat.length; i++) for (int j=0; j<mat[i].length; j++) this.value[i][j] = mat[i][j]; }

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

public int get(int i, int j) { //获得矩阵第i行第j列的元素，O(1) return value[i][j]; } public void set(int i, int j, int k) { //设置矩阵第i行第j列的元素，O(1) value[i][j]=k; } public String toString() { //行主序遍历，访问矩阵全部元素 String str=""; for (int i=0; i<value.length; i++) { for (int j=0; j<value[i].length; j++) str += " "+value[i][j]; str += "\n"; } return str; }

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

public void add(Matrix b) //this和b两个矩阵相加，改变当前矩阵 { for (int i=0; i<this.value.length; i++) for (int j=0; j<this.value[i].length; j++) this.value[i][j] += b.value[i][j]; } public Matrix transpose() //返回转置矩阵 { Matrix trans = new Matrix(value[0].length, value.length); for (int i=0; i<this.value.length; i++) for (int j=0; j<this.value[i].length; j++) trans.value[j][i]=this.value[i][j]; return trans; } }

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

class Matrix_ex{ public static void main(String args[]){ int m1[][]={{1,2,3}, {4,5,6}}; Matrix a=new Matrix(m1); int m2[][]={{1,0,0}, {0,1,0}}; Matrix b=new Matrix(m2); System.out.print("Matrix a:\n"+a.toString()); System.out.print("Matrix b:\n"+b.toString()); a.add(b); System.out.print("Matrix a:\n"+a.toString()); System.out.println(“a的转置矩阵：\n“ +a.transpose().toString()); } }

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

程序运行结果如下：

Matrix a: 1 2 3 4 5 6 Matrix b: 1 0 0 0 1 0 Matrix a: 2 2 3 4 6 6 a的转置矩阵： 2 4 2 6 3 6

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

5.2 特殊矩阵的压缩存储5.2.1 对称(三角)矩阵的存储5.2.2 稀疏矩阵的压缩存储

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

5.2.1 对称(三角)矩阵的存储

数据结构(Java)(第三版) 课件

《数据结构(Java版)》第5章 数组和广义表

1. 三角矩阵a 设 A n n 是一个n阶下三角矩阵，当i<j时， ij 0 。

An n

a 0 ,0 a1,0 … a n 1,0

0 a1,1 … a n 1,1

…

… 0 … … … a n 1, n 1 0

矩阵中非零元素总数为：

( i 1) i 0

n 1

n( n 1) 2

本文来源：https://www.bwwdw.com/article/gnpe.html