CC++ 经典算法实例.docx

CC++ 经典算法实例.docx

《CC++ 经典算法实例.docx》由会员分享，可在线阅读，更多相关《CC++ 经典算法实例.docx（9页珍藏版）》请在冰点文库上搜索。

CC++经典算法实例

2008-03-1718:

30

二分查找的代码.

intbfind（int*a,intlen,intval）

{

   intm=len/2;

   intl=0;

   intr=len;

   while（l!

=m&&r!

=m）

   {

       if（a[m]>val）

       {

           r=m;

           m=（m+l）/2;

       }

       elseif（a[m]

       {

           l=m;

           m=（m+r）/2;

       }

       else

           returnm;

   }

   return-1;  //没有找到

}

写出在母串中查找子串出现次数的代码.

intcount1（char*str,char*s）

{

   char*s1;

   char*s2;

   intcount=0;

   while（*str!

='\0'）

   {

       s1=str;

       s2=s;

       while（*s2==*s1&&（*s2!

='\0'）&&（*s1!

='0'））

       {

           s2++;

           s1++;

       }

       if（*s2=='\0'）

           count++;

       str++;

   }

   returncount;

}

查找第一个匹配子串位置,如果返回的是s1长度len1表示没有找到

size_tfind（char*s1,char*s2）

   {

       size_ti=0;

        size_tlen1=strlen（s1）

       size_tlen2=strlen（s2）;

       if（len1-len2<0）returnlen1;

       for（;i       {

           size_tm=i;

           for（size_tj=0;j           {

               if（s1[m]!

=s2[j]）

                   break;

               m++;

           }

           if（j==len）

               break;

       }

       returni   }

写出快速排序或者某种排序算法代码

快速排序:

intpartition（int*a,intl,intr）

{

   inti=l-1,j=r,v=a[r];

   while

（1）

   {

       while（a[++i]       while（a[--j]>v）if（j<=i）break;

       if（i>=j）

           break;

       swap（a[i],a[j]）;

   }

   swap（a[i],a[r]）;

   returni;

}

voidqsort（int*a,intl,intr）

{

   if（l>=r）return;

   inti=partition（a,l,r）;

   qsort（a,l,i-1）;

   qsort（a,i+1,r）;

}

冒泡排序:

voidbuble（int*a,intn）

{

   for（inti=0;i   {

       for（intj=1;j       {

           if（a[j]           {

               inttemp=a[j];

               a[j]=a[j-1];

               a[j-1]=temp;

           }

       }

   }

}

插入排序：

voidinsertsort（int*a,intn）

{

   intkey;

   for（intj=1;j   {

       key=a[j];

       for（inti=j-1;i>=0&&a[i]>key;i--）

       {

           a[i+1]=a[i];

       }

       a[i+1]=key;

   }

}

出现次数相当频繁

实现strcmp函数

intstrcmp11（char*l,char*r）

{

   assert（l!

=0&&r!

=0）;

   while（*l==*r&&*l!

='\0'）l++,r++;

   if（*l>*r）

       return1;

   elseif（*l==*r）

       return0;

   return-1;

}

实现字符串翻转

voidreserve（char*str）

{

   assert（str!

=NULL）;

   char*p1=str;

   char*p2=str-1;

   while（*++p2）;        //一般要求不能使用strlen

   p2-=1;

   while（p1   {

       charc=*p1;

       *p1++=*p2;

       *p2--=c;

  }

}

将一个单链表逆序

structlist_node

{

   list_node（inta,list_node*b）:

data（a）,next（b）//这个为了测试方便

   {}

   intdata;

   list_node*next;

};

voidreserve（list_node*phead）

{

       list_node*p=phead->next;

       if（p==NULL||p->next==NULL）return;//只有头节点或一个节点

       list_node*p1=p->next;

       p->next=NULL;

       while（p1!

=NULL）

       {

           p=p1->next;

           p1->next=phead->next;

           phead->next=p1;

           p1=p;

       }

}

测试程序：

   listlt;

   lt.phead=newlist_node（0,0）;

   lt.phead->next=newlist_node（1,0）;

   lt.phead->next->next=newlist_node（2,0）;

   lt.phead->next->next->next=newlist_node（3,0）;

   lt.reserve（）;

   list_node*p=lt.phead;

   while（p）

   {

       coutnext;

   }

循环链表的节点对换和删除。

//双向循环

list_node*earse（list_node*node）

{

   //if（node==rear）returnnode->next;   //对于头节点可判断也可不判断。

最好加上

   list_node*next=node->next;

   next->prev=node->prev;

   node->prev->next=next;

   deletenode;

   retrunnext;

}

//单项循环

list_node*earse（list_node*node）

{

   //if（node==rear）returnnode->next;   //对于头节点可判断也可不判断。

最好加上

   list_node*p=rear;

    while（p->next!

=node）p=p->next;

    p->next=node->next;

   deletenode;

   retrunp->next;

}

