{
    if(k==0)    return;
    else
    {
        a[--k] = n%10 + 48;
        n /= 10;
        numtostring(n,a,k);
    }
}

void main()
{
    int n,m,k=0;
    char a[100],sign=' ';
    printf("Please input the number:");
    scanf("%d",&n);
    if(n<0) {sign = '-';n = -n;}
    m = n;
    while(m)
    {
        k++;
        m /= 10;
    }
    a[k] = '\0';
    numtostring(n,a,k);
    printf("The number is :%c%s\n",sign,a);
}

（3）以顺序存储结构表示串，设计算法，求串S中出现的第一个最长重复子串及其位置并分
析算法的时间复杂度。（本题20分）
参考解法：
#include<stdio.h>
void maxsubstr(char s[],int &pos,int &len)
{
    int i,j,k;
    for(i=0;s[i]!='\0';i++)
    {
        j = i+1;
        k = 0;
        while(s[j]!='\0')
        {
            while(s[i+k]!='\0' && s[j+k]!='\0' && s[i+k]==s[j+k])
            {
                k++;
            }
            if(k>len)
            {
                len = k;
                pos = i;
            }
            k = 0;
            j++;
        }
    }
}

void main()
{
    int i,pos=0,len=0;
    char s[100];
    printf("please input string :");
    gets(s);
    maxsubstr(s,pos,len);
    for(i=0;i<len;i++)
    {
        printf("%c",s[pos+i]);
    }
    printf("\n");
}
时间复杂度:O(n^3)

（4）利用两个栈S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）。
（本题20分）
参考解法：
void EnQueue(ElemType x)
{
    ElemType e;
    Stack s1,s2;
    if((!StackEmpty(s1)) && (!StackEmpty(s2)))      //如果两个栈都不为空则返回
        return;
    else if((!StackEmpty(s2)) && (StackEmpty(s1)))  //如果s1栈为空，s2栈不为空
    {
        while(!StackEmpty(s2))
        {
            Pop(s2,e);
            Push(s1,e);
        }
    }
    Push(s2,x);                                     //元素x入队列
}

void DeQueue(ElemType &x)
{
    ElemType e;
    if((!StackEmpty(s1)) && (!StackEmpty(s2)))      //如果两个栈都为空
        return;
    else if((!StackEmpty(s2)) && (StackEmpty(s1)))  //如果s1栈为空，s2栈不为空
    {
        while(!StackEmpty(s2))
        {
            Pop(s2,e);
            Push(s1,e);
        }
    }
    Pop(s1,x);                                     //元素x出队列
}

（5）编写一算法，以完成在带头节点单链表M中第n个位置前插入元素X的操作。（本题20分）
参考解法：
typedef struct node
{
    ElemType data;
    struct node *next;
}LNode;

void Insert(LNode *h,int n,ElemType x)
{
    int i=0;
    LNode *p,*q;
    p = h;
    q = p->next;
    while(q && i<n-1)
    {
        i++;
        p = q;
        q = p->next;
    }
    if(i<n-1) return;
    q = (LNode *)malloc(sizeof(LNode));
    q->data = x;
    q->next = p->next;
    p->next = q;
}
（6）编写一个利用二分法查找某值X是否存在于一组已知数据X1、X2、X3、……Xn中的程序。
（本题20分）

参考解法：
#include<stdio.h>
#define N 5
void main()
{
    char ch;
    int i,e,pos,low,high,mid,flag=1;
    int a[N];
    for(i=0;i<N;i++)                    //在数组a中读取一组从小到大排列的数
    {
        printf("input %dst number:",i+1);
        scanf("%d",&a[i]);
        if(i>0)
        {
            if(a[i]<=a[i-1])
            {
                printf("input a number which is bigger than %d\n",a[i-1]);
                i--;
            }
        }
    }
    while(flag)
    {
        for(i=0;i<N;i++)
            printf("%d ",a[i]);
        printf("\nWhich number you want to query?");
        scanf("%d",&e);
        pos = -1;
        low = 0;
        high = N-1;
        while(low<=high)
        {
            mid = (low+high)/2;
            if(a[mid]==e)
            {
                pos = mid;
                break;
            }
            else if(a[mid]>e)
                high = mid-1;
            else
                low = mid+1;
        }
        if(pos==-1) printf("*****Cant't find the element!*****\n");
        else    printf("*****The element's position is %d.*****\n",pos+1);