一些测试题

1、[题目]：    给定一个单向链表（长度未知），请设计一个既节省时间又节省空间的算法来找出该链表中的倒数第m个元素。实现这个算法，并为可能出现的特例情况安排好处理措施。“倒数第m个元素”是这样规定的：当m=0时，链表的最后一个元素将被返回。

element *FindMToLastElement (int head,int m)
{
      element *p1,*p2;
      int i;
      p1 = head;
      for(i=0;i<m;i++) {
           if(p1->next)
                p1 = p1->next;
           else
                return NULL;
      }
      p2 = head;
      while(p1->next) {
           p1 = p1->next;
           p2 = p2->next;
      }
      return p2;
}

谁能看出这不是一个O(n)级别的算法

2、atoi

int atoi(char s[])
{
     int i, n, sign;
     for( i = 0; isspace(s[i]); i++)
        ;
     sign = (s[i] == '-')? -1 : 1;


     if(s[i] == '+' || s[i] == '-' )
         i++;


     for(n = 0; isdigit(s[i]); i++)
             n = 10 * n + (s[i] - '0');


    return sign * n;
}

3、itoa

void itoa (int n,char s[])
{
      int i,j,sign;

      if((sign=n)<0)//记录符号

            n=-n;//使n成为正数


      i=0;
      do{
            s[i++]=n%10+'0';//取下一个数字

      }while ((n/=10)>0);//删除该数字


      if(sign<0)
           s[i++]='-';
      s[i]='\0';

      for(j=i;j>=0;j--)//生成的数字是逆序的，所以要逆序输出

            printf("%c",s[j]);
}

4、char data[0]

typedef struct {

        int head;

        int size; //指明整个包的长度


        char reply;

        char data[0];

} packet;



packet* cmd = malloc (sizeof(packet) + 20);

memcpy (packet->data, some_data, 20);

5、用递归算法判断数组a[N]是否为一个递增数组。

bool fun( int a[], int n )
{
    if( n == 1 )
        return true;
    if( n == 2 )
        return a[n-1] >= a[n-2];
    return fun( a,n-1) && ( a[n-1] >= a[n-2] );
}

6、二分法查找

int binarySearch(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1); // key not found.

}

递归２分法

int recursiveBinarySearch(int[] a, int key, int from, int to) {

        int mid = (from + to) >> 1;
        int midVal = a[mid];
        // search left part

        if (midVal > key && from <= mid - 1) {
            return recursiveBinarySearch(a, key, from, mid - 1);
        }
        // search right part

        else if (midVal < key && mid + 1 <= to) {
            return recursiveBinarySearch(a, key, mid + 1, to);
        }
        // find key

        else if (midVal == key) {
            return mid;
        }
        // cannot find

        return -1;

}

７、快速排序

void quick_sort(int data[], int low, int high)
{
       int i, j, pivot;
       if (low < high)
       {
              pivot=data[low];
              i=low;
              j=high;
             
              while(i<j)
              {
                     while (i<j && data[j]>=pivot)
                            j--;
                     if(i<j)
                            data[i++]=data[j]; //将比枢轴记录小的记录移到低端

                    
                     while (i<j && data[i]<=pivot)
                            i++;
                     if(i<j)
                            data[j--]=data[i]; //将比枢轴记录大的记录移到高端

              }
             
              data[i]=pivot; //枢轴记录移到最终位置

             
              quick_sort(data,low,i-1);
              quick_sort(data,i+1,high);
       }
}