算法学习记录(二)--链表部分

接上文，周五本来完成了题目5的学习，不过在实现代码过程中，遇到颇多挫折，对于指针的理解还不到位，因为写着写着大脑中就又十万个为什么了，花了很大力气弥补指针的知识，个人觉得c语言指针过不去，是达到没法熟练运用的。

关于链表

1. 面试最常考的数据结构，链表的增删改查都只需要20行代码即可搞定，比较适合面试
2. 链表是一个动态的数据结构，其操作要靠指针，需要较好的编程功底
3. 链表数据结构很灵活

理解：可以理解成无左(右)子结点的树，树基本都是用递归解决的，所以链表常常可以用递归操作

链表常用操作：

参考[轻松搞定面试中的链表题目]
1. 求单链表中结点的个数
2. 将单链表反转
3. 查找单链表中的倒数第K个结点（k > 0）
4. 查找单链表的中间结点
5. 从尾到头打印单链表
6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
7. 判断一个单链表中是否有环
8. 判断两个单链表是否相交
9. 求两个单链表相交的第一个节点
10. 已知一个单链表中存在环，求进入环中的第一个节点
11. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted

题目5. 倒序打印链表

思路1. 利用栈数据结构(其实所有倒序操作都应该第一时间考虑用栈)，先入栈再出栈就完成了逆序
扩展：数组逆序、字符串逆序
代码如下：

void printLinkListWithOppositeSort(struct Node *header){
    if(header == NULL) return;
    Stack *stack = NULL;
    initStack(&stack);
    struct Node *node = header;
    // 入栈
    while (node != NULL) {
        push(stack,node);
        node = node->next;
    }
    // 出栈，并打印
    while (!empty(stack)) {
        struct Node *topNode = pop(stack);
        printf("value=%d",topNode->value);
    }
}

思路2：用递归，递归本质上也是一个栈，每输出一个结点时，先输出它的下一个结点，再输出该结点，这样不停递归，到最后就先输出最后一个结点，然后上一个结点，最后实现倒序

void recursivlyprintLinkListWithOppositeSort(struct Node *header){
    if(header != NULL){
        if(header->next != NULL){
            recursivlyprintLinkListWithOppositeSort(header->next);
        }
        printf("%d",header->value);
    }
}

---

补充指针知识：

1. 关于指针的理解，从四个维度理解

参考[知乎-从四个属性的角度来理解c语言的指针]
变量的四个维度分别是：

1. 有用数据的地址
2. 有用数据的名字
3. 有用数据的值
4. 有用数据的类型

---

指针的四个维度：

1. 指针自己的值
2. 与*结合名
3. 有用数据的值
4. 有用数据的类型

---

举例如下：

int a = 1;
int *p = NULL;
p = &a;

理解：

整形变量a = (有用数据的地址，有用数据的名字，有用数据的值，有用数据的类型)
代入就是：
整形变量a = (0x123456, a , 1, int);
指针变量p = (指针自己的值，与*结合名，有用数据的值，有用数据的类型)
代入就是：
指针变量p = (0x123456, *p, 1, int);
所以:
p = &a ,//表示a的地址
*p = a, //表示a的值

---

我们容易犯晕的是p、p与&p，a与&a，本来一个变量好好的，与或者&一结合就废了，参考上边的理解，读一遍参考的文章，应该能理解了
上边没有说到&p，&p 是p指针自身的地址，与a没有任何关系

2. 函数中的参数指针

有1个疑惑：

1. 函数参数何时要用二级指针
   答案是：当传递的是指针地址时需要用，类似int **结构
   例如:

void fun(){
  int *p;
  memInit(&p);
}
void memInit(int **p_ref){ // 参数声明等价于：int **p_ref = &p;
  *p_ref = malloc(sizeof(int));
}

理解：

1. memInit传入的是指针p的地址，p_ref是一个声明的二级指针，更多得理解是一个声明形式
2. 类似于上边与*结合就表示有用数据的名字，所以*p_ref就表示&p，也就是实参指针p的地址
3. 多级指针其实就是：
   与*结合每一级指向上一级的值，指向上上一级的地址

多级指针的理解：

- (void)_test_pointer{
    int a = 1;
    int *p = &a;
    int **p_ref = &p; 
    int ***p_ref_ref = &p_ref; 
    
    NSLog(@"\n&a:%p\np:%p\n&p:%p\np_ref:%p\n*p_ref:%p\n&p_ref:%p\np_ref_ref:%p\n",&a,p,&p,p_ref,*p_ref,&p_ref,p_ref_ref);
}

输出结果如下：

2018-03-25 13:37:45.847319+0800 iOSLearnigDemo[1795:116542]
&a:0x7ffee1f7bb04
p:0x7ffee1f7bb04
&p:0x7ffee1f7baf8
p_ref:0x7ffee1f7baf8 //指向&p
*p_ref:0x7ffee1f7bb04 //指向p,也就是&a，即指向a的地址
&p_ref:0x7ffee1f7baf0
p_ref_ref:0x7ffee1f7baf0