001_链表

  1. // 001_链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
  2. //
  4. #include "pch.h"
  5. #include <iostream>
  7. // 
  8. // 链表的数据结构
  9. // 1. 链表是由每一个节点连接起来的.
  10. struct Node {
  11.     int        nData; // 数据域
  12.     Node*    pNext; // 指针域,用于保存下一个节点的首地址
  13. };
  15. class List {
  16.     // 记录当前链表的节点个数
  17.     int m_nCount=0;
  18.     // 用于保存链表的头节点的地址
  19.     Node* m_pHead = nullptr;
  20. public:
  21.     /*!
  22.      * 函数名 : insert
  23.      * 功  能 : 将元素nData插入到链表的第nIndex位置
  24.      * 参  数 : int nIndex 插入到的下标
  25.      * 参  数 : int nData 要插入的数据
  26.      * 返回值 :  bool
  27.      */
  28.     bool insert(int nIndex, int nData)
  29.     {
  30.         // 1. 检查插入位置是否错误.
  31.         if (nIndex <0 || nIndex>m_nCount) {
  32.             return false;
  33.         }
  34.         // 2. 在堆空间中申请内存来保存新的节点
  35.         Node* pNew = new Node;
  36.         // 2.1 将要插入到链表中的数据保存在新节点.
  37.         pNew->nData = nData;
  38.         // 3. 在链表中找到插入位置的前一个节点.
  39.         // 3.1 如果插入到的是第0个位置.那么需要将
  40.         //     新节点的首地址记录在m_pHead指针中.
  41.         if (nIndex == 0) {
  42.             pNew->pNext = m_pHead;
  43.             m_pHead = pNew;
  44.         }
  45.         else {
  46.             // 循环遍历到插入位置的前一个节点.
  47.             Node* pPre = m_pHead;
  48.             for (int i = 1; i < nIndex; ++i) {
  49.                 pPre = pPre->pNext;
  50.             }
  51.             // 4. 将前一个节点的pNext字段保存到新节点的pNext字段
  52.             //      这样就可以让新节点记录下一个节点
  53.             pNew->pNext = pPre->pNext;
  54.             // 5. 将新节点的首地址保存到前一个节点的pNext字段
  55.             //    这样通过前一个节点就能找到新的节点.
  56.             pPre->pNext = pNew;
  57.         }
  58.         // 6. 增加节点个数.
  59.         ++m_nCount;
  60.     }
  62.     /*!
  63.      * 函数名 : remove
  64.      * 功  能 : 从链表中删除下标为nIndex的元素
  65.      * 参  数 : int nIndex 要删除的元素所在的下标
  66.      * 返回值 :  void
  67.      */
  68.     void remove(int nIndex)
  69.     {
  70.         // 1. 判断下标是否正确
  71.         if (nIndex < 0 || nIndex >= m_nCount) {
  72.             return;
  73.         }
  74.         // 2. 找到要删除的元素的前一个节点
  75.         // 2.1 如果删除的是第0个节点. 这个节点的首地址
  76.         //     是保存在m_pHead头节点指针中.
  77.         //     因此, 直接操作头节点指针.
  78.         if (nIndex == 0) {
  79.             // m_pHead->pNext记录的是被删除节点的下一个
  80.             // 节点的首地址
  81.             // 现在将下一个节点作为新的头节点:将节点的地址
  82.             // 记录在头节点指针中.
  83.             Node* temp = m_pHead;
  84.             m_pHead = m_pHead->pNext;
  85.             delete temp;
  86.         }
  87.         else {
  88.             Node* pPreNode = m_pHead;
  89.             for (int i = 1; i < nIndex; ++i) {
  90.                 pPreNode = pPreNode->pNext;
  91.             }
  92.             // 3. 通过前一个节点的pNext字段找到被删除节点
  93.             //      的首地址
  94.             Node* pRemoveNode = pPreNode->pNext;
  95.             // 4. 再通过被删除节点的pNext字段,得到被删除
  96.             //    节点的下一个节点的首地址
  97.             Node* pNextNode = pRemoveNode->pNext;
  98.             // 5. 将被删除节点的下一个节点的首地址保存到
  99.             //    被删除节点的前一个节点的pNext字段.
  100.             pPreNode->pNext = pNextNode;
  101.             // 6. 释放掉被删除节点的内存空间
  102.             delete pRemoveNode;
  103.         }
  104.         // 7. 递减当前节点个数
  105.         --m_nCount;
  106.     }
  108.     /*!
  109.      * 函数名 : find
  110.      * 功  能 : 在链表中查找元素
  111.      * 参  数 : int nData 被查找的元素
  112.      * 返回值 : int 元素在链表中的下标,找不到了就返回-1
  113.      */
  114.     int find(int nData) {
  115.         Node* pNode = m_pHead;
  116.         int nIndex = 0;
  117.         while (pNode != nullptr) {
  118.             // 判断当前遍历到的节点保存的数据
  119.             // 是否是要查找的数据
  120.             if (pNode->nData == nData) {
  121.                 // 如果是,就返回下标
  122.                 return nIndex;
  123.             }
  124.             // 递增下标,用于记录,当前遍历到了第几个元素
  125.             ++nIndex;
  126.             // 找到下一个节点
  127.             pNode = pNode->pNext;
  128.         }
  129.         return -1;
  130.     }
  132.     /*!
  133.      * 函数名 : at
  134.      * 功  能 : 获取指定下标的元素的数据域的引用.
  135.      * 参  数 : int nIndex 元素所在的下标
  136.      * 返回值 :  int& 返回数据的引用.这样就可以在函数外部修改节点的数据了
  137.      */
  138.     int& at(int nIndex) {
  139.         if (nIndex < 0 || nIndex >= m_nCount) {
  140.             throw std::exception("下标越界");
  141.         }
  142.         // 遍历到指定下标处的节点
  143.         Node* pNode = m_pHead;
  144.         for (int i = 0; i < nIndex; ++i) {
  145.             pNode = pNode->pNext;
  146.         }
  147.         // 返回节点的引用(返回值是int&引用类型)
  148.         return pNode->nData;
  149.     }
  151.     /*!
  152.      * 函数名 : push_back
  153.      * 功  能 : 将数据插入到链表最后一个位置
  154.      * 参  数 : int nData
  155.      * 返回值 :  void
  156.      */
  157.     void push_back(int nData) {
  158.         insert(m_nCount, nData);
  159.     }
  161.     /*!
  162.      * 函数名 : pop_back
  163.      * 功  能 : 将最后一个元素的值输出到*pData,然后删除
  164.      * 参  数 : int * pData
  165.      * 返回值 :  void
  166.      */
  167.     void pop_back(int* pData) {
  168.         if (m_nCount) {
  169.             // 先获取最后一个元素的值,并保存到
  170.             // 指针指向的内存中
  171.             *pData = at(m_nCount - 1);
  172.             // 删除该元素
  173.             remove(m_nCount - 1);
  174.         }
  175.     }
  177.     /*!
  178.      * 函数名 : push_front
  179.      * 功  能 : 将数据插入到链表的最前面
  180.      * 参  数 : int nData
  181.      * 返回值 :  void
  182.      */
  183.     void push_front(int nData) {
  184.         insert(0, nData);
  185.     }
  187.     /*!
  188.      * 函数名 : pop_front
  189.      * 功  能 : 删除链表最前面的数据, 删除前,将值输出到*pData
  190.      * 参  数 : int * pData
  191.      * 返回值 :  void
  192.      */
  193.     void pop_front(int * pData) {
  194.         if (m_nCount) {
  195.             // 先获取最后一个元素的值,并保存到
  196.             // 指针指向的内存中
  197.             *pData = at( 0 );
  198.             // 删除该元素
  199.             remove( 0 );
  200.         }
  201.     }
  203.     /*!
  204.      * 函数名 : print
  205.      * 功  能 : 打印链表中的所有元素
  206.      * 返回值 :  void
  207.      */
  208.     void print() {
  209.         Node* pNode = m_pHead;
  210.         printf("[");
  211.         while (pNode != nullptr) {
  212.             // 打印节点的数据域
  213.             printf("%d,", pNode->nData);
  214.             // 找到下一个节点
  215.             pNode = pNode->pNext;
  216.         }
  217.         printf("\b]\n");
  218.     }
  219. };
  222. int main(){
  223.     List l;
  224.     printf("测试插入功能:\n");
  225.     l.insert(0, 10);
  226.     l.insert(0, 9);
  227.     l.insert(2, 12);
  228.     l.insert(1, 11);
  229.     l.print();
  231.     // 修改链表的下标为2的项
  232.     printf("\n测试修改功能:\n");
  233.     int& rEle = l.at(2);
  234.     printf("下标为2项的值:%d\n", rEle);
  235.     rEle = 100;
  236.     printf("下标为2项的值:%d\n", rEle);
  238.     printf("\n测试查找功能:\n");
  239.     int nIndex = l.find(12);
  240.     printf("元素12在链表中的第%d项\n", nIndex);
  242.     printf("\n测试删除功能:\n");
  243.     // 删除元素9
  244.     // 1. 先通过find查找到元素9的下标
  245.     // 2. 在通过删除函数删除指定下标的元素
  246.     l.remove(l.find(9));
  248.     l.remove(3);// 9- 11 - 10 -12
  249.     l.print();
  251.     l.remove(1);
  252.     l.print();
  254.     l.remove(0);
  255.     l.print();
  257.     // 模拟栈的操作:
  258.     printf("\n模拟栈操作:\n");
  259.     int nData = 0;
  260.     l.push_back(10);
  261.     l.push_back(9);
  262.     l.push_back(8);
  263.     l.push_back(7);
  264.     l.print();
  266.     l.pop_back(&nData);
  267.     l.print();
  268.     l.pop_back(&nData);
  269.     l.print();
  270.     l.pop_back(&nData);
  271.     l.print();
  272.     l.pop_back(&nData);
  273.     l.print();
  275.     // 模拟队列的操作
  276.     printf("\n模拟队列操作:\n");
  277.     l.push_back(100);
  278.     l.push_back(101);
  279.     l.push_back(102);
  280.     l.push_back(103);
  281.     l.pop_front(&nData);
  282.     l.print();
  283.     l.pop_front(&nData);
  284.     l.print();
  285.     l.pop_front(&nData);
  286.     l.print();
  287.     l.pop_front(&nData);
  288.     l.print();
  289. }

