wumurong.c

通过使用链表对一组数进行排序,并可以在此已排序的的数组插入数并自动进行排序

/**************************************************************
    通过链表建立一个整数序列并排序，可按序在序列中插入一个数
    吴木荣
    2007年12月17日
***************************************************************/
#include <stdio.h>

struct xulie{
                int e;
                struct xulie * next;
            };
int add_xl(struct xulie *);/*建立一个整数序列*/
int paixu(struct xulie *); /*对序列排序*/
int insert_xl(struct xulie *);/*按序插入一个数*/
int show_xl(struct xulie *);/*输出序列*/

int main(void)
{
    struct xulie * head;

    int i;
    head = (struct xulie *)malloc(sizeof(struct xulie));/*定义头节点*/
    if (!head)            /*分配不成功*/
        printf("error");
    head->next=NULL;
    add_xl(head);
    printf("the last number line:");
    show_xl(head);
    paixu(head);
    printf("\n");
    printf("the new number line:");
    show_xl(head);
    printf("\n");
    while(getchar() != '\n') /*消除之前的非法字符*/
        continue;
    insert_xl(head);
    show_xl(head);

    getch();

    return 0;
}

int add_xl(struct xulie * h)
{
    int i;
    struct xulie * prav,* curr;
        
    prav = h;
    printf("Enter number:");
    while(scanf("%d",&i) == 1 && i != '\n')
    {
        while(getchar() != '\n')
            continue;
        curr=(struct xulie *)malloc(sizeof(struct xulie));
        if (h->next == NULL)
            h->next=curr;
        else
            prav->next=curr;
        curr->next=NULL;
        curr->e=i;
        printf("next number<enter char to end>:");
        prav=curr;
    }
    putchar('\n');

    return 0;
}

int paixu(struct xulie * h)
{
    struct xulie * p=h,* q;
    int m;

    p=h->next;
    while(p)
    {  
        q=p->next;
        while(q)
        {
            if(p->e > q->e)
                {
                    m=p->e;      /*做值传递*/
                    p->e=q->e;
                    q->e=m;
                 }
            q=q->next;
    }
    p=p->next;
 }

    return 0;
}

int insert_xl(struct xulie *h)
{
    struct xulie * p=h->next,* q, *s;
    int i;

    s=(struct xulie *)malloc(sizeof(struct xulie)*1);
    printf("enter insert number:");
    scanf("%d",&i);
    s->e=i;
    while(getchar() != '\n')
        continue;
    if (!p)
    {
        h->next=s;
    }
    if(i<p->e)         /*插入小于序列第一个数的整数*/
    {
        s->next=p;
        h->next=s;
        return 1;
    }
    while(p)           /* 在序列中插入数*/
    {

       if(i>p->e)
       {
            q=p;
            p=p->next;
            if(!p)        /*插入序列最后节点后*/
            {
            q->next=s;
            s->next=NULL;
            }
       }
       else
       {
            s->next=p;
            q->next=s;
            break;
       }

    }


    return 0;
}

int show_xl(struct xulie *h)
{
    struct xulie * p=h;
    int i;
    p=p->next;
    while (p)
    {
        printf("%2d--->",p->e);  /*输出序列*/
        p = p->next;
    }

    return 0;
}