✨✨✨专栏:数据结构
🧑🎓个人主页:SWsunlight
不怕别人看不起,就怕自己不争气。路是人走出来的,关键要靠自己闯。振作起来,生活的含义就是前进。
目录
一、顺序表的概念:
二、运算:
三、实现:
1、创建顺序表:
2、初始化:
3、扩容:
4、尾插:
5、尾删:
7、头删:
8、指定位置插:
9、指定位置删 :
10、查找:
11、打印:
12、销毁:
编辑 四、代码
SeqList.h头文件
SeqList.c源文件
test.c测试文件
一、顺序表的概念:
定义: 是一种线性表(某一类具有相同特性的数据的集合)的存储结构,它用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的两个元素在物理位置上也相邻;
特点:
- 顺序表具有动态分配空间、支持随机访问和顺序访问,逻辑顺序与物理顺序一致。
- 每个元素可以都有唯一的位置,可以通过索引直接访问元素。
- 元素可以是任意类型,包括基本数据类型、结构体等。
分类:
- 静态顺续表(空间有限)
- 动态顺序表(可以申请空间,空间是动态的,按需申请)
二、运算:
- 初始化和销毁
- 增添数据,删除数据,查找数据,修改数据
- 遍历
三、实现:
1、创建顺序表:
动态顺序表的成员包括:数组(动态的),有效数据个数以及空间容量
用指针来接受动态内存开辟的空间;
2、初始化:
初始情况下:
3、扩容:
在初始情况下:空间是没有申请的,在放入数据前要先申请空间:
4、尾插:
进来判断是否需要扩容,若是需要,则先扩容在插入值
5、尾删:
将最后一个元素删掉,有效个数-1即可
6、头插:
步骤大差不差,但是要给数组里面的数据全部后移一位,才能插入
7、头删:
比起尾删,要麻烦点,要将头元素后面的元素全部前移一位,直接将头元素覆盖掉
8、指定位置插:
多传一个参数,将pos传过来,就是要删除第几个元素,需要将pos后面的全部元素后移一位,腾出一个位置个pos的元素
9、指定位置删 :
将pos之后的数据前挪一下
10、查找:
遍历,返回下标即可
11、打印:
又是遍历
12、销毁:
直接对指针销毁即可,因为在动数据时,我们没有改变指针的地址,所以可以直接free掉
四、代码
SeqList.h头文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h>typedef int SLDataType;typedef struct SeqList {SLDataType* arr;//存储的数据int size;//有效数据个数;int capacity;//空间容量(字节)}SL;//初始化结构表 void SLInit(SL* ps); // 数据表的销毁 void SLDestroy(SL* ps); //扩容: void SLCheckCapacity(SL* ps); //顺序表的打印: void SLPrint(SL ps); //数据表的插入与删除; //尾插: void SLPushBack(SL* ps, SLDataType x); //尾删 void SLPopBack(SL* ps); //头插: void SLPushFront(SL* ps, SLDataType x); //头删: void SLPopFront(SL* ps); //指定位置插: void SLInsert(SL* ps, int pos, SLDataType x); //指定位置删: void SLErase(SL* ps, int pos); //查找: int SLFind(SL* ps, SLDataType x);
SeqList.c源文件
#define _CRT_SECURE_NO_WARNINGS 3 #include"SeqLIst.h" //初始化结构表 void SLInit(SL* ps) {//空指针ps->arr = NULL;//数据和内容都为0ps->size = ps->capacity = 0;} //数据表的销毁:将申请的动态内存销毁掉; void SLDestroy(SL* ps) {if (ps->arr){free(ps->arr);}ps->arr = NULL; } //查找 int SLFind(SL* ps, SLDataType x) {assert(ps);int i;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x){//返回找到的下标return i;}}return -1; } //打印: void SLPrint(SL ps) {int i;for (i = 0; i < ps.size; i++){printf("%d\n", ps.arr[i]);}printf("数据个数:%d\n", ps.size);} //扩容: void SLCheckCapacity(SL* ps) {//断言,防止顺序表传空指针assert(ps);//若是没有则先给定义一个:没有则申请4个空间int newcapacity = (ps->capacity == 0 ? 4 : 2 * (ps->capacity));//查看空间够不够:当空间大小与有效数据个数相同时。说明空间不够if (ps->capacity == ps->size){//要先申请空间:申请的内存为 容量*空间大小 SLDataType* pa = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//判断申请是否成功:if (pa == NULL){perror("realloc");return 1;}//成功了://将空间给arrps->arr = pa;//将改好的空间容量赋值给capacity;ps->capacity = newcapacity;}} //头插: void SLPushFront(SL* ps, SLDataType x) {//先确定是否需要扩容;SLCheckCapacity(ps);//先将数据整体后移int i;for (i = ps->size; i > 0; i--){//前一个往后放置:ps->arr[i] = ps->arr[i - 1];}//尾插:ps->arr[0] = x;ps->size++; } //头删 void SLPopFront(SL* ps) {assert(ps);assert(ps->arr);int i;for (i = 1; i < ps->size; i++)//(i=0;i<ps->size-1;i++){ps->arr[i - 1] = ps->arr[i];//(ps->arr[i] = ps->arr[i+1]);}ps->size--; } //尾插: void SLPushBack(SL* ps, SLDataType x) {//先确定是否需要扩容;SLCheckCapacity(ps);//插入数据:ps->arr[ps->size++] = x;} //尾删: void SLPopBack(SL* ps) {//断言!防止传空指针!assert(ps);//防止数据为空!assert(ps->arr);//数据个数减一即可;ps->size--; } //指定位置插:pos为下标 void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);//下标必须在[0,size);assert(pos >= 0 && pos < ps->size);SLCheckCapacity(ps);int i;for (i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++; } //指定位置删: void SLErase(SL* ps, int pos) {assert(ps);assert(pos >= 0 && pos < ps->size);int i;for (i = pos; i < ps->size-1; i++){//后往前摞ps->arr[i] = ps->arr[i + 1];}ps->size--; }
test.c测试文件
#define _CRT_SECURE_NO_WARNINGS 3 #include"SeqList.h"//测试; void SLest01() {SL arr;//初始化:SLInit(&arr);//尾插:SLPushBack(&arr, 5);SLPushBack(&arr, 6);//头插:SLPushFront(&arr, 7);SLPushFront(&arr, 8);//打印,值传递即可!SLPrint(arr); //指定插入:SLInsert(&arr, 0, 99);//指定位置删SLErase(&arr, 0);//尾删://SLPopBack(&arr);//头删://SLPopFront(&arr);SLPrint(arr);int FInd = SLFind(&arr, 99);if (FInd < 0){printf("没找到");}else{printf("找到了!");}SLDestroy(&arr);}int main() {SLest01();return 0; }
你的三连就是对博主最大的支持!