|
//memcpy
void *memcpy(void *des,const void *src,size_t count){
assert(des!=NULL&&src!=NULL);
char *pdes=(char *)des;
const char *psrc=(const char *)src;
if(pdes>psrc&&pdes<psrc+count)
for(int i=count-1;i>=0;--i)
pdes[i]=psrc[i];
else
for(i=0;i<count;++i)
pdes[i]=psrc[i];
return des;
}
//strlen()
int strlength(const char *str){
const char *eof=str;
while(*eof++);
return (int)(eof-str-1);
}
//strcpy()
char * strcopy(char *des,const char *src){
assert(des!=NULL&&src!=NULL);
char *start=des;
while(*des++=*src++);
return start;
}
//strcmp()
int mystrcmp(const char *src,const char *des){
int ret=0;
while(!(ret=*(unsigned char *)src-*(unsigned char *)des)&&*des)
++src,++des;
if(ret<0)ret=-1;
if(ret>0)ret=1;
return ret;
}
//strstr()
char* findstr(const char* str,const char* substr){
if(!*substr) return (char*)str;
char *cp=(char*)str;
char *s1,*s2;
while(*cp){
s1=cp;
s2=(char*)substr;
while(*s1&&*s2&&(*s1==*s2)){
++s1;
++s2;
}
if(!*s2)return cp;
++cp;
}
return NULL;
}
//count numbers of 1bit
int count1(unsigned char onechar){
int cnt=0;
for(unsigned char b=0x80;onechar;onechar<<=1){
if(onechar>=b)cnt++;
}
return cnt;
}
int count2(unsigned char onechar){
int cnt=0;
for(;onechar;onechar>>=1)
cnt+=(in&0x01);
return cnt;
}
//reverse a char string
void reversestring(char* str){
char *eof=str;
while(*p++);
int j=(int)(eof-str-2);
char tmp;
for(int i=0;i<j;++i,--j){
tmp=str[i];
str[i]=str[j];
str[j]=tmp;
}
}
//reverse a single list
struct Node{
int data;
struct Node *next;
};
typedef struct Node Node;
Node * ReverseList(Node *head){
if(head||head->next) return head;
Node *p1,*p2;
p2=head->next;
head->next=NULL;
while(p2){
p1=head;
head=p2;
p2=p2->next;
head->next=p1;
}
return head;
}
//Merge two single lists
Node * Merge(Node *head1,Node *head2)
{
if(!head1) return head2;
if(!head2) return head1;
Node *head=NULL;
Node *p1=head1;
Node *p2=head2;
if(p1->data <= p2->data){
head=p1;
p1=p1->next;
}
else{
head=p2;
p2=p2->next;
}
Node *pcurrent=head;
while(p1&&p2){
if(p1->data <= p2->data){
pcurrent->next=p1;
pcurrent=p1;
p1=p1->next;
}
else{
pcurrent->next=p2;
pcurrent=p2;
p2=p2->next;
}
}
if(p1)pcurrent->next=p1;
if(p2)pcurrent->next=p2;
return head;
}
//Merge Recursive
Node * MergeRecursive(Node *head1,Node *head2)
{
if(!head1) return head2;
if(!head2) return head1;
Node *head=NULL;
if(head1->data <= head2->data){
head=head1;
head->next=MergeRecursive(head1->next,head2);
}
else{
head=head2;
head->next=MergeRecursive(head1,head2->next);
}
return head;
}
//check a circle in a single list
bool isCircle(Node *head){
Node *p1=head;
Node *p2=head;
int i=0;
while(p1){
while(p2){
p2=p2->next;
if(p1==p2) return true;
if(i==1){
i=0;
break;
}
++i;
}
p1=p1->next;
}
return false;
}
//non-recursive binary tree pre-order travel
struct Btree{
int data;
struct Btree *left,*right;
};
typedef struct Btree Btree;
void preorder(Btree *root){
Btree *stack[100];
Btree *p=root;
int top=-1;
while(p||top!=-1){
while(p){
cout<<p->data<<" ";
stack[++top]=p;
p=p->left;
}
if(top!=-1)
p=stack[top--]->right;
}
}
//non-recursive binary tree in-order travel
void inorder(Btree *root){
int top=-1;
Btree *p=root;
Btree *stack[100];
while(p||top!=-1){
while(p){
stack[++top]=p;
p=p->left;
}
if(top!=-1){
p=stack[top--];
cout<<p->data<<" ";
p=p->right;
}
}
}
//non-recursive binary tree post-order travel
void postorder(Btree *root){
typedef enum{L,R} tagtype;
struct Bnode{
Btree *pbtree;
tagtype tag;
};
typedef struct Bnode Bnode;
int top=-1;
Bnode stack[100];
Btree *p=root;
while(p||top!=-1){
while(p){
stack[++top].pbtree=p;
stack[top].tag=L;
p=p->left;
}
while(top!=-1&&stack[top].tag==R)
cout<<stack[top--].pbtree->data<<" ";
if(top!=-1){
stack[top].tag=R;
p=stack[top].pbtree->right;
}
}
}
//insertion sort
template <class Elem,class Comp>
void Insertionsort(Elem A[],int n){
for(int i=1;i<n;++i)
for(int j=i;j>0;--j)
if(Comp::lt(A[j],A[j-1]))
swap(A,j,j-1);
}
//bubble sort
template <class Elem,class Comp>
void Bubblesort(Elem A[],int n){
for(int i=0;i<n-1;++i)
for(int j=n-1;j>i;--j)
if(Comp::lt(A[j],A[j-1]))
swap(A,j,j-1);
}
//selection sort
template <class Elem,class Comp>
void Selectionsort(Elem A[],int n){
for(int i=0;i<n-1;++i){
int lowindex=i;
for(int j=n-1;j>i;--j)
if(Comp::lt(A[j],A[lowindex]))
lowindex=j;
swap(A,i,lowindex);
}
}
//quick sort
template <class Elem,class Comp>
void Quicksort(Elem A[],int i,int j){
if(j<=i) return;
int pivotindex=(i+j)/2;
swap(A,pivotindex,j);
int k=partition<Elem,Comp>(A,i-1,j,A[j]);
swap(A,k,j);
Quicksort<Elem,Comp>(A,i,k-1);
Quicksort<Elem,Comp>(A,k+1,j);
}
template <class Elem,class Comp>
int partition(Elem A[],int l,int r,Elem pivotvalue){
while(l<r){
while(Comp::lt(A[++l],pivotvalue));
while(Comp::lt(pivotvalue,A[--r])&&r!=0);
swap(A,l,r);
}
swap(A,l,r);
return l;
}
//heap sort
template <class Elem,class Comp>
void sift(Elem A[],int n,int pos){
while(pos<n/2){
int j=2*pos+1;
if(j<n-1&&Comp::lt(A[j],A[j+1]))
++j;
if(Comp::lt(A[j],A[pos])) return;
swap(A,pos,j);
pos=j;
}
}
template <class Elem,class Comp>
void Heapsort(Elem A[],int n){
for(int i=n/2-1;i>=0;--i)
sift<Elem,Comp>(A,n,i);
for(i=n-1;i>=0;--i){
swap(A,0,i);
sift<Elem,Comp>(A,--n,0);
}
}
//Merge sort
template <class Elem,class Comp>
void Mergesort(Elem A[],Elem temp[],int left,int right){
if(left==right) return;
int mid=(left+right)/2;
Mergesort<Elem,Comp>(A,temp,left,mid);
Mergesort<Elem,Comp>(A,temp,mid+1,right);
for(int i=left;i<=right;++i)
temp[i]=A[i];
int list1=left;
int list2=mid+1;
int curr=left;
while(curr<=right){
if(list1>mid)
A[curr++]=temp[list2++];
else if(list2>right)
A[curr++]=temp[list1++];
else if(Comp::lt(temp[list1],temp[list2]))
A[curr++]=temp[list1++];
else A[curr++]=temp[list2++];
}
} |
