数组串和广义表学习教案.pptx

《数组串和广义表学习教案.pptx》由会员分享，可在线阅读，更多相关《数组串和广义表学习教案.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数组串和广义数组串和广义(gungy)表表第一页，共59页。4.1 数组数组 数组（array）表示n（n1）个具有相同数据类型的数据元素(yun s)的有序集合。第2页/共59页第二页，共59页。二维数组二维数组n n数组中数据元素由一个数据值和一个（组）下标确定。下标是数组中元素相互区分的标识。使用一个下标区分其中(qzhng)元素的数组称为一维数组。使用两个以上下标的数组称为多维数组。常用的多维数组是二维数组，通常称为矩阵。n nA3*4的阵列形式表示：第3页/共59页第三页，共59页。矩阵矩阵(j zhn)的顺序表示与实现的顺序表示与实现n n行序优先(yuxin)存储：p列序

2、优先列序优先(yuxin)存储：存储：Loc(aij)=Loc(a00)+（i*n+j）*length Loc(aij)=Loc(a00)+（j*m+i）*length第4页/共59页第四页，共59页。特殊矩阵压缩特殊矩阵压缩(y su)存储存储 1.对称(duchn)矩阵n阶方阵，沿主对角线对称(duchn)位置上的元素相等，即aij=aji。主对角线：由元素aii组成的数列 如右图的对称矩阵如右图的对称矩阵(j zhn)按行序存储下三按行序存储下三角的元素，映射到一维数组中去，其对应的一角的元素，映射到一维数组中去，其对应的一维数组下标如下图所示：维数组下标如下图所示：第5页/共59页第五

3、页，共59页。特殊矩阵特殊矩阵(j zhn)压缩存储压缩存储 1.对称矩阵(j zhn)2对称矩阵(j zhn)中任意元素与其对应的一维数组下标k的计算公式：第6页/共59页第六页，共59页。特殊矩阵压缩特殊矩阵压缩(y su)存储存储2 2.三角矩阵(j zhn)n阶方阵，沿主对角线以上的元素全为零。上三角矩阵(j zhn)、下三角矩阵(j zhn)如右图为下三角矩阵。如右图为下三角矩阵。按行序压缩存储下三角矩阵，映射到一维按行序压缩存储下三角矩阵，映射到一维数组中去，其对应数组中去，其对应(duyng)的一维数组的一维数组下标如下图所示：下标如下图所示：第7页/共59页第七页，共59页。特

4、殊矩阵特殊矩阵(j zhn)压缩存储压缩存储2 2.三角矩阵2按行序压缩存储下三角矩阵，元素下标(xi bio)（i，j）与对应的一维数组下标(xi bio)k映射公式为：k=(i+1)*i/2+j (i=j)第8页/共59页第八页，共59页。特殊矩阵特殊矩阵(j zhn)压缩存储压缩存储3 3.3.对角矩阵对角矩阵n n阶方阵，沿主对角线上下若干对角线上有非零元素阶方阵，沿主对角线上下若干对角线上有非零元素(yun s)(yun s)，其他全为零。，其他全为零。带宽：主对角线上下各带宽：主对角线上下各d d条对角线上有非零元，则共有条对角线上有非零元，则共有2d+12d+1条对角线有非零元，

5、称条对角线有非零元，称为带宽。为带宽。如右图为如右图为3对角矩阵。对角矩阵。按行序压缩按行序压缩(y su)存储存储3对角矩阵，映射到一维数对角矩阵，映射到一维数组中去，其对应的一维数组下标如下图所示：组中去，其对应的一维数组下标如下图所示：第9页/共59页第九页，共59页。特殊矩阵特殊矩阵(j zhn)压缩存储压缩存储3 3.对角矩阵2按行序压缩(y su)存储三对角矩阵，元素下标（i，j）与对应的一维数组下标k映射公式为：k=3*i-1+(j-i+1)=2*i+j 第10页/共59页第十页，共59页。稀疏矩阵稀疏矩阵(j zhn)压缩存储压缩存储 n n稀疏矩阵是指矩阵中的非零元很少，大部

