24/07/08数据结构(2.1203)顺序表实现
创始人
2025-01-15 13:34:28
0次

size属于结构体的作用域

如果要访问一个结构体的指针用->

如果要访问一个结构体的变量用. 点操作

#include
#include
#include
#include"seqlist.h"

//typedef struct seqList{
//    SLDataType* _data; //需要动态开辟的数组
//    size_t _size; //有效元素的个数
//    size_t _capacity; //挡枪可以存放的最大元素个数
//}seqList;

void initSeqList(seqList* sl){
    sl->_data = NULL;
    sl->_size = sl->_capacity = 0;
}

//尾插一个数据o(1)
void pushBack(seqList* sl, SLDataType val){
    //检查容量
    checkCapacity(sl);
    sl->_data[sl->_size] = val;
    ++sl->_size;
}

void checkCapacity(seqList* sl){
    //如果元素个数和容量相同,说明空间满了,需要扩容空间
    if (sl->_size == sl->_capacity){
        int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;
        //开一个更大的空间,拷贝已有数据,释放原有空间
        SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);
        memcpy(tmp, sl->_data, sizeof(SLDataType)* sl->_size);
        free(sl->_data);
        //更新
        sl->_data = tmp;
        sl->_capacity = newCapacity;
    }
}

void printSeList(seqList* sl){
    for (int i = 0; i < sl->_size; ++i){
        printf("%d", sl->_data[i]);
    }
    printf("\n");
}

void popBack(seqList* sl){
    if (sl == NULL)
        return;
    if (sl->_size>0)
        sl->_size--;
}

//头插 给顺序表的第一个位置插入元素o(n)
//一般不进行头插:效率低
void pushFront(seqList* sl, SLDataType val){
    if (sl == NULL)
        return;
    //0.检查容量
    checkCapacity(sl);
    //1.移动元素:从后向前移动
    int end = sl->_size;
    while (end > 0){
        sl->_data[end] = sl->_data[end - 1];
        --end;
    }
    //2.头插
    sl->_data[0] = val;

    sl->_size++;
}
//头删: 移动元素:[1,size)全部向前移动一个位置
void popFront(seqList* sl){
    if (sl == NULL || sl->_size == 0)
        return;
    int start = 1;
    while (start < sl->_size){
        sl->_data[start - 1] = sl->_data[start];
        ++start;
    }

    --sl->_size;
}

//插入
void insert(seqList* sl, int pos, SLDataType val){
    //检查容量
    if (sl == NULL)
        return;
    checkCapacity(sl);
    //移动元素
    int end = sl->_size;
    while (end > pos){
        sl->_data[end] = sl->_data[end - 1];
        --end;
    }
    //插入数据
    sl->_data[pos] = val;
    //更新
    sl->_size++;
}

void test(){
    seqList sl;
    initSeqList(&sl);
    pushBack(&sl, 1);
    pushBack(&sl, 2);
    pushBack(&sl, 3);
    pushBack(&sl, 4);
    pushBack(&sl, 5);
    insert(&sl, 1, 10); 
    insert(&sl, 2, 20);
    printSeList(&sl);
    insert(&sl, 0, -1);
    printSeList(&sl);
    insert(&sl, sl._size, 3);
    printSeList(&sl);
    

}
int main(){
    
    test();
    system("pause");
    return 0;
}

完整的代码:

.h头文件

typedef int SLDataType;

typedef struct seqList{
    SLDataType* _data; //需要动态开辟的数组
    size_t _size; //有效元素的个数
    size_t _capacity; //当前可以存放的最大元素个数
}seqList;

void initSeqList(seqList* sl);

//尾插一个数据
void pushBack(seqList* sl, SLDataType val);

void checkCapacity(seqList* sl);

void printSeList(seqList* sl);

void popBack(seqList* sl);

.c文件

#include
#include
#include
#include"seqlist.h"

//typedef struct seqList{
//    SLDataType* _data; //需要动态开辟的数组
//    size_t _size; //有效元素的个数
//    size_t _capacity; //挡枪可以存放的最大元素个数
//}seqList;

void initSeqList(seqList* sl){
    sl->_data = NULL;
    sl->_size = sl->_capacity = 0;
}

//尾插一个数据o(1)
void pushBack(seqList* sl, SLDataType val){
    //检查容量
    checkCapacity(sl);
    sl->_data[sl->_size] = val;
    ++sl->_size;
}

void checkCapacity(seqList* sl){
    //如果元素个数和容量相同,说明空间满了,需要扩容空间
    if (sl->_size == sl->_capacity){
        int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;
        //开一个更大的空间,拷贝已有数据,释放原有空间
        SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);
        memcpy(tmp, sl->_data, sizeof(SLDataType)* sl->_size);
        free(sl->_data);
        //更新
        sl->_data = tmp;
        sl->_capacity = newCapacity;
    }
}

void printSeList(seqList* sl){
    for (int i = 0; i < sl->_size; ++i){
        printf("%d", sl->_data[i]);
    }
    printf("\n");
}

void popBack(seqList* sl){
    if (sl == NULL)
        return;
    if (sl->_size>0)
        sl->_size--;
}

