AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

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

采用模板类实现的好处是，不用拘泥于特定的数据类型。就像活字印刷术，制定好模板，就可以批量印刷，比手抄要强多少倍！

此处不具体介绍泛型编程，还是着重叙述链表的定义和相关操作。 

 

 链表结构定义

定义单链表的结构可以有4方式。如代码所示。

本文采用的是第4种结构类型

复制代码
/* ************************************************************************
1、复合类：在Node类中定义友元的方式，使List类可以访问结点的私有成员
************************************************************************ */
class LinkNode
{
    friend  class LinkList;
private:
     int data;
    LinkNode *next;
};

class LinkList
{
public:
     // 单链表具体操作
private:
    LinkNode *head;
}; 

/* ************************************************************************
2、嵌套类：在List内部定义Node类，但是Node的数据成员放在public部分，使List
和Node均可以直接访问Node的成员
************************************************************************ */
class LinkList
{
public:
     // 单链表具体操作
private:
     class LinkNode
    {
     public:
         int data;
        LinkNode *next;
    };
    LinkNode *head;
}; 

/* ************************************************************************
3、继承：在Node类中把成员定义为protected，然后让List继承Node类，这样就可以
访问Node类的成员了。
************************************************************************ */
class LinkNode
{
protected:
     int data;
    LinkNode *next;
};

class LinkList :  public LinkNode
{
public:
     // 单链表具体操作
private:
    LinkNode *head;
}; 

/* ************************************************************************
4、直接用struct定义Node类，因为struct的成员默认为公有数据成员，所以可直接
访问（struct也可以指定保护类型）。
************************************************************************ */
struct LinkNode
{
     int data;
    LinkNode *next;
};

class LinkList
{
public:
     // 单链表具体操作
private:
    LinkNode *head;
}; 
复制代码

 

单链表的模板类定义

使用模板类需要注意的一点是template<class T>必须定义在同一个文件，否则编译器会无法识别。

如果在.h中声明类函数，但是在.cpp中定义函数具体实现， 会出错。所以，推荐的方式是直接在.h中定义。

复制代码
/*  单链表的结点定义  */
template< class T>
struct LinkNode
{
    T data;
    LinkNode<T> *next;
    LinkNode(LinkNode<T> *ptr = NULL){next = ptr;}
    LinkNode( const T &item, LinkNode<T> *ptr = NULL)    
     // 函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    {
        next = ptr;
        data = item;
    }
};

/*  带头结点的单链表定义  */
template< class T>
class LinkList
{
public:
     // 无参数的构造函数
    LinkList(){head =  new LinkNode<T>;}
     // 带参数的构造函数
    LinkList( const T &item){head =  new LinkNode<T>(item);}
     // 拷贝构造函数
    LinkList(LinkList<T> &List);
     // 析构函数
    ~LinkList(){Clear();}
     // 重载函数:赋值
    LinkList<T>&  operator=(LinkList<T> &List);
     // 链表清空
     void Clear();
     // 获取链表长度
     int Length()  const;
     // 获取链表头结点
    LinkNode<T>* GetHead()  const;
     // 设置链表头结点
     void SetHead(LinkNode<T> *p);
     // 查找数据的位置，返回第一个找到的满足该数值的结点指针
    LinkNode<T>* Find(T &item);
     // 定位指定的位置，返回该位置上的结点指针
    LinkNode<T>* Locate( int pos);
     // 在指定位置pos插入值为item的结点，失败返回false
     bool Insert(T &item,  int pos);
     // 删除指定位置pos上的结点，item就是该结点的值，失败返回false
     bool Remove( int pos, T &item);
     // 获取指定位置pos的结点的值，失败返回false
     bool GetData( int pos, T &item);
     // 设置指定位置pos的结点的值，失败返回false
     bool SetData( int pos, T &item);
     // 判断链表是否为空
     bool IsEmpty()  const;
     // 打印链表
     void Print()  const;
     // 链表排序
     void Sort();
     // 链表逆置
     void Reverse();
private:
    LinkNode<T> *head;
};
复制代码

 

定位位置  

