有哪些网站下载ppt是免费的,加盟合作招商,做网站用哪个电脑,郑州app开发公司哪家比较好个人主页#xff08;找往期文章包括但不限于本期文章中不懂的知识点#xff09;#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 目录
顺序表的概念及结构
顺序表的分类
顺序表的实现
在顺序表中增加数据
在顺序表中删除数据
在顺序表中查找数据
顺序表源码 顺序表的概念… 个人主页找往期文章包括但不限于本期文章中不懂的知识点我要学编程(ಥ_ಥ)-CSDN博客 目录
顺序表的概念及结构
顺序表的分类
顺序表的实现
在顺序表中增加数据
在顺序表中删除数据
在顺序表中查找数据
顺序表源码 顺序表的概念及结构
在了解顺序表之前得先知道一个东西线性表。线性表linear list是n个具有相同特性的数据元素的有限序列。简单理解就是线性表指的是具有部分相同特性的一类数据结构的集合。例如蔬菜分为绿叶类、瓜类、菌菇类。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 如何理解逻辑结构和物理结构我们去超市买东西的时候去付款时要排队假设有很多人也就意味着我们需要排成一条对去付款。这是在逻辑上就是一条线性的我们下意识认为是理想的但是实际上在站队时不一定是线性的现实情况。但是顺序表在逻辑结构和物理结构上都是线性的。这是因为顺序表的底层实现逻辑是数组。我们知道数组在内存上是连续存放的实际情况。
注意顺序表的底层虽然是数组但是却是在数组的基础之上对数组进行了封装实现了增删查改的一些功能。
顺序表的分类
我们知道数组有两种一种是定长数组也就是空间大小不可变化是固定的还有一种是变长数组这个变长数组是我们用动态内存开辟函数申请来的注意区分C99中引入的变长数组。
根据数组的不同顺序表也分为两种静态顺序表大小不可变动态顺序表大小可变。
顺序表的实现
这两种顺序表一比较肯定是第二种的优势明显一些同样在项目中动态顺序表的应用远远大于静态顺序表。下面我们就来学习动态顺序表的实现。
首先创建三个文件SeqList.h —— 顺序表的头文件 SeqList.c —— 顺序表的实现 test.c——测试顺序表
顺序表的创建
typedef struct SeqList
{SLDataType* arr;//数组指针int size;//记录当前有效的空间大小int capacity;//记录当前总空间大小
}SL;//由于struct SeqList太长比较麻烦因此就重新定义
由于数组的类型是暂定为int后续如果要改动的话不是很方便因此也是重定义。
typedef int SLDataType;//数组不一定是int类型
顺序表创建完了之后就得开始实现它的基本功能增 删 查 改。
在实现上面那些基本功能之前我们肯定得把这个顺序表进行初始化。
//初始化顺序表
void InitSeqList(SL* ps)//由于要改变顺序表所以传地址
{ps-arr NULL;//没为数组分配内存空间ps-capacity 0;ps-size 0;
}
在顺序表中增加数据
接下来就开始实现增加数据这个增加稍微有所不同是在指定的位置增加数据。
我们先来实现两种特殊的情况头插和尾插。头插是在顺序表的第一个位置数组下标为0的位置插入增加数据尾插是在顺序表的有效数据的末尾插入增加数据。
首先来实现头插数据从后往前覆盖 //在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断是否需要扩容if (ps-size ps-capacity)//数组满了{int newcapacity 0;if (ps-capacity 0){newcapacity BASE;//如果空间为0先给BASE(4)个空间}else{newcapacity 2 * ps-capacity;//扩容后为扩容前的两倍}//上面这个if...else语句也可以写成下面这样//int newcapacity (ps-capacity 0) ? 4 : 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-arr, newcapacity*sizeof(SLDataType));if (tmp NULL)//扩容失败{perror(realloc);exit(1);//直接退出程序不在执行异常退出//return 1; //这样写也是可以的}//扩容成功ps-arr tmp;ps-capacity newcapacity;}//头插数据for (int i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1];//size[1] size[0]; //根据边界来推上面的判断条件}ps-arr[0] x;ps-size;
}注意在比较大型的项目中我们写一些功能代码时一定要去检查功能是否完整。比如这里我们写这个头插功能的代码时写完之后一定要去打印结果看看是否满足我们的要求。
头插写完就开始写尾插了。 //在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//判断是否需要扩容if (ps-capacity ps-size)//数组满了{int newcapacity 0;if (ps-capacity 0)//还没分配空间{newcapacity BASE;}else{newcapacity 2 * ps-capacity;}SLDataType* tmp (SLDataType*)realloc(ps-arr, newcapacity*sizeof(SLDataType));if (tmp NULL){perror(realloc);exit(1);}ps-arr tmp;tmp NULL;ps-capacity newcapacity;}//尾插数据ps-arr[ps-size] x;//上面也可以转为下面的写法//ps-arr[ps-size] x;//ps-size;
}
通过观察上面两个代码我们会发现那个判断是否需要增容的部分是一样的因此我们就可以把这个判断是否需要增容的部分写成一个函数可以只判断也可以把增容的部分也写进去。
那么上面的代码就可以简化成下面的样子。
//判断是否需要增容如果需要则直接自动增容
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity)//数组满了{int newcapacity 0;if (ps-capacity 0){newcapacity BASE;//如果空间为0先给4个空间}else{newcapacity 2 * ps-capacity;//扩容后为扩容前的两倍}//上面这个if...else语句也可以写成下面这样//int newcapacity (ps-capacity 0) ? 4 : 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-arr, newcapacity*sizeof(SLDataType));if (tmp NULL)//扩容失败{perror(realloc);exit(1);//直接退出程序不在执行异常退出//return 1; //这样写也是可以的}//扩容成功ps-arr tmp;ps-capacity newcapacity;}
}//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断是否需要扩容SLCheckCapacity(ps);//头插数据for (int i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1];//size[1] size[0]; //根据边界来推上面的判断条件}ps-arr[0] x;ps-size;
}//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//尾插数据ps-arr[ps-size] x;//上面也可以转为下面的写法//ps-arr[ps-size] x;//ps-size;
}
两种特殊的插入写完之后就得开始写指定插入就是说在指定的位置插入数据。 和头插一样从后往前覆盖 //在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i pos; i--){ps-arr[i] ps-arr[i - 1];//arr[2] arr[1]; }ps-arr[pos] x;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 SLPopBack(SL* ps)
{assert(ps);assert(ps-size);//ps-arr[size-1] 0; //这一步可有可无ps-size--;
}接下来就是写在指定位置删除数据。 在顺序表中查找数据
最后我们就要实现在顺序表中查找数据。
找数据的话就是简单的循环找就行了。
//在顺序表中查找数据
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-arr[i] x){return i;//找到了返回x在顺序表中的下标}}return -1;//没找到
}
上面就是顺序表的全部逻辑以及实现。
顺序表源码
下面是顺序表的源码
SeqList.c
#include SeqList.h//初始化顺序表
void InitSeqList(SL* ps)
{ps-arr NULL;//没为数组分配内存空间ps-capacity 0;ps-size 0;
}//销毁顺序表
void SLDestroy(SL* ps)
{if (ps-arr)//有可能我们还没有使用为空{free(ps-arr);}ps-arr NULL;ps-size 0;ps-capacity 0;
}//打印顺序表
void SLPrint(const SL* ps)//只是打印不想被更改数据
{for (int i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);//可以选择换行不写也没关系
}//判断是否需要增容如果需要则直接自动增容
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity)//数组满了{int newcapacity 0;if (ps-capacity 0){newcapacity BASE;//如果空间为0先给4个空间}else{newcapacity 2 * ps-capacity;//扩容后为扩容前的两倍}//上面这个if...else语句也可以写成下面这样//int newcapacity (ps-capacity 0) ? 4 : 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-arr, newcapacity*sizeof(SLDataType));if (tmp NULL)//扩容失败{perror(realloc);exit(1);//直接退出程序不在执行异常退出//return 1; //这样写也是可以的}//扩容成功ps-arr tmp;ps-capacity newcapacity;}
}//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断是否需要扩容SLCheckCapacity(ps);//ps是一个指针没有因此也是一个值//头插数据for (int i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1];//size[1] size[0]; //根据边界来推上面的判断条件}ps-arr[0] x;ps-size;
}//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//尾插数据ps-arr[ps-size] x;//上面也可以转为下面的写法//ps-arr[ps-size] x;//ps-size;
}//在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i pos; i--){ps-arr[i] ps-arr[i - 1];//arr[2] arr[1]; }ps-arr[pos] x;ps-size;
}//删除顺序表头部的数据
void SLPopFront(SL* ps)
{for (int i 0; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}//删除顺序表尾部的数据
void SLPopBack(SL* ps)
{assert(ps);assert(ps-size);//ps-arr[size-1] 0; //这一步可有可无ps-size--;
}//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(ps-size);for (int i pos; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}//在顺序表中查找数据
int SLFind(SL* ps, SLDataType x)
{for (int i 0; i ps-size; i){if (ps-arr[i] x){return i;//找到了返回x在顺序表中的下标}}return -1;//没找到
}
SeqList.h
#include stdio.h
#include stdlib.h
#include assert.h#define BASE 4typedef int SLDataType;//数组不一定是int类型typedef struct SeqList
{SLDataType* arr;//数组指针int size;//记录当前有效的空间大小int capacity;//记录当前总空间大小
}SL;void InitSeqList(SL* ps);//初始化顺序表void SLDestroy(SL* ps);//销毁顺序表void SLPrint(const SL* ps);//打印顺序表的数据void SLPushFront(SL* ps, SLDataType x);//在顺序表的头部插入数据void SLPushBack(SL* ps, SLDataType x);//在顺序表的末尾插入数据void SLInsert(SL* ps, int pos, SLDataType x);//在指定位置插入数据void SLPopFront(SL* ps);//删除顺序表头部的数据void SLPopBack(SL* ps);//删除顺序表尾部的数据void SLErase(SL* ps, int pos);//删除指定位置的数据int SLFind(SL* ps, SLDataType x);//在顺序表中查找数据
好啦本期数据结构顺序表的学习就到此为止啦我们下一期再一起学习吧
