C++链表类模板

链表（list），即双向链表容器，它不支持随机访问，访问链表元素要指针从链表的某个断点开始，插入和删除操作所花费的时间是固定的，和该元素在链表中的位置无关。list在任何位置插入和删除动作都很快，不像vector只能在末尾操作。

创建list链表类模板的方法：

#include<list>		//调用list头文件
	...
	...
list<type>l;			//定义一个list
//list表示声明一个链表，<type>表示链表的类型，l表示链表名。

list对象主要成员函数说明：

只是一些常用的，其它还有很多list函数。

可以发现，list链表所支持的操作与vector向量很相近，但这些操作的实现原理不尽相同，执行效率也不一样。list双向链表的优点是插入元素的效率很高，缺点是不支持随机访问，也就是说，链表无法像数组一样通过索引来访问，形如：

list<int>l;
l[3]=4;			//错误
cout<<l[3];		//错误

链表无法通过索引进行赋值和输入输出。

关于vector向量的学习————》》C++向量类模板

迭代器

对list双向链表各个元素的访问，通常使用迭代器。
迭代器定义方法：

list<int>::iterator it=l.begin();

定义了一个迭代器it指向双向链表 l 的开始指针。

list双向链表与迭代器的入门应用

源代码：

#include<iostream>
#include<list>		//list头文件
using namespace std;
int main(){
	
	list<int>l;					//定义链表l
	int a[8]={1,3,8,6,7,2,5,4};	//定义数组a
	l=list<int>(a,a+8);			//将数组a赋值给l
	l.sort();					//排序
	
	list<int>::iterator it1=l.begin();	//定义迭代器it1指向双向链表 l 的开始指针
	for(;it1!=l.end();it1++)
		cout<<*it1<<" ";				//通过变更it1的指向遍历输出l中的所有元素
	cout<<endl;
	
	l.insert(l.end(),9); 			//将9插入到l的末尾
	list<int>::iterator it2=l.begin();
	for(;it2!=l.end();it2++)
		cout<<*it2<<" ";
	cout<<endl;
	
	list<int>::iterator it3=l.begin();
	cout<<*it3+3;		//通过迭代器加减的方式取代索引输出
	
	return 0;
}

值得一提的是，循环终止的条件是it!=l.end()而非人们惯用的it<l.end()。

结果图：

类模板都是以template开头写起，模式如下：

template<class type>  //其中class 是固定格式  type 可以指向任何一个数据的类型 如double等。
//函数模板可如下写出

type 函数名称（参数1，参数2）

//类模板如下

class 类名
{
    数据成员

    成员函数
}；

<>内为模板参数，模板参数主要分为两种：

一种是模板类型参数，另一种是模板非类型参数.

当模板被调用时，模板中的代码才会被执行。也就相当于一个实例，称为模板类或模板函数.

创建一个链表类模板步骤如下：

1.先创造一个类模板

template<class type>
class clist  //类模板
{
    private:                      //类中的私有成员

        type *pheader;            //创造一个头结点 可以是任意数据结构的头结点
        int m_nodesum;            //节点数量
    public：
        clist（）                 //构造函数 
        {
             pheader = NULL;      
             m_nodesum = 0;
             //给每个数据初始化   
        }
        
        type *movetrial()         //获取尾结点的函数
        {
               type *ptemp = pheader;    //定义一个临时节点将其指向头结点
               for(int i = 1; i < m_nodesum; i++)
               {
                    ptemp->ptemp->next;      //next指向下一个节点的指针，在后续的类中出现。    
               }
               return ptemp;
         
        }

        void addnode(type *pnode)     //添加节点的函数
        {
                if(m_nodesum == 0)    //判断链表是否为空
                {
                    pheader=pnode;
                }
                else
                {
                    type *ptrail = movetrial();    //获取尾结点的位置
                    ptrail->next = pnode;
                }
                m_nodesum++;    //每次多一个数据存储时节点数加一
        }

        void passlist()
        {
                if(m_nodesum > 0)
                {
                    type *ptmp = pheader;    //定义一个临时节点方便遍历链表
                    printf("\t\t姓名\t\t号码\n");
				    printf("\t\t%s\t\t%d\n",ptmp->name,ptmp->num);
                    for(int i = 1; i < m_nodesum; i++)
				    {
					    ptmp=ptmp->next;    //获取下一个节点
					    printf("\t\t%s\t\t%d\n",ptmp->name,ptmp->num);
				    }
                }
        }