复制代码 
/* 返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL */
template<class T>
LinkNode<T>* LinkList<T>::Locate(int pos)
{
    int i = 0;
    LinkNode<T> *p = head;

    if (pos < 0)
        return NULL;

    while (NULL != p && i < pos)
    {
        p = p->next;
        i++;
    }
    
    return p;
}
复制代码

 

插入结点

单链表插入结点的处理如图 

 

 图：单链表插入操作

要在p结点后插入一个新结点node，（1）要让node的next指针指向p的next结点；（2）再让p的next指向node结点（即断开图中的黑色实线，改成红色虚线指向node）

接下来：node->next = p->next; p->next = node; 

复制代码 
template<class T>
bool LinkList<T>::Insert(T &item, int pos)
{
    LinkNode<T> *p = Locate(pos);
    if (NULL == p)
        return false;

    LinkNode<T> *node = new LinkNode<T>(item);
    if (NULL == node)
    {
        cerr << "分配内存失败!" << endl;
        exit(1);
    }
    node->next = p->next;
    p->next = node;
    return true;
}
复制代码

 

删除结点

删除结点的处理如图：

 

图：单链表删除 

删除pos位置的结点，如果这个位置不存在结点，则返回false；

如果找到对应结点，则通过实参item输出要删除的结点的数值， 然后删除结点并返回true。

复制代码 
template<class T>
bool LinkList<T>::Remove(int pos, T &item)
{
    LinkNode<T> *p = Locate(pos);
    if (NULL == p || NULL == p->next)
        return false;

    LinkNode<T> *del = p->next;
    p->next = del->next;
    item = del->data;
    delete del;
    return true;
}
复制代码

 

清空链表 

遍历整个链表，每次head结点的next指针指向的结点，直到next指针为空。

最后保留head结点。 

复制代码 
template<class T>
void LinkList<T>::Clear()
{
    LinkNode<T> *p = NULL;

    //遍历链表，每次都删除头结点的next结点，最后保留头结点
    while (NULL != head->next)
    {
        p = head->next;
        head->next = p->next;   //每次都删除头结点的next结点
        delete p;
    }
}
复制代码

 

求链表长度和打印链表

着两个功能的实现非常相近，都是遍历链表结点，不赘述。 

复制代码 
template<class T>
void LinkList<T>::Print() const
{
    int count = 0;
    LinkNode<T> *p = head;
    while (NULL != p->next)
    {
        p = p->next;
        std::cout << p->data << " ";
        if (++count % 10 == 0)  //每隔十个元素，换行打印
            cout << std::endl;
    }
}

template<class T>
int LinkList<T>::Length() const
{
    int count = 0;
    LinkNode<T> *p = head->next;
    while (NULL != p)
    {
        p = p->next;
        ++count;
    }
    return count;
}
复制代码

 

单链表倒置

单链表的倒置处理如图： 

图：单链表倒置 

（1）初始状态：prev = head->next; curr = prev->next;

（2）让链表的第一个结点的next指针指向空

（3）开始进入循环处理，让next指向curr结点的下一个结点；再让curr结点的next指针指向prev。即：next = curr->next; curr->next = prev; 

（4）让prev、curr结点都继续向后移位。即：prev = curr; curr = next;

（5）重复(3)、（4）动作，直到curr指向空。这时循环结束，让haed指针指向prev，此时的prev是倒置后的第一个结点。即：head->next = prev;

复制代码 
template<class T>
void LinkList<T>::Reverse()
{
    LinkNode<T> *pre = head->next;
    LinkNode<T> *curr = pre->next;
    LinkNode<T> *next = NULL;

    head->next->next = NULL;
    while (curr)
    {
        next = curr->next;
        curr->next = pre;
        pre = curr;
        curr = next;
    }

    head->next = pre;
}
复制代码

 本文转自静默虚空博客园博客，原文链接：http://www.cnblogs.com/jingmoxukong/p/3827011.html，如需转载请自行联系原作者

