//对串的所有操作都可以通过以下五个基本函数实现
int StrAssign(String * , char * );//串赋值
int StrLength(String);//求串长
int StrCompare(String , String );//串比较
int StrCombine(String* , String , String );//串连接
int StrSub(String *, String , int , int );//求子串
9．已知如下程序段
FOR i:= n  DOWNTO  1  DO        {语句1}
BEGIN
x:=x+1；                      {语句2}
FOR j:=n  DOWNTO  i  DO  {语句3}
y:=y+1;                    {语句4}
END；
语句1执行的频度为 （1） ；语句2执行的频度为 （2） ；语句3执行的频度为 （3） ；语句4执行的频度为 （4） 。【北方交通大学 1999  二、4（5分）】
（1）n  n+1
（2）n n
（3）n  n+2
（4）n*(n+1)/2  n+1
3）n(n+3)/2  （4）n(n+1)/2
10．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）
  FOR  i：＝１ TO  n　DO　
  FOR  j：＝１　TO  i　DO
　        FOR　k：＝1　TO　j　DO　
ｘ：＝ｘ＋delta；
9．（1）n+1  （2）n  （3）n(n+3)/2  （4）n(n+1)/2。
10．1+（1+2）+（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6  O(n3)
简述以下算法的功能：
3.4.1
Status algo1(Stack S){
Int i,n,A[255];
n=0;
while(!StackEmpty(S)){n++;Pop(S,A[n]);};
for(i=1;i<=n;i++) Push(S,A[i]);
}
3.4.2
Status algo2(Stack S,int e){
Stack T;int d;
InitStack(T);
While(!StackEmpty(S)){
Pop(S,d);
If(d!=e) Push(T,d);
}
while(!StackEmpty(T)){
Pop(T,d);
Push(S,d);
}
}
3.9 试将下列递推过程改写为递归过程。
Void ditui(int n){
int i;   
i=n;
while(i>1)
  printf(i--);
}
Void digui(int j)
{
if(j>1){
  printf(j);
  digui(j-1);
}
}
3.10 试将下列递归过程改为非递归过程
void test(int &sum){
int x;
scanf(x);
if(x==0) sum=0;
else{test(sum);sum+=x;}
printf(sum);
}
Void test(int &sum)
{
Stack S;
  int x;
scanf(x);
InitStack(S);
while(x){
Push(S,x);
scanf(x);
}
sum=0;
printf(sum);
while(Pop(S,x)){
sum+=x;
printf(sum);
}
}
2.10
Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素
{
  if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
  for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件
    a.elem[i+count-1]=a.elem[i+count+k-1];
  a.length-=k;
  return OK;
}//DeleteK
2.23
void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
{
  p=A->next;q=B->next;C=A;
  while(p&&q)
  {
    s=p->next;p->next=q; //将B的元素插入
    if(s)
    {
      t=q->next;q->next=s; //如A非空,将A的元素插入
    }
    p=s;q=t;
  }//while
}//merge1
3.22
int GetValue_NiBoLan(char *str)//对逆波兰式求值
{
  p=str;InitStack(s); //s为操作数栈
  while(*p)
  {
    if(*p是数) push(s,*p);
    else
    {
      pop(s,a);pop(s,b);
      r=compute(b,*p,a); //假设compute为执行双目运算的过程
      push(s,r);
    }//else
    p++;
  }//while
  pop(s,r);return r;
}//GetValue_NiBoLan
4.10
void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r
{
  StrAssign(r,''); //初始化r为空串
  for(i=Strlen(s);i;i--)
  {
    StrAssign(c,SubString(s,i,1));
    StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中
  }
}//String_Reverse
4.11
void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r
{
  StrAssign(r,'');
  for(i=1;i<=Strlen(s);i++)
  {
    StrAssign(c,SubString(s,i,1));
    for(j=1;j<i&&StrCompare(c,SubString(s,j,1));j++); //判断s的当前字符c是否第一次出现
    if(i==j)
    {
      for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中
      if(k>Strlen(t)) StrAssign(r,Concat(r,c));
    }
  }//for
}//String_Subtract
//////////////////////////////
//函数功能：串赋值
//初始条件：H->ch所分配的内存已被释放
//////////////////////////////
int StrAssign(String * H, char * s)
{
if(!H->ch) 
{
free(H->ch);
H->ch=NULL;
}
int i;
for(i=0;s[i]!='\0';i++);
if(!i)
{
H->ch=NULL;
H->length=0;
}
else 
{
H->ch=(char *)malloc(sizeof(char)*(i+1));
if(!H->ch)
{
printf("ORERFLOW!");
return FALSE;
}
for(int j=0; j<=i; j++)
*(H->ch+j)=s[j];
H->length=i;
}
return TRUE;
}
//////////////////////////////
//函数功能：求串长
//初始条件：
//////////////////////////////
int StrLength(String H)
merge函数
{
return H.length;
}
//////////////////////////////
//函数功能：串比较(S>T返回值大于0)
//初始条件：
//////////////////////////////
int StrCompare(String S, String T)
{
for(int i=0; i<S.length && i<S.length; i++)
if(S.ch[i]!=T.ch[i])
return S.ch[i]-T.ch[i];
return S.length - S.length;
}
//////////////////////////////
//函数功能：串连接
//初始条件：H->ch所分配的内存已被释放
//////////////////////////////
int StrCombine(String* H, String s1, String s2)
{
if(!H->ch) 
{
free(H->ch);
H->ch=NULL;
}
H->ch=(char*)malloc(sizeof(char)*(s1.length+s2.length+1));
if(!H->ch)
{
printf("OVERFLOW!");
return FALSE;
}
for(int i=0;i<s1.length;i++)
{
*(H->ch+i)=*(s1.ch+i);
}
for(int j=s1.length; j<=s1.length+s2.length; j++)
{
*(H->ch+j)=*(s2.ch+j-s1.length);
}
H->length=s1.length+s2.length;
return TRUE;
}
//////////////////////////////
//函数功能：求子串
//初始条件：Sub->ch所分配的内存已被释放
//////////////////////////////
//用Sub返回串s的第pos个字符起长度为len的子串。其中，1<=pos<=StrLength(s)且0<=len<=StrLength(s)-pos+1。
int StrSub(String *Sub, String s, int pos, int len)
{
if(pos<1 || pos>StrLength(s) || len<0 || len>StrLength(s)-pos+1)
return FALSE;
if(!len)
StrInit(Sub);
else
{
if(!Sub->ch) 
{
free(Sub->ch);
Sub->ch=NULL;
}
Sub->ch=(char*)malloc(sizeof(char)*(len+1));
if(!Sub->ch)
{
printf("OVERFLOW!");

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。