坚持到底就是胜利

用心去做好这件事情

统计

留言簿(1)

阅读排行榜

评论排行榜

2006年11月21日 #

other algorithm

111

posted @ 2006-11-21 22:11 ailab 阅读(221) | 评论 (0) | 编辑 收藏

tree algorithm

  1.  travel tree without stack or recursive
  2. three travel using none recursive
  3. delete a element in binary search tree
  4. count words(using bst)
  5. level-travel(using queue)

posted @ 2006-11-21 22:11 ailab 阅读(245) | 评论 (0) | 编辑 收藏

array algorithm

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

posted @ 2006-11-21 22:11 ailab 阅读(207) | 评论 (0) | 编辑 收藏

list algorithm

  1. reverse_list (none-recursive && recursive)
  2. merge list
  3. find middle element of a list
  4. find the nth element from the end of list
  5. insert a element to a sorted single linked list
  6. sort single linked list
  7. swap every two element in a single linked list
  8. circle && the start point
  9. meet together
  10. ploy multi

 

posted @ 2006-11-21 22:09 ailab 阅读(217) | 评论 (0) | 编辑 收藏

string algorithm

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

posted @ 2006-11-21 21:58 ailab 阅读(266) | 评论 (0) | 编辑 收藏

2006年11月20日 #

dream come true

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

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
    
}

posted @ 2006-11-20 23:32 ailab 阅读(199) | 评论 (0) | 编辑 收藏

dream come true 5!

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

posted @ 2006-11-20 22:11 ailab 阅读(193) | 评论 (0) | 编辑 收藏

dream come true!

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

posted @ 2006-11-20 22:04 ailab 阅读(198) | 评论 (0) | 编辑 收藏

dream come true!(4) strstr

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

posted @ 2006-11-20 21:50 ailab 阅读(197) | 评论 (0) | 编辑 收藏

dream come true!(3)

给定数组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);
  
}

posted @ 2006-11-20 21:20 ailab 阅读(230) | 评论 (0) | 编辑 收藏

仅列出标题  下一页