C/C++教程

C++单链表的实现（未用模板类）

本文主要是介绍C++单链表的实现（未用模板类），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

  • 整体代码
  • 分区块实现
    • 单链表的创建
    • 遍历单链表
    • 在单链表中插入数据（分为头插，尾插和任意插）
    • 删除单链表的数据（分为头删，尾删和任意删）
    • 查找单链表的数据（按照给定值查找）
    • 修改单链表的数据（按照位置修改）
    • 销毁单链表

整体代码

#include <iostream>
using namespace std;
class Node
{
public:
    int data;   //数据域
    Node* next; //指针域
};

class Method
{
public:
    Node* head;
    int size;

    Method();   //构造函数用于处理头指针
    ~Method();  //析构函数用于释放头指针的内存
    int CreatNode1();   //创建单链表(尾插)
    int PrintNode();   //遍历单链表
    void InsertNode();  //插入
    void DeleteNode();  //删除
    int SearchNode();  //查找
    void ChangeNode();  //修改
    void DestoryNode();  //销毁
};

Method::Method()
{
    head = new Node;
    head->data = 0;
    head->next = NULL;
}

Method::~Method()
{
    delete head;
}

int Method::CreatNode1()
{
    cout << "请输入想要创建的长度：" << endl;
    int n;
    cin >> n;
    //判断是否创建合理
    while (true)
    {
        if (n < 0)
        {
            cout << "输入有误，请重新输入：" << endl;
            cin >> n;
            continue;
        }
        break;
    }
    //创建两个结点，用于更迭单链表的位置
    Node* ptemp;
    Node* pnew;
    //给当前结点分配内存
    ptemp = new Node;
    ptemp = this->head;  //让当前结点等于头结点
    cout << "开始创建数据" << endl;
    int m;   //结点的数据
    for (int i = 0; i < n; i++)
    {
        //给新结点分配内存
        pnew = new Node;
        cout << "请输入第" << i+1 << "个数据：" << " ";
        cin >> m;
        pnew->data = m;
        ptemp->next = pnew;
        ptemp  = pnew;
    }
    cout << "输入完成" << endl;
    pnew->next = NULL;
    this->size = n;
    return this->size;
}

int Method::PrintNode()
{
    //判断单链表的存在
    if (this->head->next == NULL)
    {
        cout << "单链表为空" << endl;
        return -1;
    }

    Node* ptemp = new Node;     //创建一个新的结点接收数据，并分配内存
    ptemp = this->head;
    for (int i = 0; i < this->size; i++)
    {
        cout << ptemp->next->data << "->";
        ptemp = ptemp->next;
    }
    cout << "NULL" << endl;
}

void Method::InsertNode()
{
    cout << "请输入要插入的位置：" << " ";
    int n;
    cin >> n;
    //判断输入的位置是否有误
    while (true)
    {
        if (n < 0 || n > this->size + 1)
        {
            cout << "输入有误，请重新输入：" << endl;
            cin >> n;
            continue;
        }
        break;
    }
    Node* p = new Node;
    cout << "请输入新结点的数据" << endl;
    cin >> p->data;
    //头插
    if (n == 1)
    {
        p->next = this->head->next;
        this->head->next = p;
    }
    //尾插
    Node* q = new Node;
    q = this->head;
    if (n == this->size + 1)
    {
        for (int i = 0; i < this->size; i++)
        {
            q = q->next;
            if (q->next == NULL)
            {
                q->next = p;
                p->next = NULL;
            }
        }
    }
    //任意位置插入
    if (n != 1 && n != this->size + 1)
    {
        for (int i = 0; i < n - 1; i++)
        {
            q = q->next;
        }
        p->next = q->next;
        q->next = p;
    }
    this->size++;
}

void Method::DeleteNode()
{
    cout << "请输入想要删除的位置：" << endl;
    int n;
    cin >> n;
    //判断输入是否有误
    while (true)
    {
        if (n > this->size || n < 1)
        {
            cout << "输入有误，请重新输入" << endl;
            cin >> n;
            continue;
        }
        break;
    }
    //头删
    if (n == 1)
    {
        this->head->next = this->head->next->next;
        free(this->head->next);
    }
    //尾删
    Node* q = new Node;
    q = this->head;
    if (n == this->size)
    {
        while (true)
        {
            q = q->next;
            if (q->next->next == NULL)
            {
                free(q->next);
                q->next = NULL;
                break;
            }
        }
    }
    //任意位置删除
    if (n != 1 && n != this->size)
    {
        for (int i = 0; i < n - 1; i++)
            q = q->next;
        Node* p = new Node;
        p = q->next;
        q->next = q->next->next;
        free (p);
    }
    this->size --;
}

int Method::SearchNode()
{
    cout << "请输入想要查找的数据：" <<endl;
    int n;
    cin >> n;
    Node* p = new Node;
    p = this->head;
    for (int i = 0; i < this->size; i++)
    {
        p = p->next;
        if (p->data == n)
        {
            cout << "查找的数据是：" << p->data << " "
                << "所在的位置是：" << i+1 << endl;
            return 0;
        }
    }
    cout << "没有找到想要查找的数据！" << endl;
    return -1;
}

void Method::ChangeNode()
{
    cout << "请输入想要修改的位置的数据：" << endl;
    int n;
    cin >> n;
    //判断输入的位置是否合法
    while (true)
    {
        if (n < 0 || n > this->size)
        {
            cout << "输入有误，请重新输入" << endl;
            cin >> n;
            continue;
        }
        break;
    }
    Node* p = new Node;
    p = this->head;
    for (int i = 0; i < n; i++)
    {
        p = p->next;
    }
    cout << "要将数据修改成什么？" << endl;
    int m;
    cin >> m;
    p->data = m;
}

