数据结构-链表实现（单链表，双链表，类实现）

桃扇骨 2022-05-28 12:54 346阅读 0赞

1.单链表

1）单的意思就是说只有一个方向，所以只能往一个方向增加节点。

2）也因为单（身）所以处理起来很寂寞，注意几点吧：

A）创建和遍历需要一个头节点（不含数据），和一个尾节点。

B）删除和插入都要在前一节点（比如要删除第二个节点，需要在第一个节点操作，又如在第三个节点前插入一个节点，得在第二个节点操作），所以后面类实现的成员函数一般都是找目标的前一节点。

类实现（创建，析构，删除，插入，输出）

#

#

#

  1. /*by szu_crayon 2018/3/7*/
  2. #include<iostream>
  3. using namespace std;
  4. class MyList
  5. {
  6. private:
  7.     struct Node{
  8.         int Data;
  9.         Node* Next;
  10.     };
  11.     Node* Head;  //头节点
  12.     Node* Tail;  //尾节点
  13. public:
  14.     MyList()    //创建头节点
  15.     {
  16.         Head = new Node;
  17.         Head->Data = NULL; Head->Next = NULL;
  18.         Tail = Head;
  19.     }
  20.     ~MyList()    //释放链表空间
  21.     {
  22.         Node* Temp;
  23.         while (Head)
  24.         {
  25.             Temp = Head;
  26.             Head = Head->Next;
  27.             delete Temp;
  28.         }
  29.     }
  30.     void AddNode(int num)      //从尾部增加节点
  31.     {
  32.         Node *NewNode = new Node;
  33.         NewNode->Data = num; NewNode->Next = NULL;    //增加节点的时候新节点后面没有元素所以next指向空
  34.         Tail->Next = NewNode; Tail = NewNode;      //Tail连接新节点，然后新节点作为新的尾节点
  35.     }
  36.     int ListSize()           //返回链表元素个数
  37.     {
  38.         int cnt = 0;
  39.         Node* Temp = Head;
  40.         while (Temp->Next != NULL)
  41.         {
  42.             Temp = Temp->Next;
  43.             cnt++;
  44.         }
  45.         return cnt;
  46.     }
  47.     Node* FindNode(int Index)         //返回所查找下标的前一个节点
  48.     {
  49.         Node* Temp = Head;
  50.         int cnt = 0;
  51.         while (Temp->Next != NULL)
  52.         {
  53.             cnt++;
  54.             if (cnt == Index)
  55.                 return Temp;
  56.             Temp = Temp->Next;
  57.         }
  58.         return NULL;     //no find
  59.     }
  60.     Node* FindNum(int num)     //返回查找数字所在节点的前一节点
  61.     {
  62.         Node* Temp = Head;
  63.         while (Temp->Next != NULL)
  64.         {
  65.             if (Temp->Next->Data == num)
  66.                 return Temp;
  67.             Temp = Temp->Next;
  68.         }
  69.         return NULL;     //no find
  70.     }
  71.     int DeleteNode(Node* FindedNode)    //删除指定位置的节点
  72.     {
  73.         if (FindedNode)
  74.         {
  75.             Node* Temp = FindedNode->Next;
  76.             FindedNode->Next = Temp->Next;
  77.             delete Temp;
  78.             return 1;
  79.         }
  80.         return 0;
  81.     } 
  82.     void InsertNode(int Index,int num)          //指定位置插入一个数据为num的节点
  83.     {
  84.         if (Index - 1 == ListSize())    //如果指定位置刚好比链表元素多1，那么相当于在尾部增加节点
  85.         {
  86.             AddNode(num);
  87.             PrintList();
  88.         }
  89.         else
  90.         {
  91.             Node *FindedNode = FindNode(Index);    //FIndedNode为插入位置的前一位
  92.             if (FindedNode)
  93.             {
  94.                 Node *NewNode = new Node;
  95.                 NewNode->Data = num; NewNode->Next = FindedNode->Next;
  96.                 FindedNode->Next = NewNode;
  97.                 PrintList();
  98.             }
  99.             else
  100.                 cout << "error" << endl;
  101.         }
  102.     }
  103.     void PrintList()     //输出链表
  104.     {
  105.         int cnt = 1;
  106.         Node *Temp = Head->Next;
  107.         while (Temp)
  108.         {
  109.             if (cnt == 1)
  110.                 cout << Temp->Data;
  111.             else
  112.                 cout << " " << Temp->Data;
  113.             cnt++;
  114.             Temp = Temp->Next;
  115.         }
  116.         //cout<<" " << endl;
  117.         cout << endl;
  118.     }
  119. };

