链式顺序表实现(C语言描述)

链式顺序表

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

//为数据创建比较准则
typedef struct Data_tlg {
    int key;
    char name[20];
}DATA,*LPDATA;

//定义节点结构
typedef struct Node_tlg {
    DATA data;
    struct Node_tlg* next;
}NODE,*LPNODE;

//定义顺序表结构
typedef struct sqList_tlg {
    LPNODE headNode;
    int curSize;
}SQLIST,*LPSQLIST;

//创建表头
LPNODE createHead() {
    LPNODE headNode = (LPNODE)malloc(sizeof(NODE));
    if (NULL == headNode) {
        printf("头节点申请失败!\n");
        return NULL;
    }
    headNode->next = NULL;
    return headNode;
}

//创建节点
LPNODE createNode(DATA data) {
    LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
    if (NULL == newNode) {
        printf("数据节点申请失败!\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

//创建链表
LPSQLIST createSqList() {
    LPSQLIST sqList = (LPSQLIST)malloc(sizeof(SQLIST));
    if (NULL == sqList) {
        printf("顺序表申请失败!\n");
        return NULL;
    }
    sqList->curSize = 0;
    sqList->headNode = createHead();
    return sqList;
}

//打印链表
void printSqList(LPSQLIST sqList) {
    if (sqList == NULL)
        exit(0);
    LPNODE curNode = sqList->headNode->next;
    while(curNode != NULL)
    {
        printf("key:%d,name:%s\n", 
            curNode->data.key, curNode->data.name);
        curNode = curNode->next;
    }
    putchar('\n');
}
//数据插入
void insertDataByKey(LPSQLIST sqList,DATA data) {
    LPNODE newNode = createNode(data);
    LPNODE curNode = sqList->headNode->next;
    LPNODE preNode = sqList->headNode;
    while (curNode != NULL && curNode->data.key < newNode->data.key) {
        preNode = curNode;
        curNode = curNode->next;
    }
    newNode->next = curNode;
    preNode->next = newNode;
    sqList->curSize++;
}

//数据删除
void deleteDataByKey(LPSQLIST sqList, int key) {
    LPNODE preNode = sqList->headNode;
    LPNODE curNode = sqList->headNode->next;
    while (curNode != NULL && curNode->data.key != key) {
        preNode = curNode;
        curNode = curNode->next;
    }
    if (curNode) {
        preNode->next = curNode->next;
        free(curNode);
        curNode = NULL;
    }
    else {
        printf("未找到指定节点!\n");
        return;
    }
    sqList->curSize--;
}
//万金油函数
int size(LPSQLIST sqList) {
    return sqList->curSize;
}
int empty(LPSQLIST sqList) {
    return sqList->curSize == 0;
}
//销毁顺序表
void destroySqList(LPSQLIST* sqList) {
    while((*sqList)->headNode->next != NULL) {
        deleteDataByKey(*sqList, (*sqList)->headNode->next->data.key);
    }
    if ((*sqList)->headNode->next == NULL) {
        free((*sqList)->headNode);
        (*sqList)->headNode = NULL;
        free(*sqList);
        *sqList = NULL;
    }
    else {
        printf("链表数据销毁失败!\n");
        return;
    }
}

int main()
{
    LPSQLIST sqList = createSqList();

    DATA array[4] = { {2,"张三"},{1,"李四"},{6,"电铲"},{4,"卢布"} };
    //数据插入
    for (int i = 0; i < 4; i++)
    {
        insertDataByKey(sqList, array[i]);
    }
    printSqList(sqList);

    //数据删除
    deleteDataByKey(sqList, 4);
    printSqList(sqList);
    deleteDataByKey(sqList, 8);
    printSqList(sqList);

    //顺序表销毁
    destroySqList(&sqList);
    if (sqList == NULL) {
        printf("顺序表销毁成功!\n");
    }
    else {
        printf("顺序表销毁失败!\n");
    }

    system("pause");
    return 0;
}