C++博客-坚持到底就是胜利

other algorithm

ailab — Tue, 21 Nov 2006 14:11:00 GMT

111

ailab 2006-11-21 22:11 发表评论

tree algorithm

ailab — Tue, 21 Nov 2006 14:11:00 GMT

travel tree without stack or recursive
three travel using none recursive
delete a element in binary search tree
count words(using bst)
level-travel(using queue)

ailab 2006-11-21 22:11 发表评论

array algorithm

ailab — Tue, 21 Nov 2006 14:11:00 GMT

insert a value into sorted array
select nth element
delete duplicate element
find there exits two same items in a array
find duplicate element a[0.N-1]. range from 1--N-1
a+b = s
find prim
occurs odd
findMidArray

ailab 2006-11-21 22:11 发表评论

list algorithm

ailab — Tue, 21 Nov 2006 14:09:00 GMT

reverse_list (none-recursive && recursive)
merge list
find middle element of a list
find the nth element from the end of list
insert a element to a sorted single linked list
sort single linked list
swap every two element in a single linked list
circle && the start point
meet together
ploy multi

ailab 2006-11-21 22:09 发表评论

string algorithm

ailab — Tue, 21 Nov 2006 13:58:00 GMT

word_count
reverse_string
reverse_word in a sentence
longest increasing subsequence
longest common subsequence
strstr
trim {space}
compress letter
atoi
atof
find all increasing subsequence
Find out if a string is a palindrome.
Delete characters from string 1 which are present in string 2
An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings
Given a sequence of characters. How will you convert the lower case characters to upper case characters.

ailab 2006-11-21 21:58 发表评论

dream come true

ailab — Mon, 20 Nov 2006 15:32:00 GMT

两个链表是否相交，如果相交，找出第一个开始相交的节点

node * list(node * list1,node * list2)
{
if (list1 == null || list2 == null )
    return null ;
int len1 = 0 ,len2 = 0 ;
node * p = list1, * q = list2;
while (p -> next != null )
    {
        len1 ++ ;
        p = -> next;
        }
   while (q -> next != null )
   {
      len2 ++ ;
      q = q -> next;
    }
   if (p != q)
     return null ;
  len1 ++ ;
  len2 ++ ;

  p = list1;q = list2;

   if (len1 > len2 )
   {
        int diff = len1 - len2;
       p = list1;
        while (diff > 0 && p != null ;)
         {
         p = p -> next;
         diff -- ;
          }
    }
   else
{
        int diff = len2 - len1;
       q = list2;
        while (diff > 0 && q != null )
         {diff -- ; q = q -> next;}
  }

while (p != q)
{
   p = p -> next;q = q -> next;
}
   return p

}

ailab 2006-11-20 23:32 发表评论

dream come true 5!

ailab — Mon, 20 Nov 2006 14:11:00 GMT

reverse list
recursion and none-recursion

node *reverse_list(node *head)
{
  if(head == null || head->next == null)
      return head;
  node *cur = head->next;
  node *pre = head;
  node *next = null;
  while(cur != null)
  {
     next = cur->next;
     cur->next = pre;
     pre = cur;
     cur = next;
  }
  head->next = null;
  head = pre;
  reurn head;
}

node *reverse_list(node *head)
{
  if(head == null || head->next == null)
    return head;
  node *cur = head->next;
  node *next = null;
  head->next = null;
  while(cur != null)
{
    next = cur->next;
    cur->next = head;
    head = cur;
    cur = next;
}
  return head;

}

ailab 2006-11-20 22:11 发表评论

dream come true!

ailab — Mon, 20 Nov 2006 14:04:00 GMT

node * merge(node * head1,node * head2)
{
   if (head1 == null )
      return head2;
   if (head2 == null )
      return head1;
  reverse_list( & head2);
  node * head3 = null , * cur = null ;
  node * p = head1, * q = head2;
   while (p != null && q != null )
   {
     if (p -> value < q -> value)
     {
        if (head3 == null )
         {
           head3 = p;
           cur = p;
           p = p -> next;
         }
         else
         {
          cur -> next = p;
          cur = p;
          p = p -> next;
         }
      }
      else
       {
            if (head3 == null )
            {
             head3 = q;
             cur = q;
             q = q -> next;
            }
            else
              {
               cur -> next = q;
               cur = q;
               q = q -> next;
               }
        }
   }
    if (p == null )
      cur -> next = q;
    if (q == null )
      cur -> next = p;
    return head3;
}

ailab 2006-11-20 22:04 发表评论

dream come true!(4) strstr

ailab — Mon, 20 Nov 2006 13:50:00 GMT

there are many implentations

char *strstr(const char *str,const char *sub)
{
  if(str == null || sub == null)
    return null;
  const char *p = str;
  const char *q = sub;
  while(*str != '\0' && *sub != '\0')
  {
     if(*str++ != *sub++)
      {
          str = ++p;
          sub = q;
        }
   }
  if(*sub == '\0')
    return p;
  else
    return null;
}

char *strstr(const char *str,const char *sub)
{
  if(str == null || sub == null)
    return null;
  const char *p = str;
  const char *q = sub;
  for(;*str != '\0' ;str++)
  {
    if(*str != *sub)
      continue;
    p = str;
    while(1)
    {
        if(*sub == '\0')
           return str;
        if(*p++ != *sub++)
           break;

      }
     sub = q;
}

ailab 2006-11-20 21:50 发表评论

dream come true!(3)

ailab — Mon, 20 Nov 2006 13:20:00 GMT

给定数组a[0:n-1]以及一个正整数k（0<=k<=n-1），设计一个算法，将子数组a[0:k]和
a[k+1:n-1]交换位置，要求算法在最坏的情况下耗时O(n)，且用到的辅助空间为O(1)。

in fact,the essence of above question is "revers two times"
(a'b')' = ba;

void reverse(int *a,int n,int k)
{
  if(a == null || n < 0 || k > n)
    return;
  revers_array(a,0,n-1);
  revers_array(a,0,k);
  revers_array(a,k+1,n-1);

}

ailab 2006-11-20 21:20 发表评论