抽象数据类型

//
// Created by 民 on 2021/9/26.
//
#include <iostream>

using namespace std;

typedef int Elem;

typedef struct LNode{
   
    Elem data;
    struct LNode* next;
}LNode,*LinkList;
//单链表
void Init_LinkList(LinkList &L){
   
    LNode *node = new LNode;//头结点
    node->data = 0;//存放表长
    node->next=NULL;
    L = node;
}
//获取长度
int Length(LinkList L){
   
    int len = 0;
    LNode *current = L->next;    //获取第一个节点
    while (current){
   
        len++;
        current=current->next;
    }
    return len;
}
//头插法
void head_insert_LinkList(LinkList &L){
   
    for (int i = 0; i < 10; ++i) {
   
        Elem e;
        LNode *node = new LNode ();
        cin>>e;
        node->data = e;
        node->next = L->next;
        L->next=node;
        L->data+=1;
    }
}
//尾插法
void tail_insert_LinkList(LinkList &L){
   
    LNode *tail=L;
    for (int i = 0; i < 10; ++i) {
   
        Elem e;
        LNode *node = new LNode ();
        cin>>e;
        node->data = e;
        node->next = NULL;
        tail->next = node;
        tail = node;
        L->data+=1;
    }
}
//输出链表
void print_LinkList(LinkList L){
   
    LNode *current = L->next;
    while (current){
   
        cout<<current->data<<" ";
        current = current->next;
    }
    cout<<endl;
}
//按序号查找节点
LNode *getElem(LinkList L,int i){
   
    int j=1;
    LNode *current = L->next;
    if (i==0)return L;
    if (i<0)return NULL;
    while (current&&j<i){
   
        current=current->next;
        j++;
    }
    return current;
}
//按值查找节点
LNode *LocateElem(LinkList L,Elem e){
   
    LNode *current = L->next;
    while(current && current->data!=e){
   
        current = current->next;
    }
    return current;
}
//插入指定位置-前插
void Insert_LinkList_head(LinkList &L,int pos,Elem e){
   
    LNode *node = new LNode;
    node->data = e;

    LNode *prior = getElem(L,pos-1);
    if (!prior)return;
    node->next = prior->next;
    prior->next = node;

}
//插入指定位置-前插
void Insert_LinkList_tail(LinkList &L,int pos,Elem e){
   
    LNode *node = new LNode;
    node->data = e;

    LNode *prior = getElem(L,pos);
    if (!prior)return;
    node->next = prior->next;
    prior->next = node;
}
void delete_LinkList(LinkList &L,int pos){
   
    LNode *prior = getElem(L,pos-1);
    if (!prior){
   return;}
// prior->next = prior->next->next;
    LNode *q = prior->next;
    prior->next = q->next;
    delete q;
}

int main(){
   
    LinkList L1,L2,L3;
    Init_LinkList(L1);
    Init_LinkList(L2);
    Init_LinkList(L3);
    head_insert_LinkList(L1);
    int len = Length(L1);
    cout<<"L1的长度："<<len<<endl;
    Insert_LinkList_tail(L1,5,16);
    delete_LinkList(L1,2);
    print_LinkList(L1);


    tail_insert_LinkList(L2);
    len = Length(L2);
    cout<<"L2的长度："<<len<<endl;
    Insert_LinkList_head(L2,5,16);
    delete_LinkList(L2,2);
    print_LinkList(L2);

}

相关练习

第一题、递归删除值为x的节点

void del_x(LinkList &L,Elem e){
   
    LNode *p = NULL;
    if (L == NULL)return;
    if (L->data == e){
   
        p = L;
        L = L->next;
        delete p;
        del_x(L,e);
    } else{
   
        del_x(L->next,e);
    }
}
void test_1(){
   
    LinkList L;
    Init_LinkList(L);
    head_insert_LinkList(L);
    print_LinkList(L);
    del_x(L->next,2);
    print_LinkList(L);
}

第二题：带头结点单链表，删除所有值为x的节点

//法一：非递归
void del_x_1(LinkList &L,Elem e){
   
    LNode *current = L->next,*prior = L,*p=NULL;
    while(current){
   
        if (current->data == e){
   
            p = current;
            prior->next = current->next;
            current = prior->next;
            delete p;
        } else{
   
            prior = current;
            current = prior->next;
        }
    }
}

void test_2(){
   
    LinkList L;
    Init_LinkList(L);
    head_insert_LinkList(L);
    print_LinkList(L);
    del_x_1(L,2);
    print_LinkList(L);
    del_x(L,2);
    print_LinkList(L);
}

第三题：逆序输出链表

void reverse_print(LinkList L){
   
    LinkList L1;
    Init_LinkList(L1);
    LNode *current = L->next;
    while (current){
   
        LNode *p = new LNode ;
        p->data = current->data;
        p->next = L1->next;
        L1->next = p;

        current = current->next;
    }
    LNode *q = L1->next;
    while(q){
   
        cout<<q->data<<" ";
        q=q->next;
    }
    cout<<endl;
}

void test_3(){
   
    LinkList L;
    Init_LinkList(L);
    head_insert_LinkList(L);
    print_LinkList(L);
    reverse_print(L);
}

第四题：删除带头节点单链表min

void del_min(LinkList &L){
   
    LNode *current = L->next,*prior = L,*min = current,*min_pri=prior;
    while (current){
   
        if (current->data < min->data){
   
            min = current;
            min_pri = prior;
        }
        prior = current;
        current = prior->next;
    }
    min_pri->next = min->next;
    delete min;
}

