数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

0. 数据结构图文解析系列

数据结构系列文章

数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

数据结构图文解析之:栈的简介及C++模板实现

数据结构图文解析之:队列详解与C++模板实现

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

数据结构图文解析之:AVL树详解及C++模板实现

数据结构图文解析之:二叉堆详解及C++模板实现

1. 线性表简介

线性表是一种线性结构,它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中,除了头尾元素,每个元素都有且只有一个直接前驱,有且只有一个直接后继,而序列头元素没有直接前驱,序列尾元素没有直接后继。 数据结构中常见的线性结构有数组、单链表、双链表、循环链表等。线性表中的元素为某种相同的抽象数据类型。可以是C语言的内置类型或结构体,也可以是C++自定义类型。

2. 数组

数组在实际的物理内存上也是连续存储的,数组有上界和下界。C语言中定义一个数组:

数组下标是从0开始的,a[0]对应第一个元素。其中,a[0]称为数组a的下界,a[6]称为数组a的上届。超过这个范围的下标使用数组,将造成数组越界错误。 数组的特点是:数据连续,支持快速随机访问。 数组分为固定数组与动态数组。其中固定数组的大小必须在编译时就能够确认,动态数组允许在运行时申请数组内存。复杂点的数组是多维数组,多维数组实际上也是通过一维数组来实现的。在C语言中,可以通过malloc来分配动态数组,C++使用new。另外,C++的标准模板库提供了动态数组类型vector以及内置有固定数组类型array。

3. 单向链表

单向链表是链表的一种。链表由节点所构成,节点内含一个指向下一个节点的指针,节点依次链接成为链表。因此,链表这种数据结构通常在物理内存上是不连续的。链表的通常含有一个头节点,头节点不存放实际的值,它含有一个指针,指向存放元素的第一个节点。

3.1 单向链表的节点结构

//节点结构
template <typename T>
class Node
{
public :
    T _value;
    Node* _next;
public:
    Node() = default;
    Node(T value, Node * next)
        : _value(value), _next(next){}
};
  1. _value: 节点的值
  2. _next: 指针,指向下一个节点

3.2 单向链表的抽象数据结构

//单链表
template <typename T>
class SingleLink
{
public:
    typedef Node<T>*  pointer;
    SingleLink();
    ~SingleLink();
 
    int size();                         //获取长度
    bool isEmpty();                     //判空
 
    Node<T>* insert(int index, T t); //在指定位置进行插入
    Node<T>* insert_head(T t);         //在链表头进行插入
    Node<T>* insert_last(T t);         //在链表尾进行插入
 
    Node<T>*  del(int index);         //在指定位置进行删除
    Node<T>*  delete_head();         //删除链表头
    Node<T>*  delete_last();         //删除链表尾
 
    T get(int index);                 //获取指定位置的元素
    T get_head();                     //获取链表头元素
    T get_last();                     //获取链表尾元素
 
    Node<T>* getHead();                 //获取链表头节点
 
private :
    int count;
    Node<T> * phead;                
 
private :
    Node<T> * getNode(int index);      //获取指定位置的节点
};
  1. phead: 链表的头节点。
  2. count: 链表元素个数。

3.3 单链表添加节点

链表的插入元素操作时间复杂度O(1),只需要进行指针的指向修改操作。

在2之后添加7:

  1. 为元素7构建节点 。
  2. 将节点2 的next指针指向节点7。
  3. 将节点7的next指向节点3。(节点3 的位置要先保留起来)
/*
在指定位置插入新节点
*/
template <typename T>
Node<T>* SingleLink<T>::insert(int index, T t)
{
    Node<T> * preNode = getNode(index);
    if (preNode)
    {
        Node<T> *newNode = new Node<T>(t,preNode->_next);
        preNode->_next = newNode;
        count++;
        return newNode;
    }
    return nullptr;
};
/*
从头部插入
*/
template <typename T>
Node<T>* SingleLink<T>::insert_head(T t)
{
    return insert(0, t);
};
/*
从尾部进行插入
*/
template <typename T>
Node<T>* SingleLink<T>::insert_last(T t)
{
    return insert(count, t);
};

3.4 单链表删除节点

单链表的删除操作同样是一个时间复杂度O(1)的操作,它也只需要修改节点的指针指针后即可销毁被删除节点。 例如我们删除链表元素7:

相应的代码:

/*
删除链表指定位置元素
*/
template <typename T>
Node<T>* SingleLink<T>::del(int index)
{
    if (isEmpty())
        return nullptr;
    Node<T>* ptrNode = getNode(index);
    Node<T>* delNode = ptrNode->_next;
    ptrNode->_next = delNode->_next;
    count--;
    delete delNode;
    return ptrNode->_next;
};
/*
删除头节点
*/
template<typename T>
Node<T>* SingleLink<T>::delete_head()
{
    return del(0);
};
/*
删除尾节点
*/
template<typename T>
Node<T>*SingleLink<T>::delete_last()
{
    return del(count);
};

3.5 单链表代码测试

