顺序表数组法构建(C语言描述)

数组式顺序表

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

#define MAX 5

//为数据构建一个键值作为比较的准则
typedef struct dataType {
    int key;    //通过数据中的key作为准则构建有顺序的表
    char name[20];
}DATA,*LPDATA;

//描述顺序表这种结构
typedef struct SqList_tlg {
    LPDATA memory;     //存放数据的容器
    int curSize;     //当前表实际元素个数
    int maxSize;     //顺序表的最大容量
}SQLIST,*LPSQLIST;

//创建顺序表
LPSQLIST createSqlist(){
    LPSQLIST list = (LPSQLIST)malloc(sizeof(SQLIST));
    if (NULL == list) {
        printf("顺序表申请失败!\n");
        return NULL;
    }
    list->memory = (LPDATA)malloc(sizeof(DATA) * MAX);
    if (NULL == list->memory) {
        printf("容器内存申请失败!\n");
        return NULL;
    }
    list->curSize = 0;
    list->maxSize = MAX;
    return list;
}

//寻找插入的合适位置
int searchPos(LPSQLIST sqList,DATA data) {
    if (NULL == sqList)
        exit(0);
    for (int i = 0; i < sqList->curSize; i++)
    {
        if (sqList->memory[i].key > data.key) {
            return i;
        }
    }
    return sqList->curSize;
}
//顺序表扩容
void reallSqList(LPSQLIST sqList) {
    sqList->maxSize += 10;
    if (NULL != sqList) {
        int* p = (int*)realloc(sqList->memory, sizeof(DATA) * sqList->maxSize);
        if (NULL != p) {
            printf("顺序表已扩容!\n");
            sqList->memory = p;
        }
        else {
            printf("顺序表扩容失败!\n");
            return;
        }
    }
}
//插入
void insertData(LPSQLIST sqList,DATA data) {
    if (NULL == sqList)
        exit(0);
    //1.直接插入到表后面
    if (sqList->curSize >= sqList->maxSize) {
        //给顺序表扩容
        reallSqList(sqList);
    }
    sqList->memory[sqList->curSize++] = data;
    //2.挪动到合适的位置
    for (int i = sqList->curSize - 1; i > 0; i--)
    {
        if (sqList->memory[i].key < sqList->memory[i - 1].key) {
            DATA temp = sqList->memory[i];
            sqList->memory[i] = sqList->memory[i - 1];
            sqList->memory[i - 1] = temp;
        }
        else {
            break;
        }
    }

    //找到应该插入的位置直接插入数据
    //int pos = searchPos(sqList, data);
    //for (int i = sqList->curSize - 1; i > pos; i--)
    //{
    //    if (sqList->memory[i].key < sqList->memory[i - 1].key) {
    //        DATA temp = sqList->memory[i];
    //        sqList->memory[i] = sqList->memory[i - 1];
    //        sqList->memory[i - 1] = temp;
    //    }
    //    else {
    //        break;
    //    }
    //}
}
//删除
int searchByKey(LPSQLIST sqList, int key) {
    for (int i = 0; i < sqList->curSize; i++)
    {
        if (sqList->memory[i].key == key)
            return i;
    }
    return -1;   //没有找到
}
void deleteByKey(LPSQLIST sqList, int key) {
    if (empty(sqList))
        exit(0);
    //找到key的位置, 数组元素向前覆盖
    int pos = searchByKey(sqList, key);
    if (pos == -1) {
        printf("未找到指定数据,删除失败!\n");
        return;
    }
    else {
        for (int i = pos; i < sqList->curSize; i++)
        {
            sqList->memory[i] = sqList->memory[i + 1];
        }
        sqList->curSize--;
    }
}
//销毁表
void destroy(LPSQLIST* sqList) {
    if (sqList == NULL)
        exit(0);
    free((*sqList)->memory);
    (*sqList)->memory = NULL;
    free(*sqList);
    *sqList = NULL;
}

//万金油函数
int empty(LPSQLIST list) {
    if (list == NULL)
        exit(0);
    return list->curSize == 0;
}
int size(LPSQLIST list) {
    if (list == NULL)
        exit(0);
    return list->curSize;
}

//遍历顺序表: 打印数组中数据
void printSqList(LPSQLIST sqList) {
    if (NULL == sqList)
        exit(0);
    for (int i = 0; i < sqList->curSize; i++) {
        printf("key:%d,data:%s\n", 
            sqList->memory[i].key, 
            sqList->memory[i].name);
    }
    printf("\n");
}

int main()
{
    LPSQLIST sqList = createSqlist();
    DATA array[9] = { {2,"张三"},{4,"李四"},{1,"貂蝉"},
    {9,"卢梦"},{8,"涨涨"},{5,"哈哈"} ,{7,"哼哼"},{6,"琵琶"},{3,"老贵"} };
    for (int i = 0; i < 9; i++)
    {
        insertData(sqList,array[i]);
    }
    printSqList(sqList);

    deleteByKey(sqList, 5);
    printSqList(sqList);

    if (sqList != NULL) {
        printf("顺序表未销毁!\n");
    }
    destroy(&sqList);
    if (sqList == NULL) {
        printf("顺序表已经销毁!\n");
    }

    system("pause");
    return 0;
}