将一个数字字符串转换为数字."1234"-->1234

intatoii（char*s）

{

   assert（s!

=NULL）;

   intnum=0;

   inttemp;

   while（*s>'0'&&*s<'9'）

   {

       num*=10;

       num+=*s-'0';

       s++;

   }

   returnnum;

}

出现次数相当频繁

.实现任意长度的整数相加或者相乘功能。

voidbigadd（char*num,char*str,intlen）

{

   for（inti=len;i>0;i--）

   {

       num[i]+=str[i];

       intj=i;

       while（num[j]>=10）

       {

           num[j--]-=10;

           num[j]+=1;

       }

   }

}

.写函数完成内存的拷贝

void*memcpy（void*dst,constvoid*src,unsignedintlen）

{

   registerchar*d;

   registerchar*s;

   if（len==0）

       returndst;

   if（dst>src）  //考虑覆盖情况

   {

       d=（char*）dst+len-1;

       s=（char*）src+len-1;

       while（len>=4）  //循环展开，提高执行效率

       {

           *d--=*s--;

           *d--=*s--;

           *d--=*s--;

           *d--=*s--;

           len-=4;

       }

       while（len--）

       {

           *d--=*s--;

       }

   }

   elseif（dst

   {

       d=（char*）dst;

       s=（char*）src;

       while（len>=4）

       {

           *d++=*s++;

           *d++=*s++;

           *d++=*s++;

           *d++=*s++;

           len-=4;

       }

       while（len--）

       {

           *d++=*s++;

       }

   }

   returndst;

}

出现次数相当频繁

编写类String的构造函数、析构函数和赋值函数，已知类String的原型为：

classString

{    

public:

String（constchar*str=NULL）;//普通构造函数  

String（constString&other）;//拷贝构造函数

~String（void）;//析构函数

String&operate=（constString&other）;//赋值函数    

private:

char*m_data;//用于保存字符串    

};

解答：

//普通构造函数

String:

:

String（constchar*str）

{

      if（str==NULL）

      {

              m_data=newchar[1];//得分点：

对空字符串自动申请存放结束标志'\0'的空

                                 　//加分点：

对m_data加NULL判断

             *m_data='\0';

      }  

      else

      {

       intlength=strlen（str）;

       m_data=newchar[length+1];//若能加NULL判断则更好

       strcpy（m_data,str）;

      }

}

//String的析构函数

String:

:

~String（void）

{

      delete[]m_data;//或deletem_data;

}

//拷贝构造函数

String:

:

String（constString&other）　　　//得分点：

输入参数为const型

{   

      intlength=strlen（other.m_data）;

      m_data=newchar[length+1];　　　　//加分点：

对m_data加NULL判断

      strcpy（m_data,other.m_data）;  

}

//赋值函数

String&String:

:

operate=（constString&other）//得分点：

输入参数为const型

{   

      if（this==&other）                　　//得分点：

检查自赋值

              return*this;

      delete[]m_data;          　　　　//得分点：

释放原有的内存资源

      intlength=strlen（other.m_data）;    

      m_data=newchar[length+1];　//加分点：

对m_data加NULL判断

      strcpy（m_data,other.m_data）;

      return*this;   　　　　　　　　//得分点：

返回本对象的引用

}

剖析：

能够准确无误地编写出String类的构造函数、拷贝构造函数、赋值函数和析构函数的面试者至少已经具备了C++基本功的60%以上！

在这个类中包括了指针类成员变量m_data，当类中包括指针类成员变量时，一定要重载其拷贝构造函数、赋值函数和析构函数，这既是对C++程序员的基本要求，也是《Effective　C++》中特别强调的条款。

实现strcpy

char*strcpy（char*strDest,constchar*strSrc）

{

assert（（strDest!

=NULL）&&（strSrc!

=NULL））;

char*address=strDest;

while（（*strDest++=*strSrc++）!

=‘\0’）;

returnaddress;

}

编写一个函数，作用是把一个char组成的字符串循环右移n个。

比如原来是“abcdefghi”如果n=2，移位后应该是“hiabcdefgh”

函数头是这样的：

//pStr是指向以'\0'结尾的字符串的指针

//steps是要求移动的n

voidLoopMove（char*pStr,intsteps）

{

//请填充...

}

解答：

正确解答1：

voidLoopMove（char*pStr,intsteps）

{

   intn=strlen（pStr）-steps;

   chartmp[MAX_LEN];  

   strcpy（tmp,pStr+n）;

   strcpy（tmp+steps,pStr）;  

   *（tmp+strlen（pStr））='\0';

   strcpy（pStr,tmp）;

}

正确解答2：

voidLoopMove（char*pStr,intsteps）

{

   intn=strlen（pStr）-steps;

   chartmp[MAX_LEN];  

   memcpy（tmp,pStr+n,steps）;

   memcpy（pStr+steps,pStr,n）;   

   memcpy（pStr,tmp,steps）;  

}