数据结构代码题--头插法和尾插法的应用

头插法建立单链表（一般用于链表的逆置）头插防断链 就是说用头插法时要给 p指针一个后继结点

// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
 
/*头插法建立单链表*/ 
LinkList Insert_Head(LinkList &L){
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));    // 创建头结点 
    L->next = NULL;                         // 初始为空链表
    scanf("%d",&x);
    while(x!=-1){
        s = (LNode *)malloc(sizeof(LNode));     // 创建新结点
        s->data = x;
        s->next = L->next;          // 将新结点插入表头 
        L->next = s; 
        scanf("%d",&x);
    } 
        return L; 
} 

、2、尾插法建立单链表 尾插留尾指针 用尾插法时要有一个尾指针 r

// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
 
/*尾插法建立单链表*/ 
LinkList Insert_Head(LinkList &L){
    LNode *s;
    LNode *r;   // 表尾指针 
    int x;
    L = (LinkList)malloc(sizeof(LNode));    // 创建头结点 
    r = L; 
    scanf("%d",&x);
    while(x!=-1){
        s = (LNode *)malloc(sizeof(LNode));     // 创建新结点
        s->data = x;
        r->next = s;
        r = s;                  // r 指向新的表尾结点 
        scanf("%d",&x);
    } 
    
    r->next = NULL;         // 尾结点指针指向空 
    return L; 
} 
​

1、单链表逆置

1、带头结点的单链表就地逆置 头插法

// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
/*算法思想：用头插法*/ 
LinkList Reverse(LinkList L){
    LNode *p = L->next;
    LNode *r;       // P 的后继结点
    while(P->NULL){
        r = p->next;    // 保留p的后继，防止断链 
        p->next = L->next;      // 头插法 
        L->next = p;
        p = r;
    } 
    return L; 
}

2、L={a1,a2,a3,……an}------>L={a1,an,a2,an-1,a3,an-2……}

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
​
/*算法思想：
找中间结点：两个指针同步从开头遍历，一个慢指针一次走一步，一个快指针一次走两步，当快指针到达表尾时，慢指针就刚好指向中间结点 
后半段逆置：头插法 
合并 ：尾插法 
​
*/
​
void change_list(LinkList &L){
    LNode *p,*q,*r,*s;
    // 1、寻找中间结点 
    while(q->next!=NULL){
        p = p->next;    // p走一步 
        q = q->next;    // q走两步 
        if(q->nextQ=NULL){
            q = q->next;
        } 
    }
    // 2、逆置（头插法） 
    q = p->next;  //  后半段链表，p为中间结点，q为后半段链表的首结点 
    while(q!=NULL){
        r = q->next;  // 头插法，防止断链
        q->next = p->next;
        p->next = q;
        q = r; 
    }  
    // 3、从新合并
    s = L->next;        // s指向前半段第一个结点，即插入点
    q = p->next;        // q 指向后半段第一个结点 
    p->next = NULL;
    while(q!=NULL){
        r = q->next;
        q->next = s->next;
        s->next = q;
        s = q->next;        // s指向前半段下一个插入点
        q = r; 
    } 
} 

2、链表归并与分解

1、将一个带头结点的单链表A分解为两个带头结点的单链表A和B,使得A表中保存序号是奇数的元素，B中保存序号是偶数的元素

// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
/*算法思想：不断的使用尾插法，序号奇数插入A,偶数插入B*/
LinkList Creat(LinkList &A){
    LNode *p = A->next;
    LinkList B = (LinkList)malloc(sizeof(LNode));   // 创建B链表 
    B->next = NULL;     // B链表初始化 
    A->next = NULL;     // 置空新的A链表 
    LNode *ra=A,*rb = B;        // 两个尾指针 
    int i = 0;      // 记录序号是奇数还是偶数 
    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;
} 

2、A={a1,b2,a2,b2……an,bn}，采用带头结点的单链表存放，将其拆分为两个单链表A={a1,a2,……an},B={bn,bn-1,……b2,b1}

// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
/*算法思想：遍历A链表，将奇数位尾插入A中，偶数位头插入B中*/
LinkList Creat(LinkList &A){
    int i = 0;
    LNode *p = A->next,*q;
    LNode *ra = A;
    LinkList B = (LinkList)malloc(sizeof(LNode));
    B->next = NULL;
    A->next = NULL;
    while(p!=NULL){
        i++;
        if(i%2 == 0){   // 奇数位,头插入B 
            q = p->next; // 头插法遍历原来的A链表时，保留p的后继结点，防止断链
            p->next = B->next;
            B->next = p;
            p = q; 
        }else{      // 奇数位，尾插入A中 
            ra->next = p;   // 尾插法 
            ra = p;
            p = p->next;
        }
    } 
    ra->next = NULL;
    return B;
} 