6、分是零元素(yun s)，且非零元的分布没有规律。如下矩阵：第11页/共59页第十一页，共59页。稀疏矩阵稀疏矩阵(j zhn)压缩存储压缩存储1.三元组表表示法在存储稀疏(xsh)矩阵中的非零元时，为了描述一个非零元素，需要元素本身的值和行标、列标三方面的信息，这些信息的组合就称为三元组。第12页/共59页第十二页，共59页。1.三元组表表示法三元组表表示法2n n用用C C语言定义三元组表的结构类型语言定义三元组表的结构类型(lixng)(lixng)如下：如下：00 typedef int DataType;/*假设稀疏假设稀疏(xsh)矩阵的元素类型为整型矩阵的元素类型为整型 */01

7、#define MAXSIZE 100 /*非零元个数的最大值非零元个数的最大值 */02 typedef struct /*定义三元组结点类型定义三元组结点类型 */03 04 int row,col;/*非零元所在的行下标非零元所在的行下标,列下标列下标*/05 DataType value;/*非零元素值非零元素值 */06 Triple;07 typedef struct /*定义三元组表结构类型定义三元组表结构类型 SMatrix*/08 09 Triple dataMAXSIZE+1;/*非零元组成的三元组表非零元组成的三元组表 */10 int mu,nu,tu;/*稀疏稀疏(x

8、sh)矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数 */11 SMatrix;第13页/共59页第十三页，共59页。1.三元组表表示法三元组表表示法3（1 1）建立稀疏）建立稀疏(xsh)(xsh)矩阵的三元组表矩阵的三元组表1 1算法算法4-1 4-1 建立并输出稀疏建立并输出稀疏(xsh)(xsh)矩阵的三元组表矩阵的三元组表 00 SMatrix CreateSMatrix()/*00 SMatrix CreateSMatrix()/*创建稀疏创建稀疏(xsh)(xsh)矩阵矩阵M*/M*/01 01 02 SMatrix M;02 SMatrix M;0303 int i;

9、int i;0404 printf(n printf(n请输入矩阵的行数：请输入矩阵的行数：););0505 scanf(%d,&M.mu);scanf(%d,&M.mu);0606 printf(n printf(n请输入矩阵的列数：请输入矩阵的列数：););0707 scanf(%d,&M.nu);scanf(%d,&M.nu);0808 printf(n printf(n请输入矩阵的非零元素个数：请输入矩阵的非零元素个数：););0909 scanf(%d,&M.tu);scanf(%d,&M.tu);10 for(i=0;i M.tu;i+)10 for(i=0;i 0)08 09 k

10、=0;10 for(i=0;iM.nu;i+)/*M有有nu列，要扫描列，要扫描nu趟趟*/11 for(j=0;j0)10 11 for(j=0;jM.nu;j+)/*设设rowsize的初值全为的初值全为0*/12 rowsizej=0;13 for(i=0;iM.tu;i+)/*求求M中每一列非零元素个数中每一列非零元素个数*/14 15 j=M.datai.col;16 rowsizej=rowsizej+1;17 18 printf(nrowsize:);19 for(i=0;iM.nu;i+)/*打印输出打印输出rowsize变量变量*/20 printf(%d ,rowsizei

11、);21 printf(n);第19页/共59页第十九页，共59页。算法算法算法算法4-3 4-3 稀疏稀疏稀疏稀疏(xsh)(xsh)矩阵的快速转置算法矩阵的快速转置算法矩阵的快速转置算法矩阵的快速转置算法2 222 rowstart0=0;23 for(j=1;jM.nu;j+)/*求第求第j列中第一个非零元在列中第一个非零元在 T中的位置中的位置*/24 rowstartj=rowstartj-1+rowsizej-1;25 printf(nrowstart:);26 for(i=0;iM.nu;i+)/*打印输出打印输出rowstart变量变量(binling)*/27 printf(

12、%d ,rowstarti);28 printf(n);29 for(i=0;iM.tu;i+)30 31 j=M.datai.col;/*取得三元组的列值取得三元组的列值 */32 k=rowstartj;/*取得三元组在取得三元组在 T中的位置中的位置*/33 T.datak.row=M.datai.col;34 T.datak.col=M.datai.row;35 T.datak.value=M.datai.value;36 rowstartj=rowstartj+1;37 38 39 return T;40 第20页/共59页第二十页，共59页。稀疏矩阵稀疏矩阵(j zhn)压缩压缩存

