Day01-Day50

/**
一、带头结点的顺序表。删除所有值为x的结点，并释放其空间
算法思想：
1.找遍历顺序表，找到值为x的元素,并用k记录其个数
2.删除（移动）
**/
/*法一：遍历顺序表，用k记录x的个数，将其中不为x的元素向前移动k个单位*/
void Del_x(SqList &L,ElemType x){
    int i;
    for(i=0;i<L.length;i++){
        int k=0;
        if(L.data[i]==x){
            k++;
        }
        else{
            L.data[i-k]=L.data[i];//非x元素向前移动k个单位
        }     
    }
    L.length=L.length-k;
}
/*法二：遍历顺序表，只需保留下不是x的值*/
void Del_x(SqList &L,ElemType x){
    int k=0;
    for(i=0;i<L.length;i++){
        if(L.data[i]!=x){
            L.data[k]=L.data[i]
            k++;
        }   
    }
    L.length=k;
}

/**
二、将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
思想：
将A、B中较小值一次值依次存入C
**/

bool Merge(SqList A,SqList B, SqList &C){
    if(A.length + B.length > C.length) return false;
    int i=0,j=0,k=0;
    while(i<A.length && j<B.length){
        if(A.data[i] < B.data[j]){
            C.data[k]=A.data[i];
            i++;
            k++;
        }
        else{
            C.data[k]=B.data[j];
            j++;
            k++;
        }
    }
     //如果A中有剩余，依次写入C中
       while(i<A.length){
        C.data[k++]=A.data[i++];
       }
       while(j<A.length){
        C.data[k++]=B.data[j++];
       }
       C.length=k;
       return true;
}

/**
三、设计一个高效算法，将顺序表L的所有元素逆置，要求算法空间复杂度为O(1)
思想：第i个数与n-i个数交换即 L.data[i]与L.data[L.length-1-i]交换
**/
法一：常规方法
void reverse(SqList &L){
    ElemType temp;
    for(int i=0;i<length/2;i++){
        temp =L.data[i];
        L.data[i]=L.data[L.length-1-i];
        L.data[L.length-1-i]=temp;
    }
}  
法二：递归（递归空间复杂度不符合O(1)）
void reverse(int *A, int i,int j){
    if(i<j){
        swap(A[i],A[j]);
        reverse(A,i+1;j-1;)
    }
}

/**
四、带头结点的单链表。删除所有值为x的结点，并释放其空间
算法思想：扫描单链表，遇到值为想的结点就将其删除
1.需要三个指针：p：当前结点，pre：p的前驱；q:用来保存p
**/
typedef struct LinkNode{
    int data;
    struct *next;
}LinkNode,*SqList;
void Del_x(LinkList &L, ElemType x){
    LNode *p=L->next, *pre=L, *q;
    while(!p){
        if(p->data==x){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }
        else{//如果不等于x，pre和p都向后移
            pre=p;
            p=p->next;
        }
    }
}

/**
五、从顺序表中删除其值在s与t之间的所有元素，如果s或t不合理或顺序表为空，显示错误信息并返回
思想：
**/
法一：移动
bool Dels_t(SqList &L,int s,int t){
    int k=0;
    for(i=0;i<L.length;i++){
        if(L.data[i]>=s && L.data[i]<=t){
            k++;
        }else{
            L.data[i-k]=L.data[i];
        }
    }
    L.length -= k;
    return true;
}

法二：保留不在s与t之间的数
 bool Dec_s_t(SqList &L,int s, int t){
    int i=0,k=0;
    if(L.length==0) {
        cout<<"L 不能为空！";
        return false;
    }
    if(s>t) {
        cout<<"s与t输入错误！";
        return false;
    }
    for(i=0;i<L.length;i++){
        if(L.data[i]<=s ||L.data[i]>=t){
            L.data[k++]=L.data[i]
        }
    }
    L.length=k;
    return true;
}

/**
六、从有序顺序表中删除所有重复元素
思想：利用两个工作指针遍历,不重复就保留，重复就不保留（删除）。
1.首先i指向L.data[0], j指向L.data[1]，
2.如果两数不相同，保留，j后移
  如果相同，不保留，j后移
**/
void del_same(SqList &L){
    for(i=0;j=1;j<L.length;j++)
    if(L.data[i]!=L.data[j]){
        L.data[++i]=L.data[j];//保留之前要i++
    }
}

/**
七、一维数组中A[m+n]一次存放两个线性表(a1,a2,..am)和(b1,b2,..bn)。编写函数，将数组中两个顺序表的位置互换
思想：三次逆置 (a1,a2,..am)逆置，再(b1,b2,..bn)逆置；最后整体逆置
**/
void exchage(int A[],0,m+n){
    reverse(A,0,m-1);
    reverse(A,m,m+n-1);
    reverse(A,0,m+n-1);
}
void reverse(int A[], int a,int n){
    ElemType temp;
    for(i=a;i<n;i++){//第i个元素与第n-i个进行交换
        temp=A[i];
        A[i]=A[L.length-1-i];
        A[L.length-1-i]=temp;
    }
    
}

