C封装单链表对象

SingleLinkedList(单链表)

github源码
特点：
1.用一组任意的存储单元存储数据元素，逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。
2.存储节点包含两个域：其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。

3.整个链表的存取必须从头指针开始，头指针表示链表中第一个节点的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为空（NULL）。
4.在单链表中，取得第i个元素必须从头指针出发寻找，因此单链表是非随机存取的存储结构。
5.在单链表中插入节点temp：

temp->next = p->next;
p->next = temp;

6.在单链表中删除节点temp：

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

7.在单链表中插入或删除一个节点时，仅需修改指针而不需要移动元素。
8.单链表获取、插入、删除元素的时间复杂度均为O(n)，因为找到第i个结点都必须首先找到第i-1个结点，while循环环体中的语句频度与被查元素在表中位置有关，若1<=i<=n,则频度为i-1，否则频度为n。

SingleLinkedList.c文件

#include <stdio.h>
#include <malloc.h>
#include "SingleLinkedList.h"

static void clear(SingleLinkedList *This);
static int isEmpty(SingleLinkedList *This);
static int length(SingleLinkedList *This);
static void print(SingleLinkedList *This);
static int indexElem(SingleLinkedList *This, ElemType* x);
static int getElem(SingleLinkedList *This, int index, ElemType *e);
static int modifyElem(SingleLinkedList *This, int index, ElemType* e);
static int deleteElem(SingleLinkedList *This, int index, ElemType* e);
static int appendElem(SingleLinkedList *This, ElemType *e);
static int insertElem(SingleLinkedList *This, int index, ElemType *e);
static int popElem(SingleLinkedList *This, ElemType* e);

SingleLinkedList *InitSingleLinkedList(){
    SingleLinkedList *L = (SingleLinkedList *)malloc(sizeof(SingleLinkedList));
    Node *p = (Node *)malloc(sizeof(Node));
    L->This = p;
    p->next = NULL;
    L->clear = clear;
    L->isEmpty = isEmpty;
    L->length = length;
    L->print = print;
    L->indexElem = indexElem;
    L->getElem = getElem;
    L->modifyElem = modifyElem;
    L->deleteElem = deleteElem;
    L->appendElem = appendElem;
    L->insertElem = insertElem;
    L->popElem = popElem;
    return L;
}

void DestroySingleLinkedList(SingleLinkedList *L){
    L->clear(L);
    free(L->This);
    free(L);
    L = NULL;
}

static void clear(SingleLinkedList *This){
    Node *p = This->This->next;
    Node *temp = NULL;
    while(p){
        temp = p;
        p = p->next;
        free(temp);
    } 
    p = This->This;
    p->next = NULL;
}

static int isEmpty(SingleLinkedList *This){
    Node *p = This->This;
    if(p->next){
        return 0;
    }else{
        return 1;
    }
}

static int length(SingleLinkedList *This){
    int j = 0;
    Node *p = This->This->next;
    while(p){
        j++;
        p = p->next;
    } 
    return j;
}

static void print(SingleLinkedList *This){
    Node *p = This->This->next;
    while(p){
        printf("%d ", p->elem);
        p = p->next;
    } 
    printf("\n");
}

static int indexElem(SingleLinkedList *This, ElemType* e){
    Node *p = This->This->next;
    int pos = -1;
    int j = 0;
    while(p){
        if(*e == p->elem){
            pos = j;
        }
        p = p->next;
        j++;
    } 
    return pos;
}

static int getElem(SingleLinkedList *This, int index, ElemType *e){
    Node *p = This->This->next;
    int j = 0;
    while(p && j < index){
        p = p->next;
        j++;
    } 
    if(!p || j > index) return -1;
    *e = p->elem;
    return 0;
}

static int modifyElem(SingleLinkedList *This, int index, ElemType* e){
    Node *p = This->This->next;
    int j = 0;
    while(p && j < index){
        p = p->next;
        j++;
    } 
    if(!p || j > index) return -1;
    p->elem = *e;
    return 0;
}

static int insertElem(SingleLinkedList *This, int index, ElemType *e){
    Node *p = This->This;
    int j = 0;
    Node *temp = (Node *)malloc(sizeof(Node));
    if(!temp) return -1;
    while(p && j < index){
        p = p->next;
        j++;
    } 
    if(!p || j > index) return -1;
    temp->elem = *e;
    temp->next = p->next;
    p->next = temp;
    return 0;
}

