数据结构 整理笔记(三)
mpty())
{
return_v[i++] = stack1.top();
stack1.pop();
}
return_v[i]='/0';
return return_v;
}
int main(int argc, char* argv[])
{
cout<<"This is fishsky 's Chinese site: http://www.fishsky.com.cn/cn/n";
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;
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)是一个经常用的函数，他的作用就是在字符串s1中寻找字符串s2如果找到了就返回指针，否则返回NULL。
下面是这个函数的一个简单实现：
static const char* _strstr(const char* s1, const char* s2)
{
assert(s2 && s1);
const char* p=s1, *r=s2;
while(*p!='/0')
{
while(*p++==*r++);
if(*r=='/0')
return p;
else
{
r=s2;
p=++s1;
}
}
return NULL;
}
11,半素数
题目定义了一种叫半素数的数：只要一个数能被分解成两个素数，那么这个数就是半素数。
Prime Number Definition
An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For instance, 2, 11, 67, 89 are prime numbers but 8, 20, 27 are not.
Semi-Prime Number Definition
An integer greater than one is called a semi-prime number if it can be decompounded to TWO prime numbers. For example, 6 is a semi-prime number but 12 is not.
Your task is just to determinate whether a given number is a semi-prime number.
Input
There are several test cases in the input. Each case contains a single integer N (2 <= N <= 1,000,000)
Output
One line with a single integer for each case. If the number is a semi-prime number, then output "Yes", otherwise "No".
Sample Input
3
4
6
12
Sample Output
No
Yes
Yes
No
没什么好说的，解法很简单，解法如下：
#include
#include
using namespace std;
bool isprime(long test)
{
int i;