/**
八、【2010统考真题】设将n(n>1)个整数存放到一维数组R中。设计一个尽可能高效的算法
将R中保存的序列循环左移p(o<p<n)个位置，数据由(X0,X1,X2,...Xn-1)变换为(Xp,Xp+1,..Xn-1,...X1,X2,..Xp-1)
思想：三次逆置  (X0,X1,X2,...Xp-1)逆置；(Xp,XP+1,...Xn-1)逆置；再整体逆置
**/

/**
九、带头结点的单链表中，删除最小值所在的结点（假设唯一）
思想：1.找最小值 两个指针  2.删除 两个指针
用指针p遍历，指针minp 标记最小值结点，（要删除还需要知道前驱）
pre指向p的前驱，minpre指向minp的前驱
扫描过程中，如果p->data小于minp->data;则将p，pre分别赋值给minp和minpre
扫描完毕后，minp标记的就是最小值所在的结点，删除该结点
**/

LinkList Delete_min(LinkList &L){
    LNode *pre=L, *p=pre->next;
    LNode *minpre=L, *minp=p;
    while(!p){
        if(p->data<minp->data){
            minp=p;
            minpre=pre;
        }
        pre=p;
        p=p->next;
    }
    //删除
    minpre->next=minp->next;
    free(minp);
    return L;

}

/**
十、头插法建立单链表:元素生成次序相反。元素逆置时可以使用尾插法
思想：指针S指向即将被插入结点，S->next=L->next; L->next=S; 每增加一个结点，从头结点的后面插入
**/

LinkList insert_head(LinkList &L){
    LNode *S, int x;
    L = (LinkList)malloc(sizeof(LNode));//创建头结点
    L->next=NULL;
    scanf("%d ",&x);
    while(x!=NULL){
        S = (LinkList)malloc(sizeof(LNode));//创建头结点
        S->data;
        S->next=L->next;
        L->next=S;
    }
    return L;
}

    
/**
十一、尾插法 
思想：r->next=S; r=S;
**/
LinkList insert_tail(LinkList &L){
    LNode *S, *r=L;
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    scanf("%d",&x);
    while(x!=NULL){
        S=(LinkList)malloc(sizeof(LNode));
        S->data=x;
        r->next=S;
        r=S;
    }
    r->next=NULL;
}
    

    
/**
十二、将带头结点的单链表就地逆置
思想：使用头插法依次将结点重新插入单链表
逆置就想到头插法
防止断链：r指针标记，保留p的后继，直到r为空
**/
法一：
LinkList reverse_linklist(LinkList &L){
    LNode *P=L->next, *r=p->next;
    L->next=NULL;//头结点指向空
    while(p!=NULL){
        r=p->next;//保留后继，防止断链
        //头插法
        p->next=L->next;
        L->next=p;
        //p，r向后移动
        p=r;
    }
    return L;
}
法二：改变链表指针方向：将p的后继，指向p的前驱
使用三个指针pre，p，r，
LinkList reverse_linklist(LinkList &L){
    LNode *pre=L->next,
    *P=pre->next,
    *r=p->next;
    pre->next=NULL;//第一个结点的后继指向空
    while(r!=NULL){
        p->next=pre;
        pre=p;
        p=r;
        r=r->next;
    }
    L->next=p;//最后，r指向空，头结点指向最后一个结点
    return L;
}

/**
十三、带头结点的单链表，结点值无序，编写函数删除大小介于s与t之间的元素
思想：1.找 2.删除
遍历链表，删除在最小值和最大值之间的数
**/
void Dels_t_Link(LinkList &L int s,int t){
    LNode *pre=L, *p=L->next;

    while(p!=NULL){
        if(p->data>=s && p->data<=t){
            pre->next=p->next;
            free(p);
            p=p->next;
        }
        else{//如果不是，两个指针都向后移
            pre=p;
            p=p->next;
        }
    }
    
}

