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

/* 鏈表的結構體描述 */
typedef struct chain
{
    int data;
    struct chain *next;
} C;

/* 找到指定節點 */
C *find(C *head, int i)
{
    C *node = head;
    if (node == NULL)
        return NULL; // 若頭節點為空則退出
    while (i--)
    {
        node = node->next;
        if (node == NULL)
            return NULL; // 未找到
    }
    return node;
}

/* 鏈表節點的插入, 在i的後面插入 */
/* 不能在頭節點前插入節點 */
int insert(C *head, int i, int value)
{
    C *node, *new;
    if (i < 0)
        return 0;

    node = find(head, i); // 找到插入點
    if (node == NULL)
        return 0;

    // 創建新節點
    new = (C *)malloc(sizeof(C));
    if (new == NULL)
        return 0;
    new->data = value;

    new->next = node->next;
    node->next = new;
    return 1;
}

/* 鏈表節點的刪除 */
int delete(C* head, int i)
{
    C *prev, *node;
    if (i <= 0)
        return 0; // 頭節點不可刪除
    prev = find(head, i - 1);
    node = prev->next; // 要刪除的節點
    if (prev == NULL || node == NULL)
        return 0; // 節點不存在

    prev->next = node->next;
    free(node);
    return 1;
}








/* 以下為測試代碼 */
void show(C *head)
{
    C *node;
    for (node = head; node != NULL; node = node->next)
        printf("%d ", node->data);
    putchar('\n');
}

void destroy(C *head)
{
    C *node = head->next;
    C *p;
    while (node != NULL)
    {
        p = node->next;
        free(node);
        node = p;
    }
}

int main(void)
{
    C c = {0};
    c.data = 15; // 頭節點
    
    insert(&c, 0, 73);
    insert(&c, 1, -48);
    insert(&c, 2, -264);
    show(&c);

    insert(&c, 1, 185);
    show(&c);
    insert(&c, 3, 224);
    show(&c);
    insert(&c, 5, 1);
    show(&c);
    insert(&c, 6, 2);
    show(&c);

    putchar('\n');
    delete(&c, 7);
    show(&c);
    delete(&c, 3);
    show(&c);
    delete(&c, 4);
    show(&c);
    
    destroy(&c);
    return 0;
}

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

#define STEP 10 // 每次增加的容量

/* 順序表的結構體描述 */
typedef struct table
{
    int *data;
    int capacity; // 容量
    int length; // 當前擁有的數據個數
} T;

/* 順序表的插入操作，在i的前面插入 */
int insert(T *t, int i, int value)
{
    int j;
    void *ptr;

    if (i < 0 || i > t->length)
        return 0;

    if (t->capacity == t->length)
    {
        // 擴容
        t->capacity += STEP;
        ptr = realloc(t->data, t->capacity * sizeof(int));
        if (ptr == NULL)
            return 0; // 如果內存分配失敗, 則操作失敗
        t->data = (int *)ptr;
    }

    // 把len-1>=j>=i的內容向後移動到len>=j+1>=i+1處
    for (j = t->length - 1; j >= i; j--)
        t->data[j + 1] = t->data[j];
    
    t->length++;
    t->data[i] = value;
    return 1; // 成功
}

/* 順序表的刪除操作 */
int delete(T *t, int i)
{
    int j;
    if (i < 0 || i >= t->length)
        return 0; // 元素不存在
    
    // 後續內容向前移動
    // 把i+1<=j<=len-1移動到i<=j-1<=len-2處, 並捨棄i處的內容
    for (j = i + 1; j <= t->length - 1; j++)
        t->data[j - 1] = t->data[j];
    
    t->length--;
    return 1;
}








/* 以下為測試代碼 */
void show(T *t)
{
    int i;
    for (i = 0; i < t->length; i++)
        printf("%d ", t->data[i]);
    putchar('\n');
}

int main(void)
{
    T t = {0};

    insert(&t, 0, 15);
    insert(&t, 1, 73);
    insert(&t, 2, -48);
    insert(&t, 3, -264);
    show(&t);

    insert(&t, 1, 185);
    show(&t);
    insert(&t, 3, 224);
    show(&t);
    insert(&t, 5, 1);
    show(&t);
    insert(&t, 7, 2);
    show(&t);

    putchar('\n');
    delete(&t, 7);
    show(&t);
    delete(&t, 0);
    show(&t);
    delete(&t, 3);
    show(&t);
    delete(&t, 4);
    show(&t);
    
    free(t.data);
    return 0;
}