C++博客- Problem Solving using C++

博客移至http://libiao.appspot.com

Kingoal Lee's Alogrithm Study using cplusplus — Sun, 26 Jul 2009 14:12:00 GMT

博客移至http://libiao.appspot.com,专注于专注于FreeBSD,C/C++, Python,算法和服务器开发

Kingoal Lee's Alogrithm Study using cplusplus 2009-07-26 22:12 发表评论

单链表的翻转

Kingoal Lee's Alogrithm Study using cplusplus — Wed, 05 Sep 2007 06:41:00 GMT

非常简单的实现，设置3个指针，分别指向当前节点、前一个节点、后一个节点，然后依次处理所有的节点就OK了。
具体代码为：

#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;
}

Kingoal Lee's Alogrithm Study using cplusplus 2007-09-05 14:41 发表评论

求两排序数组的中位数

Kingoal Lee's Alogrithm Study using cplusplus — Fri, 31 Aug 2007 02:32:00 GMT

#include <iostream>
#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 发表评论

常用字符串string操作--find

Kingoal Lee's Alogrithm Study using cplusplus — Wed, 29 Aug 2007 03:12:00 GMT

#include <iostream>
#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;
}

Kingoal Lee's Alogrithm Study using cplusplus 2007-08-29 11:12 发表评论

STL常见操作（1）--排序

Kingoal Lee's Alogrithm Study using cplusplus — Tue, 28 Aug 2007 02:54:00 GMT

vector vec;
generate_n(back_inserter(vec),100,rand);

sort(vec.begin(),vec.end());//or sort(vec.begin(),vec.end(),greater());

copy(vec.begin(),vec.end(),ostream_iterator(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;
}

Kingoal Lee's Alogrithm Study using cplusplus 2007-08-28 10:54 发表评论

partial_sort--基于堆排序

Kingoal Lee's Alogrithm Study using cplusplus — Mon, 27 Aug 2007 14:49:00 GMT

经常会出现求n个数中的前k个最小值(最大值），可以采取的策略为：

看n和k的大小，数组的规律。即便看情况也不一定有绝对的“最优"
如果是基本有序的，那么就用Hoare的算法，每次选中间位置的数当轴。
如果k或(n-k)是小常数，那么部分排序算法，比如用堆。
如果要抵抗算法复杂度攻击，那么可以考虑随机Hoare或者linear time selection.

在k为小值的时候，可以采用基于堆排序的部分排序方法：
代码如下：

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <iterator>

using namespace std;

void min_heapify(int arr[],int i,int size)
{
    int left = 2*i+1;
    int right = left+1;

    int largest;

    if((left<=size)&&(arr[left]>arr[i]))
    {
        largest = left;
    }
    else
    {
        largest = i;
    }

    if((right<=size)&&(arr[right]>arr[largest]))
    {
        largest = right;
    }

    if(largest!=i)
    {
        int temp = arr[i];
        arr[i]=arr[largest];
        arr[largest]=temp;

        min_heapify(arr,largest,size);
    }
}

void fillarray(int arr[],int size)
{
    for(int i=0;i<size;i++)
    {
        arr[i]=rand()%size;
    }
}

void print(const int arr[],int size)
{
    copy(arr,arr+size,ostream_iterator<int>(cout," "));
    cout<<endl;
}

int main(int argc,char* argv[])
{
    int size,k;

    while(cin>>size)
    {
        int* buff=new int[size];

        fillarray(buff,size);
        print(buff,size);

        cout<<"Please input the top k value:"<<endl;
        cin>>k;

        for(int i=(k-1)/2;i>=0;i--)
            min_heapify(buff,i,k-1);

        print(buff,size);
        cout<<endl<<endl;
        for(int i=size-1;i>=k;i--)
        {
            if(buff[i]<buff[0])
            {
                int temp = buff[0];
                buff[0]=buff[i];
                buff[i]=temp;

                min_heapify(buff,0,k-1);
            }
        }

        print(buff,size);

        delete [] buff;
    }
}

Kingoal Lee's Alogrithm Study using cplusplus 2007-08-27 22:49 发表评论

二叉搜索树操作(3)----非递归遍历

Kingoal Lee's Alogrithm Study using cplusplus — Fri, 24 Aug 2007 08:16:00 GMT

应用队列(queue)和栈(stack)对二叉搜索树进行非递归遍历
应用队列queue的是BFS,栈stack的是DFS
代码为:

#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;
}

Kingoal Lee's Alogrithm Study using cplusplus 2007-08-24 16:16 发表评论

二叉搜索树操作(2)--其他

Kingoal Lee's Alogrithm Study using cplusplus — Fri, 24 Aug 2007 04:35:00 GMT

#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;

    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 发表评论

二叉搜索树操作(1)----生成

Kingoal Lee's Alogrithm Study using cplusplus — Fri, 24 Aug 2007 01:19:00 GMT

二叉搜索树是专门有利于搜索(时间复杂度为logn)的二叉树。
生成一棵二叉搜索树关键是不断地插入数据到该树中，若当前的root为NULL，则当前插入的节点为root，否则比较左右树插入，直到为NULL为之。
二叉搜索树的插入代码为:
void BST_Insert(int key)
{
    构建当前节点current,初始化current,设置其value=key,左右父节点都为NULL;
   //用x,y两个指针来跟踪current放置的位置
   y=NULL;
x=root;

while(x)//x有下面的节点时
    {
       y=x;
         x的key和当前参数里面的key做对比，若大于当前key，则x=left[x],否则x=right[x];
    }

比较y和NULL的关系，若y==NULL,则root=NULL，有root=current;
设置parent[current]=y;
比较current的key和y的key的大小，若大，则left[y]=current,否则right[y]=current;
//插入完毕
}
使用代码表示为:

Kingoal Lee's Alogrithm Study using cplusplus 2007-08-24 09:19 发表评论

选择算法--Random Select

Kingoal Lee's Alogrithm Study using cplusplus — Thu, 23 Aug 2007 02:35:00 GMT

从一个乱序数组A[1....n]中选择排第i的数，就是经典的选择select问题
最Naive的办法就是先对整个数组进行排序（可以使用quicksort/merge sort/heap sort）但是其算法复杂度为O(nlogn)，如果使用quicksort的partition的变种的话，其最差复杂度为O(n^2)，但是平均复杂度为O(n).其核心算法如下：
int randselect(int p,int r,int i)
{
    if(p==r)
          return arr[p];
   int q = partition(p,r);//调用quicksort里面的partition
   int k = q-p+1;
   if(i==k)
           return arr[q];
   if(i           return randselect(p,q-1,i);
   if(i>k)
           return randselect(q+1,r,i-k);
}

代码如下：

#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;
}

Kingoal Lee's Alogrithm Study using cplusplus 2007-08-23 10:35 发表评论