2.双向链表

1）在单向链表的基础上拥有前驱指针（指向前一个节点）。

2）友好，因为有指向前一节点的指针，说明插入删除只需查找当前需要插入或者删除的节点！

3）还能逆序输出，两端插入！

4）因为我懒，所以功能实现没有前插和后插，其实可以把头节点删了换成一个头指针（就是指向有数据的第一个节点），这样就能实现前插后插，交给你们啦~

5）一个彩蛋，数据结构和STL相关，比如list就是以双链表为基础，所以下篇blog介绍List。

类实现（创建，析构，删除，插入，输出）

  1. #include<iostream>
  2. using namespace std;
  3. struct Node
  4. {
  5.     int Data;
  6.     Node* Prior;
  7.     Node* Next;
  8. };
  9. class Double_direct_List
  10. {
  11. private:
  13.     Node * Head;
  14.     Node * Tail;
  15.     int List_Size;
  16. public:
  17.     Double_direct_List();      //创建
  18.     void AddNode(int Elem);     //尾插节点
  19.     Node* Find_Elem(int Being_Find_Elem);   //查找含有指定数据的节点
  20.     Node* Find_Index_Node(int Index);      //查找Index位置的节点
  21.     int Delete_Node(Node* Finded_Node);     //删除节点
  22.     int Insert_Node(int insert_index,int insert_Elem);    //插入含有数据insert_elem的节点
  23.     int Get_ListSize();             //返回链表元素个数
  24.     void Head_To_Tail_OutPut();   //顺序输出
  25.     void Tail_To_Head_OutPut();   //逆序输出
  26. };
  27. Double_direct_List::Double_direct_List() :List_Size(0)
  28. {
  29.     Head = new Node;
  30.     Head->Next = NULL; Head->Prior = NULL;
  31.     Tail = Head;
  32. }
  33. void Double_direct_List::AddNode(int Elem)
  34. {
  35.     Node* NewNode = new Node;
  36.     NewNode->Data = Elem;
  37.     NewNode->Next = NULL;
  38.     NewNode->Prior = Tail;    //比单向链表多了这一步，就是前驱指针要指向前一节点
  39.     Tail->Next = NewNode;
  40.     Tail = NewNode;
  41.     List_Size++;
  42. }
  43. Node* Double_direct_List::Find_Elem(int Being_Find_Elem)
  44. {
  45.     Node* Index = Head->Next;
  46.     while (Index)
  47.     {
  48.         if (Index->Data == Being_Find_Elem)
  49.             return Index;
  50.         Index = Index->Next;
  51.     }
  52.     return NULL;
  53. }
  54. Node* Double_direct_List::Find_Index_Node(int Index)
  55. {
  56.     Node* TempIndex = Head->Next;
  57.     int cnt = 0;
  58.     while (TempIndex)
  59.     {
  60.         if (++cnt == Index)
  61.             return TempIndex;
  62.         TempIndex = TempIndex->Next;
  63.     }
  64.     return NULL;
  65. }
  66. int Double_direct_List::Delete_Node(Node* Finded_Node)
  67. {
  68.     if (Finded_Node == NULL)
  69.         return 0;
  70.     Node* Prior_Node = Finded_Node->Prior;
  71.     Node* Next_Node = Finded_Node->Next;
  72.     Prior_Node->Next = Next_Node;
  73.     if(Next_Node)
  74.         Next_Node->Prior = Prior_Node;
  75.     List_Size--;
  76.     delete Finded_Node;
  77.     return 1;
  78. }
  79. int Double_direct_List::Insert_Node(int insert_index, int insert_Elem)
  80. {
  81.     if (insert_index == List_Size+1)
  82.         AddNode(insert_Elem);
  83.     else
  84.     {
  85.         Node* Finded_Node = Find_Index_Node(insert_index);
  86.         if (Finded_Node == NULL)
  87.             return 0;
  88.         else
  89.         {
  90.             Node* Prior_Node = Finded_Node->Prior;
  91.             Node* NewNode = new Node;
  92.             NewNode->Data = insert_Elem;
  93.             Prior_Node->Next = NewNode;
  94.             Finded_Node->Prior = NewNode;
  95.             NewNode->Next = Finded_Node;
  96.             NewNode->Prior = Prior_Node;
  97.             List_Size++;
  98.         }
  99.     }
  100.     return 1;
  101. }
  102. int Double_direct_List::Get_ListSize()
  103. {
  104.     return List_Size;
  105. }
  106. void Double_direct_List::Head_To_Tail_OutPut()
  107. {
  108.     int i=0;
  109.     Node* TempHead = Head->Next;
  110.     while (TempHead)
  111.     {
  112.         if (++i == 1)
  113.             cout << TempHead->Data;
  114.         else
  115.             cout << " " << TempHead->Data;
  116.         TempHead = TempHead->Next;
  117.     }
  118.     cout << endl;
  119. }
  120. void Double_direct_List::Tail_To_Head_OutPut()
  121. {
  122.     Node* TempTail = Tail;
  123.     while (TempTail->Prior)
  124.     {
  125.         cout << TempTail->Data << " ";
  126.         TempTail = TempTail->Prior;
  127.     }
  128.     cout << endl;
  129. }