/**
十四、给定两个单链表，编写算法找出两个单链表的公共结点  双指针问题
若有公共结点，链表形状是Y型， ○ → ○ → ○ → ○ ↘           而不是X型
                                            ○ → ○ → ○
                                ○ → ○ → ○ ↗
思考：1.如何判断链表有公共结点? ----》 p,q同时到达表尾时，p=q 说明有公共结点；没有p=q 说明不存在公共结点
    2.如何同时到达表尾？ 长度相等好办，长度不相等呢？   ----》 若LA较长，LA表的p指针先移动k次(k=LA.length-LB.length)然后p,q再同步向后移动
**/
法一：暴力法；两次循环 时间复杂度O(LA x LB)
search_commmon(LinkList &LA,LinkList &LB){
        while(p!=NULL){
            while(q!=NULL){
            if(p=q){    //p=q,说明两个表的结点相遇/重合
                return p;
            q=q->next;
            }
            p=p->next;//一轮之后，没找到，p后移一个单位
        }
    }
    
法二：线性的方法优化后：O(2LA + LB) 也就是 O(LA+LB)
LinkList search_commmon(LinkList &LA,LinkList &LB){
    int k;
    int lenA=length(LA);
    int lenB=length(LB);
    if(lenA-lenB){
        k=lenA-lenB;    //求出两个链表之差
    }else {
        k=lenB-lenA;
    }
    p=LA->next;
    q=LB->next
    while(k--){ //p先移动k位
        p=p->next;
    }
    while(p!=NULL){
        if(p=q) return p; //若p=q，则找到了公共结点
        else{             //若不等，则同步向后移动
            p=p->next;
            q=q->next;
        }
    }
    return 0;   //如果最后都没用p=q，说明没有公共结点
}

/**
十五、将带头结点的单链表A 分解为两个带头结点的单链表A和B；
使得A表中含有原表中序号为奇数的元素，B表中含有原表中序号为偶数的元素，且保持其相对顺序不变
分析：要保持顺序不变，自然想到尾插法
思想：不断地使用尾插法，依次生成链表A、B
**/
LinkList create(LinkList &L){
    int i=0;
    B = (LinkList)malloc(sizeof(LNode));
    LNode *ra,*rb=B;  //A和B的表尾指针
    p=A->next;

    while(p!=NULL){
        i++;
        if(i%2==0){ //如果是偶数，插入B中
            rb->next=p;
            rb=p;
        }
        else{   //如果是奇数，插入到A中
            ra->next=p;
            ra=p;
        }
        p=p->next;
    }
    ra->next=NULL;
    rb->next=NULL;
    return B;
}
   

/**
十六、将带头结点单链表C={a1,b1,a2,b2,...an,bn}拆分成两个单链表
使得A={a1,a2,...an},B={bn,...b2,b1}
分析：对于A使用尾插法；对B采用头插法
        头插防断链；尾插留指针
**/
LinkList create(LinkList &hc){
    LNode *ra=hc;   //尾插法的尾指针
    LNode *p=hc->next;  //遍历指针

    A=(LinkList)malloc(sizeof(LNode));
    B=(LinkList)malloc(sizeof(LNode));
    A->next=NULL;
    B->next=NULL;
    while(p!=NULL){//头插尾插交替进行，不必使用i
        ra->next=p;//尾插法插入A
        ra=p;
        p=p->next;
        if(p!=NULL){
            r=p->next;  //标记防断链
            p->next=B->next; //头插法插入B
            B->next=p;
            p=r;
        }       
    }
    ra->next=NULL;
}

/**
十七、递增有序的单链表中，删除重复的结点
分析：递增有序，则重复元素是相邻的
    1.找    2.删(需要知道前驱pre)  双指针（也可以用后继，如法二）
**/
法一：双指针pre、p
void del_same(LinkList &L){
    LNode *pre=L->next, *p=pre->next;
    while(p!=NULL){
        if(pre->data==p->data){
            pre->next=p->next;
            free(p);
            p=p->next;
        }
        else{   //两个指针同时向后移一位
            pre=p;
            p=p->next;
        }
    }
}

法二：一个指针p (实际还是双指针的思想，需令q=p->next)
void del_same(LinkList &L){
    LNode *p=L->next,*q;
    while(p->next!=NULL){
        q=p->next;
        if(p->data==q->data){
            p->next=q->next;
            free(q);
            p=p->next;
        }
        else{
            p=p->next;//相较法一，这里就只需移动一个指针了
        }
    }
}

/**
十八、两个按元素值递增次序排列的单链表，编写算法将两个单链表归并为一个元素值递减排列的单链表
要求利用原本的单链表结点存放归并后的单链表
思想：不断地将较小数头插法插入入合并链表，被插入结点的的指针后移一位，直到某一条链表为空
**/

LinkList Merge(LinkList &LA,LinkList &LB){
    LNode *p=LA->next,*q=LB->next;
    A->next=NULL;
    while (p!=NULL){
        while(q!=NULL){
            if(p->data > q->data){ //将B中较小数头插入A, q后移继续比较
                r=q->next;//防止断链
                q->next=LA->next;
                LA->next=q;
                q=r;//q向后移动
            }
            else{ //若p->data较小，p结点头插入A，p后移一位，继续比较
                r=p->next;
                p->next=LA->next;
                LA->next=p;
                p=r;
            }
        }    
    }
    //q==NULL,但p！=NULL;将A中剩余部分依次头插入A，或者改变指针方向
    while(p!=NULL){
        r=p->next;
        p->next=LA->next;
        LA->next=p;
        p=r;
    }
    //若p=NUUL;但q!=NULL；将B中剩余的依次头插入A，或者改变指针方向
    while(q!=NULL){
        r=q->next;
        q->next=LA->next;
        LA->next=q;
        q=r;
    }
}

/**
十九、A和B是两个单链表，其中元素递增有序，设计算法从A、B中的公共元素产生单链表C，要求不破坏A、B的结点（即不能改变其指针，只能申请新结点）
思想：表A、B有序，依次比较A、B元素。小的指针往后移，
若相等则创建新的结点，其元素值等于两结点的值。
使用尾插法插入到新表中，并将两个指针同时后移一位，直到表尾（若有剩余，无需处理）
**/

LinkList common(LinkList A,LinkList B){
    LNode *p=A->next,*q=B->next;
    LNode *r;
    LinkList C = (LinkList)malloc(sizeof(LNode));
    r=C;
    while(p!=NULL && q!=NULL){
        if(p->data<q->data){
            p=p->next;
        }
        else if(p->data>q->data){
            q=q->next;
        }
        else if(p->data==q->data){  //若两个元素相等
            S=(LinkList)malloc(sizeof(LNode));
            S->data=p->data;
            r->next=S;
            r=S;
            p=p->next;  //两个指针同时向后移
            q=q->next;
        }
        r->next=NULL;
        return C;   
    }
 
}

/*************
二十、两个链表A、B分别表示两个集合，其元素递增有序排列。编写函数求A、B的交集，并存放于A链表中
分析：A中只能存放公共元素，不符合要求的结点要释放掉 边比较边释放空间
算法思想：
1.依次扫描A、B结点，比较扫描结点data域的值，将较小的指针向后移（并释放空间）
2.若两者相等，尾插入A，直到遍历表尾
3.若有剩余，则剩余元素不可能有交集，全部释放）
**/
LinkList common(LinkList &A,LinkList &B){
    LNode *p=A->next,*q=B->next, *r,*u;
    A->next=NUll;//尾插尾结点置空，p保留了A的后继，不用担心断链
    r=A;
    while(p!=NULL&&q!=NULL){
        if(p->data<q->data){
            u=p;
            p=p->next;
            free(p);
        }
        else if(p->data > q->data){
            u=q;
            q=q->next;
            free(u);
        }
        else if(p->data==q->data){  //如果两元素相等，保留p，释放q
            //保留p，尾插入A
            r->next=p;
            r=p;
            p=p->next;
            //释放q
            u=q;
            q=q->next;
            free(u);
        }
    }
    while(p!=NULL){ //若A有剩余
        u=p;
        p=p->next;
        free(u);
    }
    while(q!=NULL){ //若B有剩余
        u=q;
        q=q->next;
        free(u);
    }
    r->next=NULL;
    return A;
}

/**
二十一、两个整数序列A={a1,a2,...am}和B={b1,b2,..bn}已经存入两个单链表中，设计一个算法，判断序列B是否是A的连续子序列
算法思想：1）暴力法：依次遍历A、B，比较p->data与q->data，若相等，一起后移
                    若不等，A从上次开始比较结点的后继开始，B从头开始，直到B到尾结点，表示匹配成功
                    若A链表到了末尾，但B链表未到末尾，则匹配失败

**/1

法一：暴力法
bool son_(LinkList A,LinkList B){
    LNode *p=A->next,*q=B->next;
    LNode *pre=p;
    while(p!=NULL&&q!=NULL){
        if(p->data!=q->data){//如果发现不相等了，p要回到上次开始的后继，q回到B第一个元素位置
            pre=pre->next; //上次开始的后继
            p=pre;
            q=B->next;//q回到B的头结点的后继（即第一个元素的位置）
        }
        else{
            p=p->next;
            q=q->next;
        }
    }
    //循环结束后，如果q走到了最后（q=NULL），则匹配成功；（无论p此时在单链表的中间还是末尾）
    if(q==NULL){
        return true;
    }
    else 
        return false;
}

/**
二十二、设计一个算法用于判断带头结点的循环双链表是否对称
思想：循环双链表画成一个环，如果p->data=q->data, 两个指针同时后移
    让p从左往右移动(p=p->next),q从右往左移动(q=q->prior)扫描，
    直到他们指向同一结点（偶数个）或他俩是相邻结点（奇数个），则他们是对称的

**/

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode;

int symetry(DLinkList L){
    DNode *p=L->next, *q=L->prior;
    while(p!=q){    //如果是对称的，就算是奇数个结点，第一次p、q相邻后，继续遍历，直到最后回到开始结点，也是p=q;
        if(p->data==q->data){
            p=p->next;
            q=q->prior;
        }else{
            return 0;
        }
    }
    return 1;//能从循环跳出。说明对称了
}

/**
二十三、两个循环单链表，表头指针分别为h1和h2，将链表h2链接到h1链表之后，要求连接之后的链表扔保持循环链表的形式
思想：找到好h1的表尾p，h2的表尾q；然后将p指向h2，将q指向h1，变成一条循环单链表
**/
LinkList link(LinkList &h1,LinkList &h2){
    LNode *p=h1->next,*q=h2->next;
    p=h1;//找h1的表尾
    while(p->next!=h1){
        p=p->next;
    }
    q=h2;//找h2的表尾
    while(q->next!=h2){
        q=q->next;
    }
    //将p指向h2，q指向h1
    p->next=h2;
    q->next=h1;
}

/**
二十四、从带头结点的循环单链表中反复找出最小值的结点并输出，然后将该结点从中删除
思想：反复找出当前的最小值，并删掉，直到链表为空，再释放头结点
**/
void Del_all(LinkNode *L){
    LNode *pre=L, *p=L->next;
    LNode *mipre=L, *minp=L->next;
    while(L->next!=L){
        while(p!=L){    //当P的后继不是头结点时，
            if(p->data<minp->data){
                minp=p;
                minpre=pre;
            }//pre和p向后移
            pre=p;
            p=p->next;
        }
        printf("%d",minp->data);
        minpre->next=minp;
        free(minp);
    }
    free(L);//最后释放头结点；
}

/**
二十五、带头结点的非循环双向链表，其每个结点除了有prior（前驱指针）data（数据）和next指针（后继）域外，还有一个访问频度域freq。
在链表被启用前，其值均初始化为零。每当再链表中进行Locate(L,x)操作时，
分析：1.找到x的结点，freq++
    3.取下x结点，根据freq的大小插入x结点
**/
DLinkList Locate(DLinkList &L,int x){\
    LNode *p=L->next,*q;
    while(p!=NULL&&p->data!=x){
        p=p->next;
    }
    if(p==NULL) {
        printf("不存在值为x的结点");
        exit(0);
    }else{//找到值为x的结点，freq++
        freq++;
        //1.取下该结点。2.根据preq的大小插入合适的位置
        if(p->next!=NULL){ 
            //1.取下该结点，即从原表中删除
            p->next->prior=p->pre;
            p->pre->next=p->next;
            //2.往前寻找。找到第一个比它大的结点，插入其后
            while(q!=NULL&&q->freq<=p->freq){
                q=q->prior;
            }
            p->next=q->next;//(1)
            q->next->prior=p;//(2)
            p->prior=q;//(3)
            q->next->p;//(4)一定要在(1)、(2)之后。防止断链找不到
        }
    }
}

/**
二十六、单链表结构为data域link域。只给出头指针list，查找倒数第k个位置上的结点，尽可能高效
思想：双指针，间隔一定，同步后移
**/
int search_k(LinkList list,int k){
    LNode *p=list->link,*q=list->link;
    int count =0;
    while(q!=NULL){
        if(count<k){    //q先到达第k个位置
            count++;    //直到count=k;
            q=q->link;
        }
        else{           //p、q同时后移
            p=p->link;
            q=q->link;
        }
    }
    //处理边界或者极端情况
    if(count<k){    //k大于链表长度
        printf("k值过大！");
        exit(0);
    }
    return q->data;
}
    

/** 对比十四题 双指针，间隔一定，同步后移
二十七、假定采用带头结点的单链表保存两个单词有相同的后缀，可享受相同的后缀存储空间。比如loading,reading 
"若有公共结点，链表形状是Y型"
法一：暴力法（双重循环）O(mxn)
法二：只遍历一次 （较长的先移动|A.len-B.len|次）O(m+n)
算法思想：1.求出str1与str2所指链表的长度m和n
        2.将较长的链表先移动|m-n|次
        3.反复将p、q指针后移。直到p、q指向同一指针(p=q)
**/

LN0de Fun_search_common(LinkList str1,LinkList str2){
    LNode *p,*q;
    int m,n;
    m=listlen(str1);
    n=listlen(str2);
    for(p=str1->next;m>n;m--){//m大m移动m-n次
        p=p->next;
    }
    for(q=str2->next;n>m;n--){//n大n移动n-m次
        q=q->next;
    }
    while(p!=NULL&&q!=NULL){
        if(p=q) return p;
        else{
            p=p->next;
            q=q->next;   
        }
    }
    return 0;   //直到最后p、q也没有合并，说明没有公共部分
}
int listlen(LinkList L){
    LNode *p=L->next;
    int count=0;
    while(p!=NULL){
        count ++;
        p=p->next;
    }
    return count;
}

/**
二十八、移动单链表保存m个整数，结点结构为[data][link]，且|data|<= n(n正整数)，现要求设计一个时间复杂度尽可能高效（暗示可以以空间换时间）
的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点，而删除其余绝对值相等的结点
分析：第一次出现保留，其余均删除（取绝对值）
标记数组：从链表中的值转化为数组中次序：如链表第一个元素的值为-20，那么数组data[20]置为1，表示已经20或-20出现过了
算法思想：申请一个大小为n+1个辅助空间（初始为0），第一次出现，保留（标记从0变1）否则删掉结点
**/

    C=(int)malloc(sizeof(int*)(n+1));
    for(int i=0;i<n+1;i++){
        C.data[i]=0;
    }
    while(p!=NULL){
        m=p->data > 0 ? m=p->data : m=- p->data ;
        if(C.data[m]==0){ //第一次出现，需要保留
            C.data[m]=1;
            p=p->next;
        }
        else{//不是第一次出现，则删除
            pre->next=p->next;
            free(p);
            p=p->next;
        }
    }

/**
二十九、将单链表{a1,a2,a3,...an-1,an-1,an}重新排列变为{a1,an,a2,an-1,a3,an-2...} 要求空间复杂度为O(1)且时间上尽可能高效
思想：1.找到中间结点---》快慢指针p每移动一次，q移动两次
    2.将后半段逆置---》{a1,a2,a3,....,an,an-1,an-2,...} 头插法
    3.合并插入---》后半段的结点依次插入到合适的位置,（或把所有结点都摘下来再用尾插法
**/
void change(LinkList &L){
    LNode *p=L->next,
    while(q->next!=NULL){   //p走一步，q走两步
        p=p->next;
        q=q->next;
        if(q->next!=NULL){  //如果q->next不为空，q走第二步
            q=q->next;
        }
    }
    q=p->next;  //让q指向中间结点p的后一个位置
    while(q!=NULL){ //使用头插法逆置后半段 头插放断链
        r=q->next;
        q->next=p->next;
        p->next=q;
        q=r;
    }
    S=L->next;
    q=p->next;
    while(q!=NULL){
        r=q->next;
        q->next=S->next;
        S->next=q;
        S=q->next;//更改S位置，移动到下一插入位置
        q=r;
    }
}

/*********************************/
顺序存储结构通常用来存完全二叉树或满二叉树
思考：对于一颗普通二叉树，如何使用顺序存储？
    普通二叉树----》完全二叉树（补空结点）
/********************************/
/**
三十一、一直一颗二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个结点的最近公共祖先结点的值
思想：不断地将较大的取一半，然后比较i和j的大小，直到i=j
**/
ElelType com_ancestor(BTree T,int i, int j){
    if(T[i]!=NULL&&T[j]!=NULL){
        while(i!=j){
            if(i>j){
                i=i/2;
            }
            else{
                j=j/2;
            } 
        }
    }
   return T[i];
}

/**
三十二、先续Preorder、中序Inorder、后序Postorder的递归算法
时间复杂度O(n)。空间复杂度O(n)(最坏情况想退化成链表)
**/
typedef struct BiTree{
    ElemType data;
    struct BiTNode *lchild;
    struct BItNode *rchild;
}BItNode,BiTree;

vod Preorder(BiTree T){        void Inorder(BiTree T){         void Postorder(BiTree T){
    if(T!=NULL){                    if(T!=NULL){                    if(T!=NULL){
        visit(T);                       Inorder(T->lchild);             Postorder(T->lchild);
        Preorder(T->lchild);            visit(T);                       Postorder(T->rchild);
        Preorder(T->rchild);            Inorder(T->rchild);             visit(T);
    }                               }                               }
}                               }                               }

/**
三十三、二叉树遍历非递归算法(经常考)                        ○
中序：☆❤️入栈向左一直走，出栈访问右子树
    1、沿着根的左孩子。依次入栈，直到左孩子为空
    2、栈顶元素出栈并访问；若其右孩子为空继续出栈
    3.否则执行1
**/
void Inorder2(BiTree T){
    while(p&&!isEmpty(S)){ //栈不为空。且指针不为空(栈空不一定遍历完)
        if(p){
            push(S,p);  //一路向左；
            p=p->lchild;//左孩子不空，一直向左
        }
        else{
            Pop(S,p);
            visit(p);   //栈顶元素出栈并访问
            p=p->rchild;//向右子树
        }
    }
}

/**
三十四、
后序：❤️入栈向左一直走，判定（右子树），出栈访问，标记，重置
    1、沿着跟的左孩子依次入栈，直到左孩子为空
    2、读栈顶元素（判定）若其右子树不为空且未被访问；对右子树执行1
    3、如果右子树为空或已被访问，栈顶元素出栈并访问
**/
void Postorder2(BiTree T){
    InitStack(S);
    p=T;
    r=NULL;
    while(p&&!isEmpty(S)){
        if(p){
            p=p->lchild;
        }
        else{
            GetTop(S,p);//读取栈顶元素，判定
            if(p->rchild && p->rchild !=r){ //若右子树不为空且未被访问
                p=p->rchild;//指向右子树
                push(S,p);  //入栈
                p=p->lchild;//指向左孩子
            }
            else{   //若右子树为空或被访问过，
                pop(S,p);   //栈顶元素出栈并访问、标记
                visit(p->data);
                r=p;    //  r标记最近结点
                p=NULL; //已经出栈了，就没必要继续指向它了，置空
            }
        }
    }
}

/**
三十五、二叉树的层次遍历 
❤️入队出队访问；有左入左，有右入右
算法思想：
1、（队列）将根结点入队，出队、访问出队结点
2、若它有左子树则将左子树入队，若它有右子树则将右子树入队
然后出队，。。。如此反复直到队列为空
**/
void LevelOrder(BiTree){
    InitQueue(Q);//初始化队列
    BiTree p;
    EnQueue(Q,T);//根结点入队
    while(!isEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL) EnQueue(Q,p->lchild);
        if(p->rchild!=NULL) EnQueue(Q,p->rchild);
    }
}

