1 离散存储【链表】（我们搞底层的开发，类似于SUN公司的类）

1.1 定义：

  1. n个节点离散分配
  2. 彼此通过指针相连
  3. 每个节点只有一个前驱节点，每个节点只有一个后续节点

  4. 首节点没有前驱节点，尾节点没有后续节点。

    1.2 链表的优缺点：

    1.2.1 优点：

  5. 空间没有限制

  6. 插入删除元素很快

    1.2.2 缺点：

  7. 存取速度很慢。

    2 专业术语：

    2.1 头节点：

    头结点的数据类型和首节点的类型一样没有存放有效数据，最最前面的，是在首节点之前的，主要是为了方便对链表的操作。
    头结点有可能很大，占的内存可能大，假设我想造一个函数输出所有链表的值，那你如果不用头指针类型做形参，那由于不同链表的头节点不一样大小，这样就没办法找出形参

    2.2 首节点：第一个有效节点

    2.3 尾节点：最后一个有效节点

    2.4 头指针：（指向头）指向头节点的指针变量

  • 存放头结点的地址

    2.5 尾指针：指向尾节点的指针

  • 存放尾节点的地址

    2.6确定一个链表需要几个参数：

    （或者说如果期望一个函数对链表进行操作我们至少需要接收链表的那些信息？？？）

  • 只需要一个参数:头指针，因为通过它我们可以推出链表的所有信息。

（链表的程序最好一定要自己敲出来）

2.7 创建一个Node

  1. /*
  2.  * @Descripttion: 
  3.  * @version: Beta-v1.0.0
  4.  * @Author: jhong.tao
  5.  * @Date: 2020-11-29 19:37:19
  6.  * @LastEditTime: 2020-11-29 19:41:38
  7.  */
  9. # include <stdio.h>
  11. typedef struct Node{
  12.     int data;   // 数据域
  13.     struct Node * pNext;    // 指针域
  14. }NODE,* PNODE;
  16. int main(void){
  18.     return 0;
  19. }

3. 链表的分类

  • 单链表
  • 双链表： 每一个节点有两个指针域
  • 循环链表：能通过任何一个节点找到其他所有的节点
  • 非循环链表

java中变成垃圾内存则会自动释放，但是C和C++则不会，所以要手动释放，否则会引起内存泄露。delete等于free

4 链表相关的操作（算法）

  • 算法：狭义的算法是与数据的存储方式密切相关

    1. 广义的算法是与数据的存储方式无关

  • 泛型：（给你一种假象，只不过牛人从内部都弄好了）

    1.    利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的

  • 算法的真正学法：很多算法你根本解决不了！！！！！！

因为很多都属于数学上的东西，所以我们把答案找出来，如果能看懂就行，但是大部分人又看不懂，分三步，按照流程，语句试数。这个过程肯定会不断地出错，所以不断出错，不断改错，这样反复敲很多次，才能有个提高。实在看不懂 就先背会。

4.1 遍历

4.2 查找

4.3 清空

4.4 销毁

4.5 求长度

4.6 排序

4.7 删除节点

  1. r = p->pNext;
  2. p->pNext = p->pNetx->pNext;
  3. free(r);

4.8 插入节点

  1. q->pNext = p->pNext;
  2. p->pNext = q;