3.具体题目

(小傲娇放在最后没人看！)一道题：约瑟夫环（单链表实现），看完双链表可以用双链表实现下，附上题目及我代码的链接：点击打开链接

1.单链表的删除

1.问题描述

给出初始数据，实现单链表的定义、创建、查找和删除。假设单链表中的结点计数从1开始。

2.算法

单链表结点的存储结构包含两部分：数据、下一结点指针。

单链表的创建：依次为输入的数据分配结点，并按序链接起来。

单链表的查找：给出位置i，若第i个结点存在(1<=i<=表中结点数L)，返回结点地址；否则，返回NULL。

单链表的删除：给出位置i，删除第i个结点(1<=i<=L)。

要求定义删除函数：int DeleteList(Node *H,int i) //删除第i个结点成功，返回1；第i个结点不存在，删除不成功，返回0。其中Node是链表结点结构体名，H是链表头指针。

每个样本分2行：

第一行：第一个数字n表示样本数目，其后跟n个样本

第二行：删除测试次数m 后跟m个删除位置

输出

第一行：单链表创建后，输出链表中元素个数和单链表中的全部数据。

第二行至第m+1行：若删除指定位置的数据成功，输出链表中元素个数和单链表中的全部数据；若删除不成功，输出error。

样例输入

5 2 4 3 5 7

3 0 2 4

样例输出

5 2 4 3 5 7

error

4 2 3 5 7

3 2 3 5

应用上述类实现代码
单链表实现
  1. int main()
  2. {
  3.     int n, num;
  4.     int t, Index;
  5.     MyList OneList;
  6.     cin >> n;
  7.     for (int i = 1; i <= n; i++)
  8.     {
  9.         cin >> num;
  10.         OneList.AddNode(num);
  11.     }
  12.     cout << OneList.ListSize();
  13.     OneList.PrintList();
  14.     cin >> t;
  15.     while (t--)
  16.     {
  17.         cin >> Index;
  18.         if (OneList.DeleteNode(OneList.FindNode(Index)) )
  19.         {
  20.             cout << OneList.ListSize();
  21.             OneList.PrintList();
  22.         }
  23.         else
  24.             cout << "error" << endl;
  25.     }
  26.     return 0;
  27. }
双向链表实现
  1. int main()
  2. {
  3.     int size, deltime, delnum, num;
  4.     Double_direct_List MyList;
  5.     cin >> size;
  6.     for (int i = 1; i <= size; i++)
  7.     {
  8.         cin >> num;
  9.         MyList.AddNode(num);
  10.     }
  11.     cout << MyList.Get_ListSize();
  12.     MyList.Head_To_Tail_OutPut();
  13.     cin >> deltime;
  14.     while(deltime--)
  15.     {
  16.         cin >> delnum;
  17.         if (MyList.Delete_Node(MyList.Find_Index_Node(delnum) ) )
  18.         {
  19.             cout << MyList.Get_ListSize();
  20.             MyList.Head_To_Tail_OutPut();
  21.         }
  22.         else
  23.             cout << "error" << endl;
  24.     }
  25.     return 0;
  26. }

2.单链表查找

1.问题描述

给出初始数据，实现单链表的定义、创建、查找。假设单链表中的结点计数从1开始。

2.算法

单链表结点的存储结构包含两部分：数据、下一结点指针。

单链表的创建：依次为输入的数据分配结点，并按序链接起来。

单链表结点个数L(也称单链表表长L)：从头至尾遍历单链表，对结点进行计数。

单链表的查找：给出位置i,若第i个结点存在(1<=i<=L)，返回结点地址；否则，返回NULL。

