---

 

注释：对于找工作真的是很好的教程，基本什么方面都讲的很细致，但是对于大多数人只有快进快进再快进~~

注释：基本链表信息自己百度，这里只是一个快速拾遗过程。

1.链表定义

1 typedef int DATA;//int的别名，为了便于管理2 3 //定义链表一个链节点4 typedef struct SNode5 {6     DATA data;//数据，可以是结构体和类等，4字节7     SNode *pNext;//指针，指向下一个节点，4字节8 };

2.插入一个节点

1 #include 
     
       2  3 using namespace std; 4  5 //#define DATA int 6 typedef int DATA;//int的别名，为了便于管理 7  8 //定义链表一个链节点 9 typedef struct SNode10 {11     DATA data;//数据，可以是结构体和类等，4字节12     SNode *pNext;//指针，指向下一个节点，4字节13 }; 14 SNode* g_pHead = NULL;//第一个链表是空链表15 //从头插入一个数据16 void AddHead(DATA data)17 {18     SNode* p = new SNode;//申请一个堆空间，8字节19     p->data  = data;20     p->pNext = g_pHead;21     g_pHead  = p;//把新插入的节点当做头22 }23 int main(int argc, char**argv[])24 {25     AddHead(1);26     AddHead(2);27     AddHead(3);28     cout<
      
       data<
       
        <
        
         pNext->data<
         
          <
          
           pNext->pNext->data<
          
         
        
       
      
     

3.从尾部插入一个节点

1 #include 
     
       2  3 using namespace std; 4  5 //#define DATA int 6 typedef int DATA;//int的别名，为了便于管理 7  8 //定义链表一个链节点 9 typedef struct SNode10 {11     DATA data;//数据，可以是结构体和类等，4字节12     SNode *pNext;//指针，指向下一个节点，4字节13 }; 14 SNode* g_pHead = NULL;//第一个链表是空链表15 //从尾插入一个数据16 void AddTail(DATA data)17 {18     SNode* p = g_pHead;//防止改变头结点的指针19     //建立新的节点20     SNode* p1 = new SNode;21     p1->data = data;22     p1->pNext = NULL;23     if(!p)//如果一开始就是空链表24     {25         g_pHead = p1;26         return;27     }28     while(p->pNext)//找到最尾部的节点29     {30         p = p->pNext;31     }32     p->pNext = p1;33 }34 int main(int argc, char**argv[])35 {36 /*     AddHead(1);37     AddHead(2);38     AddHead(3); */39     AddTail(11);40     AddTail(12);41     AddTail(13);42     while(g_pHead)43     {44         cout<
      
       data<
       
        pNext;46     }47     //cout<
        
         data<
         
          <
          
           pNext->data<
           
            <
            
             pNext->pNext->data<
            
           
          
         
        
       
      
     

4.修改节点数据

1 #include 
     
       2  3 using namespace std; 4  5 //#define DATA int 6 typedef int DATA;//int的别名，为了便于管理 7  8 //定义链表一个链节点 9 typedef struct SNode10 {11     DATA data;//数据，可以是结构体和类等，4字节12     SNode *pNext;//指针，指向下一个节点，4字节13 }; 14 SNode* g_pHead = NULL;//第一个链表是空链表15 //从尾插入一个数据16 void AddTail(DATA data)17 {18     SNode* p = g_pHead;//防止改变头结点的指针19     //建立新的节点20     SNode* p1 = new SNode;21     p1->data = data;22     p1->pNext = NULL;23     if(!p)//如果一开始就是空链表24     {25         g_pHead = p1;26         return;27     }28     while(p->pNext)//找到最尾部的节点29     {30         p = p->pNext;31     }32     p->pNext = p1;33 }34 void Modify(DATA data, DATA newData)35 {36     SNode* p = g_pHead;37     SNode* p1 = new SNode;38     if (!p)39     {40         p1->data = newData;41         p1->pNext = NULL;42         g_pHead = p1;43         return;44     }45     while(p)46     {47         if (p->data==data)48         {49             p->data = newData;50         }51         p = p->pNext; 52     }53 }54 int main(int argc, char**argv[])55 {56 /*     AddHead(1);57     AddHead(2);58     AddHead(3); */59     AddTail(11);60     AddTail(12);61     AddTail(13);62     Modify(13,16);63     while(g_pHead)64     {65         cout<
      
       data<
       
        pNext;67     }68     cout<<"hell2";69     return 0;70 }
       
      
     

5.查找和打印链表

