C语言顺序表实现：数据结构基础学习与代码示例

本文将介绍C语言实现顺序表数据结构的基本操作，并提供完整的代码示例。通过该代码示例，您将学习到如何使用顺序表进行数据的插入、删除、查找、排序等操作，以及如何对顺序表进行初始化、销毁和清空等操作。

1. 顺序表的基本概念

顺序表是一种线性表，它使用一块连续的内存空间来存储数据元素。顺序表中的数据元素按照其逻辑顺序依次存储在内存中。

2. 顺序表的C语言实现

// Created by DELL on 2023/10/7.
//
#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100 // 初始化顺序表的大小
#define LISTINCREMENT 10 // 每次扩容的大小
#define ElemType int // 数据元素的类型
#define Status int // 返回状态码的类型
#define OK 1
#define ERROR 0

// 定义线性表的数据结构
typedef struct {
    ElemType *elem; // 储存线性表的数组
    int length; // 线性表的长度;
    int listsize; // 当前线性表的容量
} SqList;

// 初始化线性表为空表
Status InitList(SqList *L) {
    L->elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (L->elem == NULL) {
        return ERROR;
    }
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return OK;
}

// 销毁线性表
Status DestroyList(SqList *L) {
    free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
    return OK;
}

// 清空线性表
Status ClearList(SqList *L) {
    L->length = 0;
    return OK;
}

// 判断线性表是否为空
Status ListEmpty(SqList L) {
    if (L.length == 0) return ERROR;
    else return OK;
}

// 求线性表长度
Status Listlength(SqList L) {
    return L.length;
}

// 获取线性表中指定位置的元素
Status GetElem(SqList L, int i, ElemType *e) {
    if (i < 0 || i > L.length) return ERROR;
    *e = L.elem[i - 1];
    return OK;
}

// 获取元素e的位置
Status LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

// 求前驱
Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e) {
    int i = LocateElem(L, cur_e);
    if (i == 1 || i == 0) return ERROR;
    *pre_e = L.elem[i - 2];
    return OK;
}

// 求后继
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e) {
    int i = LocateElem(L, cur_e);
    if (i == 0 || i == L.length) return ERROR;
    *next_e = L.elem[i];
    return OK;
}

// 在线性表指定位置插入元素
Status ListInsert(SqList *L, int i, ElemType e) {
    // 分配空间操作
    if (i < 1 || i > L->length + 1) return ERROR;
    if (L->length > L->listsize) {
        ElemType *newbase = (ElemType *) realloc(L->elem, sizeof(ElemType) * (L->listsize + LISTINCREMENT));
        if (!newbase) return ERROR;
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }
    // 开始插入
    ElemType *p = &(L->elem[i - 1]);
    for (ElemType *q = &(L->elem[L->length - 1]); q >= p; q--) {
        *(q + 1) = *q;
    }
    *p = e;
    L->length++;
    return OK;
}

// 删除线性表指定位置的元素
Status ListDelete(SqList *L, int i, ElemType *e) {
    if (i < 1 || i > L->length) return ERROR;
    ElemType *p = &(L->elem[i - 1]);
    *e = *p;
    for (ElemType *q = p; q < &(L->elem[L->length - 1]); q++) {
        *q = *(q + 1);
    }
    L->length--;
    return OK;
}

// 显示线性表
Status DisplayList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.elem[i]);
    }
    printf("\n");
    return OK;
}

// 合并两个非递减有序的线性表
Status MergeList(SqList La, SqList Lb, SqList *Lc) {
    InitList(Lc);
    int i = 1;
    int j = 1;
    int k = 0;
    ElemType *ai;
    ElemType *bj;
    int La_len = Listlength(La);
    int Lb_len = Listlength(Lb);
    while ((i <= La_len) && (j <= Lb_len)) {
        GetElem(La, i, ai);
        GetElem(Lb, j, bj);
        if (*ai < *bj) {
            ListInsert(Lc, k, *ai);
            i++;
        } else {
            ListInsert(Lc, k, *bj);
            j++;
        }
    }
    while (i <= La_len) {
        GetElem(La, i, ai);
        ListInsert(Lc, k, *ai);
        i++;
    }
    while (j <= Lb_len) {
        GetElem(Lb, j, bj);
        ListInsert(Lc, k, *bj);
        j++;
    }
    return OK;
}

