devbox
小桥流水78
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

“波吉向你发出学习邀请”，数据结构之单双向链表_建立一个非递减有序单链表(不少于5个元素结点),输出该链表中重复的元素以及重复次

作者：小桥流水78 | 2024-07-20 23:20:28

赞

踩

建立一个非递减有序单链表(不少于5个元素结点),输出该链表中重复的元素以及重复次

目录

序

嗨，这里是狐狸​

单链表​

单向链表的节点

 单向链表实验

实验内容：

实验说明 :

源代码 

运行截图：

双向链表​

双向链表的创建

双向链表实验

实验内容：

实验说明：

源代码

 总结​

序

青春的列车上，如果你要提前下车，请别推醒装睡的我

嗨，这里是狐狸

今天是周末，昨日一夜未眠，不知怎的失眠了，没事就爬起来谢谢博客吧，最近中年的焦虑慢慢蔓延上心头，浑身不舒服，或许坐在电脑屏幕前才能得到一丝宁静吧。今天来给大家分享的是数据结构的知识——单链表以及双向链表。

单链表

         单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单向链表的节点

       如下代码所示，双向链表的节点包含两个指向关系和一个数据空间，两个指向分别连接该节点的上一个和下一个节点，数据类型可以是一个结构体类型，也可以是其他类型。

  1. typedef struct node
  2. {
  3.   int data;
  4.   struct node *pre;
  5.   struct node *next;
  6. }Node;

 单向链表实验

实验内容：

1．随机产生或键盘输入一组元素（不少于10个元素），建立一个带头结点的单链表。
2．把单链表中的元素逆置（不允许申请新的结点空间）。
3．删除单链表中所有的偶数元素结点。
4．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，利用该函数建立一个
       非递减有序单链表。
5．利用算法4建立两个非递减有序单链表，然后合并成一个非递增链表。
6．把算法1建立的链表分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量
       利用已有存储空间）。
7．在主函数中设计一个简单菜单，调用上述算法。

实验说明 :

1．结点类型定义

  1.    typedef  int  ElemType； // 元素类型 
  2.    typedef  struct  LNode 
  3.       {
  4. ElemType  data ; 
  5.        struct  LNode * next ; 
  6.       } LNode,  *pLinkList ;

2．为了简单，采用带头结点的单链表。

