#include<stdio.h>
#include <malloc.h>
void InitList();

typedef int Datatype;
typedef struct linknode
{
    Datatype data;
    struct linknode *next;
}LinkList;
LinkList *head; 

LinkList * InitList(LinkList *head){
    head=(LinkList*)malloc(sizeof(LinkList));
    head->next=NULL;
    return head;
} 
//头插法
void CreateListH(LinkList*head,int n){
    LinkList *s;
    int i;
    printf("请输入%d个整数",n);
    for(i=0;i<n;i++){
        s=(LinkList*)malloc(sizeof(LinkList));
        scanf("%d",&s->data);
        s->next=head->next;
        head->next=s;
    }
    printf("建立链表成功！");
}
//尾插法
void CreateListL(LinkList *head,int n)
{
    LinkList *last,*s;
    int i;
    last=head;
    printf("请输入%d个整数：",n);
    for(i=0;i<n;i++){
        s=(LinkList *)malloc(sizeof(LinkList));
        scanf("%d",&s->data);
        s->next=NULL;
        last->next = s;
        last=s;
    }   
}
void DispList(LinkList *head)
{
    LinkList *p;
    p=head->next;
    while(p!=NULL){
        printf("%5d",p->data);
        p=p->next;
    }
    printf("\n");
}

int ListLen(LinkList *head){
    LinkList *p = head;
    int c=0;
    while(p->next){
        c++;
        p=p->next;
    }
    return c;
}



//按值查找
void locateElem(LinkList *head,Datatype x){
    LinkList *p = head->next;
    int c=1;
    while(p){
        if(p->data==x) {
            printf("%d所在位置%d\n",x,c);
            return;
        }
        c++;
        p=p->next;
    }
    printf("链表中不存在%d\n",x);
} 

//按位置查找
void getElem(LinkList *head,int pos) {
    LinkList *p = head->next;
    int i=1;
    int len = ListLen(head);
    if(pos<1 || pos>len) {
        printf("参数错误！");
        return ;
    }
    while(p){
        if(i==pos){
            printf("%d 位置上的值为 %d\n",pos,p->data);
            return;
        } 
        p=p->next;
        i++;
    }
}
//在pos处插入元素x 
void insertElem(LinkList *head,int pos,Datatype x){
    LinkList *p = head,*s;
    int i=0;
    int len = ListLen(head);
    if(pos<1 || pos>len+1) {
        printf("参数错误！");
        return ;
    }
    s = (LinkList *)malloc(sizeof(LinkList ));
    s->data = x;
    while(p->next){
        i++;
        if(i==pos){//p的下一个位置是要插入的位置 
            s->next = p->next;
            p->next= s;
            return;
        }
        p=p->next;
    }
    s->next = p->next;
    p->next= s;

}
//删除pos处元素x 
void delElem(LinkList *head,int pos,Datatype *x){
    LinkList *p = head,*s;
    int i=0;
    int len = ListLen(head);
    if(pos<1 || pos>len+1) {
        printf("参数错误！");
        return ;
    }
    while(p->next){
        i++;
        if(i==pos){//p的下一个位置是要插入的位置 
            s = p->next;//s将被删除 
            p->next= s->next;
            *x = s->data;
            free(s);
            return;
        }
        p=p->next;
    }
}

void sortedInsert(LinkList *head,Datatype x){
    LinkList * p = head,*s;
    s=(LinkList *)malloc(sizeof(LinkList ));
    s->data = x;
    while(p->next){
        if(p->next->data>=x){
            s->next = p->next;
            p->next =s;
            return;
        }else{      
            p=p->next;
        }
    }
    s->next = p->next;
    p->next =s;
}

void insertSort1(LinkList *head){
    LinkList * p;
    if(head->next){
        p = head->next->next;
        head->next->next=NULL;
        while(p){
            sortedInsert(head,p->data);
            p=p->next;
        }
    }   
}
void insertSort2(LinkList *head){
    LinkList * p,*q,*t;
    int f=0;
    if(head->next){
        p = head->next->next;
        head->next->next=NULL;
        while(p){
            q = p->next;
            t=head;
            f=0;
            while(t->next){
                if(p->data<=t->next->data){
                    p->next = t->next;
                    t->next = p;
                    f=1;
                    break; 
                }else{
                    t=t->next;
                }               
            }
            if(f==0){
                p->next = t->next;
                t->next = p;
            }
            p = q;
        }
    }   
}


int main(){
    LinkList *head;
    head = InitList(head);
    int n=5;
    int x=3;
    int  pos=2;


    //LinkList *head;
    /*
    CreateListH(head,n);
    DispList(head);
    */  
    CreateListL(head,n);
    DispList(head);


    insertSort2(head);
    DispList(head);
}