数据结构第06章-数组和广义表课件.ppt

1、数据结构（数据结构（C+版）版）n 第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计第6章 数组和广义表 6.1 数组 6.2 矩阵类 6.3 特殊矩阵的压缩存储 6.4 稀疏矩阵 6.5 广义表数据结构（C+版）叶核亚6.1 数组l6.1.1 一维数组l6.1.2 多维数组数据结构（C+版）叶核亚6.1.1 一维数组数组分配内存空间的方式有2种静态数组：声明时给出数组元素个数。当程序开始运行时，数组即获得系统分配的一块地址连续的内存空间。静态数组所占用的内存空间由系统自动管理。

2、动态数组：声明时不指定数组长度。当程序运行中需要使用数组时，向系统申请数组的存储单元空间，并给出数组长度。当数组使用完之后，需要向系统归还所占用的内存空间。数据结构（C+版）叶核亚6.1.2 多维数组1.多维数组的概念2.多维数组的遍历行优先次序a1,1，a1,2，a1,n，a2,1，a2,2，a2,n，am,1，am,2，am,n列优先次序a1,1，a2,1，am,1，a1,2，a2,2，am,2，a1,n，a2,n，am,nnmmmnnnmaaaaaaaaa,2,1,22,21,2,12,11,1A数据结构（C+版）叶核亚3多维数组的顺序存储结构将二维数组Amn按行优先次序存储在内存以后，

3、元素ai,j的地址计算函数为：按列优先次序存储数组时，元素ai,j的地址计算函数为：)1()1()(Loc)(Loc1,1,jniaaji)1()1()(Loc)(Loc1,1,imjaaji数据结构（C+版）叶核亚4.多维数组的随机存储机制(a)二维数组的逻辑结构(c)列优先顺序存储结构(b)行优先顺序存储结构第1行第i行a11a12a21a22a1na2nam1am2amn第1行第2行第m行第1列第2列第n列a11ai1ai,j-1a1nainam1aijamn第m行下标0n1(i1)nj1(i1)nj(i1)n(i1)nn1(m1)n(m1)nn1第1列第j列a11a1jai-1,jam

4、1amja1naijamn第n列下标0m1(j1)mi1(j1)mi(j1)m(j1)mm1(n1)m(n1)mm1数据结构（C+版）叶核亚6.2 矩阵类 l6.2.1 矩阵类的声明l6.2.2 矩阵类的操作 数据结构（C+版）叶核亚6.2.1 矩阵类的声明矩阵类Matrix1的成员变量table是一个元素类型为整型的一维数组。声明如下：#include class Matrix1 /顺序存储结构的矩阵类private:int n;/矩阵的阶数 int*table;/一维数组指针public:Matrix1(int n=0);/构造空矩阵对象 Matrix1(int mat1,int n);/

5、以一维数组构造矩阵对象 Matrix1(Matrix1&mat1);/以已知对象构造矩阵对象 Matrix1();/析构函数 int get(int i,int j);/获得矩阵的数据元素 bool set(int i,int j,int k);/设置矩阵的数据元素数据结构（C+版）叶核亚6.2.2 矩阵类的操作 1.创建矩阵对象矩阵类Matrix1声明了3种构造函数，分别对应不同的参数。Matrix1类的构造函数实现如下：Matrix1:Matrix1(int n)/构造空矩阵对象，数据元素全为0 this-n=n;this-table=NULL;if(n0)table=new intn*n

6、;/为矩阵分配n*n个存储单元 for(int i=0;in*n;i+)tablei=0;Matrix1:Matrix1(int mat1,int n)/以一维数组构造矩阵对象数据结构（C+版）叶核亚例6-1 矩阵相加运算#include Matrix1.h /矩阵类void main()int m1=1,2,3,4;/一维数组 int m222=1,0,0,1;/二维数组 Matrix1 mat1(m1,2);/以一维数组构造矩阵对象 Matrix1 mat2(&m200,2);/二维数组转换为一维数组构造矩阵对象 Matrix1 mat3(mat1);/以已知对象构造矩阵对象 coutma

7、t3;/输出流运算符重载 Matrix1 mat4(2);/构造空矩阵对象，数据元素全为0 mat4=mat2;/矩阵赋值运算 coutmat4;数据结构（C+版）叶核亚6.3 特殊矩阵的压缩存储 a11，a21，a22，am1，am2，amn mnmmnmaaaaaaA21222111000nijjiiaaij1),1(2)1()(Loc)(Loc11数据结构（C+版）叶核亚6.4 稀疏矩阵l6.4.1 稀疏矩阵的三元组线性表l6.4.2 三元组顺序表l6.4.3 三元组链表数据结构（C+版）叶核亚6.4.1 稀疏矩阵的三元组线性表1.稀疏矩阵的非零元素由三部分组成：行下标、列下标和矩阵元素

8、值，这称为稀疏矩阵的三元组。2.用稀疏矩阵的三元组序列表示为：1,1,1,3,1,2,3,3,7,4,3,8,4,4,9。9800070200000001A数据结构（C+版）叶核亚6.4.2 三元组顺序表表6-1 稀疏矩阵的三元组顺序表数组下标行下标列下标数据元素值01111312233734384449数据结构（C+版）叶核亚6.4.3 三元组链表1行的单链表示行指针数组table2column列号1117383941324行号头指针next指向后继结点的指针data值数据结构（C+版）叶核亚2十字链表11123173394484312341324列指针数组行指针数组数据结构（C+版）叶核亚

9、6.5 广义表l6.5.1 广义表的概念l6.5.2 广义表的存储结构数据结构（C+版）叶核亚6.5.1 广义表的概念1.广义表的定义广义表（general list）是n（n0）个数据元素a1,a2,an组成的有限序列，记为：List=(a1,a2,an)L(a，b)/线性表，长度为2T(c，L)(c，(a，b)/L为T的子表，T的长度为2G(d，L，T)(d，(a，b)，(c，(a，b)/L、T为G的子表，G的长度为3S()/空表，长度为0S1(S)()/非空表，元素是一个空表，长度为1Z(e，Z)(e，(e，(e，()/递归表，Z的长度为2数据结构（C+版）叶核亚2广义表的特性（1）广义表是一种线性结构（2）广义表也是一种多层次的结构（3）广义表可为其他广义表共享（4）广义表可以是一个递归表LbaTc(a)线性结构的线性表L(a,b)dZeG(b)树结构的纯表T(c,L(a,b)(c)图结构的再入表G(d,L(a,b),T(c,L(a,b)LbaLaTcb(d)图结构的递归表Z(e,Z)数据结构（C+版）叶核亚6.5.2 广义表的存储结构1广义表的单链表示数据结构（C+版）叶核亚2广义表的双链表示数据结构（C+版）叶核亚