[数据结构与算法]链表编程（C语言）

1.带头结点单链表

结点类型描述

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

基本操作定义

LinkList list_init();

void list_head_insert(LinkList L, ElemType e);

void list_tail_insert(LinkList L, ElemType e);

void list_insert(LinkList L, ElemType e, int position);//insert a new node at the nth position

void list_delete(LinkList L, int position);//delete the node of the nth position

void list_modify(LinkList L, ElemType e, int position);//modify the node of the nth position

ElemType list_find(LinkList L, int position);//find the data of the nth position

void list_display(LinkList L);

int list_length(LinkList L);

void list_empty(LinkList L);//wipe data(except head node)

void list_destroy(LinkList *L);//release all the space(include head node)

基本操作实现

LinkList list_init() {
    LinkList L = (LinkList) malloc(sizeof(LNode));

    L->data = 0;
    L->next = NULL;
    return L;
}

void list_head_insert(LinkList L, ElemType e) {
    LNode *new_node = (LNode *) malloc(sizeof(LNode));

    new_node->data = e;
    new_node->next = L->next;
    L->next = new_node;
}

void list_tail_insert(LinkList L, ElemType e) {
    LNode *new_node = (LNode *) malloc(sizeof(LNode));
    LNode *tail = L;

    while (tail->next) {
        tail = tail->next;
    }
    tail->next = new_node;
    new_node->data = e;
    new_node->next = NULL;
}

void list_insert(LinkList L, ElemType e, int position) {
    LNode *new_node = (LNode *) malloc(sizeof(LNode));
    LNode *p = L;

    while (--position) {
        p = p->next;
    }
    new_node->data = e;
    new_node->next = p->next;
    p->next = new_node;
}

void list_delete(LinkList L, int position) {
    LNode *p = L, *q = L->next;

    while (--position) {
        p = p->next;
        q = q->next;
    }
    p->next = q->next;
    free(q);
}

void list_modify(LinkList L, ElemType e, int position) {
    LNode *p = L;

    while (position--) {
        p = p->next;
    }
    p->data = e;
}

ElemType list_find(LinkList L, int position) {
    LNode *p = L;

    while (position--) {
        p = p->next;
    }
    return p->data;
}

void list_display(LinkList L) {
    LNode *p = L->next;

    if (!p) {
        printf("This is a empty single linked list.\n");
    } else {
        printf("All data are: ");
        while (p) {
            printf("%d%c", p->data, (p->next == NULL) ? 46 : 32);
            p = p->next;
        }
        printf("\n");
    }
}