文章标签：
C++
编译器
关键词：
C++模板类
C++模板
C++类
C++单链表
单链表C++
文艺小青年
目录
相关文章
平凡程序猿~
|
7月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
163 0
hahaha无
|
3月前
|
存储 算法 安全
c++模板进阶操作——非类型模板参数、模板的特化以及模板的分离编译
在 C++ 中，仿函数（Functor）是指重载了函数调用运算符()的对象。仿函数可以像普通函数一样被调用，但它们实际上是对象，可以携带状态并具有更多功能。与普通函数相比，仿函数具有更强的灵活性和可扩展性。仿函数通常通过定义一个包含operator()的类来实现。public:// 重载函数调用运算符Add add;// 创建 Add 类的对象// 使用仿函数return 0;
hahaha无
118 0
hahaha无
|
3月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
85 0
hahaha无
|
3月前
|
存储 编译器 程序员
c++的类（附含explicit关键字，友元，内部类）
本文介绍了C++中类的核心概念与用法，涵盖封装、继承、多态三大特性。重点讲解了类的定义（`class`与`struct`）、访问限定符（`private`、`public`、`protected`）、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数（构造函数、析构函数、拷贝构造、赋值重载）以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员（变量与函数）、友元（友元函数与友元类）的概念及其使用场景，并简要介绍了内部类的特性。
hahaha无
166 0
ephemerals__
|
5月前
|
编译器 C++ 容器
【c++11】c++11新特性（上）（列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式）
C++11为C++带来了革命性变化，引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式，initializer_list简化了容器多元素初始化；右值引用和移动语义优化了资源管理，减少拷贝开销；类新增移动构造和移动赋值函数提升性能；lambda表达式提供匿名函数对象，增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展，提升了开发效率与程序性能。
ephemerals__
168 12
蓝易云
|
6月前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨，我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性，而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧，对于提升C++编程水平至关重要。
蓝易云
126 16
预备女程序员a
|
6月前
|
编译器 C++
模板（C++）
本内容主要讲解了C++中的函数模板与类模板。函数模板是一个与类型无关的函数家族，使用时根据实参类型生成特定版本，其定义可用`typename`或`class`作为关键字。函数模板实例化分为隐式和显式，前者由编译器推导类型，后者手动指定类型。同时，非模板函数优先于同名模板函数调用，且模板函数不支持自动类型转换。类模板则通过在类名后加`&lt;&gt;`指定类型实例化，生成具体类。最后，语录鼓励大家继续努力，技术不断进步！
预备女程序员a
103 2
预备女程序员a
|
6月前
|
编译器 C++
类和对象（中 ）C++
本文详细讲解了C++中的默认成员函数，包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系，如构造函数的主要任务是初始化对象，而非创建空间；析构函数用于清理资源；拷贝构造与赋值运算符的区别在于前者用于创建新对象，后者用于已存在的对象赋值。同时，文章还探讨了运算符重载的规则及其应用场景，并通过实例加深理解。最后强调，若类中存在资源管理，需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
预备女程序员a
80 1
预备女程序员a
|
6月前
|
存储 编译器 C++
类和对象（上）（C++）
本篇内容主要讲解了C++中类的相关知识，包括类的定义、实例化及this指针的作用。详细说明了类的定义格式、成员函数默认为inline、访问限定符（public、protected、private）的使用规则，以及class与struct的区别。同时分析了类实例化的概念，对象大小的计算规则和内存对齐原则。最后介绍了this指针的工作机制，解释了成员函数如何通过隐含的this指针区分不同对象的数据。这些知识点帮助我们更好地理解C++中类的封装性和对象的实现原理。
预备女程序员a
120 1
ephemerals__
|
6月前
|
安全 C++
【c++】继承（继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员）
本文深入探讨了C++中的继承机制，作为面向对象编程（OOP）的核心特性之一。继承通过允许派生类扩展基类的属性和方法，极大促进了代码复用，增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式（public、protected、private）、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题，并对比了继承与组合的优缺点。最后总结指出，虽然继承提高了代码灵活性和复用率，但也带来了耦合度高的问题，建议在“has-a”和“is-a”关系同时存在时优先使用组合。
ephemerals__
329 6