C/C++ 经典算法实例

二分查找的代码.

int bfind(int* a,int len,int val)

{

int m = len/2;

int l = 0;

int r = len;

while(l!=m && r!= m)

{

if(a[m] > val)

{

r = m;

m = (m+l)/2;

}

else if(a[m] < val)

{

l = m;

m = (m+r)/2;

}

else

return m;

}

return -1;   //没有找到

}

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

int count1(char* str,char* s)

{

char* s1;

char* s2;

int count = 0;

while(*str!=”)

{

s1 = str;

s2 = s;

while(*s2 == *s1&&(*s2!=”)&&(*s1!=’0′))

{

s2++;

s1++;

}

if(*s2 == ”)

count++;

str++;

}

return count;

}

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

size_t find(char* s1,char* s2)

{

size_t i=0;

size_t len1 = strlen(s1)

size_t len2 = strlen(s2);

if(len1-len2<0) return len1;

for(;i        {

size_t m = i;

for(size_t j=0;j            {

if(s1[m]!=s2[j])

break;

m++;

}

if(j==len)

break;

}

return i    }

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

快速排序:

int partition(int* a,int l,int r)

{

int i=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]);

return i;

}

void qsort(int* a,int l,int r)

{

if(l>=r) return;

int i = partition(a,l,r);

qsort(a,l,i-1);

qsort(a,i+1,r);

}

冒泡排序:

void buble(int *a,int n)

{

for(int i=0;i    {

for(int j=1;j        {

if(a[j]            {

int temp=a[j];

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

a[j-1] = temp;

}

}

}

}

插入排序:

void insertsort(int* a,int n)

{

int key;

for(int j=1;j    {

key = a[j];

for(int i=j-1;i>=0&&a[i]>key;i–)

{

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

}

a[i+1] = key;

}

}

出现次数相当频繁

实现strcmp函数

int strcmp11(char* l,char* r)

{

assert(l!=0&&r!=0);

while(*l == *r &&*l != ”) l++,r++;

if(*l > *r)

return 1;

else if(*l == *r)

return 0;

return -1;

}

实现字符串翻转

void reserve(char* str)

{

assert(str != NULL);

char * p1 = str;

char * p2 = str-1;

while(*++p2);         //一般要求不能使用strlen

p2 -= 1;

while(p1    {

char c = *p1;

*p1++ = *p2;

*p2– = c;

}

}

将一个单链表逆序

struct list_node

{

list_node(int a,list_node* b):data(a),next(b) //这个为了测试方便

{}

int data;

list_node* next;

};

void reserve(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;

}

}

测试程序:

list lt;

lt.phead = new list_node(0,0);

lt.phead->next = new list_node(1,0);

lt.phead->next->next = new list_node(2,0);

lt.phead->next->next->next = new list_node(3,0);

lt.reserve();

list_node * p = lt.phead;

while(p)

{

cout<data<        p = p->next;

}

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

//双向循环

list_node* earse(list_node* node)

{

// if(node == rear) return node->next;    //对于头节点可判断也可不判断。最好加上

list_node* next = node->next;

next->prev = node->prev;

node->prev->next = next;

delete node;

retrun next;

}

//单项循环

list_node* earse(list_node* node)

{

// if(node == rear) return node->next;    //对于头节点可判断也可不判断。最好加上

list_node* p = rear;

while(p->next != node) p=p->next;

p->next = node->next;

delete node;

retrun p->next;

}

将一个数字字符串转换为数字.”1234″ –>1234

int atoii(char* s)

{

assert(s!=NULL);

int num = 0;

int temp;

while(*s>’0′ && *s<‘9’)

{

num *= 10;

num += *s-‘0’;

s++;

}

return num;

}

出现次数相当频繁

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

void bigadd(char* num,char* str,int len)

{

for(int i=len;i>0;i–)

{

num[i] += str[i];

int j = i;

while(num[j]>=10)

{

num[j–] -= 10;

num[j] += 1;

}

}

}

.写函数完成内存的拷贝

void* memcpy( void *dst, const void *src, unsigned int len )

{

register char *d;

register char *s;

if (len == 0)

return dst;

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–;

}

}

else if ( dst < src )

{

d = (char *)dst;

s = (char *)src;

while ( len >= 4 )

{

*d++ = *s++;

*d++ = *s++;

*d++ = *s++;

*d++ = *s++;

len -= 4;

}

while ( len– )

{

*d++ = *s++;

}

}

return dst;

}

出现次数相当频繁

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

class String

{

public:

String(const char *str = NULL); // 普通构造函数

String(const String &other); // 拷贝构造函数

~ String(void); // 析构函数

String & operate =(const String &other); // 赋值函数

private:

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

};

解答:

//普通构造函数

String::String(const char *str)

{

if(str==NULL)

{

m_data = new char[1]; // 得分点:对空字符串自动申请存放结束标志”的空

//加分点:对m_data加NULL 判断

*m_data = ”;

}

else

{

int length = strlen(str);

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

strcpy(m_data, str);

}

}

// String的析构函数

String::~String(void)

{

delete [] m_data; // 或delete m_data;

}

//拷贝构造函数

String::String(const String &other)    // 得分点:输入参数为const型

{

int length = strlen(other.m_data);

m_data = new char[length+1];     //加分点:对m_data加NULL 判断

strcpy(m_data, other.m_data);

}

//赋值函数

String & String::operate =(const String &other) // 得分点:输入参数为const型

{

if(this == &other)                   //得分点:检查自赋值

return *this;

delete [] m_data;               //得分点:释放原有的内存资源

int length = strlen( other.m_data );

m_data = new char[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, const char *strSrc )

{

assert( (strDest != NULL) && (strSrc != NULL) );

char *address = strDest;

while( (*strDest++ = * strSrc++) != ‘’ );

return address;

}

编写一个函数,作用是把一个char组成的字符串循环右移n个。比如原来是“abcdefghi”如果n=2,移位后应该是“hiabcdefgh”

函数头是这样的:

//pStr是指向以”结尾的字符串的指针

//steps是要求移动的n

void LoopMove ( char * pStr, int steps )

{

//请填充…

}

解答:

正确解答1:

void LoopMove ( char *pStr, int steps )

{

int n = strlen( pStr ) – steps;

char tmp[MAX_LEN];

strcpy ( tmp, pStr + n );

strcpy ( tmp + steps, pStr);

*( tmp + strlen ( pStr ) ) = ”;

strcpy( pStr, tmp );

}

正确解答2:

void LoopMove ( char *pStr, int steps )

{

int n = strlen( pStr ) – steps;

char tmp[MAX_LEN];

memcpy( tmp, pStr + n, steps );

memcpy(pStr + steps, pStr, n );

memcpy(pStr, tmp, steps );

}

Read: 1786

发表评论

电子邮件地址不会被公开。 必填项已用*标注