第四章串和数组2011

ring s, SString t)
/*若串s和t相等则返回0；若s>t则返回正数；若s<t则返 回负数*/
{ int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]);
初 始 条 件 : 串 S 存 在 ,1≤pos≤StrLength(S) 且 1≤len≤StrLength(S)-pos+1
操作结果:用Sub返回串S的第pos个字符起长度为len的子串
返回主目录
（11）StrIndex(S,T,pos)
初始条件: 串S和T存在,T是非空串, 1≤pos≤StrLength(S)
return(s.len); }
返回主目录
（7）清空函数
StrClear(SString *s) /*将串s置为空串*/ {
s->len=0; }
返回主目录
（8）连接函数
(1) 连接后串长≤MAXLEN，则直接将B加在A的 后面。 (2) 连接后串长>MAXLEN且LA<MAXLEN，则B 会有部分字符被舍弃。 (3) 连接后串长>MAXLEN且LA=MAXLEN，则B 的全部字符被舍弃（不需连接）。
for (i=s->len + t.len-1;i>=t.len + pos;i--)
s->ch[i]=s->ch[i-t.len];
for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i];
s->len=s->len+t.len;

an1ij n mkin
j1 kj1
n维数组
LO [j1 ,j2 C , ,jn ] LO [0 ,0 , C ,0 ] nc iji L i 1
c n L ,c i 1 b i c i,1 i n
练习 设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0]存放位置在644(10)，A[2][2]存放位置 在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列。 然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否 则没有感染。 例如，假设病毒的DNA序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba， 则未感染。 （注意，人的DNA序列是线性的，而病毒的DNA序列是环状的)
}
BF算法时间复杂度
例： S=‘0000000001’，T=‘0001’，pos=1
若n为主串长度，m为子串长度，最坏情况是 ✓主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次 ✓最后m位也各比较了1次
总次数为：(n-m)*m+m＝(n-m+1)*m 若m<<n，则算法复杂度O(n*m)
R {a ,a 1
j1jijn j1ji 1jn
|
0jk bk 1, 1kn,且ki,
0ji bk 2, aj1jijn,aj1ji1jn D,i 2,,n}
基本操作:
(1) InitArray (&A,n,bound1, boundn)
//构造数组A
(2) DestroyArray (&A)

❖串赋值 StrAssign ❖串比较 StrCompare ❖求串长 StrLength ❖串联接 Concat ❖求子串 SubString
最小操作子集
算法4.1
int Index(String s, String T, int Pos){ if(pos>0){ n=StrLength(s); m=StrLength(T); i=pos; while (i<=n-m+1) { SubString(sub,s,I,m); If ( StrCompare(sub,T) != 0 ) ++ i; else return i; //返回子串在主串中的位置 }//while
串是由零个或多个字符组成的有限序列。 s= ‘a1a2…an ‘ (n≥0)
其中：s为串名； a1a2…an是串的值； 可以是字母、数字或其他字符； 字符串字符的数目n称为串的长度。
❖零个字符的串称为空串（Null String） ，长 度为0；以两个相邻的单引号来表示：
❖ s= ’’；
❖由若干个空格字符组成的串称为空格串，如： s= ’ ’；空格应计入串的长度中，如： s= ’It’s cool!’的长度为10。
❖假设S1,S2和T都是SString型的串变量,且串 T是由串S1联结串S2得到的,即串T的值的前 一段和串S1的值相等,串T的值的后一段和 串S2的值相等,则只要进行相应的"串值复制 "操作即可,对超长部分实施"截断"操作.
❖以下是串联接可能出现的三种情况:
S1 S2 T
aea
bf b
c \0 c
第4章 串
第四章 串
❖
4.1 串及基本运算
❖

min_p=j;} printf(“the min is%d,position %d”,min,min_p);
} (5)数组在内存中的存放 例如 int data[3]；则在内存中的状态如下：
1000 1002
1004
data[0] data[1] data[2]
讨论、思考题、作业： 实验指导书习题
f[0]=1；f[1]=1；f[2]=f[0]+f[1]；f[3]=f[2]+f[1]；依次类推找出 公式为： f[i]=f[i-1]+f[i-2]； 循环语句为：for(i=2;i<20;i++) 程序代码: main（）
{ int i;
static int f［20］=｛1，1｝;
/*定义 20 个元素的数组
参考资料（含参考书、文献等）：
叶斌 陈世强. C 语言程序设计. 北京：科学出版社 授课类型：理论课 讨论课□ 实验课□ 练习课□ 其他□ 教学方式：传统授课 双语□ 讨论□ 示教□ 指导□ 其他□ 教学资源：多媒体 模型□ 实物□ 挂图□ 音像□ 其他□
定义了一个二维数组 b，该数组由 9 个元素构成，其中每一个数组元素都属于浮点（实
数）数据类型。
数组
b
的各 个数据元 素依次
是:b[0][0],b[0][1],b[0][2],b[1][0],b[1][1],b[1][2],b[2][0],b[2][1],b[2][2]（注意：下标从 0-2）。
每个数组元素也都可以作为单个变量使用。
例如：int a［10］=｛0，0，0，0，0，0，0，0，0，0｝; 或 int a［10］;系统会对所有数
组元素自动赋 0 值。
4）在对全部数组元素赋初值时，可以不指定数组长度。