C++链表

//
//  linklist.cpp
//  链表
//
//  Created by edisoncgh on 2020/4/4.
//  Copyright © 2020 edisoncgh. All rights reserved.
//

#include <cstdio>
#include <iostream>
#include <cstdlib>

using namespace std;

//构建节点类
class Node
{
public:
    int data;//数据域
    Node* next;//指针域
};

class List//构建链表类
{
public:
    List();//构建函数
    ~List();//析构函数
    void createList(int n);//创建一个n结点的链表
    void travelList();//遍历链表
    int getLength();//获取链表长度
    bool isEmpty();//链表判空
    Node* findNode(int data);//查找指定数据域的结点
    int searchNode(int n);//查找第n个结点的值;
    void endInsert(int data);//尾插
    void headInsert(int data);//头插
    void listInsert(int data, int n);//插入第n个结点
    void nodeDelete(int data);//删除指定数据域的结点
    void findDelete(int n);//删除第n个结点
private:
    Node* head;//头结点
};

//初始化链表类
List::List()
{
    head = (Node*)malloc(sizeof(Node));
    head->data = -1;
    head->next = NULL;
}

//销毁链表类
List::~List()
{
    delete head;
}

//创建一个长n个结点的链表
void List::createList(int n)
{
    Node *temp = nullptr, *newp = nullptr;
    temp = head;
    if(n < 0)
    {
        printf("输入有误\n");
        return ;
    }
    for (int i = 0; i < n; i++)
    {
        newp = (Node*)malloc(sizeof(Node));
        printf("输入第%d个值\n", i+1);
        cin >> newp->data;
        newp->next = NULL;
        temp->next = newp;
        temp = newp;
    }
}

//遍历链表
void List::travelList()
{
    if(head == NULL || head->next == NULL)
    {
        printf("链表为空\n");
        return ;
    }
    Node *t;
    t = head->next;
    while(t != NULL)
    {
        cout << t->data << " ";
        t = t->next;
    }
    cout << endl;
}

//返回链表长度
int List::getLength()
{
    int length = 0;
    Node *t;
    t = head;
    while(t->next != NULL)
    {
        length++;
        t = t->next;
    }
    return length;
}

//链表判空
bool List::isEmpty()
{
    return head->next == NULL;
}

//查找数据域为data的结点
Node* List::findNode(int data)
{
    Node *p = head;
    if(p == NULL || p->next == NULL)
    {
        printf("链表为空\n");
        return NULL;
    }
    else
    {
        while(p->next != NULL)
        {
            if(p->data == data) return p;
            p = p->next;
        }
        return NULL;//表里没有这个结点
    }
}

//查找第n个结点的值
int List::searchNode(int n)
{
    Node *p = head;
    int i = 1;
    while(n >= i)
    {
        p = p->next;
        i++;
    }
    return p->data;
}

//尾插
void List::endInsert(int data)
{
    Node *newp;
    newp = (Node*)malloc(sizeof(Node));
    newp->next = NULL;
    newp->data = data;
    Node *p = head;
    if(head == NULL) head = newp;//若链表为空则此结点为头结点
    else//找到之前的尾结点，将新结点设置为新尾结点
    {
        while(p->next != NULL)
            p = p->next;
        p->next = newp;
    }
}

//头插
void List::headInsert(int data)
{
    Node *newp;
    newp = (Node*)malloc(sizeof(Node));
    newp->data = data;
    Node *p = head;
    if(head == NULL) head = newp;//若链表为空则此结点为头结点
    else
    {
        newp->next = p->next;
        p->next = newp;
    }
}

//指定位置插入
void List::listInsert(int data, int n)
{
    if(n < 1 || n > getLength())
    {
        printf("输入有误\n");
        return ;
    }
    else
    {
        Node *temp;
        temp = (Node*)malloc(sizeof(Node));
        temp->data = data;
        Node *p = head;
        int i = 1;
        while(n > i)//从第1个结点遍历到指定结点
        {
            p = p->next;
            i++;
        }
        temp->next = p->next;
        p->next = temp;
    }
}

//删除指定数据
void List::nodeDelete(int data)
{
    Node *temp = findNode(data);//找到指定数据位置;
    Node *p = head->next;
    while(p->next != temp)//遍历到指定结点
        p = p->next;
    p->next = temp->next;//挤掉
    delete temp;//删掉
    temp = NULL;
}

//删除第n个结点
void List::findDelete(int n)
{
    Node *p = head;
    Node *pre = (Node*)malloc(sizeof(Node));
    int i = 1;
    while(n >= i)
    {
        i++;
        pre = p;
        p = p->next;
    }
    pre->next = p->next;
    delete p;
    p = NULL;
}

int main()
{
    List l1;
    int n;
    printf("输入链表长度：\n");
    cin >> n;
    l1.createList(n);
    if(l1.isEmpty() == 1) printf("此表为空\n");
    else printf("链表长为%d\n", l1.getLength());

    int i;
    printf("输入查找第几位结点的值\n");
    cin >> i;
    printf("第%d位结点的值为%d\n", i, l1.searchNode(i));

    int data, datap;
    printf("输入要要插入的数据与它的位置：\n");
    cin >> data >> datap;
    l1.listInsert(data, datap);
    printf("插入后链表为：\n");
    l1.travelList();

    int headdata;
    printf("输入要在头部插入的值：\n");
    cin >> headdata;
    l1.headInsert(headdata);
    printf("插入后链表为：\n");
    l1.travelList();

    int taildata;
    printf("输入要在尾部插入的值：\n");
    cin >> taildata;
    l1.endInsert(taildata);
    printf("插入后链表为：\n");
    l1.travelList();

    int deldata;
    printf("输入要删除的值：\n");
    cin >> deldata;
    l1.nodeDelete(deldata);
    printf("删除后链表为：\n");
    l1.travelList();

    int nodel;
    printf("输入要删除的结点：\n");
    cin >> nodel;
    l1.findDelete(nodel);
    printf("删除后链表为：\n");
    l1.travelList();

    return 0;
}