开发者社区> 大黄有故事> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

C++ 数据结构链表的实现代码

简介: C++ 链表 之前一直没怎么在意C++中的链表,但是突然一下子让自己写,就老是出错。没办法,决定好好恶补一下该方面的知识,也为今后的数据结构打下个良好的基础,于是我总结出以下几点,有些地方可能不正确,还望大家不吝赐教,旨在共同进步。
+关注继续查看

C++ 链表

之前一直没怎么在意C++中的链表,但是突然一下子让自己写,就老是出错。没办法,决定好好恶补一下该方面的知识,也为今后的数据结构打下个良好的基础,于是我总结出以下几点,有些地方可能不正确,还望大家不吝赐教,旨在共同进步。

总结:

1、链表List的基本单元是节点Node,因此想要操作方便,就必须为每一步打好基础,Node的基本结构如下:

class Node {
public:
    int data;
    Node *next;

    Node(int da = 0, Node *p = NULL) {
        this->data = da;
        this->next = p;
    }
};

我们可以看出,Node的成员变量一共有两个,都是public,因为我们要对这两个变量进行操作,所以不能是private类型的。然后是一个构造函数,第二个参数默认值为NULL,也就是说如果我们创建新节点时只指定第一个参数,而不写第二个参数,那么它默认的就是NULL,以这种方式可以更灵活的使用Node,个人建议这么使用哦。

2、第二步就是创建我们的链表了,同样我们这里先给出链表的代码,再进行一一的解释。

class List{
private:
  Node *head,*tail;
  int position;
public:
  List(){head=tail=NULL;};
  ~List(){delete head;delete tail;};
  void print();
  void Insert(int da=0);
  void Delete(int da=0);
  void Search(int da=0);
};

我们这里面有两个数据类型,一个是Node。另一个是指代节点位置的成员变量(起不到什么作用,且不去管它吧)。使用head和tail来命名便是为了见名知意,使操作更加准确。然后是重要的六个函数,各自的功能不言而喻咯,其实最重要的是在每一个函数中我们都默认能操作head和tail两个成员变量,这样能简化我们的参数列表,使得函数更加优雅。
下面是我的一个单链表的实现,包含创建链表,插入值,删除特定的值,查找特定值得在链表中的位置。

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node *next;

    Node(int da = 0, Node *p = NULL) {
        this->data = da;
        this->next = p;
    }
};

class List {
private:
    Node *head, *tail;
    int position;
public:
    List() { head = tail = NULL; };

    ~List() {
        delete head;
        delete tail;
    };

    void print();

    void Insert(int da = 0);

    void Delete(int da = 0);

    void Search(int da = 0);

    int getValueAt(int position);

    void setValueAt(int position, int da);
};

int List::getValueAt(int position) {
    Node *p = head;
    if (p == NULL) {
        cout << "The List is Empty!" << endl;
    } else {
        int posi = 0;
        while (p != NULL && posi != position) {
            posi++;
            p = p->next;
        }
        if (p == NULL) {
            cout << "There is no value of this position in this List!" << endl;
        } else {
            cout << "In this Position,the value is" << p->data << endl;
        }
    }
    return p->data;
}

void List::setValueAt(int position, int da) {
    Node *p = head;
    if (p == NULL) {
        cout << "The List is Empty!" << endl;
    } else {
        int posi = 0;
        while (p != NULL && posi != position) {
            posi++;
            p = p->next;
        }
        if (p == NULL) {
            cout << "There is No Position in this List!" << endl;
        } else {
            p->data = da;
            cout << "The Value in this position has been Updated!" << endl;
        }
    }
}

void List::Search(int da) {

    Node *p = head;
    if (p == NULL) {
        cout << "Sorry, The List is Empty!" << endl;
        return;
    }
    int count = 0;
    while (p != NULL && p->data != da) {
        p = p->next;
        count++;
    }
    cout << "the value you want to search is at position %d" << count << endl;
}

void List::Delete(int da) {
    Node *p = head, *q = head;
    if (p == NULL) {
        cout << "Sorry, The List is Empty!" << endl;
        return;
    }
    while (p != NULL && p->data != da) {
        q = p;
        p = p->next;
    }
    q->next = p->next;
    cout << "The Deletion Operation had been finished!" << endl;
}

void List::Insert(int da) {
    if (head == NULL) {
        head = tail = new Node(da);
        head->next = NULL;
        tail->next = NULL;
    } else {
        Node *p = new Node(da);
        tail->next = p;
        tail = p;
        tail->next = NULL;
    }

}

void List::print() {
    Node *p = head;
    while (p != NULL) {
        cout << p->data << " \a";
        p = p->next;
    }
    cout << endl;
}

int main() {
    cout << "Hello World!" << endl;
    List l1;
    l1.Insert(1);
    l1.Insert(2);
    l1.Insert(3);
    l1.Insert(4);
    l1.Insert(5);
    l1.Insert(6);
    l1.Insert(7);
    l1.print();
    l1.Search(4);
    l1.Delete(6);
    l1.print();
    l1.getValueAt(3);
    l1.setValueAt(3, 9);
    l1.print();
    cout << "The End!" << endl;
    return 0;
}

运行结果:

这里写图片描述

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《恋上数据结构第1季》二叉树代码实现
《恋上数据结构第1季》二叉树代码实现
11 0
【数据结构】堆(C++)
【数据结构】堆(C++)
23 0
【数据结构】栈(C++ )
【数据结构】栈(C++ )
17 0
【数据结构】计算器的实现--栈的实战
【数据结构】计算器的实现--栈的实战
21 0
【数据结构】C++用链表实现一个箱子排序附源代码详解
【数据结构】C++用链表实现一个箱子排序附源代码详解
33 0
C++数据类型——链表
C++数据类型——链表
59 0
用js来实现那些数据结构07(链表01-链表的实现)
  前面讲解了数组,栈和队列。其实大家回想一下。它们有很多相似的地方。甚至栈和队列这两种数据结构在js中的实现方式也都是基于数组。无论增删的方式、遵循的原则如何,它们都是有序集合的列表。在js中,我们新建一个数组并不需要限定他的大小也就是长度,但是实际上,数组的底层仍旧为初始化的数组设置了一个长度限制。
774 0
【数据结构2】链表
1单链表 1结点定义 2头插法建立单链表 3尾插法建立单链表 4按序号查找表结点 5按值查找表结点 6插入结点操作 7删除结点操作 8合并有序链表 2循环双链表 1结点定义 2插入和删除操作 3循环单链表 4带尾指针的循环单链表 5静态链表 由于顺序表的插入和删除操作需要移动大量元素,影响了效率。
974 0
+关注
大黄有故事
java,算法,编程语言相关技术专家
114
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载