初阶数据结构【顺序表及其接口的实现】

1.线性表线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。2.顺序表的概念及结构顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为2.1. 静态顺序表使用定长数组存储元素#pragmaoncetypedefintSLDataType;//顺序表数据类型#defineN10//顺序表的大小structSeqList{SLDataType a[N];//定长数组intsize;//有效数据的个数};这就是静态顺序表我们可以看到其实也就是个套壳的数组没办法动态的改变空间所以这里的静态的意思就是固定大小。2.2. 动态顺序表使用动态开辟的数组存储。typedefintSLDataType;structSeqList{SLDataType*arr;intsize;intcapacity;};3.顺序表的接口实现静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。我们用C语言实现顺序表的以下接口//检查扩容函数voidSLCheckCapacity(SeqList*psl);//打印函数voidSeqListPrint(SeqList*psl);// 顺序表初始化voidSeqListInit(SeqList*psl);// 检查空间如果满了进行增容voidSLCheckCapacity(SeqList*psl);// 顺序表尾插voidSeqListPushBack(SeqList*psl,SLDataType x);// 顺序表尾删voidSeqListPopBack(SeqList*psl);// 顺序表头插voidSeqListPushFront(SeqList*psl,SLDataType x);// 顺序表头删voidSeqListPopFront(SeqList*psl);// 顺序表查找intSeqListFind(SeqList*psl,SLDataType x);// 顺序表在pos位置插入xvoidSeqListInsert(SeqList*psl,size_tpos,SLDataType x);// 顺序表删除pos位置的值voidSeqListErase(SeqList*psl,size_tpos);// 顺序表销毁voidSeqListDestory(SeqList*psl);// 顺序表打印voidSeqListPrint(SeqList*psl);//顺序表的排序voidSeqListSort(SeqList*psl);//二分查找intSeqBinarySearch(SeqList*psl,size_tleft,size_tright,SLDataType x);3.1. 顺序表基本功能接口3.1.1. 打印函数为了测试我们所写的接口是否正确我们需要写一个打印函数用来打印顺序表的元素voidSeqListPrint(SeqList*psl){assert(psl);for(inti0;ipsl-size;i){printf(%d ,psl-arr[i]);}printf(\n);}3.1.2. 初始化函数voidSeqListInit(SeqList*s){/*s.size 0; s.arr NULL; s.capacity 0;*/s-arr(SLDataType*)malloc(sizeof(SLDataType)*4);if(s-arrNULL){perror(malloc);exit(-1);//退出程序}s-size0;s-capacity4;}3.1.3. 顺序表销毁我们在创建顺序表的时候我们对顺序表进行malloc开辟空间既然我们开辟了空间在对空间使用结束后我们要将空间归还// 顺序表销毁voidSeqListDestory(SeqList*psl){if(psl!NULL){free(psl-arr);psl-arrNULL;psl-sizepsl-capacity0;}}3.2. 顺序表内存检查扩容接口3.2.1. 检查容量函数我们在执行顺序表的插入操作时可能会造成空间的容量不足这时候我们就要对空间进行扩容很明显我们既然使用malloc函数来初始化函数就可以用realloc函数进行空间的扩容一般我们对空间进行2倍的扩容。voidSLCheckCapacity(SeqList*psl){// 检查容量if(psl-sizepsl-capacity){// 开辟空间时注意当capacity初始化为 0 时直接相乘的结果还是 0 // 所以要先判断一下, 并且需要做 申请空间是否成功的判断// 还不能直接将申请的空间赋值给 目标数组先给一个 临时变量size_tnewCapcitypsl-capacity0?4:psl-capacity*2;SLDataType*tmp(SLDataType*)realloc(psl-arr,newCapcity*sizeof(SLDataType));if(tmpNULL){perror(realloc fail);return;//exit(-1);}psl-arrtmp;psl-capacitynewCapcity;}}3.3. 顺序表增加功能接口3.3.1. 顺序表的头插voidSeqListPushFront(SeqList*psl,SLDataType x){assert(psl);SLCheckCapacity(psl);intend(int)psl-size-1;while(end0){psl-arr[end1]psl-arr[end];end--;}psl-arr[0]x;psl-size;}3.3.2. 顺序表尾插我们在对顺序表进行尾部插入的时候我们在插入前要对顺序表进行容量检查即调用检查容量函数插入结束后顺序表的容量不变有效数据的个数加1voidSeqListPushBack(SeqList*psl,SLDataType x){assert(psl);//如果满了需要增容//一般我们增2倍SLCheckCapacity(psl);psl-arr[psl-size]x;psl-size;}3.3.3. 在顺序表pos位置前插入x首先我们要检查传入的指针 psl 是否为 NULL。如果 psl 是 NULL则程序会触发断言并终止执行。接着我们要检查插入位置 pos 是否有效。插入位置必须在当前顺序表的范围内即从 0 到 psl-size包括 psl-size如果需要在末尾插入插入前我们要先将pos及后面的元素向后移动给插入的位置腾出空间当然插入前我们要进行空间容量的检查。voidSeqListInsert(SeqList*psl,size_tpos,SLDataType x){assert(psl);assert(pospsl-size);SLCheckCapacity(psl);//插入前先检查一下满了没。//向后挪位置size_tendpsl-size;while(posend){psl-arr[end]psl-arr[end-1];end--;}psl-arr[pos]x;psl-size;}3.3.4. 在顺序表pos位置后插入x和在pos位置前插入同理我们只要在向后挪的操作少一次即可//在pos之后位置插入xvoidSeqListInsertBack(SeqList*ps1,size_t pos,SLDataType x){assert(ps1);assert(posps1-sizepos0);SLCheckCapacity(ps1);size_t endps1-size;for(end;endpos1;end--){ps1-arr[end]ps1-arr[end-1];}ps1-arr[pos1]x;ps1-size;}3.4. 顺序表删除功能接口3.4.1. 顺序表的头删我们直接从第二个元素向前移动覆盖第一个元素也就完成了头删操作最后不要忘记修改size的值voidSeqListPopFront(SeqList*psl){assert(psl);intstart0;while(startpsl-size){psl-arr[start]psl-arr[start1];start;}psl-size--;}3.4.2. 顺序表尾删voidSeqListPopBack(SeqList*psl){assert(psl);//psl-arr[psl-size - 1] 0; //可以不加没什么意义psl-size--;}3.4.3. 顺序表删除pos位置的值voidSeqListErase(SeqList*psl,size_tpos){assert(psl);assert(pospsl-size);size_tend--psl-size;while(posend){psl-arr[pos]psl-arr[pos1];end--;}}3.5. 顺序表查找接口3.5.1. 顺序表查找函数我们遍历顺序表如果找到x则返回这个顺序表的下标若没找到返回-1intSeqListFind(SeqList*psl,SLDataType x){assert(psl);for(inti0;ipsl-size;i){if(psl-arr[i]x){returni;//返回数组下标}}return-1;//没找到}3.6. 顺序表其他接口3.6.1. 顺序表的排序小到大我们利用冒泡排序法进行排序//顺序表的排序voidSeqListSort(SeqList*psl){if(psl-size2)return;bool swappedfalse;for(inti0;ipsl-size-1;i){for(intj0;jpsl-size-i-1;j){if(psl-arr[j]psl-arr[j1]){inttemppsl-arr[j];psl-arr[j]psl-arr[j1];psl-arr[j1]temp;swappedtrue;}}if(!swapped)break;}}3.6.2. 二分查找法intSeqBinarySearch(SeqList*psl,size_tleft,size_tright,SLDataType x){intmid0;intfind0;while(leftright){mid(int)(leftright)/2;if(psl-arr[mid]x){rightmid-1;}elseif(psl-arr[mid]x){leftmid1;}else{find1;break;}}if(1find){returnmid;}else{return-1;//没找到}}源代码已绑定了这篇文章需要者自取3.7. 测试函数我们可以在test.c文件进行测试:#define_CRT_SECURE_NO_WARNINGS#includeSeqList.hvoidTestSeqList1(){SeqList s;SeqListInit(s);//初始化SeqListPushBack(s,1);//尾插1SeqListPushBack(s,2);//尾插2SeqListPushBack(s,3);//尾插3SeqListPushBack(s,3);//尾插3SeqListPushBack(s,3);//尾插3SeqListPushBack(s,3);//尾插3SeqListPushBack(s,3);//尾插3SeqListPopBack(s);//尾删SeqListPopBack(s);//尾删SeqListPopBack(s);//尾删SeqListPopBack(s);//尾删SeqListPrint(s);//打印输出顺序表SeqListPushFront(s,6);//头插6SeqListPushFront(s,7);//头插7SeqListPushFront(s,8);//头插8SeqListPrint(s);//打印输出顺序表SeqListPopFront(s);//头删SeqListPopFront(s);//头删SeqListPopFront(s);//头删SeqListPrint(s);//打印输出顺序表printf(%d\n,SeqListFind(s,2));//找2在顺序表的位置SeqListInsert(s,1,6);//在下标为1的地方插入6SeqListPrint(s);//打印输出顺序表SeqListErase(s,2);//删除顺序表下标为2的位置SeqListPrint(s);//打印输出顺序表SeqListPushBack(s,10);//尾插10SeqListPushBack(s,4);//尾插4SeqListSort(s);//排序顺序表SeqListPrint(s);//打印输出顺序表printf(已找到数组下标是%d\n,SeqBinarySearch(s,0,s.size-1,10));//二分查找SeqListDestory(s);//销毁}intmain(){TestSeqList1();return0;}测试结果接口均正确