數據結構——鏈表的封裝

作者：馮老師,華清遠見教育科技集團講師。

鏈表是數據結構中基本的線性結構，在編程中使用的頻率高，那么如何用封裝思想來編寫一個完整的鏈表操作呢？且看以下代碼的實例。

/*功能：演示鏈表的操作方法 */
        /*作者： 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;
        }