3、将两个按元素值递增排序的单链表合并位一个按元素值递减排序的单链表

// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
/*算法思想：依次比较A和B中的值，将小的头插入到C中,如果其中一条链表有元素剩余，则依次进行头插入C中*/ 
void MergeList(LinkList &A,LinkList &B){
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *t;       // 防止断链 
    A->next = NULL  // A置空 
    while(p!=NULL&&q!=NULL){
        if(p->data<=q->data){   // 将较小的头插入A中
            t = p->next;        //头插法遍历原来的链表时，保留p的后继结点，防止断链
            p->next = A->next;
            A->next = p;
            p = q;
        }else{              //  将较小的B头插入A中
            t = q->next;
            q->next = A->next;
            A->next = q;
            q = t; 
        }
    }
    
    while(p!=NULL){     // A中还有元素剩余，依次头插入A中 
        t = p->next;        //头插法遍历原来的链表时，保留p的后继结点，防止断链
        p->next = A->next;
        A->next = p;
        p = q;
    }
    
    while(q!=NULL){     // B中还有元素剩余，依次头插入A中 
        t = q->next;
        q->next = A->next;
        A->next = q;
        q = t;
    } 
    free(B);
}

4、A，B为元素递增有序的单链表，找到A和B中的公共元素，存放到C中

// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
/*算法思想：遍历A和B链表，比较元素值，将元素值小的指针后移，将相等的元素值尾插法插入到C中*/
void Creat_Conmmon(LinkList A,LinkList B){
    LinkList C = (LinkList)malloc(sizeof(LNode));   // 创建C链表 
    C->next = NULL;         // 初始化C链表 
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r = C;
    LNode *s; 
    while(p!=NULL&&q!=NULL){
        if(p->data > q->data){      //更小的指针后移， q向后移 
            q = q->next; 
        }else if(p->data < q->data){    // p向后移
            p = p->next; 
        }else{  // 相同结点尾插法插入C中
            s = (LNode *)malloc(sizeof(LNode)); 
            s->data = p->data;
            r->next = s;
            r = s;
            // p,q同时后移
            p = p->next;
            q = q->next; 
        } 
    } 
    
    r->next = NULL; 
} 

5、A,B两个单链表递增有序，求A，B的交集并存放于A中

​
// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
​
​
/*算法思想：依次扫描A，B两条链表，比较data域的值，将较小的指针向后移动（并释放空间），若
两者相等，则尾插入A中，直到遍历表尾，（若A链表还有元素剩余，则逐个释放剩余元素，只保留公共元素）*/
​
void Union(LinkList &A,LinkList &B){
    
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *u;
    A->next = NULL;         // A链表置空，重新插入元素 
    LNode *r = A;
    
    while(p!=NULL && q->next!=NULL){
        if(p->data < q->data){      // 元素小的指针后移，并释放空间 
            u = p;
            p = p->next;
            free(u);
        }
        else if(p->data > q->data){
            u = q;
            q = q->next;
            free(u);
        }
        else{               // 找到公共元素，保留一个，释放一个 
            r->next = p;
            r = p;          // 保留p释放q;
            p = p->next;
            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;
    free(B);
} 

4、寻找相同子序列

1、两个整数子序列A = a1,a2……an B= b1,b2,……bn,存放到两个单链表中，判断序列B是否为A的连续子序列

// 单链表的定义 
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList; 
​
/*算法思想：暴力法：类似字符串的模式匹配，依次遍历A和B链表，如果data值相同，同时后移，如果不相同
A返回开始比较结点的后继结点，B则从头开始 
​
*/
bool Pattern(LinkList A,LinkList B){
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *pre = p;
    
    while(p!=NULL&&q!=NULL){
        if(p->data == q->data){     // 结点值相同，两个结点同时向后移
            p = p->next;
            q = q->next; 
        }else{
            pre = pre->next;    // 
            p = pre;            // A返回开始比较结点的后继结点
            q = B->next;        // B则从头开始  
        } 
    }
    
    if(q == NULL){      // B中没有元素了,说明B是A的自序列 
        return true;
    }else{
        return false;
    }
     
} 
​