中山火炬开发区建设局网站,牡丹江做网站,四川招标投标网,医院网站icp备案吗目录
一、顺序表的概念
二、顺序表的分类
1.静态顺序表
2.动态顺序表
3.顺序表的增删改查
总结 一、顺序表的概念
顺序表是一段物理地址连续的村塾单元依次存储数据元素的线性结构#xff0c;一般情况下使用数组存储#xff0c;在数组上完成数据的增删改查。
二、顺…目录
一、顺序表的概念
二、顺序表的分类
1.静态顺序表
2.动态顺序表
3.顺序表的增删改查
总结 一、顺序表的概念
顺序表是一段物理地址连续的村塾单元依次存储数据元素的线性结构一般情况下使用数组存储在数组上完成数据的增删改查。
二、顺序表的分类
1.静态顺序表
使用定长数组存储元素
#define N 7typedef int SLDataType;typedef struct SeqList{SLDataType array[N]; //定长数组size_t size ; //有效数据的个数
}SeqList;
静态顺序表只适用于确定需要多少数据的情况N大了空间浪费N小了不够用所以一般用动态顺序表按需分配空间。
2.动态顺序表
使用动态开辟的数组存储
//顺序表的动态存储
typedef struct SeqList
{SLDataType * array; //指向动态开辟的数组size_t size; //有效的数据个数sieze_t capacity; //容量空间的大小
}SeqList;
3.顺序表的增删改查
顺序表的初始化顺序表为一个结构体里面有3个参数指向数组的指针顺序表中的有效数字个数顺序表的大小初始化的时候全部置空
//顺序表的初始化
void SLInit(SL * ps)
{assert(ps);ps-a NULL;ps-size 0;ps-capacity 0;
}
尾插首先在尾部插入数据先判断顺序表中的大小是否能插入如果不能需要扩容如果可以插入则要找到尾的位置然后把数据放入放入的时候根据size找下标放入a中。ps-a[ps-size];此时size
void SLCheckCapacity(SL * ps)
{assert(ps);//如果容量满了if(ps-size ps-capacity){//如果是第一次开辟空间 给4个字节 // 后面开辟扩容到二倍int newCapacity ps-capacity 0 ?4: ps-capacity * 2;//扩容的地址 realloc 形参为第一次开辟的地址和要扩容的大小 //要扩容的单位 字节 字节个数扩容几个 * 类型SLDataType * tmp (SLDataType * ) realloc(ps-a, newCapcity * sizeof(SLDataType));//如果开失败if(tmp NULL){perror(realloc fail);exit(-1);}//开成功 地址给a realloc可能为原地也可能为异地 相当于一次原地扩容ps-a tmp;// 容量大小改变ps-capacity newCapacity;
}void SLPushBack(SL * ps,SLDataType x)
{assert(ps);//检查容量SLCheckCapacity(ps);ps-a[ps-size] x; //x要放入a数组中根据现在的数据个数(即数组的最后一个)找下标赋值插入ps-size;
}
尾删先判断顺序表是否删空了如果空了返回。如果不空a数组中的尾部位置数置0size--.
void SLPopBack(SL * ps)
{assert(ps);assert(ps-size 0);ps-a[ps-size-1] 0; //注意下标的位置size是有效数据个数size-1是最后一个数的位置ps-size--;
}
头插插入之前需要先判断能否插入使用checkCapacity检查如果可以插入头插需要把后面的数字往后挪往后挪有两种方式从前往后从后往前此时需要从后往前否则会覆盖掉后一个数字挪动结束后第一个位置插入插入之后size
//头插
void SLPushFront(SL * ps,SLDataType)
{assert(ps);SLCheckCapacity(ps);//挪动数据int end ps-size-1;while(end0){ps-a[end1] ps-a[end];end--;}ps-a[0] x;ps-size;
}
头删先判断是否为空的顺序表然后删除第一个后面的数据往前挪动挪动的时候从前往后挪不会覆盖删除结束之后size--
//头删
void SLPopFront(SL * ps)
{assert(ps-size 0)int begin 1; //注意这里begin设置为1 while(beginps-size){ps-a[begin-1] ps-a[begin]; //覆盖前一个begin;}ps-size--;
}
查找遍历顺序表 根据数据查找位置找到了就返回数据的下标
int Find(SL * ps, SLDataType x)
{assert(ps);for(int i 0;ips-size;i){if(ps-a[size] x){return i;}}//没找到return -1;
}
在pos位置插入x先判断pos位置的合法性是否在这个顺序表的范围里然后判断是否能插入如果不可以需要扩容如果可以插入pos位置之后的先往后挪动endpos,然后pos位置插入数据
void SLInsert(SL * ps,SLDataType x)
{assert(ps);//判断pos的合法性 在这个顺序表中assert(pos0);assert(posps-size);//判断是否要扩容SLCheckCapacity(ps);int end ps-size - 1;//pos位置之后的挪动 往后挪while(endpos){ps-a[end1] ps-a[end];end--;}ps-a[pos] x;ps-size;
}
在pos位置删除x
先判断pos的合法性判断顺序表是否为空如果可以删除pos位置之后的往前挪动size--
void SLErase(SL * ps,int pos)
{assert(ps);assert(pos0);assert(posps-size);assert(ps-size 0);//挪动数据覆盖int begin pos1;while(beginps-size){ps-a[begin-1] ps-a[begin];begin;}ps-size--;
顺序表的打印遍历打印即可打印数组中的内容
void SLPrint(SL * ps)
{assert(ps;for(int i 0;ips-size;i){printf(%d,ps-a[i];);}
}
顺序表的销毁将顺序表中的数组内容置空size和capacity均置空
void SLDestroy(SL * ps)
{assert(ps);if(ps-a){free(ps-a);ps-a NULL;ps-size ps-capacity 0;}} 总结
本文主要介绍了顺序表的结构以及对顺序表的操作增删改查等。如有错误请指正。