源代码 

  1. #include <iostream>
  2. #include <time.h>
  3. #include <iomanip>
  4. #include <stdlib.h>
  5. using namespace std;
  6. typedef int ElemType;
  7.  
  8. typedef struct LNode
  9. {
  10.     ElemType data;
  11.     struct LNode* next;
  12. }LNode, *pLinkList;
  13.  
  14. pLinkList LinkList_Init()                           //单链表创建
  15. {
  16.     int n;
  17.     LNode *phead, *temp, *p;
  18.     phead = new LNode;
  19.  
  20.     if (phead == NULL)
  21.     {
  22.         cout << "链表创建失败！" << endl;
  23.         exit(0);
  24.     }
  25.     cout << "输入需要随机产生的元素的个数(不少于10个)：";
  26.     cin >> n;
  27.     temp = phead;
  28.     srand(unsigned(time(NULL)));
  29.     for (int i = 0; i < n; i++)
  30.     {
  31.         p = new LNode;
  32.         p->data = rand() % 100;
  33.         temp->next = p;
  34.         temp = p;
  35.     }
  36.     temp->next = NULL;
  37.     return phead;
  38. }
  39. void LinkList_Display(pLinkList phead)                     //输出链表
  40. {
  41.     phead = phead->next;
  42.     while (phead)
  43.     {
  44.         cout << setw(4) << phead->data;
  45.         phead = phead->next;
  46.     }
  47.     cout << endl;
  48. }
  49. void LinkList_Free(pLinkList phead)                   //链表释放
  50. {
  51.     LNode *p;
  52.     while (phead)
  53.     {
  54.         p = phead;
  55.         phead = phead->next;
  56.         delete p;
  57.     }
  58. }
  59. void LinkList_Convert(pLinkList phead)         //单链表中的元素逆置
  60. {
  61.     LNode *p1, *p2, *p3;                         //p3为第一个结点，p2为第二个结点，p1为第三个结点
  62.     if (phead->next == NULL)
  63.     {
  64.         cout << "链表为空！" << endl;
  65.         return;
  66.     }
  67.     p3 = phead->next;
  68.     p2 = p3->next;
  69.     if (p2 == NULL)
  70.     {
  71.         return;
  72.     }
  73.     p1 = p2->next;
  74.     p3->next = NULL;
  75.     while (p1)
  76.     {
  77.         p2->next = p3;
  78.         p3 = p2;
  79.         p2 = p1;
  80.         p1 = p1->next;
  81.     }
  82.     p2->next = p3;
  83.     phead->next = p2;
  84. }
  85. void LinkLIst_Del_oushu(pLinkList phead)    //删除单链表中所有的偶数元素结点
  86. {
  87.     LNode *p1, *p2;
  88.     p2 = phead;
  89.     phead = phead->next;
  90.     while (phead)
  91.     {
  92.         if (phead->data % 2 == 0)
  93.         {
  94.             p1 = phead;
  95.             phead = phead->next;
  96.             delete p1;
  97.             p2->next = phead;
  98.             continue;
  99.         }
  100.         p2 = phead;
  101.         phead = phead->next;
  102.     }
  103. }
  104. void LinkList_Sort(pLinkList phead)                  //排序
  105. {
  106.     ElemType *num, temp;
  107.     LNode *p;
  108.     int count = 0, i = 0;
  109.     if (phead->next == NULL)
  110.     {
  111.         cout << "链表为空！" << endl;
  112.         return;
  113.     }
  114.     p = phead->next;
  115.     while (p)
  116.     {
  117.         count++;
  118.         p = p->next;
  119.     }
  120.     num = new ElemType[count];
  121.     p = phead->next;
  122.     while (p)
  123.     {
  124.         num[i++] = p->data;
  125.         p = p->next;
  126.     }
  127.     for (int j = 0; j < count - 1; j++)
  128.         for (int k = 0; k < count - j - 1; k++)
  129.             if (num[k] > num[k + 1])
  130.             {
  131.                 temp = num[k];
  132.                 num[k] = num[k + 1];
  133.                 num[k + 1] = temp;
  134.             }
  135.     p = phead->next;
  136.     i = 0;
  137.     while (p)
  138.     {
  139.         p->data = num[i++];
  140.         p = p->next;
  141.     }
  142.     delete[] num;
  143. }
  144. void LinkList_Insert(pLinkList phead, ElemType elem)    //插入一个元素
  145. {
  146.     LNode *p1, *p2, *tmp = NULL;
  147.     p1 = phead->next;
  148.     p2 = phead;
  149.     while (p1)
  150.     {
  151.         if (elem < p1->data)
  152.             break;
  153.         p2 = p1;
  154.         p1 = p1->next;
  155.     }
  156.     tmp = new LNode;
  157.     tmp->data = elem;
  158.     p2->next = tmp;
  159.     tmp->next = p1;
  160. }
  161. void LinkList_Divide(pLinkList L1, pLinkList L2)           //链表分解成奇数和偶数两个链表
  162. {
  163.     LNode *p1, *p2;
  164.     p2 = L1;
  165.     p1 = L1->next;
  166.     while (p1)
  167.     {
  168.         if ((p1->data) % 2 == 0)
  169.         {
  170.             L2->next = p1;
  171.             L2 = p1;
  172.             p1 = p1->next;
  173.             p2->next = p1;
  174.         }
  175.         else
  176.         {
  177.             p2 = p1; p1 = p1->next;
  178.         }
  179.     }
  180.     L2->next = NULL;
  181. }
  182. void LinkList_Cat(pLinkList L1, pLinkList L2)           //链表合并,
  183. {
  184.     pLinkList p1, p2;
  185.     p2 = L1;
  186.     p1 = L1->next;
  187.     while (p1)
  188.     {
  189.         p2 = p1; p1 = p1->next;
  190.     }
  191.     p2->next = L2->next;
  192.     LinkList_Sort(L1);
  193.     LinkList_Convert(L1);
  194. }
  195. int main()
  196. {
  197.     LNode *L = NULL, *L1 = NULL, *L2 = NULL;
  198.     int num;
  199.     cout << "1:随机产生或键盘输入一组元素（不少于10个元素）,建立一个带头结点的单链表" << endl;
  200.     cout << "2:单链表中的元素逆置" << endl;
  201.     cout << "3:单链表排序输出" << endl;
  202.     cout << "4:删除单链表中所有的偶数元素结点" << endl;
  203.     cout << "5:插入一个元素，用该函数建立一个非递减有序单链表（插入）" << endl;
  204.     cout << "6:建立两个非递减有序单链表，然后合并成一个非递增链表（合并）" << endl;
  205.     cout << "7:链表分解成两个链表，其中一个全部为奇数，另一个全部为偶数" << endl;
  206.     cout << "8:退出" << endl;
  207.     cout << endl;
  208.     while (true)
  209.     {
  210.         cout << "请输入一个数字选项：";
  211.         cin >> num;
  212.         switch (num)
  213.         {
  214.         case 1:
  215.         {   L = LinkList_Init();
  216.             cout << "L链表为：";
  217.             LinkList_Display(L);
  218.             cout << endl;
  219.         }break;
  220.         case 2:
  221.         {    LinkList_Convert(L);
  222.             cout << "链表为：";
  223.             LinkList_Display(L);
  224.             cout << endl;
  225.         }break;
  226.         case 3:
  227.         {    LinkList_Sort(L);
  228.             cout << "链表为：";
  229.             LinkList_Display(L);
  230.             cout << endl;
  231.         }break;
  232.         case 4:
  233.         {    LinkLIst_Del_oushu(L);
  234.             cout << "链表为：";
  235.             LinkList_Display(L);
  236.             cout << endl;
  237.         }break;
  238.         case 5:
  239.         {   ElemType elem;
  240.             cout << "输入要插入的元素：";
  241.             cin >> elem;
  242.             LinkList_Sort(L);
  243.             LinkList_Insert(L, elem);
  244.         cout << "链表为：";
  245.         LinkList_Display(L);
  246.         cout << endl;
  247.         }break;
  248.         case 6:
  249.         {   
  250.             L1 = LinkList_Init();
  251.             cout << "L1链表为：";
  252.             LinkList_Display(L1);
  253.             L2 = LinkList_Init();
  254.             cout << "L2链表为：";
  255.             LinkList_Display(L2);
  256.             LinkList_Cat(L1, L2);
  257.             cout << "合并的链表为：";
  258.             LinkList_Display(L1);
  259.             cout << endl;
  260.         }break;
  261.         case 7:
  262.         {
  263.             L2 = new LNode;
  264.             LinkList_Divide(L1, L2);
  265.             cout << "L1链表为：";
  266.             LinkList_Display(L1);
  267.             cout << "L2链表为：";
  268.             LinkList_Display(L2);
  269.             LinkList_Free(L2);
  270.             cout << endl;
  271.         }break;
  272.         case 8:
  273.         {
  274.             LinkList_Free(L);
  275.             delete L1;
  276.             cout << endl;
  277.             cout << "链表已释放并删除"<<endl;
  278.             cout << endl;
  279.         }break;
  280.         default:
  281.             cout << "输入错误！请重新输入！" << endl;
  282.             cout << endl;
  283.         }
  284.     }
  285.     return 0;
  286. }

