【数据结构】之顺序表（C语言描述）

　　顺序表是线性表的一种，它将元素存储在一段连续的内存空间中，表中的任意元素都可以通过下标快速的获取到，因此，顺序表适合查询操作频繁的场景，而不适合增删操作频繁的场景。

　　下面是使用 C语言编写的顺序表的代码：

　　顺序表的头文件SeqList.h中的代码如下：

/**

 * 顺序表（线性存储）

 * 注意：添加数据时，先判断容量是否存满，存满才扩容，而不是添加元素后判断扩容！

 */

#include <stdio.h>

#include <stdlib.h>

// 定义常量

#define SEQLIST_INITIAL_SIZE 5    // 顺序表的初始长度

#define SEQLIST_INCREMENT_SIZE 5  // 顺序表的递增长度

// 类型定义

typedef int seqElemType;

// 定义顺序表（线性存储）的数据结构

typedef struct MySeqList {

    seqElemType* data; // 存储所有数据的数组

    int currentLength; // 当前长度

    int totalLength;   // 总长度

} MySeqList;

// 0.比较两个元素数据是否相等

int isEqual(seqElemType a, seqElemType b) {

    return a == b;

}

// 1.初始化顺序表L，即进行动态存储空间分配并置L为一个空表

void initSeqList(MySeqList* L, int ms) {

    if(ms <= ) {

        printf("顺序表的初始长度非法！\n");

        exit();

    }

    L->data = (seqElemType*)malloc(ms * sizeof(seqElemType));

    if(L->data != NULL) {

        L->currentLength = ;

        L->totalLength = ms;

        printf("顺序表初始化成功！当前总长度：%d\n", L->totalLength);

    } else {

        printf("顺序表初始化失败！\n");

        exit();

    }

}

// 2.清除顺序表L中的所有元素，释放动态存储空间，使之成为一个空表

void clearList(MySeqList* L) {

    if(L->data == NULL || L->totalLength < ) {

        printf("顺序表不存在，清空失败！\n");

        exit();

    }

    free(L->data);

    L->data = ;

    L->currentLength = L->totalLength = ;

    printf("顺序表清空成功！\n");

}

// 3.返回顺序表L的长度，若L为空则返回0

int getListSize(MySeqList* L) {

    if(L->data == NULL) {

        return ;

    }

    return L->currentLength;

}

// 4.判断顺序表L是否为空，若为空则返回1，否则返回0

int isListEmpty(MySeqList* L) {

    if(L->data == NULL) {

        return ;

    }

    return L->currentLength == ;

}

// 5.返回顺序表L中第pos个元素的值，若pos超出范围，则停止程序运行

seqElemType getElemAtPos(MySeqList* L, int pos) {

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    if(pos <  || pos >= L->currentLength) {

        printf("下标无效！\n");

        exit();

    }

    return L->data[pos - ];

}

// 6.顺序扫描（即遍历）输出顺序表L中的每个元素

void traverseList(MySeqList* L) {

    int i = ;

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    printf("顺序遍历顺序表：");

    for(i = ; i < L->currentLength; i++) {

        printf("%-4d", L->data[i]);

    }

    printf("\n");

}

// 7.从顺序表L中查找值与x相等的元素（第一个），若查找成功则返回其位置（下标），否则返回-1

int getPositionOfElem(MySeqList* L, seqElemType x) {

    int i = ;

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    for(i = ; i < L->currentLength; i++) {

        if(isEqual(L->data[i], x)) {

            break;

        }

    }

    if(i == L->currentLength) {

        i = -;

    }

    return i;

}

// 8.把顺序表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0

int setElemValue(MySeqList* L, int pos, seqElemType x) {

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        return ;

    }

    if(pos <  || pos >= L->currentLength) {

        printf("下标无效！\n");

        return ;

    }

    L->data[pos] = x;

    return ;

}

// 9.0.判断顺序表是否需要扩容，如果需要则扩容

void expandWhenShould(MySeqList* L) {

    if(L->currentLength == L->totalLength) {

        L->data = (seqElemType*)realloc(L->data, (L->totalLength + SEQLIST_INCREMENT_SIZE) * sizeof(seqElemType));

        L->totalLength += SEQLIST_INCREMENT_SIZE;

        if(L->data == NULL || L->totalLength <= ) {

            printf("顺序表重分配空间失败，插入元素失败！\n");

            exit();

        }

        printf("扩容成功，顺序表容量扩大到%d！\n", L->totalLength);

    }

}

// 9.向顺序表L的表头插入元素x

