数据结构之线性表：单链表（王道2021习题算法实现及测试）_Sunshine_victory的博客

#include <iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

typedef int ElemType;
//单链表定义
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

//函数声明
LNode *List_TailerInsert(LNode *&L);
int ListLength(LNode *L);
void Print_LinkList(LNode *L);

//尾插法，以-1结束输入。
LNode *List_TailerInsert(LNode *&L) {
    L = (LNode*)malloc(sizeof(LNode));
    int x = 0;
    LNode *s, *r = L;
    L->next = NULL;
    scanf("%d", &x);
    while(x!=-1) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

//求表长
int ListLength(LNode *L) {
    int len = 0;
    LNode *p = L->next;
    while(p) {
        len++;
        p = p->next;
    }
    return len;
}
//顺序输出
void Print_LinkList(LNode *L) {
    LNode *p = L->next;
    while(p!=NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

///*******************课后习题********************///
//2、删除所有值为x的结点并释放其空间
LNode *DeleteX(LNode *&L, int x) {
    LNode *p = L;
    while(p->next) {
        LNode *q = p->next;
        if(q->data == x) {
            p->next = q->next;
            free(q);
        }
        p = p->next;
    }
    return L;
}

//3、反向输出单链表中元素
void PrintReserve(LNode *L) {
    if(L->next!=NULL) PrintReserve(L->next);
    printf("%d ", L->data);
}

//4、删除最小值元素
LNode *DeleteMIN(LNode *&L) {
    LNode *pre = L, *MinPre = L->next;
    ElemType Min = 2147483647;
    while(pre->next) {
        LNode *p = pre->next;
        if(p->data<Min) {
            MinPre = pre;
            Min = p->data;
        }
        pre = pre->next;
    }
    LNode *q = MinPre->next;
    MinPre->next = q->next;
    free(q);
    return L;
}

//5、就地逆置单链表
LNode *Reserve(LNode *&L) {
    LNode *p = L->next;
    if(p==NULL) return L;
    LNode *q = p->next;
    if(q==NULL) return L;
    LNode *r = q->next;
    while(true) {
        if(r==NULL) {
            q->next = p;
            L->next->next = NULL;
            L->next = q;
            break;
        }
        q->next = p;
        p = q;
        q = r;
        r = r->next;
    }
    return L;
}
//6、给单链表中元素排序
LNode *Sort(LNode *&L) {
    LNode *p = L->next;
    int i = 0, k = 0;
    ElemType a[1005];
    while(p) {
        a[k++] = p->data;
        p = p->next;
    }
    sort(a, a+k);
    printf("%d\n", a[0]);
    p = L->next;
    while(k--) {
        p->data = a[i++];
        p = p->next;
    }
    return L;
}

//7、删除单链表中在l和r之间的元素
LNode *DeleteLR(LNode *&L, ElemType l, ElemType r) {
    LNode *p = L, *q;
    while(p->next) {
        q = p->next;
        if(q->data>l && q->data<r) {
            p->next = q->next;
            free(q);
        } else p = p->next;
    }
    return L;
}

//8、给定两个单链表，找出它们的公共结点
LNode *Search_list_common(LNode *L1, LNode *L2) {
    int len1 = ListLength(L1), len2 = ListLength(L2);
    LNode *longlist, *shortlist;
    if(len1>len2) {
        longlist = L1;
        shortlist = L2;
    } else {
        longlist = L2;
        shortlist = L1;
    }
    int dist = abs(len1 - len2);
    while(dist--) longlist = longlist->next;
    while(longlist) {
        if(longlist==shortlist)
            return longlist;
        else {
            longlist = longlist->next;
            shortlist = shortlist->next;
        }
    }
    return NULL;
}

//9、设计原地算法，按递增顺序输出单链表中元素并释放其空间
void MinDelete(LNode *&L) {
    while(L->next) {
        LNode *pre = L, *p = L->next, *MinPre = pre, *Min = p;
        while(p) {
            if(p->data<Min->data) {
                Min = p;
                MinPre = pre;
            } else {
                pre = p;
                p = p->next;
            }
        }
        MinPre->next = Min->next;
        printf("%d ", Min->data);
        free(Min);
    }
    printf("\n");
}

//10、将单链表A拆成A，B，分别存放奇数位和偶数位的元素
LNode *disCreat_1(LNode *&A) {
    LNode *B = (LNode*)malloc(sizeof(LNode));
    B->next = NULL;
    LNode *PAPre = A, *PA = A->next, *PB = B;
    int k = 0;
    while(PA) {
        k++;
        if(k%2) {
            PAPre = PA;
            PA = PA->next;
        } else {
            LNode *s = PA;
            //deal with A
            PAPre->next = PA->next;
            PA = PA->next;
            //deal with B
            PB->next = s;
            s->next = NULL;
            PB = s;
        }
    }
    return B;
}

//11、设计就地算法，将单链表A={a1,b1,a2,b2....an,bn}拆成两个单链表A={a1,a2...an},B={bn....b2,b1}
LNode *disCreat_2(LNode *&A) {
    LNode *B = (LNode*)malloc(sizeof(LNode));
    B->next = NULL;
    LNode *PAPre = A, *PA = A->next;
    int k = 0;
    while(PA) {
        k++;
        if(k%2) {
            PAPre = PA;
            PA = PA->next;
        } else {
            LNode *s = PA;
            //deal with A
            PAPre->next = PA->next;
            PA = PA->next;
            //deal with B
            s->next = B->next;
            B->next = s;
        }
    }
    return B;
}

//12、递增有序单链表中有充重复元素存在，将频数大于1的元素删除只留一个。
//(3 4 5 5 6 6 6 7 2 -1)->(3 4 5 6 7 2 -1)
LNode *DeleteSame(LNode *&L) {
    if(ListLength(L)<2) return L;
    LNode *pre = L->next, *p = pre->next;
    while(p) {
        if(pre->data==p->data) {
            LNode *q = p;
            pre->next = q->next;
            p = q->next;
            free(q);
        } else {
            pre = p;
            p = p->next;
        }
    }
    return L;
}

//13、设计原地算法。将两个递增的单链表A,B合并成一个递减的单链表L
LNode *MergeList(LNode *&A, LNode *&B) {
    LNode *L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *PA = A->next, *PB = B->next, *s;//s用于临时保存指针
    while(PA && PB) {
        if(PA->data < PB->data) {
            s = PA;
            A->next = PA->next;
            PA = s->next;
        } else {
            s = PB;
            B->next = PB->next;
            PB = s->next;
        }
        //insert to L
        s->next = L->next;
        L->next = s;
    }
    if(PA) PB = PA;
    while(PB) {
        s = PB;
        B->next = PB->next;
        PB = s->next;
        s->next = L->next;
        L->next = s;
    }
    return L;
}

//14、设计算法产生包含单链表A,B(元素递增)公共元素的单链表C；
LNode *CommonElem(LNode *A, LNode *B) {
    LNode *C = (LNode*)malloc(sizeof(LNode));
    C->next = NULL;  //define headNode
    LNode *PA = A->next, *PB = B->next, *PC = C, *s;
    while(PA && PB) {
        if(PA->data < PB->data) PA = PA->next;
        else if(PA->data > PB->data) PB = PB->next;
        else {
            //to insert common elemment to C
            s = (LNode*)malloc(sizeof(LNode));
            s->data = PA->data;
            s->next = NULL;
            PC->next = s;
            PC = s;
            //move point
            PA = PA->next;
            PB = PB->next;
        }
    }
    return C;
}

//15、链表A,B分别表示两个集合，元素递增排列。求A,B的交集，并存放在A中。
LNode *Union(LNode *&A, LNode *B) {
    LNode *PAPre = A, *PA = A->next, *PB = B->next, *s;
    while(PA && PB) {
        if(PA->data < PB->data) { //directly delete this element
            s = PA;
            PAPre->next = PA->next;
            PA = PA->next;
            free(s);
        }
        else if(PA->data > PB->data) PB = PB->next;
        else { //reserve this element
            PAPre = PA;
            PA = PA->next;
            PB = PB->next;
        }
    }
    while(PA) {
        s = PA;
        PAPre->next = PA->next;
        PA = PA->next;
        free(s);
    }
    PB = B;
    while(PB) {
        s = PB;
        PB = PB->next;
        free(s);
    }
    return A;
}

//16、A={a1,a2....am}, B={b1,b2,....bn},判断B是否是A的连续子序列
bool ChildSeq(LNode *A, LNode *B){
    LNode *PA = A->next, *PBFirst = B->next;
    while(PA){
        if(PA->data == PBFirst->data){
            LNode *PA2 = PA->next, *PB2 = PBFirst->next;//the first node is equal, then comparing next node as new begin
            while(PB2){
                if(PA2==NULL) break;//the remaining node of B is longer
                if(PA2->data != PB2->data) break;
                PA2 = PA2->next;
                PB2 = PB2->next;
            }
            if(PB2 == NULL) return true;
        }
        PA = PA->next;
    }
    return false;
}

//17、设计算法判断带头结点的循环双链表是否对称
//因写该题需要重新定义循环双链表以及表的建立函数，所以没有写。
//18、循环单链表
//19、循环单链表
///*******************课后习题********************///

int main() {
    LNode *L, *L1, *C;
    List_TailerInsert(L);
    List_TailerInsert(L1);
    cout<<ChildSeq(L, L1)<<endl;
    //Print_LinkList(C);
    return 0;
}
#include <iostream>
#include<algorithm>
#includ