void Method::DestoryNode()
{
    Node* p;
    Node* q;
    p = this->head->next;
    for (int i = 0; p->next == NULL; i++)
    {
        q = p->next;
        free (p);
        p = q;
    }

    head->next = NULL;
}

int main()
{
    Method mth;
    mth.CreatNode1();
    mth.PrintNode();
    mth.InsertNode();
    mth.PrintNode();
    mth.DeleteNode();
    mth.PrintNode();
    mth.SearchNode();
    mth.ChangeNode();
    mth.PrintNode();

    return 0;
}

也算是自己写了一个早上吧，记录自己的学习进度吧，网上数据结构大部分使用c讲的，我看的也是c的书，但是不是特别想拿c去写数据结构，所以看完书以后自己琢磨写了写cpp的单链表

分区块实现

单链表的创建

	cout << "请输入想要创建的长度：" << endl;
    int n;
    cin >> n;
    //判断是否创建合理
    while (true)
    {
        if (n < 0)
        {
            cout << "输入有误，请重新输入：" << endl;
            cin >> n;
            continue;
        }
        break;
    }
    //创建两个结点，用于更迭单链表的位置
    Node* ptemp;
    Node* pnew;
    //给当前结点分配内存
    ptemp = new Node;
    ptemp = this->head;  //让当前结点等于头结点
    cout << "开始创建数据" << endl;
    int m;   //结点的数据
    for (int i = 0; i < n; i++)
    {
        //给新结点分配内存
        pnew = new Node;
        cout << "请输入第" << i+1 << "个数据：" << " ";
        cin >> m;
        pnew->data = m;
        ptemp->next = pnew;
        ptemp  = pnew;
    }
    cout << "输入完成" << endl;
    pnew->next = NULL;
    this->size = n;
    return this->size;

遍历单链表

 	//判断单链表的存在
    if (this->head->next == NULL)
    {
        cout << "单链表为空" << endl;
        return -1;
    }

    Node* ptemp = new Node;     //创建一个新的结点接收数据，并分配内存
    ptemp = this->head;
    for (int i = 0; i < this->size; i++)
    {
        cout << ptemp->next->data << "->";
        ptemp = ptemp->next;
    }
    cout << "NULL" << endl;

在单链表中插入数据（分为头插，尾插和任意插）

	cout << "请输入要插入的位置：" << " ";
    int n;
    cin >> n;
    //判断输入的位置是否有误
    while (true)
    {
        if (n < 0 || n > this->size + 1)
        {
            cout << "输入有误，请重新输入：" << endl;
            cin >> n;
            continue;
        }
        break;
    }
    Node* p = new Node;
    cout << "请输入新结点的数据" << endl;
    cin >> p->data;
    //头插
    if (n == 1)
    {
        p->next = this->head->next;
        this->head->next = p;
    }
    //尾插
    Node* q = new Node;
    q = this->head;
    if (n == this->size + 1)
    {
        for (int i = 0; i < this->size; i++)
        {
            q = q->next;
            if (q->next == NULL)
            {
                q->next = p;
                p->next = NULL;
            }
        }
    }
    //任意位置插入
    if (n != 1 && n != this->size + 1)
    {
        for (int i = 0; i < n - 1; i++)
        {
            q = q->next;
        }
        p->next = q->next;
        q->next = p;
    }
    this->size++;

删除单链表的数据（分为头删，尾删和任意删）

	cout << "请输入想要删除的位置：" << endl;
    int n;
    cin >> n;
    //判断输入是否有误
    while (true)
    {
        if (n > this->size || n < 1)
        {
            cout << "输入有误，请重新输入" << endl;
            cin >> n;
            continue;
        }
        break;
    }
    //头删
    if (n == 1)
    {
        this->head->next = this->head->next->next;
        free(this->head->next);
    }
    //尾删
    Node* q = new Node;
    q = this->head;
    if (n == this->size)
    {
        while (true)
        {
            q = q->next;
            if (q->next->next == NULL)
            {
                free(q->next);
                q->next = NULL;
                break;
            }
        }
    }
    //任意位置删除
    if (n != 1 && n != this->size)
    {
        for (int i = 0; i < n - 1; i++)
            q = q->next;
        Node* p = new Node;
        p = q->next;
        q->next = q->next->next;
        free (p);
    }
    this->size --;

查找单链表的数据（按照给定值查找）

	cout << "请输入想要查找的数据：" <<endl;
    int n;
    cin >> n;
    Node* p = new Node;
    p = this->head;
    for (int i = 0; i < this->size; i++)
    {
        p = p->next;
        if (p->data == n)
        {
            cout << "查找的数据是：" << p->data << " "
                << "所在的位置是：" << i+1 << endl;
            return 0;
        }
    }
    cout << "没有找到想要查找的数据！" << endl;
    return -1;

修改单链表的数据（按照位置修改）

	cout << "请输入想要修改的位置的数据：" << endl;
    int n;
    cin >> n;
    //判断输入的位置是否合法
    while (true)
    {
        if (n < 0 || n > this->size)
        {
            cout << "输入有误，请重新输入" << endl;
            cin >> n;
            continue;
        }
        break;
    }
    Node* p = new Node;
    p = this->head;
    for (int i = 0; i < n; i++)
    {
        p = p->next;
    }
    cout << "要将数据修改成什么？" << endl;
    int m;
    cin >> m;
    p->data = m;

销毁单链表

	Node* p;
    Node* q;
    p = this->head->next;
    for (int i = 0; p->next == NULL; i++)
    {
        q = p->next;
        free (p);
        p = q;
    }

    head->next = NULL;

最后呢，因为这是我的第一篇blog，有什么问题欢迎指正，谢谢~

这篇关于C++单链表的实现（未用模板类）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航