要求查找子函数定义为：Node *Find(Node *H,int i)

//若i的值在1…单链表长L之间，返回第i个结点的地址；否则返回空指针NULL。其中Node为链表结点结构体名，H为链表头指针。

输入

每个样本分2行：

第一行：第一个数字n表示样本数目，其后跟n个样本。

第二行：查找测试次数m 后跟m个待查找的位置。

输出

第一行：单链表创建后，输出链表中元素个数和单链表中的全部数据。

第二行到第n+1行，对每个查找位置，若结点存在，输出结点数据；否则输出error。

样例输入

6 1 2 3 4 5 64 0 2 10 6

样例输出

6 1 2 3 4 5 6

error

2

error

6

应用上述类实现代码
单向链表实现
  1. int main()
  2. {
  3.     MyList OneList;
  4.     int n, num;
  5.     int t, Index;
  6.     cin >> n;
  7.     for (int i = 1; i <= n; i++)
  8.     {
  9.         cin >> num;
  10.         OneList.AddNode(num);
  11.     }
  12.     cout << OneList.ListSize();
  13.     OneList.PrintList();
  14.     cin >> t;
  15.     while (t--)
  16.     {
  17.         cin >> Index;
  18.         if (OneList.FindNode(Index))
  19.             cout << OneList.FindNode(Index)->Next->Data<< endl;
  20.         else
  21.             cout << "error" << endl;
  22.     }
  23.     return 0;
  24. }
双向链表实现
  1. int main()
  2. {
  3.     int size, TxTtime, testindex, num;
  4.     Double_direct_List MyList;
  5.     cin >> size;
  6.     for (int i = 1; i <= size; i++)
  7.     {
  8.         cin >> num;
  9.         MyList.AddNode(num);
  10.     }
  11.     cout << MyList.Get_ListSize()<<" ";
  12.     MyList.Head_To_Tail_OutPut();
  13.     cin >> TxTtime;
  14.     while (TxTtime--)
  15.     {
  16.         cin >> testindex;
  17.         Node* FindedNode = MyList.Find_Index_Node(testindex);
  18.         if (FindedNode)
  19.             cout << FindedNode->Data << endl;
  20.         else
  21.             cout << "error" << endl;
  22.     }
  23.     return 0;
  24. }

3.单链表插入

1.问题描述

单链表初始为空，给定插入位置和数据，插入结点实现单链表的创建。假设单链表中的结点计数从1开始。

2.算法

单链表结点的存储结构包含两部分：数据、下一结点指针

单链表的查找：给出位置i，若第i个结点存在(1<=i<=表中结点数L)，返回结点地址；否则，返回NULL。

单链表的插入：给出位置i和数据e，在单链表第i(1<=i<=L+1)个结点位置插入新结点，数据为e。

输入

测试次数n

每行一组测试数据,格式如下：

位置i 数据e

输出

对每组测试数据，调用插入函数在位置i插入数据e，若插入成功，输出当前链表中的数据；若插入不成功，输出error。

样例输入

80 10

1 10

2 20

3 30

1 40

6 60

5 50

9 100

样例输出

error

10

10 20

10 20 30

40 10 20 30

error

40 10 20 30 50

error

应用上述类实现代码
单向链表实现
  1. int main()
  2. {
  3.     MyList OneList;
  4.     int t, Index, num;
  5.     cin >> t;
  6.     while (t--)
  7.     {
  8.         cin >> Index >> num;
  9.         OneList.InsertNode(Index, num);
  10.     }
  11.     return 0;
  12. }
双向链表实现
  1. int main()
  2. {
  3.     Double_direct_List MyList;
  4.     int insert_time, insert_data, insert_index;
  5.     cin >> insert_time;
  6.     while (insert_time--)
  7.     {
  8.         cin >> insert_index >> insert_data;
  9.         if (MyList.Insert_Node(insert_index, insert_data))
  10.         {
  11.             MyList.Head_To_Tail_OutPut();
  12.             MyList.Tail_To_Head_OutPut();
  13.         }
  14.         else
  15.             cout << "error" << endl;
  16.     }
  18.     return 0;
  19. }

还有一道题：约瑟夫环，看完双链表可以用双链表实现下，附上题目及我代码的链接：点击打开链接

感觉没有注释是不是和没缩减对齐一样是渣男~

发表评论

表情：
评论列表 （有 0 条评论，346人围观）

还没有评论，来说两句吧...

相关阅读