1 #include 
     
       2  3 using namespace std; 4  5 //#define DATA int 6 typedef int DATA;//int的别名，为了便于管理 7  8 //定义链表一个链节点 9 typedef struct SNode10 {11     DATA data;//数据，可以是结构体和类等，4字节12     SNode *pNext;//指针，指向下一个节点，4字节13 }; 14 SNode* g_pHead = NULL;//第一个链表是空链表15 //从尾插入一个数据16 void AddTail(DATA data)17 {18     SNode* p = g_pHead;//防止改变头结点的指针19     //建立新的节点20     SNode* p1 = new SNode;21     p1->data = data;22     p1->pNext = NULL;23     if(!p)//如果一开始就是空链表24     {25         g_pHead = p1;26         return;27     }28     while(p->pNext)//找到最尾部的节点29     {30         p = p->pNext;31     }32     p->pNext = p1;33 }34 //查找某个数据35 bool Find(DATA data)36 {37     SNode* p = g_pHead;38     while(p)39     {40         if(p->data == data) return true;41         p = p->pNext;    42     }43     return false;44 }45 void print()46 {47     SNode* p = g_pHead;48     while(p)49     {50         cout<
      
       data<
       
        pNext;52     }53 }54 int main(int argc, char**argv[])55 {56 /*     AddHead(1);57     AddHead(2);58     AddHead(3); */59     AddTail(11);60     AddTail(12);61     AddTail(13);62     //Modify(13,16);63     print();64     cout<<"shifou : "<
       
      
     

6.删除链表节点

1 #include 
     
       2  3 using namespace std; 4  5 //#define DATA int 6 typedef int DATA;//int的别名，为了便于管理 7  8 //定义链表一个链节点 9 typedef struct SNode10 {11     DATA data;//数据，可以是结构体和类等，4字节12     SNode *pNext;//指针，指向下一个节点，4字节13 }; 14 SNode* g_pHead = NULL;//第一个链表是空链表15 //从尾插入一个数据16 void AddTail(DATA data)17 {18     SNode* p = g_pHead;//防止改变头结点的指针19     //建立新的节点20     SNode* p1 = new SNode;21     p1->data = data;22     p1->pNext = NULL;23     if(!p)//如果一开始就是空链表24     {25         g_pHead = p1;26         return;27     }28     while(p->pNext)//找到最尾部的节点29     {30         p = p->pNext;31     }32     p->pNext = p1;33 }34 //删除某个节点35 bool Delete(DATA data)36 {37     SNode* p = g_pHead;//当前节点38     SNode* p1 = NULL;//下一个节点39     if(!p) return false;//空链表直接返回40     if(p->data == data )//删除第一个节点41     {42         g_pHead = p->pNext;43         delete p;44         return true;45     }        46     while(p)//删除中间和结尾节点47     {48         if(p->data == data)49         {50             p1->pNext = p->pNext;51             delete p;52             return true;53         }54         p1 = p;55         p = p->pNext;56     }57     return false;58 }59 void print()60 {61     SNode* p = g_pHead;62     while(p)63     {64         cout<
      
       data<
       
        pNext;66     }67 }68 int main(int argc, char**argv[])69 {70 /*     AddHead(1);71     AddHead(2);72     AddHead(3); */73     AddTail(11);74     AddTail(12);75     AddTail(13);76     //Modify(13,16);77     Delete(13);78     print();79     cout<<"shifou : "<
       
      
     

7.排序链表

　　以后面试再看链表外排和内排：

1 #include 
     
       2  3 using namespace std; 4  5 //#define DATA int 6 typedef int DATA;//int的别名，为了便于管理 7 //定义一个结构体当做数据 8 /* typedef struct DATA 9 {10     int nNumb;11     char sName[20];12     float fMath;13 }; */14 //定义链表一个链节点15 typedef struct SNode16 {17     DATA data;//数据，可以是结构体和类等，4字节18     SNode *pNext;//指针，指向下一个节点，4字节19 }SNode; 20 SNode* g_pHead = NULL;//第一个链表是空链表21 //从尾插入一个数据22 void AddTail(DATA data)23 {24     SNode* p = g_pHead;//防止改变头结点的指针25     //建立新的节点26     SNode* p1 = new SNode;27     p1->data = data;28     p1->pNext = NULL;29     if(!p)//如果一开始就是空链表30     {31         g_pHead = p1;32         return;33     }34     while(p->pNext)//找到最尾部的节点35     {36         p = p->pNext;37     }38     p->pNext = p1;39 }40 //打印全部节点数据41 void print()42 {43     SNode* p = g_pHead;44     while(p)45     {46         cout<
      
       data<
       
        pNext;48     }49 }50 //交换数据的排序51 void sortByNum(bool reverse = true)52 {53     SNode* p = g_pHead;54     SNode* m = NULL;55     while(p)56     {57         m = p->pNext;58         while(m)59         {60             if(p->data > m->data && reverse)61             {62                 DATA midData;63                 midData = p->data;64                 p->data = m->data;65                 m->data = midData;66             }67             else if(p->data < m->data && !reverse)68             {69                 DATA midData;70                 midData = p->data;71                 p->data = m->data;72                 m->data = midData;73             }74             m = m->pNext;75         }76         p=p->pNext;77     }78 }79 int main(int argc, char*argv[])80 {81 /*     AddHead(1);82     AddHead(2);83     AddHead(3); */84     AddTail(11);85     AddTail(2);86     AddTail(13);87     AddTail(10);88     AddTail(14);89     AddTail(1);90     //Modify(13,16);91     //Delete(13);92     print();93     sortByNum(false);94     print();95     return 0;96 }
       
      
     

