网上找的一些字符串和稀疏矩阵

1、字符串及稀疏矩阵、广义表一、字符串的存储及操作运算1、字符串变量、字符数组：顺序存储，链接表结构顺序存储 ：每个字符占用一个字节（8位二进制），一般用字符数组或字符串变量。字符串变量相当于一维的字符数组 字符串变量：var st1 :array 1.15 of char ; 表示固定长度存储 var st2 : string 15 ; 非固定长度，最长=15 (3) 链接表结构 ： type point = node node= record ch : char ; next : point ; end; A da next2、字符串运算：（1）连接运算：将两个字符串首尾相连成一个字符串（2）

2、取子串运算：从第i 个位置开始，取n个字符（3）删除子串运算：从第i 个位置开始，删除n个字符（4） 插入子串运算：插入到某个位置（5）求子串的位置：用回溯算法实现求子串的位置。字符串的连接运算 ： 将第二个字符串合并到第一个字符串尾部其它操作可以利用pascal 的过程与函数Pascal 字符串过程与函数(1) 字符串合并 ： st : =concat(s1,s2,s3, sn) ;截取子字符串 ：st:= copy(s1 , pos , len ) ;删除一个子串： delete( s1 , pos , len ) ;插入子串 ： st:= (s1, d , pos ) 从某位开始插入d

3、字符串 求字符串长度 ： len := length( s1) ; 求子串的位置 问题分析：读入两个字符串：ch1,ch2求ch2在ch1中的位置：例如：ch1= a b s y t k n m s x t h j k , ch2= s x t I=1 j=1 ch1i ch2j 开始做：i：=I+1 ;直到 ch1 I = ch21 a b s x y t k n m s x t h j k s x t I=3 j=1 I=5, j=3 不相等, 则I回到上一个位置 I= I-j +2 j=1 (3) 当jL2则输出子串位置 : I- L2 即为子串的位置。程序如下： type pstr=r

4、ecord vec : string ; len: integer ; end ; var r1,r2 : pstr ; y, l1,l2 : integer ; function pos(r1, r2 :pstr): integer ; var x, j : integer ; begin x:=1 ; j:=1; Whtile (x=r1.len ) and ( jr2.len then pos:= x r2.len else pos:=0 ;End ; begin (1) 输入字符串 1 (2) 输入字符串 2 (3) 分别计算两个字符串的长度 (4) 调用函数 y:= pos( r1,

5、 r2 ) (5) 输出 Y 的值 二、应用：例题1， 求n个字符串的最长公共子串（n20,字符串的长度=1) do begin I:=1 ; while not(found) and ( I= min-len+1) do Begin for j:=1 to len do longestj:= chI+j-1 ; longest0:=chr(len) ; found := true ; k:=1 ; while found and (k=n) do begin if not(check(longest,strk) then found :=false ; k:=k+1 ; end; if k=

6、 n then found :=false ; I:=I+1 ; end ; len:=len-1 ;End ; If found then 输出最长公共子串 else 没有公共子串二、稀疏矩阵1、矩阵中非零元素的个数远远少于零元素的个数，这样的矩阵称为非零矩阵。2、存储方法：三元组存储法，设稀疏矩阵按行、列号从小到大顺序排列。如书图（3-16），变为一个线性表 顺序存储(1) 用一个二维数组A0.m ,1.3 : integer (2) 存储方法：a0,1存放非零元素个数，a0,2总行数 a0,3存放总列数 (3) 按行存放：每个非零元素所在行、列数以及值（p.72) 链接存储：设定一个一维的指针记录数组每个单元是一个链表，链接是本行的非零元素（p.73）3、稀疏矩阵运算：转置运算（p.75) 转置运算优化（快速转置, p.75）加法运算(p.76)三、广义表：1、 定义：广义表可以是一个空表，也可以非空表，其元素可以是某个确定类型的对象，也可以是由元素组成的表。即可以是元素或子表。 例如：A=（） ，B=（e), C=(a, ( b, c ,d ) D=(A ,B , C )=( ( ) ,(e) , ( a, ( b,c,d ) ) p.78 图 2、存储结构：用动态链接表表示：Type node =record tag : 0.1; 标记，0元素，1