/**
三十六、试编写二叉树自下而上的层次遍历
分析：一般层次遍历是自上而下，所以需要逆置---》想到栈
思想：利用原本的层次遍历算法，出队的同时将结点入栈，再出栈
**/
void InvertLevel(BiTree bt){
    if(bt!=NULL){
        InitQueue(Q);
        InitStack(S);
        BiTNode p;
        EnQueue(Q,T);
        while(!isEmpty(Q)){
            DeQueue(p);
            //visit(p);必须等到出栈时再访问
            push(S,p);
            if(p->lchild!=NULL) EnQueue(p->rchild);
            if(p->rchild!=NULL) EnQueue(p->rchild);
        }
        while(!isEmpty(S)){
            Pop(S,p);
            visit(p);
        }
    }
}

/**
三十七、设计算法求链式存储结构的二叉数的高度（递归和非递归）
分析： 递归思想要抽象，左右子树哪个的高度更大？大的那个+1 就是二叉树的高度
       非递归相对更加具体，改造层次遍历：每层的最右结点
**/
int Btdepth(BiTree T){
    if(T!==NULL) {
        return 0;
    }
        ldeep=Btdepth(T->lchild);
        rdeep=Btdepth(T->rchild);
        if(ldeep>rdeep){
            return ldeep+1;
        }
        else{
            return rdeep+1;
        }
}

