printf("\n");
}
void main()
{
    int i;
    LNode *h,*p;
    h = (LNode *)malloc(sizeof(LNode));
    if(!h)  exit(0);
    h->data = 0;
    h->next = NULL;
    for(i=1;i<=20;i++)
    {
        p = (LNode *)malloc(sizeof(LNode));
        p->data = i;
        p->next = h->next;
        h->next = p;
    }
    print(h);
    convert(h);
    print(h);
}
（3）设定串采用顺序存储结构，求串s1和串s2的一个最长公共子串的长度，并指出该最长
公共子串分别在s1和s2中的起始位置。（本题15分）
参考解法：
#include<stdio.h>
void maxcomstr(char s1[],char s2[],int &p1,int &p2,int &len)
{
    int i=0,j=0,k=0;
    while(s1[i] != '\0')
    {
        j = 0;
        while(s2[j] != '\0')
        {
            if(s1[i] == s2[j])
            {
                k = 1;
                while(s1[i+k] != '\0' && s2[j+k] != '\0' && s1[i+k]==s2[j+k])
                    k++;
                if(k>len)
                {
                    p1 = i;
                    p2 = j;
                    len = k;
                }
            }
            j++;
        }
        i++;
    }
}

void main()
{
    int i,p1=0,p2=0,len=0;
    char a[80],b[80];
    printf("input string a:");
    gets(a);
    printf("input stirng b:");
    gets(b);
    maxcomstr(a,b,p1,p2,len);
    printf("The common string is : ");
    for(i=0;i<len;i++)
    {
        printf("%c",a[p1+i]);
    }
    printf("\nString a Position:%d\n",p1+1);
    printf("String b Position:%d\n",p2+1);
    printf("The lenght of common string is :%d\n",len);
}

（4）设单链表中存放n个字符，试设计一个算法，使用栈判断该字符串是否中心对称，如
xyzzyx即为中心对称字符串。（本题15分）
参考解法：
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    char data;
    struct node *next;
}LNode;
int dui(LNode *h,int n)
{
    int i;
    LNode *top,*p,*q;
    top = NULL;
    p = h->next;
    for(i=0;i<n/2;i++)
    {
        q = (LNode *)malloc(sizeof(LNode));
        q->data = p->data;
        q->next = top;
        top = q;
        p = p->next;
    }
    if(n%2==1)  p = p->next;
    q = top;
    while(q != NULL && q->data == p->data)
    {
        top = q->next;
        free(q);
        p = p->next;
        q = top;
    }
    if(!top)    return 1;
    else return 0;
}

void print(LNode *h)
{
    h = h->next;
    while(h)
    {
        printf("%c",h->data);
        h = h->next;
    }
    printf("\n");
}
void main()
{
    int n=0;
    char ch;
    LNode *h,*p;
    h = (LNode *)malloc(sizeof(LNode));
    h->next = NULL;
    scanf("%c",&ch);
    while(ch != '\n')
    {
        p = (LNode *)malloc(sizeof(LNode));
        p->data = ch;
        p->next = h->next;
        h->next = p;
        n++;
        scanf("%c",&ch);
    }
    print(h);
    if(dui(h,n))
        printf("Symmetrical!\n");
    else
        printf("Not symmetrical!\n");
}

（5）编写算法找出从自然数1,2,...,n中任取r个数的所有组合。（本题15分）
参考解法：
#include<stdio.h>
void f(int n,int r,int a[],int m)
{
    int i;
    if(r==0)
    {
        for(i=0;i<m;i++)
        {
            printf("%d",a[i]);
        }
        printf(" ");
    }
    else
    {
        for(i=n;i>=r;i--)
        {
            a[m] = i;
            f(i-1,r-1,a,m+1);
        }
    }
}

void main()
{
    int n,r,m=0;
    int a[80];
    printf("please input n and r :");
    scanf("%d%d",&n,&r);
    f(n,r,a,m);
    printf("\n");
}

（6）设计一个计算二叉树各结点的子孙个数的算法。
参考解法：
typedef struct BiNode
{
    BElemType data;
    struct BiNode *lchild,*rchild;
}BiNode;

int count(BiNode *b)
{
    if(b==NULL) return 0;
    if(b->lchild==NULL && b->rchild=NULL)
        return 1;
    else
        return(count(b->lchild)+count(b->rchild)+1);
}

（7）已知一棵二叉树的先序序列和中序序列，则可唯一确定一棵二叉树。（本题20分）
<1>设计一个算法由先序序列和中序序列构造二叉树
<2>若先序序列为abcdefg，中序序列为cbaefdg，画图构造对应的二叉树，并写二叉树的后序
序列。
参考解法：
<1>
#include<stdio.h>
#include<stdlib.h>
#define N 100
typedef struct node
{
    char data;
    struct node *lchild,*rchild;
}BiNode;

void createBiTree(BiNode *&root,char a[],int a_start,int a_end,char b[],int b_start,int b_end)
{
    int k;
    char ch;
    if(a_start>a_end)
        root = NULL;
    else
    {   ch = a[a_start];