基于C++实现链表的(头插法/尾插法)创建链表/插入数据/删除数据

基于C++实现链表的(头插法/尾插法)创建链表/插入数据/删除数据

#include<malloc.h>
#include<iostream>
using namespace std;

class Data{
    public:
    Data *CreatList_h(); //头插法建立链表
    Data *CreatList_t(int n); //尾插法建立链表
    Data *InsertList(Data *L,int n); //向链表指定位置n插入元素
    Data *DeleteList(Data *L,int n); //删除链表中的指定值n
    void FindList(Data *L,int m); //查找链表中指定元素的位置
    void OutputList(Data *L); //输出链表的所有值
    //private: //不能为private :否则系统编译不通过,且报错,目前不清楚原因,欢迎留言;
    int n; //链表长度
    int data;
    Data *next;
};

int main(){
    Data L;
    int i=0;
    while(i != 7){
    cout << “***菜单****“ << endl;
    cout << “1.头插法建立链表\n2.尾插法建立链表\n3.向链表指定位置插入元素\n4.删除链表中的指定值\n5.查找链表中指定元素的位置\n6.输出链表的所有值\n7.退出\n请选择:” ;
    cin >> i;
    switch(i){
        case 1 :L = L->CreatList_h();break;
        case 2 : {
            int n=0;
            cout << “请输入链表数据个数:” << endl;
            cin >> n;
            L = L->CreatList_t(n);
        }; break; //尾插法建立链表
        case 3 : {
            int m = 0;
            cout<<”请输入要插入的位置:”;
            cin >> m;
            L = L->InsertList(L,m);
        }; break; //向链表指定位置插入元素
        case 4 :{
            int j = 0;
            cout<<”请输入想删除的数:”;
            cin>>j;
            L = L->DeleteList(L,j);
            }; break; //删除链表中的指定值
        case 5 :{
            int n = 0;
            cout << “请输入要查找位置的元素: “;
            cin >> n;
            L->FindList(L,n);
            };break; //查找链表中指定元素的位置
        case 6 : L->OutputList(L); break; //输出链表的所有值
        case 7 : cout << “退出” << endl ; break;
        }
        cout << endl;
    }
return 0;
}

Data *Data::CreatList_h(){ //头插法建立链表
    Data *L = new class Data[sizeof(class Data)];
    cout << “请输入链表数据个数:” << endl;
    cin >> L->n;
    L->next = NULL;
    for(int i = L->n ; i > 1; –i){
        Data *p = new class Data [sizeof(class Data)];
        cout << “请输入序号为”<< i <<”的数据:” ;
        cin >> p->data ;
        p->next = L->next; //L->next = NULL,确保尾节点为空值
        L->next = p; //链接，使上一个地址指向下一个元素位置
    }
    cout << “请输入序号为1的数据:” ;
    cin >> L->data ; //使 L->data有值,否则会出现为0且多一个数的情况;
    return L;
}

Data *Data::CreatList_t(int n){ //尾插法建立链表
    Data *q;
    Data *L = new class Data[sizeof(class Data)];
    q = L;
    L->next = NULL;
    cout << “请输入序号为1的数据:”; // 不进行该步骤会导致首元素为0
    cin >> L->data ; //使 L->data有值,否则会出现为0且多一个数的情况;
    for(int i = 2; i <= n ; i++){
        Data *p = new class Data [sizeof(class Data)];
        cout << “请输入序号为”<< i <<”的数据:” ;
        cin >> p->data ;
        q->next = p;
        q = p;
        p->ext = NULL;
    }
    return L;
}

Data *Data::InsertList(Data *L,int n){ //向链表指定位置n插入元素
    int j = 1,m;
    Data *p = L;
    cout << “请输入插入元素的值:” ;
    cin >> m;
    while( p && j < n-1){
        p = p->next;
        ++j;
    }
    if(!p || j > n-1) //i小于1或者大于表长+1
        return 0;
    Data *q = new class Data [sizeof(class Data)];
    q->data = m;
    q->next = p->next;
    p->next = q;
    return L; //一定要加这个,否则会吧n之前的数据全部扔掉,而不会返回;
}

Data *Data::DeleteList(Data *L,int n){ //删除链表中的指定值n
    int i=0;
    Data *p=L;
    Data *q;
    while(n != p->data){
        q = p;
        p = p->next;
    }
    q->next = p->next;
    cout << “已删除:” << n << endl;
    free(p);
    return L;
}

void Data::OutputList(Data L){
    int i=1;
    cout << “\n***“ << endl;
    while(L != NULL){
        cout << “序号:” << i << “数据:” << L->data << endl;
        L = L->next;
        i++;
    }
}

void Data::FindList(Data *L,int m){
    int i = 1;
    while(L != NULL){
        if( L->data == m)
            cout << “元素 “ << m << “的位置是 “ << i << endl;
        L = L->next;
    i++;
    }
}