void insertElemAtStart(MySeqList* L, seqElemType x) {

    int i = ;

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    if(L->totalLength > ) {

        expandWhenShould(L);

        L->currentLength++;

        for(i = L->currentLength; i > ; i--) {

            L->data[i] = L->data[i - ];

        }

        L->data[] = x;

        printf("成功将元素%d插入到表头！\n", x);

    } else {

        printf("顺序表长度不合法，插入元素失败！\n");

        exit();

    }

}

// 10.向顺序表L的表尾插入元素x

void insertElemAtEnd(MySeqList* L, seqElemType x) {

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    if(L->totalLength > ) {

        expandWhenShould(L);

        L->data[L->currentLength++] = x;

        printf("成功将元素%d插入到表尾！\n", x);

    } else {

        printf("顺序表长度不合法，插入元素失败！\n");

        exit();

    }

}

// 11.向顺序表L中第pos个元素位置插入元素x，若插入成功返回1，否则返回0

int insertElemAtPos(MySeqList* L, int pos, seqElemType x) {

    int i = ;

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        return ;

    }

    if(pos <  || pos > L->currentLength) {

        printf("下标不合法，插入元素失败！\n");

        return ;

    }

    if(L->totalLength > ) {

        expandWhenShould(L);

        L->currentLength++;

        for(i = L->currentLength; i > pos; i--) {

            L->data[i] = L->data[i - ];

        }

        L->data[pos] = x;

        printf("成功添加%d到顺序表第%d个位置！\n", x, pos);

    } else {

        printf("顺序表长度不合法，插入元素失败！\n");

        return ;

    }

    return ;

}

// 12.向有序（递增）顺序表L中插入元素x，使得插入后仍然有序

void insertOrderly(MySeqList* L, seqElemType x) {

    int i = ;

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    if(L->totalLength > ) {

        expandWhenShould(L);

        L->currentLength++;

        for(i = L->currentLength; i > ; i--) {

            if(x < L->data[i - ]) {

                L->data[i] = L->data[i - ];

            } else {

                L->data[i] = x;

                printf("成功将%d插入到顺序表的%d位置！\n", x, i);

                break;

            }

        }

        if(i == ) {

            L->data[i] = x;

            printf("成功将%d插入到顺序表的%d位置！\n", x, i);

        }

    } else {

        printf("顺序表长度不合法，插入元素失败！\n");

        exit();

    }

}

// 13.从顺序表L中删除表头元素并返回它，若删除失败则停止程序运行

seqElemType deleteFirstElem(MySeqList* L) {

    int i = ;

    int result = -;

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    result = L->data[];

    for(i = ; i < L->currentLength; i++) {

        L->data[i - ] = L->data[i];

    }

    L->currentLength--;

    printf("删除表头元素成功，返回表头元素：%d\n", result);

    return result;

}

// 14.从顺序表L中删除表尾元素并返回它，若删除失败则停止程序运行

seqElemType deleteLastElem(MySeqList* L) {

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    L->currentLength--;

    printf("删除表尾元素成功，返回表尾元素：%d\n", L->data[L->currentLength]);

    return L->data[L->currentLength];

}

// 15.从顺序表L中删除第pos个元素并返回它，若删除失败则停止程序运行

seqElemType deleteElemAtPos(MySeqList* L, int pos) {

    int i = ;

    int result = -;

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        exit();

    }

    if(pos <  || pos >= L->currentLength) {

        printf("下标无效，删除元素失败！");

        exit();

    }

    result = L->data[pos];

    for(i = pos + ; i < L->currentLength; i++) {

        L->data[i - ] = L->data[i];

    }

    L->currentLength--;

    printf("成功将%d从顺序表的%d位置删除！\n", result, pos);

    return result;

}

// 16.从顺序表L中删除值为x的第一个元素，若删除成功返回1否则返回0

int deleteElemByValue(MySeqList* L, seqElemType x) {

    int i = ;

    if(L->data == NULL) {

        printf("顺序表不存在！\n");

        return ;

    }

    for(i = ; i < L->currentLength; i++) {

        if(isEqual(L->data[i], x)) {

            deleteElemAtPos(L, i);

            printf("成功删除%d在顺序表中出现的第一个数据（%d位置）！\n", x, i);

            return ;

        }

    }

    printf("%d没有在顺序表中出现过，删除失败！\n");

    return ;

}

// 测试方法

