C封装线性表对象

github源码

LinearList.c文件

#include <stdio.h>
#include <malloc.h>
#include "LinearList.h"
//线性表

static void clear(LinearList *This);
static int isEmpty(LinearList *This);
static int length(LinearList *This);
static void print(LinearList *This);
static int indexElem(LinearList *This, ElemType* x);
static int priorElem(LinearList *This, ElemType* cur_elem, ElemType* pre_elem);
static int getElem(LinearList *This, int index, ElemType* e);
static int modifyElem(LinearList *This, int index, ElemType* e);
static int nextElem(LinearList *This, ElemType* cur_elem, ElemType* next_elem);
static int insertElem(LinearList *This, int index, ElemType* e);
static int deleteElem(LinearList *This, int index, ElemType* e);
static int appendElem(LinearList *This,ElemType* e);
static int popElem(LinearList *This, ElemType* e);

LinearList *InitLinearList(){
    LinearList *L = (LinearList *)malloc(sizeof(LinearList));
    LinearList_P *p = (LinearList_P *)malloc(sizeof(LinearList_P));
    p->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    p->length = 0; //当前长度
    p->size = LIST_INIT_SIZE; //当前分配量
    L->This = p;
    L->clear = clear;
    L->isEmpty = isEmpty;
    L->length = length;
    L->print = print;
    L->indexElem = indexElem;
    L->priorElem = priorElem;
    L->getElem = getElem;
    L->modifyElem = modifyElem;
    L->nextElem = nextElem;
    L->insertElem = insertElem;
    L->deleteElem = deleteElem;
    L->appendElem = appendElem;
    L->popElem = popElem;
    return L;
}

void DestroyLinearList(LinearList *L){
    free(L->This);
    free(L);
    L = NULL;
}

static void clear(LinearList *This){
    LinearList_P *p = This->This;
    p->length = 0; //当前长度
}

static int isEmpty(LinearList *This){
    LinearList_P *p = This->This;
    return (p->length == 0);
}

static int length(LinearList *This){
    LinearList_P *p = This->This;
    return p->length;
}

static void print(LinearList *This){
    LinearList_P *p = This->This;
    int i;
    for (i=0; i < p->length; i++){
        printf("%d ", p->elem[i]);
    }
    printf("\n");
}

static int indexElem(LinearList *This, ElemType* x){
    LinearList_P *p = This->This;
    int pos = -1;
    for (int i = 0; i < p->length; i++){
        if (p->elem[i] == *x){
            pos = i;
        }
    }
    return pos;
}

static int priorElem(LinearList *This, ElemType* cur_elem, ElemType* pre_elem){
    LinearList_P *p = This->This;
    int pos = -1;
    pos = indexElem(This, cur_elem);
    if(pos <= 0) return -1;
    *pre_elem = p->elem[pos-1];
    return 0;
}

static int getElem(LinearList *This, int index, ElemType* e){
    LinearList_P *p = This->This;
    if (index<0 || index >= p->length) return -1;
    *e = p->elem[index];
    return 0;
}

static int modifyElem(LinearList *This, int index, ElemType* e){
    LinearList_P *p = This->This;
    if (index<0 || index >= p->length) return -1;
    p->elem[index] = *e;
    return 0;
}

static int nextElem(LinearList *This, ElemType* cur_elem, ElemType* next_elem){
    LinearList_P *p = This->This;
    int pos = -1;
    pos = indexElem(This, cur_elem);
    if(pos == -1 || pos == (p->length - 1)) return -1;
    *next_elem = p->elem[pos+1];
    return 0;
}

static int insertElem(LinearList *This, int index, ElemType* e){
    LinearList_P *p = This->This;
    if (index<0 || index >= p->length) return -1;
    if (p->length >= p->size){ //判断存储空间是否够用
        ElemType *newbase = (ElemType *)realloc(p->elem, (p->size + LISTINCREMENT)*sizeof(ElemType));
        if (!newbase) return -1;//存储空间分配失败
        p->elem = newbase;//新基址
        p->size += LISTINCREMENT;//增加存储容量
    }
    ElemType *elem_q = NULL;, *elem_p = NULL;;
    elem_q = &(p->elem[index]); //q为插入位置
    for (elem_p = &(p->elem[p->length - 1]); elem_p >= elem_q; --elem_p){ //从ai到an-1依次后移，注意后移操作要从后往前进行
        *(elem_p + 1) = *elem_p;
    }
    *elem_q = *e;
    ++p->length;
    return 0;
}

