投稿
  1. 首页
  2. C

使用C语言实现顺序表

code • 2022-4-19 • C • 阅读 39

使用C语言实现顺序表,第1张

C语言实现顺序表 定义结构体 
//结构体
typedef struct {
    int *data;   //动态分配的指针
    int maxsize; //顺序表的最大容量
    int length;  //静态顺序表的当前长度
} SeqList;
此处声明函数 
//声明基本 *** 作
void initList(SeqList *L);
void increaseSize(SeqList *L);
int getLength(SeqList L);
int locateElem(SeqList L, int e);
int getElem(SeqList L, int i);
bool insertData(SeqList *L, int i, int e);
bool deleteData(SeqList *L, int i, int *e);
void printList(SeqList L);
bool isEmpty(SeqList L);
void destoryList(SeqList *L);
初始化顺序表。

使用 malloc 进行内存的动态分配。

void initList(SeqList *L) {
    L->data = (int *)malloc(INITSIZE * sizeof(int)); // 使用malloc动态分类空间
    L->length = 0;                                   //设置初始长度为0
    L->maxsize = INITSIZE; //设置当前最大容量为初始容量
}
使用 realloc 函数重新分配内存。

当插入时溢出调用该方法扩容。

void increaseSize(SeqList *L) {
    printf("即将溢出，进行数组扩容\n");
    int tempSize = L->maxsize;
    L->data = (int *)realloc(L->data, INITSIZE * 2 * sizeof(int));
    L->maxsize = L->maxsize * 2;
    printf("扩容成功，原容量为:%d,扩容后容量为:%d\n", tempSize, L->maxsize);
}
获取当前表的长度。

int getLength(SeqList L) {
    printf("当前表的最大容量：%d\n", L.maxsize);
    return L.length;
}
查找值为 e 的位序。

注意位序从 1 开始而不是 0。

int locateElem(SeqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}
查找位序为 i 的值。

int getElem(SeqList L, int i) {
    if (i < 1 || i > L.length) { //查找的元素位序不合法
        printf("查找的元素位序不合法！\n");
        return 0;
    } else {
        return L.data[i - 1];
    }
}
在第 i 个位序中插入元素 e。

bool insertData(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) { //插入位置不合法
        return false;
    } else if (L->length == L->maxsize) { //容量已满，扩容
        increaseSize(L);
    }
    for (int j = L->length; j >= i; j--) { //将第j-1个元素的值赋值给第j个元素
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e; //将e赋值给第i-1个元素
    L->length++;        //当前长度+1
    return true;
}
删除第 i 个位序的值。

bool deleteData(SeqList *L, int i, int *e) {
    if (i < 1 || i > L->length + 1) { //位置不合法
        return false;
    } else {
        *e = L->data[i - 1];
        printf("将被删除的值为:%d\n", *e);
        for (int j = i; j < L->length; j++) { //将后一个元素的值赋值给前一个元素
            L->data[j - 1] = L->data[j];
        }
        L->length--;
        return true;
    }
}
判断表是否为空。

bool isEmpty(SeqList L) { return L.length == 0; }
销毁表，释放空间。

void destoryList(SeqList *L) {
    free(L->data);
    L->length = 0;
    L->maxsize = 0;
}
遍历顺序表，打印输出。

void printList(SeqList L) {
    printf("打印当前表\n");
    for (int i = 0; i < L.length; i++) {
        printf("L.data[%d]=%d\n", i, L.data[i]);
    }
}
测试结果


完整代码 
#include 
#include 
#include 
#define INITSIZE 10 //定义初始容量

//结构体数组
typedef struct {
    int *data;   //动态分配的指针
    int maxsize; //顺序表的最大容量
    int length;  //静态顺序表的当前长度
} SeqList;

//声明基本 *** 作
void initList(SeqList *L);
void increaseSize(SeqList *L);
int getLength(SeqList L);
int locateElem(SeqList L, int e);
int getElem(SeqList L, int i);
bool insertData(SeqList *L, int i, int e);
bool deleteData(SeqList *L, int i, int *e);
void printList(SeqList L);
bool isEmpty(SeqList L);
void destoryList(SeqList *L);

