#include "../stdafx.h"
#include
#include
#include
#include
#include "Algorithm.h"
#include
using namespace std;
/*
Çó×Ö·û´®µÄ×ÖµäÐòÈ«ÅÅÁÐ
@src£ºÔ´×Ö·û´®
*/
/*========================================================== READY =============================================================================*/
void dictSort(char* src){
int length = strlen(src);
sort(src,src+length);
cout<0;i--){
if(src[i] src[start-1]){
change++;
}
else
break;
}
int temp = src[start-1];
src[start-1] = src[change];
src[change] = temp;
sort(src+start,src+length);
}while(true);
}
/*========================================================== END =============================================================================*/
/*
2.kmp×Ö·û´®Æ¥ÅäË㷨ʵÏÖ
@src£ºÔ´×Ö·û´®
*/
/*========================================================= READY =============================================================================*/
//¼ÆËãnextÊý×é
void calculateNext(int next[], char* pattern)
{
double startTick = GetTickCount();
if (pattern == NULL)
{
return;
}
int len = strlen(pattern);
next[0] = 0;
int i, k;
for (i = 1, k = 0; i < len; i++)
{
while (k > 0 && pattern[i] != pattern[k])
{
k = next[k - 1];
}
if (pattern[i] == pattern[k])
{
k++;
}
next[i] = k;
}
double endTick = GetTickCount();
char buff[128] = { 0 };
sprintf(buff, "time : %f", endTick);
cout << buff;
}
int kmp(char* src,char* pattern)
{
int patLen = strlen(pattern);
int srcLen = strlen(src);
int* next = (int*)malloc(patLen*sizeof(int));
memset(next, 0, patLen*sizeof(int));
calculateNext(next,pattern);
for (int i = 0; i < patLen; i++)
{
cout << next[i] << " ";
}
for (int s = 0, p = 0; s < srcLen; s++)
{
while (p>0 && src[s] != pattern[p])
p = next[p - 1];
if (src[s] == pattern[p])
{
p++;
}
if (p == patLen)
{
cout << "find success";
return s - p + 1;
}
}
free(next);
next = NULL;
}
/*========================================================== END =============================================================================*/
/*
½¨Á¢¶þ²æÅÅÐòÊ÷BST
²¢ÊµÏÖÏà¹Ø²Ù×÷
*/
//´´½¨¶þ²æÊ÷
bool createBSTree(BSTreeNode *&root,int value)
{
if (root == NULL)
{
root = new BSTreeNode;
root->data = value;
root->left = NULL;
root->right = NULL;
return true;
}
if (value > root->data)
{
createBSTree(root->right, value);
}
else if(value < root->data)
{
createBSTree(root->left, value);
}
}
//ÏÈÐò±éÀú(µÝ¹é)
void preVisit(BSTreeNode *&root)
{
if (root == NULL)
{
return;
}
cout << root->data << "--->";
if (root->left != NULL)
{
preVisit(root->left);
}
if (root->right != NULL)
{
preVisit(root->right);
}
}
//ÖÐÐò±éÀú(µÝ¹é)
void inVisit(BSTreeNode *&root)
{
if (root == NULL)
return;
if (root->left != NULL)
inVisit(root->left);
cout << root->data << "--->";
if (root->right != NULL)
inVisit(root->right);
}
//ºóÐò±éÀú(µÝ¹é)
void postVisit(BSTreeNode *&root)
{
if (root == NULL)
return;
if (root->left != NULL)
postVisit(root->left);
if (root->right != NULL)
postVisit(root->right);
cout << root->data << "--->";
}
//
BSTreeNode* Head = NULL;
BSTreeNode* Last
void tranformBSTreeToList(BSTreeNode *&root)
{
}