链表初步

最近也是开始入算法的坑，学校要求完成一个小的C语言项目实践，主要用到链表和文件处理，索性先对链表做一个简单的总结。

认识链表

要创建链表，我们首先要了解链表的本质：一连串的结构体或者说对象（由于是C语言，我在下文统一称为结构体），每个结构体中都保存了下个结构体的指针（当然，这并不绝对），也就是说，链表的存储并不是类似于数组的存放在一片连续的内存空间，而是存放在随机的内存空间中

现在，来创造一个简单的链表的结构

struct ListNode{
    int num;
    struct ListNode *next;
};//一般的表达方式
typedef struct ListNode{
    int num;
    struct ListNode *next;
}Node;//为了后文书写方便，我们直接定义类型Node

再来看看创建列表的一个单元

Node n1={n1.num=1, n1.next = NULL};
Node *n2;
n2->num=2;n2->next=NULL;//注意此处n2->num即指针n2指向的Node中的num

由于链表中我们会涉及到大量的地址操作，我们一般使用n2对应的创建方式

让我们再来创建一个真正的连续的链表

Node *n1;
n1->num=1;
Node *n2;
n2->num=2;
Node *n3;
n3->num=3;
n1->next=n2;
n2->next=n3;
n3->next=NULL;

(注意到了吗,根据约定成俗的规矩.链表的最后一个元素的next应当为NULL)

这种创建方式当然没什么大问题,但是值得注意的是,这些链表单元是出于堆空间的,注定是要在函数生成的,也就是说,在函数执行完毕后,它们所占用的空间将会被释放,这显然和我们的目的不符,所以一般我们会进行如下的改造

Node *n1=malloc(sizeof (Node));

这样,这些单元的空间将不会被自动释放

链表的创建

显然,按照上面的方法创建链表要一个个写,太过于不方便,也太过于缺乏实用性,所以我们选择写两个函数来完成链表的创建

首先是创建链表单元的函数

Node* creatNode(int x){
    Node *n1= malloc(sizeof (Node));
    n1->next=NULL;
    n1->num=x;
    return n1;
} 

很简单不做过多的赘述

Node *head=NULL;
Node *end=NULL;
void addNode(Node* n1){
    if(head==NULL){
        head=end=n1;
    }else{
        end->next=n1;
        end=n1;
    }
}

这里有必要简单的解释一下,我们创建了两个Node指针来保存链表的首尾如果链表为空,则新插入的链表单元为首尾,如果链表不为空,则将尾单元的next指向新插入的单元,再将尾单元更新为新插入的单元,还是很简单

链表对应单元的修改与删除

就像数组那样,链表也应当可以做到任意的增删改查,我相信看到这里的你肯定可以想到怎样进行删除,修改,查找等基础操作,但还是容许我讲讲

就像这样

void delete(Node *n1  ){
    Node* left=head;
    while(left->next!=n1 && left){
        left=left->next;
    }
    left->next=left->next->next;
    free(n1);
}

最后不要忘记释放对应的空间

然后呢再考虑修改，这个的原理和删除完全相同，我就不过多讲解了

链表对应单元的查找

还是很简单，可以通过一个指针来遍历链表找出符合要求的项

Node* select(int x){
    Node* left=head;
    while(left->num!=x && left !=NULL){
        left=left->next;
    }
    return left;
}

上面所提到的内容都属于链表中极为基础的部分,后续的与算法相关的内容我会新开一篇来讲

最后，本期镇楼图