int Btdepth(BiTree T){
    if(!T) {
        return 0;
    }
    int front=-1,rear=-1;
    int last=0,level=0; //last指向最右结点，level++
    BiTree Q[MaxSize];
   
    Q[++rear]=T;//相当于T入队了(类似循环队列)
    InitQueue(Q);
    BiTree p;
    EnQueue(p);
    while(front<rear){//如果队不为空
        p=Q[++front];//相当于出队
        if(p->lchild) {
            Q[++rear]=p->lchild;    //左子树入队
        }
        if(p->rchild){
            Q[++rear]=p->rchild;    //右子树入队
        }
        if(front=last){//到下一层开始，再次入队，last和front重合
            level++;
            last=rear;//last指向这一层的最右结点（队尾就是最右结点）
        }
    }
    return level;
}

/**
三十八、链式存储结构的二叉树，编写算法将树中所有结点左右子树进行交换
递归抽象化：递归地交换左右子树
**/
void swap(BiTree b){
    if(b){
        swap(b->lchild);
        swap(b->rchild);
        temp=b->lchild;
        b->lchild=b->rchild;
        b->rchild=temp;
    }
}

/**
三十九、二叉树采用链式存储，计算一棵给定二叉树的双分支结点个数
递归抽象化：1.p=NULL 该结点为空
    f(b)=  2.f(lchild)+f(rchild)+1 该结点左右子树的个数+自己本身
           3.f(lchild)+f(rchild) 单左子树时f(rchild)=0; 单右子树时f(lchild)=0
**/