        ~clist()    //类中的析构函数，将所有的数据都进行删除处理
        {
            if(m_nodesum > 0)
            {
                type *pdelete = pheader;
                type *t=NULL;
                for(int i = 0; i < m_nodesum; i++)
                {
                        t = pdelete->next;    // 保存链表后一个未被删除的数据
                        delete pdelete;    //释放当前节点
                        pdelete = t;
                }
                m_nodesum = 0;
                pdelete = NULL;
                t = NULL;
            }
            pheader = NULL; 
        }
};

链表的类模板完成后，要出现一个参数类来代替其中的type。并起到可以保存数据的作用，可以使用类或者结构体都可以完成本操作。（其中结构体和类的一个区别是：结构体中不能有成员函数，但是类中可以有成员函数）。

2.完成上述的一个参数类

利用这个类来代替上述链表类中的type，用来保存数据

class cnode
{
    public:
        cnode *next;
        char name[28];
        int num;
    cnode()
    {
        next = NULL;
    }
};

3.写出主函数：

代码如下：

int main()
{
	int n;
	clist<cnode> nodelist;    //构造一个类模板实例
	cout<<"请输入成员个数:"<<endl;
	cin>>n;
	cout<<"请输入成员信息:"<<endl;
	for(int i=0;i<n;i++)
	{
		node *pnode=new cnode();    //给cnode类开辟一个空间保存数据
		cin>>pnode->name>>pnode->num;
		nodelist.addnode(pnode);     //将其添加到链表中
	}
	nodelist.passlist();            //遍历链表输出
	return 0;
}

运行结果如下：

 此链表模板可以应用任意一个程序之中，只要自己创建一个类模板实例即可，不需要将所有的代码重新再敲一遍，这样节省了很多时间。例如我们现在要创建一个球队的数据，只需要知道球队几个人以及各个人的姓名以及球衣的号码即可。

clist<cnode> basketballteam;
cout<<"请输入球队成员个数:"<<endl;
	cin>>n;
	cout<<"请输入球队成员信息:"<<endl;
	for(int i=0;i<n;i++)
	{
		node *pnode=new node();
		cin>>pnode->name>>pnode->num;
		basketballteam.add(pnode); 
	}
	basketballteam.passlist();
	

如上代码，我们还可以将其改为通讯录的保存或者班级成员的信息保存链表。

只需要构造一个模板实例 将名字改为我们所需要的名字，输入输出数据也可以发生更改，只需要在链表类模板中将其遍历的函数中输出的结构改变即可。

第一篇博客就到这里了，本人（c++小白）只是将自己理解的链表模板类写出来，如果以上有什么细节出现了问题希望各位大佬帮助更改，虚心学习.本人随心情更新博客不进任何实验室,不喜欢被催着的感觉,喜欢自由在,也同样希望可以和大佬一起讨论问题。

1. 用C++实现链表

    本文用到C++中的类模板,用类模板的好处就是方便建立任何类型的链表。但类模板这里有个坑就是无法分离编译，具体原因可以百度搜索类模板无法分离编译。最后废话不多说，直接上代码。

2. 代码

    linklist.h文件实现顺序表的声明和定义

#ifndef LINKLIST_H
#define LINKLIST_H
#include <iostream>
using namespace std;
template <typename T>
class Node {
public:
    /* 用于链表节点的定义 */
    T data; // 表示数据域
    Node<T> *next;  // 表示指针域，存储下一个节点的位置
};
template <typename T>
class LinkList : public Node<T>{
private:
    /* 用于链表的定义 */
    Node<T> *head; // 头节点
public:
    /* 成员函数的声明 */
    LinkList(); // 重写默认的构造函数
    bool Empty(); // 判断链表是否为空
    int GetLen(); // 获取链表的长度
    void insert(T elem); // 默认插入链表的开头
    bool insert(int idx, T elem); // 在链表的指定位置插入元素
    void remove(T &elem); // 默认删除链表的第一个元素，并返回该元素
    bool remove(int idx, T &elem); // 删除并指定位置的元素
    bool index(int idx, T &elem); // 找出并返回指定位置的元素
    int index(bool (*compare(T, T)), T elem); // 找到并返回满足compare的元素
    void traverse(void (* print)(T &elem)); // 用于遍历整个链表
};