//头插 给顺序表的第一个位置插入元素o(n)
//一般不进行头插:效率低
void pushFront(seqList* sl, SLDataType val){
    if (sl == NULL)
        return;
    //0.检查容量
    checkCapacity(sl);
    //1.移动元素:从后向前移动
    int end = sl->_size;
    while (end > 0){
        sl->_data[end] = sl->_data[end - 1];
        --end;
    }
    //2.头插
    sl->_data[0] = val;

    sl->_size++;
}
//头删: 移动元素:[1,size)全部向前移动一个位置
void popFront(seqList* sl){
    if (sl == NULL || sl->_size == 0)
        return;
    int start = 1;
    while (start < sl->_size){
        sl->_data[start - 1] = sl->_data[start];
        ++start;
    }

    --sl->_size;
}

//插入
void insert(seqList* sl, int pos, SLDataType val){
    //检查容量
    if (sl == NULL)
        return;
    checkCapacity(sl);
    //移动元素
    int end = sl->_size;
    while (end > pos){
        sl->_data[end] = sl->_data[end - 1];
        --end;
    }
    //插入数据
    sl->_data[pos] = val;
    //更新
    sl->_size++;
}

//删除的操作
void erase(seqList* sl, int pos){
    if (sl == NULL || sl->_size == 0)
        return;
    //有效位置:[0,size)
    if (pos >= 0 && pos < sl->_size){
        //1.移动元素:(pos,size),从pos + 1开始,从前往后依次移动
        int start = pos + 1;
        while (start < sl-> _size){
            sl->_data[start - 1] = sl->_data[start];
            ++start;
        }
        --sl->_size;
    }
}

int empty(seqList* sl){
    if (sl = NULL || sl->_size == 0)
        return 1;
    else
        return 0;
}

int size(seqList* sl){
    if (sl == NULL)
        return 0;
    else
        return sl->_size;
}

int findIdx(seqList* sl, SLDataType val){
    int i = 0;
    for (; i < sl->_size; ++i){
        if (sl->_data[i] == val)
            return i;
    }
    return -1;
}

SLDataType getIdx(seqList* sl, int pos){
    
        return sl->_data[pos];
}

void destorySeqList(seqList* sl){
    if (sl){
        //释放堆上申请的空间
        if (sl->_data){
            free(sl->_data);
            sl->_data = NULL;
        }
    }
}

void test(){
    seqList sl;
    initSeqList(&sl);
    pushBack(&sl, 1 );
    pushBack(&sl, 2 );
    pushBack(&sl, 3 );
    pushBack(&sl, 4 );
    pushBack(&sl, 5 );
    erase(&sl, 3);
    erase(&sl, 2);
    erase(&sl, 0);
    printSeList(&sl);
}

//void test(){
//    seqList sl;
//    initSeqList(&sl);
//    pushBack(&sl, 1);
//    pushBack(&sl, 2);
//    pushBack(&sl, 3);
//    pushBack(&sl, 4);
//    pushBack(&sl, 5);
//    insert(&sl, 1, 10); 
//    insert(&sl, 2, 20);
//    printSeList(&sl);
//    insert(&sl, 0, -1);
//    printSeList(&sl);
//    insert(&sl, sl._size, 3);
//    printSeList(&sl);
//    
//
//}
int main(){
    
    test();
    system("pause");
    return 0;
}

由此可以看出顺序表的一些特性:

        1.空间联系

        2.支持随机访问

        3.尾插,尾删效率高:O(1)

        4.空间利用率高,不容易造成内存碎片

        5.其他位置插入,删除效率低:O(n) ---> 移动元素

        6.增容代价比较大

上一篇：HTML5表单的自动验证、取消验证、自定义错误信息

下一篇：如何使一个盒子水平垂直居中（常用的）

相关内容

热门资讯

为了进一步！微信小程序免费黑科... 为了进一步！微信小程序免费黑科技透视，新道游app辅助器教材教程（有挂规律）1、玩家可以在微信小程序...
如何分辨真伪！新超凡软件辅助，... 【福星临门，好运相随】；如何分辨真伪！新超凡软件辅助，微乐陕西小程序脚本，新版2025教程（原来有开...
实测发现！微乐贵阳捉鸡麻将挂软... 您好：微乐贵阳捉鸡麻将挂软件这款游戏可以开挂的，确实是有挂的，很多玩家在这款游戏中打牌都会发现很多用...
带你了解！牛总管一定要牛辅助，... 带你了解！牛总管一定要牛辅助，雀友会潮汕图片辅助器，wepoke教程（原来有开挂辅助神器）是一款可以...
推荐十款！爱玩联盟辅助下载，悟... 推荐十款！爱玩联盟辅助下载，悟空大厅微信辅助，解说技巧（原来有开挂辅助黑科技）；推荐十款！爱玩联盟辅...
最新技巧！雀友会辅助潮汕麻将脚... 最新技巧！雀友会辅助潮汕麻将脚本，微信小程序微乐怎么才能发好牌，2025版教程（原来有开挂辅助助手）...
玩家亲测！欢乐达人脚本，wep... 玩家亲测！欢乐达人脚本，wepoker插件下载，科技教程（原来有开挂辅助app）；作为系统规律正版授...
推荐攻略！悟空大厅辅助助手下载... 推荐攻略！悟空大厅辅助助手下载安装，hhpoker是正规的吗，揭秘教程（原来有开挂辅助器）;是一种具...
玩家必看！花花生活圈私人局辅助... 玩家必看！花花生活圈私人局辅助器，新青鸟辅助，高科技教程（原来有开挂辅助器）;AI辅助机器人普及解说...
技术分享！兴动平台辅助下载，财... 技术分享！兴动平台辅助下载，财神十三张脚本辅助，wepoke教程（原来有开挂辅助挂）；最新版2026...