刺激战场
六合彩
贵宾厅
  • 1312阅读
  • 1回复

链表学习笔记 [复制链接]

上一主题 下一主题
离线啊冲
 

只看楼主 倒序阅读 使用道具 楼主  发表于: 2016-02-04



自己整理的链表简单操作,修改成了模板,记录一下,方便复习


单链表:


[cpp] view plain copy
  1. #pragma once  
  2. #include <string.h>  
  3.   
  4.   
  5. template <class TYPE>  
  6. class CMyList  
  7. {  
  8. public:  
  9. ////////////////////////////////////////////////////////////////////  
  10.     typedef struct _NODE  
  11.     {  
  12.         TYPE nData;  
  13.         _NODE* pNext;  
  14.   
  15.     }NODE, *PNODE;  
  16. ////////////////////////////////////////////////////////////////////  
  17.     CMyList()  
  18.     {  
  19.         memset(&m_stcHead, 0, sizeof(NODE));  
  20.         m_nCount = 0;  
  21.     }  
  22.     ~CMyList(){ Clear(); };  
  23. public:  
  24.   
  25.     // 向尾部添加一个元素  
  26.     void push_back(TYPE nData)  
  27.     {  
  28.         // 1.获取头结点地址  
  29.         NODE* pNew = &m_stcHead;  
  30.         // 2.从头结点开始遍历每个节点找到为空的pNext  
  31.         while (pNew->pNext)  
  32.         {  
  33.             pNew = pNew->pNext;  
  34.         }  
  35.         // 3.创建一个新结点  
  36.         pNew->pNext = new NODE;  
  37.         memset(pNew->pNext, 0, sizeof(NODE));  
  38.         pNew->pNext->nData = nData;  
  39.         // 将新结点的pNext指向空  
  40.         pNew->pNext->pNext = nullptr;  
  41.         // 4.结点数量加1;  
  42.         m_nCount++;  
  43.     }  
  44.   
  45.     // 向nIndex插入一个元素  
  46.     void Insert(int nIndex, TYPE nData)  
  47.     {  
  48.         // 1.先获取头结点的地址  
  49.         NODE* pNew = &m_stcHead;  
  50.         // 2.从头结点开始遍历找到nIndex,记录pNew结点  
  51.         int nCurrentPos = 0;  
  52.         while (pNew->pNext)  
  53.         {  
  54.             if (nCurrentPos == nIndex)  
  55.                 break;  
  56.             pNew = pNew->pNext;  
  57.             nCurrentPos++;  
  58.         }  
  59.         // 3.保存当前结点的下一个结点的地址  
  60.         NODE* pOld = pNew->pNext;  
  61.         // 4.插入新的结点  
  62.         pNew->pNext = new NODE;  
  63.         memset(pNew->pNext, 0, sizeof(NODE));  
  64.         pNew->pNext->nData = nData;  
  65.         // 5.插入结点的pNext指向刚刚保存的节点的地址  
  66.         pNew->pNext->pNext = pOld;  
  67.   
  68.         m_nCount++; //增加元素  
  69.     }  
  70.   
  71.     // 删除nIndex结点  
  72.     void Delete(int nIndex)  
  73.     {  
  74.         // 1.先获取头结点的地址  
  75.         NODE* pNew = &m_stcHead;  
  76.         // 2.从头结点开始遍历找到nIndex,记录pNew结点  
  77.         int nCurrentPos = 0;  
  78.         while (pNew->pNext)  
  79.         {  
  80.             if (nCurrentPos == nIndex)  
  81.                 break;  
  82.             pNew = pNew->pNext;  
  83.             nCurrentPos++;  
  84.         }  
  85.         NODE* pDel = pNew->pNext;  
  86.         pNew->pNext = pDel->pNext;  
  87.         delete pDel;  
  88.         pDel = nullptr;  
  89.         m_nCount--;  
  90.     }  
  91.   
  92.     // 清空链表  
  93.     void Clear()  
  94.     {  
  95.         if (m_nCount > 0)    //判断是否有结点  
  96.         {  
  97.             // 1.先获取头结点的地址  
  98.             NODE* pDel = &m_stcHead;  
  99.             NODE* pDelNext = pDel->pNext;  
  100.             while (pDelNext)  
  101.             {  
  102.                 pDel = pDelNext;  
  103.                 pDelNext = pDel->pNext;  
  104.                 delete pDel;  
  105.                 pDel = nullptr;  
  106.             }  
  107.             m_nCount = 0;  
  108.         }  
  109.     }  
  110.   
  111.   
  112. private:  
  113.     NODE m_stcHead;  
  114.     int  m_nCount;  
  115. };  



循环单链表:


