顺序表的实现

线性表的顺序实现实现起来还是相对容易的。

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT  10
#define OK               1
#define ERROR            0
#define OVERFLOW        -1

typedef int Status;
typedef int ElemType;
typedef int Bool;

typedef struct
{
    ElemType *elem;
    int length;
    int listsize;
}SqList;

Status InitList(SqList *L)
{
    assert(L);
    L->elem = (ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);
    if (!L->elem)
        exit(OVERFLOW);
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return OK;
}

void DestroyList(SqList *L)
{
    assert(L);
    free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
}

void ClearList(SqList *L)
{
    assert(L);
    L->length = 0;
}

Bool ListEmpty(SqList *L)
{
    assert(L);
    return L->length == 0;
}

int ListLength(SqList *L)
{
    assert(L);
    return L->length;
}

Status GetElem(SqList *L, int pos, ElemType *e)
{
    assert(L&&e);
    if (pos<1 || pos>L->length)
        return ERROR;
    *e = L->elem[pos - 1];
    return OK;
}

int LocateElem(SqList *L, ElemType *e, int(*cmp)(ElemType*, ElemType *))
{
    assert(L&&e&&cmp);
    int i = 0;
    ElemType *p = L->elem;

    while (i < L->length&&!cmp(e, p++))
        ++i;
    if (i < L->length)
        return i + 1;
    return 0;
}

Status ListInsert(SqList *L, int pos, ElemType *e)
{
    assert(L&&e);
    ElemType *p, *q;

    if (pos<1 || pos>L->length + 1)
        return ERROR;
    if (L->length >= L->listsize)
    {
        ElemType *tmp = (ElemType *)realloc(L->elem, sizeof(ElemType)*(L->listsize + LIST_INCREMENT));
        if (!tmp)
            exit(OVERFLOW);
        L->elem = tmp;
        L->listsize += LIST_INCREMENT;
    }

    p = L->elem + L->length - 1;
    for (q = L->elem + pos - 1; p >= q; --p)
        *(p + 1) = *p;
    *q = *e;
    ++L->length;
    return OK;
}

Status ListDelete(SqList *L, int pos, ElemType *e)
{
    assert(L);
    ElemType *p, *q;

    if (pos<1 || pos>L->length)
        return ERROR;

    p = L->elem + pos - 1;
    if (e)
        *e = *p;
    q = L->elem + L->length - 1;
    for (++p; p <= q; ++p)
        *(p - 1) = *p;
    --L->length;
    return OK;
}

void ListTraverse(SqList *L, void(*visit)(ElemType*))
{
    assert(L&&visit);
    ElemType *p, *q;

    p = L->elem;
    q = L->elem + L->length - 1;
    while (p <= q)
        visit(p++);
}

#define PRIOR 1
#define NEXT  2
Status PrOrNeElem(SqList *L, ElemType *e,ElemType *get,int mod)
{
    assert(L&&e&&get);
    ElemType *p, *q;

    p = L->elem;
    q = L->elem + L->length - 1;
    while (p <= q)
    {
        if (*e == *p)
            break;
            ++p;
    }
    switch (mod)
    {
    case PRIOR:
        --p;
        if (p < L->elem)
            return ERROR;
        break;
    default:
        ++p;
        if (p >= L->elem+L->length)
            return ERROR;
        break;
    }
    *get = *p;
    return OK;
}

下面是测试代码：

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

void head()
{
    printf("1.END 2.INIT 3.DSTY 4.CLR 5.EMPTY 6.LEN 7.GET 8.LCT
"
        "9.INS 10.DEL 11.TRVL 12.CLS 13.PRE/NXT 
");
}
void visit(ElemType *e)
{
    printf("%d
", *e);
}
int cmp(ElemType  *e1, ElemType *e2)
{
    return *e1 == *e2;
}
enum {END=1,INIT,DSTY,CLR,EMPTY,LEN,GET,LCT,INS,DEL,TRVL,CLS,PRE,NXT};
int main(int argc, char *argv[])
{
    int instr;
    SqList L;
    ElemType e, get;
    int pos,porn;
    Status flag;
    
    head();
    printf(">>>");
    scanf("%d", &instr);
    while (1)
    {
        switch (instr)
        {
        case END:
            goto end;//跳转到main函数结尾
        case INIT:
            DestroyList(&L);
            InitList(&L);
            break;
        case DSTY:
            DestroyList(&L);
            break;
        case CLR:
            ClearList(&L);
            break;
        case EMPTY:
            printf(ListEmpty(&L) ? "List is empty.
" : "List is not empty.
");
            break;
        case LEN:
            printf("List length is %d 
", ListLength(&L));
            break;
        case GET:
            printf("请输入pos:");
            scanf("%d", &pos);
            flag=GetElem(&L, pos, &e);
            if (flag == ERROR)
                printf("Error
");
            else
                visit(&e);
            break;
        case LCT:
            printf("请输入elem:");
            scanf("%d", &e);
            pos = LocateElem(&L, &e, cmp);
            if (pos == 0)
                printf("null
");
            else
                printf("pos=%d
", pos);
            break;
        case INS:
            printf("要插入的元素");
            scanf("%d", &e);
            printf("要插入的位置");
            scanf("%d", &pos);
            flag = ListInsert(&L, pos, &e);
            if (flag == ERROR)
                printf("插入失败
");
            else
                printf("插入成功
");
            break;
        case DEL:
            printf("要删除的位置");
            scanf("%d", &pos);
            flag = ListDelete(&L, pos, &e);
            if (flag == ERROR)
                printf("插入失败
");
            else
                printf("插入成功
");
            printf("%d", e);
            break;
        case TRVL:
            ListTraverse(&L, visit);
            break;
        case PRE:
        case NXT:
            printf("输入一个元素");
            scanf("%d", &e);
            printf("您要查找前驱(1)还是后继(2)");
            scanf("%d", &porn);
            flag = PrOrNeElem(&L, &e, &get, porn);
            if (flag == ERROR)
                printf("%d没有%s
", e, porn == PRIOR ? "前驱" : "后继");
            else
                printf("%d的%s是%d
", e, porn == PRIOR ? "前驱" : "后继", get);
            break;
        case CLS:
            system("cls");
            head();
            break;
        default:
            printf("指令错误
");
            break;
        }
        printf(">>>");
        scanf("%d", &instr);
    }
end:
    printf("谢谢使用");
    system("pause");
    return 0;
}

顺序表的实现

相关推荐