运行截图：

双向链表

         双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

双向链表的创建

        头插法和尾插法只看代码比较难以与理解，建议画出插入节点时的链表变化图则会非常容易理解，另外，个人认为头插法较优，因为其插入逻辑一步到位，不像尾插法还需在后面完成双向链表的环状连接。

1.头插法

  1. Node * creatList()
  2. {
  3.    Node * head = (Node*)malloc(sizeof(Node));
  4.    Node * cur = NULL;
  5.    head->next = head;
  6.    head->pre = head;
  7.    int data;
  8.    scanf("%d",&data);
  9.    while(data)
  10.      {
  11.        cur = (Node*)malloc(sizeof(Node));
  12.        cur->data = data;
  13.        cur->next = head->next;
  14.        cur->pre = head;
  15.        head->next = cur;
  16.        cur->next->pre = cur;
  17.        scanf("%d",&data);
  18.      }
  19.   return head;
  20. }

2.尾插法

  1. Node * creatList()
  2. {
  3.   Node * head = (Node*)malloc(sizeof(Node));
  4.   Node * phead = head;
  5.   Node * cur = NULL;
  6.   phead->next = NULL;
  7.   phead->pre = NULL;
  8.   int data;
  9.   scanf("%d",&data);
  10.   while(data)
  11.   {
  12.      cur = (Node*)malloc(sizeof(Node));
  13.      cur->data = data;
  14.      phead->next = cur;
  15.      cur->pre = phead;
  16.      phead = cur;
  17.      scanf("%d",&data);
  18.   }
  19. //完成回环
  20.   cur->next = head;
  21.   head->pre = cur;
  22.   return head;
  23. }

