1、第四章第四章 串、数组和广义表串、数组和广义表2 学时学时教学目标教学目标l了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。l 明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。l掌握广义表的定义、性质及其GetHead和GetTail的操作。数据结构串串第一节第一节补充：补充：C语言中常用的串运算语言中常用的串运算调用标准库函数调用标准库函数#includel串比较，串比较，strcmp(char s1,char s2)l串复制，串复制，strcpy(char to,char from)l串连接，串连接，strcat(char to,c
2、har from)l求串长，求串长，strlen(char s)l 4.1.1 串串的基本概念的基本概念串串(String)：零个或多个字符组成的有限序列。零个或多个字符组成的有限序列。21naaas串名串名串值串值串长串长n空串空串n=04.1.1 串串的基本概念的基本概念a=BEI,b=JING c=BEIJING d=BEI JINGla和和b是是c和和d的子串的子串la在在c和和d中的位置是中的位置是1。lb在在c中的位置是中的位置是4，在，在d中的位置为中的位置为5。l 是空格串是空格串子串子串字符位置字符位置主串主串子串位置子串位置串相等串相等空格串空格串4.1.2 串串的的抽象数
3、据类型抽象数据类型ADT String数据对象：数据对象：D=ai|aiCharacterSet,i=1,2,n,n 0 数据关系：数据关系：R=|ai-1,aiD,i=2,3,n 基本操作：基本操作：StrLength(s)：求串求串s的长度。的长度。StrAssign(s1,s2)：赋值，将赋值，将s2的值赋值给串的值赋值给串s1。StrConcat(s1,s2,s)：连接，将串连接，将串s2放在串放在串s1的后面连接的后面连接成一个新串成一个新串s。SubStr(s,i,len)：求子串，返回从串求子串，返回从串s的第的第i个字符开始取个字符开始取长为长为 len 的子串。的子串。4.1
4、.2 串串的的抽象数据类型抽象数据类型 StrCmp(s1,s2)：串比较，若串比较，若s1=s2，返回，返回0；若；若s1s2,返回返回1。StrIndex(s,t)：定位，返回子串定位，返回子串t在主串在主串s中首次出现的位中首次出现的位置。若置。若t不是不是s的子串，则返回的子串，则返回0。StrInsert(s,i,t)：插入，将串插入，将串t插入到串插入到串s中的第中的第i个位置。个位置。StrDelete(s,i,len)：删除，在串删除，在串s中删除从第中删除从第i个字符开始个字符开始的连续的连续len个字符。个字符。StrRep(s,t,r)：替换，在串替换，在串s中用串中用串
5、r替换所有与串替换所有与串t相等相等的子串。的子串。ADT String4.1.2 串串的的抽象数据类型抽象数据类型求子串操作求子串操作SubStr(s,i,len)示例示例a b c d e f g ei=3,len=3i=7,len=4c d ea b c d e f g eg e空串空串4.1.3 串与线性表的比较串与线性表的比较l逻辑结构逻辑结构 串的逻辑结构和线性表极为相似，区别仅在于串的数据对串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。象约束为字符集。l 基本操作基本操作l在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个元素单个元素”作为操作作为
6、操作对象；对象；l在串的基本操作中，通常以在串的基本操作中，通常以“串的整体串的整体”作为操作对象作为操作对象。4.1.4 串串的的存储结构存储结构l 串是一种特殊的线性表，其存储表示和线性表类似，但又串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。串的存储方式取决于将要对串所进行的操作不完全相同。串的存储方式取决于将要对串所进行的操作。串在计算机中有。串在计算机中有3种表示方式：种表示方式：l定长顺序存储表示：定长顺序存储表示：将串定义成字符数组，利用串名可将串定义成字符数组，利用串名可以直接访问串值。用这种表示方式，串的存储空间在编以直接访问串值。用这种表示方式，串的存储空间
7、在编译时确定，其大小不能改变。译时确定，其大小不能改变。l堆分配存储方式：堆分配存储方式：仍然用一组地址连续的存储单元来依仍然用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序运行次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。时根据串的实际长度动态分配的。l 块链存储方式：块链存储方式：是一种链式存储结构表示。是一种链式存储结构表示。4.1.4 串串的的存储结构存储结构l串的定长顺序存储表示串的定长顺序存储表示 这种存储结构又称为串的顺序存储结构。是用一组连续的存储单元来这种存储结构又称为串的顺序存储结构。是用一组连续的存储单元来存放串中的
8、字符序列。所谓定长顺序存储结构，是直接使用定长的字存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先确定。符数组来定义，数组的上界预先确定。l特点特点:l串的实际长度可在这个予定义长度的范围内随意设定，超过予定义串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为长度的串值则被舍去，称之为“截断截断”。l按这种串的表示方法实现的串的运算时，其基本操作为按这种串的表示方法实现的串的运算时，其基本操作为“字符序字符序列的复制列的复制”。l定长顺序存储结构定义为：定长顺序存储结构定义为：#define MAX_STRLEN 256
9、 typedef struct char strMAX_STRLEN;int length;StringType;4.1.4 串串的的存储结构存储结构方案方案1：用一个变量来表示串的实际长度。用一个变量来表示串的实际长度。如何表示串的长度？如何表示串的长度？0 1 2 3 4 5 6 Max-1 a b c d e f g9空空 闲闲0 1 2 3 4 5 6 7 Max-1 a b c d e f g 0空空 闲闲方案方案2：在串尾存储一个不会在串中出现的特殊字符在串尾存储一个不会在串中出现的特殊字符作为串的终结符，作为串的终结符，表示串的结尾。表示串的结尾。方案方案3：用数组的用数组的0号
10、单元存放串的长度，从号单元存放串的长度，从1号单号单元开始存放串值。元开始存放串值。0 1 2 3 4 5 6 7 Max-1 9 a b c d e f g空空 闲闲4.1.4 串串的的存储结构存储结构l串的联接算法中需分三种情况处理：串的联接算法中需分三种情况处理：Status Concat(SString S1,SString S2,SString&T)/用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串。若未截断,则返回则返回TRUE，否则，否则FALSE。if(S10+S20=MAXSTRLEN)/未截断未截断T1.S10=S11.S10;TS10+1.S10+S2
11、0=S21.S20;T0=S10+S20;uncut=TRUE;else if(S10 MAXSTRLEN)/s2截断截断,s1未截断未截断T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;else /s1截断截断(仅取仅取S1)T1.MAXSTRLEN=S11.MAXSTRLEN;T0=MAXSTRLEN uncut=FALSE;return uncut;/Concat4.1.4 串串的的存储结构存储结构l串的堆分配存储表示串的堆分配存储表示l实现方法：实现方法：系统提供一个空间足够大且地址连续
12、的存储空系统提供一个空间足够大且地址连续的存储空间间(称为称为“堆堆”)供串使用。可使用供串使用。可使用C语言的动态存储分配函语言的动态存储分配函数数malloc()和和free()来管理。来管理。l特点：特点：仍然以一组地址连续的存储空间来存储字符串值，仍然以一组地址连续的存储空间来存储字符串值，但其所需的存储空间是在程序执行过程中动态分配，故是但其所需的存储空间是在程序执行过程中动态分配，故是动态的，变长的。动态的，变长的。l串的堆式存储结构的类型定义串的堆式存储结构的类型定义 typedef struct char*ch;/*若非空，按长度分配，否则为若非空，按长度分配，否则为NULL*
13、/int length;/*串的长度串的长度 */HString;4.1.4 串串的的存储结构存储结构l串的链式存储表示串的链式存储表示 串的链式存储结构和线性表的串的链式存储结构类似，采串的链式存储结构和线性表的串的链式存储结构类似，采用单链表来存储串，结点的构成是：用单链表来存储串，结点的构成是：l data域：存放字符，域：存放字符，data域可存放的字符个数称为结点的大小；域可存放的字符个数称为结点的大小；l next域：存放指向下一结点的指针。域：存放指向下一结点的指针。l 若每个结点仅存放一个字符，则结点的指针域就非常多，若每个结点仅存放一个字符，则结点的指针域就非常多，造成系统空
14、间浪费，为节省存储空间，考虑串结构的特殊造成系统空间浪费，为节省存储空间，考虑串结构的特殊性，使每个结点存放若干个字符，这种结构称为性，使每个结点存放若干个字符，这种结构称为块链结构块链结构first a b ge f gfirsta b c d4.1.4 匹配模式匹配模式模式匹配：模式匹配：给定主串给定主串S=s1s2sn和模式和模式T=t1t2tm，在在S中寻找中寻找T 的过程称为模式匹配的过程称为模式匹配。如果匹配成功，返回如果匹配成功，返回T 在在S中的位置，如果匹配失败，返回中的位置，如果匹配失败，返回0。基本思想：基本思想：从主串从主串S的第一个字符开始和模式的第一个字符开始和模式
15、T 的第一个字符的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，进行比较，若相等，则继续比较两者的后续字符；否则，从主串从主串S的第二个字符开始和模式的第二个字符开始和模式T 的第一个字符进行比较，的第一个字符进行比较，重复上述过程，直到重复上述过程，直到T 中的字符全部比较完毕，则说明本中的字符全部比较完毕，则说明本趟匹配成功；或趟匹配成功；或S中字符全部比较完，则说明匹配失败。中字符全部比较完，则说明匹配失败。模式匹配问题的特点：模式匹配问题的特点：算法的一次执行时间不容忽视：问题规模通常很大，常算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹配；常需
16、要在大量信息中进行匹配；算法改进所取得的积累效益不容忽视：模式匹配操作经算法改进所取得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。常被调用，执行频率高。4.1.4 匹配模式匹配模式BP算法算法 si 主串主串S模式模式T tjji 回溯回溯 回溯回溯4.1.4 匹配模式匹配模式BP算法算法 si 主串主串S模式模式Tji tj4.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bi=3，j=3失败；失败；i“回溯回溯”到到2，j回溯到回溯到1ij第第 1趟趟a b c a c
17、4.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bij第第 1趟趟a b c a c i=3，j=3失败；失败；i“回溯回溯”到到2，j回溯到回溯到14.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bij第第 2趟趟a b c a c i=2，j=1失败；失败；i“回溯回溯”到到3，j回溯到回溯到14.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcac
18、bab，模式模式T=abcaca b a b c a b c a c b a bij第第 2趟趟a b c a c i=2，j=1失败；失败；i“回溯回溯”到到3，j回溯到回溯到14.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bi=7，j=5失败；失败；i“回溯回溯”到到4，j回溯到回溯到1ij第第 3趟趟a b c a c 4.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a b
19、ij第第 3趟趟a b c a c i=7，j=5失败；失败；i“回溯回溯”到到4，j回溯到回溯到14.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bij第第 4趟趟a b c a c i=4，j=1失败；失败；i“回溯回溯”到到5，j回溯到回溯到14.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bij第第 4趟趟a b c a c i=4，j=1失败；失败；i“回溯回溯”到到
20、5，j回溯到回溯到14.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bij第第 5趟趟a b c a c i=5，j=1失败；失败；i“回溯回溯”到到6，j回溯到回溯到14.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bij第第 5趟趟a b c a c i=5，j=1失败；失败；i“回溯回溯”到到6，j回溯到回溯到14.1.4 匹配模式匹配模式BP算法算法例：主串例：主串S=
21、ababcabcacbab，模式模式T=abcaca b a b c a b c a c b a bij第第 6趟趟a b c a c i=11，j=6，T中全部字符都比中全部字符都比较完毕，较完毕，匹配成功匹配成功。4.1.4 匹配模式匹配模式BP算法算法l算法描述算法描述l在串在串S和串和串T中设比较的起始下标中设比较的起始下标i和和j；l循环直到循环直到S或或T的所有字符均比较完；的所有字符均比较完；如果如果Si=Tj，继续比较继续比较S和和T的下一个字符；的下一个字符；否则，将否则，将i和和j回溯，准备下一趟比较；回溯，准备下一趟比较；l如果如果T中所有字符均比较完，则匹配成功，返回匹
22、配的起中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回始比较下标；否则，匹配失败，返回0；4.1.4 匹配模式匹配模式BP算法算法int Index(SString S,SString T,int pos)/返回子串返回子串T在主串在主串S中第中第pos个字符之后的位置。若不存在，则函数个字符之后的位置。若不存在，则函数值为值为0。/其中，其中，T非空，非空，1posStrLength(S)。i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/Indexijj-1i-1i-j+2i-j+1124.1.4 匹配模式
23、匹配模式BP算法算法l时间复杂度：时间复杂度：设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况下，考虑，在匹配成功的情况下，考虑两种极端情况：两种极端情况：最好情况：最好情况：不成功的匹配都发生在串不成功的匹配都发生在串T的第一个字符。的第一个字符。例如：例如：S=aaaaaaaaaabcdccccc T=bcd 设匹配成功发生在设匹配成功发生在si处，则在处，则在i-1趟不成功的匹配中共比较了趟不成功的匹配中共比较了i-1次，第次，第i趟成功的匹配共比较了趟成功的匹配共比较了m次，所以总共比较了次，所以总共比较了i-1+m次，所有匹配成功的可能情况共有次，所有匹配成功的可能
24、情况共有n-m+1种，则：种，则：)(2)()1(11mnOmnmipmnii+-+-4.1.4 匹配模式匹配模式BP算法算法l时间复杂度：时间复杂度：设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况下，考虑，在匹配成功的情况下，考虑两种极端情况：两种极端情况：最坏情况：最坏情况：不成功的匹配都发生在串不成功的匹配都发生在串T的最后一个字符。的最后一个字符。例如：例如：S=aaaaaaaaaaabccccc T=aaab 设匹配成功发生在设匹配成功发生在si处，则在处，则在i-1趟不成功的匹中共比较了趟不成功的匹中共比较了(i-1)m次，第次，第i趟成功的匹配共比较了趟成功的
25、匹配共比较了m次，所以总共比较次，所以总共比较了了im次，因此（一般地，次，因此（一般地，mn）)(2)2()(11mnOmnmmipmnii+-+-4.1.4 匹配模式匹配模式BP算法算法l为什么为什么BF算法时间性能低？算法时间性能低？在每趟匹配不成功时存在大量在每趟匹配不成功时存在大量回溯回溯，没有利用已经部分匹，没有利用已经部分匹配的结果。配的结果。l如何在匹配不成功时主串不回溯？如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离。主串不回溯，模式就需要向右滑动一段距离。l 如何确定模式的滑动距离？如何确定模式的滑动距离？4.1.4 匹配模式匹配模式KMP算法算法i=
26、3，j=3失败；失败；s2=t2;t1t2t1s2a b a b c a b c a c b a bij第第 1趟趟a b c a c a b a b c a b c a c b a b第第 2趟趟a b c a c 4.1.4 匹配模式匹配模式KMP算法算法i=3，j=3失败；失败；s2=t2;t1t2t1s2a b a b c a b c a c b a bij第第 1趟趟a b c a c a b a b c a b c a c b a ba b c a c 第第 3趟趟4.1.4 匹配模式匹配模式KMP算法算法a b a b c a b c a c b a ba b c a c 第第
27、3趟趟iji=7，j=5失败失败s4=t2;t1t2t1s4a b a b c a b c a c b a ba b c a c 第第 4趟趟4.1.4 匹配模式匹配模式KMP算法算法a b a b c a b c a c b a ba b c a c 第第 3趟趟iji=7，j=5失败失败s5=t3;t1t3t1s5a b a b c a b c a c b a ba b c a c 第第 5趟趟4.1.4 匹配模式匹配模式KMP算法算法a b a b c a b c a c b a ba b c a c 第第 3趟趟iji=7，j=5失败失败s5=t3;t1t3t1s5a b a b c
28、a b c a c b a ba b c a c 第第 6趟趟匹配成功匹配成功4.1.4 匹配模式匹配模式KMP算法算法l结论：结论：i可以不回溯，模式向右滑动到的新比较起点可以不回溯，模式向右滑动到的新比较起点k（使（使si和和tk继续进行匹配），并且继续进行匹配），并且k 仅与模式串仅与模式串T有关！有关！l 需要讨论两个问题：需要讨论两个问题：l如何由当前部分匹配结果确定模式向右滑动的新比较起点如何由当前部分匹配结果确定模式向右滑动的新比较起点k？l模式应该向右滑多远才是最高效率的模式应该向右滑多远才是最高效率的?4.1.4 匹配模式匹配模式KMP算法算法请抓住部分匹配时的两个特征：请抓
29、住部分匹配时的两个特征：两式联立可得：两式联立可得：（2）则）则Tj-(k-1)Tj-1 SiS=a b a b c a b c a c b a bT=a b c a cjk（1）设模式滑动到第）设模式滑动到第k个字符，则个字符，则 S S=a b a b c a b c a c b a bT=a b c a cikS=a b a b c a b c a c b a bT=a b c a cikj4.1.4 匹配模式匹配模式KMP算法算法lT1Tk-1Tj-(k-1)Tj-1说明了什么？说明了什么？（1）k 与与 j 具有函数关系，由当前失配位置具有函数关系，由当前失配位置 j，可以计算出，可
30、以计算出滑动位置滑动位置 k（即比较的新起点）；（即比较的新起点）；（2）滑动位置）滑动位置k 仅与模式串仅与模式串T有关。有关。lT1Tk-1Tj-(k-1)Tj-1的物理意义是什么？的物理意义是什么？l模式应该向右滑多远才是最高效率的模式应该向右滑多远才是最高效率的?kmax k|1kj 且且T1Tk-1Tj-(k-1)Tj-1 从第从第1位往右位往右经过经过k-1位位从从j-1位往左位往左经过经过k-1位位4.1.4 匹配模式匹配模式KMP算法算法next j 0 当当j j1 1时时 /不比较不比较max k|1k1时，时，nextj的值为：模式串的位置从的值为：模式串的位置从1到到j
31、-1构成的串构成的串中所出现的首尾相同的子串的最大长度加中所出现的首尾相同的子串的最大长度加1。l 当无首尾相同的子串时当无首尾相同的子串时nextj的值为的值为1。/nextj=1表示从模式串头部开始进行字符比较表示从模式串头部开始进行字符比较4.1.4 匹配模式匹配模式KMP算法算法 模模 式式 串串 T：a b a a b c a c 可能失配位可能失配位 j：1 2 3 4 5 6 7 8新匹配位新匹配位k=nextj:01122312j=1j=1时时,nextjnextj 0 0；j=2j=2时时,nextjnextj 1 1；j=3j=3时时,t t1 1t t2 2，因此，因此，
32、k=1k=1；j=4j=4时时,t t1 1t t3 3，因此，因此，k=2k=2；j=5j=5时时,t t1 1t t4 4，因此，因此，k=2k=2；j=6j=6时时,t t2 2t t5 5，因此，因此，k=3k=3；j=7j=7时时,t t3 3 t t6 6，t1t6，因此，因此，k=1k=1；j=8j=8时时,t t1 1t t7 7，因此，因此，k=2k=2课堂练习：课堂练习：已知已知T=“ababac”T=“ababac”求模式求模式T T的的nextjnextj。4.1.4 匹配模式匹配模式KMP算法算法lKMP算法：算法：l在串在串S和串和串T中分别设比较的起始下标中分别设
33、比较的起始下标i和和j；l循环直到循环直到S中所剩字符长度小于中所剩字符长度小于T的长度或的长度或T中所有字符均中所有字符均比较完毕比较完毕l 如果如果Si=Tj，继续比较继续比较S和和T的下一个字符；否则的下一个字符；否则l 将将j向右滑动到向右滑动到nextj位置，即位置，即j=nextj；l 如果如果j=0，则将则将i和和j分别加分别加1，准备下一趟比较；，准备下一趟比较；l如果如果T中所有字符均比较完毕，则返回匹配的起始下标；中所有字符均比较完毕，则返回匹配的起始下标；否则返回否则返回0；数据结构数组数组 第二节第二节本节所讨论的数组与高级语言中的数组区别：本节所讨论的数组与高级语言中
34、的数组区别：l高级语言中的数组是顺序结构；高级语言中的数组是顺序结构；l而本章的数组既可以是顺序的，也可以是链式结构，用户可而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。根据需要选择。4.2.1 4.2.1 数组的抽象数组类型数组的抽象数组类型ADT Array数据对象：数据对象：ji=0,1,bi-1,1,2,n;D=aj1j2jn|n0称为数组的维数，称为数组的维数，bi是数组第是数组第i维的长度，维的长度，ji是数组元素第是数组元素第i维的下标，维的下标，aj1j2jnElemSet 数据关系：数据关系：R=R1,R2,Rn Ri=|0jkbk-1，1kn且且ki，0
35、jibi-2，aj1j2 ji+1jnD 基本操作：基本操作：(1)InitArray(&A,n,bound1,boundn)/构造数组构造数组A (2)DestroyArray(&A)/销毁数组销毁数组A (3)Value(A,&e,index1,indexn)/取数组元素值取数组元素值 (4)Assign(A,&e,index1,indexn)/给数组元素赋值给数组元素赋值 ADT Array4.2.2 4.2.2 一维数组一维数组35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9l l l l l l l l l l LOC(i)=LOC(i
36、-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i 0 a,i=0 a+i*la4.2.3 4.2.3 二维数组二维数组mnmmnnnmaaaaaaaaaA212222111211mnmmnnnmaaaaaaaaaA212222111211naaamjjjjj1 ),(21miaaainiii1 ),(21n)m(p ),(21或pA4.2.3 4.2.3 二维数组二维数组以行序为主序以行序为主序C,PASCAL4.2.3 4.2.3 二维数组二维数组以列序为主序FORTRAN4.2.3 4.2.3 二维数组二维数组l二维数组的行序优先表示二维数组的行序优先表示 anm-
37、111101121202111101101000mnananamaaamaaamaaaa设数组开始存放位置设数组开始存放位置 LOC(0,0)=a LOC(j,k)=a+j*m+k4.2.4 4.2.4 三维数组三维数组l1u1l2u2l3u3按页按页/行行/列存放，页优先的顺序存储列存放，页优先的顺序存储4.2.4 4.2.4 三维数组三维数组lam1m2 m3 各维元素个数为各维元素个数为 m1,m2,m3l下标为下标为 i1,i2,i3的数组元素的存储位置：的数组元素的存储位置：LOC(i1,i2,i3)=a+i1*m2*m3+i2*m3+i3前前i1页总页总元素个数元素个数第第i1页的
38、页的前前i2行总元行总元素个数素个数第第 i2 行前行前 i3 列列元素个数元素个数4.2.5 n4.2.5 n维数组维数组l 各维元素个数为各维元素个数为 m1,m2,m3,mnl 下标为下标为 i1,i2,i3,in 的数组元素的存储位置：的数组元素的存储位置：nnjnjkkjnnnnnnimiimimmmimmmiiiiLOC+-+-111143232121 a a),(练习练习l设有一个二维数组设有一个二维数组Amn按行优先顺序存储，假设按行优先顺序存储，假设A00存放位置在存放位置在644(10)，A22存放位置在存放位置在676(10)，每个元素，每个元素占一个空间，问占一个空间，
39、问A33(10)存放在什么位置？脚注存放在什么位置？脚注(10)表示表示用用10进制表示。进制表示。答：答：设数组元素设数组元素Aij存放在起始地址为存放在起始地址为Loc(i,j)的存储单的存储单元中元中 Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.n=(676-2-644)/2=15 Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.练习练习l设有二维数组设有二维数组A10,20，其每个元素占两个字节，其每个元素占两个字节，A00存储地址为存储地址为100，若按行优先顺序存储，则，若按行优先顺序存储，则元素元素A6,6的存储地址为的
40、存储地址为 ，按列优先顺序存储，按列优先顺序存储，元素，元素A6,6的存储地址为的存储地址为 。答：答：(6*20+6)*2+100=352 (6*10+6)*2+100=2323523522322324.2.6 4.2.6 特殊矩阵的压缩存储特殊矩阵的压缩存储1.什么是压缩存储？什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。空间，且零元素不占存储空间。2.什么样的矩阵能够压缩？什么样的矩阵能够压缩？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，
41、稀疏矩阵等。疏矩阵等。3.什么叫稀疏矩阵？什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%）数据结构广义表广义表第三节第三节3.3.1 3.3.1 广义表的基本概念广义表的基本概念l 广义表（列表）：广义表（列表）：n(0)个表元素组成的有限序列，个表元素组成的有限序列，记作记作LS=(a1,a2,an-1)l LS是表名，是表名，ai是表元素，它可以是表是表元素，它可以是表(称为子表称为子表)，可以是数据元素，可以是数据元素(称为原子称为原子)。习惯上用大写字母表示广义表的名称，小写字母表示。习惯上用大写字母表示广义表的名称，小写字母表示原子。原子。l
42、 n为表的长度。为表的长度。n=0 的广义表为空表。的广义表为空表。l广义表与线性表的区别广义表与线性表的区别l线性表的成分都是结构上不可分的单元素线性表的成分都是结构上不可分的单元素l广义表的成分可以是单元素，也可以是有结构的表广义表的成分可以是单元素，也可以是有结构的表l线性表是一种特殊的广义表线性表是一种特殊的广义表l广义表不一定是线性表，也不一定是线性结构广义表不一定是线性表，也不一定是线性结构3.3.2 3.3.2 广义表的基本运算广义表的基本运算l 求表头求表头GetHead(L)：非空广义表的第一个元素，可以是一非空广义表的第一个元素，可以是一个单元素，也可以是一个子表个单元素，
43、也可以是一个子表l 求表尾求表尾GetTail(L)：非空广义表除去表头元素以外其它元非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表素所构成的表。表尾一定是一个表A=()GetHead和和GetTail均无定义均无定义A=(a,b)GetHead(A)=a GetTail(A)=(b)A=(a)GetHead(A)=a GetTail(A)=()A=(a)GetHead(A)=(a)GetTail(A)=()GetHead(GetTail(GetHead(GetTail(GetTail(A)A=(a,b,(c,d),(e,(f,g)d3.3.3 3.3.3 广义表的特点广义表的
44、特点l有次序性：有次序性：一个直接前驱和一个直接后继一个直接前驱和一个直接后继l有长度：有长度：表中元素个数表中元素个数l有深度：有深度：表中括号的重数表中括号的重数l可递归：可递归：自己可以作为自己的子表自己可以作为自己的子表l可共享：可共享：可以为其他广义表所共享可以为其他广义表所共享3.3.3 3.3.3 广义表的特点广义表的特点E=(a,E)=(a,(a,E)=(a,(a,(a,.)，E为递归表为递归表1）A=()2）B=(e)3）C=(a,(b,c,d)4）D=(A,B,C)5）E=(a,E)n=0，因为因为A是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a 为原子，为
45、原子，(b,c,d)为子表为子表n=3，3个元素都是子表个元素都是子表n=2，a 为原子，为原子，E为子表为子表D=(A,B,C)=(),(e),(a,(b,c,d)，共享表共享表数据结构串、数组和广义表串、数组和广义表练习练习课堂练习课堂练习1、设有二维数组设有二维数组a68，每个元素占相邻的，每个元素占相邻的4个字节，存储个字节，存储器按字节编址，已知器按字节编址，已知a的起始地址是的起始地址是1000，试计算：，试计算：l数组数组a的最后一个元素的最后一个元素a57起始地址；起始地址；l按行序优先时，元素按行序优先时，元素a46起始地址；起始地址；l按列序优先时，元素按列序优先时，元素a46起始地址。起始地址。
