通过数组实现线性表

基本实现：

 

一、头文件、宏定义以及函数声明：

 

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LIST_INC 10

typedef int ElemType;

typedef enum Status {
    success, range_error, fatal, fail
    } Status;

typedef struct sqlList {
    ElemType *elem; // 结点元素
    int length; // List的当前长度
    int list_size; // List的最大长度
} SqList, *Ptr;
typedef Ptr SqlListptr;

Status List_Init(SqlListptr L);
Status List_Retrival(SqlListptr L, int pos, ElemType *elem);
Status List_Locate(SqlListptr L, int *pos, ElemType elem);
Status List_Insert(SqlListptr L, int pos, ElemType elem);
Status List_delete(SqlListptr L, int pos);

 

 

二、初始化函数：

 

Status List_Init(SqlListptr L) {
    Status s = success;
    L->list_size = LIST_INIT_SIZE;
    L->length = 0;
    L->elem = (ElemType*)malloc(sizeof(ElemType)*L->list_size); // malloc() 返回的是空指针，所以需要强制转换
    if(L->elem == NULL) {
        s = fatal;
    }
    return s;
}

 

 

三、功能函数：

 

// 按位置查找元素
Status List_Retrival(SqlListptr L, int pos, ElemType *elem) {
    Status s = range_error;
    if(L) {
        if((pos-1>=0) && (pos-1) < L->length) {
            *elem = L->elem[pos-1];
            s = success;
        }
    }
    else 
        s = fatal;
    return s;
}

// 按值查找元素
Status List_Locate(SqlListptr L, int *pos, ElemType elem) {
    Status s = range_error;
    if(L) {
        for(size_t i = 0; i < L->length; i++) {
            if(elem == L->elem[i]) {
                *pos = i+1;
                s = success;
                break;
            }
        }
    }
    else    
        s = fatal;
    return s;
}

// 插入元素
Status List_Insert(SqlListptr L, int pos, ElemType elem) {
    Status s = range_error;
    if((pos-1) >= 0 && (pos-1) <= L->length) {
        if(L && L->length < L->list_size ) {
            for(int i = L->length-1; i >= pos-1 ; i--) {
                L->elem[i+1] = L->elem[i];
            } 
            L->elem[pos-1] = elem;
            L->length++;
            s = success;
        }
    } else 
        s = fatal;
    return s;
}

// 删除元素
Status List_delete(SqlListptr L, int pos) {
    Status s = range_error;
    if((pos-1) >= 0 && (pos-1) < L->length) {
        if(L && L->length > 0) {
            for(int i = pos; i <= L->length; i++) {
                L->elem[i-1] = L->elem[i];
            }
            L->length--;
            s = success;
        }
    } else {
        s = fail;
    }
    return s;
}

 

完整实现代码：

#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LIST_INC 10

typedef int ElemType;

typedef enum Status {
    success, range_error, fatal, fail
} Status;

typedef struct sqlList {
    ElemType *elem; // 结点元素
    int length; // List的当前长度
    int list_size; // List的最大长度
} SqList, *Ptr;
typedef Ptr SqlListptr;

Status List_Init(SqlListptr *L);
Status List_Retrival(SqlListptr L, int pos, ElemType *elem);
Status List_Locate(SqlListptr L, int *pos, ElemType elem);
Status List_Insert(SqlListptr L, int pos, ElemType elem);
Status List_delete(SqlListptr L, int pos);
void List_print(SqlListptr L);
int dealProcess(void);

int main(int argc, char const *argv[])
{
    dealProcess();
    return 0;
}