[cpp] view plain copy
  1. #pragma once  
  2. #include <string.h>  
  3.   
  4.   
  5. template <class TYPE>  
  6. class CMyLoopList  
  7. {  
  8. public:  
  9. ////////////////////////////////////////////////////////////////////  
  10.     typedef struct _NODE  
  11.     {  
  12.         TYPE nData;  
  13.         _NODE* pNext;  
  14.   
  15.     }NODE, *PNODE;  
  16. ////////////////////////////////////////////////////////////////////  
  17.     CMyLoopList()  
  18.     {  
  19.         memset(&m_stcHead, 0, sizeof(NODE));  
  20.         m_stcHead.pNext = &m_stcHead;  
  21.         m_nCount = 0;  
  22.     }  
  23.     ~CMyLoopList(){ Clear(); };  
  24. public:  
  25.   
  26.     // 向尾部添加一个元素  
  27.     void push_back(TYPE nData)  
  28.     {  
  29.         // 1.获取头结点地址  
  30.         NODE* pNew = &m_stcHead;  
  31.         // 2.从头结点开始遍历每个节点找到为空的pNext  
  32.         while (pNew->pNext != &m_stcHead)  
  33.         {  
  34.             pNew = pNew->pNext;  
  35.         }  
  36.         // 3.创建一个新结点  
  37.         pNew->pNext = new NODE;  
  38.         memset(pNew->pNext, 0, sizeof(NODE));  
  39.         pNew->pNext->nData = nData;  
  40.         // 将新结点的pNext指向头结点  
  41.         pNew->pNext->pNext = &m_stcHead;  
  42.   
  43.         // 4.结点数量加1;  
  44.         m_nCount++;  
  45.     }  
  46.   
  47.     // 向nIndex插入一个元素  
  48.     void Insert(int nIndex, TYPE nData)  
  49.     {  
  50.         // 1.先获取头结点的地址  
  51.         NODE* pNew = &m_stcHead;  
  52.         // 2.从头结点开始遍历找到nIndex,记录pNew结点  
  53.         int nCurrentPos = 0;  
  54.         while (pNew->pNext != &m_stcHead)  
  55.         {  
  56.             if (nCurrentPos == nIndex)  
  57.                 break;  
  58.             pNew = pNew->pNext;  
  59.             nCurrentPos++;  
  60.         }  
  61.         // 3.保存当前结点的下一个结点的地址  
  62.         NODE* pOld = pNew->pNext;  
  63.         // 4.插入新的结点  
  64.         pNew->pNext = new NODE;  
  65.         memset(pNew->pNext, 0, sizeof(NODE));  
  66.         pNew->pNext->nData = nData;  
  67.         // 5.插入结点的pNext指向刚刚保存的节点的地址  
  68.         pNew->pNext->pNext = pOld;  
  69.   
  70.         m_nCount++; //增加元素  
  71.     }  
  72.   
  73.     // 删除nIndex结点  
  74.     void Delete(int nIndex)  
  75.     {  
  76.         // 1.先获取头结点的地址  
  77.         NODE* pNew = &m_stcHead;  
  78.         // 2.从头结点开始遍历找到nIndex,记录pNew结点  
  79.         int nCurrentPos = 0;  
  80.         while (pNew->pNext != &m_stcHead)  
  81.         {  
  82.             if (nCurrentPos == nIndex)  
  83.                 break;  
  84.             pNew = pNew->pNext;  
  85.             nCurrentPos++;  
  86.         }  
  87.         NODE* pDel = pNew->pNext;  
  88.         pNew->pNext = pDel->pNext;  
  89.         delete pDel;  
  90.         pDel = nullptr;  
  91.         m_nCount--;  
  92.     }  
  93.   
  94.     // 清空链表  
  95.     void Clear()  
  96.     {  
  97.         if (m_nCount > 0)    //判断是否有结点  
  98.         {  
  99.             // 1.先获取头结点的地址  
  100.             NODE* pDel = &m_stcHead;  
  101.             NODE* pDelNext = pDel->pNext;  
  102.             while (pDelNext && pDelNext != &m_stcHead)  
  103.             {  
  104.                 pDel = pDelNext;  
  105.                 pDelNext = pDel->pNext;  
  106.                 delete pDel;  
  107.                 pDel = nullptr;  
  108.             }  
  109.             m_nCount = 0;  
  110.         }  
  111.     }  
  112.   
  113. private:  
  114.     NODE m_stcHead;  
  115.     int  m_nCount;  
  116. };  

循环双链表:



