我们在上一章节中讲解到了C++vector容器以及vector容器的各种方法实现原理，我们在这一章节讲解一下链表以及链表的各种方法操作原理。
数组为我们在编程的时候提供了很大的便利，但是有时候我们定义的数组不能满足我们的需求，我们需要一个可变数组来存储我们的数据，我们存储多大数据，就为我们分配多少内存空间，这时候链表就显得尤为重要了。
链表的内部结构其实很简单，就是定义一个结构体，该结构体内不仅存储了我们需要的数据，而且存储了下一个结构的指针，通过指针，让各个元素连接起来，这就是链表。这里给出一张图帮助大家理解
链表实现源码
这里给出链表的各种方法实现源码，源码中注释写得很清楚，相信大家能够理解：
#include <iostream> #include<windows.h> using namespace std; #define success 1 #define error 0 template <class T_ELE> class LinkedList{ public: LinkedList(); ~LinkedList(); bool IsEmpty(); //判断链表是否为空 DWORD clear(); //清空链表 DWORD GetElement(IN DWORD dwIndex,OUT T_ELE& Element); //根据索引获取元素 DWORD GetElementIndex(IN T_ELE&Element); //根据内容获取索引 DWORD Insert(IN T_ELE& Element); //在链表尾部新增元素 DWORD Insert(IN DWORD dwIndex,IN T_ELE& Element); //在指定位置插入元素 DWORD Delete(IN DWORD dwIndex); //根据索引删除元素 DWORD GetSize(); //获取链表中元素的数量 private: typedef struct _NODE{ T_ELE Data; //链表数据 _NODE* pNext; //下一个数据指针 }NODE,*PNODE; private: PNODE m_pList; //链表头指针 DWORD m_dwLength; //当前链表元素数量 }; //无参构造函数，初始化成员 template <class T_ELE> LinkedList<T_ELE>::LinkedList() :m_pList(NULL),m_dwLength(0){ cout<<"构造函数完成。"<<endl; } //析构函数 template <class T_ELE> LinkedList<T_ELE>::~LinkedList(){ clear(); cout<<"析构函数完成。"<<endl; } //判断链表是否为空 template <class T_ELE> bool LinkedList<T_ELE>::IsEmpty(){ if((m_dwLength = 0 || m_dwLength) = 0){ cout<<"链表为空！"<<endl; return error; }else{ cout<<"链表不为空，将继续执行。"<<endl; return success; } } //链表尾部新增节点 template <class T_ELE> DWORD LinkedList<T_ELE>::Insert(IN T_ELE& Element){ PNODE pNewNode = new NODE; memset(pNewNode,0,sizeof(NODE)); memcpy(pNewNode,&Element,sizeof(T_ELE)); pNewNode->pNext = 0; //判断列表是否为空，如果为空，则从0新增元素 PNODE ptemp = m_pList; if(IsEmpty()){ m_pList = pNewNode; m_dwLength++; return success; }else{ for(int i = 0;i < m_dwLength-1;i++){ ptemp = ptemp->pNext; if(ptemp = NULL){ cout<<"检测本结构下一个指针为0"<<endl; } } } ptemp->pNext = pNewNode; m_dwLength++; cout<<"表尾新增节点成功。"<<endl; } //新增节点到指定位置 template <class T_ELE> DWORD LinkedList<T_ELE>::Insert(IN DWORD dwIndex,IN T_ELE& Element){ PNODE pNewNode = new NODE; memset(pNewNode,0,sizeof(NODE)); memcpy(pNewNode,Element,sizeof(T_ELE)); pNewNode->pNext = 0; //判断链表是否为空,如果指针为空，并且Index为0，将在0的位置新增 if(IsEmpty){ m_pList = pNewNode; m_dwLength++; return success; cout<<"在索引值为0的位置新增元素成功。"<<endl; } //判断索引值是否有效 if(dwIndex < 0 || dwIndex>m_dwLength){ cout<<"索引值无效！"<<endl; return error; } //如果索引值为0，则将链表头指针指向new的内存，并且将pNext指向原来索引值为0的元素 pNewNode->m_List; m_pList = pNewNode; m_dwLength++; return success; //如果索引值为表尾 if(dwIndex = m_dwLength){ Insert(Element); return success; } //如果索引在链表中 PNODE ptemp = m_pList; for(int i = 0;i < dwIndex-1;i++){ ptemp = ptemp->pNext; } pNewNode->pNext = ptemp->pNext; ptemp->pNext = pNewNode; cout<<"在"<<dwIndex<<"的位置新增元素成功。"<<endl; } //根据索引删除元素 template <class T_ELE> DWORD LinkedList<T_ELE>::Delete(IN DWORD dwIndex){ //如果索引为0 m_pList = m_pList->pNext; delete m_pList; m_dwLength--; cout<<"删除索引为0的元素已删除。"<<endl; //如果索引不为0 //判断索引是否有效 if(dwIndex<0 || dwIndex>m_dwLength){ cout<<"索引"<<dwIndex<<"无效！"<<endl; return error; } //如果索引为链表尾部 if(dwIndex = m_dwLength){ PNODE ptemp; for(int i = 0;i<dwIndex - 1;i++){ ptemp = ptemp->pNext; } delete ptemp->pNext; ptemp->pNext = 0; cout<<"索引"<<dwIndex<<"元素已删除。"<<endl; } //如果索引为链表中间位置 PNODE ptemp1= m_pList; for(int i = 0;i<dwIndex-1;i++){ ptemp1 = ptemp1->pNext; } PNODE ptemp2 = ptemp1->pNext; ptemp1->pNext = ptemp2->pNext; delete ptemp2; m_dwLength--; cout<<"索引"<<dwIndex<<"的元素已删除。"<<endl; return success; } //获取链表中元素数量 template <class T_ELE> DWORD LinkedList<T_ELE>::GetSize(){ cout<<"当前链表元素个数为"<<m_dwLength<<endl; return m_dwLength; } //清除链表元素 template <class T_ELE> DWORD LinkedList<T_ELE>::clear(){ PNODE ptemp1 = m_pList; PNODE ptemp2 = NULL; for(int i = 0;i < m_dwLength;i++){ ptemp2 = ptemp1->pNext; delete ptemp1; } } //测试函数 void Test(){ LinkedList<int> v1; int a=5; v1.Insert(a); } int main(){ Test(); return 0; }
