数据结构——链表的封装

作者：冯老师,华清远见教育科技集团讲师。

链表是数据结构中基本的线性结构，在编程中使用的频率高，那么如何用封装思想来编写一个完整的链表操作呢？且看以下代码的实例。

/*功能：演示链表的操作方法 */
        /*作者： james */
        /*时间： 2014.7.16 */
        /*版本： v1.0 */
        /*说明：使用面向对象思想封装一个链表*/

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

        /* 定义链式节点结构体 */
        typedef struct _linknode_ {
                int data; /* 节点的数据域，存放数据 */
                struct _linknode_ *next; /* 节点的指针域，指向下一个节点 */
        }linknode_t;

        /* 定义链表描述结构体，对链表数据、标志位等的封装 */
        typedef struct _linklist_ {
                struct _linknode_ *head; /* 链表的头指针，指向头节点 */
                int clen; /* 当前链表的长度 */
                int tlen; /* 链表的总长度，表明上限 */
        }linklist_t;

        /* 创建链式节点 */
        linknode_t *create_linknode(int value);
        /* 初始化链表（创建一个带有头节点的空链表） */
        linklist_t *linklist_init(int len);
        /* 销毁一个链表资源 */
        int linklist_destroy(linklist_t *list);
        /* 插入链表节点（头部插入） */
        int linklist_insert(linklist_t *list, int value);
        /* 打印链表内容 */
        int linklist_show(linklist_t *list);
        /* 根据值删除链表一个节点（如有重复则只删第一个） */
        int linklist_delete(linklist_t *list, int obj);
        /* 修改指定链表节点的值 */
        int linklist_modify(linklist_t *list, int old, int new);

        /* 定位链表节点并返回该节点地址 */
        linknode_t *linklist_search(linklist_t *list, int obj);
        int main()
        {
                linklist_t *list = NULL;
                int value = 100;
                linknode_t *p = NULL;

                list = linklist_init(10);

               while (0 == linklist_insert(list, value))
                value += 100;

                linklist_delete(list, 100);

                linklist_modify(list, 150, 250);
                linklist_show(list);

                p = linklist_search(list, 2500);
                if (NULL != p)
                printf("search: %d\n", p->data);
                else
                puts("search: NULL");

                linklist_destroy(list);

                return 0;
        }

        linklist_t *linklist_init(int len)
        {
                linklist_t *list = NULL;

                list = malloc(sizeof(*list));
                list->head = create_linknode(0);
                list->clen = 0;
                list->tlen = len;
                return list;
        }

        int linklist_destroy(linklist_t *list)
        {
                linknode_t *p = list->head;
                linknode_t *tmp = NULL;

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

                free(list);

                return 0;
        }

        int linklist_insert(linklist_t *list, int value)
        {
                linknode_t *new = NULL;

                if (list->clen >= list->tlen)
                return -1;

                new = create_linknode(value);
                new->next = list->head->next;
                list->head->next = new;

                list->clen++;
                return 0;
        }

        linknode_t *create_linknode(int value)
        {
                linknode_t *node = NULL;

                node = malloc(sizeof(*node));
                node->data = value;
                node->next = NULL;

                return node;
        }

        int linklist_show(linklist_t *list)
        {
                linknode_t *p = list->head->next;

                while (NULL != p) {
                        printf("%5d", p->data);
                        p = p->next;
                }
                putchar('\n');

                return 0;
        }

        int linklist_delete(linklist_t *list, int obj)
        {
                linknode_t *p = list->head;
                linknode_t *tmp = NULL;

                while (NULL != p->next) {
                        if (p->next->data == obj)
                        break;
                        p = p->next;
                }

                if (p->next == NULL)
                return -1;

                tmp = p->next;
                p->next = tmp->next;
                free(tmp);

                list->clen--;
                return 0;
        }

        int linklist_modify(linklist_t *list, int old, int new)
        {
                linknode_t *p = list->head->next;

                while (NULL != p) {
                        if (p->data == old)
                        break;
                        p = p->next;
                }
                if (NULL == p)
                return -1;

                p->data = new;

                return 0;
        }
        linknode_t *linklist_search(linklist_t *list, int obj)
        {
                linknode_t *p = list->head->next;

                while (NULL != p) {
                        if (p->data == obj)
                        return p;
                        p = p->next;
                }

                return NULL;
        }