【考研数据结构代码题】day11-day20

十一、尾插法 

思想：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->datadata){
            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->datadata){
            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;
}