2021-09-27 循环单链表

//
// Created by 民 on 2021/9/27.
//

#include <iostream>
using namespace std;
typedef int Elem;
typedef struct LNode{
   
    Elem data;
    struct LNode *next;
}LNode,*CLinkList;
//循环单链表
void Init_CLinkList(CLinkList &L){
   
    LNode *node = new LNode;//头结点
    node->data = 0;//存放表长
    node->next=node;
    L = node;
}
//获取长度
int Length(CLinkList L){
   
    cout<<"单循环链表获取长度：";
    int len = 0;
    LNode *current = L->next;    //获取第一个节点
    while (current!=L){
   
        len++;
        current=current->next;
    }
    cout<<len<<endl;
    return len;
}
//头插法
void head_insert_CLinkList(CLinkList &L){
   
    cout<<"头插法：插入十个数："<<endl;
    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_CLinkList(CLinkList &L){
   
    cout<<"尾插法：插入十个数："<<endl;
    LNode *tail=L;
    for (int i = 0; i < 10; ++i) {
   
        Elem e;
        LNode *node = new LNode ();
        cin>>e;
        node->data = e;
        node->next = L;
        tail->next = node;
        tail = node;
        L->data+=1;
    }
}
//输出链表
void print_CLinkList(CLinkList L){
   
    cout<<"输出循环单链表"<<endl;
    LNode *current = L->next;
    while (current!=L){
   
        cout<<current->data<<" ";
        current = current->next;
    }
    cout<<endl;
}
//按序号查找节点
LNode *getElem(CLinkList L,int i){
   
    cout<<"按序号查找节点，查询序号为"<<i<<"的节点:";
    int j=1;
    LNode *current = L->next;
    if (i==0)return L;
    if (i<0)return NULL;
    while (current!=L&&j<i){
   
        current=current->next;
        j++;
    }
    if (current!=L){
   
        cout<<current->data<<endl;
    } else{
   
        cout<<"无此节点"<<endl;
    }
    return current;
}
//按值查找节点
LNode *LocateElem(CLinkList L,Elem e){
   
    cout<<"按值查找节点，查询值为"<<e<<"的节点：";
    LNode *current = L->next;
    while(current!=L && current->data!=e){
   
        current = current->next;
    }
    if (current!=L){
   cout<<current->data<<endl;}
    else{
   cout<<"无此节点"<<endl;}
    return current;
}
//插入指定位置-前插
void Insert_CLinkList_head(CLinkList &L,int pos,Elem e){
   
    cout<<"在第"<<pos<<"个位置上前插："<<e<<endl;
    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_CLinkList_tail(CLinkList &L,int pos,Elem e){
   
    cout<<"在第"<<pos<<"个位置上尾插："<<e<<endl;
    LNode *node = new LNode;
    node->data = e;

    LNode *prior = getElem(L,pos);
    if (!prior)return;
    node->next = prior->next;
    prior->next = node;
}
void delete_CLinkList(CLinkList &L,int pos){
   
    cout<<"删除第"<<pos<<"个位置的节点"<<endl;
    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() {
   
    CLinkList L1,L2;
    Init_CLinkList(L1);
    Init_CLinkList(L2);

    head_insert_CLinkList(L1);
    print_CLinkList(L1);
    tail_insert_CLinkList(L2);
    print_CLinkList(L2);
    getElem(L2,10);
    getElem(L2,13);
    LocateElem(L2,7);
    LocateElem(L2,15);
    cout<<"-------------"<<endl;
    print_CLinkList(L1);
    Insert_CLinkList_head(L1,5,16);
    print_CLinkList(L1);
    cout<<"-------------"<<endl;
    print_CLinkList(L2);
    Insert_CLinkList_tail(L2,5,16);
    print_CLinkList(L2);
    cout<<endl;
    delete_CLinkList(L2,2);
    print_CLinkList(L2);
    return 0;
}