Kingoal Lee's Alogrithm Study using cplusplus 2009-07-26 22:12 鍙戣〃璇勮
]]>#include <iostream>
using namespace std;
#ifndef null
#define null (void*)0
#endif
typedef struct node
{
struct node* next;
int data;
}node;
node* head=(node*)null;
void reverse(node* root)
{
node *cur,*pre,*next;
pre=(node*)null;
cur=root;
next=cur->next;
while(next)
{
cur->next=pre;
pre=cur;
cur=next;
next=cur->next;
}
head=cur;
cur->next=pre;
}
void insert(node* p)
{
p->next=head;
head=p;
}
void del(node* p)
{
node *cur,*next;
cur=p;
next=p->next;
while(next)
{
delete cur;
cur=next;
next=cur->next;
}
delete cur;
}
void print(node* p)
{
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main(int argc,char** argv)
{
for(int i=0;i<10;i++)
{
node* p=new node;
p->next=(node*)null;
p->data=i;
insert(p);
}
print(head);
cout<<"reverse order:"<<endl;
reverse(head);
print(head);
del(head);
system("pause");
return 0;
}
using namespace std;
#ifndef null
#define null (void*)0
#endif
typedef struct node
{
struct node* next;
int data;
}node;
node* head=(node*)null;
void reverse(node* root)
{
node *cur,*pre,*next;
pre=(node*)null;
cur=root;
next=cur->next;
while(next)
{
cur->next=pre;
pre=cur;
cur=next;
next=cur->next;
}
head=cur;
cur->next=pre;
}
void insert(node* p)
{
p->next=head;
head=p;
}
void del(node* p)
{
node *cur,*next;
cur=p;
next=p->next;
while(next)
{
delete cur;
cur=next;
next=cur->next;
}
delete cur;
}
void print(node* p)
{
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main(int argc,char** argv)
{
for(int i=0;i<10;i++)
{
node* p=new node;
p->next=(node*)null;
p->data=i;
insert(p);
}
print(head);
cout<<"reverse order:"<<endl;
reverse(head);
print(head);
del(head);
system("pause");
return 0;
}
Kingoal Lee's Alogrithm Study using cplusplus 2007-09-05 14:41 鍙戣〃璇勮
]]>#include <string>
using namespace std;
int main(int argc,char* argv[])
{
int A[]={1,3,5,7,8,9};
int B[]={2,4,6,10,11,12,13,14};
int sizeA = sizeof(A)/sizeof(int);
int sizeB = sizeof(B)/sizeof(int);
int ma=0,na=sizeA-1;
int mb=0,nb=sizeB-1;
while(1)
{
int ka=(na+ma+1)/2;
int kb=(nb+mb+1)/2;
if(na<ma)
{
cout<<B[kb]<<endl;
break;
}
if(nb<mb)
{
cout<<A[ka]<<endl;
break;
}
if(A[ka]==B[kb])//find the value
{
cout<<A[ka]<<endl;
break;
}
if((ma==na)&&((nb-mb+1)%2==0))//there is only one element at A[]
{
if((A[na]<B[kb])&&(A[na]>=B[kb-1]))
{
cout<<A[na]<<endl;
break;
}
}
if((ma==na)&&((nb-mb+1)%2))
{
if((A[na]>B[kb])&&(A[na]<=B[kb+1]))
{
cout<<A[na]<<endl;
break;
}
}
if((mb==nb)&&((na-ma+1)%2==0))//there is only one element at B[]
{
if((B[nb]<A[ka])&&(B[nb]>=A[ka-1]))
{
cout<<B[nb]<<endl;
break;
}
}
if((mb==nb)&&((na-ma+1)%2))
{
if((B[nb]>A[ka])&&(B[nb]<=A[ka+1]))
{
cout<<B[nb]<<endl;
break;
}
}
int offset=ka-ma;
if(offset>(kb-mb))
offset=kb-mb;
if(offset==0)
offset++;
//int offset=((ka>=kb)?ka:kb);
if(A[ka]<B[kb])
{
ma+=offset;
nb-=offset;
}
if(A[ka]>B[kb])
{
na-=offset;
mb+=offset;
}
}
system("pause");
return 0;
}
Kingoal Lee's Alogrithm Study using cplusplus 2007-08-31 10:32 鍙戣〃璇勮
]]>#include <string>
#include <cctype>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main(int argc,char** argv[])
{
string line1="We were her pride of 10 she named us:";
string line2="Benjamin, Phoenix, the Prodigal";
string line3="and perspicacious pacific Suzanne";
string sentence = line1+' '+line2+' '+line3;
string separator(" \n\t:,\r\v\f");
vector<string> longest,shortest;
int num = 0;
string::size_type startpos=0,endpos=0;
string word;
int longLen=0,shortLen=-1,wordlen;
while((startpos=sentence.find_first_not_of(separator,endpos))!=string::npos)
{
++num;
endpos=sentence.find_first_of(separator,startpos);
if(endpos==string::npos)
{
wordlen = sentence.size()-startpos;
}
else
{
wordlen = endpos-startpos;
}
word.assign(sentence.begin()+startpos,sentence.begin()+wordlen+startpos);
startpos = sentence.find_first_not_of(separator,endpos);
if(shortLen==-1)
{
shortLen=longLen=wordlen;
shortest.push_back(word);
longest.push_back(word);
continue;
}
if(shortLen==wordlen)
{
shortest.push_back(word);
}
if(shortLen>wordlen)
{
shortest.clear();
shortest.push_back(word);
shortLen = wordlen;
}
if(wordlen==longLen)
{
longest.push_back(word);
}
if(wordlen>longLen)
{
longest.clear();
longest.push_back(word);
longLen=wordlen;
}
}
cout<<"Words:"<<num<<endl;
cout<<"Shortest:"<<shortLen<<endl;
copy(shortest.begin(),shortest.end(),ostream_iterator<string>(cout," "));
cout<<endl;
cout<<"Longest:"<<longLen<<endl;
copy(longest.begin(),longest.end(),ostream_iterator<string>(cout," "));
cout<<endl;
system("pause");
return 0;
}
#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
void str_replace(string& str,const string& src,const string& dst)
{
string::size_type pos = 0;
int srclen = src.size();
int dstlen = dst.size();
while((pos = str.find(src,pos))!=string::npos)
{
//str.replace(pos,srclen,dst);
str.erase(pos,srclen);
str.insert(pos,dst);
pos+=dstlen;
}
}
int main(int argc,char** argv[])
{
//replace/erase/insert
string str("I like apple,what about you? apple tastes great!");
cout<<str<<endl;
str_replace(str,"apple","banana");
cout<<str<<endl;
//assign/append
string q1("When lilacs last in the dooryard bloom'd");
string q2("The child is father of the man");
string sentence;
sentence.assign(q2.begin(),q2.begin()+13);
sentence.append(q1.substr(q1.find("in"),15));
cout<<sentence<<endl;
system("pause");
return 0;
}
#include <string>
#include <cctype>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
void str_replace(string& str,const string& src,const string& dst)
{
string::size_type pos = 0;
int srclen = src.size();
int dstlen = dst.size();
while((pos = str.find(src,pos))!=string::npos)
{
//str.replace(pos,srclen,dst);
str.erase(pos,srclen);
str.insert(pos,dst);
pos+=dstlen;
}
}
int main(int argc,char** argv[])
{
//replace/erase/insert
string str("I like apple,what about you? apple tastes great!");
cout<<str<<endl;
str_replace(str,"apple","banana");
cout<<str<<endl;
//assign/append
string q1("When lilacs last in the dooryard bloom'd");
string q2("The child is father of the man");
string sentence;
sentence.assign(q2.begin(),q2.begin()+13);
sentence.append(q1.substr(q1.find("in"),15));
cout<<sentence<<endl;
system("pause");
return 0;
}
Kingoal Lee's Alogrithm Study using cplusplus 2007-08-29 11:12 鍙戣〃璇勮
]]>sort(vec.begin(),vec.end());//or sort(vec.begin(),vec.end(),greater<int>());
copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
#include <iostream>
#include <functional>
#include <algorithm>
#include <iterator>
#include <vector>
#include <cstdlib>
using namespace std;
int main(int argc,char** argv)
{
vector<int> vec;
generate_n(back_inserter(vec),100,rand);
copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
cout<<endl;
sort(vec.begin(),vec.end());
copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
cout<<endl;
system("pause");
return 0;
}
#include <functional>
#include <algorithm>
#include <iterator>
#include <vector>
#include <cstdlib>
using namespace std;
int main(int argc,char** argv)
{
vector<int> vec;
generate_n(back_inserter(vec),100,rand);
copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
cout<<endl;
sort(vec.begin(),vec.end());
copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
cout<<endl;
system("pause");
return 0;
}
Kingoal Lee's Alogrithm Study using cplusplus 2007-08-28 10:54 鍙戣〃璇勮
]]>浠ｇ爜涓?
#include <iostream>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
#ifndef MAXSIZE
#define MAXSIZE 10
#endif
typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites
struct BST* left;
struct BST* right;
struct BST* parent;
} BST;
BST* root=NULL;
void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node
BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
while(x!=NULL)
{
y=x;
if(key<x->key)
x=x->left;
else
x=x->right;
}
node->parent=y;
if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}
void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}
void BST_Build()
{
int temp;
cout<<"Original Input:"<<endl;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}
void BST_Inorder_Walk(BST* p)
{
if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}
void BST_Preorder_Walk(BST* p)
{
if(p)
{
cout<<p->key<<" ";
BST_Preorder_Walk(p->left);
BST_Preorder_Walk(p->right);
}
}
void BST_Postorder_Walk(BST* p)
{
if(p)
{
BST_Postorder_Walk(p->left);
BST_Postorder_Walk(p->right);
cout<<p->key<<" ";
}
}
void BST_Layer_Walk()
{
queue<BST*> queue;
BST* p;
queue.push(root);
while(!queue.empty())
{
p=queue.front();
queue.pop();
if(p->left)
queue.push(p->left);
if(p->right)
queue.push(p->right);
cout<<p->key<<" ";
}
cout<<endl;
}
void Inorder_Walk(BST* node=root)
{
stack<BST*> stk;
while(!stk.empty()||node)
{
if(node)
{
stk.push(node);
node=node->left;
}
else
{
node=stk.top();
cout<<node->key<<" ";
stk.pop();
node=node->right;
}
}
}
void Preorder_Walk(BST* node=root)
{
stack<BST*> stk;
while(!stk.empty()||node)
{
if(node)
{
cout<<node->key<<" ";
stk.push(node);
node=node->left;
}
else
{
node=stk.top();
stk.pop();
node=node->right;
}
}
}
void Postorder_Walk(BST* node=root)
{
stack<BST*> stk;
BST* p;
int flag = 0;//0 stands for left, 1 stands for right
do
{
while(node)
{
stk.push(node);
node=node->left;
}
p=NULL;
flag=0;
while(!stk.empty()&&(flag==0))
{
node=stk.top();
if(node->right==p)
{
stk.pop();
p=node;
cout<<node->key<<" ";
}
else
{
node= node->right;
flag=1;
}
}
}while(!stk.empty());
}
int main(int argc,char* argv[])
{
int input;
BST_Build();
cout<<"Inorder Walk:"<<endl;
//BST_Inorder_Walk(root);
Inorder_Walk();
cout<<endl;
cout<<"Preorder Walk:"<<endl;
BST_Preorder_Walk(root);
cout<<endl;
cout<<"Stack Preorder Walk:"<<endl;
Preorder_Walk(root);
cout<<endl;
cout<<"Postorder Walk:"<<endl;
BST_Postorder_Walk(root);
cout<<endl;
cout<<"Stack Postorder Walk:"<<endl;
Postorder_Walk(root);
cout<<endl;
cout<<"Layer Walk:"<<endl;
BST_Layer_Walk();
BST_Delete(root);
cout<<endl;
system("pause");
return 0;
}
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
#ifndef MAXSIZE
#define MAXSIZE 10
#endif
typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites
struct BST* left;
struct BST* right;
struct BST* parent;
} BST;
BST* root=NULL;
void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node
BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
while(x!=NULL)
{
y=x;
if(key<x->key)
x=x->left;
else
x=x->right;
}
node->parent=y;
if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}
void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}
void BST_Build()
{
int temp;
cout<<"Original Input:"<<endl;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}
void BST_Inorder_Walk(BST* p)
{
if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}
void BST_Preorder_Walk(BST* p)
{
if(p)
{
cout<<p->key<<" ";
BST_Preorder_Walk(p->left);
BST_Preorder_Walk(p->right);
}
}
void BST_Postorder_Walk(BST* p)
{
if(p)
{
BST_Postorder_Walk(p->left);
BST_Postorder_Walk(p->right);
cout<<p->key<<" ";
}
}
void BST_Layer_Walk()
{
queue<BST*> queue;
BST* p;
queue.push(root);
while(!queue.empty())
{
p=queue.front();
queue.pop();
if(p->left)
queue.push(p->left);
if(p->right)
queue.push(p->right);
cout<<p->key<<" ";
}
cout<<endl;
}
void Inorder_Walk(BST* node=root)
{
stack<BST*> stk;
while(!stk.empty()||node)
{
if(node)
{
stk.push(node);
node=node->left;
}
else
{
node=stk.top();
cout<<node->key<<" ";
stk.pop();
node=node->right;
}
}
}
void Preorder_Walk(BST* node=root)
{
stack<BST*> stk;
while(!stk.empty()||node)
{
if(node)
{
cout<<node->key<<" ";
stk.push(node);
node=node->left;
}
else
{
node=stk.top();
stk.pop();
node=node->right;
}
}
}
void Postorder_Walk(BST* node=root)
{
stack<BST*> stk;
BST* p;
int flag = 0;//0 stands for left, 1 stands for right
do
{
while(node)
{
stk.push(node);
node=node->left;
}
p=NULL;
flag=0;
while(!stk.empty()&&(flag==0))
{
node=stk.top();
if(node->right==p)
{
stk.pop();
p=node;
cout<<node->key<<" ";
}
else
{
node= node->right;
flag=1;
}
}
}while(!stk.empty());
}
int main(int argc,char* argv[])
{
int input;
BST_Build();
cout<<"Inorder Walk:"<<endl;
//BST_Inorder_Walk(root);
Inorder_Walk();
cout<<endl;
cout<<"Preorder Walk:"<<endl;
BST_Preorder_Walk(root);
cout<<endl;
cout<<"Stack Preorder Walk:"<<endl;
Preorder_Walk(root);
cout<<endl;
cout<<"Postorder Walk:"<<endl;
BST_Postorder_Walk(root);
cout<<endl;
cout<<"Stack Postorder Walk:"<<endl;
Postorder_Walk(root);
cout<<endl;
cout<<"Layer Walk:"<<endl;
BST_Layer_Walk();
BST_Delete(root);
cout<<endl;
system("pause");
return 0;
}
Kingoal Lee's Alogrithm Study using cplusplus 2007-08-24 16:16 鍙戣〃璇勮
]]>#include <cstdlib>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
#ifndef MAXSIZE
#define MAXSIZE 10
#endif
typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites
struct BST* left;
struct BST* right;
struct BST* parent;
} BST;
BST* root=NULL;
void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node
BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
while(x!=NULL)
{
y=x;
if(key<x->key)
x=x->left;
else
x=x->right;
}
node->parent=y;
if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}
void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}
void BST_Build()
{
int temp;
cout<<"Original Input:"<<endl;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}
void BST_Inorder_Walk(BST* p)
{
if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}
void BST_Preorder_Walk(BST* p)
{
if(p)
{
cout<<p->key<<" ";
BST_Preorder_Walk(p->left);
BST_Preorder_Walk(p->right);
}
}
void BST_Postorder_Walk(BST* p)
{
if(p)
{
BST_Postorder_Walk(p->left);
BST_Postorder_Walk(p->right);
cout<<p->key<<" ";
}
}
BST* BST_Search(int key)
{
BST* x=root;
while(x)
{
if(x->key==key)
return x;
else
if(x->key>key)
x=x->left;
else
x=x->right;
}
return NULL;
}
BST* BST_Min(BST* p=root)
{
//BST* p = root;
while(p->left)
{
p=p->left;
}
return p;
}
BST* BST_Max(BST* p=root)
{
//BST* p = root;
while(p->right)
{
p=p->right;
}
return p;
}
BST* BST_Successor(int key)
{
BST* p = BST_Search(key);
BST* y;
if(p)
{
if(p->right)
{
return BST_Min(p->right);
}
y=p->parent;
while(y&&(y->right==p))
{
p=y;
y=y->parent;
}
return y;
}
return NULL;
}
BST* BST_Predecessor(int key)
{
BST* p = BST_Search(key);
BST* y;
if(p)
{
if(p->left)
return BST_Max(p->left);
y=p->parent;
while(y&&(y->left==p))
{
p=y;
y=y->parent;
}
return y;
}
return p;
}
BST* BST_Delete(int key)
{
BST* p = BST_Search(key);
BST* y,*x;
if(p)
{
if(!p->left||!p->right)
{
y=p;
}
else
y=BST_Successor(key);
if(y->left)
x=y->left;
else
x=y->right;
if(x!=NULL)
x->parent=y->parent;
if(!y->parent)
root=x;
else
{
if(y==y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
}
if(y!=p)
p->key=y->key;
return y;
}
return p;
}
int main(int argc,char* argv[])
{
int input;
BST_Build();
BST_Delete(7);
cout<<"Inorder Walk:"<<endl;
BST_Inorder_Walk(root);
cout<<endl;
cout<<"Preorder Walk:"<<endl;
BST_Preorder_Walk(root);
cout<<endl;
cout<<"Postorder Walk:"<<endl;
BST_Postorder_Walk(root);
cout<<endl;
cout<<"Min: "<<BST_Min()->key<<endl;
cout<<"Max: "<<BST_Max()->key<<endl;
while(1)
{
cin>>input;
if(input==-1)
break;
BST* p;
if(p=BST_Search(input))
{
cout<<"Parent="<<(p->parent)->key<<endl;
if(p->left)
cout<<"Left:"<<p->left->key<<endl;
if(p->right)
cout<<"Right:"<<p->right->key<<endl;
}
else
{
cout<<"Not found!"<<endl;
break;
}
if(p=BST_Predecessor(input))
{
cout<<"Predecessor:"<<p->key<<endl;
}
if(p=BST_Successor(input))
{
cout<<"Successor:"<<p->key<<endl;
}
}
BST_Delete(root);
cout<<endl;
system("pause");
return 0;
}
Kingoal Lee's Alogrithm Study using cplusplus 2007-08-24 12:35 鍙戣〃璇勮
]]>void BST_Insert(int key)
{
鏋勫緩褰撳墠鑺傜偣current,鍒濆鍖朿urrent,璁劇疆鍏秜alue=key,宸﹀彸鐖惰妭鐐歸兘涓篘ULL;
//鐢▁,y涓や釜鎸囬拡鏉ヨ窡韙猚urrent鏀劇疆鐨勪綅緗?br> y=NULL;
x=root;
while(x)//x鏈変笅闈㈢殑鑺傜偣鏃?br> {
y=x;
x鐨刱ey鍜屽綋鍓嶅弬鏁伴噷闈㈢殑key鍋氬姣旓紝鑻ュぇ浜庡綋鍓峩ey錛屽垯x=left[x],鍚﹀垯x=right[x];
}
姣旇緝y鍜孨ULL鐨勫叧緋伙紝鑻==NULL,鍒檙oot=NULL錛屾湁root=current;
璁劇疆parent[current]=y;
姣旇緝current鐨刱ey鍜寉鐨刱ey鐨勫ぇ灝忥紝鑻ュぇ錛屽垯left[y]=current,鍚﹀垯right[y]=current;
//鎻掑叆瀹屾瘯
}
浣跨敤浠ｇ爜琛ㄧず涓?
#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
#ifndef MAXSIZE
#define MAXSIZE 10
#endif
typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites
struct BST* left;
struct BST* right;
struct BST* parent;
} BST;
BST* root=NULL;
void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node
BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
while(x!=NULL)
{
y=x;
if(key<x->key)
x=x->left;
else
x=x->right;
}
node->parent=y;
if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}
void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}
void BST_Build()
{
int temp;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}
void BST_Inorder_Walk(BST* p)
{
if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}
int main(int argc,char* argv[])
{
BST_Build();
BST_Inorder_Walk(root);
BST_Delete(root);
cout<<endl;
system("pause");
return 0;
}
#include <cstdlib>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
#ifndef MAXSIZE
#define MAXSIZE 10
#endif
typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites
struct BST* left;
struct BST* right;
struct BST* parent;
} BST;
BST* root=NULL;
void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node
BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
while(x!=NULL)
{
y=x;
if(key<x->key)
x=x->left;
else
x=x->right;
}
node->parent=y;
if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}
void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}
void BST_Build()
{
int temp;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}
void BST_Inorder_Walk(BST* p)
{
if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}
int main(int argc,char* argv[])
{
BST_Build();
BST_Inorder_Walk(root);
BST_Delete(root);
cout<<endl;
system("pause");
return 0;
}
Kingoal Lee's Alogrithm Study using cplusplus 2007-08-24 09:19 鍙戣〃璇勮
]]>int randselect(int p,int r,int i)
{
if(p==r)
return arr[p];
int q = partition(p,r);//璋冪敤quicksort閲岄潰鐨刾artition
int k = q-p+1;
if(i==k)
return arr[q];
if(i<k)
return randselect(p,q-1,i);
if(i>k)
return randselect(q+1,r,i-k);
}
浠ｇ爜濡備笅錛?br>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define MAXSIZE 100
int arr[MAXSIZE];
void fillarray()
{
for(int i=0;i<MAXSIZE;i++)
{
arr[i]=rand()%MAXSIZE;
}
}
void print(bool flag=true)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
int partition(int p,int r)
{
int pivot = arr[r];
int i=p-1;
for(int j=p;j<r;j++)
{
if(arr[j]<pivot)
{
i++;
int temp = arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
arr[r]=arr[i+1];
arr[i+1]=pivot;
return i+1;
}
void quicksort(int p,int r)
{
if(p<r)
{
int q=partition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}
int randselect(int p,int r,int i)
{
if(p==r)
return arr[p];
int q = partition(p,r);
int k = q-p+1;
if(i==k)
return arr[q];
if(i<k)
return randselect(p,q-1,i);
if(i>k)
return randselect(q+1,r,i-k);
}
int main(int argc,char* argv[])
{
fillarray();
print();
//quicksort(0,MAXSIZE-1);
//print();
for(int i=0;i<MAXSIZE;i++)
cout<<randselect(0,MAXSIZE-1,i+1)<<" ";
cout<<endl;
system("pause");
return 0;
}
#include <iterator>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define MAXSIZE 100
int arr[MAXSIZE];
void fillarray()
{
for(int i=0;i<MAXSIZE;i++)
{
arr[i]=rand()%MAXSIZE;
}
}
void print(bool flag=true)
{
if(flag)
{
copy(arr,arr+MAXSIZE,ostream_iterator<int>(cout," "));
cout<<endl;
}
}
int partition(int p,int r)
{
int pivot = arr[r];
int i=p-1;
for(int j=p;j<r;j++)
{
if(arr[j]<pivot)
{
i++;
int temp = arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
arr[r]=arr[i+1];
arr[i+1]=pivot;
return i+1;
}
void quicksort(int p,int r)
{
if(p<r)
{
int q=partition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}
int randselect(int p,int r,int i)
{
if(p==r)
return arr[p];
int q = partition(p,r);
int k = q-p+1;
if(i==k)
return arr[q];
if(i<k)
return randselect(p,q-1,i);
if(i>k)
return randselect(q+1,r,i-k);
}
int main(int argc,char* argv[])
{
fillarray();
print();
//quicksort(0,MAXSIZE-1);
//print();
for(int i=0;i<MAXSIZE;i++)
cout<<randselect(0,MAXSIZE-1,i+1)<<" ";
cout<<endl;
system("pause");
return 0;
}
Kingoal Lee's Alogrithm Study using cplusplus 2007-08-23 10:35 鍙戣〃璇勮
]]>