第五章数组字符串集合类.ppt

{ int Bnubmer = 0; for(k=0;kCols;k++) for(i=0;iCount;i++) if(smArray[i].col==k) { b.smArray[Bnumber].row=k; b.smArray[Bnumber].col= smArray[i].row; b.smArray[Bnumber].value= smArray[i].value; Bnumber++;} } return b; // 返回转置矩阵 b } b[0] b[1] b[2] b[3] b[4] b[5] 0 0 50 3 0 -30 1 0 10 3 3 5 3 2 -60 1 2 20 a[0] a[1] a[2] a[3] a[4] a[5] 0 0 50 2 1 20 0 1 10 3 3 5 2 3 -60 0 3 -30 2 十字链表 ?矩阵的元素结构如下：分别表示该元素的左邻非零元素、上邻非零元素、所在的行、所在的列和它的值。 [例] 稀疏矩阵? LEFT UP ROW COL VAL 矩阵的每一行、每一列都设置为由一个表头结点引导的循环链表，并且各行和各列的表头结点有如下特点： -1 = COL（Loc（BASEROW[i]）） 0 -1 = ROW（Loc（BASECOL[j]）） 0 [例] “主步骤”操作：要求主行主列元素非零。 ? 主行 别列 主列 别行 a c … . . . … . . . . . . b d … . . . … . . . . . . … … 变换前 主行 别列 主列 别行 1/a … . . . … . . . . . . b/a d-bc/a … . . . … . . . . . . … -c/a 变换后 5.2 字符串 5.2.1 串的定义和操作 ● 串的定义：串是零个或多个字符组成的有限序 列。 记为 S ＝ “a0a1… an-1”，串名 串值 串的长度 ● 空串：长度为零的串称为空串。 ● 空白串：由一个或多个空格组成的串称为空白 串。 子串：串中任意个连续字符组成的子序列称为该串的子串。 主串：包含子串的串相应地称为主串。 子串在主串中的位置：子串在主串中第一次出现时，子串第一个字符在主串中的序号。 [例] A = “This is a string” B = “is” 类String的串运算 [1] ??? 关系运算符 ，= ， ， = ，= = ，!= 的重载. [2] ??? 串拼接运算符的重载. [3] ? 从start位置确定字符c的位置： 函数int Find （char c，int start）const [4] ? 确定字符c最后一次出现的位置： 函数int FindLast（char c） const [5] ??取子串： 函数String Substr（int index，int count） const [6] ??? 在index处插入字符串s： 函数void Insert（const String s，int index） …… 5.2.2 串的存储方式 1 串的顺序存储：把一个串所包含的字符序列相继存入连续的字节中 ● 非紧缩格式 // 一个存储单元存放一个字符 [例] S ＝ “a0a1… an-1” a0 a1 an-1 Word 0 Word 1 Word n-1 … … … … a ● 紧缩格式 // 一个存储单元存放多个字符 [例] S=“a0a1… an-1” // 一个存储单元存放4个字符 a1 a4 an-1 Word 0 Word 1 … … a0 a2 a3 a5 a6 a7 an-2 Word n/4 -1 … … a 2 串的链式存储串的链接存储是把可用的存储空间分成一系列大小相同的结点，其中每个结点的结构为： （str, link） 5 c h i n a ∧ p ● 结点大小为4的链 S