全网最全线性表代码大全（顺序表，链表），王道大题大全

#include 
#include 
#include 
#include 
#define MaxSize 50
typedef int ElemType ;
//定义顺序表
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;
//定义单链表
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
//定义双链表
typedef struct DNode{
    ElemType data;
    struct DNode *next,*prior;
}DNode,*DLinkList;
//初始化顺序表
void InitList(SqList &L){
    for(int i=0;inext;
    while(p!=NULL){
        printf("%d	",p->data);
        p=p->next;
    }
    printf("
");
}
//打印双链表
void printDList(DLinkList L){
    DNode *p=L->next;
    while(p!=L){
        printf("%d	",p->data);
        p=p->next;
    }
    printf("
");
}
//计算长度
int length(LinkList L){
    LNode *p=L->next;
    int len=0;
    while(p!=NULL){
        len++;
        p=p->next;
    }
    return len;
}
//头插法建立双链表
DLinkList create_DL(DLinkList &L){
    DNode *s;
    int x;
    L=(DNode *)malloc(sizeof(DNode));
    L->next=L->prior=NULL;
    scanf("%d",&x);
    while(x!=9999){
       s=(DNode *)malloc(sizeof(DNode));
       s->data=x;
       s->next=s->prior=NULL;
       s->next=L->next;
       L->next->prior=s;
       s->prior=L;
       L->next=s;
       scanf("%d",&x);
    }
    return L;
}
//P17 1
int deleteElement(SqList &L){
    int i,temp=0,min=L.data[0];
    if(L.length>0){
        for(i=0;i=t || L.length==0){
        printf("Error!");
    }
    //找到第一个要删除的元素
    for(i=0;i=L.length)
        printf("Error!");
    //找到最后一个删除元素的下一个元素
    for(j=i;j=s && L.data[i]<=t){
            k++;
        }else{
            for(j=0;jL.length)
        return false;
    //只要中间有一个顺序表结束就终止循环
    while(iright || right>arraySize)
        return;
    for(int i=0;ix){
            high=mid-1;
        }else{
            low=mid+1;
        }
    }
    //直接mid查到
    if(L.data[mid]==x && mid<=L.length-1){
        int temp=L.data[mid];
        L.data[mid]=L.data[mid+1];
        L.data[mid+1]=temp;
    }
    //查不到
    if(low>high){
        for(int j=L.length;j>=low;j--){
            L.data[j]=L.data[j-1];
        }
        L.data[low]=x;
    }
}
//将6-100之间的偶数表示为两个素数之和(哥德巴赫猜想)
void mergeNum(){
    int i,j,k,a,b,count=0;
    int num[100];
    //表示所有偶数
    for(i=8;i<=100;i+=2){
        //计算每个偶数的素数
        for(j=2;jL.length/2){
            return L.data[i];
        }else{
            count=0;
        }
    }
    //没有主元素
    return -1;
}
//p18 13
int find_n(int A[],int n){
    //定义相关变量
    int i,*B;
    B=(int *)malloc(sizeof(int)*n);
    //将A中相关变量放在B中
    for(i=0;i0 && A[i]<=n){
            B[A[i]-1]=A[i];
        }
    }
    for(i=0;inext=NULL;
    //输入要插入的元素
    scanf("%d",&x);
    while(x!=9999){
        //为插入节点申请地址
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}
//王道P37 1
void Del_x_3(LinkList &L,ElemType x){
    LNode *p;
    //L为空直接返回
    if(L==NULL){
        return;
    }
    //找到数值
    if(L->data==x){
        p=L;
        L=L->next;
        free(p);
        Del_x_3(L,x);
    }else{
        Del_x_3(L->next,x);
    }
}
//王道 P38 2
void Del_x_4(LinkList &L,ElemType x){
    LNode *p=L->next,*pre=L,*q;
    //遍历链表
    while(p!=NULL){
        //找到数值相同节点，删除
        if(p->data==x){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
}
//王道 P38 3
void R_Print(LinkList &L){
    //先找到最后的元素
    if(L->next!=NULL){
        R_Print(L->next);
    }
    //反向输出
    if(L!=NULL){
        printf("%d	",L->data);
    }
}
void R_Ignorance_Head(LinkList &L){
    if(L!=NULL){
        R_Print(L->next);
    }
}
//王道P38 3
LinkList Del_min_x(LinkList &L){
    //定义四个变量分别指向不同的位置
    LNode *pre=L,*p=pre->next;
    LNode *minpre=pre,*minp=p;
    //遍历链表
    while(p!=NULL){
        if(p->datadata){
            minp=p;
            minpre=pre;
        }
        //后面继续遍历
        pre=p;
        p=p->next;
    }
    //删除最小元素
    minpre->next=minp->next;
    free(minp);
    return L;
}
//王道 P38 5(反转链表)
LinkList Reverse_L(LinkList &L){
    //定义指针
    LNode *p,*r;
    //断链并存储地址
    p=L->next;
    L->next=NULL;
    while(p!=NULL){
        //保存下一个地址
        r=p->next;
        //头插
        p->next=L->next;
        L->next=p;
        //将p重新指向r
        p=r;
    }
}
//王道 p38 6
LinkList Sort(LinkList &L){
    LNode *p,*r,*pre;
    //断链
    p=L->next;
    r=p->next;
    p->next=NULL;
    p=r;
    //遍历
    while(p!=NULL){
        //保存节点
        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->datadata){
            pre=pre->next;
        }
        //找到位置插入位置
        p->next=pre->next;
        pre->next=p;
        p=r;
    }
    return L;
}
//王道 p38 7(删除介于两个数值之间的所有元素)
LinkList Del_x_5(LinkList &L,int min,int max){
    //定义变量
    LNode *pre=L,*p=pre->next,*q;
    //开始循环
    while(p!=NULL){
        //判断是否介于两者之间
        if(p->data>min && p->datanext=p->next;
            p=p->next;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
    return L;
}
//王道 p38 8(查找两个链表的公共节点，暴力算法)
LinkList Find_x(LinkList &L,LinkList L1,LinkList L2){
    LNode *p=L1->next,*q=L2->next,*r;
    L=(LNode *)malloc(sizeof(LNode));
    r=L;
    L->next=NULL;
    while(p!=NULL && q!=NULL){
        if(p->data==q->data){
            L->next=p;
            r=p;
            r->next=NULL;
        }
        p=p->next;
        q=q->next;
    }
    return L;
}
//第二种方法（先算出长度，然后将长的链表先遍历，然后再同时遍历）
LinkList Find_x_1(LinkList &L1,LinkList &L2){
    //设置指针,计算长度
    LNode *longList,*shortList;
    int len1=length(L1),len2=length(L2),dist;
    //比较长度
    if(len1>len2){
        //指针确定指向
        longList=L1->next;
        shortList=L2->next;
        dist=len1-len2;
    }else{
        longList=L2->next;
        shortList=L1->next;
        dist=len2-len1;
    }
    //先将多余的遍历完成
    while(dist--)
        longList=longList->next;
    //同时遍历
    while(longList!=NULL){
        if(longList==shortList){
            return longList;
        }
        longList=longList->next;
        shortList=shortList->next;
    }
    return NULL;
}
//P38 9将元素按递增排序后删除
void Del_x_6(LinkList &L) {
    //只剩下头节点
    while (L->next != NULL) {
        //设置相关指针
        LNode *pre = L, *p = pre->next, *q;
        //遍历找到最小的元素
        while (p->next != NULL) {
            //判断
            if (p->next->data < pre->next->data) {
                pre = p;
            }
            p = p->next;
        }
        //展现节点，删除节点
        printf("%d", pre->next->data);
        q = pre->next;
        pre->next = q->next;
        free(q);
    }
    //释放头节点
    free(L);
}
LinkList resolve(LinkList &A){
    //设置相关节点
    int count=0;
    LinkList B=(LNode*)malloc(sizeof(LNode));
    B->next=NULL;
    LNode *p=A->next,*ra=A,*rb=B;
    //断链
    A->next=NULL;
    //遍历循环
    while(p!=NULL){
        count++;
        //奇偶性判断
        if(count%2==0){
            rb->next=p;
            rb=p;
        }else{
            ra->next=p;
            ra=p;
        }
        //p指向下一个元素
        p=p->next;
    }
    ra->next=NULL;
    ra->next=NULL;
    return B;
}
//王道 P38 11
void resolve_1(LinkList &C,LinkList &A,LinkList &B){
    //声明链表
    A->next=NULL;
    B->next=NULL;
    //声明辅助变量
    LNode *p=C->next;
    //声明A链表的链尾变量
    LNode *ra=A;
    //声明B的保存变量
    LNode *q;
    //断链
    C->next=NULL;
    //开始遍历
    while(p!=NULL){
        ra->next=p;
        ra=p;
        p=p->next;
        //保存地址
        if(p!=NULL){
            q=p->next;
        }
        //头插
        p->next=B->next;
        B->next=p;
        p=q;
    }
}
//王道 p38 13(删除有序链表中的重复元素)
LinkList Del_x_7(LinkList &L){
    //定义相关辅助变量
    LNode *pre=L,*p=pre->next,*q;
    //开始遍历
    while(p!=NULL){
        //判断
        if(pre->next->data==p->next->data){
            q=pre->next;
            pre->next=q->next;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
    return L;
}
//P38 13(将两个单调递增的序列合并成一个单调递减的序列）
LinkList merge_L(LinkList &A,LinkList &B){
    //声明相关变量
    LNode *la=A->next,*lb=B->next,*r;
    //初始化A链表，断链
    A->next=NULL;
    //开始遍历(两个链表都不可以为空)
    while(la && lb){
        //比较
        if(la->datadata){
            //保存地址
            r=la->next;
            //头插法
            la->next=A->next;
            A->next=la;
            la=r;
        }else{
            r=lb->next;
            lb->next=B->next;
            B->next=lb;
            lb=r;
        }
    }
    //处理剩下的链表段
    //无论谁剩下都将lb指向对应的地址
    if(la){
        lb=la;
    }
    //处理lb指向的地址
    while(lb){
        r=lb->next;
        lb->next=A->next;
        A->next=lb;
        lb=r;
    }
    free(lb);
    return A;
}
//王道 P38 14(从两个链表中找出公共元素，形成新的链表)
LinkList create_c(LinkList &A,LinkList &B){
    //创建一个c链表
    LinkList C=(LNode*)malloc(sizeof(LNode));
    C->next=NULL;
    //尾插法设置尾端变量，还有两个辅助变量
    LNode *r=C,*la=A->next,*lb=B->next;
    //遍历两个链表
    while(la && lb){
        //判断两个链表的元素大小
        if(la->datadata){
            la=la->next;
        }else if(la->data>lb->data){
            lb=lb->next;
        }else{
            LNode *s=(LNode *)malloc(sizeof(LNode));
            s->data=la->data;
            r->next=s;
            r=s;
            la=la->next;
            lb=lb->next;
        }
    }
    r->next=NULL;
    return C;
}
//王道 P38 16(判断B是不是A的子序列)
bool rank_L(LinkList A,LinkList B){
    //两个辅助指针
    LNode *pa=A->next,*pb=B->next;
    //记录A地址指针
    LNode *pre=A->next;
    //循环
    while(pa && pb){
        //判断
        if(pa->data==pb->data){
            pa=pa->next;
            pb=pb->next;
        }else{
            pa=pre->next;
            pb=B->next;
            pre=pre->next;
        }
    }
    //如果pb为空则是子序列
    if(pb==NULL){
        return true;
    }else{
        return false;
    }
}

int main() {
    DLinkList L;
    create_DL(L);
    printDList(L);
}