单向链表

oneway_list.h：

#ifndef _ONEWAY_LIST_
#define _ONEWAY_LIST_

#include <stdio.h>

#define SUCC 1
#define FAIL 0

#define show_str(fmt, ...)\
    printf("%%Tips: %s %d %s: " fmt, __FILE__, __LINE__, __FUNCTION__, ##__VA_ARGS__)

typedef struct node_s {
    int integer;
    struct node_s *next;
}node_t;

typedef struct list_s {
    node_t *first, *last;
}list_t;

void destroy_list(list_t *lst);
int insert_to_list(list_t *lst, int element);
int del_from_list(list_t *lst, int element);
void display_list(list_t *lst);

#endif

oneway_list.c:

 

/* create by fishmwei */
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#include "oneway_list.h"

/**
 * destroy_list- 清空链表
 *
 * @lst:要清空链表的指针
 *
 */
void destroy_list(list_t *lst)
{
    node_t *index, *index_n;

    if (lst == NULL) {
        return;
    }

    index = lst->first;
    while (index) {
        index_n = index->next;
        free(index);
        index = index_n;
    }

    lst->first = NULL;
    lst->last = NULL;
    show_str("destroy list!\n");
}

/**
 * insert_to_list - 往链表插入新元素
 *
 * @lst:插入到的链表的指针
 * @element: 新元素值
 *
 * 成功返回SUCC,失败返回FAIL
 */
int insert_to_list(list_t *lst, int element)
{
    node_t *index, *new_node, *prev;

    if (lst == NULL) {
        show_str("bad para\n");
        return FAIL;
    }

    new_node = (node_t *)malloc(sizeof(node_t));
    if (new_node == NULL) {
        show_str("alloc memory failed\n");
        return FAIL;
    }
    memset(new_node, 0, sizeof(node_t));
    new_node->integer = element;

    index = lst->first;
    if (index == NULL) {
        lst->first = new_node;
        lst->last = new_node;
        show_str("new node become the first node\n");
        return SUCC;
    }

    if (index->integer > element) {
        new_node->next = lst->first;
        lst->first = new_node;
        show_str("new node become the first node\n");
        return SUCC;
    } else if (index->integer == element) {
        show_str("repeat with the first node\n");
        free(new_node);
        return SUCC;
    }

    prev = index;
    index = index->next;
    while (index) {
        if (index->integer == element) {
            show_str("repeat with other node\n");
            free(new_node);
            return SUCC;
        } else if (index->integer > element) {
            /* 插入之前 */
            new_node->next = index;
            prev->next = new_node;
            show_str("insert before %d\n", index->integer);
            return SUCC;
        } else {
         prev = index;
            index = index->next;
        }
    }

    show_str("new node become the last node\n");
    lst->last->next = new_node;
    lst->last = new_node;

    return SUCC;
}

/**
 * del_from_list -从链表中删除对应元素的成员
 *
 * @lst:链表指针
 * @element: 要删除的元素
 *
 * 成功返回SUCC,失败返回FAIL
 */
int del_from_list(list_t *lst, int element)
{
    node_t *index, *prev;

    if (lst == NULL) {
        show_str("bad para\n");
        return FAIL;
    }

    index = lst->first;
    if (index == NULL) {
        show_str("lst is NULL list\n");
        return FAIL;
    }

    if (index->integer == element) {
        lst->first = index->next;
        free(index);
        show_str("del the first node\n");
        return SUCC;
    } else if (index->integer > element) {
        show_str("no the elememt, del %d failed\n", element);
        return FAIL;
    }

    prev = index;
    index = index->next;
    while (index) {
        if (index->integer == element) {
            prev->next = index->next;
            free(index);
            show_str("del %d SUCCESS\n", element);
            return SUCC;
        } else if (index->integer > element) {
            show_str("no the elememt, del %d failed\n", element);
            return FAIL;
        } else {
         prev = index;
            index = index->next;
        }
    }

    show_str("no the elememt, del %d failed\n", element);

    return FAIL;
}

/**
 * display_list -显示链表中的所有元素
 *
 * @lst:链表的指针
 *
 */
void display_list(list_t *lst)
{
    node_t *index;

    if (lst == NULL) {
        show_str("bad para\n");
        return;
    }

    printf("list:\n");

    if (lst->first == NULL) {
        printf("lst is a NULL list\n");
        return;
    }

    index = lst->first;
    while (index) {
        printf("%d\t", index->integer);
        index = index->next;
    }

    printf("\n");
}

/* 测试主程序 */
int main(void)
{
    int op, num;
    list_t test_lst;

    test_lst.first = NULL;
    test_lst.last = NULL;

    while (1) {
        printf("\nop: 1.add 2.del 3.quit\n");
        scanf("%d", &op);
        switch (op) {
        case 1:
            printf("input int to add\n");
            scanf("%d", &num);
            insert_to_list(&test_lst, num);
            display_list(&test_lst);
            break;
        case 2:
            printf("input int to del\n");
            scanf("%d", &num);
            del_from_list(&test_lst, num);
            display_list(&test_lst);
            break;
        case 3:
            goto quit;
        default:
            show_str("input error\n");
            break;
        }
    }

quit:
    destroy_list(&test_lst);

    return 0;
}