int DoubleNodes(BiTree b){
    if(!b) {
        return 0;
    }
    else if(b->lchild!=NULL&&b->rchild!=NULL){
       return DoubleNodes(b->lchild)+DoubleNodes(b->rchild)+1;
    }
    else {
        return DoubleNodes(p-lchild)+DoubleNodes(p->rchild)
    }
}

int Degree_0(BiTree b){
    if(!b) {
        return 0;
    }
    else if(b->lchild==NULL&&b->rchild==NULL){//若没有左右子树，只有一个结点
        return 1;
    }
    else{
        return Degree_0(b->lchild)+Degree_0(b->rchild);
    }
}

int Degree_1(BiTree b){
    if(b==NULL){
        return 0;
    }
    if((b->lchild==NULL&&p->rchild!=NULL)||(b->lchild!=NULL&&b->rchild==NULL)){
        return Degree_1(b->lchild)+Degree_1(b->rchild)+1;
    }
    else{
        return Degree_1(b->lchild)+Degree_1(b->rchild);
    }
}

/**
四十、计算二叉树所有结点的个数
**/
法一：递归
int count(BiTree b){
    int num1,num2;
    if(b==NULL){
        return 0;
    }
    else {
        num1 = allNodes(b->lchild)
        num2 = allNodes(b->rchild);
        return num1+num2+1;
    }
}
法二：遍历法改造（递归）
int n=0;//全局变量
void count(BiTree T){  
    if(p!=NULL){
        ++n;//visit(p)改为++n;
        count(T->lchild);
        count(T->rchild);
    }
}

