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表单的自动验证、取消验证、自定义错误信息

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

相关内容

热门资讯

透视窍门！德普之星怎么开辅助，... 透视窍门！德普之星怎么开辅助，德扑之心免费透视（透视）好像存在有脚本脚本（哔哩哔哩）1、游戏颠覆性的...
透视资料！hhpoker辅助软... 透视资料！hhpoker辅助软件下载，模拟器打开hhpoker（透视）好像是有透视器（哔哩哔哩）在进...
透视课程！德普之星透视辅助，德... 透视课程！德普之星透视辅助，德普之星怎么设置埋牌（透视）总是有透视方法（哔哩哔哩）1、德普之星怎么设...
透视模块！wpk透视辅助下载，... 您好，wpk透视辅助下载这款游戏可以开挂的，确实是有挂的，需要了解加去威信【485275054】很多...
透视操作！购买的wpk辅助在哪... 透视操作！购买的wpk辅助在哪里下载，wpk系统是否存在作必弊行为（透视）真是是真的脚本教程（哔哩哔...
透视绝活儿！aapoker发牌... 透视绝活儿！aapoker发牌逻辑，aapoker脚本（透视）真是真的是有透视工具（哔哩哔哩）1、任...
透视演示！aapoker透视方... 透视演示！aapoker透视方法，aapoker透视脚本下载（透视）其实是真的脚本脚本（哔哩哔哩）1...
透视要领！hhpoker俱乐部... 透视要领！hhpoker俱乐部是干嘛的，hhpoker有后台操作吗（透视）真是真的有脚本器（哔哩哔哩...
透视手筋！德普软件，德普辅助器... 透视手筋！德普软件，德普辅助器怎么用（透视）都是真的有脚本技巧（哔哩哔哩）1、德普辅助器怎么用有没有...
透视讲义！wepoker分析，... 透视讲义！wepoker分析，wepoker私人定制透视（透视）果然有脚本软件（哔哩哔哩）1、该软件...