目录:
一:什么是顺序表
二:如何创建一个好的顺序表
(1)动态和静态版本顺序表比较。
三:顺序表的基本操作
(1)数据存入任意位置。
(2)任意位置数据的删除。
(3)顺序表中元素的修改
一:什么是顺序表
使用一段的物理地址连续的存储单元,依次存储数据元素的线性结构,一般的情况下用数组存储,在数组上完成 增 改 删 查等操作。(顺序表要求数据的存储必须是连续的)
二:如何创建一个好的顺序表!!!!
(1)静态版本的顺序表
静态版本的顺序表,创建起来会比较简单,直接创建一个该种类型的长数组即可。但是在使用起来,会比较呆板,不够灵活,当存储的数据较少时,会造成内存浪费,当需要存储的数据较多时,会出现存满的情况。
(2)动态版本的顺序表
动态版本的顺序表,可以根据需要存储数据的量,去自动的增加存储空间(动态内存开辟)。这样在使用时,会比较灵活。当需要存储的数据较少时,不会造成内存的浪费,随着需要存储的数据增加,会自动增加存储空间。
(3)typedef int SQdataty;
将int类型重命名为SQdataty ,当需要存储的数据类型是其他类型时,可以直接修改在这个重命名处进行修改,可以大大增加程序的可维护性。如果现在需要创建一个char类型的顺序表,那么我们直接替换这个定义就可以了。
每次存储一个数据,size都加一,当size==capacity时,使用realloc扩容就可以实现动态版本的顺序表了。
//判断是否需要扩容
void SQlist_capacityadd(SQ* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{//说明需要开辟空间了
SQdataty* ptr = (SQdataty*)realloc(ps->a, ps->capacity * 2 * sizeof(SQdataty));
if (ptr == NULL)
{//开辟空间失败
perror(realloc);
return;
}
else
{//开辟空间成功,将新开辟的空间交给ps->a维护
ps->a = ptr;
ps->capacity *= 2;
}
}
}
综上,我们创建出了一个好的动态版本的顺序表,并对其进行了初始化。
三:顺序表的基础操作
(1)顺序表中数据的存储
我们定义了一个向顺序表中增加数据的函数(可以添加到顺序表的任意位置)
但是要注意该位置不能大于size
当然我们在将数据存储到顺序表中的任意指定位置时,我们需要将该位置以后的数据向后移动一位。不然会将该位置的数据覆盖掉。(增加完成后ps->size需要++)
//将指定i位置的数据向后移动一位
void SQlistafter(SQ* ps, int i)
{
int m = ps->size;
if (i <= ps->size &&ps->size != 0)
{
for (m -= 1; m >= i; --m)
{
ps->a[m + 1] = ps->a[m];
}
}
else return;
}
//顺序表的增加 任意位置增加
void SQlistanyadd(SQ* ps,SQdataty tmp,int i)
{
if (i > ps->size)
{
printf("不能跳跃存储\n");
return;
}
else// i<=ps->size
{
SQlistafter(ps, i);
ps->a[i] = tmp;
ps->size++;
SQlist_capacityadd(ps);//判断是否需要扩容
}
}
(2)顺序表中任意位置数据的删除
和任意位置数据的添加一样,删除任意位置的一个数据,也需要将该位置后的数据向前移动一位。(因为顺序表需要连续存储)完成后ps->size需要--。
//顺序表的删除 任意位置
void SQlistanydelay(SQ* ps, int i)
{
if (i > ps->size)
{
return;
}
else
{
for (int min = i - 1; min < ps->size; ++min)
{
ps->a[min] = ps->a[min + 1];
}
ps->size--;
}
}
(3)顺序表中数据的查找
我们将顺序表的地址,与需要查找的元素作为参数,设计一个函数历遍该顺序表,如果查找到了该数据,便返回该元素的下标。找不到就返回 -1.
//顺序表中数据的查找
int SQlistcheck(SQ* ps, SQdataty tmp)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == tmp)
{
return i;
}
}
return -1;
}
//查找到的数据进行显示
void SQcheckPrin(SQ* ps, SQdataty tmp)
{
if (SQlistcheck(ps, tmp) == -1)
{
printf("表中没有这个元素\n");
}
else
printf("该元素在 %d号位置", SQlistcheck(ps, tmp)+1);
}
(4)顺序表中元素的修改
我们将顺序表的地址,与需要修改的元素,更改后的数据。作为参数,设计一个函数历遍该顺序表,如果查找到了该数据,就自动修改该数据。(这里还需要调用查找元素的函数)
//顺序表中数据的查找
int SQlistcheck(SQ* ps, SQdataty tmp)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == tmp)
{
return i;
}
}
return -1;
}
//顺序表中数据的修改
void SQlistchage(SQ* ps, SQdataty tmp, SQdataty tmp1)
{
int i = SQlistcheck(ps, tmp);
if (i == -1)
{
printf("没有该数据\n");
}
else
ps->a[i] = tmp1;
}
下面我们来测试一个整个程序各种功能
可以看到,测试的结果如预期一样。各种函数的功能也可以实现。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)