// 处理过程
int dealProcess() {
    int action;
    Status s;
    SqlListptr L = (SqlListptr)malloc(sizeof(SqList));;
    int position, *elem;
    int *pos, value;

    printf("初始化线性表——1\n");
    printf("按位置查找元素——2\n");
    printf("按值查找元素——3\n");
    printf("插入元素——4\n");
    printf("删除元素——5\n");
    printf("打印元素——6\n");
    printf("输入当前操作：\n");
    
    while((scanf("%d", &action)) != EOF){
        switch (action) {
            case 1:
                s = List_Init(&L);
                if(s == success) {
                    printf("初始化成功\n");
                } else {
                    printf("初始化错误\n");
                }
                break;
            case 2:
                printf("请输入查询位置：\n");
                scanf("%d", &position);
                elem = malloc(sizeof(int));
                s = List_Retrival(L, position, elem);
                if(s == success) {
                    printf("你所查询的元素是：%d\n", *elem);
                } else {
                    printf("该位置无元素\n");
                }
                break;
            case 3:
                pos = malloc(sizeof(int));
                printf("请输入要查询元素的值：\n");
                scanf("%d", &value);
                s = List_Locate(L, pos, value);
                if(s == success) {
                    printf("%d 的位置在 %d\n", value, *pos);
                } else {
                    printf("未找到该元素\n");
                }
                free(pos);
                break;
            case 4:
                printf("请依次输入插入位置和插入的值\n");
                scanf("%d %d", &position, &value);
                s = List_Insert(L, position, value);
                if(s == success) {
                    printf("插入成功\n");
                } else {
                    printf("插入失败\n");
                }
                break;
            case 5:
                printf("请输入要删除的元素的位置\n");
                scanf("%d", &position);
                s = List_delete(L, position);
                if(s == success) {
                    printf("删除成功\n");
                } else {
                    printf("删除失败\n");
                }
                break;
            case 6:
                printf("*****************************\n");
                List_print(L);
                printf("*****************************\n");
                break;
        }
    }
    return 0;
}

// 初始化线性表
Status List_Init(SqlListptr *L) {
    Status s = fail;
    (*L)->length = 0;
    (*L)->list_size = LIST_INIT_SIZE;
    (*L)->elem = malloc(sizeof(int)*LIST_INIT_SIZE);
    s = success;
    return s;
}

// 按位置查找元素
Status List_Retrival(SqlListptr L, int pos, ElemType *elem) {
    Status s = range_error;
    if(L) {
        if((pos-1>=0) && (pos-1) < L->length) {
            *elem = L->elem[pos-1];
            s = success;
        }
    }
    else
        s = fatal;
    return s;
}

// 按值查找元素
Status List_Locate(SqlListptr L, int *pos, ElemType elem) {
    Status s = range_error;
    if(L) {
        for(int i = 0; i < L->length; i++) {
            if(elem == L->elem[i]) {
                *pos = i+1;
                s = success;
                break;
            }
        }
    }
    else
        s = fatal;
    return s;
}

// 插入元素
Status List_Insert(SqlListptr L, int pos, ElemType elem) {
    Status s = range_error;
    if((pos-1) >= 0 && (pos-1) <= L->length) {
        if(L && L->length < L->list_size ) {
            for(int i = L->length-1; i >= pos-1 ; i--) {
                L->elem[i+1] = L->elem[i];
            }
            L->elem[pos-1] = elem;
            L->length++;
            s = success;
        }
    } else
        s = fatal;
    return s;
}

// 删除元素
Status List_delete(SqlListptr L, int pos) {
    Status s = range_error;
    if((pos-1) >= 0 && (pos-1) < L->length) {
        if(L && L->length > 0) {
            for(int i = pos; i <= L->length; i++) {
                L->elem[i-1] = L->elem[i];
            }
            L->length--;
            s = success;
        }
    } else {
        s = fail;
    }
    return s;
}

// 打印元素 
void List_print(SqlListptr L) {
    int flag = 0;
    if(L->length == 0) printf("无元素\n");
    else {
        for(int i = 0; i < L->length; i++) {
            if(flag) printf(" ");
            flag = 1;
            printf("%d", *(L->elem++));
        }
        printf("\n");
    }
}

 

 

总体来说数组线性表实现比较简单，查询元素速度较快，但是插入和删除元素效率很低：

 

插入元素时间复杂度：

 

删除元素时间复杂度：