01 数据结构与算法之单向链表（C语言实现）

链表基础概念请参考其他书籍或文章。本文只列出完整测试代码

实现链表代码 头指针法(需要特判)，采用虚头节点，节省特判操作。

插入示例：

Node *p = &(l->head), *node = getNewNode(val);
while (ind--) p = p->next;
node->next = p->next;
p->next = node;

#include 
#include 
#include 
//结构定义
typedef struct Node {
	int data;
    struct Node *next;
} Node;
typedef struct List {
    Node head;//Node head虚拟头节点，注意与Node *head的区别
    int length;
} List;
//函数声明
Node *getNewNode(int);
List *init_list();
void clear_node(Node *);
int insert(List *, int, int);
int erase(List *, int);

Node *getNewNode(int val) {//创建初始化节点
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = val;
    node->next = NULL;
    return node;
}
List *init_list(){//创建初始化链表
    List *l = (List *)malloc(sizeof(List));
    l->head.next = NULL;//点是变量的访问，->是访问地址
    l->length = 0;
    return l;
}
int insert(List *l, int ind, int val){
    if (l == NULL) return 0;
    if (ind < 0 || ind > l->length) return 0;
    Node *p = &(l->head), *node = getNewNode(val);
    while (ind--) p = p->next;
    node->next = p->next;
    p->next = node;
    l->length++;
    return 1;
}
int erase(List *l, int ind) {
    if(l == NULL) return 0;
    if(ind < 0 || ind >= l->length) return 0;
    Node *p = &(l->head), *q;
    while(ind--) p = p->next;
    q = p->next;
    p->next = q->next;
    clear_node(q);
    l->length -= 1;
    return 1;
}
void reverse(List *l){
    if(l ==NULL) return;
    Node *p = l->head.next, *q;//p = l->head.next指向第一个节点
    l->head.next = NULL;//取下头节点
    while(p) {
        q = p->next;
        p->next = l->head.next;
	l->head.next = p;
        p = q;
    }
    return ;
}
void output(List *l){
    if(l ==NULL) return;
    printf("list(%d) :", l->length);
    for(Node *p = l->head.next; p; p = p->next) {
        printf("%d->", p->data);
    }
    printf("NULLn");
    return ;
}
void clear_node(Node *node){//删除节点
    if (node == NULL) return;
    free(node);
    return ;
}
void clear(List *l){//删除链表
    if (l == NULL) return;
    Node *p = l->head.next, *q;
    while (p) {
        q = p->next;
        clear_node(p);
        p = q;
    }
    free(l);
    return ;
}
int main() {
	srand(time(0));
    #define MAX_OP 20
    List *l =init_list();
    for (int i = 0; i < MAX_OP; i++){
        int val = rand() % 100;
        int ind = rand() % (l->length +3) - 1;
        int op = rand() % 4; // 百分之25的概率插入，因为case为0 1 2 3
        switch (op) {
            case 0:
            case 2:{
                printf("reverse the list!n");
                reverse(l);
                output(l), printf("n");
            }
            case 1:{
                printf("insert %d at %d to List = %dn", val, ind ,insert(l, ind, val));
            }break;
            case 3:{
                printf("erase a item at %d from List = %dn",ind, erase(l, ind));
            }break;
        }
        output(l), printf("n");
    }
    clear(l);
    #undef MAX_OP
	return 0;
}