13、储存储22.2.十字链表法十字链表法当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用三元组表来表示，当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用三元组表来表示，对此种类型矩阵，采用链式存储表示三元组的线性表更为合适。对此种类型矩阵，采用链式存储表示三元组的线性表更为合适。为了为了(wi le)(wi le)使用链表存储稀疏矩阵，需要分别建立非零元素结点、行使用链表存储稀疏矩阵，需要分别建立非零元素结点、行/列链表头结点列链表头结点和整个链表头结点。和整个链表头结点。第21页/共59页第二十一页，共59页。2.2.十字十字十字十字(sh z)(sh z)链表法链表法链表法

14、链表法2 2非零元素结点C语言定义如下：00 typedef int DataType;/*假设稀疏矩阵的元素类型(lixng)为整型*/01 struct node /*定义十字链表结点结构*/02 03 int row,col;/*非零元所在的行下标,列下标*/04 DataType value;/*非零元素值*/05 struct node*down;/*定义down域指向同一列中下一个非零元地址*/06 struct node*right;/*定义right域指向同一行中下一个非零元地址*/07 ;08 typedef struct node TripleNode;/*定义十字链表结点

15、类型(lixng)*/第22页/共59页第二十二页，共59页。2.2.十字十字十字十字(sh z)(sh z)链表法链表法链表法链表法3 3十字链表头结点C语言定义如下(rxi)：00 struct node1 /*定义十字链表结点结构*/01 02 int mu,nu,tu;/*稀疏矩阵的行数、列数和非零元个数*/03 TripleNode*head;/*定义head域指向行列表头结点向量*/04 ;05 typedef struct node1 Triple;/*定义十字链表类型*/建立稀疏矩阵的十字链表程序见节算法4-4第23页/共59页第二十三页，共59页。2.2.十字十字十字十字(s

16、h z)(sh z)链表法链表法链表法链表法4 4一个一个(y(y )十字链表实例：十字链表实例：第24页/共59页第二十四页，共59页。4.2 串串串及相关概念 串（string）：是由零个或多个字符组成的有限序列。S=a0a1a2an-1 (n 0)串名：大写字母S为串名 串值：引号引起来的字符序列 长度：n表示串值中的字符个数，称为长度 空串：当n=0时，称为空串 空格串：由一个或多个空格组成的串 子串与主串：串中任意(rny)连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。位置：字符在字符串中首次出现的位置 相等：两个串的长度相等且对应位置上的字符都一一相等 第25页

17、/共59页第二十五页，共59页。串的基本操作串的基本操作n n串的抽象数据类型定义串的抽象数据类型定义(dngy)(dngy)如下：如下：ADT String is数据对象：数据对象：D=ai|ai CharacterSet,i=0,1,2,n-1,n0 数据关系：数据关系：R=|ai-1,ai D,i=1,2,n-1基本操作：基本操作：（1）StrAssign(String T,String chars)把把chars赋为赋为T的值，的值，chars是字符串常量是字符串常量(chngling)。（2）StrCopy(String T,String S)将串将串S复制到串复制到串T中。中。（3

18、）StrEmpty(String S)判断串判断串S是否为空串，并返回是否为空串，并返回 TRUE或或FALSE的标志。的标志。（4）StrCompare(String S,String T)判断两个字符串是否相等，若判断两个字符串是否相等，若 ST，则返回值，则返回值 0；若；若S=T，则返回值，则返回值=0；若；若ST，则返回值，则返回值 0。（5）int StrLength(String S)返回字符串返回字符串 S的元素个数，称为串的长度。的元素个数，称为串的长度。ADT String第26页/共59页第二十六页，共59页。串的存储串的存储(cn ch)结构结构1.1.串的定长顺序存储

19、结构串的定长顺序存储结构串的定长顺序存储表示，也称为静态存储分配的顺序串。它是用一组地址串的定长顺序存储表示，也称为静态存储分配的顺序串。它是用一组地址连续的存储单元存储串值的字符序列。所谓定长顺序存储结构，是直连续的存储单元存储串值的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义。接使用定长的字符数组来定义。用用C C语言定义串的结构类型如下：语言定义串的结构类型如下：typedef struct typedef struct char dataMAXSTRLEN;/*char dataMAXSTRLEN;/*定义定义datadata域为定长的顺序存储结构域为定长的顺序存储结

20、构*/*/int len;/*int len;/*定义定义lenlen域为串的长度域为串的长度*/*/String;/*String;/*定义串的结构类型为定义串的结构类型为String*/String*/串的定长顺序存储结构，优点是可以实现直接存取，定位方便，可以很方串的定长顺序存储结构，优点是可以实现直接存取，定位方便，可以很方便地求取子串；缺点便地求取子串；缺点(qudi(qudi n)n)是插入、删除、置换等操作困难，需要是插入、删除、置换等操作困难，需要移动大量的字符。移动大量的字符。第27页/共59页第二十七页，共59页。串的存储串的存储(cn ch)结构结构22.串的链式存储(c

21、n ch)结构串的单链表存储(cn ch)表示p结点大小为结点大小为4的块链存储的块链存储(cn ch)表示表示 最后结点不满可以用最后结点不满可以用“#”号补上；号补上；也可设置尾指针，方便联接操作，注意也可设置尾指针，方便联接操作，注意“#”号的处理。号的处理。第28页/共59页第二十八页，共59页。2 2、串的链式存储、串的链式存储、串的链式存储、串的链式存储(cn ch(cn ch)结构结构结构结构2 2重点：设定结点的大小，小则操作方便，但系统重点：设定结点的大小，小则操作方便，但系统 开销大；大节省开销大；大节省(jishng)(jishng)空间，操作不方便。空间，操作不方便。存

22、储密度存储密度 =串值所占存储空间串值所占存储空间实际分配的存储空间实际分配的存储空间第29页/共59页第二十九页，共59页。串的模式匹配串的模式匹配 串的模式匹配是一种重要的串运算，即子串定位操作，具体含义是：若主串串的模式匹配是一种重要的串运算，即子串定位操作，具体含义是：若主串 S S中存在和中存在和串串T T值相同的子串值相同的子串,则返回它在主串则返回它在主串S S中第一次出现首字母的位置中第一次出现首字母的位置;否则函数值为否则函数值为-1-1。1.BF1.BF算法算法基本基本(jbn)(jbn)思想：思想：假设主串假设主串S=s0s1s2sn-1S=s0s1s2sn-1，模式串，

23、模式串T=t0t1t2tm-1T=t0t1t2tm-1，n n为为S S的长度，的长度，mm为为T T的长度。从主串的长度。从主串S S的第一个字符开始和模式串的第一个字符开始和模式串T T的第一个字符进行比较，若相等，则继续比较两者的后续字的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串符；否则，从主串S S的第二个字符开始和模式的第二个字符开始和模式T T的第一个字符进行匹配。重复上述过程，若的第一个字符进行匹配。重复上述过程，若T T中的字符全部匹配完毕，则说明本趟匹配成功，返回本趟匹配中的字符全部匹配完毕，则说明本趟匹配成功，返回本趟匹配S S的起始位置；否则，匹配

24、的起始位置；否则，匹配失败，返回失败，返回-1-1。第30页/共59页第三十页，共59页。设主串设主串S=abacababaabcacadcaa,S=abacababaabcacadcaa,模式串模式串T=abaabcacT=abaabcac，BFBF算法匹配过程算法匹配过程(guchng)(guchng)如下图所示：如下图所示：第31页/共59页第三十一页，共59页。匹配匹配(p(p pi)pi)过程图（续）：过程图（续）：第32页/共59页第三十二页，共59页。1.BF算法算法(sun f)2 BF BF算法算法(sun f(sun f)虽然简单但是效率较低，时间复杂度为虽然简单但是效率较

25、低，时间复杂度为O(nm)O(nm)。造成。造成BFBF算法算法(sun f(sun f)效率低的原因是回溯，即在某趟匹效率低的原因是回溯，即在某趟匹配配i i个字符失败后，对于主串个字符失败后，对于主串S S要回溯到本趟匹配开始字符的下一要回溯到本趟匹配开始字符的下一个字符，模式串个字符，模式串T T要回溯到第一个字符，没有利用前要回溯到第一个字符，没有利用前i-1i-1个字符时个字符时的部分匹配结果。的部分匹配结果。BF BF算法算法(sun f(sun f)详见教材节的算法详见教材节的算法(sun f(sun f)4-5)4-5。第33页/共59页第三十三页，共59页。串的模式匹配串的模

26、式匹配22.KMP算法基本思想：该算法主要消除了主串指针(i指针)的回溯，利用已经得到的部分匹配结果将模式串右滑尽可能远的一段距离再继续比较，从而使算法效率有某种程度的提高，可使效率提高到O(n+m)的水平。KMP算法当某趟匹配不成功时，即SiTj时，主串S下标i不回溯，模式串T下标j也不回到0位置，而是回到一个恰当的位置，所以(suy)在主串下标i不回溯的前提下，下标j回到哪个位置是问题的关键。假设回到位置j，代表的意思是在主串S位置i之前（j-1）位必定与模式串T的前（j-1）位一一匹配。第34页/共59页第三十四页，共59页。设主串设主串S=abacababaabcacadcaa,S=a

27、bacababaabcacadcaa,模式串模式串T=abaabcacT=abaabcac，T T中中nextnext函数函数(hnsh)(hnsh)值如下表所示：值如下表所示：第35页/共59页第三十五页，共59页。KMPKMP算法算法(sun f(sun f)匹配过程如下图：匹配过程如下图：第36页/共59页第三十六页，共59页。2.KMP2.KMP算法算法算法算法(sun f(sun f)2)2n nnextnext函数的值完全只与模式串有关而与主串的值没有任何关系，因此函数的值完全只与模式串有关而与主串的值没有任何关系，因此(ync(ync)对于每个模式串来说都有一个唯一的对于每个模式

28、串来说都有一个唯一的nextnext数组值。数组值。n nnextnext数组的计算公式为：数组的计算公式为：pIndex_KMP函数中，求函数中，求next数组的数组的GetNext函数时间函数时间(shjin)复杂度为复杂度为O（m）接下来不回溯的匹配过程时间）接下来不回溯的匹配过程时间(shjin)复杂复杂度为度为O（n），所以，），所以，KMP算法总的时间算法总的时间(shjin)复杂度为复杂度为O（m+n）。）。KMP算法详见教材节的算法算法详见教材节的算法4-6。第37页/共59页第三十七页，共59页。4.3 广义(gungy)表广义表基本概念广义表基本概念1.1.广义表及相关概念

29、广义表及相关概念 广义表（广义表（Generalized ListsGeneralized Lists）是由）是由n n（n0n0）个数据元素组成的有序序列，一般）个数据元素组成的有序序列，一般(ybn)(ybn)记为：记为：Lists=Lists=（a0a0，a1a1，a2a2，an-1an-1）长度：广义表中包含数据元素（直接数据元素）个数称为该广义表的长度长度：广义表中包含数据元素（直接数据元素）个数称为该广义表的长度 深度：包含括弧的最大嵌套层数称为该广义表的深度深度：包含括弧的最大嵌套层数称为该广义表的深度 子表：广义表的递归性使得广义表中数据元素为子广义表子表：广义表的递归性使得广

30、义表中数据元素为子广义表 表头：广义表中第一个元素表头：广义表中第一个元素a0a0为广义表的表头为广义表的表头 表尾：广义表中除了表头之外的其它元素组成的广义表称为表尾表尾：广义表中除了表头之外的其它元素组成的广义表称为表尾 再入表：广义表再入表：广义表L L中存在某个原子或子表成员出现多次中存在某个原子或子表成员出现多次 纯表：广义表纯表：广义表L L中不存在相同数据元素出现两次以上中不存在相同数据元素出现两次以上 第38页/共59页第三十八页，共59页。1.1.广义广义广义广义(gu(gu ngy)ngy)表及相关概念表及相关概念表及相关概念表及相关概念2 2n n一些广义表的例子：一些广

31、义表的例子：n n A=A=（）。（）。A A是一个广义表，而且是一个空表，长度为是一个广义表，而且是一个空表，长度为0 0。表头。表头(bi(bi o tu)o tu)为空，为空，表尾为（）。表尾为（）。n n B=B=（）。注意（）。注意B B与与A A的区别，的区别，B B的长度为的长度为1 1，子表是（）。表头，子表是（）。表头(bi(bi o tu)heado tu)head（A A）=（），表尾（），表尾tailtail（B B）=（）。（）。n n C=C=（a a，b b，c c）。）。C C是一个长度为是一个长度为3 3的广义表，它的数据元素都是原子元素。表的广义表，它的数据

32、元素都是原子元素。表头头(bi(bi o tu)heado tu)head（C C）=a=a，表尾，表尾tailtail（C C）=（b b，c c）。此时，）。此时，C C是一个纯表。是一个纯表。n n D=D=（a a，（，（a a，b b），（），（a a，（，（a a，b b）。）。DD是一个长度为是一个长度为3 3，深度为，深度为3 3的广义表，的广义表，它的数据元素有原子元素，也有广义表。表头它的数据元素有原子元素，也有广义表。表头(bi(bi o tu)heado tu)head（DD）=a=a，表尾，表尾tailtail（DD）=（a a，b b），（），（a a，（，（a a

33、，b b）。此时，）。此时，DD是一个再入表是一个再入表n n E=E=（A A，C C，d d）=（），（），（a a，b b，c c），），d d）长度为）长度为3 3，深度为，深度为2 2。此时，广义。此时，广义表中的子表可以用广义表的名称来代替。表中的子表可以用广义表的名称来代替。n n F=F=（f f，F F）。广义表）。广义表F F是一个递归表述的表，意义为是一个递归表述的表，意义为F=F=（f f，（，（f f，（，（f f，（），），F F的长度为的长度为2 2。此时，。此时，F F是一个递归表是一个递归表n n广义表能够实现共享！广义表能够实现共享！第39页/共59页第三十

34、九页，共59页。广义广义(gungy)表基本概表基本概念念22.2.广义广义(gu(gu ngy)ngy)表表ADTADT描述描述ADT Generalized Lists is数据对象：数据对象：D=ai|ai AtomSet或者或者ai Generalized,i=0,1,2,n-1,n0，AtomSet为某种数据元素类型为某种数据元素类型 数据关系：数据关系：R=|ai-1,ai D,i=1,2,n-1基本操作：基本操作：（1）InitGList(Generalized Ls)创建一个空的广义表创建一个空的广义表 Ls。（2）GetHead(Generalized Ls)返回取广义表返回

35、取广义表 Ls的表头。的表头。（3）GetTail(Generalized Ls)返回广义表返回广义表 Ls的表尾。的表尾。（4）GListDepth(Generalized Ls)返回广义表返回广义表 Ls的深度。的深度。（5）GListEmpty(Generalized Ls)判断判断(pndun)广义表广义表Ls是否为空广义表。是否为空广义表。（6）DestroyGList(Generalized Ls)销毁广义表销毁广义表 Ls释放空间。释放空间。ADT Generalized第40页/共59页第四十页，共59页。广义表存储广义表存储(cn ch)结结构构n n广义表中的元素有原子元素

36、和广义表，在存储结构设计上也需要使广义表中的元素有原子元素和广义表，在存储结构设计上也需要使用用(sh(sh yng)yng)表结点和原子结点两种类型。表结点和原子结点两种类型。第41页/共59页第四十一页，共59页。广义表存储广义表存储(cn ch)结结构构2n n用C语言定义(dngy)广义表的结点结构类型如下：00 typedef struct GLnode01 02 int tag;/*标识域，用于区分原子结点和表结点标识域，用于区分原子结点和表结点*/03 union04 05 DataType atom;/*原子结点的值域，元素类型为原子结点的值域，元素类型为DataType*/0

37、6 struct GLnode*sublist;/*指向表头指向表头(bio tu)结点的指针域结点的指针域*/08 struct GLnode*next;/*指向下一元素结点的指针域指向下一元素结点的指针域*/09 GLnode;/*定义广义表结点类型为定义广义表结点类型为GLnode*/第42页/共59页第四十二页，共59页。广义表存储广义表存储(cn ch)结结构构3n n广义广义(gu(gu ngy)ngy)表存储结构示例：表存储结构示例：第43页/共59页第四十三页，共59页。广义广义(gungy)表基本操表基本操作作1.广义广义(gungy)表创建表创建00 GLnode*crea

38、tglist(char*s)/*创建广义创建广义(gungy)表表*/01 02 GLnode*h;03 char ch;04 ch=*s;05 s+;06 if(ch!=0)07 08 h=(GLnode*)malloc(sizeof(GLnode);09 if(!h)10 printf(error!n);11 if(ch=()12 13 h-tag=1;14 h-val.sublist=creatglist(s);/*递归创建广义递归创建广义(gungy)表表*/15 16 else17 if(ch=)18 h=NULL;第44页/共59页第四十四页，共59页。广义广义(gungy)表基本

39、操表基本操作作1.广义广义(gungy)表创建表创建219 else20 21 h-tag=0;22 h-val.atom=ch;23 24 25 else26 h=NULL;27 ch=*s;28 s+;29 if(h!=NULL)30 31 if(ch=,)32 h-next=creatglist(s);33 else34 h-next=NULL;35 36 return h;37 第45页/共59页第四十五页，共59页。广义广义(gungy)表基本操表基本操作作22.输出输出(shch)广义表广义表00 void output(GLnode*h)01 02 if(h!=NULL)03 0

40、4 if(h-tag=1)05 06 printf();07 if(h-val.sublist=NULL)08 printf();09 else10 output(h-val.sublist);/*输出输出(shch)广义表表头结点广义表表头结点*/11 12 else13 printf(%c,h-val.atom);/*如该元素为原子结点，输出如该元素为原子结点，输出(shch)元素值元素值*/14 if(h-tag=1)15 printf();16 if(h-next!=NULL)17 18 printf(,);19 output(h-next);/*继续输出继续输出(shch)广义表下一

41、个元素广义表下一个元素*/20 第46页/共59页第四十六页，共59页。广义广义(gungy)表基本操表基本操作作33.插入元素插入元素(yun s)到广义表表头到广义表表头00 viod insert(GLnode*h,char e)01 02 GLnode*p;03 p=(GLnode*)malloc(sizeof(GLnode);/*申请新结点申请新结点p并赋值并赋值*/04 p-tag=0;05 p-val.atom=e;06 p-next=h-val.sublist;/*将新结点将新结点p插入到广义表中插入到广义表中*/07 h-val.sublist=p;08 第47页/共59页第

42、四十七页，共59页。广义广义(gungy)表基本操表基本操作作44.求广义表深度求广义表深度00 int depth(GLnode*h)/*求广义表的深度求广义表的深度*/01 02 int max=0,dep;03 while(h!=NULL)04 05 if(h-tag=1)/*如该元素如该元素(yun s)为广义表，继续求为广义表，继续求其子表深度其子表深度*/06 07 dep=depth(h-val.sublist);08 if(depmax)09 max=dep;/*各子表深度最大值为子表的深度各子表深度最大值为子表的深度*/10 11 h=h-next;12 13 return max+1;/*返回子表深度返回子表深度+1*/14 第48页/共59页第四十八页，共59页。本章本章(bn zhn)小结小结n n本章基本本章基本(jbn)(jbn)内容：内容：第49页/共59页第四十九页，共59页。本章本章(bn zhn)小结小结2n n基于基于(jy)(jy)线性表的数据结构：线性表的数据结构：第50页/共59页第五十页，共59页。感谢您的观看感谢您的观看(gunkn)！第59页/共59页第五十九页，共59页。