int main()
{
    SingleLink<int> link;
    for (int i = 0; i < 10; i++)
    {
        link.insert(i, i);
    }
    cout << link.size() << endl;
 
    link.insert_head(1111);
    link.insert_last(2222);
 
    SingleLink<int>::pointer ptr = link.getHead();
    while (ptr != nullptr)
    {
        cout << ptr->_value << endl;
        ptr = ptr->_next;
    }
 
    getchar();
    return 0;
}

测试结果:

10
1111
0
1
2
3
4
5
6
7
8
9
2222

其他的操作较为简单,不在这里贴出代码,文章底部有完整链表类的代码链接。

4. 双向链表

单链表的节点链接是单方向的,要得到指定节点的前一个节点,必须从头遍历链表。 双向链表是链表的一种。与单链表一样,双向节点由节点链接而成,每个节点含有两个指针,分别指向直接前驱与直接后继。从双向链表的任何一个节点开始都能够遍历整个链表。 我们将双向链表实现为双向循环链表,也即是最后一个元素的后继将指向头节点,整个链表形成一个循环 例如,我们为元素1,2,3,4,5 构建一个双向循环链表

在图中: 表头为空。 表头的前驱节点是节点5,表头的后继节点是节点1; 节点1的前驱节点是表头,节点1的后继节点是节点2; 节点2的前驱节点是节点1,节点2的后继节点是节点3; ...

4.1 双向链表节点结构

双向循环的节点中,比单向链表中多了一个指向直接前驱的指针

/*
双向链表的节点结构
*/
template <typename T>
struct Node
{
public:
    Node()= default;
    Node(T value, Node<T>* preptr, Node<T>* nextptr)
        :_value(value), pre_ptr(preptr), next_ptr(nextptr){}
 
public:
    T _value;
    Node<T>* pre_ptr;
    Node<T>* next_ptr;
};
  1. _value: 节点元素的值
  2. pre_ptr:指向直接前驱的指针
  3. next_ptr:指向直接后继的指针

4.2 双向链表的抽象数据结构

双向链表类的定义与单链表相似。

/*
* 双向链表类
*/
template<typename T>
class DoubleLink
{
public:
    typedef Node<T>* pointer;
public:
    DoubleLink();
    ~DoubleLink(){};
public:
    Node<T>* insert(int index, T value);
    Node<T>* insert_front(T value);
    Node<T>* insert_last(T value);
 
    Node<T>* del(int index);
    Node<T>* delete_front();
    Node<T>* delete_last();
 
    bool isEmpty();
    int size();
 
    T get(int index);
    T get_front();
    T get_last();
    Node<T>* getHead();
 
private:
    Node<T>* phead;
    int count;
private :
    Node<T>* getNode(int index);
};

4.3 双向链表添加节点

与单链表一样,双向链表添加节点的时间复杂度为O(1),它也只需要修改相关指针的指向。

/*
*将新节点插到第一个位置
*/
template <typename T>
Node<T>* DoubleLink<T>::insert_front(T value)
{
    Node<T>* newNode = new Node<int>(value, phead, phead->next_ptr);
    phead->next_ptr ->pre_ptr= newNode;
    phead->next_ptr = newNode;
    count++;
    return newNode;
};
/*
*将新节点插到链表尾部
*/
template <typename T>
Node<T>* DoubleLink<T>::insert_last(T value)
{
    Node<T> * newNode = new Node<int>(value, phead->pre_ptr, phead);
    phead->pre_ptr->next_ptr = newNode;
    phead->pre_ptr = newNode;
    count++;
    return newNode;
};
/*
*将节点位置插到index位置之前
*/
 
template <typename T>
Node<T>* DoubleLink<T>::insert(int index, T value)
{
    if (index == 0)
        return insert_front(value);
 
    Node<T>* pNode = getNode(index);
    if (pNode == nullptr)
        return nullptr;
    Node<T>* newNode = new Node<T>(value, pNode->pre_ptr, pNode);
    pNode->pre_ptr->next_ptr = newNode;
    pNode->pre_ptr = newNode;
    count++;
 
    return newNode;
};

4.4 双向链表删除节点

双向链表的删除操作时间复杂度为O(1).我们删除节点7:

/*
*删除链表第一个节点
*返回删除后链表第一个节点
*/
template<typename T>
Node<T>* DoubleLink<T>::delete_front()
{
    if (count == 0)
    {
        return nullptr;
    }
    Node<T>* pnode = phead->next_ptr;
    phead->next_ptr = pnode->next_ptr;
    pnode->next_ptr->pre_ptr = phead;
    delete pnode;
    count--;
    return phead->next_ptr;
};
/*
*删除链表的末尾节点
*返回删除后链表尾部元素
*/
template<typename T>
Node<T>* DoubleLink<T>::delete_last()
{
    if (count == 0)
    {
        return nullptr;
    }
    Node<T>*pnode = phead->pre_ptr;
    pnode->pre_ptr->next_ptr = phead;
    phead->pre_ptr = pnode->pre_ptr;
    delete pnode;
    count--;
    return phead->pre_ptr;
}
/*
*删除指定位置的元素
*
*/
template <typename T>
Node<T>* DoubleLink<T>::del(int index)
{
    if (index == 0)
        return delete_front();
    if (index == count - 1)
        return delete_last();
    if (index >= count)
        return nullptr;
    Node<T>* pnode = getNode(index);
    pnode->pre_ptr->next_ptr = pnode->next_ptr;
    pnode->next_ptr->pre_ptr = pnode->pre_ptr;
 
    Node<T>* ptemp = pnode->pre_ptr;
    delete pnode;
    count--;
    return ptemp;
};