static int deleteElem(SingleLinkedList *This, int index, ElemType* e){
    Node *p = This->This;
    Node *temp = NULL;
    int j = 0;
    while(p->next && j < index){
        p = p->next;
        j++;
    } 
    if(!p->next || j > index) return -1;
    temp = p->next;
    p->next = temp->next;
    *e = temp->elem;
    free(temp);
    return 0;
}

static int appendElem(SingleLinkedList *This, ElemType *e){
    Node *p = This->This;
    Node *temp = (Node *)malloc(sizeof(Node));
    if(!temp) return -1;
    while(p){
        if(NULL == p->next){
            temp->elem = *e;
            p->next = temp;
            temp->next =  NULL;
        }
        p = p->next;
    } 
    return 0;
}

static int popElem(SingleLinkedList *This, ElemType* e){
    Node *p = This->This;
    Node *temp = NULL;
    while(p->next->next){
        p = p->next;
    } 
    temp = p->next;
    if(!temp) return -1;
    *e = temp->elem;
    free(temp);
    p->next = NULL;
    return 0;
}

SingleLinkedList.h文件

/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef __SINGLELINKEDLIST_H
#define __SINGLELINKEDLIST_H
/* Includes ------------------------------------------------------------------*/
/* Exported types ------------------------------------------------------------*/
typedef int ElemType;      //数据元素的类型，假设是int型的

typedef struct Node{
    ElemType elem;  //存储空间
    struct Node *next;
}Node;

typedef struct SingleLinkedList{
    Node *This;
    void (*clear)(struct SingleLinkedList *This);
    int (*isEmpty)(struct SingleLinkedList *This);
    int (*length)(struct SingleLinkedList *This);
    void (*print)(struct SingleLinkedList *This);
    int (*indexElem)(struct SingleLinkedList *This, ElemType* x);
    int (*getElem)(struct SingleLinkedList *This, int index, ElemType *e);
    int (*modifyElem)(struct SingleLinkedList *This, int index, ElemType* e);
    int (*deleteElem)(struct SingleLinkedList *This, int index, ElemType* e);
    int (*appendElem)(struct SingleLinkedList *This, ElemType *e);
    int (*insertElem)(struct SingleLinkedList *This, int index, ElemType *e);
    int (*popElem)(struct SingleLinkedList *This, ElemType* e);
}SingleLinkedList;

/* Exported macro ------------------------------------------------------------*/
SingleLinkedList *InitSingleLinkedList();
void DestroySingleLinkedList(SingleLinkedList *L);

#endif

testSingleLinkedList.c文件

#include <stdio.h>
#include <malloc.h>
#include "SingleLinkedList.h"

int main(void){
    int i;
    ElemType elem,elem1;
    SingleLinkedList *list = InitSingleLinkedList();
    printf("list is empty:%d\n",list->isEmpty(list));
    for(i=0;i<10;i++){
        list->appendElem(list,&i);
    }
    list->print(list);
    printf("list is empty:%d\n",list->isEmpty(list));
    printf("list length:%d\n",list->length(list));
    list->clear(list);
    for (i = 10; i < 20; i++){
        list->appendElem(list,&i);
    }   
    list->print(list);
    list->getElem(list,3,&elem1);
    printf("the elem of index 3 is %d\n",elem1);
    elem = 31;
    list->modifyElem(list,3,&elem);
    list->getElem(list,3,&elem1);
    printf("modify the elem of index 3 to %d\n",elem1);
    list->print(list);
    elem = 25;
    list->insertElem(list,5,&elem);
    printf("insert elem %d to index 5\n",elem);
    list->print(list);
    list->deleteElem(list,7,&elem);
    printf("delete elem %d of index 7\n",elem);
    list->print(list);
    elem = 14;
    printf("the index of 14 is %d\n",list->indexElem(list,&elem));
    list->popElem(list,&elem);
    printf("pop elem %d\n",elem);
    list->print(list);
    DestroySingleLinkedList(list);
    return 0;
}

编译：

gcc SingleLinkedList.c SingleLinkedList.h testSingleLinkedList.c -o testSingleLinkedList

运行testSingleLinkedList
输出：

list is empty:1
0 1 2 3 4 5 6 7 8 9
list is empty:0
list length:10
10 11 12 13 14 15 16 17 18 19
the elem of index 3 is 13
modify the elem of index 3 to 31
10 11 12 31 14 15 16 17 18 19
insert elem 25 to index 5
10 11 12 31 14 25 15 16 17 18 19
delete elem 16 of index 7
10 11 12 31 14 25 15 17 18 19
the index of 14 is 4
pop elem 19
10 11 12 31 14 25 15 17 18