数据结构——线性顺序表c代码实现_C

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

概述
- 1.头文件
- 2.源文件
- 3.注意

概述

顺序表：

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中

1.头文件

#include
#include
#include 

//线性表(顺序表)
//实现了简单的顺序表 *** 作，包括初始化，头插，尾插，任意位置插，头删，尾删，任意位置删，修改，查找，打印，清空

typedef struct SeqList{
    int *data;
    int size;
    int cap;
} SL;

// 初始化顺序表
SL * init_seqList(int n);

// 向顺序表中插入数据(任意位置插入)
int SeqListPushIndex(SL *seq, int ind, int x);

// 向顺序表中插入数据(尾插)
int SeqListPushBack(SL *seq, int x);

// 向顺序表中插入数据(头插)
int SeqListPushFront(SL *seq, int x);

// 从顺序表中删除数据(任意位置删)
int SeqListPopIndex(SL *seq, int ind);

// 从顺序表中删除数据(头删)
int SeqListPopFront(SL *seq);

// 从顺序表中删除数据(尾删)
int SeqListPopBack(SL *seq);

//顺序表查找
int SeqListFind(SL *seq, int x);

//顺序表修改
int SeqListModify(SL *seq, int ind, int x);

//顺序表打印
void SeqListPrint(SL *seq);

//删除顺序表
void delete_seqList(SL * seq);

2.源文件

#include "seq_list.h"

// 初始化顺序表
SL * init_seqList(int n){
    SL * seq = (SL *)malloc(sizeof(SL));
    seq->data = (int *)malloc(sizeof(int) * n);
    seq->size = 0;
    seq->cap = n;
    return seq;
}


// 向顺序表中插入数据(任意位置插入)
int SeqListPushIndex(SL *seq, int ind, int x){
    assert(seq != NULL);
    if(seq->size == seq->cap){
        int * newData = (int *)realloc(seq->data, sizeof(int) * (seq->cap * 2));
        if(newData == NULL){
            printf("realloc error\n");
            return -1;
        }
        seq->data = newData;
        seq->cap = seq->cap * 2;
    }
    for(int i = seq->size; i > ind; i--){
        seq->data[i] = seq->data[i - 1];
    }
    seq->data[ind] = x;
    seq->size++;
    return 0;
}



// 向顺序表中插入数据(尾插)
int SeqListPushBack(SL *seq, int x){
    // assert(seq != NULL);
    // if(seq->size == seq->cap){
    //     int * newData = (int *)realloc(seq->data, sizeof(int) * (seq->cap * 2));
    //     if(newData == NULL){
    //         printf("realloc error\n");
    //         return -1;
    //     }
    //     seq->data = newData;
    //     seq->cap = seq->cap * 2;
    // }
    // seq->data[seq->size] = x;
    // seq->size++;
    return SeqListPushIndex(seq, seq->size, x);  //可以直接调用任意位置插入函数
}



// 向顺序表中插入数据(头插)
int SeqListPushFront(SL *seq, int x){
    // assert(seq != NULL);
    // if(seq->size == seq->cap){
    //     int * newData = (int *)realloc(seq->data, sizeof(int) * (seq->cap * 2));
    //     if(newData == NULL){
    //         printf("realloc error\n");
    //         return -1;
    //     }
    //     seq->data = newData;
    //     seq->cap = seq->cap * 2;
    // }
    // for(int i = seq->size; i > 0; i--){
    //     seq->data[i] = seq->data[i - 1];
    // }
    // seq->data[0] = x;
    // seq->size++;
    return SeqListPushIndex(seq, 0, x);   //可以直接调用任意位置插入函数
}



// 从顺序表中删除数据(任意位置删)
int SeqListPopIndex(SL *seq, int ind){
    assert(seq != NULL);
    assert(seq->size > 0);
    assert(ind >= 0 && ind < seq->size);
    for(int i = ind; i < seq->size - 1; i++){
        seq->data[i] = seq->data[i + 1];
    }
    seq->size--;
    return 0;
}


// 从顺序表中删除数据(头删)
int SeqListPopFront(SL *seq){
    // assert(seq != NULL);
    // assert(seq->size > 0);
    // for(int i = 0; i < seq->size - 1; i++){
    //     seq->data[i] = seq->data[i + 1];
    // }
    // seq->size--;
    return SeqListPopIndex(seq, 0);  //可以直接调用任意位置删除函数
}


// 从顺序表中删除数据(尾删)
int SeqListPopBack(SL *seq){
    // assert(seq != NULL);
    // assert(seq->size > 0);
    // seq->size--;

    return SeqListPopIndex(seq, seq->size - 1);  //可以直接调用任意位置删除函数
}



//顺序表查找
int SeqListFind(SL *seq, int x){
    assert(seq != NULL);
    for(int i = 0; i < seq->size; i++){
        if(seq->data[i] == x){
            return i;
        }
    }
    return -1;
}


//顺序表修改
int SeqListModify(SL *seq, int ind, int x){
    assert(seq != NULL);
    assert(ind >= 0 && ind < seq->size);
    seq->data[ind] = x;
    return 0;
}


//顺序表打印
void SeqListPrint(SL *seq){
    assert(seq != NULL);
    printf("----------size: %d, cap: %d----------\n", seq->size, seq->cap);
    for(int i = 0; i < seq->size; i++){
        printf("%d ", seq->data[i]);
    }
    printf("\n-----------------------------------\n");
}


//删除顺序表
void delete_seqList(SL * seq){
    assert(seq != NULL);
    free(seq->data);
    seq->data = NULL;
    free(seq);
}


int main(){
    int n , m;
    int pos = 0;
    scanf("%d %d", &n, &m);
    SL * seq = init_seqList(m);
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        if(x == 0){
            scanf("%d", &x);
            SeqListPushBack(seq, x);
        }else if(x == 1){
            scanf("%d", &x);
            SeqListPushFront(seq, x);
        }else if(x == 2){
            scanf("%d", &pos);
            scanf("%d", &x);
            SeqListPushIndex(seq, pos, x);
        }else if(x == 3){
            SeqListPopBack(seq);
        }else if(x == 4){
            SeqListPopFront(seq);
        }else if(x == 5){
            scanf("%d", &pos);
            SeqListPopIndex(seq, pos);
        }else if (x == 6){
            scanf("%d", &x);
            printf("%d\n", SeqListFind(seq, x));
        }else if (x == 7){
            scanf("%d", &pos);
            scanf("%d", &x);
            SeqListModify(seq, pos, x);
        }
        SeqListPrint(seq);
    }
    
    delete_seqList(seq);
    return 0;
}