5 单链表操作code

  1. /*
  2.  * @Descripttion: 
  3.  * @version: Beta-v1.0.0
  4.  * @Author: jhong.tao
  5.  * @Date: 2020-11-30 16:38:12
  6.  * @LastEditTime: 2020-12-01 21:11:37
  7.  */
  9. # include <stdio.h>
  10. # include <stdlib.h>
  11. # include <stdbool.h>
  13. /**
  14.  * @name: struct Node
  15.  * @brief: 链表的每一个节点，
  16.  * @param {int data:链表节点中存放的数据}
  17.  * @param {struct Node* next:链表节点指向下一个节点的指针}
  18.  */
  19. typedef struct Node{
  20.     int data;       // 数据域
  21.     struct Node* next;     // 指针域
  22. }Node,*pNode;
  24. /**
  25.  * @name: struct List
  26.  * @brief: 定义的一个链表，包含了链表的头指针，尾指针和长度
  27.  * @param {pNode pHeat：链表的头结点指针}
  28.  * @param {pNode pTail：链表的尾指针}
  29.  * @param {int cnt：链表的长度}
  30.  */
  31. typedef struct List{
  32.     pNode pHeat;    // 头指针
  33.     pNode pTail;    // 尾指针
  34.     int cnt;        // 链表长度
  35. }List,*pList;
  37. // 函数声明
  38. pNode create_node(int val); // 创建一个节点
  39. pList create_list(int listName);    // 创建链表
  40. void print_List(pList pl); // 遍历链表
  41. bool list_append(pList pl, int val);   // 添加结点
  42. void free_list(pList pl);       // 释放链表
  43. bool is_empty(pList pl);        // 判断链表是否为空
  44. bool insert_list(pList pl, int pos, int val); // 插入数据
  45. pNode find_list(pList pl, int val); // 查找节点
  46. bool delet_list(pList pl, int val); // 删除一个节点
  47. void sort_list(pList pl);   // 对链表进行升序排序
  50. int main(void){
  51.     pList pl = create_list(0);
  52.     list_append(pl,1);
  53.     list_append(pl,2);
  55.     insert_list(pl,1,4);
  56.     print_List(pl);
  58.     sort_list(pl);
  59.     print_List(pl);
  60.     printf("查找到2的值为：%d\n",find_list(pl,2)->next->data);
  61.     free_list(pl);
  62.     return 0;
  63. }
  65. /**
  66.  * @name: void sort_list(pList pl)
  67.  * @brief: 对链表进行升序排序
  68.  * @param {pList pl：链表地址}
  69.  * @return {无}
  70.  */
  71. void sort_list(pList pl){
  72.     /*  方法一：取出链表的每个节点的数据存放在数组中，对数组排序，然后将数据从新写回链表
  73.         方法二：直接对链表进行选择排序，只操作数据不操作节点,本算法
  74.     */
  75.     if(pl->pHeat->next == NULL)  // 如果链表为空则终止
  76.         return;
  78.     pNode pi = pl->pHeat->next;  // 已排序游标指针，永远指向已排序的最后也是最大的那个节点
  79.     pNode pj = pi->next;         // 选择排序指针
  80.     pNode pMin = pi;             // 选择指针，每次都去寻找一个最小的节点
  81.     int intTemp;
  82.     while(pi!=NULL){
  83.         // 寻找未排序的最小节点
  84.         while(pj!=NULL){
  85.             if(pj->data < pMin->data)
  86.                 pMin = pj;
  87.             pj = pj->next;
  88.         }
  89.         // 如果在未排序的队列中第一个节点就是最小节点的情况,直接后移
  90.         if(pMin == pi){
  91.             pi = pi->next;
  92.             pMin = pi;
  93.             if(pj !=NULL)   //  当循环到最后一个节点时会出现pi->next=null的情况
  94.                 pj = pi->next;
  95.         }else{
  96.             // 如果未排序队列的第一个节点不是最小的，需要交换数据
  97.             intTemp = pi->data;
  98.             pi->data = pMin->data;
  99.             pMin->data = intTemp;
  100.             pi = pi->next;
  101.             pMin = pi;
  102.             pj = pi->next;
  103.         }
  104.     }
  105. }
  107. /**
  108.  * @name: bool delet_list(pList pl, int val)
  109.  * @brief: 删除一个第一次出现值为val的节点
  110.  * @param {pList pl：链表地址}
  111.  * @param {int val：要删除数}
  112.  * @return {true:表示删除成功}
  113.  */
  114. bool delet_list(pList pl, int val){
  115.     pNode p = find_list(pl, val);   // 获取当前节点的前驱的地址
  116.     if(p==NULL)
  117.         return false;
  119.     pNode pTemp = p->next; // 获取当前节点的地址
  120.     p->next = pTemp->next;
  121.     free(pTemp);
  122. }
  124. /**
  125.  * @name: bool find_list(pList pl, int val)
  126.  * @brief: 查找首次在链表中出现的节点的前一个节点的地址
  127.  * @param {pList pl：链表地址}
  128.  * @param {int val：备查找的数}
  129.  * @return {找到返回该节点前一个节点的地址，找不到返回NULL}
  130.  */
  131. pNode find_list(pList pl, int val){
  132.     pNode p = pl->pHeat; // 游标指针指向头节点
  133.     while(p != NULL){
  134.         if(val == p->next->data)
  135.             return p;
  136.         p = p->next;
  137.     }
  138.     return NULL;
  139. }
  141. /**
  142.  * @name: insert_list(pList pl, int pos, int val)
  143.  * @brief: 向链表中插入一个数据
  144.  * @param {pList pl：链表地址}
  145.  * @param {int pos：插入链表的位置，计数从1开始}
  146.  * @param {int val：需要插入的数值}
  147.  * @return {true：表示插入成功}
  148.  */
  149. bool insert_list(pList pl, int pos, int val){
  150.     // 位置小于1越界异常，插入失败
  151.     if(pos<1){
  152.         printf("越界异常，插入失败\n");
  153.         return false;
  154.     }
  156.     // 位置比当前链表长则直接追加
  157.     if(pos>pl->cnt){
  158.         if(list_append(pl,val))
  159.             return true;
  160.         return false;
  161.     }
  163.     // 位置落在 1到链表长度之间
  164.     pNode pn = create_node(val);
  165.     if(pn == NULL)
  166.         return false;
  167.     pNode p = pl->pHeat;  // 游标指针指向 头节点
  168.     for(int i=0; i<pos; i++){
  169.         if(i+1 == pos){
  170.             pn->next = p->next;
  171.             p->next = pn;
  172.             pl->cnt++;
  173.             return true;
  174.         }
  175.         p = p->next;
  176.     }
  177. }
  179. /**
  180.  * @name: bool is_empty(pList pl)
  181.  * @brief: 判断链表是否为空
  182.  * @param {pList pl：链表地址}
  183.  * @return {true表示链表为空}
  184.  */
  185. bool is_empty(pList pl){
  186.     if(pl->pHeat->next == NULL)
  187.         return true;
  188.     return false;
  189. }
  191. /**
  192.  * @name: void free_list(pList pl)
  193.  * @brief: 释放一个链表
  194.  * @param {pList pl：链表的头指针}
  195.  * @return {无}
  196.  */
  197. void free_list(pList pl){
  198.     if (pl==NULL)
  199.         return;
  200.     pNode p = pl->pHeat->next;  // 遍历链表的指针，获取链表的首节点
  201.     while(p != NULL){       
  202.         pl->pHeat->next = p->next;
  203.         free(p);                // 循环释放每个节点
  204.         p = pl->pHeat->next;    // 更新p,再次指向首节点
  205.     }
  206.     free(pl->pHeat);            // 释放链表头结点
  207.     free(pl);                   // 释放链表
  208. }   
  210. /**
  211.  * @name: pList create_list()
  212.  * @brief: 创建一个链表，包含头，尾指针和链表长度
  213.  * @param {int listName:链表的头结点存放的数据，可以表示链表的编号或者名称}
  214.  * @return {pList pl:链表的地址}
  215.  */
  216. pList create_list(int listName){
  217.     // 创建头结点
  218.     pList pl = (pList)malloc(sizeof(List));
  219.     if(NULL == pl){
  220.          printf("链表创建失败");
  221.          exit(-1);
  222.     } 
  223.     pNode pHead = (pNode)malloc(sizeof(Node));
  224.     if(NULL == pHead){
  225.          printf("链表创建失败");
  226.          exit(-1);
  227.     } 
  228.     pHead->data = listName;     // 头结点，记录链表名称
  229.     pHead->next = NULL;         // 头结点，指针域置空
  231.     pl->pHeat = pHead;          // 头指针，指向头结点
  232.     pl->cnt = 0;                // 初始化链表，长度，头结点不算入链表长度
  233.     pl->pTail = pHead;          // 尾结点,初始化链表时也指向头结点
  234.     return pl;
  235. }
  237. /**
  238.  * @name: pNode create_node(int val)
  239.  * @brief: 创建链表的每一个节点
  240.  * @param {int val：链表节点中保存的数据}
  241.  * @return {pNode pHead：生成的链表节点的地址}
  242.  */
  243. pNode create_node(int val){
  244.     pNode pHead = (pNode)malloc(sizeof(Node));  // 创建一个链表节点
  245.     if(NULL != pHead){
  246.         pHead->data = val;      // 给节点数据域赋值
  247.         pHead->next = NULL;     // 置空节点指针域
  248.     } 
  249.     return pHead;
  250. }
  252. /**
  253.  * @name: bool list_append(pList pl, int val)
  254.  * @brief: 向链表中添加数据
  255.  * @param {pList pl：链表地址}
  256.  * @param {int val：添加的值}
  257.  * @return {true：表示添加成功}
  258.  */
  259. bool list_append(pList pl, int val){
  260.     pNode pn = create_node(val);    // 创建一个结点
  261.     if(pn == NULL)
  262.         return false;
  263.     pl->pTail->next = pn;           // 将新节点挂在链表尾部
  264.     pl->pTail = pn;                 // 更新链表的尾指针
  265.     pl->cnt++;                      // 更新链表长度    
  266.     return true;
  267. }
  269. /**
  270.  * @name: void print_List(pList pl)
  271.  * @brief: 打印链表
  272.  * @param {pList pl：链表地址}
  273.  * @return {无返回值}
  274.  */
  275. void print_List(pList pl){
  276.     pNode p = pl->pHeat->next;  // 获取链表首节点，即链表第一个存放真实数据的节点，不是头结点
  277.     printf("%d 链表的长度为:%d\n", pl->pHeat->data, pl->cnt);
  278.     while(p != NULL){
  279.         printf("%d  ",p->data);     // 打印链表的每个节点的数据
  280.         p = p->next;
  281.     }
  282.     printf("\n");
  283. }