/*
 * 线性表的链式存储结构（有头结点的单向链表）
 */
#ifndef LINKLIST_H__
#define LINKLIST_H__

// 单向链表元素类型定义
typedef int datatype;

/*
 * 单向链表结构
 */
typedef struct node_st {
    datatype data; // 数据结点
    struct node_st *next; // 指向下一个结点的指针
}linklist;

/*
 * 初始化，创建单向链表
 * 返回结构体类型的指针
 */
linklist *linklist_create();

/*
 * 初始化，创建单向链表
 * 传入一个二级指针的方式
 */
void linklist_init(linklist **);

/*
 * 销毁单向链表
 * 释放单向链表所占内存
 */
void linklist_destroy(linklist *);

/*
 * 判断单向链表是否为空
 */
int linklist_is_empty(linklist *);

/*
 * 获取单向链表中元素的个数
 */
int linklist_length(linklist *);

/*
 * 往单向链表中指定位置插入数据
 */
int linklist_insert_by_pos(linklist *, int, datatype *);

/*
 * 往单向链表中插入数据
 */
int linklist_insert(linklist *, datatype *);

/*
 * 从单向链表中指定位置删除数据
 */
int linklist_delete_by_pos(linklist *, int, datatype *);

/*
 * 从单向链表中删除数据
 */
int linklist_delete(linklist *, datatype *);

/*
 * 遍历单向链表
 */
void linklist_display(linklist *);

#endif

#include <stdio.h>
#include <stdlib.h>

#include "linklist.h"

/*
 * 初始化，创建单向链表
 * 返回结构体类型的指针
 */
linklist *linklist_create() {
    linklist *head; // 头结点
    head = malloc(sizeof(*head));
    if (head == NULL) {
        return NULL;
    }

    // 刚初始化的单向链表的头结点没有指向的下一个结点
    head->next = NULL;
    return head;
}

/*
 * 初始化，创建单向链表
 * 传入一个二级指针的方式
 */
void linklist_init(linklist **head) {
    *head = malloc(sizeof(**head));
    if (*head == NULL) {
        return; // 无返回值
    }

    // 刚初始化的单向链表的头结点没有指向的下一个结点
    (*head)->next = NULL;
    return; // 无返回值
}

/*
 * 销毁单向链表
 * 释放单向链表所占内存
 */
void linklist_destroy(linklist *head) {
    linklist *node, *next; // 当前结点，下一个结点
    for (node = head->next; node != NULL; node=next) {
        // 由于是一个有头的单向链表，第一个结点是头结点所指向的下一个结点
        next = node->next; // 获取下一个结点
        free(node); // 释放当前结点
    }
    free(head); // 释放头结点
    return; // 无返回值
}

/*
 * 判断单向链表是否为空
 */
int linklist_is_empty(linklist *head) {
    if (head->next == NULL) {
        // 头结点没有任何指向，说明链表为空
        return 0;
    }

    // 非空
    return -1;
}

/*
 * 获取单向链表中元素的个数
 */
int linklist_length(linklist *head) {
    linklist *node; // 当前结点
    int length = 0; // 链表长度，即链表元素的个数

    // 确保链表存在，且不为空表
    if (head == NULL || head->next == NULL) {
        return -1;
    }

    // 既然不是空表，必然存在第一个结点
    node = head->next;

    while (node != NULL) {
        length++; // 长度加 1
        node = node->next; // 指向到下一个结点
    }

    // 返回链表长度
    return length;
}

/*
 * 往单向链表中指定位置插入数据
 */
int linklist_insert_by_pos(linklist *head, int pos, datatype *data) {
    int i = 0; // 循环索引值
    linklist *prev = head, *node = NULL; // 前一个结点，新结点

    if (pos < 0) {
        // 插入的位置不对
        return -1;
    }

    // 通过 while 循环，走到要插入的位置，并且得到前一个结点
    while (i < pos && prev != NULL) {
        prev = prev->next;
        i++;
    }

    if (prev) {
        // 存在前一个结点
        // 给新结点开辟内存空间
        node = malloc(sizeof(*node));
        if (node == NULL) {
            // 内存空间分配失败
            return -2;
        }
        // 给新结点赋值
        node->data = *data;
        // 新结点的下一个结点，指向到前一个结点的下一个结点
        node->next = prev->next;
        // 前一个结点指向到新结点
        prev->next = node;

        // 成功插入
        return 0;
    } else {
        // 前一个结点不存在
        // 插入的位置不对
        return -1;
    }
}

/*
 * 往单向链表中插入数据
 */
int linklist_insert(linklist *head, datatype *data) {
    linklist *prev = head, *node; // 前一个结点，新结点

    // 通过 while 循环，走到要插入的位置
    while (prev->next && prev->next->data < *data) {
        // 升序插入
        prev = prev->next;
    }

    // 给新结点开辟内存空间
    node = malloc(sizeof(*node));
    if (node == NULL) {
        // 内存空间分配失败
        return -1;
    }

    // 给新结点赋值
    node->data = *data;
    // 新结点的下一个结点，指向到前一个结点的下一个结点
    node->next = prev->next;
    // 前一个结点指向到新结点
    prev->next = node;

    // 成功插入
    return 0;
}

/*
 * 从单向链表中指定位置删除数据
 */