其他的接口实现都很简单,这里不再讲解。下面有提供完整的工程项目及源代码。

4.5 双向链表代码测试

int main()
{
    DoubleLink<int> dlink;
    //插入测试
    for (int i = 0; i < 10; i++)
    {
        dlink.insert(0, i+10);
    }
    dlink.insert(0,  100);
    dlink.insert_last(1000);
    cout <<"链表长度:"<< dlink.size() << endl;
 
    //删除测试
    dlink.delete_front();
    dlink.delete_last();
    dlink.del(3);
 
 
    DoubleLink<int>::pointer ptr = dlink.getHead();
    ptr = ptr->next_ptr;
    while (ptr != dlink.getHead())
    {
        cout << ptr->_value<<endl;
        ptr = ptr->next_ptr;
    }
 
    getchar();
    return 0;
}

测试结果:

链表长度:12
19
18
17
15
14
13
12
11
10

5. 单链表、双向链表源代码

单链表github源代码:https://github.com/huanzheWu/Data-Structure/blob/master/singleList/singleList/singleList.h 双链表github源代码:https://github.com/huanzheWu/Data-Structure/blob/master/DoubleLink/DoubleLink/DoubleLink.h

另外声明:

  1. C++模板不支持分离编译,因此类定义与成员函数的实现都在.h文件中完成;
  2. 可以看到代码中new一个新节点之后,并没有使用(prt!=nullptr)来检查内存分配是否成功,这是因为new失败时直接抛出异常,不同于C语言malloc内存分配失败返回NULL。

原创文章,转载请注明出处:http://www.cnblogs.com/QG-whz/p/5170147.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

JS 计时器参数剖析与真题

HTML5学堂-码匠:计时器的第一个参数,包含几种不同的书写方法,可以是函数名,匿名函数,JS代码字符串,还有一些面试题当中会出现“函数调用”的书写方式。 那么...

2664
来自专栏前端架构与工程

【译】《Understanding ECMAScript6》- 第一章-基础知识(二)

块绑定 JavaScript中使用var进行变量声明的机制非常怪异。在大多数C系列的编程语言中,变量的创建是在被声明的时刻同时进行的。但是JavaScript并...

2505
来自专栏编程

Python读书笔记5

上期分享了Python相关的字符串应用,重点分享了转义字符。今天和大家分享和字符串相关的函数和应用。 一、字符串的合并! Python用“+”号可以连接两个文本...

1727
来自专栏何俊林

NDK开发才是有精华和特色的部分

通常有特色的应用都会涉及NDK开发,而NDK开发基本是C/C++开发,核心和精华也是在这块。像滤镜、美颜、美肤、人脸识别,编解码,这些出了问项目问题外,首先要过...

2633
来自专栏lhyt前端之路

浅谈js的内存与闭包0.前言1.先说类型2.再说顺序3.然后到了函数4.接着是临时空间5.垃圾回收6.IIFE和闭包

主要结合了内存的概念讲了js的一些的很简单、但是又不小心就犯错的地方。 结论:js执行顺序,先定义,后执行,从上到下,就近原则。闭包可以让外部访问某函数内部变量...

643
来自专栏微信公众号:Java团长

触摸Java常量池

java常量池是一个经久不衰的话题,也是面试官的最爱,题目花样百出,这次好好总结一下。

491
来自专栏程序员互动联盟

【专业技术】C++里面重要的几个关键字的用法

编者按: 这几个关键字非常重要,程序中经常见到他们的身影,但是确切意思有时候还需要多搜索下才能知道。笔者这里把它搬出来,也是希望大家引起重视,努力掌握它。 C+...

3497
来自专栏java思维导图

你真的懂Java中的String、StringBuilder和StringBuffer吗?

相信String这个类是Java中使用得最频繁的类之一,并且又是各大公司面试喜欢问到的地方,今天就来和大家一起学习一下String、StringBui...

1022
来自专栏前端知识分享

第158天:面向对象入门

在这里我们可以理解为创造对象的几种模式:单例模式,工厂模式,构造函数模式,原型模式等。

672
来自专栏枕边书

PHP中的回调函数和匿名函数

前言 前段时间在公司忙成狗,每天下班回家都觉得脑袋沉沉的。周六周日也各种事,不想动手码字,文章也就拖下来了,预感最近一段时间不会太忙了,开始有空写一写,总结分享...

2248

扫码关注云+社区