// slist.h
#pragma once
#define NULL  0 
#include <stdio.h>
#include <stdlib.h>

typedef int type;

struct node {
    node* next;
    type data;
};

static node* h;
static int n;

node* head();

int size();

void ins_node(node* curr, node* succ);

void del_node(node* curr);

node* tail();

node* before_tail();

node* create_node(type data);

void traverse(node* cur);

void insert(type data, int nInsHead = 1);

void remove(type data, int nDelSame = 1);

void find(type data, int nFindMulti = 1);

void remove_all_form_head();

void remove_all_from_tail();

void remove_all(int nDelFromHead = 1);

node* selectsort(node* cur);

// list.cpp
#include "list.h"

node* head() {
    return h;
}

int size() {
    return n;
}

void ins_node(node* curr, node* succ) {
    if (!curr) {
        succ->next = h;
        h = succ;
    }
    else {
        succ->next = curr->next;
        curr->next = succ;
    }
    n++;
}

void del_node(node* curr) {
    if (!head()) return;
    node* succ = NULL;
    if (!curr) {
        succ = h;
        h = h->next;
    }
    else {
        if (!(succ = curr->next)) return;
        curr->next = succ->next;
    }
    if (succ) free(succ), n--;
    else h = NULL;
}

node* tail() {
    node* tail = NULL;
    for (; tail && tail->next; tail = tail->next);
    return tail;
}

node* before_tail() {
    node* before = NULL;
    for (; before && before->next && before->next->next; before = before->next);
    return before;
}

node* create_node(type data) {
    node* succ = (node*)malloc(sizeof(node));
    if (!succ) return NULL;
    succ->next = NULL;
    succ->data = data;
    return succ;
}

void insert(type data, int nInsHead) {
    node* succ = create_node(data);
    if (!succ) return;
    nInsHead ? ins_node(NULL, succ) : ins_node(tail(), succ);
}

void remove(type data, int nDelSame) {
    if (!head()) return;
    for (node* curr = head(); curr->next; curr = curr->next) {
        while (curr->data == data || curr->next->data == data) {
            if (curr->data == data) {
                del_node(NULL);
                if (!nDelSame || !(curr = head())) return;
            }
            else if (curr->next->data == data) {
                del_node(curr);
                if (!nDelSame || !curr->next) return;
            }
        }
    }
}

void find(type data, int nFindMulti) {
    int cnt = 0;
    for (node* curr = head(); curr; curr = curr->next) {
        if (curr->data == data) {
            cnt++;
            if (!nFindMulti) return;
            printf("data = [%2d] in list and node address = [%p]\n", curr->data, curr);
        }
    }
    printf("find [%d]'s data = [%d]\n", cnt, data);
}

void modify(type found, type data, int nModifyMulti) {
    int cnt = 0;
    for (node* curr = head(); curr; curr = curr->next) {
        if (curr->data == found) {
            cnt++;
            curr->data = data;
            if (!nModifyMulti) return;
        }
    }
    printf("modified [%d]'s datas\n", cnt);
}

void remove_all_form_head() {
    while (size()) del_node(NULL);
    n = 0, h = NULL;
}

void remove_all_from_tail() {
    while (size()) {
        node* p = before_tail();
        if (!p) return;
        del_node(p);
    }
    n = 0, h = NULL;
}

void remove_all(int nDelFromHead) {
    nDelFromHead ? remove_all_form_head() : remove_all_from_tail();
}

node* selectsort(node* cur) {
    node* p,q,small, n = 0;
    int temp;
    for(p = cur->next; p->next != NULL; p = p->next) {
        small = p;
        for(q = p->next; q; q = q->next) {
            if(q->data < small->data)
                small = q;
        }
        printf_s("第%d轮循环获得最小值为:%d, 此时链表为:", ++n, small->data);
        if(small != p) {
            temp = p->data;
            p->data = small->data;
            small->data = temp;
        }
        traverse(cur);
    }
    printf("输出排序后的数字:\n");
    return cur;
}

void traverse(node* cur) {
   if(!cur) return;
   for(node* p = cur->next; p; p = p->next) 
       printf_s("%d",  p->data);
}

// 测试代码
include "list.h"

void print_all() {
    for (node* p = head(); p; p = p->next)
        printf("[%2d], [%p]\n", p->data, p);
    printf("\n");
}

int main() {
    insert(1, 1);
    insert(2, 1);
    insert(0, 1);
    insert(1, 1);
    insert(3, 1);
    insert(2, 1);
    insert(3, 1);
    insert(4, 1);

    remove(1, 1);
    print_all();
    remove(2, 1);

    remove(3, 1);
    print_all();
    remove(4, 1);



    find(3, 1);
    remove_all_form_head();
    remove_all_from_tail();
    print_all();
    return 0;
}