力扣刷题日记/day3/2022.6.25

新手村

C语言理解

链表的有关概念

逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）

线性表的链式存储结构生成的表，称作“链表”。

链表中数据元素由两部分组成，数据域和指针域

每个数据元素的存储结构称之为节点，节点之间通过指针域相互链接，形成一个链表

如果每个节点只包含一个指针域，那么这个链表被称为线性链表或单链表

链表的实现

链表中存放的不是基本数据类型，需要用结构体实现自定义

typedef struct Link{
    char elem;//代表数据域
    struct Link * next;//代表指针域，指向直接后继元素
}link;

理解：

typedef函数的作用是建立已经定义好的数据类型的别名。

形式为：typedef  已有变量名  别名;

通俗的来说就是给已有数据类型另起一个名字

上述使用typedef函数，将struct  Link已有变量名另起一个名字为link，两者等价

下面介绍第二种写法：

第一行语句，Node和struct Node等价，

第二行语句中，struct Node* 是已有变量名，LinkList是别名

总结：

 

struct Node等价于Node

struct Node*等价于LinkList

Node的对象为结构体

LinkList的对象为指针域

LinkList L //定义一个指向结构体的指针变量L

Node *P 等价于 LinkList L  //Node*可以替代LinkList

**P指针取值运算

总结2：

假设我们定义一个指针p。
那么会经常使用到三个符号：
1，p；
2，*p;
3，&p;
初学者经常会感到很迷茫，到底这三个符号表示什么？

p是一个指针变量的名字，表示此指针变量指向的内存地址，如果使用%p来输出的话，它将是一个16进制数。

*p表示此指针指向的内存地址中存放的内容，一般是一个和指针类型一致的变量或者常量。 而我们知道，&是取地址运算符，&p就是取指针p的地址。

p指向的地址中的内容就用*p表示。

*p和**p的区别

int *p ：一级指针，表示p所指向的地址里面存放的是一个int类型的值
int **p ：二级指针，表示p所指向的地址里面存放的是一个指向int类型的指针（即p指向的地址里面存放的是一个指向int的一级指针）
例如：
int i=10; //定义了一个整型变量
int *p=&i; //定义了一个指针指向这个变量
int **p1=&p; //定义了一个二级指针指向p指针
那么取出10的值方式为：
printf(“i=[%d]\n”,*p);
printf(“i=[%d]\n”,**p1);

三个知识点

头节点，头指针，首元节点 

头节点:有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。

若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。

首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。

头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。

单链表中可以没有头结点，但是不能没有头指针！

链表的创建，查找，添加，删除（C语言）

万事开头难，初始化链表首先要做的就是创建链表的头结点或者首元结点。创建的同时，要保证有一个指针永远指向的是链表的表头，这样做不至于丢失链表。

//链表的创建
link * initLink(){
    link * p=(link*)malloc(sizeof(link));//创建一个头结点
    link * temp=p;//声明一个指针指向头结点，用于遍历链表
    //生成链表
    for (int i=1; i<5; i++) {
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        temp->next=a;
        temp=temp->next;
    }
    return p;
}

//节点的查询
int selectElem(link * p,int elem){
    link * t=p;
    int i=1;
    while (t->next) {
        t=t->next;
        if (t->elem==elem) {
            return i;
        }
        i++;
    }
    return -1;
}

//更改某节点的值，更新函数，其中，add 表示更改结点在链表中的位置，newElem 为新的数据域的值
link *amendElem(link * p,int add,int newElem){
    link * temp=p;
    temp=temp->next;//在遍历之前，temp指向首元结点
    //遍历到被删除结点
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    temp->elem=newElem;
    return p;
}

//链表的插入，实现思路
//将新结点的next指针指向插入位置后的结点；将插入位置前的结点的next指针指向插入结点；
link * insertElem(link * p,int elem,int add){
    link * temp=p;//创建临时结点temp
    //首先找到要插入位置的上一个结点
    for (int i=1; i<add; i++) {
        if (temp==NULL) {
            printf("插入位置无效\n");
            return p;
        }
        temp=temp->next;
    }    
    //创建插入结点c
    link * c=(link*)malloc(sizeof(link));
    c->elem=elem;
    //向链表中插入结点
    c->next=temp->next;
    temp->next=c;
    return  p;
}

//节点的删除，实现思路
//将结点从链表中摘下来;手动释放掉结点，回收被结点占用的内存空间;
link * delElem(link * p,int add){
    link * temp=p;
    //temp指向被删除结点的上一个结点
    for (int i=1; i<add; i++) {
        temp=temp->next;
    }
    link * del=temp->next;//单独设置一个指针指向被删除结点，以防丢失
    temp->next=temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
    free(del);//手动释放该结点，防止内存泄漏
    return p;
}

使用malloc函数申请的空间，一定要注意手动free掉。否则在程序运行的整个过程中，申请的内存空间不会自己释放（只有当整个程序运行完了以后，这块内存才会被回收），造成内存泄漏，别把它当成是小问题

理解

java中LinkedList对应链表

例题

 解题思路：

用两个指针，遍历单链表，快指针每次遍历两个节点，慢指针每次遍历一个节点，当快指针遍历完链表时，慢指针刚好遍历到中间

class Solution {
    public ListNode middleNode(ListNode head) {
            ListNode fast=head,slow=head;
            while(fast!=null && fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            return slow;
    }
}