#include<stdio.h>
#include<stdlib.h>
//线性链表

typedef float elemtype;
typedef float status;

typedef struct lnode{
    elemtype data;
    struct lnode *next;
}lnode,*linklist;

int listlength_xx(linklist l){
    return (int)l->data;
}
//算法2.9
int insertlist_xx(linklist &l,int i,elemtype e){
    linklist li=l;
    //教材：int j=0;while(p&&j<i-1){p=p->next;++j;} if(!p||j>i-1) return error;下3行
    int j=1;
    for(;j<i;j++,li=li->next){}//循环到要插入的位置
    if(!li||j>i) return 1;
    linklist s=(linklist)malloc(sizeof(lnode));//创建一个新的结点，包含e
    s->data=e;
    s->next=li->next;
    li->next=s;
    l->data=l->data+1;//长度+1
    return 0;
}
//算法2.10
elemtype deletelist_xx(linklist &l,int i){
    linklist ld=l;
    //教材：int j=0;while(p->next&&j<i-1){p=p->next;++j}if(!(p->next)||j>i-1) return error;下3行
    int j=1;
    for(;j<i;j++,ld=ld->next){}//寻找第i个的前趋
    if(!(ld->next)||j>i) return NULL;
    linklist ll=ld->next;
    ld->next=ld->next->next;
    elemtype e=ll->data;
    free(ll);
    l->data=l->data-1;//长度-1
    return e;
}

void initlist_xx(linklist &l){
    l=new lnode;
    l->data=(elemtype)0;
    l->next=NULL;
}
//算法2.11    逆序创建表
void createlist_xx(linklist &l,int n){
    l=(linklist)malloc(sizeof(lnode));
    l->next=NULL;    
    l->data=(elemtype)n;
    for(int i=n;i>0;--i){
        linklist p=(linklist)malloc(sizeof(lnode));
        scanf("%f",&p->data);
        p->next=l->next;//插入在l中第一个有效数据之前
        l->next=p;//将新的有效数据列插在l->next
    }

}

void scanf_xx(linklist &l){
    printf("请输入你想输入元素个数：");
    int num=0;
    scanf("%d",&num);
    printf("开始输入：\n");
        elemtype e=0;
        for(int i=1;i<=num;i++){
            scanf("%f",&e);
            insertlist_xx(l,i,e);
        }
}
void printf_xx(linklist &l){
    linklist lp;
    lp=l;
    l=l->next;
    for(int i=0;i<lp->data;i++){
        printf("%f    ",l->data);
        l=l->next;
    }
    l=lp;
}
void listtraverse_xx(linklist &l,void (*p)(linklist &l)){
    (*p)(l);
}
//算法2.12    将两个有序链表并为一个有序链表（非递减排列）破坏性
void mergelist_xx(linklist &la,linklist &lb,linklist &lc){
    linklist pa,pb,pc;
    pa=la->next;pb=lb->next;lc=pc=la;//用la的头结点作为lc的头结点
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;//pa仅作改变是pa=pa->next
        }
        else{
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
        //假设la,lb都为12345
        //第一次，将pa插到pc（lc）后面，重赋pc为pa，又做pa=pa->next
        //第二次，将pb插到pc（pa）后面，重赋pc为pb，又做pb=pb->next
        //第三次，将pa查到pc（pb）后面，重赋pc为pa，又做pa=pa->next
        //......
        
    }


    pc->next=pa?pa:pb;
    lc->data=la->data+lb->data;
    free(lb);
}

void main(){
    linklist l;
    initlist_xx(l);

    printf("*********测试listtraverse_xx_scanf(insertlist_xx)    \n");
    listtraverse_xx(l,scanf_xx);
        printf("\n");


    printf("*********测试createlist_xx    \n");
    linklist ll;
    int n=NULL;printf("请输入你想输入元素个数：");scanf("%d",&n);
    createlist_xx(ll,n);
        printf("\n");

    //printf("*********测试listtraverse_xx_printf    \n");
    //listtraverse_xx(l,printf_xx);
        //printf("\n");

    printf("*********测试mergelist_xx    \n");
    linklist lll;
    mergelist_xx(l,ll,lll);
        printf("\n");

    printf("*********测试listtraverse_xx_printf    \n");
    listtraverse_xx(lll,printf_xx);
        printf("\n");
        

    //printf("\n*********测试listlength_xx    \n");
    //printf("表中的数据有 %d 个\n",listlength_xx(l));
        //printf("\n");

    //if(listlength_xx(l)>=3){
    //printf("*********当表数据大于等于3时，测试insertlist_xx    \n");
    //insertlist_xx(
        l,3,88);
    //printf("在第三个位置插为88后：    ");
    //listtraverse_xx(l,printf_xx);}
        //printf("\n");

    //if(listlength_xx(l)>=3){
    //printf("*********当表数据大于等于5时，测试deletelist_xx    \n");
    //printf("删除第5个    ---    ");
    //printf("删除的为：%f        删除后：",deletelist_xx(l,5));
    //listtraverse_xx(l,printf_xx);}
        //printf("\n");


}

学习记录