|
这里的每个单词用空格分开。例如：
Here is www.fishksy.com.cn
经过反转后变为：
www.fishksy.com.cn is Here
如果只是简单的将所有字符串翻转的话，可以遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，
依次循环。其实按照单词反转的话可以在第一遍遍历的基础上，再遍历一遍字符串，对每一个单词再反转一次。这样每
个单词又恢复了原来的顺序。
char* reverse_word(const char* str)
{
int len = strlen(str);
char* restr = new char[len+1];
strcpy(restr,str);
int i,j;
for(i=0,j=len-1;i
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
int k=0;
while(k
{
i=j=k;
while(restr[j]!=' ' && restr[j]!='' )
j++;
k=j+1;
j--;
for(;i
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
}
return restr;
}
如果考虑空间和时间的优化的话，当然可以将上面代码里两个字符串交换部分改为异或实现。
例如将
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
改为
restr[i]^=restr[j];
restr[j]^=restr[i];
restr[i]^=restr[j];
7,字符串反转
我没有记错的话是一道MSN的笔试题，网上无意中看到的，拿来做了一下。题目是这样的，给定一个字符串，一个这个字
符串的子串，将第一个字符串反转，但保留子串的顺序不变。例如：
输入：第一个字符串: "This is fishsky 's Chinese site: http://www.fishsky.com.cn/cn"
子串: "fishsky"
输出： "nc/nc.moc.fishsky.www//:ptth :etis esenihC s'fishsky si sihT"
一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下
来的子串再用stack反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串，就将子串倒过来压入堆栈。
最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。源代码如下：
第 3 页
数据结构面试大全
#include
#include
#include
using namespace std;
//reverse the string ‘s1′ except the substring ‘token’.
const char* reverse(const char* s1, const char* token)
{
assert(s1 && token);
stack
stack1;
const char* ptoken = token, *head = s1, *rear = s1;
while (*head != ”)
{
while(*head!= ” && *ptoken == *head)
{
ptoken++;
head++;
}
if(*ptoken == ”)//contain the token
{
const char* p;
for(p=head-1;p>=rear;p–)
stack1.push(*p);
ptoken = token;
rear = head;
}
else
{
stack1.push(*rear);
head=++rear;
ptoken = token;
}
}
char * return_v = new char[strlen(s1)+1];
int i=0;
while(!stack1.empty())
{
return_v[i++] = stack1.top();
stack1.pop();
}
return_v[i]=”;
return return_v;
}
int main(int argc, char* argv[])
{
cout<<"This is fishsky 's Chinese site: http://www.fishsky.com.cn/cn
";
cout<
return 0;
}
8, 删除数组中重复的数字
问题：一个动态长度可变的数字序列，以数字0为结束标志，要求将重复的数字用一个数字代替，例如：
将数组 1,1,1,2,2,2,2,2,7,7,1,5,5,5,0 转变成1,2,7,1,5,0
问题比较简单，要注意的是这个数组是动态的。所以避免麻烦我还是用了STL的vector。
#include
#include
using namespace std;
//remove the duplicated numbers in an intger array, the array was end with 0;
//e.g. 1,1,1,2,2,5,4,4,4,4,1,0 —>1,2,5,4,1,0
void static remove_duplicated(int a[], vector
& _st)
{
_st.push_back(a[0]);
for(int i=1;_st[_st.size()-1]!=0;i++)
{
if(a[i-1]!=a[i])
_st.push_back(a[i]);
}
}
当然如果可以改变原来的数组的话，可以不用STL，仅需要指针操作就可以了。下面这个程序将修改原来数组的内容。
void static remove_duplicated2(int a[])
{
if(a[0]==0 || a==NULL)
return;
int insert=1,current=1;
第 4 页
数据结构面试大全
while(a[current]!=0)
{
if(a[current]!=a[current-1])
{
a[insert]=a[current];
insert++;
current++;
}
else
current++;
}
a[insert]=0;
}
9,如何判断一棵二叉树是否是平衡二叉树
问题：判断一个二叉排序树是否是平衡二叉树
解决方案：
根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。
首先编写一个计算二叉树深度的函数，利用递归实现。
template
static int Depth(BSTreeNode
* pbs)
{
if (pbs==NULL)
return 0;
else
{
int ld = Depth(pbs->left);
int rd = Depth(pbs->right);
return 1 + (ld >rd ld : rd);
}
}
下面是利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树的函数：
template
static bool isBalance(BSTreeNode
* pbs)
{
if (pbs==NULL)
return true;
int dis = Depth(pbs->left) – Depth(pbs->right);
if (dis>1 || dis<-1 )
return false;
else
return isBalance(pbs->left) && isBalance(pbs->right);
}10, strstr()的简单实现
strstr(s1,s2)是一个经常用的函数，他的作用就是 |