int list_length(LinkList L) {
    LNode *p = L->next;
    int length = 0;

    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

void list_empty(LinkList L) {
    LNode *p;

    while (L->next) {
        p = L->next;
        L->next = p->next;
        free(p);
    }
}

void list_destroy(LinkList *L) {
    LNode *head = *L, *tmp;

    *L = NULL;
    while (head) {
        tmp = head->next;
        free(head);
        head = tmp;
    }
}

其他操作（交集，差集，合并，逆置，排序）

2.不带头结点单链栈

结点类型描述

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkStack;

基本操作定义

LinkStack stack_init();

void stack_push(LinkStack *S, int e);

int stack_pop(LinkStack *S);

void stack_destroy(LinkStack *S);

基本操作实现

LinkStack stack_init() {
    LinkStack S = NULL;
    return S;
}

void stack_push(LinkStack *S, int e) {
    LNode *new_node = (LNode *)malloc(sizeof(LNode));

    new_node->data = e;
    new_node->next = *S;
    *S = new_node;
}

int stack_pop(LinkStack *S) {
    LNode *p = *S;
    int val = p->data;

    *S = p->next;
    free(p);
    return val;
}

void stack_destroy(LinkStack *S) {
    LNode *p = *S;

    while (*S) {
        *S = p->next;
        free(p);
    }
}

3.循环单链表

结点类型描述

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

基本操作定义

LinkList list_init();

void list_head_insert(LinkList L, ElemType e);

void list_tail_insert(LinkList L, ElemType e);

void list_insert(LinkList L, ElemType e, int position);//insert a new node at the nth position

void list_delete(LinkList L, int position);//delete the node of the nth position

void list_modify(LinkList L, ElemType e, int position);//modify the node of the nth position

ElemType list_find(LinkList L, int position);//find the data of the nth position

void list_display(LinkList L);

int list_length(LinkList L);

void list_empty(LinkList L);//wipe data(except head node)

void list_destroy(LinkList *L);//release all the space(include head node)

基本操作实现

LinkList list_init() {
    LinkList L = (LinkList) malloc(sizeof(LNode));

    L->data = 0;
    L->next = L;
    return L;
}

void list_head_insert(LinkList L, ElemType e) {
    LNode *new_node = (LNode *) malloc(sizeof(LNode));

    new_node->data = e;
    new_node->next = L->next;
    L->next = new_node;
}

void list_tail_insert(LinkList L, ElemType e) {
    LNode *new_node = (LNode *) malloc(sizeof(LNode));
    LNode *tail = L;

    while (tail->next != L) {
        tail = tail->next;
    }
    tail->next = new_node;
    new_node->data = e;
    new_node->next = L;
}

void list_insert(LinkList L, ElemType e, int position) {
    LNode *new_node = (LNode *) malloc(sizeof(LNode));
    LNode *p = L;

    while (--position) {
        p = p->next;
    }
    new_node->data = e;
    new_node->next = p->next;
    p->next = new_node;
}

void list_delete(LinkList L, int position) {
    LNode *p = L, *q = L->next;

    while (--position) {
        p = p->next;
        q = q->next;
    }
    p->next = q->next;
    free(q);
}

void list_modify(LinkList L, ElemType e, int position) {
    LNode *p = L;

    while (position--) {
        p = p->next;
    }
    p->data = e;
}

ElemType list_find(LinkList L, int position) {
    LNode *p = L;

    while (position--) {
        p = p->next;
    }
    return p->data;
}

void list_display(LinkList L) {
    if (L->next == L) {
        printf("This is a empty circular single linked list.\n");
    } else {
        LNode *p = L->next;

        printf("All data are: ");
        while (p != L) {
            printf("%d%c", p->data, (p->next == L) ? 46 : 32);
            p = p->next;
        }
        printf("\n");
    }
}

int list_length(LinkList L) {
    LNode *p = L->next;
    int length = 0;

    while (p != L) {
        length++;
        p = p->next;
    }
    return length;
}

void list_empty(LinkList L) {
    LNode *p;

    while (L->next != L) {
        p = L->next;
        L->next = p->next;
        free(p);
    }
}

void list_destroy(LinkList *L) {
    LNode *head = (*L)->next, *tmp;

    while (head != *L) {
        tmp = head->next;
        free(head);
        head = tmp;
    }
    free(head);
    *L = NULL;
}

4.循环双链表

结点类型描述

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

基本操作定义

DLinkList list_init();

void list_insert(DLinkList L, ElemType e, int position);//insert a new node at the nth position

void list_delete(DLinkList L, int position);//delete the node of the nth position

void list_display(DLinkList L);

void list_empty(DLinkList L);//wipe data(except head node)

void list_destroy(DLinkList *L);//release all the space(include head node)

基本操作实现

DLinkList list_init() {
    DLinkList L = (DLinkList) malloc(sizeof(DNode));

    L->data = 0;
    L->next = L;
    L->prior = L;
}

void list_insert(DLinkList L, ElemType e, int position) {
    DNode *new_node = (DNode *)malloc(sizeof(DNode));
    DNode *p = L, *q = L->next;

    while (--position) {
        p = p->next;
        q = q->next;
    }
    new_node->data = e;
    new_node->next = q;
    new_node->prior = p;
    p->next = new_node;
    q->prior = new_node;
}

void list_delete(DLinkList L, int position) {
    DNode *p = L, *q = L->next;

    while (--position) {
        p = p->next;
        q = q->next;
    }
    p->next = q->next;
    q->next->prior = p;
    free(q);
}

void list_display(DLinkList L) {
    if (L->next == L) {
        printf("This is a empty circular double linked list.\n");
    } else {
        DNode *p = L->next;
        printf("All data are: ");
        while (p != L) {
            printf("%d%c", p->data, (p->next == L) ? 46 : 32);
            p = p->next;
        }
        printf("\n");
    }
}

void list_empty(DLinkList L) {
    DNode *p;

    while (L->next != L) {
        p = L->next;
        L->next = p->next;
        free(p);
    }
    L->prior = L;
}

void list_destroy(DLinkList *L) {
    DNode *head = (*L)->next, *tmp;

    while (head != *L) {
        tmp = head->next;
        free(head);
        head = tmp;
    }
    free(head);
    *L = NULL;
}