int linklist_delete_by_pos(linklist *head, int pos, datatype *data) {
    int i = 0; // 循环索引值
    linklist *prev = head, *node; // 前一个结点，要删除的结点
    *data = -1; // 要删除的数据

    if (pos < 0) {
        // 删除元素的位置不对
        return -1;
    }

    // 通过 while 循环，走到要删除的位置，并且得到前一个结点
    while (i < pos && prev != NULL) {
        prev = prev->next;
        i++;
    }

    if (prev) {
        // 存在前一个结点
        // 要删除的结点指向到前一个结点的下一个结点，即得到要删除的结点
        node = prev->next;
        // 获取要删除的数据
        *data = node->data;
        // 将前一个结点的下一个结点，指向到要删除结点的下一个结点
        prev->next = node->next;
        // 释放要删除结点所占内存
        free(node);
        // 将要删除结点指向为 NULL
        node = NULL;

        // 删除成功
        return 0;
    } else {
        // 前一个结点不存在
        // 删除元素的位置不对
        return -1;
    }
}

/*
 * 从单向链表中删除数据
 */
int linklist_delete(linklist *head, datatype *data) {
    linklist *prev = head, *node; // 前一个结点，要删除的结点

    // 通过 while 循环，走到要删除的位置
    while (prev->next && prev->next->data != *data) {
        prev = prev->next;
    }

    if (prev->next == NULL) {
        // 不存在要删除的数据
        return -1;
    } else {
        // 要删除的结点指向到前一个结点的下一个结点，即得到要删除的结点
        node = prev->next;
        // 将前一个结点的下一个结点，指向到要删除结点的下一个结点
        prev->next = node->next;
        // 释放要删除结点所占内存
        free(node);
        // 将要删除结点指向为 NULL
        node = NULL;

        // 删除成功
        return 0;
    }
}

/*
 * 遍历单向链表
 */
void linklist_display(linklist *head) {
    linklist *node = head->next; // 当前结点

    if (linklist_is_empty(head) == 0) {
        // 空链表
        return; // 无返回值
    }

    while (node != NULL) {
        printf("%d ", node->data); // 打印当前结点的数据
        node = node->next; // 指向到下一个结点
    }
    printf("\n");

    return; // 无返回值
}

#include <stdio.h>
#include <stdlib.h>

#include "linklist.h"

int main() {
    int i; // 循环索引值
    int ret; // 返回状态值
    int len; // 链表长度
    linklist *list; // 单向链表
    // 两条测试数据
    datatype data1[] = {12, 81, 23, 76, 34, 62};
    datatype data2[] = {73, 45, 15, 61, 99, 56};
    // 指定要删除的数据
    int del_data = 76;
    // 保存要删除的数据
    datatype delete_data;

    /* 初始化单向链表 */
    list = linklist_create(); // 方法一
    //linklist_init(&list); // 方法二

    if (list == NULL) {
        fprintf(stderr, "初始化单向链表 list 失败！\n");
        exit(1);
    }

    /* 往单向链表中插入数据 */
    // 方法一：按升序插入（前提是新链表，或已经排序好的链表）
    for (i = 0; i < sizeof(data1)/sizeof(*data1); i++) {
        if ((ret = linklist_insert(list, &data1[i])) != 0) {
            if (ret == -1) {
                fprintf(stderr, "单向链表 list 数据插入的位置有误。\n");
            } else if (ret == -2) {
                fprintf(stderr, "内存空间分配失败。\n");
            } else {
                fprintf(stderr, "发生未知错误。\n");
            }
            exit(1);
        }
    }

    /* 遍历单向链表 */
    printf("单向链表 list 中的元素：");
    linklist_display(list);

    /* 获取单向链表中元素的个数 */
    len = linklist_length(list);
    printf("单向链表 list 中元素的个数：%d\n", len);

    /* 往单向链表中插入数据 */
    // 方法二：指定位置插入，这里按顺序依次插入
    for (i = 0; i < sizeof(data2)/sizeof(*data2); i++) {
        if ((ret = linklist_insert_by_pos(list, len + i, &data2[i])) != 0) {
            if (ret == -1) {
                fprintf(stderr, "单向链表 list 数据插入的位置有误。\n");
            } else if (ret == -2) {
                fprintf(stderr, "内存空间分配失败。\n");
            } else {
                fprintf(stderr, "发生未知错误。\n");
            }
            exit(1);
        }
    }

    /* 遍历单向链表 */
    printf("单向链表 list 中的元素：");
    linklist_display(list);

    /* 从单向链表中删除数据 */
    if ((ret = linklist_delete(list, &del_data)) != 0) {
        if (ret == -1) {
            printf("不存在要删除的数据。\n");
        } else {
            fprintf(stderr, "发生未知错误。\n");
            exit(1);
        }
    }

    ret = linklist_delete_by_pos(list, 2, &delete_data);
    if (ret == 0) {
        printf("数据 %d 已从单向链表 list 中删除。\n", delete_data);
    } else if (ret == -1) {
        fprintf(stderr, "从单向链表 list 中删除元素的位置有误。\n");
        exit(1);
    } else {
        fprintf(stderr, "发生未知错误。\n");
        exit(1);
    }

    /* 遍历单向链表 */
    printf("单向链表 list 中的元素：");
    linklist_display(list);

    /* 销毁单向链表 */
    linklist_destroy(list);

    exit(0);
}

OBJS=main.o linklist.o
CC=gcc
CFLAGS+=-c -Wall -g
linklist:$(OBJS)
    $(CC) $^ -o $@
%.o:%.c
    $(CC) $^ $(CFLAGS) -o $@
clean:
    $(RM) *.o linklist -r

root@RicenOS:~# make
gcc main.c -c -Wall -g -o main.o
gcc linklist.c -c -Wall -g -o linklist.o
gcc main.o linklist.o -o linklist
root@RicenOS:~# ./linklist
单向链表 list 中的元素：12 23 34 62 76 81
单向链表 list 中元素的个数：6
单向链表 list 中的元素：12 23 34 62 76 81 73 45 15 61 99 56
数据 34 已从单向链表 list 中删除。
单向链表 list 中的元素：12 23 62 81 73 45 15 61 99 56