双向链表实验

实验内容：

１．利用尾插法建立一个双向链表。
２．遍历双向链表。
３．实现双向链表中删除一个指定元素。
４．在非递减有序双向链表中实现插入元素e仍有序的算法。
５．判断双向链表中元素是否对称，若对称返回 1，否则返回 0。
６．设元素为正整型，实现算法把所有奇数排列在偶数之前。
７．在主函数中设计一个简单菜单，调用上述算法。

实验说明：

双向链表的类型定义

  1.    typedef  int  ElemType；  // 元素类型 
  2.    typedef  struct  DuLNode 
  3.    {
  4. ElemType  data; 
  5.       DuLNode *prior, *next; 
  6.    } DuLNode, *pDuLinkList;

源代码

  1. #include <iostream>
  2. #include <time.h>
  3. #include <stdlib.h>
  4. #include <iomanip>
  5. using namespace std;
  6.  
  7. typedef  int  ElemType;
  8. typedef  struct  DuLNode
  9. {
  10.     ElemType  data;
  11.     struct DuLNode *prior, *next;
  12. } DuLNode, *pDuLinkList;
  13.  
  14. pDuLinkList DuLinkLinst_Init()         //建立双向链表
  15. {
  16.     int n;
  17.     DuLNode *phead, *tmp, *p;
  18.     srand(unsigned(time(NULL)));
  19.     cout << "输入建立链表的元素个数：";
  20.     cin >> n;
  21.     phead = new DuLNode;
  22.     phead->next = phead;
  23.     phead->prior = phead;
  24.     p = phead;
  25.     for (int i = 0; i < n; i++)
  26.     {
  27.         tmp = new DuLNode;
  28.         tmp->data = rand() % 100;
  29.         tmp->prior = p;
  30.         p->next = tmp;
  31.         p = tmp;
  32.     }
  33.     p->next = phead;
  34.     phead->prior = p;
  35.     return phead;
  36. }
  37. void DuLinkList_Display(pDuLinkList phead)   //输出双向链表
  38. {
  39.     DuLNode *p;
  40.     p = phead->next;
  41.     while (p != phead)
  42.     {
  43.         cout << setw(4) << p->data;
  44.         p = p->next;
  45.     }
  46.     cout << endl;
  47. }
  48. void DuLinkList_Free(pDuLinkList phead)   //释放双链表
  49. {
  50.     DuLNode *p, *t;
  51.     p = phead->next;
  52.     while (p != phead)
  53.     {
  54.         t = p;
  55.         p = p->next;
  56.         delete t;
  57.     }
  58.     delete p;
  59. }
  60. void DuLinkList_Del(pDuLinkList phead, ElemType x)    //删除指定元素
  61. {
  62.     DuLNode *p1, *p2;
  63.     p1 = phead->next;
  64.     p2 = phead;
  65.     while (p1)
  66.     {
  67.         if (x == p1->data)
  68.         {
  69.             p2->next = p1->next;
  70.             p1->next->prior = p2;
  71.             delete p1;
  72.             return;
  73.         }
  74.         p2 = p1;
  75.         p1 = p1->next;
  76.     }
  77.     cout << "指定元素未找到！" << endl;
  78. }
  79. void DuLinkList_Sort(pDuLinkList phead)               //排序
  80. {
  81.     DuLNode *p;
  82.     int count = 0, i = 0;
  83.     ElemType *num, tmp;
  84.     p = phead->next;
  85.     if (p == phead)
  86.     {
  87.         cout << "双向链表为空！" << endl;
  88.         return;
  89.     }
  90.     while (p != phead)
  91.     {
  92.         count++;
  93.         p = p->next;
  94.     }
  95.     num = new ElemType[count];
  96.     p = phead->next;
  97.     while (p != phead)
  98.     {
  99.         num[i++] = p->data;
  100.         p = p->next;
  101.     }
  102.     for (int k = 0; k < count - 1; k++)
  103.         for (int j = 0; j < count - k - 1; j++)
  104.             if (num[j] > num[j + 1])
  105.             {
  106.                 tmp = num[j];
  107.                 num[j] = num[j + 1];
  108.                 num[j + 1] = tmp;
  109.             }
  110.     p = phead->next;
  111.     i = 0;
  112.     while (p != phead)
  113.     {
  114.         p->data = num[i++];
  115.         p = p->next;
  116.     }
  117.     delete[] num;
  118. }
  119. void DuLinkList_Insert(pDuLinkList phead, ElemType elem)    //插入一个元素
  120. {
  121.     DuLNode *p, *tmp;
  122.     p = phead->next;
  123.  
  124.     while (p != phead)
  125.     {
  126.         if (elem <= p->data)
  127.             break;
  128.         p = p->next;
  129.     }
  130.     tmp = new DuLNode;
  131.     tmp->data = elem;
  132.     tmp->next = p;
  133.     tmp->prior = p->prior;
  134.     p->prior->next = tmp;
  135.     p->prior = tmp;
  136. }
  137. int DuLinkList_symmetry(pDuLinkList phead)  //链表中元素是否对称
  138. {
  139.     DuLNode *p1, *p2;
  140.     p1 = phead->prior;
  141.     p2 = phead->next;
  142.     while (p1 != p2)
  143.     {
  144.         if (p1->data != p2->data)
  145.         {
  146.             return 0;
  147.         }
  148.         p1 = p1->prior;
  149.         p2 = p2->next;
  150.     }
  151.     return 1;
  152. }
  153. void DuLinkList_jiousort(pDuLinkList phead)     //奇数在偶数前面
  154. {
  155.     DuLNode *p1, *p2;
  156.     p1 = phead->next;
  157.     p2 = p1->next;
  158.     if (p1 == phead)
  159.     {
  160.         cout << "双向链表为空！" << endl;
  161.         return;
  162.     }
  163.     if (p2 == phead)
  164.     {
  165.         return;
  166.     }
  167.     while (p1 != phead)
  168.     {
  169.         if ((p1->data) % 2 != 0)
  170.         {
  171.             p2 = p1;
  172.             p1 = p1->next;
  173.  
  174.             p1->prior = p2->prior;
  175.             p2->prior->next = p1;
  176.  
  177.             p2->next = phead->next;
  178.             phead->next->prior = p2;
  179.             phead->next = p2;
  180.             p2->prior = phead;
  181.         }
  182.         else
  183.             p1 = p1->next;
  184.     }
  185. }
  186. int main()
  187. {
  188.     DuLNode *L = NULL;
  189.     ElemType t;
  190.     int num;
  191.     cout << "1:利用尾插法建立一个双向链表" << endl;
  192.     cout << "2:遍历双向链表" << endl;
  193.     cout << "3:双向链表中删除一个指定元素" << endl;
  194.     cout << "4:在非递减有序双向链表中实现插入元素e仍有序的算法。" << endl;
  195.     cout << "5:判断双向链表中元素是否对称，若对称返回 1，否则返回 0" << endl;
  196.     cout << "6:设元素为正整型，实现算法把所有奇数排列在偶数之前" << endl;
  197.     cout << "7:退出" << endl;
  198.     while (true)
  199.     {
  200.         cout << "请输入一个数字选项:";
  201.         cin >> num;
  202.         switch (num)
  203.         {
  204.         case 1:
  205.         {
  206.             L = DuLinkLinst_Init();
  207.             cout << "L双向链表为：";
  208.             DuLinkList_Display(L);
  209.             cout << endl;
  210.         }break;
  211.         case 2:
  212.         {
  213.             cout << "双向链表为：";
  214.             DuLinkList_Display(L);
  215.             cout << endl;
  216.         }break;
  217.         case 3:
  218.         {
  219.             cout << "输入需要删除的元素：";
  220.             cin >> t;
  221.             DuLinkList_Del(L, t);
  222.             cout << "双向链表为：";
  223.             DuLinkList_Display(L);
  224.             cout << endl;
  225.         }break;
  226.         case 4:
  227.         {
  228.             cout << "输入要插入的元素：";
  229.             cin >> t;
  230.             DuLinkList_Sort(L);
  231.             DuLinkList_Insert(L, t);
  232.             cout << "双向链表为：";
  233.             DuLinkList_Display(L);
  234.             cout << endl;
  235.         }break;
  236.         case 5:
  237.         {
  238.              if(DuLinkList_symmetry(L)==1)
  239.                  cout << "双向链表中元素对称" << endl;
  240.              else 
  241.                  cout << "双向链表中元素不对称" << endl;
  242.              cout << endl;
  243.         }break;
  244.         case 6:
  245.         {
  246.             DuLinkList_jiousort(L);
  247.             cout << "双向链表为：";
  248.             DuLinkList_Display(L);
  249.             cout << endl;
  250.         }break;
  251.         case 7:
  252.         {
  253.             DuLinkList_Free(L);
  254.             cout << endl;
  255.             return 0;
  256.         }break;
  257.         default:
  258.             cout << "输入错误！请重新输入！" << endl;
  259.             cout << endl;
  260.         }
  261.     }
  262.     return 0;
  263. }