/**
四十一、先序遍历，求二叉树第k个结点的值
算法：对二叉树先续遍历递归算法进行改造
**/
int n=0;
void trave(BTNode *p,int k){
    if(p!=NULL){
        n++;
        if(n==k){
            printf("%d",p->data);
            return;
        }
        trave(p->lchild,k);
        trave(p->rchild,k);
    }
}

/**
四十二、计算二叉树中所有叶子结点的个数
**/
法一、递归
int count(BTNode *p){
    int n1,n2;
    if(p==NULL){
        return 0;
    }
    if(p->rchild==NULL&&p->rchild==NULL){
        return 1; 
    }
    n1=count(p->lchild);
    n2=count(p->rchild);
}

法二、对先序遍历进行改造
int n;
void count(BTNode *p){
    if(p!=NULL){
        if(p->lchild==NULL&&p->rchild==NULL){
            n++;
        }
        count(p->lchild);
        count(p->rchild);
    }
}

/**
四十三、
**/

/**
四十四、利用结点的右孩子指针将一个二叉树的叶子结点从左向右链接成一个单链表
(head指向第一个，tail指向最后一个)
思想：1、找到叶子结点
    2、连成单链表。第一个叶子结点（head），其他叶子结点。。
**/
head=NULL;
void link(BTNode *p,BTNode *head,BTNOde *tail){
    if(p!=NULL){
        /**** 改造visit();
        if(!p->lchild && !p->rchild){ //如果左右子树都为空
            if(head==NULL){//第一个叶子结点用head指向它
                head=p;
                tail=p;
            }
            else{
                tail->rchild=p;
                tail=p;;
            }
        }
        ******/
    }
    link(p->lchild,head,tail);
    link(p->rchild,hread,tail);

}

