字符串操作

Q1:Write code to reverse a C-Style String.
Q2:Design an algorithm and wirte code to remove the duplicate characters in a string without using any additional buffer.

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

/**************************/
/*Reverse a C-style String*/
/**************************/
void reverse(char * str)
{
	char *end=str;
	char tmp;
	if(str)
	{
		while(*end)
			++end;
	}
	--end;
	while(str<end)
	{
		tmp=*str;
		*str++ = *end;
		*end--=tmp;
	}
}
/*********************************************/
/*Remove the duplicate characters in a string*/
/*********************************************/
/*No Additional Memory*/
static void removeDuplicates(char str[])
{
	if(str==NULL) return;
	int len=strlen(str);
	if(len<2) return;

	int tail=1;//tail指向未含重复字符的字符串的下一位,等待被赋值
	for(int i=1;i<len;++i)
	{
		//遍历一遍字符串
		int j;
		for(j=0;j<tail;++j)
		{
			//j遍历0-tail中指向的已统计的无重复字符
			if(str[i]==str[j]) break;//遇到重复的字符只是简单跳过
		}
		if(j==tail)
		{
			//若之前的字符都无重复,则j=tail,str[i]添加进无重复字符串中
			str[tail]=str[i];
			++tail;
		}
	}
	str[tail]=0;
}
/*With Additional Memory of Constant Size*/
static void removeDuplicatessEff(char str[])
{
	if(str==NULL) return;
	int len=strlen(str);
	if(len<2) return;
	//ASCⅡ码8位
	bool *hit=new bool[256];
	for(int i=0;i<256;++i)
		hit[i]=false;
	hit[str[0]]=true;
	int tail=1;
	for(int i=1;i<len;++i)
	{
		if(!hit[str[i]])
		{
			str[tail]=str[i];
			++tail;
			hit[str[i]]=true;
		}
	}
	str[tail]=0;
}

int main()
{
	char tmp1[]="abcababababa";
	char tmp2[]="abcababababa";
	char tmp3[]="abcdfe";
	removeDuplicates(tmp1);
	removeDuplicatessEff(tmp2);
	reverse(tmp3);
	cout << tmp1 <<endl;
	cout << tmp2 <<endl;
	cout << tmp3 <<endl;
}

Leave a Reply

Your email address will not be published. Required fields are marked *