(2025年)数据结构(C语言)课后习题答案之串、数组和广义表

(2025年)数据结构(C语言)课后习题答案之串、数组和广义表串部分习题解答习题1：已知模式串为“abacab”，主串为“aabacababac”，要求：（1）计算模式串的next数组；（2）使用KMP算法找出主串中所有与模式串匹配的起始位置（下标从0开始）。（1）计算next数组步骤如下：模式串记为p[0..5]（长度6），next数组长度与模式串相同，定义next[0]=-1（表示无真前缀）。-next[1]：p[0]与p[1]（'a'与'b'）不相等，最长相等前缀后缀长度为0，故next[1]=0。-next[2]：比较p[0]与p[2]（'a'与'a'），相等，故最长相等前缀后缀长度为1，next[2]=1。-next[3]：比较p[next[2]]（p[1]='b'）与p[3]（'c'），不相等；继续回退到next[next[2]]=next[1]=0，比较p[0]与p[3]（'a'与'c'），不相等，故最长相等前缀后缀长度为0，next[3]=0。-next[4]：比较p[next[3]]（p[0]='a'）与p[4]（'a'），相等，故最长相等前缀后缀长度为1（next[3]+1），next[4]=1。-next[5]：比较p[next[4]]（p[1]='b'）与p[5]（'b'），相等，故最长相等前缀后缀长度为2（next[4]+1），next[5]=2。综上，next数组为[-1,0,1,0,1,2]。（2）KMP匹配过程：主串s[0..10]：'a','a','b','a','c','a','b','a','b','a','c'；模式串p[0..5]。初始化i=0（主串指针），j=0（模式串指针）。-i=0，j=0：s[0]='a'=p[0]，i=1，j=1。-i=1，j=1：s[1]='a'≠p[1]='b'，j=next[1]=0。-i=1，j=0：s[1]='a'=p[0]，i=2，j=1。-i=2，j=1：s[2]='b'=p[1]，i=3，j=2。-i=3，j=2：s[3]='a'=p[2]='a'，i=4，j=3。-i=4，j=3：s[4]='c'=p[3]='c'，i=5，j=4。-i=5，j=4：s[5]='a'=p[4]='a'，i=6，j=5。-i=6，j=5：s[6]='b'=p[5]='b'，i=7，j=6（j=6等于模式串长度，匹配成功，记录起始位置i-j=7-6=1？需检查：i=6时j=5，匹配后j=6，此时i=7，起始位置应为i-j=7-6=1？实际主串从i=1开始：i=1时j=0开始匹配，到i=6时j=5完成，起始位置是i-j=6-5=1？此处需修正：当j=6时表示模式串完全匹配，此时主串的起始位置是i-j=6-5=1（因为i在匹配完成后递增到7，而j=6，所以正确起始位置是i-j=7-6=1）。继续匹配：j=next[5]=2，i=7。-i=7，j=2：s[7]='a'=p[2]='a'，i=8，j=3。-i=8，j=3：s[8]='b'≠p[3]='c'，j=next[3]=0。-i=8，j=0：s[8]='b'≠p[0]='a'，i=9，j=0。-i=9，j=0：s[9]='a'=p[0]，i=10，j=1。-i=10，j=1：s[10]='c'≠p[1]='b'，j=next[1]=0。-i=10，j=0：s[10]='c'≠p[0]='a'，i=11（超出主串长度），结束。最终匹配位置为起始下标1和可能的其他位置？需重新检查：第一次匹配成功时，i=6（s[6]='b'是模式串最后一个字符），此时j=5，匹配完成，起始位置为i-j=6-5=1。继续匹配时，j回退到next[5]=2，i=7，s[7]='a'=p[2]，j=3；s[8]='b'≠p[3]，j=next[3]=0；i=8，s[8]='b'≠p[0]，i=9；s[9]='a'=p[0]，j=1；s[10]='c'≠p[1]，j=0；i=11结束。因此仅找到一个匹配位置：下标1。数组部分习题解答习题2：设有一个二维数组A[10..20][5..15]，每个元素占4个存储单元，基址为1000。若按行优先顺序存储，求元素A[15][10]的存储地址。分析：二维数组的行优先存储地址计算公式为：LOC(i,j)=基址+((i-下界1)列数+(j-下界2))元素大小其中，行下界为10，行上界为20，行数=20-10+1=11；列下界为5，列上界为15，列数=15-5+1=11。对于A[15][10]，i=15，j=10：行偏移量=i-行下界=15-10=5列偏移量=j-列下界=10-5=5总偏移量=行偏移量列数+列偏移量=511+5=60存储地址=1000+604=1000+240=1240。习题3：已知对称矩阵A[4][4]（下标从0开始），采用压缩存储方式存储其下三角部分（包括对角线）于一维数组B中，B的下标从0开始。求元素A[2][3]在B中的位置。分析：对称矩阵满足A[i][j]=A[j][i]，压缩存储下三角部分时，仅存储i≥j的元素。对于i<j的元素A[i][j]，其值等于A[j][i]，因此在一维数组中的位置与A[j][i]相同。下三角部分元素的一维数组下标计算公式为：k=i(i+1)/2+j（i≥j）。对于A[2][3]，i=2<j=3，因此需转换为A[3][2]（i=3≥j=2）。计算k=3(3+1)/2+2=34/2+2=6+2=8。因此，A[2][3]在B中的位置为8。广义表部分习题解答习题4：已知广义表L=(a,(b,(c,d)),e)，要求：（1）求L的长度和深度；（2）指出L的表头和表尾；（3）画出L的头尾链表存储结构（原子节点用圆形，子表节点用方形）。（1）长度：广义表中直接元素的个数。L的直接元素为a、(b,(c,d))、e，共3个，故长度为3。深度：广义表中括号的最大嵌套层数。L的最内层括号是(c,d)，嵌套层数为2（外层是(b,(c,d))的括号，内层是(c,d)的括号），加上最外层的括号，总深度为3（或按定义：原子深度为1，空表深度为1，子表深度为子表深度+1）。具体分析：a的深度为1，(b,(c,d))的深度为1+max(1,2)=3？不，正确计算方式是：广义表的深度是各元素深度的最大值加1（外层括号）。原子深度为1，子表的深度是其自身深度。例如，(c,d)的深度是2（两个原子，外层括号），(b,(c,d))的深度是1+max(1,2)=3？实际标准定义是：广义表的深度是展开后括号的最大层数。L展开为：-最外层：(a,(b,(c,d)),e)→第1层-子表(b,(c,d))→第2层-子表(c,d)→第3层因此，L的深度为3。（2）表头：广义表的第一个元素，即a。表尾：广义表除去第一个元素后剩余元素组成的广义表，即((b,(c,d)),e)。（3）头尾链表存储结构：-广义表L的头节点为子表节点（方形），hp指向表头a（原子节点，圆形），tp指向表尾((b,(c,d)),e)的子表节点。-表尾((b,(c,d)),e)的头节点为子表节点，hp指向(b,(c,d))的子表节点，tp指向e的原子节点。-(b,(c,d))的头节点为子表节点，hp指向b（原子节点），tp指向(c,d)的子表节点。-(c,d)的头节点为子表节点，hp指向c（原子节点），tp指向d（原子节点）。习题5：广义表M=((()),a,(b,(c)))，求其长度、深度，并判断是否为递归表。长度：直接元素个数为3（((())),a,(b,(c))），故长度3。深度：展开后括号层数：-((()))→3层括号（最内层空表？不，((()))的展开是：最外层括号（第1层），内层括号（第2层），最内层括号（第3层），其中最内层括号内无元素，为空表，但空表深度为1。因此((()))的深度为3。-a的深度为1。-(b,(c))的深度为2（外层括号第1层，内层(c)的括号第2层）。因此，M的深度为max(3,1,2)=3。递归表判断：递归表是指表中某子表直接或间接包含自身。M中所