/* 用于实现成员函数的定义 */
template <typename T>
inline LinkList<T>::LinkList() {
    this -> head = (Node<T> *)malloc(sizeof(Node<T>));
    if (!this -> head) {
        cerr << "Error allocating memory!" << endl;
    }
    this -> head -> next = nullptr;
}

template <typename T>
inline bool LinkList<T>::Empty() {
    if (this -> head == nullptr) {
        return true;
    }
    return false;
} 

template <typename T>
int LinkList<T>::GetLen() {
    Node<T> *tmp = this -> head -> next;
    int counter = 0;
    while (tmp) {
        counter++;
        tmp = tmp -> next;
    }
    return counter;
}

template <typename T>
inline void LinkList<T>::insert(T elem) {
    Node<T> *newnode = (Node<T> *)malloc(sizeof(Node<T>));
    newnode -> data = elem;
    newnode -> next = this -> head -> next;
    this -> head -> next = newnode;
}

template <typename T>
bool LinkList<T>::insert(int idx, T elem) {
    if (idx < 1 || idx > this -> GetLen() + 1) {
        cerr << "subscript wrong!" << endl;
        return false;
    }
    int counter = 0;
    Node<T> *newnode = this -> head, *tmp = (Node<T> *)malloc(sizeof(Node<T>));
    while (counter < idx - 1 && newnode -> next != nullptr) {
        counter++;
        newnode = newnode -> next;
    }
    tmp -> data = elem;
    tmp -> next = newnode -> next;
    newnode -> next = tmp;
    return true;
}

template <typename T>
void LinkList<T>::remove(T &elem) {
    Node<T> *tmp = this -> head -> next;
    this -> head -> next = tmp -> next;
    elem = tmp -> data;
    free(tmp);
}

template <typename T>
bool LinkList<T>::remove(int idx, T &elem) {
    if (idx < 1 || idx > this -> GetLen()) {
        cerr << "subscript wrong!" << endl;
        return false;
    }
    Node<T> *newnode = this -> head, *tmp;
    int counter = 0;
    while (counter < idx - 1 && newnode -> next != nullptr) {
        newnode = newnode -> next;
        counter++;
    }
    tmp = newnode -> next;
    elem = tmp -> data;
    newnode -> next = tmp -> next;
    free(tmp);
    return true;
}

template <typename T>
bool LinkList<T>::index(int idx, T &elem) {
    if (idx < 1 || idx > this -> GetLen()) {
        cerr << "subscript wrong!" << endl;
        return false;
    }
    Node<T> *newnode = this -> head -> next;
    int counter = 1;
    while (counter < idx) {
        counter++;
        newnode = newnode -> next;
    }
    elem = newnode -> data;
    return true;
}

template <typename T>
int LinkList<T>::index(bool (*compare(T, T)), T elem) {
    Node<T> *newnode = this -> head;
    int counter = 0;
    while (newnode -> next != nullptr) {
        newnode = newnode -> next;
        counter++;
        if (compare(newnode -> data, elem)) {
            return counter;
        }
    }
    return -1;
}
template <typename T>
void LinkList<T>::traverse(void (* print)(T &elem)) {
    Node<T> *tmp = this -> head -> next;
    while (tmp) {
        print(tmp -> data);
        tmp = tmp -> next;
    }
    cout << endl;
}

/* 用于定义非成员函数 */
template <typename T>
void show(LinkList<T> &L) {
    cout << "length : " << L.GetLen() << endl;
}

template <typename T>
void print(T &elem) {
    cout << elem << " ";
}
#endif

    main.cpp文件测试顺序表

#include <iostream>
#include "linklist.h"
using namespace std;
int main(int argc, char const *argv[])
{
    /* code */
    LinkList<int> L;
    L.insert(1);
    L.insert(2);
    L.insert(3);
    L.insert(4);
    L.insert(1,5);
    L.traverse(print);
    int tmp;
    L.remove(5,tmp);
    L.traverse(print);
    L.index(5, tmp);
    cout << tmp << endl;
    show(L);
    return 0;
}

    喜欢的话，就点个关注吧。