数组与广义表Bppt课件

内内 容容 安安 排排章章内内 容容 学时学时 章章 内内 容容 学时学时 1序序 论论26树和二叉树树和二叉树 82线性表线性表67图图63栈和队列栈和队列48查找查找64串串39内部排序内部排序65数组和广义表数组和广义表 3合计讲课合计讲课44后后2次实验安排在次实验安排在9周和周和13周二晚周二晚 6:309:50考试方式：笔试开卷平常成果作业和实验考试方式：笔试开卷平常成果作业和实验 占占 80%占占20%告告 示示为保证电信为保证电信6 6、7 7、8 8班和通讯班和通讯1 1、2 2班同窗的班同窗的正常上课权限，请同窗们依以下图就座，敬请配正常上课权限，请同窗们依以下图就座，敬请配合！合！讲讲 台台电信电信7班班 通讯通讯1班班 (4列列)(4列列)旁听席最后旁听席最后2行行 电电信信8班班1列列电信电信6班班 电信电信8班班 通讯通讯2班班 (3列列)(3列列)(3列列)前门前门后门后门数据构造课程的内容数据构造课程的内容第第5章章 数组和广义表数组和广义表Arrays&Lists 元素的值并非原子类型，可以再分解，表中元素也是一元素的值并非原子类型，可以再分解，表中元素也是一个线性表即广义的线性表。个线性表即广义的线性表。一切数据元素仍属同一数据类型。一切数据元素仍属同一数据类型。5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的紧缩存储矩阵的紧缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储构造广义表的存储构造数组和广义表的特点：一种特殊的线性表数组和广义表的特点：一种特殊的线性表顺序存储方式：按低地址优先或高地址优先顺序存入一维顺序存储方式：按低地址优先或高地址优先顺序存入一维数组。数组。行指针向量行指针向量a11a12a1nam1am2amn补充：补充：链式存储方式：用带行指针向量的单链表来链式存储方式：用带行指针向量的单链表来表示。表示。注：数组的运算参见下一节实例稀疏矩阵的转置注：数组的运算参见下一节实例稀疏矩阵的转置难点是多维数组与一维数组的地址映射关系难点是多维数组与一维数组的地址映射关系5.3 5.3 矩阵的紧缩存储矩阵的紧缩存储讨论：讨论：1.什么是紧缩存储？什么是紧缩存储？假设多个数据元素的值都一样，那么只分配一个元素值的存储假设多个数据元素的值都一样，那么只分配一个元素值的存储空间，且零元素不占存储空间。空间，且零元素不占存储空间。2.一切二维数组矩阵都能紧缩吗？一切二维数组矩阵都能紧缩吗？未必，要看矩阵能否具备以上紧缩条件。未必，要看矩阵能否具备以上紧缩条件。3.什么样的矩阵具备以上紧缩条件？什么样的矩阵具备以上紧缩条件？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。阵等。4.什么叫稀疏矩阵？什么叫稀疏矩阵？矩阵中非零元素的个数较少普通小于矩阵中非零元素的个数较少普通小于5%重点引见稀疏矩阵的紧缩和相应的操作。重点引见稀疏矩阵的紧缩和相应的操作。一、稀疏矩阵的紧缩存储一、稀疏矩阵的紧缩存储问题：问题：假设只存储稀疏矩阵中的非零元素，那这些元素的假设只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？位置信息该如何表示？处理思绪：处理思绪：对每个非零元素增开假设干存储单元，例如存放其对每个非零元素增开假设干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。所在的行号和列号，便可准确反映该元素所在位置。实现方法：实现方法：将每个非零元素用一个三元组将每个非零元素用一个三元组i，j，aij来表示，来表示，那么每个稀疏矩阵可用一个三元组表来表示。那么每个稀疏矩阵可用一个三元组表来表示。二、稀疏矩阵的操作二、稀疏矩阵的操作例例1：三元素组表中的每个结点对应于稀疏矩阵的三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该一个非零元素，它包含有三个数据项，分别表示该元素的元素的 、和和 。行下标行下标列下标列下标元素值元素值例例2 2：写出右图所示稀疏：写出右图所示稀疏矩阵的紧缩存储方式。矩阵的紧缩存储方式。0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0(1,2,12)(1,2,12)，(1,3,9)(1,3,9)，(3,1,-3)(3,1,-3)，(3,5,14)(3,5,14)，(4,3,24)(4,3,24)，(5,2,18)(5,2,18)，(6,1,15)(6,1,15)，(6,4,-7)(6,4,-7)法法1 1：用线性表表示：用线性表表示：0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0法法2 2：用三元组矩阵表示：用三元组矩阵表示：0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0121213931-3351443245218611564-7留意：为更可靠描画，留意：为更可靠描画，通常再加一行通常再加一行“总体总体信息：即总行数、总信息：即总行数、总列数、非零元素总个列数、非零元素总个数数668ijvalue稀疏矩阵紧缩存储的缺陷：将失去随机存取功能稀疏矩阵紧缩存储的缺陷：将失去随机存取功能 :-(法三：用带辅助向量的三元组表示。法三：用带辅助向量的三元组表示。方法：方法：添加添加2个辅助向量：个辅助向量：记录每行非记录每行非0元素个数，用元素个数，用NUMi表示；表示；记录稀疏矩阵中每行第一个非记录稀疏矩阵中每行第一个非0元素在三元素在三元组中的行号，用元组中的行号，用POSi表示。表示。76531211202NUM(i)6543POS(i)21i0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0-7461516182524341453-3139311221866vji0123456783用途：经过三元组高效访问稀疏矩阵中用途：经过三元组高效访问稀疏矩阵中任一非零元素。任一非零元素。规律：规律：POS(1)1 POS(i)POS(i-1)+NUM(i-1)法四：用十字链表表示法四：用十字链表表示用途：方便稀疏矩阵的加减运算；用途：方便稀疏矩阵的加减运算；方法：每个非方法：每个非0元素占用元素占用5个域。个域。right downvji同一列中下一非同一列中下一非零元素的指针零元素的指针同一行中下一非同一行中下一非零元素的指针零元素的指针十字链表的特点：十字链表的特点：每行非零元素链接成带表头结点的循环链表；每行非零元素链接成带表头结点的循环链表；每列非零元素也链接成带表头结点的循环链表。每列非零元素也链接成带表头结点的循环链表。那么每个非零元素既是行循环链表中的一个结点；那么每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即呈十字链状。又是列循环链表中的一个结点，即呈十字链状。以刚刚的以刚刚的稀疏矩阵稀疏矩阵为例：为例：122100H19311825#define MAXSIZE 125000 /#define MAXSIZE 125000 /设非零元素最大个数设非零元素最大个数125000125000 typedef struct typedef struct int i;/int i;/元素行号元素行号 int j;/int j;/元素列号元素列号 ElemType e;/ElemType e;/元素值元素值Triple;Triple;typedef structtypedef struct Triple dataMAXSIZE+1;/Triple dataMAXSIZE+1;/三元组表，以行为主序存入一三元组表，以行为主序存入一维向量维向量 data data 中中 int mu;/int mu;/矩阵总行数矩阵总行数 int nu;/int nu;/矩阵总列数矩阵总列数 int tu;/int tu;/矩阵中非零元素总个数矩阵中非零元素总个数TsMatrix;TsMatrix;三元组表的顺序存储表示见教材三元组表的顺序存储表示见教材P98P98：/一个结点的构造定义一个结点的构造定义/整个三元组表的定义整个三元组表的定义二、稀疏矩阵的操作二、稀疏矩阵的操作 0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 00 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)三三元元组组表表a.data三三元元组组表表b.data转置后转置后MT以转置运算为例以转置运算为例目的：目的：答：一定不正确！答：一定不正确！除了：除了：1 1每个元素的行下标和列下标互换即三元组每个元素的行下标和列下标互换即三元组中的中的i i和和j j互换；互换；还应该：还应该：2 2T T的总行数的总行数mumu和总列数和总列数nunu与与M M值不同互换；值不同互换；3 3重排三元组内元素顺序，使转置后的三元组重排三元组内元素顺序，使转置后的三元组也按行或列为主序有规律的陈列。也按行或列为主序有规律的陈列。上述上述1 1和和2 2容易实现，难点在容易实现，难点在3 3。假设采用三元组紧缩技术存储稀疏矩阵，只需把每假设采用三元组紧缩技术存储稀疏矩阵，只需把每个元素的行下标和列下标互换，就完成了对该矩阵的转置个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？运算，这种说法正确吗？有两种实现方法有两种实现方法紧缩转置紧缩转置(紧缩紧缩)快速转置快速转置提问：提问：方法方法1 1：紧缩转置：紧缩转置思绪：反复扫描思绪：反复扫描a.dataa.data中的列序，从小到大依次进展转置。中的列序，从小到大依次进展转置。三三元元组组表表a.data三三元元组组表表b.data(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)11 22col q1234 p1234Status TransPoseSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=M.nu;col+)for(p=1;p=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.value=M.datap.value;q+;return OK;/TranposeSMatrix;紧缩转置算法描画：见教材紧缩转置算法描画：见教材P99/用三元组表存放稀疏矩阵用三元组表存放稀疏矩阵M M，求，求M M的转置矩阵的转置矩阵T T/q/q是转置矩阵是转置矩阵T T的结点编号的结点编号/col/col是扫描是扫描M M三元表列序的变量三元表列序的变量/p/p是是M M三元表中结点编号三元表中结点编号1 1、主要时间耗费在查找、主要时间耗费在查找M.datap.j=colM.datap.j=col的元素，由两重循的元素，由两重循环完成环完成:for(col=1;col=M.nu;col+):for(col=1;col=M.nu;col+)循环次数循环次数nunu for(p=1;p=M.tu;p+)for(p=1;p=M.tu;p+)循环次数循环次数tutu所以该算法的时间复杂度为所以该算法的时间复杂度为O(nuO(nu*tu)tu)-即即M M的列数与的列数与M M中非零元素的个数之积中非零元素的个数之积最恶劣情况：最恶劣情况：M M中全是非零元素，此时中全是非零元素，此时tu=mutu=mu*nunu，时间复杂度为时间复杂度为 O(nu2O(nu2*mu)mu)注：假设注：假设M M中根本上是非零元素时，即使用非紧缩传统转置算中根本上是非零元素时，即使用非紧缩传统转置算法的时间复杂度也不过是法的时间复杂度也不过是O(nuO(nu*mu)mu)程序见教材程序见教材P99P99结论：紧缩转置算法不能滥用。结论：紧缩转置算法不能滥用。前提：仅适用于非零元素个数很少即前提：仅适用于非零元素个数很少即tumutumu*nunu的情况。的情况。紧缩转置算法的效率分析：紧缩转置算法的效率分析：方法方法2 2 快速转置快速转置三三元元组组表表a.data三三元元组组表表b.data(1,3,-3)(2,1,12)(2,5,18)(3,1,9)(4,6,-7)(5,3,14)(1,6,15)(3,4,24)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)思绪：依次把思绪：依次把a.dataa.data中的元素直接送入中的元素直接送入b.datab.data的恰当位的恰当位置上即置上即M M三元组的三元组的p p指针不回溯。指针不回溯。关键：怎样寻觅关键：怎样寻觅b.datab.data的的“恰当位置？恰当位置？p1234 q 3 5假设能预知假设能预知M M矩阵每一列矩阵每一列(即即T T的每一行的每一行)的非零元素个数，的非零元素个数，又能预知第一个非零元素在又能预知第一个非零元素在b.datab.data中的位置中的位置,那么扫描那么扫描a.dataa.data时便可以将每个元素准确定位由于知假设干参考时便可以将每个元素准确定位由于知假设干参考点。点。技巧：利用带辅助向量的三元组表，它正好携带每行或列技巧：利用带辅助向量的三元组表，它正好携带每行或列的非零元素个数的非零元素个数 NUM(i)NUM(i)以及每行或列的第一个非以及每行或列的第一个非零元素在三元组表中的位置零元素在三元组表中的位置POS(i)POS(i)等信息。等信息。设计思绪：设计思绪：i123456NUM(i)202112POS(i)133567不过我们需求的是按列生成的不过我们需求的是按列生成的M M矩阵的辅助向量。矩阵的辅助向量。规律：规律：POS(1)1POS(i)POS(i-1)+NUM(i-1)请回想：请回想：请留意请留意a.dataa.data特征：每列首个非零元素必定先被扫描到。特征：每列首个非零元素必定先被扫描到。令：令：M中的列变量用中的列变量用col表示；表示；num col：存放：存放M中第中第col 列中非列中非0元素个数，元素个数，cpot col：存放：存放M中第中第col列的第一个非列的第一个非0元素的位置，元素的位置，即即b.data中待计算的中待计算的“恰当位置所需参考点恰当位置所需参考点讨论：按列优先的辅助向量求出后，下一步该如何操作？讨论：按列优先的辅助向量求出后，下一步该如何操作？由由a.data中每个元素的列信息，即可直接查出中每个元素的列信息，即可直接查出b.data中的重中的重要参考点之位置，进而可确定当前元素之位置！要参考点之位置，进而可确定当前元素之位置！col123456numcol222110cpotcol1规律：规律：cpot(1)1cpotcol cpotcol-1+numcol-10 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0M 3 5 7 8 8col 1 2 3 4 5 6Status FastTransposeSMatrixTSMatirx M,TSMatirx&T T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;col+)numcol=0;for(i=1;i=M.tu;i+)col=M.data i .j;+num col;cpos 1 =1;for(col=2;col=M.nu;col+)cposcol=cposcol-1+num col-1 ;for(p=1;p=M.tu;p+)col=M.data p.j;q=cpos col;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.value=M.datap.value;+cposcol;/for /ifreturn OK;/FastTranposeSMatrix;快速转置算法描画：快速转置算法描画：/M/M用顺序存储表示，求用顺序存储表示，求M M的转置矩阵的转置矩阵T T/先统计每列非零元素个数先统计每列非零元素个数/再生成每列首元位置辅助向量表再生成每列首元位置辅助向量表/p/p指向指向a.dataa.data，循环次数为非，循环次数为非0 0元素总个数元素总个数tutu/查辅助向量表得查辅助向量表得q q，即，即T T中位置中位置/重要语句！修正向量表中列坐标值，供重要语句！修正向量表中列坐标值，供同一列下一非零元素定位之用！同一列下一非零元素定位之用！1.1.与常规算法相比，附加了生成辅助向量表的任务。增开了与常规算法相比，附加了生成辅助向量表的任务。增开了2 2个长度为列长的数组个长度为列长的数组(num(num 和和cpos cpos。传统转置：传统转置：O(muO(mu*nu)nu)紧缩转置：紧缩转置：O(muO(mu*tu)tu)紧缩快速转置：紧缩快速转置：O(nu+tu)O(nu+tu)牺牲空间效率换时间效率。牺牲空间效率换时间效率。快速转置算法的效率分析：快速转置算法的效率分析：2.2.从时间上，此算法用了从时间上，此算法用了4 4个并列的单循环，而且其中前个并列的单循环，而且其中前3 3个个单循环都是用来产生辅助向量表的。单循环都是用来产生辅助向量表的。for(col=1;col=M.nu;col+)for(col=1;col=M.nu;col+)循环次数循环次数nu;nu;for(i=1;i=M.tu;i+)for(i=1;i=M.tu;i+)循环次数循环次数tu;tu;for(col=2;col=M.nu;col+)for(col=2;col=M.nu;col+)循环次数循环次数nu;nu;for(p=1;p=M.tu;p+)for(p=1;p=M.tu;p+)循环次数循环次数tu;tu;该算法的时间复杂度该算法的时间复杂度(nu(nu*2)+(tu2)+(tu*2)=O(nu+tu2)=O(nu+tu讨论：最恶劣情况是讨论：最恶劣情况是tu=nutu=nu*mu(mu(即矩阵中全部是非零元素，即矩阵中全部是非零元素，而此时的时间复杂度也只是而此时的时间复杂度也只是O(muO(mu*nu)nu)，并未超越传统转置算，并未超越传统转置算法的时间复杂度。法的时间复杂度。小结：小结：稀疏矩阵相乘的算法见教材稀疏矩阵相乘的算法见教材P101-103P101-1035.4 5.4 广义表的定义广义表的定义广义表是线性表的推行，也称为列表广义表是线性表的推行，也称为列表lists记为：记为：LS =(a1,a2,，an)广义表名广义表名 表头表头(Head 表尾表尾(Tail)1、定义：、定义：第一个元素是表头，而其他元素组成的表称为表尾；第一个元素是表头，而其他元素组成的表称为表尾；用小写字母表示原子类型，用大写字母表示列表。用小写字母表示原子类型，用大写字母表示列表。n n是表长是表长在广义表中商定：在广义表中商定：讨论：广义表与线性表的区别和联络？讨论：广义表与线性表的区别和联络？广义表中元素既可以是原子类型，也可以是列表；广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型一样时，就是线性表。当每个元素都为原子且类型一样时，就是线性表。2、特点：、特点：有次序性有次序性 有长度有长度 有深度有深度 可递归可递归 可共享可共享一个直接前驱和一个直接后继一个直接前驱和一个直接后继表中元素个数表中元素个数表中括号的重数表中括号的重数本人可以作为本人的子表本人可以作为本人的子表可以为其他广义表所共享可以为其他广义表所共享特别提示：任何一个非空表，表头能够是原子，也能够特别提示：任何一个非空表，表头能够是原子，也能够是列表；但表尾一定是列表。是列表；但表尾一定是列表。E=(a,E)=(a,(a,E)=(a,(a,(a,.)，E为递归表为递归表1A=()2B=(e)3C=(a,(b,c,d)4D=(A,B,C)5E=(a,E)例例1：求以下广义表的长度。：求以下广义表的长度。n=0，由于，由于A是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a 为原子，为原子，(b,c,d)为子表为子表n=3，3个元素都是子表个元素都是子表n=2，a 为原子，为原子，E为子表为子表D=(A,B,C)=(),(e),(a,(b,c,d)，共享表，共享表ABDCeabcd A=(a,(b,A)例例2 2：试用图形表示以下广义表：试用图形表示以下广义表.设设 代表原子，代表原子，代表子表代表子表 e D=(A,B,C)=(),(e),(a,(b,c,d)Aab的长度为的长度为3，深度为，深度为3的长度为的长度为2，深度为，深度为深度括号的重数深度括号的重数 结点的层数结点的层数引见两种特殊的根本操作：引见两种特殊的根本操作：GetHead(L)GetHead(L)取表头取表头(能够是原子或列表能够是原子或列表););GetTail(L)GetTail(L)取表尾取表尾(一定是列表一定是列表)。广义表的笼统数据类型定义见教材广义表的笼统数据类型定义见教材P107-108P107-1081.GetTail【(b,k,p,h)】;2.GetHead【(a,b),(c,d)】;3.GetTail【(a,b),(c,d)】;4.GetTail【GetHead【(a,b),(c,d)】;例：求以下广义表操作的结果严题集例：求以下广义表操作的结果严题集5.10(k,p,h)b(a,b)5.GetTail【e】;6.GetHead【()】.7.GetTail【()】.()(c,d)()()(c,d)5.5 广义表的存储构造广义表的存储构造由于广义表的元素可以是不同构造原子或列表，难以用由于广义表的元素可以是不同构造原子或列表，难以用顺序存储构造表示顺序存储构造表示 ，通常用链式构造，每个元素用一个结，通常用链式构造，每个元素用一个结点表示。点表示。valuetag=0标志域标志域 数值域数值域留意：列表的留意：列表的“元素还可以是列表，所以结点能够有两种方式元素还可以是列表，所以结点能够有两种方式tpatomtag=标志域标志域 值域表尾指针值域表尾指针法法2 2：标志域、值域、表尾指针：标志域、值域、表尾指针指向下一结点指向下一结点法法1 1：标志域，数值域：标志域，数值域tphptag=1 标志域标志域 表头指针表头指针 表尾指针表尾指针2.2.表结点：表示列表，假设表不空，那么可分解为表头和表结点：表示列表，假设表不空，那么可分解为表头和表尾，用表尾，用3 3个域表示：标志域，表头指针，表尾指针。个域表示：标志域，表头指针，表尾指针。A=()10e C=(a,(b,c,d)1110a0b0d0c11例：例：B=(e)A=NULL指向子表指向子表指向下一结点指向下一结点1 E=(a,E)D=(A,B,C)(),(e),(a,(b,c,d)0a1110e111110a0b0d0c111本章终了本章终了参见教材参见教材P109图图 喻信星空喻信星空BBS 211.69.196.32 端口端口:2600FTPftp211.69.196.32/pub/dian/本周四上课之前完成第本周四上课之前完成第4-54-5章自测卷全部内容。章自测卷全部内容。算法设计题建议上机验证。算法设计题建议上机验证。刘玉教师的信箱：刘玉教师的信箱：jimu.room263本章作业本章作业新增：新增：严题集全部算法设计题参考程序已紧缩为严题集全部算法设计题参考程序已紧缩为116KB)；数据构造演示系统数据构造演示系统(5.75MB)