电商网站建设行业现状,网站建设吉金手指排名13,wordpress表单创建插件,绵阳科技网站建设前言:在之前我们学习了C语言的各种各样的语法#xff0c;因此我们今天开始学习数据结构这一个模块#xff0c;因此我们就从第一个部分来开始学习顺序表。 #x1f496; 博主CSDN主页:卫卫卫的个人主页 #x1f49e; #x1f449; 专栏分类:数据结构 #x1f…前言:在之前我们学习了C语言的各种各样的语法因此我们今天开始学习数据结构这一个模块因此我们就从第一个部分来开始学习顺序表。 博主CSDN主页:卫卫卫的个人主页 专栏分类:数据结构 代码仓库:卫卫周大胖的学习日记 关注博主和博主一起学习!一起努力 目录 顺序表动态顺序表顺序表的初始化顺序表的销毁顺序表的空间容量检查顺序表的打印顺序表的尾增顺序表的头增顺序表的头删顺序表的尾删顺序表的选择插入顺序表的删除数据顺序表数据的查找 练习 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为两个部分静态顺序表(使用定长数组存储元素)和动态顺序表(使用动态开辟的数组存储)。静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。 动态顺序表
首先我们创建一个结构体去实现数据的动态存储。
代码如下
typedef int SLDataype;//定义整型方便后面进行数据的更改typedef struct SeqList //动态顺序表的开辟
{SLDataype* a;int size; //记录多少个有效数据int capacity; //记录空间有多大
}SL; 接下来我们就实现一个个接口来实现顺序表的基本功能
顺序表的初始化
顺序表的初始化十分简单只需要将开辟的指针置为空指针有效数据清零空间容量清零即可。 代码如下
void SLInit(SL* ps1)//顺序表的初始化
{assert(ps1);ps1-a NULL;//将指针置为空指针ps1-size 0;//数据清零ps1-capacity 0;//容量清零
} 顺序表的销毁
同理顺序表的销毁只需要判断所开辟的空间是否已经是被释放了和被置为空指针了如果不是就把所开辟的空间释放和数据清零即可。 代码如下
void SLDestory(SL* ps1)//顺序表的销毁
{if (ps1-a ! NULL)//判断该指针是否为空指针{free(ps1-a);//释放该指针所开辟的空间ps1-a NULL;//置为空指针ps1-size 0;//数据清零ps1-capacity 0;//容量清0}
} 顺序表的空间容量检查
我们想要实现在所开辟的空间中增加数据就不可避免的需要去检查所开辟的空间的容量是否充足如果不充足我们就需要去增容那该增加多少呢增加太多会导致空间的浪费太少又会导致不断的扩容这是一个双向的问题因此这也没有什么十分固定的答案通常来讲一般增容一倍即可。 代码思路在检查空间的时候我们应该考虑传过来的指针是否是空指针即是否是初始化后的顺序表但realloc函数是可以对空指针进行扩容的但是我们为了防止扩容失败应该开辟一个新的结构体指针来接收这块空间在开辟成功后重新覆盖回去。 代码实现
void SLCheckCapacity(SL* ps1)//检查空间
{if (ps1-size ps1-capacity)//判断记录的数据个数与空间容量释放相同相同的时候即空间满了需要增容{int newCapacity ps1-capacity 0 ? 4 : ps1-capacity * 2;//判断开辟的空间是否是初始化的空间如果是就让他容量为4如果不是就开辟当前空间的两倍SLDataype* tmp (SLDataype*)realloc(ps1-a, sizeof(SLDataype) * newCapacity);//创建一个新的结构体指针在他的后面扩容放在开辟失败后原本的数据也不见了//realloc 可以对空指针进行扩容if (tmp NULL){perror(realloc fail);return;}ps1-a tmp;//将开辟后面的指针传给原本的地址ps1-capacity newCapacity;//更新容量}
}顺序表的打印
void SLPrint(SL* ps1)
{for (int i 0; i ps1-size; i)//变量开辟的数据{printf(%d , ps1-a[i]);//直接打印}printf(\n);
}顺序表的尾增
代码思路因为前面我们提到了size是有效数据的个数也是指向的数组的最后一个元素的后一个的位置因此只需要在此位置赋值即可然后再让size往后偏移一位。
代码实现
void SLPushBack(SL* ps1, SLDataype x)//尾增
{SLCheckCapacity(ps1);//检查空间容量ps1-a[ps1-size] x;//因size指向的是数组最后一个元素的后一个元素因此只需要直接在此位置赋值即可ps1-size;//size继续指向后一个元素
}
现在我们实现了四个小的接口忙活了这么久我们来见一下效果好歹听个响是吧。 效果图
void TestSL1()//测试函数
{SL s1;//创建动态顺序表SLInit(s1);//初始化顺序表SLPushBack(s1, 2);//尾增数据SLPushBack(s1, 3);SLPushBack(s1, 4);SLPrint(s1);//打印数据SLPushBack(s1, 5);SLPushBack(s1, 6);SLPrint(s1);//打印数据SLDestory(s1);//销毁顺序表
}int main()
{TestSL1();return 0;
} 顺序表的头增
代码实现思路我们记录数据的最后一个位置为end,最后一个数据后面的一个数据位置为end1,让end依次往后覆盖然后end–直到end到起始位置即停止循环具体思路如下图: 代码实现
void SLPushFront(SL* ps1, SLDataype x)//头增
{SLCheckCapacity(ps1);//先检查数据//挪动数据int end ps1-size - 1;//记录最后一个位置while (end 0)//end到起始位置时即覆盖完成{ps1-a[end 1] ps1-a[end];//将数据依次往后覆盖--end;}ps1-a[0] x;//将数据赋值给起始位置就可以实现头增ps1-size;//size
}当然了不能白忙活我们来测试一下这个函数来看看效果如何
void TestSL2()
{SL s1;//创建动态顺序表SLInit(s1);//初始化顺序表SLPushBack(s1, 2);//尾增数据SLPushBack(s1, 3);SLPushBack(s1, 4);SLPrint(s1);//打印尾增的数据printf(上面是尾增的数据\n);printf(------------------------------\n);printf(下面是头增的数据\n);SLPushFront(s1, 20);//头增的数据SLPushFront(s1, 10);SLPushFront(s1, 0);SLPushFront(s1,9);SLPrint(s1);//打印头增的数据SLDestory(s1);//销毁顺序表
}int main()
{//TestSL1();TestSL2();return 0;
} 顺序表的头删
代码思路我们记录一个起始位置即数组的第二个元素记录为begin让他往前面一个数据begin-1覆盖然后再放入循环中不断覆盖当运行到size的位置的时候停止循环具体思路如下图: 代码如下
void SLPopFront(SL* ps1)//头删
{assert(ps1-size 0);//判断传过来是是不是为空数据int begin 1;//将起始位置置为1while (begin ps1-size)//再起始位置等于size时即覆盖完成{ps1-a[begin - 1] ps1-a[begin];//后面覆盖前面begin;}ps1-size--;//size减减
}当然我们依然来听个响听听声音效果图如下 void TestSL3()
{SL s1;//创建动态顺序表SLInit(s1);//初始化顺序表SLPushBack(s1, 2);//尾增数据SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushFront(s1, 20);//头增的数据SLPushFront(s1, 10);SLPushFront(s1, 0);SLPushFront(s1, 9);SLPrint(s1);//打印原本的数据printf(上面是原本的数据\n);printf(--------------------------------------\n);printf(下面是删除后的数据\n);SLPopFront(s1);//头删数据SLPopFront(s1);SLPopFront(s1);SLPrint(s1);//打印删除后的数据SLDestory(s1);//销毁顺序表
}int main()
{//TestSL1();//TestSL2();TestSL3();return 0;
}顺序表的尾删
代码思路我们可以通过前面的打印函数可以知道我们是通过打印到size前面的一个下标来访问所有的元素因此我们只需要让size往前面走一个就可以把尾部的元素删除可以看下图思路
代码实现:
void SLPopBack(SL* ps1)//尾删
{//空if (ps1-size 0)//判断删除的是否为空{return;}ps1-size--;//size--即可
}
我们依然来测试一下我们函数看看效果是否成功实现代码和效果图如下
void TestSL4()
{SL s1;//创建动态顺序表SLInit(s1);//初始化顺序表SLPushBack(s1, 2);//尾增数据SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushFront(s1, 20);//头增的数据SLPushFront(s1, 10);SLPushFront(s1, 0);SLPushFront(s1, 9);SLPrint(s1);//打印原本的数据printf(上面是原本的数据\n);printf(--------------------------------------\n);printf(下面是删除后的数据\n);SLPopBack(s1);//尾删数据SLPopBack(s1);SLPrint(s1);//打印删除后的数据SLDestory(s1);//销毁顺序表
}int main()
{//TestSL1();//TestSL2();//TestSL3();TestSL4();return 0;
}顺序表的选择插入
代码思路选择插入即将一个值任意插入到顺序表中的范围内当然了口头总是不太好说清我们对着下图来进行一一分析我们可以记录一个end坐标记录数据的尾部然后将值一一覆盖pos为我们想要出入数据的位置例如下图当end走到pos的位置的时候即可停止覆盖这有点类似与我们前面的头删将值pos之后的值全部往后挪动了一位然后将最后重复的值被想插入的值覆盖即可。
代码实现
void SLInsert(SL* ps1, int pos, SLDataype x)//插入数据
//pos是下标size是数据个数看作下标的话他是最后一个数的下一个位置
{assert(ps1);//判断传来的值是否是空指针assert(pos 0 pos ps1-size);//插入的值必须是再范围内可以包括尾增SLCheckCapacity(ps1);//检查空间// 挪动数据int end ps1-size - 1;//找到尾坐标while (end pos){ps1-a[end 1] ps1-a[end];//将值一一覆盖类似于头删--end;}ps1-a[pos] x;//赋值ps1-size;
}我们依然来看看函数的效果是否实现测试代码和效果图如下
void TestSL5()
{SL s1;//创建动态顺序表SLInit(s1);//初始化顺序表SLPushBack(s1, 2);//尾增数据SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushFront(s1, 20);//头增的数据SLPushFront(s1, 10);SLPushFront(s1, 0);SLPushFront(s1, 9);SLPrint(s1);//打印原本的数据printf(上面是原本的数据\n);printf(--------------------------------------\n);printf(下面是选择插入后的数据\n);SLInsert(s1, 3, 99);SLInsert(s1, 1, 2);SLPrint(s1);//打印选择插入后的数据SLDestory(s1);//销毁顺序表
}
int main()
{//TestSL1();//TestSL2();//TestSL3();//TestSL4();TestSL5();return 0;
} 顺序表的删除数据
代码思路删除数据和选择插入的概念其实大差不差首先也应当判断传过来的数是否是空指针删除的数据在不在数据范围内然后我们再通过图文来进行分析如下图先把删除的位置记录下来当然了和前面同理依次往前面覆盖再打印的时候直接将size往前移一位即可把最后重复的值给去掉达到顺序表的删除的功能。 函数代码
void SLErase(SL* ps1, int pos)//删除数据
{assert(ps1);assert(pos 0 pos ps1-size);int begin pos 1;//记录删除数据后的位置while (begin ps1-size){ps1-a[begin - 1] ps1-a[begin];//依次覆盖begin;}ps1-size--;
}代码实现和函数实现效果图如下
void TestSL6()
{SL s1;//创建动态顺序表SLInit(s1);//初始化顺序表SLPushBack(s1, 2);//尾增数据SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushFront(s1, 20);//头增的数据SLPushFront(s1, 10);SLPushFront(s1, 0);SLPushFront(s1, 9);SLPrint(s1);//打印原本的数据printf(上面是原本的数据\n);printf(--------------------------------------\n);printf(下面是选择插入后的数据\n);SLErase(s1, 3);//删除数据SLErase(s1, 1);//删除数据SLPrint(s1);//打印选择插入后的数据SLDestory(s1);//销毁顺序表}int main()
{//TestSL1();//TestSL2();//TestSL3();//TestSL4();//TestSL5();TestSL6();return 0;
}顺序表数据的查找
代码思路顺序表数据的查找就过于简单了我们只需要遍历数据看看是否有对应的值有则返回该数的下标没有则返回**-1**。代码如下
int SLFind(SL* ps1, SLDataype x)//顺序表数据的查找
{assert(ps1);//判断传来的数据是否是空指针for (int i 0; i ps1-size; i)//遍历数组{if (ps1-a[i] x)return i;//找到即返回坐标i}return -1;//没找到返回-1
}函数测试与效果图
void TestSL7()
{SL s1;//创建动态顺序表SLInit(s1);//初始化顺序表SLPushBack(s1, 2);//尾增数据SLPushBack(s1, 3);SLPushBack(s1, 4);SLPushFront(s1, 20);//头增的数据SLPushFront(s1, 10);SLPushFront(s1, 0);SLPushFront(s1, 9);SLPrint(s1);//打印原本的数据printf(上面是原本的数据\n);printf(--------------------------------------\n);printf(下面是选择插入后的数据\n);printf(该数的下标是:%d\n,SLFind(s1, 2));SLDestory(s1);//销毁顺序表
}
int main()
{//TestSL1();//TestSL2();//TestSL3();//TestSL4();//TestSL5();//TestSL6();TestSL7();return 0;
} 讲到这里关于顺序表的基本内容实现全部讲完了接下来我们来看一题目练习一下把 练习
题目链接
思路分析看到这个题大家都会想到一个很通俗易懂的方法就是开辟一个辅助数组将所有的数放进去然后进去排序当然我们今天是不讲这个方法的因为这个方法的时间复杂度过于高。我们看到这个是一个非递减顺序可以知道最大的数都放在了后面因此我们可以将两个数中最后的元素拿出来依次比较然后将较大的放在nums1中的最后面依次类推放到最后自然而然的可以将所有数进行排序那怎么去实现它呢看图说话如下图我们记录一个坐标i1和i2分别记录下两个数组中的最后一个元素然后依次进行比较如果i1中的数较大就放在下标j的位置反之则把i2放进去且如果nums1中走完了nums2还没有就只需要将nums2中的数据单独拿出来放再j所在的位置即可。 代码实现如下
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int i1 m - 1;//记录第一个数组的尾坐标int i2 n - 1;//第二个数组尾坐标int j m n - 1;//记录总元素的坐标while(i1 0 i2 0){if(nums1[i1] nums2[i2]){nums1[j--] nums1[i1--]; }else{nums1[j--] nums2[i2--];}}while(i2 0){nums1[j--] nums2[i2--];}
}运行结果 结语今天的内容就到这里吧谢谢各位的观看如果有讲的不好的地方也请各位多多指出作者每一条评论都会读的谢谢各位。 祝各位接下来好运连连