static int deleteElem(LinearList *This, int index, ElemType* e){
    LinearList_P *p = This->This;
    if (index<1 || index > p->length) return -1;
    ElemType *elem_q = NULL;, *elem_p = NULL;;
    elem_p = &(p->elem[index]);//elem_p为被删除元素的位置
    *e = *elem_p; //被删除的元素赋值给e
    elem_q = p->elem + p->length - 1;//elem_q指向表尾最后一个元素
    for (++elem_p; elem_p <= elem_q; ++elem_p){ //从elem_p的下一个元素开始依次前移
        *(elem_p - 1) = *elem_p;
    }
    --p->length;
    return 0;
}

static int appendElem(LinearList *This,ElemType* e){
    LinearList_P *p = This->This;
    if (p->length >= p->size){ //判断存储空间是否够用
        ElemType *newbase = (ElemType *)realloc(p->elem, (p->size + LISTINCREMENT)*sizeof(ElemType));
        if (!newbase) return -1;//存储空间分配失败
        p->elem = newbase;//新基址
        p->size += LISTINCREMENT;//增加存储容量
    }
    p->elem[p->length] = *e;
    ++p->length;
    return 0;
}

static int popElem(LinearList *This, ElemType* e){
    LinearList_P *p = This->This;
    if (isEmpty(This)) return -1;
    *e = p->elem[p->length - 1];
    --p->length;
    return 0;
}

LinearList.h文件：

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

typedef struct LinearList_P{
    ElemType *elem;  //存储空间的基地址
    int length;      //当前线性表的长度
    int size;    //当前分配的存储容量
}LinearList_P;

typedef struct LinearList{
    LinearList_P *This;  
    void (*clear)(struct LinearList *This);
    int (*isEmpty)(struct LinearList *This);
    int (*length)(struct LinearList *This);
    void (*print)(struct LinearList *This);
    int (*indexElem)(struct LinearList *This, ElemType* x);
    int (*priorElem)(struct LinearList *This, ElemType* cur_elem, ElemType* pre_elem);
    int (*getElem)(struct LinearList *This, int index, ElemType* e);
    int (*modifyElem)(struct LinearList *This, int index, ElemType* e);
    int (*nextElem)(struct LinearList *This, ElemType* cur_elem, ElemType* next_elem);
    int (*insertElem)(struct LinearList *This, int index, ElemType* e);
    int (*deleteElem)(struct LinearList *This, int index, ElemType* e);
    int (*appendElem)(struct LinearList *This,ElemType* e);
    int (*popElem)(struct LinearList *This, ElemType* e);
}LinearList;

/* Exported define -----------------------------------------------------------*/
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10   //线性表存储空间的分配增量(当存储空间不够时要用到)
/* Exported macro ------------------------------------------------------------*/
LinearList *InitLinearList();
void DestroyLinearList(LinearList *L);

#endif

测试文件 testLinearList.c

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

int main(void)
{
    int i;
    ElemType elem,elem1;
    LinearList *list = InitLinearList();
    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);
    elem = 17;
    printf("the index of 17 is %d\n",list->indexElem(list,&elem));
    list->priorElem(list,&elem,&elem1);
    printf("the prior elem of 17 is %d\n",elem1);
    list->nextElem(list,&elem,&elem1);
    printf("the next elem of 17 is %d\n",elem1);
    list->getElem(list,3,&elem1);
    printf("the elem of index 3 is %d\n",elem1);
    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->deleteElem(list,7,&elem);
    printf("delete elem %d of index 7\n",elem);
    list->print(list);
    list->popElem(list,&elem);
    printf("pop elem %d\n",elem);
    list->print(list);
    DestroyLinearList(list);
    return 0;
}

编译：

gcc LinearList.c LinearList.h testLinearList.c -o testLinearList

运行testLinearList
输出：

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 index of 17 is 7
the prior elem of 17 is 16
the next elem of 17 is 18
the elem of index 3 is 13
modify the elem of index 3 to 17
10 11 12 17 14 15 16 17 18 19
insert elem 25 to index 5
delete elem 16 of index 7
10 11 12 17 14 25 15 17 18 19
pop elem 19
10 11 12 17 14 25 15 17 18