StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V));
StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串 i+=Strlen(V); //当前指针跳到插入串以后 n++; n++; }//if return n; }//Replace
分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下, 会引起不希望的后果,虽然在大多数情况下没有影响。
四、附加题
4.1 选择题
（ ）1. 串是一种特殊的线性表，其特殊性体现在：B Ａ．可以顺序存储 Ｂ．数据元素是一个字符 Ｃ．可以链式存储 Ｄ．数据元素可以是多个字符
（ ）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作：B Ａ．连接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串长
（ ）3. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：D
Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF
第5章 数组与广义表
一、基本内容
数组的类型定义和表示方式；特殊矩阵和稀疏矩阵的压缩存储方法以及运算的实现；广义表的逻辑结构和存储结构。
二、学习要点
1．了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 2．掌握对特殊矩阵进行压缩存储时的下标变换公式。
3．了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。
4．掌握广义表的结构特点及其存储表示方法，可根据自己的习惯，熟练掌握任意一种结构的链表。
三、基础知识题
5.1 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算： （1）数组A的体积（存储量）；
（2）末尾元素A57的第一个字节地址为；
（3）若按行存储时，元素A14的第一个字节地址为； （4）若按列存储时，元素A47的第一个字节地址为。 答：
（1）6*6*8=288 （2）1000+288-6=1282
（3）1000+((1-0)*8+(4-0))*6=1072 （4）1000+((7-0)*6+(4-0))*6=1276 5.10 求下列广义表操作的结果。 (1) GetHead[(p,h,w)] (2) GetTail[(b,k,p,h)] (3) GetHead[((a,b),(c,d))] (4) GetTail[((a,b),(c,d))]
(5) GetHead[GetTail[((a,b),(c,d))]] (6) GetTail[GetHead[((a,b),(c,d))]]
(7) GetHead[GetTail[GetHead[((a,b),(c,d))]]] (8) GetTail[GetHead[GetTail[((a,b),(c,d))]]]
答：(1) p (2) (k,p,h) (3) (a,b) (4) ((c,d)) (5) (c,d) (6) (b) (7) b (8) (d)
5.12 按教科书5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求它的深度。 （1）（（（）），a，（（b，c），（），d），（（（e））））； （2）（（（（a），b）），（（（），d），（e，f）））； 答：
（1）深度为4
（2）深度为4
四、附加题
4.1 用三元组表表示下列稀疏矩阵：
?00000000??00000000?02??0000????000090??03000800?????00000000??000000?? (2)?(1)? ?00060000?005000?????000000??00000000????00000005?000030?????20000000?答：
（1） {(3,2,3),(3,6,8),(5,4,6),(7,8,5),(8,1,2)} （2） {(1,6,-2),(2,5,9),(4,3,5),(6,5,3)}
第6章 树和二叉树
一、基本内容
二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构与二叉树的转换、遍历；树的多种应用。本章是课程的重点内容之一。
二、学习要点
1．熟练掌握二叉树的结构特性，了解相应的证明方法。 2．熟悉二叉树的各种存储结构的特点及适用范围。
3．遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。不仅要熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运算遍历算法实现二叉树的其他操作。层次遍历是按另一种搜索策略进行的遍历。
4．理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。
5．熟悉树的各种存储结构和特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其他操作的前提，要掌握1至2种建立二叉树和树的存储结构的方法。 6．了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。
三、基础知识题
6.1 已知一棵树边的集合为{
（9）树的深度是多少？ （10）以结点C为根的子树的深度是多少？
A B C H G D E F I M N J K L 答：（1） A （2）D,M,N,F,J,K,L (3）C （4）A,C
（5）J,K （6）I,M,N （7）E的兄弟是D,F的兄弟是G和H （8）2，5 （9）5 （10）3