8.总链表（结构体版）

1 #include 
     
        2   3 using namespace std;  4   5 //#define DATA int  6 typedef int DATA;//int的别名，为了便于管理  7 //定义一个结构体当做数据  8 /* typedef struct DATA  9 { 10     int nNumb; 11     char sName[20]; 12     float fMath; 13 }; */ 14 //定义链表一个链节点 15 typedef struct SNode 16 { 17     DATA data;//数据，可以是结构体和类等，4字节 18     SNode *pNext;//指针，指向下一个节点，4字节 19 }SNode;  20 SNode* g_pHead = NULL;//第一个链表是空链表 21 //从尾插入一个数据 22 void AddTail(DATA data) 23 { 24     SNode* p = g_pHead;//防止改变头结点的指针 25     //建立新的节点 26     SNode* p1 = new SNode; 27     p1->data = data; 28     p1->pNext = NULL; 29     if(!p)//如果一开始就是空链表 30     { 31         g_pHead = p1; 32         return; 33     } 34     while(p->pNext)//找到最尾部的节点 35     { 36         p = p->pNext; 37     } 38     p->pNext = p1; 39 } 40 //从头插入一个数据 41 void AddHead(DATA data) 42 { 43     SNode* p = new SNode;//申请一个堆空间，8字节 44     p->data  = data; 45     p->pNext = g_pHead; 46     g_pHead  = p;//把新插入的节点当做头 47 } 48 //修改链表节点数据 49 void Modify(DATA data, DATA newData) 50 { 51     SNode* p = g_pHead; 52     SNode* p1 = new SNode; 53     if (!p) 54     { 55         p1->data = newData; 56         p1->pNext = NULL; 57         g_pHead = p1; 58         return; 59     } 60     while(p) 61     { 62         if (p->data==data) 63         { 64             p->data = newData; 65         } 66         p = p->pNext;  67     } 68 } 69 //查找某个数据 70 bool Find(DATA data) 71 { 72     SNode* p = g_pHead; 73     while(p) 74     { 75         if(p->data == data) return true; 76         p = p->pNext;     77     } 78     return false; 79 } 80 //删除某个节点 81 bool Delete(DATA data) 82 { 83     SNode* p = g_pHead;//当前节点 84     SNode* p1 = NULL;//下一个节点 85     if(!p) return false;//空链表直接返回 86     if(p->data == data )//删除第一个节点 87     { 88         g_pHead = p->pNext; 89         delete p; 90         return true; 91     }         92     while(p)//删除中间和结尾节点 93     { 94         if(p->data == data) 95         { 96             p1->pNext = p->pNext; 97             delete p; 98             return true; 99         }100         p1 = p;101         p = p->pNext;102     }103     return false;104 }105 //打印全部节点数据106 void print()107 {108     SNode* p = g_pHead;109     while(p)110     {111         cout<
      
       data<
       
        pNext;113     }114 }115 //交换数据的排序116 void sortByNum(bool reverse = true)117 {118     SNode* p = g_pHead;119     SNode* m = NULL;120     while(p)121     {122         m = p->pNext;123         while(m)124         {125             if(p->data > m->data && reverse)126             {127                 DATA midData;128                 midData = p->data;129                 p->data = m->data;130                 m->data = midData;131             }132             else if(p->data < m->data && !reverse)133             {134                 DATA midData;135                 midData = p->data;136                 p->data = m->data;137                 m->data = midData;138             }139             m = m->pNext;140         }141         p=p->pNext;142     }143 }144 int main(int argc, char*argv[])145 {146 /*     AddHead(1);147     AddHead(2);148     AddHead(3); */149     AddTail(11);150     AddTail(2);151     AddTail(13);152     AddTail(10);153     AddTail(14);154     AddTail(1);155     //Modify(13,16);156     //Delete(13);157     print();158     sortByNum(false);159     print();160     return 0;161 }
       
      
     

