注册网站邮箱格式怎么写,外网无法访问WordPress,千牛怎么做免费推广引流,制作快递网站顺序表的概念 顺序表的底层结构是数组#xff0c;对数组的封装#xff0c;实现了常用的增删改查等接口。在物理结构和逻辑结构都是连续的#xff0c;物理结构是指顺序表在计算机内存的存储方式#xff0c;逻辑结构是我们思考的形式#xff0c;顺序表和数组是类似的#x…顺序表的概念 顺序表的底层结构是数组对数组的封装实现了常用的增删改查等接口。在物理结构和逻辑结构都是连续的物理结构是指顺序表在计算机内存的存储方式逻辑结构是我们思考的形式顺序表和数组是类似的都是使用了连续的空间进行数据的保存由于是连续的空间所以逻辑结构当然也可以像数组一样去思考所以说逻辑结构也是连续的。
静态顺序表 静态顺序表是指顺序表的空间大小一开始就是给定的这也就有一个弊端如果空间给大了就会造成空间浪费也就不经济了如果空间给小了就有可能出现空间不够造成数据丢失。
动态顺序表 动态顺序表是指空间大小是可以动态的变化的随着数据的增多如果空间不够就会自动扩容所以动态顺序表相比静态的顺序表更加灵活这里我会以动态的顺序表进行讲解~~
顺序表的实现 顺序表的实现主要分为初始化插入数据删除数据查找数据以及销毁。这里我们需要三个文件一个是顺序表的头文件SeqList.h),一个是顺序表的实现文件SeqList.c),最后一个就是我们的测试文件test.c),加测试文件是用来测试代码有没有写错这也还是一个程序员的必备技能。
定义顺序表的结构 由于是动态的顺序表我们就需要一个指针变量一个变量size来记录当前存储了多少空间还有一个变量来记录当前的容量大小capacity)来判断是否需要扩容。 定义如下
typedef int SLDataType;
#define MAX_CAPACITY 4typedef struct SeqList
{SLDataType* data;int size;int capacity;
}SL;稍微解释一下为什么使用SLDataType 为了方便后期修改数据类型这次使用int万一下次使用char、double… MAX_CAPACITY 是来定义初始容量是多少下面我们会用到。
初始化与销毁
初始化很简单就是把指针置空把容量和size置为0.
void SLInit(SL* ps)//顺序表初始化
{ps-data NULL;ps-size ps-capacity 0;
}销毁需要我们释放动态内存开辟的空间。
void SLDestory(SL* ps)//顺序表销毁
{assert(ps);free(ps-data);ps-data NULL;ps-size ps-capacity 0;
}插入数据 这里的插入数据分为三种方式的插入头插尾插指定位置插入。
//插入
void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插
void SLPushPos(SL* ps, int pos, SLDataType x);//指定位置插入扩容
在插入数据之前我们需要对空间进行检查看看是否需要扩容由于插入函数有三个那就意味着要写三次扩容为了方便我们就再创建一个函数来检查是否需要扩容。
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){int newcapacity ps-capacity 0 ? MAX_CAPACITY : ps-capacity * 2;SLDataType* tmp (SLDataType*)realloc(ps-data, newcapacity * sizeof(SLDataType));if (tmp NULL){perror(realloc fail);exit(1);}ps-data tmp;ps-capacity newcapacity;}
}这里我们要注意了什么时候判断扩容扩容条件就需要当前的数据量和容量是相等的情况下进行这里我们建议以2倍或3倍来进行扩容不信的小伙伴可以自己百度一下这里涉及数学知识 但是当容量为空的时候无论你是几倍最后都是0所以我们可以先判断一下容量是否为0如果为0就赋值为我们上面定义的初始容量否则就是正常的2倍或3倍来扩容。 使用什么动态开辟函数这里使用realloc因为realloc不仅具有和malloc函数一样的开辟功能就是传入的指针为NULL时就可以看成malloc一样自动开辟一块内存空间不了解的可以翻阅我的动态内存函数详解那一篇博客而且realloc还具有扩容的功能所以推荐使用realloc进行动态开辟。 由于realloc 可能会开辟失败返回NULL所以我们用一个变量来接收直接接收的话会导致无法找回之前的空间导致内存泄漏。 尾插
尾插就是从后面开始插入数据这个很简单但是要保证传来的指针不为NULL并且检查是否需要扩容。
void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);ps-data[ps-size] x;
}头插
头插时从第一个空间开始插入数据所以要先把后面的数据向后移动避免数据丢失。
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapacity(ps);int i 0;for (i ps-size; i 0; i--){ps-data[i] ps-data[i - 1];}ps-data[0] x;ps-size;
}指定位置插入
我们需要找到指定的位置从这里开始后面的数据都需要往后移动然后腾出来位置留给新来的数据这是对中间插入的考虑我们还需要考虑如果传入的位置正好是头部或者是尾部的时候是不是也是这样很显然一个循环确实能保证这两种情况。 最后我们要注意如果传来的pos是一个负数或者超过尾部的时候我们是不允许插入的这里我们可以判断一下或者直接警告。 void SLPushPos(SL* ps, int pos, SLDataType x)//指定位置插入
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);int i 0;for (i ps-size; i pos; i--){ps-data[i] ps-data[i - 1];}ps-data[pos] x;ps-size;
}删除数据 这里的删除数据也分为三种方式的删除头删尾删指定位置删除。 在删除数据的时候我们要保证有数据可以删除否则size就会变成负数不利于后续的插入操作这里我们判断一下就可以了。 尾删
void SLPopBack(SL* ps)//尾删
{assert(ps);assert(ps-size);ps-size--;
}头删
这个很简单就是把数据往前移动最后size–就可以了。
void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps-size);int i 0;for (i 0; i ps-size - 1; i){ps-data[i] ps-data[i 1];}ps-size--;
}指定位置删除
和头删类似把数据往前移动也要注意pos 的值
void SLPopPos(SL* ps, int pos)//指定位置删除
{assert(ps);assert(ps-size);assert(pos 0 pos ps-size);int i 0;for (i pos; i ps-size - 1; i){ps-data[i] ps-data[i 1];}ps-size--;
}
查找
顾名思义就是查找一个数据的小标
int SLFind(SL* ps, SLDataType x)
{assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-data[i] x){return i;}}return -1;
}打印
为了方便测试我们可以写一个打印函数。
void SLPrint(SL sl)
{int i 0;for (i 0; i sl.size; i){printf(%d , sl.data[i]);}printf(\n);
}测试和封装
我们每写完一个函数就要进行调试 我们可以写一些测试函数来进行测试要注意测试的代码尽量包含边界情况和中间情况尤其是插入和删除函数的测试 就类似下面的测试代码
#includeSeqList.h//void Test1()
//{
// SL sl;
// SLInit(sl);
// SLPushBack(sl,1);
// SLPushBack(sl,2);
// SLPushBack(sl,3);
// SLPushFront(sl, 5);
// SLPushFront(sl, 10);
// SLPushPos(sl, 2, 50);
// SLPrint(sl);
// SLPushPos(sl, 4, 100);
// SLPrint(sl);
//
// SLDestory(sl);
//}
//
//void Test2()
//{
// SL sl;
// SLInit(sl);
// SLPushBack(sl, 1);
// SLPushBack(sl, 2);
// SLPushBack(sl, 3);
//
// SLPopPos(sl,1);
// SLPrint(sl);
//
//}void Test3()
{SL sl;SLInit(sl);SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPrint(sl);SLPushFront(sl, 10);SLPushFront(sl, 20);SLPushFront(sl, 30);SLPrint(sl);SLPushPos(sl, 1, 200);SLPrint(sl);SLPushPos(sl, sl.size ,100);SLPrint(sl);SLPushPos(sl, 0, 5000);SLPrint(sl);SLPopBack(sl);SLPrint(sl);SLPopFront(sl);SLPrint(sl);SLPopPos(sl, 0);SLPrint(sl);SLPopPos(sl, 2);SLPrint(sl);SLPopPos(sl, sl.size-1);SLPrint(sl);printf(%d\n,SLFind(sl, 1));SLDestory(sl);
}int main()
{//Test1();//Test2();Test3();return 0;
}接着我们需要注意把函数的实现放在SeqList.c文件里把结构体、函数声明、define、typedef等放在SeqList,h里。完成函数的封装。
