线性表的顺序操作

栏目: 数据库 · 发布时间: 7年前

#include <stdio.h>

#define maxsize 10
#define failure -1
#define success 1
typedef int datatype;

typedef struct {
    datatype data[maxsize];
    int length;
} Seqlist;

typedef Seqlist* List;

///求表长度 o(1)
int length(Seqlist L) {
    return L.length;
}

/// 取表元 O(n)
datatype get(List L, int index) {
    if (index < 1 || index > L->length ) {
        return failure;
    }
    return L->data[index - 1];
}

/// 定位 O(n)
int locate(List L, datatype x) {
//    for (int i = 0; i < L->length - 1; i++) {
//        if (x == L->data[i]) {
//            return i + 1;
//        }
//    }
//    return failure;
    int i = 0;
    while (i < L->length && L->data[i] != x) {
        i++;
    }
    if (i < L->length) {
        return i + 1;
    } else {
        return failure;
    }
}

/// 删除 O(n)
int delete(List L, int index) {
    if (index < 1 || index > L->length) {
        return failure;
    }
    for (int j = index; j < L->length; j++) {
        L->data[j - 1] = L->data[j];
    }
    return success;
}

/// 插入 O(n)
int insert(List L, datatype x, int index) {
    
    if (L->length == maxsize) {
        return failure; //表满
    }
    if (index < 1 || index > L->length + 1) {
        return failure; //位置错
    }
    
    for (int j = L->length; j >= index; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[index - 1] = x;
    L->length++;
    return success;
}



int main(int argc, const char * argv[]) {
    List L = (List)malloc(sizeof(Seqlist));
    L->length = 0;
    printf("%d\n", length(*L));
    int result = insert(L, 0, 1);
    printf("%d\n", result);
    printf("%d\n", length(*L));
    
    printf("取表元 %d\n", get(L, 0));
    return 0;
}