9.总链表（类版本）

1 #include 
     
        2   3 using namespace std;  4 /*  5 typedef struct DATA  6 {  7     int sNum;  8     char sName[20];  9 }DATA; 10 */ 11 typedef int DATA; 12 typedef struct SNode 13 { 14     DATA data; 15     SNode* pNext; 16 }SNode; 17 class CList 18 { 19 public: 20     CList(); 21     ~CList(); 22     CList(CList&p); 23     void AddTail(DATA data); 24     void AddHead(DATA data); 25     void Modify(DATA data, DATA newData); 26     bool Find(DATA data); 27     bool Delete(DATA data); 28     void print(); 29     void sortByNum(bool reverse = true); 30 private: 31     SNode* m_pHead; 32 }; 33  34 int main(int argc,char*argv[]) 35 { 36     CList list1, list2; 37     list1.AddHead(10); 38     list1.AddHead(6); 39     list1.AddHead(11); 40     list1.AddHead(8); 41     list1.AddHead(10); 42     list1.AddHead(1); 43     list1.print(); 44  45     list1.sortByNum(); 46     list1.print(); 47     list2 = list1; 48     list2.print(); 49     return 0; 50 } 51  52 CList::CList() 53 { 54     m_pHead = NULL;// 55 } 56  57 CList::~CList() 58 {
   //析构函数，C++自动清除堆空间数据 59 } 60 CList::CList(CList& p) 61 { 62     memcpy(this,&p,sizeof(p));//拷贝构造函数 63 } 64 //从尾插入一个数据 65 void CList::AddTail(DATA data) 66 { 67     SNode* p = m_pHead;//防止改变头结点的指针 68                        //建立新的节点 69     SNode* p1 = new SNode; 70     p1->data = data; 71     p1->pNext = NULL; 72     if (!p)//如果一开始就是空链表 73     { 74         m_pHead = p1; 75         return; 76     } 77     while (p->pNext)//找到最尾部的节点 78     { 79         p = p->pNext; 80     } 81     p->pNext = p1; 82 } 83 //从头插入一个数据 84 void CList::AddHead(DATA data) 85 { 86     SNode* p = new SNode;//申请一个堆空间，8字节 87     p->data = data; 88     p->pNext = m_pHead; 89     m_pHead = p;//把新插入的节点当做头 90 } 91 //修改链表节点数据 92 void CList::Modify(DATA data, DATA newData) 93 { 94     SNode* p = m_pHead; 95     SNode* p1 = new SNode; 96     if (!p) 97     { 98         p1->data = newData; 99         p1->pNext = NULL;100         m_pHead = p1;101         return;102     }103     while (p)104     {105         if (p->data == data)106         {107             p->data = newData;108         }109         p = p->pNext;110     }111 }112 //查找某个数据113 bool CList::Find(DATA data)114 {115     SNode* p = m_pHead;116     while (p)117     {118         if (p->data == data) return true;119         p = p->pNext;120     }121     return false;122 }123 //删除某个节点124 bool CList::Delete(DATA data)125 {126     SNode* p = m_pHead;//当前节点127     SNode* p1 = NULL;//下一个节点128     if (!p) return false;//空链表直接返回129     if (p->data == data)//删除第一个节点130     {131         m_pHead = p->pNext;132         delete p;133         return true;134     }135     while (p)//删除中间和结尾节点136     {137         if (p->data == data)138         {139             p1->pNext = p->pNext;140             delete p;141             return true;142         }143         p1 = p;144         p = p->pNext;145     }146     return false;147 }148 //打印全部节点数据149 void CList::print()150 {151     SNode* p = m_pHead;152     while (p)153     {154         cout << p->data << endl;155         p = p->pNext;156     }157 }158 //交换数据的排序159 void CList::sortByNum(bool reverse)160 {161     SNode* p = m_pHead;162     SNode* m = NULL;163     while (p)164     {165         m = p->pNext;166         while (m)167         {168             if (p->data > m->data && reverse)169             {170                 DATA midData;171                 midData = p->data;172                 p->data = m->data;173                 m->data = midData;174             }175             else if (p->data < m->data && !reverse)176             {177                 DATA midData;178                 midData = p->data;179                 p->data = m->data;180                 m->data = midData;181             }182             m = m->pNext;183         }184         p = p->pNext;185     }186 }
     

9.改进版