void test_4(){
   
    LinkList L;
    Init_LinkList(L);
    head_insert_LinkList(L);
    print_LinkList(L);
    del_min(L);
    print_LinkList(L);
}

第五题：链表逆置

void reverse(LinkList &L){
   
    LNode *p=L->next,*r=NULL;
    L->next = NULL;
    while(p){
   
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r;
    }
    print_LinkList(L);
}
void test_5(){
   
    LinkList L;
    Init_LinkList(L);
    head_insert_LinkList(L);
    print_LinkList(L);
    reverse(L);
}

第六题、使链表升序

LNode *get_Elem_By_x(LinkList L,Elem e){
   
    LNode *current = L->next;
    LNode *prior = L;
    if (!current)return L;
    while (current!=NULL){
   
        if (current->data>=e){
   
            return prior;
        } else{
   
            prior = current;
            current = prior->next;
        }
    }
    return prior;
}
void sort_asc(LinkList &L){
   
    LNode *p = L->next,*r=NULL;
    L->next = NULL;
    while (p){
   
        r = p->next;
        LNode *node = get_Elem_By_x(L,p->data);
        p->next=node->next;
        node->next=p;
        p = r;
    }
}

//解法二：排序后尾插
void sort(LinkList &L){
   
    int len = Length(L);
    int A[len];
    int i=0;
    LNode *p = L->next;
    while (p){
   
        A[i++]=p->data;
        p=p->next;
    }
    LNode *tail = L;
    sort(A,A+len);
    for (int j = 0; j < len; ++j) {
   
        LNode *node = new LNode ;
        node->data = A[j];
        node->next = NULL;
        tail->next = node;
        tail = node;
    }

}


void test_6(){
   
    LinkList L;
    Init_LinkList(L);
    head_insert_LinkList(L);
    print_LinkList(L);
// sort_asc(L);
// print_LinkList(L);
    sort(L);
    print_LinkList(L);
}

第七题、删除无序链表中介于给定两个值之间的元素

void delete_elem_from_to(LinkList &L , Elem from,Elem to){
   
    LNode *prior = L,*current = L->next;
    while (current){
   
        if (current->data>=from && current->data<=to ){
   
            LNode *tmp = current;
            prior->next = current->next;
            current = current->next;
            delete tmp;
        } else{
   
            prior = current;
            current = current->next;
        }
    }
}

void test_7(){
   
    LinkList L;
    Init_LinkList(L);
    head_insert_LinkList(L);
    print_LinkList(L);
    delete_elem_from_to(L,5,10);
    print_LinkList(L);
}

第八题、找到两个节点的公共节点

LNode * find_common_node(LinkList L1, LinkList L2){
   
    LNode *maxNode,*minNode;
    int max=0,min=0;
    //1、找到min，max长度以及maxNode，minNode
    if (Length(L1)> Length(L2)){
   
        max = Length(L1);
        min = Length(L2);
        maxNode = L1->next;
        minNode = L2->next;
    } else{
   
        max = Length(L2);
        min = Length(L1);
        maxNode = L2->next;
        minNode = L1->next;
    }
    //2、将当前遍历节点移动至长度相同的位置
    while (max > min){
   maxNode = maxNode->next;max--;}
    //3、找共同节点
    while (maxNode){
   
        if (maxNode == minNode){
   return maxNode;}
        else{
   
            maxNode = maxNode->next;
            minNode = minNode->next;
        }
    }
    return NULL;
}

void test_8(){
   
    LinkList L,L2;
    Init_LinkList(L);
    Init_LinkList(L2);
    head_insert_LinkList(L);
    print_LinkList(L);
    head_insert_LinkList(L2);
    L2->next->next->next->next->next->next=L->next->next->next->next;
    print_LinkList(L2);

    LNode * node = find_common_node(L,L2);
    cout<<node->data<<endl;
}

第九题、升序删除节点

void delete_node_asc(LinkList &L){
   
    while (Length(L)>0){
   
        LNode *minPri = L,*min = L->next,*current = min,*current_pri=minPri;
        while (current){
   
            if (current->data < min->data){
   
                minPri = current_pri;
                min = current;
            }
            current = current->next;
        }
        cout<<"删除"<<min->data<<" ";
        minPri->next = min->next;
    }
    cout<<endl;
}
void test_9(){
   
    LinkList L;
    Init_LinkList(L);
    head_insert_LinkList(L);
    print_LinkList(L);
    delete_node_asc(L);
}

第十题：将链表按奇偶查分成两个链表

void divide_LinkList(LinkList &L1,LinkList &L2){
   
    int i = 1;
    LNode *current = L1->next,*L2_tail=L2,*L1_pri = L1;
    while (current){
   
        if (i%2==1){
   
            L1_pri = current;
            current = current->next;
        } else{
   
            L1_pri->next = current->next;
            current->next = NULL;
            L2_tail->next = current;
            L2_tail = current;
            current = L1_pri->next;
        }
        i++;
    }
}
void test_10(){
   
    LinkList L,L2;
    Init_LinkList(L);
    Init_LinkList(L2);
    head_insert_LinkList(L);
    print_LinkList(L);
    divide_LinkList(L,L2);
    print_LinkList(L);
    print_LinkList(L2);
}