二分法

  1. // 二分法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
  2. //
  4. #include "pch.h"
  5. #include <iostream>
  7. int bin_seach(int* pArr, int nCount, int nData)
  8. {
  9.     //1. 先确定开始下标和结束的下标
  10.     int nBeg = 0;
  11.     int nEnd = nCount - 1;
  12.     int nMid = (nEnd - nBeg) / 2;
  13.     int i = 1;
  14.     while (1)
  15.     {
  16.         // 判断中间位置保存的数据是否就是
  17.         // 要查找的元素
  18.         if (pArr[nMid] == nData) {
  19.             return nMid;
  20.         }
  21.         if (nBeg == nEnd) {
  22.             return -1;
  23.         }
  24.         // 开始确定下一次的查找范围
  25.         if (nData < pArr[nMid]) {
  26.             // 1. 保存开始下标不变
  27.             // 2. 将当前中间下标设置为新的结束下标
  28.             nEnd = nMid;
  29.         }
  30.         else {
  31.             // 1. 保存结束的下标不变
  32.             // 2. 将当前中间下标设置为新的开始下标
  33.             nBeg = nMid;
  34.         }
  35.         // 重新计算新的中间下标
  36.         nMid = ((nEnd - nBeg) / 2) + nBeg;
  37.         printf("循环了%d次\n", i++);
  38.     }
  40. }
  42. void sort(int *pArr, int nCount) {
  43.     for (int i = 0; i < nCount - 1; ++i) {
  44.         for (int j = 0; j < nCount - i - 1; ++j) {
  45.             if (pArr[j] > pArr[j + 1]) {
  46.                 int temp = pArr[j];
  47.                 pArr[j] = pArr[j + 1];
  48.                 pArr[j + 1] = temp;
  49.             }
  50.         }
  51.     }
  52. }
  54. void printArr(int *pArr, int nCount) {
  55.     for (int i = 0; i < nCount; ++i) {
  56.         printf("%d,", pArr[i]);
  57.     }
  58.     printf("\b\n");
  59. }
  61. int main()
  62. {
  63.     int nArr[] = { 10,5,6,8,9,45,65,32,45 };
  64.     printArr(nArr, _countof(nArr));
  65.     sort(nArr, _countof(nArr));
  66.     printArr(nArr, _countof(nArr));
  68.     int nIndex = bin_seach(nArr, _countof(nArr), 45);
  69.     printf("45在%d\n", nIndex);
  71. }