/**
四十五、二叉树采用链式存储结构，求出指定的结点在二叉排序树的层次
二叉排序树：左子树小于它，右子树大于它
思想：用t指针遍历，如果t->data大于指定结点p->data,去t的左边，否则去t的右边找，每判断一次层数+1
**/
    BTNode *t=bt;//遍历指针
    if(bt!=NULL){
        while(t->data!=p->data){
            if(t->data<p->data){
                t=t->rchild;//比p->data下，去右边找
            }
            else{
                t=t->lchild;/比p->data大，去左边找
            }
            n++;//去到下一层了，所以层数+1
        }
    }

/**
四十六、求二叉树的带权路径长度（WPL）是所有叶子结点结的带权路径之和  层数*权值 之和 
结点结构：|left|weight|right|
思想：使用递归，将所有叶子结点的WPL累加即可
补充：深度和高度是区别：一个是从上往下数，一个从下往上数
    1）某结点的深度是指从根结点到该结点的最长简单路径的条数
    2）某结点的高度是指从该结点到叶子结点的最长简单路径的条数
**/

int WPL_preorder(BiTree root,int deep){
    int wpl=0;
    if(p!=NULL){
        if(root->lchild==NULL&&root->rchild==NULL){
            wpl=deep*root->weight;
        }
        if(root->lchild!=NULL){
            WPL_preorder(root->lchild,deep+1;);
        }
        if(root->rchild!=NULL){
            WPL_preorder(root->rchild,deep+1);
        }
    }
    return wpl;
}

int WPL(BiTree root){
    return WPL_preorder(root,0);//根结点deep为0，第二层deep为1（一条边）
}

/**
四十七、根据二叉树输出等价的中缀表达式
思想：1、中缀表达式用中序
    2、什么时候需要加括号？---》
        1）根不加；
        2）叶子结点不加；
        3）其他结点需要加：中序访问左子树之前加左括号，访问右子树之后加右括号
**/
void Inorderfun(BiTree *root,int deep){
    if(root==NULL){
        return;
    }
    else if(root->left==NULL&&root->right==NULL){//如果是叶子结点，输出
        printf("%s",root->data);
    }
    else{
        if(deep>1){
            printf("(");//访问左子树之前加
        } 
        Inorderfun(root->left,deep+1);
        printf("%s",root->data);/打印操作。改造visit()
        Inorderfun(root->right,deep+1);
        if(deep>1){
            printf(")");//访问右子树之前后加
        }
    }
}

/**
四十八、二叉树采用二叉链表结构存储，设计算法求二叉树中值为x的层数
思想：1.遍历 
     2.h何时+1？何时-1？ ----》“三次访问” 经历①②③分别对应先序，中序和后续
                        ---》经历①时h++，经过③时h--
**/

int h=1;
void fun(BTNode *p,int x){
    if(p!=NULL){
        if(p->data==x){
            printf("%d",h);
        }
        h++;    //经历①时h++
        fun(p->lchild,x);
        fun(p->rchild,x);
        h--;    //经过③时h--
    }
    
}

/**
四十九、增加一个指向双亲结点的parent指针，并给指向的指针赋值，并输出所有结点到根结点的路径
分析：1）D->B->A,只要我们通过parent指针，就可以不断往上走
     2）输出单个结点到根结点路径
     3）遍历整棵树，调用函数，输出所有路径
**/
typedef struct BTNode(
    char data;
    struct BTNode* parent,lchild,rchild;
)BTNode;

//1.增加parent指针
void fun(BTNode *p,BTNode *q){
    if(p!=NULL){ 
        p->parent=q;
        q=p;//要往下遍历了呀，p节点已经找到父亲q了，然后让q指向p，让p往下走，然后p的父亲指针再指向q，就又找到父亲了，然后重复（递归）找父亲，直到所有节点都找到父亲
        fun(p->lchild,q);
        fun(p->rchild,q);
    }
   
}

 //2.单个结点到根结点的路径
 void printpath(BTNode *p){
    while(p!=NULL){
        printf("%c",p->data);
        p=p->parent;
    }
 }

//3/遍历整棵树
 void allpath(BTNode *p){
    if(p!=NULL){
        printpath(p);
        allpath(p->lchild);
        allpath(p->rchild);
    }
 }

 /**
 五十、一棵二叉树采用链式存储结构，设计一个算法输出根结点到每个叶子结点的路径
 思想：1）遍历
      2）对特殊的结点进行处理
      3）栈
 **/

 void path(BTNode *p){
    int i=0,top=0;
    ElelType Stack[MaxSize];//这个stack是数组，top是下标，把它当栈用，所有可以遍历
    if(p!=NULL){
        Stack[top]=p->data; //入栈,top从0开始
        ++top;          //栈顶指针上移
    }
    if(p->lchild==NULL&&p->rchild==NULL){ //如果是叶子结点，从下往上读出栈中元素
        for(i=0;i<top;i++){
            printf("%c",Stack[i]);
        }
    }
    path(p->lchild);
    path(p->rchild);
    --top;//回退到双亲，后面再读右子树，Stack[]中右子树就将最顶上的左子树覆盖掉了
 }