InitList(&L)
DestroyList(&L)

ClearList(&L)

ListEmpty(L)
ListLength(L)

GetElem(L, i, &e)
LocateElem(L, e, compare())

PriorElem(L, e, &pre)
NextElem(L, e, &next)

ListInsert(&L, i, e)
ListDelete(L, i, &e)
ListTraverse(L, visit())

线性表

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
    ElemType *elem;
    int length;
    int listsize;
}SqList;

Status InitList_Sq(SqList &L){
    L.elem = (ElemType*) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(!L.elem) exit(OVERFLOW);

    L.length = 0;
    L.listsize = LIST_INIT_SIZE;

    return OK;
}

Status ListInsert_Sq(SqList &L, int i, ElemType e){
    if(i < 1 || i > L.length + 1) return ERROR;

    if(L.length >= L.listsize){
        newbase = (ElemType*) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);

        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }

    q = &(L.elem[i - 1];
    for(p = &(L.elem[L.length - 1]; p >= q; —p){
        *(p + 1) = *p;
    }
    *q = e;
    ++L.length;

    return OK;
}

Status ListDelete_Sq(SqList &L, int i, ElemType &e){
    if( i < 1 || i > L.length) return ERROR;

    p = &(L.elem[i - 1];
    e = *p;
    q = L.elem + L.length - 1;

    for(++p; p <= q; ++p){
        *(p - 1) = *p;
    }

    —L.length;
    return OK;
}

线性链表

• 单链表

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

void CreateList_L(LinkList &L, int n){
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    for(i = n; i > 0; --i){
        p = (LinkList)malloc(sizeof(LNode));
        scanf(&p->data);
        p->next = L->next;
        L->next = p;
    }
}

常量阶O(1)、线性阶O(n)、平方阶O(n²)、多项式阶O(nk)、对数阶O(log n)、指数阶O(2n)

1>log n>n>n²>2n

继续阅读复杂度