官网的网站建设,ai制作网页,莱芜可信赖的网站建设,湖北勘察设计协会网站✨✨小新课堂开课了#xff0c;欢迎欢迎~✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;http://t.csdnimg.cn/oHJAK#xff08;数据结构与算法#xff09; 小新的主页#xff1a;编程版小新-CSDN博客 … ✨✨小新课堂开课了欢迎欢迎~✨✨ 养成好习惯先赞后看哦~ 所属专栏http://t.csdnimg.cn/oHJAK数据结构与算法 小新的主页编程版小新-CSDN博客 1.什么是顺序表
顺序表的底层是数组但它提供了很多现成的方法开箱即用就成了顺序表。简单来理解顺序表其实就是数组的升级版。顺序在物理结构上不一定连续但在逻辑结构上是连续的可以抽象成一个直线 。
2.顺序表的分类
顺序表可以分为静态顺序表和动态顺序表。
2.1顺序表的定义
静态顺序表 #define N 100struct SeqList
{int arr[N];int size;//有效数据个数
};
动态顺序表
typedef int SLDataType;//为了方便更改类型
typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间大小
}SL;
静态顺序表的数组是定长的给小了不够用给大了浪费空间而动态顺序表是可以动态增容的相对于静态顺序表更加的灵活和节省空间所以也更推荐使用动态顺序表。
3.顺序表的功能 1.顺序表的初始化 2.对顺序表进行尾插在末尾处插入数据 3.对顺序表进行尾删删除末尾处的数据 4.对顺序表进行头插在开始位置插入数据 5.对顺序表进行头删删除在起始位置的数据 6.在指定位置之前插入数据 7.删除指定位置的数据 8.打印顺序表 9.查找顺序表 10.修改顺序表 11.销毁顺序表 4.顺序表功能的实现
4.1顺序表的初始化
//顺序表的初始化
void SLInit(SL* ps)//传址调用
{ps-arr NULL;ps-size ps-capacity 0;
}
易错点这里一定要采用传址调用因为采用传值调用的话形参只是对实参的一份临时拷贝出了{}以后就被销毁了。
4.2顺序表的尾插
在说明顺序表的尾插之前我们要先想一个问题我们既然要插入数据就要考虑空间够不够的问题所以数据在进行插入之前要检查空间够不够。
//检查是否用足够的空间
void SLCheck(SL* ps)
{if (ps-size ps-capacity)//空间不够{//申请空间//三目操作符int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacitySLDataType* tmp (SLDataType*)realloc(ps-arr, newcapacity * sizeof(SLDataType));//需要申请多大的空间if (tmp NULL){perror(realloc fail);return;}//申请成功ps-arr tmp;ps-capacity newcapacity;}}
动态增容的时候一般是成倍的扩增采用2倍扩增是比较合适的。
这里大家可能会有疑问这样开辟空间不会浪费空间吗
答案是会的但是这样浪费的空间相对于静态开辟的空间好一些。
在开辟空间的时候为什么要*sizeof(类型)因为单位是字节要*sizeof(类型)才能得出真正所需要的空间大小。
判断了空间够不够之后我们看一看如何进行尾插吧。
//顺序表的尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//插入之前要检查是否有空间SLCheck(ps);//插入ps-arr[ps-size] x;//细节之后置
}
后置在这里使用的是真的很不错。 4.3顺序表的尾删
//顺序表的尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps-size);//顺序表不能为空--ps-size;
}
4.4顺序表的头插
//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//插入之前要检查是否有足够的空间SLCheck(ps);//先让顺序表中已有的数据整体往后移动一位for (int i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1];}ps-arr[0] x;ps-size;//不要忘记
}
这里之所以是从后往前移动是为了避免数据被覆盖。
4.5 顺序表的头删
//顺序表的头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size);//整体往前挪动一位for (int i 0; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}
4.6在指定位置之前插入数据 //在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);//插入之前要检查空间够不够SLCheck(ps);//先让pos及其之后的数据整体往后挪动一位for (int i ps-size; i pos; i--){ps-arr[i] ps-arr[i - 1];//如果不知道结束条件是什么就可以用最后一次挪动去推//ps-arr[pos1]ps-arr[pos]}ps-arr[pos] x;ps-size;
}
4.7在指定位置删除数据
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);//让pos之后的数据整体往前挪动一位for (int i pos; i ps-size-1; i){ps-arr[i] ps-arr[i 1];}ps-size--;}
4.8打印顺序表
void SLPrint(SL ps)
{for (int i 0; i ps.size; i){printf(%d , ps.arr[i]);}printf(\n);
}
4.9查找顺序表
//查找指定数据
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-arr[i] x){//找到了return i;//返回下标}}//没有找到return -1;}
4.10修改顺序表
//修改指定位置的数据
void SeqListModify(SL* ps, int pos, SLDataType x)
{assert(ps); //断言assert(ps-size 0); //顺序表不能为空assert(pos 0 pos ps-size); //检查pos下标的合法性ps-arr[pos] x; //修改pos下标处对应的数据
}4.11销毁顺序表
//顺序表的销毁
void SLDestroy(SL* ps)
{if (ps-arr ! NULL)//ps-arr{free(ps-arr);}ps-arr NULL;//避免访问野指针ps-size ps-capacity 0;
}
5.完整代码
5.1SeqList.c
#includeSeqList.h
//顺序表的初始化
void SLInit(SL* ps)//传址调用
{ps-arr NULL;ps-size ps-capacity 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{if (ps-arr ! NULL)//ps-arr{free(ps-arr);}ps-arr NULL;//避免访问野指针ps-size ps-capacity 0;
}//检查是否用足够的空间
void SLCheck(SL* ps)
{if (ps-size ps-capacity)//空间不够{//申请空间//三目操作符int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;//少了等号。一个是赋值SLDataType* tmp (SLDataType*)realloc(ps-arr, newcapacity * sizeof(SLDataType));//需要申请多大的空间if (tmp NULL){perror(realloc fail);return;}//申请成功ps-arr tmp;ps-capacity newcapacity;}}//打印顺序表
void SLPrint(SL ps)
{for (int i 0; i ps.size; i){printf(%d , ps.arr[i]);}printf(\n);
}//顺序表的尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//插入之前要检查是否有空间SLCheck(ps);//插入ps-arr[ps-size] x;//细节之后置
}//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//插入之前要检查是否有足够的空间SLCheck(ps);//先让顺序表中已有的数据整体往后移动一位for (int i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1];}ps-arr[0] x;ps-size;//不要忘记
}//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);//插入之前要检查空间够不够SLCheck(ps);//先让pos及其之后的数据整体往后挪动一位for (int i ps-size; i pos; i--){ps-arr[i] ps-arr[i - 1];//ps-arr[pos1]ps-arr[pos]}ps-arr[pos] x;ps-size;
}//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);//让pos之后的数据整体往前挪动一位for (int i pos; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;}
//顺序表的尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps-size);//顺序表不能为空--ps-size;
}//顺序表的头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size);//整体往前挪动一位for (int i 0; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}//修改指定位置的数据
void SeqListModify(SL* ps, int pos, SLDataType x)
{assert(ps); //断言assert(ps-size 0); //顺序表不能为空assert(pos 0 pos ps-size); //检查pos下标的合法性ps-arr[pos] x; //修改pos下标处对应的数据
}//查找指定数据
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-arr[i] x){//找到了return i;//返回下标}}//没有找到return -1;}
5.2SeqList.h
#includestdio.h
#includestdlib.h
#includeassert.h
//定义顺序表//静态顺序表
//#define N 100
//
//struct SeqList
//{
// int arr[N];
// int size;//有效数据个数
//};//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;//有效数据个数int capacity;//空间大小
}SL;//顺序表的初始化
void SLInit(SL* ps);//顺序表的销毁
void SLDestroy(SL* ps);//尾部插入
void SLPushBack(SL* ps, SLDataType x);//尾部删除
void SLPopBack(SL* ps);//头部插入
void SLPushFront(SL* ps, SLDataType x);//头部删除
void SLPopFront(SL* ps);//指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x);//指定位置删除
void SLErase(SL* ps, int pos);//打印顺序表
void SLPrint(SL ps);//查找数据
int SLFind(SL* ps, SLDataType x);//修改指定位置的数据
void SeqListModify(SL* ps, int pos, SLDataType x);下课了~
别忘了下次再来哦
