《数据结构（C语言描述）pp5教学课件.ppt》由会员分享，可在线阅读，更多相关《数据结构（C语言描述）pp5教学课件.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构（C语言描述）pp5教学课件第5章 数组和广义表5.6 广义表的抽象数据类型广义表的抽象数据类型5.4 矩阵的压缩存储矩阵的压缩存储5.8 广义表的应用广义表的应用5.3 数组的存储结构数组的存储结构5.7 广义表的存储结构与操作广义表的存储结构与操作5.1 数组的定义数组的定义5.2 数组的抽象数据类型数组的抽象数据类型5.5 广义表的定义广义表的定义主要内容主要内容5.1 数组的定义数组的定义n定义n数组是由n(n1)个具有相同数据类型的数据元素a0,a1,a2,an-1组成的有限序列。n特点n数组中的数据元素的数据类型相同；n数组是一种随机存取结构，只要给定一组下标，就可以访问与
2、其对应的数组元素；n数组中数据元素的个数是固定的。5.1 数组的定义数组的定义n例子：二维数组的不同表示(a)矩阵形式的表示(b)列向量的一维数组(c)行向量的一维数组 5.2 数组的抽象数据类型数组的抽象数据类型ADT ArrayDataset：D=|i=1,2,n,n=0称为数组的维数 Relationset：OperationSet：lArrayInit(&A,n)初始条件：无 输入参数：无 实现功能：创建一个n维数组A，并返回lArrayDestroy(&A)初始条件：A是n维数组 输入参数：无 实现功能：销毁数组AlAssign(A,e,i)初始条件：A是n维数组，e是元素变量，i为
3、下标；输入参数：无 实现功能：将e的值赋给数组A中下标为i的元素，并返回OKlValue(A,i)初始条件：A是n维数组，i为下标 输入参数：无 实现功能：取出数组A中下标为i的数组元素ADT Array5.3 数组的存储结构数组的存储结构n一维数组的存储结构n一维数组是采用内存中一段连续的存储单元进行存储 n例如：一维数组an=a0,a1,an-1 一维数组任意数据元素ai的存储单元地址 Loc(ai)=Loc(a0)+i*k (0 i n)a0a1an-15.3 数组的存储结构数组的存储结构n二维数组的存储结构 二维数组有以列序为主序和以行序为主序的两种存储结构n例如：一个二维数组am-1
4、,n-1 a0,0a0,1a0,n-1a1,0a1,1a1,n-1am-1,0am-1,1am-1,n-15.3 数组的存储结构数组的存储结构n以行序为主序以行序为主序 a00a01.a0,n-1a10a11.a1,n-1aijam-1,0am-1,1am-1,n-1Loc(a00)第0行第1行Loc(ai j)第m-1行二维数组的任一数据元素ai,j的存储单元地址:Loc(aij)=Loc(a00)+(i*n+j)*k (0 i m,0 j n)5.3 数组的存储结构数组的存储结构n以列序为主序以列序为主序 Loc(a00)第0列第1列Loc(ai j)第m-1列a00a10.am-1,0a
5、01a11.am-1,1aija0,n-1a1,n-1am-1,n-1列序为主的存储方式，则任一数据元素aij的存储单元地址 Loc(aij)=Loc(a00)+(j*m+i)*k (0 i m,0 j n)5.3 数组的存储结构数组的存储结构n推广到一般情况，n维数组中数据元素的存储地址的映射关系 其中cn=k,ci-1=bici,1 i n,上式n维数组的映射函数。数组元素的存储位置是其下标的线性函数。一旦确定了数组各维数的长度，ci就是常数。5.4矩阵的压缩存储矩阵的压缩存储n特殊矩阵 相同元素或零元素的分布具有某种规律的矩阵 n稀疏矩阵n 相同元素或零元素的分布无规律，但存在大量的零值
6、元素的矩阵 n压缩存储 对特殊矩阵的存储采取相同值元素只存储一次，对零值元素不分配存储空间的策略，这种存储方法称为压缩存储 5.4矩阵的压缩存储矩阵的压缩存储5.4.1 特殊矩阵特殊矩阵5.4.2稀疏矩阵稀疏矩阵5.4矩阵的压缩存储矩阵的压缩存储5.4.1 特殊矩阵特殊矩阵5.4矩阵的压缩存储矩阵的压缩存储n对对称矩称矩阵阵 若一个n阶矩阵A矩阵满足以下条件：aij=aji (1=i,j=j)，k=i*(i-1)/2+j-1 n矩阵元素aij位于矩阵A的上三角中时(i=0;eiAtomSet或eiGList,AtomSet为某个数据对象Relationset：R=|ei-1,eiD,2inOp
7、erationSet：ADT GList 5.6 广义表的抽象数据类型广义表的抽象数据类型lOperationSet：(1)InitGlist(&L);初始条件：无；输入参数：无；实现功能：创建空的广义表L(2)CreateGList(&L);初始条件：无；输入参数：无；实现功能：创建广义表L(3)DestroyGlist(&L);初始条件：广义表L存在；输入参数：无；实现功能：销毁广义表L(4)CopyGlist(&T,L);初始条件：广义表L存在；输入参数：无；实现功能:由广义表L复制得到广义表T(5)GListLength(L);初始条件：广义表L存在；输入参数：无；实现功能：求广义表L
8、的长度，即元素个数(6)GListDepth(L);初始条件：广义表L存在；输入参数：无；实现功能：求广义表L的深度 5.6 广义表的抽象数据类型广义表的抽象数据类型(7)GlistEmpty(L);初始条件：广义表L存在；输入参数：无；实现功能：判断广义表L是否为空(8)GetHead(L);初始条件：广义表L存在；输入参数：无；实现功能：取广义表L的头(9)GetTail(L);初始条件：广义表L存在；输入参数：无；实现功能：取广义表L的尾(10)InsertFirst_GL(&L,e);初始条件：广义表L存在；输入参数：无；实现功能：插入元素e作为广义表L的第一元素(11)DeleteF
9、irst_GL(&L,&e);初始条件：广义表L存在；输入参数：无；实现功能：删除广义表L的第一元素,并用e返回其值(12)Traverse_GL(L,Visit();初始条件：广义表L存在；输入参数：无；实现功能：遍历广义表L,用函数Visit处理每个元素5.7 广义表的存储结构与操作广义表的存储结构与操作5.7.1 头尾表示法及实现头尾表示法及实现5.7.2孩子兄弟表示法及实现孩子兄弟表示法及实现5.7 广义表的存储结构与操作广义表的存储结构与操作 任意非空的广义表，可分解为表头和表尾，反之，一对确定的表头和表尾可唯一确定一个广义表。头尾表示法中的需要两种结构的结点：一种是表结点，用以表示
10、子表；一种是原子结点，用以表示单元素。在表结点中有三个域组成：标志域、指向表头的指针域和指向表尾的指针域；而原子结点需要两个域：标志域和值域。标志域是用来区分这两种结点的。如图5-12所示。图5-12 头尾表示法的结点形式5.7.1 头尾表示法及实现头尾表示法及实现5.7 广义表的存储结构与操作广义表的存储结构与操作 头头尾表示法的形式定尾表示法的形式定义说义说明如下：明如下：Typedef struct Nodeint tag;/*公共部分，取值为0或1*/union /*原子结点和表结点的联合部分*/struct Node*hp,*tp;Mathtype data;/*AtomTpye指原
11、子结点值域的数据类型，由用户定义*/Node;其中，tag为标志位，1表示本结点为表结点，0表示本结点为原子结点；hp存放子表的第一个元素对应的链接点的地址；tp存放同一层的下一个元素所在的链接点的地址，当本元素是所在层的最后一个元素时，tp的值为NULL。5.7.1 头尾表示法及实现头尾表示法及实现 5.7 广义表的存储结构与操作广义表的存储结构与操作n例5.6 对于5.6节例5.5所列举的广义表A,B,C,D,E,F，采用头尾表示法的存储方式，其存储结构如图所示。A=NULL图5-13 广义表存储结构示例(头尾表示法)5.7.1 头尾表示法及实现头尾表示法及实现 5.7 广义表的存储结构与
12、操作广义表的存储结构与操作n例5.7基于头尾表示法的存储结构，实现广义表的抽象数据类型定义中的GListLength(L)操作，用伪码表述其基本思想即可。nint GListLength(L)/*求广义表L的长度*/Node *p;int count;if(L=NULL)return 0;/*L是一个空表,返回0*/p=L-tp;count=1;while(p!=NULL)p=p-tp;count+;return count;/*L不是空表，返回表的长度count*/5.7.1 头尾表示法及实现头尾表示法及实现5.7 广义表的存储结构与操作广义表的存储结构与操作n在孩子兄弟表示法中，原子结点和
13、表结点用相似的两种结点来表示。如图图5-14 孩子兄弟表示法的结点形式 其中表结点是有孩子的结点，cp和bp分别是指向第一个孩子和一个兄弟的指针域；原子结点是无孩子结点，data和bp分别是值域和指向兄弟的指针域。tag是标志域，用来区分这两类结点，如tag为1，则表示该结点为表结点即有孩子的结点；为0，则表示该结点为原子结点即无孩子结点。5.7.2孩子兄弟表示法及实现孩子兄弟表示法及实现 5.7 广义表的存储结构与操作广义表的存储结构与操作n孩子兄弟表示法形式定义说明如下：Typedef enumAtom,ListElemTag;/*Atom=0:原子，List=1:子表*/Typedef
14、struct NodeElemTag tag;/*公共部分，用于区分原子结点和表结点*/union /*原子结点和表结点的联合部分*/struct Node*cp;/*表结点的孩子指针*/Mathtype data;/*原子结点的值域*/struct Node*bp;/*表结点的兄弟指针*/Node;5.7.2孩子兄弟表示法及实现孩子兄弟表示法及实现 5.7 广义表的存储结构与操作广义表的存储结构与操作n例5.8 对于5.6节例5.5所列举的广义表A,B,C,D,E,F，采用孩子兄弟表示法的存储方式，其存储结构如图所示。图5-15 广义表存储结构示例(孩子兄弟表示法)5.7.2孩子兄弟表示法及
15、实现孩子兄弟表示法及实现5.8广义表的应用广义表的应用 现实生活中，无论是政府、企业、家族或高校，其成员都可以组织成为一定的并列关系或层次关系，处理这类组织关系时，可以用广义表作为其抽象模型。比如一个政府部门需要设置从最高领导到职员的管理层次关系，如图5-16所示。图 5-16 多级管理示意图 5.8广义表的应用广义表的应用n由图可知多级管理机制的构成也是递归的，同一级别的人员之间是线性关系，但么一个级别的人员的数量是不确定的，很难用普通的线性表来表示，可采用广义表的形式加以抽象，即：(局长，(副局长1，副局长2，副局长3，)(副局长1，(科长1，科长2，科长3，)(科长1，(科员1，科员2，
16、)每个职工的信息包括职称/职务和姓名。则整个多级管理机制的存储、查询、统计等可以用广义表的相关操作来实现。5.8广义表的应用广义表的应用n下面给出广义表的创建、查询算法的实现。下面给出广义表的创建、查询算法的实现。算法算法5.3：/*建立广义表的存储结构*/void CreateGList(struct Node L)char ch;scanf(%c,&ch);if(ch=#)L=NULL else if(ch=()L=malloc(sizeof(struct Node);L-tag=1;creatGList(&(L-hp);else L=malloc(sizeof(struct Node);
17、L-tag=0;L-data=ch;scanf(%c,&ch);if(*gl=NULL);else if(ch=,)creatGList(&(L-tp);else if(ch=)|(ch=;)(L-tp=NULL;return;算法算法5.4：/*在广义表在广义表L中查询姓名为中查询姓名为name的人员信息，并输的人员信息，并输出出*/QueryInfo(Glist L,String name)If(L=NULL)return;If(L-tag=0)If(L-data=name)printf(“姓名为姓名为name的信息为：的信息为：”+L-data);int flag=1;Return;No
18、de*p=L;While(p)L=p-hp;QueryInfo(L,name);p=p-tp;If(flag！=1)printf(“对不起，没有该人的信息！对不起，没有该人的信息！”);5.8广义表的应用广义表的应用nint main()/*广义表的创建、查询主程序*/struct GNode L;string name;printf(输入一个广义表，以右括号结束);creatGList(&L);printf(输出广义表：);printf(输入姓名name=);QueryInfo(L,name);return 0;本章小结本章小结n数组是由若干个具有相同数据类型的数据元素组成的序列。每个元素在数组中的位置是由它的下标决定的。n特殊矩阵的某些相同元素或零元素的分布具有一定的规律。为节省存储空间，对这些相同元素只分配一个存储单元，零元素不分配存储单元。n广义表是线性表的推广，也是由若干元素组成的有限序列，但线性表中的元素可以是另一个广义表，或其自身。广义表通常采用链式的存储结构，表中的每个元素可以用一个结点来表示。根据结点形式的不同，广义表的链式存储结构可分为头尾表示法和孩子兄弟表示法两种存储方式。