// 主菜单
int main() {
    int choice;
    printf("1---初始化一个线性表\n");
    printf("2---销毁线性表：\n");
    printf("3---清空线性表\n");
    printf("4---判断线性表是否为空\n");
    printf("5---求线性表长度\n");
    printf("6---获取线性表中指定位置的元素\n");
    printf("7---获取线性表元素的位置\n");
    printf("8---求前驱\n");
    printf("9---求后继\n");
    printf("10---在线性表指定位置插入元素\n");
    printf("11---删除线性表指定位置的元素\n");
    printf("12---显示线性表\n");
    printf("13---合并两个非递减有序的线性表\n");
    printf("退出，请输入一个负数!\n");

    SqList L1;
    do {
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                if (InitList(&L1) == OK) {
                    printf("初始化成功\n");
                } else {
                    printf("初始化失败\n");
                }
                break;
            case 2:
                if (DestroyList(&L1) == OK) {
                    printf("销毁成功\n");
                } else {
                    printf("销毁失败\n");
                }
                break;
            case 3:
                if (ClearList(&L1) == OK) {
                    printf("清空成功\n");
                } else {
                    printf("清空失败\n");
                }
                break;
            case 4:
                if (ListEmpty(L1) == OK) {
                    printf("线性表为空\n");
                } else {
                    printf("线性表不为空\n");
                }
                break;
            case 5:
                printf("线性表长度为：%d\n", Listlength(L1));
                break;
            case 6:
                printf("请输入需要获取元素的位置：\n");
                int position;
                scanf("%d", &position);
                ElemType e;
                if (GetElem(L1, position, &e) == OK) {
                    printf("指定位置的元素为：%d\n", e);
                } else {
                    printf("指定位置超出范围\n");
                }
                break;
            case 7:
                printf("请输入需要获取位置的元素：\n");
                int element;
                scanf("%d", &element);
                int pos = LocateElem(L1, element);
                if (pos != 0) {
                    printf("元素的位置为：%d\n", pos);
                } else {
                    printf("元素不存在\n");
                }
                break;
            case 8:
                printf("请输入需要求前驱的元素：\n");
                int cur_e;
                scanf("%d", &cur_e);
                ElemType pre_e;
                if (PriorElem(L1, cur_e, &pre_e) == OK) {
                    printf("前驱元素为：%d\n", pre_e);
                } else {
                    printf("该元素没有前驱或元素不存在\n");
                }
                break;
            case 9:
                printf("请输入需要求后继的元素：\n");
                int cur_e2;
                scanf("%d", &cur_e2);
                ElemType next_e;
                if (NextElem(L1, cur_e2, &next_e) == OK) {
                    printf("后继元素为：%d\n", next_e);
                } else {
                    printf("该元素没有后继或元素不存在\n");
                }
                break;
            case 10:
                printf("请输入插入位置和元素：\n");
                int insert_pos, insert_ele;
                scanf("%d %d", &insert_pos, &insert_ele);
                if (ListInsert(&L1, insert_pos, insert_ele) == OK) {
                    printf("插入成功\n");
                } else {
                    printf("插入失败\n");
                }
                break;
            case 11:
                printf("请输入删除位置：\n");
                int delete_pos;
                scanf("%d", &delete_pos);
                ElemType deleted_e;
                if (ListDelete(&L1, delete_pos, &deleted_e) == OK) {
                    printf("删除成功，删除元素为：%d\n", deleted_e);
                } else {
                    printf("删除失败\n");
                }
                break;
            case 12:
                DisplayList(L1);
                break;
            case 13:
                printf("请先初始化两个非递减有序的线性表：\n");
                SqList L2, L3;
                InitList(&L2);
                InitList(&L3);
                printf("请输入第一个线性表的数据个数：\n");
                int num1, num2;
                scanf("%d", &num1);
                printf("请输入第一个线性表的数据：\n");
                for (int i = 0; i < num1; i++) {
                    int a;
                    scanf("%d", &a);
                    L2.elem[L2.length] = a;
                    L2.length++;
                }
                printf("请输入第二个线性表的数据个数：\n");
                scanf("%d", &num2);
                printf("请输入第二个线性表的数据：\n");
                for (int i = 0; i < num2; i++) {
                    int b;
                    scanf("%d", &b);
                    L3.elem[L3.length] = b;
                    L3.length++;
                }
                if (MergeList(L2, L3, &L1) == OK) {
                    printf("合并成功\n");
                    printf("合并后的线性表：\n");
                    DisplayList(L1);
                } else {
                    printf("合并失败\n");
                }
                break;
            default:
                if (choice < 0) {
                    printf("退出程序\n");
                    free(L1.elem);
                    L1.elem = NULL;
                } else {
                    printf("无效操作\n");
                }
                break;
        }
    } while (choice >= 0);

    return 0;
}

3. 代码示例

上面的代码示例实现了顺序表的基本操作，包括初始化、销毁、清空、判断空、求长度、获取元素、查找元素、求前驱、求后继、插入元素、删除元素、显示元素等操作。此外，代码还实现了合并两个非递减有序线性表的功能。

4. 使用示例

初始化线性表
插入元素
显示线性表
清空线性表
销毁线性表
合并两个非递减有序的线性表

5. 总结

本文介绍了C语言实现顺序表数据结构的基本操作，并提供了完整的代码示例。顺序表是一种常用的数据结构，它在很多场景中都有着广泛的应用。希望本文能帮助您更好地理解顺序表的概念，并掌握其C语言实现方法。