19. 例4、for(I=1;I<=n;++I)
for(j=1;j<=n;++j)
{++x;s+=x;}
语句频度为:2n2
其时间复杂度为:O(n2)
即时间复杂度为平方阶。
定理:若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式,则A(n)=O(n m)
证略。
例5for(i=2;i<=n;++I)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
59. 上述算法里动态申请新结点空间时未加错误处理,可作下列处理:
p=(listnode*)malloc(sizeof(listnode))
if(p==NULL)
error(〝No space for node can be obtained〞);
return ERROR;
以上算法的时间复杂度均为O(n)。
104. 0 1 2 3 0 1 2 3 b c front rear front
rear (c) a出队 (d) b,c出队,队为空
和栈类似,队列中亦有上溢和下溢现象。此外,顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中,头尾指针只增加不减小,致使被删除元素的空间永远无法重新利用。因此,尽管队列中实际的元素个数远远小于向量空间的规模,但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
124. 串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号,定义为子串在主串中的序号(或位置)。例如,设A和B分别为
A=“This is a string” B=“is”
则B是A的子串,A为主串。B在A中出现了两次,其中首次出现所对应的主串位置是3。因此,称B在A中的序号(或位置)为3
特别地,空串是任意串的子串,任意串是其自身的子串。
通常在程序中使用的串可分为两种:串变量和串常量。串常量和整常数、实常数一样,在
148. 其算法段为:
for(i=0;i<=n-m;i++){
if(S[i..i+m-1]=T[0..m-1]
return i;
下面以第二种定长的顺序串类型作为存储结构,给出具体的串匹配算法。
int index(sstring s,sstring t,int pos){
int i,j,k;
int m=s.length;
int n=t.length;
for(i=0;i<=n-m;i++){
j=0;k=i;