void testMySeqList() {

    // 声明顺序表变量

    MySeqList list;

    // 初始化顺序表

    initSeqList(&list, SEQLIST_INITIAL_SIZE);

    // 清空顺序表

    // clearList(&list);

    // 获取顺序表的当前长度

    printf("顺序表当前长度：%d\n", getListSize(&list));

    // 判断顺序表是否为空

    printf("顺序表是否为空？%s\n", isListEmpty(&list) ? "是" : "否");

    // 向表头插入数据

    insertElemAtStart(&list, );

    insertElemAtStart(&list, );

    insertElemAtStart(&list, );

    insertElemAtStart(&list, );

    insertElemAtStart(&list, );

    insertElemAtStart(&list, );

    // 顺序遍历顺序表

    traverseList(&list);

    // 向表尾插入数据

    insertElemAtEnd(&list, );

    insertElemAtEnd(&list, );

    insertElemAtEnd(&list, );

    insertElemAtEnd(&list, );

    insertElemAtEnd(&list, );

    // 顺序遍历顺序表

    traverseList(&list);

    // 向顺序表指定位置插入数据

    insertElemAtPos(&list, , );

    insertElemAtPos(&list, , );

    insertElemAtPos(&list, , );

    insertElemAtPos(&list, , );

    insertElemAtPos(&list, , );

    // 顺序遍历顺序表

    traverseList(&list);

    // 有序表插入元素

    insertOrderly(&list, );

    insertOrderly(&list, );

    // 顺序遍历顺序表

    traverseList(&list);

    // 删除表头元素

    deleteFirstElem(&list);

    deleteFirstElem(&list);

    deleteFirstElem(&list);

    deleteFirstElem(&list);

    // 顺序遍历顺序表

    traverseList(&list);

    // 删除表尾元素

    deleteLastElem(&list);

    deleteLastElem(&list);

    deleteLastElem(&list);

    deleteLastElem(&list);

    // 顺序遍历顺序表

    traverseList(&list);

    // 删除指定位置的元素

    deleteElemAtPos(&list, );

    deleteElemAtPos(&list, );

    deleteElemAtPos(&list, );

    // 顺序遍历顺序表

    traverseList(&list);

    // 删除某元素的首次出现

    deleteElemByValue(&list, );

    deleteElemByValue(&list, );

    // 顺序遍历顺序表

    traverseList(&list);

}

　　主文件main.c中的代码：

#include <SeqList.h>

//主函数

int main() {

    testMySeqList(); // 顺序表（顺序存储）顺序结构的测试

    return ;

}

　　运行结果如下：

顺序表初始化成功！当前总长度：5

顺序表当前长度：0

顺序表是否为空？是

成功将元素6插入到表头！

成功将元素5插入到表头！

成功将元素4插入到表头！

成功将元素3插入到表头！

成功将元素2插入到表头！

扩容成功，顺序表容量扩大到10！

成功将元素1插入到表头！

顺序遍历顺序表：1   2   3   4   5   6

成功将元素6插入到表尾！

成功将元素7插入到表尾！

成功将元素7插入到表尾！

成功将元素7插入到表尾！

扩容成功，顺序表容量扩大到15！

成功将元素8插入到表尾！

顺序遍历顺序表：1   2   3   4   5   6   6   7   7   7   8

成功添加7到顺序表第9个位置！

成功添加7到顺序表第9个位置！

成功添加7到顺序表第9个位置！

成功添加7到顺序表第9个位置！

扩容成功，顺序表容量扩大到20！

成功添加7到顺序表第9个位置！

顺序遍历顺序表：1   2   3   4   5   6   6   7   7   7   7   7   7   7   7   8

成功将7插入到顺序表的15位置！

成功将0插入到顺序表的0位置！

顺序遍历顺序表：0   1   2   3   4   5   6   6   7   7   7   7   7   7   7   7   7   8

删除表头元素成功，返回表头元素：0

删除表头元素成功，返回表头元素：1

删除表头元素成功，返回表头元素：2

删除表头元素成功，返回表头元素：3

顺序遍历顺序表：4   5   6   6   7   7   7   7   7   7   7   7   7   8

删除表尾元素成功，返回表尾元素：8

删除表尾元素成功，返回表尾元素：7

删除表尾元素成功，返回表尾元素：7

删除表尾元素成功，返回表尾元素：7

顺序遍历顺序表：4   5   6   6   7   7   7   7   7   7

成功将6从顺序表的3位置删除！

成功将7从顺序表的3位置删除！

成功将7从顺序表的3位置删除！

顺序遍历顺序表：4   5   6   7   7   7   7

成功将7从顺序表的3位置删除！

成功删除7在顺序表中出现的第一个数据（3位置）！

10没有在顺序表中出现过，删除失败！

顺序遍历顺序表：4   5   6   7   7   7

Process returned 0 (0x0)   execution time : 0.172 s

Press any key to continue.

巴特西

【数据结构】之顺序表（C语言描述）

最新文章

热门文章