/*
初始化顺序表
*/
void initList(SeqList *L) {
    L->data = (int *)malloc(INITSIZE * sizeof(int)); // 使用malloc动态分类空间
    L->length = 0;                                   //设置初始长度为0
    L->maxsize = INITSIZE; //设置当前最大容量为初始容量
}

/*
增加动态数组长度，默认扩容为原来的两倍
*/
void increaseSize(SeqList *L) {
    printf("即将溢出，进行数组扩容\n");
    int tempSize = L->maxsize;
    L->data = (int *)realloc(L->data, INITSIZE * 2 * sizeof(int));
    L->maxsize = L->maxsize * 2;
    printf("扩容成功，原容量为:%d,扩容后容量为:%d\n", tempSize, L->maxsize);
}

/*
获取当前表的长度
*/
int getLength(SeqList L) {
    printf("当前表的最大容量：%d\n", L.maxsize);
    return L.length;
}

/*
查找值为e的元素的位序
如果能够找到，返回该元素的位置，否则返回0。

*/
int locateElem(SeqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

/*
获取第i个元素的值
*/
int getElem(SeqList L, int i) {
    if (i < 1 || i > L.length) { //查找的元素位序不合法
        printf("查找的元素位序不合法！\n");
        return 0;
    } else {
        return L.data[i - 1];
    }
}

/*
在第i个位置插入元素e
*/
bool insertData(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) { //插入位置不合法
        return false;
    } else if (L->length == L->maxsize) { //容量已满，扩容
        increaseSize(L);
    }
    for (int j = L->length; j >= i; j--) { //将第j-1个元素的值赋值给第j个元素
        L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = e; //将e赋值给第i-1个元素
    L->length++;        //当前长度+1
    return true;
}

/*
删除表第i个位序的值。
如果删除成功则返回true并存入e。

删除失败则返回false
*/
bool deleteData(SeqList *L, int i, int *e) {
    if (i < 1 || i > L->length + 1) { //位置不合法
        return false;
    } else {
        *e = L->data[i - 1];
        printf("将被删除的值为:%d\n", *e);
        for (int j = i; j < L->length; j++) { //将后一个元素的值赋值给前一个元素
            L->data[j - 1] = L->data[j];
        }
        L->length--;
        return true;
    }
}

/*
判断表是否为空
*/
bool isEmpty(SeqList L) { return L.length == 0; }

/*
释放表的空间，销毁表
*/
void destoryList(SeqList *L) {
    free(L->data);
    L->length = 0;
    L->maxsize = 0;
}

/*
遍历顺序表，打印输出
*/
void printList(SeqList L) {
    printf("打印当前表\n");
    for (int i = 0; i < L.length; i++) {
        printf("L.data[%d]=%d\n", i, L.data[i]);
    }
}

int main(int argc, char const *argv[]) {
    SeqList L;
    printf("初始化当前顺序表...\n");
    initList(&L);
    if (isEmpty(L)) {
        printf("该表为空!\n");
    } else {
        printf("该表非空!\n");
    }
    printf("当前表的长度：%d\n", getLength(L));
    int num;
    printf("插入元素个数为:");
    scanf("%d", &num);
    for (int i = 0; i < num; i++) {
        insertData(&L, i + 1, i);
    }
    printList(L);
    printf("当前表的长度：%d\n", getLength(L));
    int e;
    printf("输入要获取位序的数:");
    scanf("%d", &e);
    printf("值为%d的位序为:%d\n", e, locateElem(L, e));
    int i;
    printf("输入位序:");
    scanf("%d", &i);
    printf("位序为%d的值为:%d\n", i, getElem(L, i));
    int *delNum, delLocal;
    printf("输入要删除位序的值:");
    scanf("%d", &delLocal);
    bool flag = deleteData(&L, delLocal, delNum);
    if (flag) {
        printf("第%d个位序被删除，删除的值为:%d\n", delLocal, *delNum);
        printf("当前表的长度：%d\n", getLength(L));
    } else {
        printf("输入的位序不合法，删除失败！\n");
    }
    printList(L);
    printf("销毁该表！\n");
    destoryList(&L);

    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/673613.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-19
下一篇 2022-04-19

发表评论

登录后才能评论

评论列表（0条）

保存