• 数据结构与算法之美读书笔记6

    一、理解指针或引用的含义

    1.含义：将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。

    2.示例：

    p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。

    p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

    二、警惕指针丢失和内存泄漏（单链表）

    1.插入节点

            在节点a和节点b之间插入节点x，b是a的下一节点，，p指针指向节点a，则造成指针丢失和内存泄漏的代码：p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。
    正确的写法是2句代码交换顺序，即：x—>next = p—>next; p—>next = x;

    2.删除节点

            在节点a和节点b之间删除节点b，b是a的下一节点，p指针指向节点a：p—>next = p—>next—>next;

    三、利用“哨兵”简化实现难度

    1.什么是“哨兵”？

            链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，或者头结点。相反，没有“哨兵”节点的链表就称为不带头链表或不带头结点的链表。

    2.未引入“哨兵”的情况

    1. //如果在p节点后插入一个节点，只需2行代码即可搞定：
    2.  
    3. new_node—>next = p—>next;
    4. p—>next = new_node;
    5.  
    6. //但，若向空链表中插入一个节点，则代码如下：
    7.  
    8. if(head == null){
    9.     head = new_node;
    10. }
    11.  
    12. //如果要删除节点p的后继节点，只需1行代码即可搞定：
    13.  
    14. p—>next = p—>next—>next;
    15.  
    16. //但，若是删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：
    17.  
    18. if(head—>next == null){
    19.     head = null;
    20. }
    21.


    从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。

    3.引入“哨兵”的情况

    “哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。很方便！

    四、重点留意边界条件处理

    经常用来检查链表是否正确的边界4个边界条件：

    1.如果链表为空时，代码是否能正常工作？

    2.如果链表只包含一个节点时，代码是否能正常工作？

    3.如果链表只包含两个节点时，代码是否能正常工作？

    4.代码逻辑在处理头尾节点时是否能正常工作？

    五、举例画图，辅助思考

    数形结合！

    六、多写多练，没有捷径

    拿出我大一上学期写的陈年代码举例😊

    常见的链表操作：

    链表遍历

    1. #include
    2. #include
    3. struct node
    4. {
    5.     int num;
    6.     struct node * next;
    7. };
    8.  
    9. struct node * creat(int n)
    10. {
    11.  struct node * head,*q,*p;
    12.  head=(struct node *)malloc(sizeof(struct node));
    13.  head->next=NULL;
    14.  p=head;
    15.  char s[1000];
    16.  int i=0;
    17.  scanf("%s",s);
    18.  while(n--)
    19.  {
    20.      q=(struct node *)malloc(sizeof(struct node));
    21.      q->num=s[i++]-'0';
    22.      q->next=NULL;
    23.      p->next=q;
    24.      p=q;
    25.  }
    26.  return head;
    27. }
    28. int main()
    29. {
    30.     int t,n;
    31.     scanf("%d",&t);
    32.     while(t--)
    33.     {
    34.         int sum=0;
    35.         struct node *list1,*list2,*p,*q;
    36.         scanf("%d",&n);
    37.         list1=creat(n);
    38.         list2=creat(n);
    39.         p=list1->next;
    40.         q=list2->next;
    41.         while(n--)
    42.         {
    43.             //printf("%d %d\n",p->num,q->num);
    44.             if(p->num == q->num)
    45.                 sum++;
    46.             p=p->next;
    47.             q=q->next;
    48.         }
    49.         printf("%d\n",sum);
    50.     }
    51.     return 0;
    52. }

    链表插入

    1. #include
    2. #include
    3. struct node
    4. {
    5.     int num;
    6.     struct node * next;
    7. };
    8.  
    9. struct node * creat(int n)
    10. {
    11.     int data;
    12.     struct node * head,*p,*q;
    13.     head = (struct node*)malloc(sizeof(struct node));
    14.     head -> next=NULL;
    15.     p=head;
    16.     while(n--)
    17.     {
    18.         scanf("%d",&data);
    19.         q = (struct node*)malloc(sizeof(struct node));
    20.         q -> num = data;
    21.         q -> next = NULL;
    22.         p -> next = q;
    23.         p=q;
    24.     }
    25.     return head;
    26. }
    27.  
    28. void in(struct node * head,int data)
    29. {
    30.     struct node * newNode =(struct node *)malloc(sizeof(struct node));
    31.     newNode->num =data;
    32.     newNode->next=NULL;
    33.     struct node * Move=head->next;
    34.     if(data <= Move->next->num)
    35.     {
    36.         newNode->next=Move->next;
    37.         Move->next=newNode;
    38.     }
    39.     else
    40.     {
    41.         while(Move != NULL)
    42.         {
    43.             if(data>Move->num&&datanext->num)
    44.             {
    45.                 newNode->next=Move->next;
    46.                 Move->next=newNode;
    47.                 break;
    48.             }
    49.             Move=Move->next;
    50.             if(Move->next==NULL&&data>Move->num)
    51.             {
    52.                 Move->next=newNode;
    53.                 break;
    54.             }
    55.         }
    56.     }
    57. }
    58. void print(struct node * head)
    59. {
    60.     struct node * pMove;
    61.     pMove=(struct node *)malloc(sizeof(struct node));
    62.     pMove=head->next->next;
    63.     while(pMove!=NULL)
    64.     {
    65.         printf("%d ",pMove->num);
    66.         pMove=pMove->next;
    67.     }
    68.     printf("\n");
    69. }
    70. int main()
    71. {
    72.     int n,dataa;
    73.     struct node * list;
    74.     scanf("%d",&n);
    75.     list=creat(n);
    76.     dataa=list->next->num;
    77.     //printf("%d",data);
    78.     in(list,dataa);
    79.     print(list);
    80.     return 0;
    81. }

    链表查找

    1. #include
    2. #include
    3. struct node
    4. {
    5.     int num;
    6.     struct node * next;
    7. };
    8.  
    9. struct node * creat(int n)
    10. {
    11.     int data;
    12.     struct node * head,*p,*q;
    13.     head = (struct node*)malloc(sizeof(struct node));
    14.     head -> next=NULL;
    15.     p=head;
    16.     while(n--)
    17.     {
    18.         scanf("%d",&data);
    19.         q = (struct node*)malloc(sizeof(struct node));
    20.         q -> num = data;
    21.         q -> next = NULL;
    22.         p -> next = q;
    23.         p=q;
    24.     }
    25.     return head;
    26. }
    27. void fun(struct node * head)
    28.     struct node * Move;
    29.     Move=(struct node*)malloc(sizeof(struct node));
    30.     Move=head->next;
    31.     int min=Move->num;
    32.     while(Move!=NULL)
    33.     {
    34.         if(min>Move->num)
    35.         {
    36.             min=Move->num;
    37.         }
    38.         Move=Move->next;
    39.     }
    40.     Move=head->next;
    41.     if(min == Move->num)
    42.         return 0;
    43.     else
    44.     {
    45.         struct node * p;
    46.         p=(struct node*)malloc(sizeof(struct node));
    47.         while(Move!=NULL)
    48.         {
    49.            if(Move->next->num == min)
    50.             {
    51.               p=Move->next;
    52.               Move->next=Move->next->next;
    53.               p->next=head->next;
    54.               head->next=p;
    55.               break;
    56.             }
    57.          Move=Move->next;
    58.         }
    59.     }
    60. }
    61. void print(struct node * head)
    62. {
    63.     struct node * pMove;
    64.     pMove=(struct node *)malloc(sizeof(struct node));
    65.     pMove=head->next;
    66.     while(pMove!=NULL)
    67.     {
    68.         printf("%d ",pMove->num);
    69.         pMove=pMove->next;
    70.     }
    71.     printf("\n");
    72. }
    73. int main()
    74. {
    75.     int n,dataa;
    76.     struct node * list;
    77.     scanf("%d",&n);
    78.     list=creat(n);
    79.     fun(list);
    80.     print(list);
    81.     return 0;
    82. }

    链表排列

    1. #include
    2. #include
    3. struct node
    4. {
    5.     int num;
    6.     struct node * next;
    7. };
    8.  
    9. struct node * creat(int n)
    10. {
    11.  struct node * head,*p,*q;
    12.  head=(struct node *)malloc(sizeof(struct node));
    13.  head->next=NULL;
    14.  p=head;
    15.  while(n--)
    16.  {
    17.     q=(struct node *)malloc(sizeof(struct node));
    18.     scanf("%d",&q->num);
    19.     q->next=NULL;
    20.     p->next=q;
    21.     p=q;
    22.  }
    23.  return head;
    24. }
    25. void fun(struct node * head)
    26. {
    27.     int temp;
    28.     struct node *i,*j;
    29.     for(i=head->next;i!=NULL;i=i->next)
    30.     {
    31.         for(j=i->next;j!=NULL;j=j->next)
    32.         {
    33.             if(j->num < i->num)
    34.             {
    35.                 temp = j->num;
    36.                 j->num = i->num;
    37.                 i->num = temp;
    38.             }
    39.         }
    40.     }
    41. }
    42. void print(struct node * head)
    43. {
    44.     struct node * pMove;
    45.     pMove=(struct node *)malloc(sizeof(struct node));
    46.     pMove=head->next;
    47.     while(pMove!=NULL)
    48.     {
    49.         printf("%d ",pMove->num);
    50.         pMove=pMove->next;
    51.     }
    52.     printf("\n");
    53. }
    54. int main()
    55. {
    56.     struct node * list;
    57.     int n;
    58.     scanf("%d",&n);
    59.     getchar();
    60.     list=creat(n);
    61.     fun(list);
    62.     print(list);
    63.     return 0;
    64. }

    链表去重排序

    1. #include
    2. #include
    3. struct node
    4. {
    5.     int num;
    6.     struct node * next;
    7. };
    8. struct node *creat(int n)
    9. {
    10.     struct node * head,*p,*q;
    11.     head=(struct node *)malloc(sizeof(struct node));
    12.     head->next=NULL;
    13.     p=head;
    14.     while(n--)
    15.     {
    16.         q=(struct node *)malloc(sizeof(struct node));
    17.         scanf("%d",&q->num);
    18.         q->next=NULL;
    19.         p->next=q;
    20.         p=q;
    21.     }
    22.     return head;
    23. }
    24.  
    25. void print(struct node * head)
    26. {
    27.     struct node * pMove;
    28.     pMove=(struct node *)malloc(sizeof(struct node));
    29.     pMove=head->next;
    30.     while(pMove!=NULL)
    31.     {
    32.         printf("%d ",pMove->num);
    33.         pMove=pMove->next;
    34.     }
    35.     printf("\n");
    36. }
    37.  
    38. void delet(struct node * head,int data)
    39. {
    40.     struct node * posNode=head->next;
    41.     struct node * posNodeFront=head;
    42.     while(posNode!=NULL)
    43.     {
    44.         if(posNode -> num == data)
    45.         {
    46.             posNodeFront->next =posNode->next;
    47.             free(posNode);
    48.             posNode=posNodeFront->next;
    49.  
    50.         }
    51.         else
    52.         {
    53.             posNodeFront=posNode;
    54.             posNode=posNode->next;
    55.         }
    56.  
    57.     }
    58. }
    59.  
    60. void fun(struct node * head1,struct node * head2)
    61. {
    62.     int sign[1001]= {0},si[1001]= {0};
    63.     struct node *Move1,*Move2;
    64.     Move1=head1->next;
    65.     Move2=head2->next;
    66.     while(Move1!=NULL)
    67.     {
    68.         sign[Move1->num]++;
    69.         Move1=Move1->next;
    70.     }
    71.     while(Move2!=NULL)
    72.     {
    73.         si[Move2->num]++;
    74.         Move2=Move2->next;
    75.     }
    76.     /*
    77.     Move1=head1;
    78.     Move2=head2;
    79.     */
    80.     for(int i=0; i<1001; i++)
    81.     {
    82.         if(sign[i]>=1&&si[i]>=1)
    83.         {
    84.             for(int j=0; j
    85.             {
    86.                 delet(head1,i);
    87.                 delet(head2,i);
    88.             }
    89.         }
    90.     }
    91.     //print(head1);print(head2);
    92. }
    93.  
    94. void fun2(struct node * head)
    95. {
    96.     int temp;
    97.     struct node *i,*j;
    98.     for(i=head->next; i!=NULL; i=i->next)
    99.     {
    100.         for(j=i->next; j!=NULL; j=j->next)
    101.         {
    102.             if(j->num < i->num)
    103.             {
    104.                 temp = j->num;
    105.                 j->num = i->num;
    106.                 i->num = temp;
    107.             }
    108.         }
    109.     }
    110. }
    111.  
    112. void fun3(struct node * head)
    113. {
    114.     int temp;
    115.     struct node *i,*j;
    116.     for(i=head->next; i!=NULL; i=i->next)
    117.     {
    118.         for(j=i->next; j!=NULL; j=j->next)
    119.         {
    120.             if(j->num > i->num)
    121.             {
    122.                 temp = j->num;
    123.                 j->num = i->num;
    124.                 i->num = temp;
    125.             }
    126.         }
    127.     }
    128. }
    129.  
    130. int main()
    131. {
    132.     int m,n;
    133.     while(~scanf("%d%d",&m,&n))
    134.     {
    135.         struct node *list1,*list2;
    136.         list1=creat(m);
    137.         list2=creat(n);
    138.         //print(list1);print(list2);
    139.         fun2(list1);
    140.         fun3(list2);
    141.         //print(list1);print(list2);
    142.         fun(list1,list2);
    143.         print(list1);
    144.         print(list2);
    145.     }
    146.     return 0;
    147. }
    148.

    单链表反转

    1. 思路就是两个两个的循环，设置当前位置，父亲位置，和儿子位置，并随着循环改变位置，两个两个的改变箭头方向，画个图就能很形象的理解解题步骤。 
    2. /**
    3.  * Definition for singly-linked list.
    4.  * struct ListNode {
    5.  *     int val;
    6.  *     ListNode *next;
    7.  *     ListNode() : val(0), next(nullptr) {}
    8.  *     ListNode(int x) : val(x), next(nullptr) {}
    9.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    10.  * };
    11.  */
    12. class Solution {
    13. public:
    14.     ListNode* reverseList(ListNode* head) {
    15.         struct ListNode *p,*q;
    16.         p=head;
    17.         q=nullptr;
    18.         while(p){
    19.             ListNode *t=p->next;
    20.             p->next=q;
    21.             q=p;
    22.             p=t;
    23.         }
    24.         return q;
    25.     }
    26. };

    链表中环的检测

    1.  * Definition for singly-linked list.
    2.  * struct ListNode {
    3.  *     int val;
    4.  *     ListNode *next;
    5.  *     ListNode(int x) : val(x), next(NULL) {}
    6.  * };
    7.  */
    8. class Solution {
    9. public:
    10.     mapint> m;
    11.     ListNode *detectCycle(ListNode *head) {
    12.         while(head){
    13.             if(m[head]!=NULL) return head;//如果该点被记录过，则该点为入口点
    14.             m[head]=1;
    15.             head=head->next;
    16.         }
    17.         return NULL;
    18.     }
    19. };
    20. ```
    21. 利用map标记遍历过的结点即可。在遍历中先进行判断。

    两个有序链表合并

    1. * Definition for singly-linked list.
    2.  * struct ListNode {
    3.  *     int val;
    4.  *     ListNode *next;
    5.  *     ListNode() : val(0), next(nullptr) {}
    6.  *     ListNode(int x) : val(x), next(nullptr) {}
    7.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    8.  * };
    9.  */
    10. class Solution {
    11. public:
    12.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    13.         ListNode Head(0);//创建新空链表
    14.         ListNode *p= &Head;//让p代表head
    15.         while(l1 && l2){//当l1和l2都没到结尾时
    16.             if(l1->val > l2->val) swap(l1,l2);
    17.             p->next=l1;
    18.             l1=l1->next;
    19.             p=p->next;
    20.         }
    21.         p->next =l1?l1:l2;
    22.         return Head.next;
    23.     }
    24. };

    删除链表倒数第n个节点

    1. 删除链表的倒数第N个结点，即链表的第len-n个结点。
    2. 我们设置快慢指针。让快指针先走n步，再让快慢指针一起走。
    3. tip:为了防止空指针问题，我们应该设置一个头结点，它的next为head。
    4. 创建： ListNode anspre=new ListNode(-1); 
    5. 然后令快慢指针等于该带有头结点的链表。
    6. fast=anspre;
    7. slow=anspre;
    8. 初始时：
    9. 	🎈快指针所在结点处：n-1
    10. 	🎈慢指针所在结点处：0-1
    11. 直到快指针为空
    12. 	✨len-1
    13.     ✨len-n-1(此时，慢指针位置是倒数第n个结点的前一个结点，可以通过slow-》next=slow-》next-》next达到删除结点的目的)
    14. 	
    15. ```
    16. class Solution {
    17. public:
    18.     ListNode* removeNthFromEnd(ListNode* head, int n) {
    19.         ListNode *fast,*slow;
    20.         ListNode *anspre=new ListNode(-1); 
    21.         anspre->next=head;
    22.         if(head==NULL)return {};
    23.         fast=anspre;
    24.         slow=anspre;
    25.         for(int i=0;i<=n;i++){
    26.             fast=fast->next;
    27.         }
    28.         while(fast!=NULL){
    29.             fast=fast->next;
    30.             slow=slow->next;
    31.         }
    32.         slow->next=slow->next->next;
    33.         return anspre->next;
    34.     }
    35. };

    求链表的中间节点

    快慢指针，一个一次走两步，一个一次走一步，快指针到达末尾时，慢指针在中间结点处。

    合并链表并排序

    1. #include
    2. #include
    3. struct node
    4. {
    5.     int num;
    6.     struct node * next;
    7. };
    8.  
    9. struct node * creat(int n)
    10. {
    11.  struct node * head,*p,*q;
    12.  head=(struct node *)malloc(sizeof(struct node));
    13.  head->next=NULL;
    14.  p=head;
    15.  while(n--)
    16.  {
    17.     q=(struct node *)malloc(sizeof(struct node));
    18.     scanf("%d",&q->num);
    19.     q->next=NULL;
    20.     p->next=q;
    21.     p=q;
    22.  }
    23.  return head;
    24. }
    25. void print(struct node * head)
    26. {
    27.     struct node * pMove;
    28.     pMove=(struct node *)malloc(sizeof(struct node));
    29.     pMove=head->next;
    30.     while(pMove!=NULL)
    31.     {
    32.         printf("%d ",pMove->num);
    33.         pMove=pMove->next;
    34.     }
    35.     printf("\n");
    36. }
    37.  
    38. struct node * fun(struct node * head1,struct node * head2)
    39. {
    40.     struct node * Move;
    41.     Move=head1->next;
    42.     while(Move->next!=NULL)
    43.     {
    44.         Move=Move->next;
    45.     }
    46.     Move->next=head2->next;
    47.     Move=head1;
    48.     return Move;
    49. }
    50. void funnn(struct node * head)
    51. {
    52.     int temp;
    53.     struct node *i,*j;
    54.     for(i=head->next;i!=NULL;i=i->next)
    55.     {
    56.         for(j=i->next;j!=NULL;j=j->next)
    57.         {
    58.             if(j->num > i->num)
    59.             {
    60.                 temp = j->num;
    61.                 j->num = i->num;
    62.                 i->num = temp;
    63.             }
    64.         }
    65.     }
    66. }
    67. int main()
    68. {
    69.     int m,n;
    70.     struct node *mlist,*nlist,*list;
    71.     scanf("%d",&m);
    72.     mlist=creat(m);
    73.     scanf("%d",&n);
    74.     nlist=creat(n);
    75.     list=fun(mlist,nlist);
    76.     funnn(list);
    77.     print(list);
    78.     return 0;
    79. }

  • 相关阅读:
    Windows系统下使用tar命令，压缩文件与解压缩文件并指定路径
    黑客帝国：随机字母生成器
    《儿童教育心理学》读书笔记
    Vue框架（三）------quasar组件使用及文件上传
    如何撰写综述性论文
    Arcgis如何制作专题地图中漂亮的饼图
    Docker安装可视化管理器Portainer
    MySQL学习笔记（1）——简单操作
    uniapp：录音权限检查，录音功能
    华为HCIP认证用处大吗？
  • 原文地址：https://blog.csdn.net/m0_62742402/article/details/126582557