运行截图： 

 

 总结

         如果把编程语言比作一个句子，那数据结构就好比是一篇文章。写好句子要意思清晰明确，写文章的话，更看重的是其传达的思想。马克吐温有句话是这样说的，当你手拿着锤子的时候，看见很多东西都是钉子。这句话原来的意思我不大想深究，毕竟这不是技术问题。而在读过了著名黑客雷蒙德的一篇经典文章《如何成 为一名黑客》，我对这个说法有一个新的感悟。他在文中写道：“做一名黑客会有很多乐趣，但却  是要费很多气力方能得到的乐趣。 这些努力需要动力。成功的运动员从锻炼身体、超越自我极限的愉悦中得到动力。 同样，做黑客，你得能从解决问题，磨练技术及锻炼智力中得到基本的乐趣。”锤子是工具，钉子是问题，当工具被用来解决你的问题的时候，享受那种满足的感觉，   是很难用言语来形容的。学习 C 语言不是光为了学习 C 语言，你是要用它来解决问题的。很遗憾在现实中，很多同学在大一大二学完了C 语言这门课程，甚至也考了一个不错的分数之后， 就把这门工具丢到一旁了，再也没理了。他们没有享受到这种乐趣，这是很可惜的。你是一个手拿锤子的人吗？握紧！

        好叭。今天就到这里了，我也该去睡觉了，后续我还会发布更多的项目源或者学习资料，希望大家可以持续关注，有什么问题可以回帖留言。想要提前掌握的可以加群领取C/C++学习资料以及其他项目的源码的可以加群【1083227756】了解。想要对程序员的未来发展有兴趣的可以关注微信公众号：【狐狸的编码时光】，希望和大家一起学习进步！

念七可爱卡通情侣头像 可做表情包的卡通情侣头像

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/858827
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号