[cpp] view plain copy
  1. #pragma once  
  2. #include <string.h>  
  3.   
  4.   
  5. template <class TYPE>  
  6. class CMyDoubleList  
  7. {  
  8. public:  
  9. ////////////////////////////////////////////////////////////////////  
  10.     typedef struct _NODE  
  11.     {  
  12.         TYPE nData;  
  13.         _NODE* pPrev;  
  14.         _NODE* pNext;  
  15.   
  16.     }NODE, *PNODE;  
  17. ////////////////////////////////////////////////////////////////////  
  18.   
  19.     CMyDoubleList()  
  20.     {  
  21.         //初始化  
  22.         memset(&m_stcHead, 0, sizeof(NODE));  
  23.         m_stcHead.pNext = &m_stcHead;  
  24.         m_nCount = 0;  
  25.     }  
  26.     ~CMyDoubleList(){};  
  27.   
  28. public:  
  29.     // 向尾部添加一个元素  
  30.     void push_back(TYPE nData)  
  31.     {  
  32.         // 1.获取头结点地址  
  33.         NODE* pNew = &m_stcHead;  
  34.         NODE* pPrev = pNew;  
  35.         // 2.从头结点开始遍历每个节点找到为空的pNext  
  36.         while (pNew->pNext != &m_stcHead)  
  37.         {  
  38.             pNew = pNew->pNext;  
  39.             pPrev = pNew;  
  40.         }  
  41.         // 3.创建一个新结点  
  42.         pNew->pNext = new NODE;  
  43.         memset(pNew->pNext, 0, sizeof(NODE));  
  44.         pNew->pNext->nData = nData;  
  45.         pNew->pNext->pPrev = pPrev;  
  46.         // 将新结点的pNext指向头结点  
  47.         pNew->pNext->pNext = &m_stcHead;  
  48.   
  49.         // 4.结点数量加1;  
  50.         m_nCount++;  
  51.     }  
  52.   
  53.     // 向nIndex插入一个元素  
  54.     void Insert(int nIndex, TYPE nData)  
  55.     {  
  56.         // 1.先获取头结点的地址  
  57.         NODE* pNew = &m_stcHead;  
  58.         NODE* pPrev = pNew;  
  59.         // 2.从头结点开始遍历找到nIndex,记录pNew结点  
  60.         int nCurrentPos = 0;  
  61.         while (pNew->pNext != &m_stcHead)  
  62.         {  
  63.             if (nCurrentPos == nIndex)  
  64.                 break;  
  65.             pNew = pNew->pNext;  
  66.             pPrev = pNew;  
  67.             nCurrentPos++;  
  68.         }  
  69.         // 3.保存当前结点的下一个结点的地址  
  70.         NODE* pOld = pNew->pNext;  
  71.         // 4.插入新的结点  
  72.         pNew->pNext = new NODE;  
  73.         memset(pNew->pNext, 0, sizeof(NODE));  
  74.         pNew->pNext->nData = nData;  
  75.         pNew->pNext->pPrev = pPrev;  
  76.         // 5.插入结点的pNext指向刚刚保存的节点的地址  
  77.         pNew->pNext->pNext = pOld;  
  78.   
  79.         m_nCount++; //增加元素  
  80.     }  
  81.   
  82.     // 删除nIndex结点  
  83.     void Delete(int nIndex)  
  84.     {  
  85.         // 1.先获取头结点的地址  
  86.         NODE* pNew = &m_stcHead;  
  87.         // 2.从头结点开始遍历找到nIndex,记录pNew结点  
  88.         int nCurrentPos = 0;  
  89.         while (pNew->pNext != &m_stcHead)  
  90.         {  
  91.             if (nCurrentPos == nIndex)  
  92.                 break;  
  93.             pNew = pNew->pNext;  
  94.             nCurrentPos++;  
  95.         }  
  96.         NODE* pDel = pNew->pNext;  
  97.         pNew->pNext = pDel->pNext;  
  98.         pNew->pNext->pPrev = pNew;  
  99.         delete pDel;  
  100.         pDel = nullptr;  
  101.         m_nCount--;  
  102.     }  
  103.   
  104.     // 清空链表  
  105.     void Clear()  
  106.     {  
  107.         if (m_nCount > 0)    //判断是否有结点  
  108.         {  
  109.             // 1.先获取头结点的地址  
  110.             NODE* pDel = &m_stcHead;  
  111.             NODE* pDelNext = pDel->pNext;  
  112.             while (pDelNext && pDelNext != &m_stcHead)  
  113.             {  
  114.                 pDel = pDelNext;  
  115.                 pDelNext = pDel->pNext;  
  116.                 delete pDel;  
  117.                 pDel = nullptr;  
  118.             }  
  119.             m_nCount = 0;  
  120.         }  
  121.     }  
  122.   
  123.   
  124. private:  
  125.     NODE m_stcHead;  
  126.     int  m_nCount;  
  127.   
  128. };  

善者 慈悲心常在 无怨无恨 以苦为乐
默认压缩密码www.hifyl.com
文件分享密码问题:http://www.hifyl.com/read-htm-tid-4444.html
离线v2680267313

只看该作者 沙发  发表于: 2016-04-30
用户被禁言,该主题自动屏蔽!
快速回复
限100 字节
批量上传需要先选择文件,再选择上传
 
上一个 下一个