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

#define INIT_LEN 6

typedef struct node{
    int x;
    struct node * next;
}link;

link * initLink(link * head){
    link * pr = head, *p;
    int i, num;
    printf("输入数组%d个元素的值。\n", INIT_LEN);
    for(i = 0;i < INIT_LEN;i++){
        //create node
        p = (link*)malloc(sizeof(link));
        if(p == NULL) exit(EXIT_FAILURE);
        scanf("%d", &num);
        p->x = num;
        p->next = NULL;
        
        //link node
        pr->next = p;
        pr = p;
    }
    return head;
}

link * deleteLink(link * head, int num){
    link * p = head->next, *pr = head;
    while(p != NULL){ //带头结点的删除
        if(p->x == num) break;
        pr = p;
        p = p->next;
    }
    
    if(p == NULL){
        printf("NOT FOUND!\n");
    }else{
        pr->next = p->next;
        p->next = NULL;
        free(p);
    }
    
    return head;
}

link * insertLink(link * head, int num){// 带头结点的顺序插入
    //create node
    link * pt = (link*)malloc(sizeof(link));
    if(pt == NULL) exit(EXIT_FAILURE);
    pt->x = num;
    pt->next = NULL;
    
    if(head == NULL) head = pt;
    
    link * p = head;
    while(p->next != NULL && p->next->x < num)
        p = p->next;
    
    //when p->next->x >= num
    pt->next = p->next;
    p->next = pt;
    
    return head;
}

void printLink(link * head){
    link * p = head->next; //头结点内容不输出
    while(p != NULL){
        printf("%d ",p->x);
        p = p->next;
    }
    printf("\n");
}

void destoryLink(link * head){
    link * p = head;
    while(p != NULL){
        head = p->next;
        free(p);
        p = head;
    }
}

int main() {
    int cnt, del, add;
    link * head = (link*)malloc(sizeof(link)); // 带头结点
//    head = initLink(head);
    
    printf("此链表各个结点的数据域为：");
    printLink(head);
    
    printf("输入要插入的数据个数：");
    scanf("%d",&cnt);
    printf("输入要插入的数据x: ");
    for(int i = 0;i < cnt;i++){
        scanf("%d", &add);
        insertLink(head, add);
    }
    printf("当前链表各个结点的数据域为：");
    printLink(head);
    
    
    printf("输入要删除的数据x: ");
    scanf("%d", &del);
    deleteLink(head, del);
    
    printf("删除后链表各个结点的数据域为：");
    printLink(head);
    
    
    destoryLink(head);
    return 0;
    
}