顺序表是上机时的作业,是一种插入和删除的时间复杂度都是 O(N) 的~神奇~数据结构,下面是简易实现~,其中测试函数是抄来的~:

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

#define OK 1
#define NONONO 0

#define INITLENGTH 1000
#define ADDLENGTH 1000

typedef int Status;
typedef int element_type;

typedef struct ARRLIST
{
    element_type *base;
    int length;
    int max;
} ArrList;

//  初始化顺序表
Status ListInit(ArrList *L);
//  删除顺序表
Status ListDestroy(ArrList *L);
//  清空顺序表
Status ListClear(ArrList *L);
//  判断顺序表为空
Status isListEmpty(ArrList *L);
//  返回顺序表当前长度
Status ListLength(ArrList *L);
//  用第三个参数 x 返回顺序表中第 n 位的值
Status ListGetELement(ArrList *L, int n, element_type *x);
//  用第三个参数 n 返回顺序表中值为 x 的项位置序号最小的一项的位置
Status ListGetLocation(ArrList *L, element_type x, int *n);
//  在顺序表第 n 位插入值 x
Status ListInsert(ArrList *L, int n, element_type x);
//  删除顺序表第 n 位的值,并用 x 返回其值
Status ListDelete(ArrList *L, int n, element_type *x);
//  从头遍历整个顺序表
Status ListTrave(ArrList *L);

Status ListInit(ArrList *L)
{
    L->base = (element_type *)malloc(INITLENGTH * sizeof(element_type));
    assert(L->base);
    L->length = 0;
    L->max = INITLENGTH;
    return OK;
}

Status ListDestroy(ArrList *L)
{
    free(L->base);
    L->length = L->max = 0;
    return OK;
}

Status ListClear(ArrList *L)
{
    free(L->base);
    L->base = (element_type *)malloc(L->max * sizeof(element_type));
    L->length = 0;
    return OK;
}

Status isListEmpty(ArrList *L)
{
    return L->length == 0;
}

Status ListLength(ArrList *L)
{
    return L->length;
}

Status ListGetELement(ArrList *L, int n, element_type *x)
{
    assert(n > 0);
    assert(n <= L->length);
    *x = L->base[n - 1];
    return OK;
}

Status ListGetLocation(ArrList *L, element_type x, int *n)
{
    for (int i = 0; i < L->length; i++)
    {
        if (L->base[i] == x)
        {
            *n = i + 1;
            return OK;
        }
    }
    return NONONO;
}

Status ListInsert(ArrList *L, int n, element_type x)
{
    assert(n > 0);
    if (L->length + 1 > L->max)
    {
        element_type *tmp;
        tmp = (element_type *)realloc(L->base, (L->max + ADDLENGTH) * sizeof(element_type));
        assert(!tmp);
        L->max += ADDLENGTH;
        L->base = tmp;
    }
    element_type *P = &L->base[n - 1];
    element_type *Q = &L->base[L->length - 1];
    for (; Q >= P; Q--)
    {
        *(Q + 1) = *Q;
    }
    *P = x;
    L->length++;
    return OK;
}

Status ListDelete(ArrList *L, int n, element_type *x)
{
    assert(n > 0);
    element_type *tmp = &L->base[n - 1];
    *x = *tmp;
    for (; tmp < &L->base[L->length]; tmp++)
    {
        *(tmp) = *(tmp + 1);
    }
    L->length--;
    return OK;
}

Status ListTrave(ArrList *L)
{
    for (int i = 0; i < L->length; i++)
        printf("-> %d ", L->base[i]);
    return OK;
}

void test_arrlist()
{
    ArrList L;
    if (ListInit(&L))
    {
        element_type e;
        printf("init_success\n");
        int i;
        for (i = 0; i < 10; i++)
        {
            ListInsert(&L, i + 1, i);
        }
        printf("length is %d\n", ListLength(&L));
        if (ListGetELement(&L, 1, &e))
            printf("The first element is %d\n", e);
        else
            printf("element is not exist\n");
        if (isListEmpty(&L))
            printf("list is empty\n");
        else
            printf("list is not empty\n");
        ListGetLocation(&L, 5, &i);
        printf("The 5 at %d\n", i);
        printf("List:");
        ListTrave(&L);
        printf("\n");
        ListDelete(&L, 5, &e);
        printf("delete fifth element is %d\n", e);
        printf("List:");
        ListTrave(&L);
        if (ListDestroy(&L))
            printf("\ndestroy_success\n");
    }
}

int main(void)
{
    test_arrlist();
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *