线性表之单链表（上）

单链表就是一个表结构最后存储的位置是下一个表结构的地址，一般通过p->next表示存储的下一个位置的地址

// link_list.h
typedef int data_t;

typedef struct node{
    data_t data;
    struct node *next;
}listnode, *linklist;

linklist list_create();
int list_tail_insert(linklist H, data_t value);
linklist list_get(linklist H, int pos);
int list_insert(linklist H, data_t value, int pos);
int list_show(linklist H);

// link_list.c
//
// Created by Lenovo on 2023/9/17.
//
# include <stdio.h>
# include <stdlib.h>
# include "link_list.h"

linklist list_create(){
    linklist H;

    H = (linklist)malloc(sizeof(listnode));
    if (H == NULL){
        printf("malloc failed\n");
        return H;
    }
    //申请完堆空间后对链表进行赋值，初始化
    H->data = 0;
    H->next = NULL;
}

int list_tail_insert(linklist H, data_t value){
    linklist p;
    linklist q;

    if (H == NULL){
        printf("H is NULL\n");
        return -1;
    }
    // 1 new node p
    if ((p=(linklist)malloc(sizeof(listnode))) == NULL){
        printf("malloc failed\n");
        return -1;
    }
    p->data = value;
    p->next = NULL;

    //2 locate locate ... tail node
    q = H;
    while(q->next != NULL){
        q = q->next;
    }
    //3 insert;
    q->next = p;
    return 0;
}

linklist list_get(linklist H, int pos){
    linklist p;
    int i;

    if (H == NULL){
        printf("H is NULL\n");
        return NULL;
    }
    if (pos == -1){  // 选择-1时，退出
        return H;
    }
    p = H;
    i = -1;
    while (i < pos){
        p = p->next;
        if (p == NULL){
            printf("pos is invalid\n");
            return NULL;
        }
        i++;
    }
    return p;
}

int list_insert(linklist H, data_t value, int pos){
    linklist p;
    linklist q;

    if (H == NULL){
        printf("H is NULL\n");
        return -1;
    }
    //1 locate node p （pos-1）
    p = list_get(H, pos-1);
    if (p == NULL){
        return -1;
    }
    //2 new node q
    if((q=(linklist)malloc(sizeof(listnode))) == NULL){
        printf("malloc is failed\n");
        return -1;
    }
    q->data = value;
    q->next = NULL;

    //3 insert
    q->next = p->next;
    p->next = q;
    return 0;
}

int list_show(linklist H){
    linklist p;

    if(H==NULL){
        printf("H is NULL\n");
        return -1;
    }
    p= H;
    while(p->next != NULL){
        printf("%d ", p->next->data);
        p = p->next;
    }
    puts("");
    return 0;
}

// test.c
//
// Created by Lenovo on 2023/9/17.
//
# include <stdio.h>
# include "link_list.h"

void text_get();

int main(){
    linklist H;
    int value;

    H = list_create();
    if(H==NULL){
        return -1;
    }
    printf("input:");
    while(1){
        scanf("%d", &value);
        if (value == -1){
            break;
        }
        list_tail_insert(H, value);
        printf("input:");
    }
    list_show(H);
    list_insert(H, 100, 2);
    list_show(H);

    return 0;
}

void test_get(){
    linklist H;
    int value;
    linklist p;

    H = list_create();
    if(H == NULL){
        return;
    }
    printf("input:");
    while (1){
        scanf("%d", &value);
        if(value == -1){
            break;
        }
        list_tail_insert(H, value);
        printf("input:");
    }
    list_show(H);

    p = list_get(H, 4);
    if(p!=NULL){
        printf("value=%d\n", p->data);
    }
}