河南网站排名优化哪家好,企业网站 留言板,济宁做网站大约多少钱,网站建设要注意哪些文章目录 一、线性表二、顺序表1. 概念与分类2. 准备工作3. 静态顺序表4. 动态顺序表4.1 定义顺序表结构4.2 顺序表的初始化4.3 检查空间是否足够4.3 尾部插入数据4.4 头部插入数据4.5 尾部删除数据4.6 头部删除数据4.7 在指定位置插入数据4.8 在指定位置删除数据4.9 顺序表的销… 文章目录 一、线性表二、顺序表1. 概念与分类2. 准备工作3. 静态顺序表4. 动态顺序表4.1 定义顺序表结构4.2 顺序表的初始化4.3 检查空间是否足够4.3 尾部插入数据4.4 头部插入数据4.5 尾部删除数据4.6 头部删除数据4.7 在指定位置插入数据4.8 在指定位置删除数据4.9 顺序表的销毁 一、线性表
线性表是若干个具有相同特性的数据元素的有限序列是一种在实际中广泛使用的数据结构常见的线性表有顺序表、链表、栈、队列、字符串等等。线性表在逻辑上是线性结构的但在物理层面上地址不一定是线性结构的。 线性表逻辑上连续地址不一定连续
本篇文章先来了解顺序表。
二、顺序表
1. 概念与分类
顺序表的概念顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构一般情况下采用数组存储。 顺序表和数组的区别在于顺序表的底层结构是数组它是对数组的封装实现了常用的增删查改等功能是一个结构体类型。
一般情况下顺序表可以分为静态顺序表、动态顺序表
2. 准备工作
顺序表的英文是SeqList一在实际写代码过程中我们常常typedef重命名为SL方便书写。由于顺序表存储的数据类型有很多种可能在一个项目实战中面对成百上千行代码一旦要修改顺序表存放数据类型一个个修改会很麻烦。所以我们可以一开始就定义typedef 类型 SLDataType;然后创建顺序表的数组或是其他要写到顺序表元素类型的地方直接写成SLDataType。这样需要改变数据类型时直接改typedef那里就可。通常我们把结构体的定义、函数的声明放在SeqList.h 头文件中。把顺序表的功能实现方法代码放在SeqList.c 源文件中每一个功能都封装成一个函数。测试顺序表功能则在test.c 中完成。它们都要包含SeqList.h头文件
这些道理不仅适用于本文未来学习其他内容也是一样的以后就不再提醒了。
3. 静态顺序表
静态顺序表就是固定大小的顺序表使用定长数组存储元素
typedef struct SeqList
{SLDataType arr[7]; //定长数组int size; //有效元素个数
}SL;其实它和数组也没有太大区别了只是对数组进行了简单封装 静态顺序表的大小无法再改变因此面对空间给大了或空间给小了的情况时无能为力。所以在实际项目中我们很少用到它动态顺序表才是更重要的。 4. 动态顺序表
动态顺序表的特点是空间按需申请。按需申请说明数组的内存大小要靠动态内存分配实现。下面我们就来演示一下常见的动态顺序表的操作
4.1 定义顺序表结构
typedef struct SeqList
{SLDataType* arr;//数组首元素地址int size; //有效数据个数int capacity; //空间大小
}SL;4.2 顺序表的初始化
//不能进行传值调用否则修改的只是形参因此要传址调用
void SLInit(SL* psl)
{psl-arr NULL;psl-size psl-capacity 0;
}测试
4.3 检查空间是否足够
在插入顺序表元素前我们要确保表的空间足够当size capacity说明空间已满需要扩容。而假如capacity还为0则先自己给定一个大小不为0一般呈二倍扩容这是由概率论总结出来的最适合的扩容大小。每个插入数据操作都应该包括这一步。
void SLCheckCapacity(SL* psl)
{if(psl-size psl-capacity){int newCapacity (psl-capacity0)? 5: 2*psl-capacity;SLDataType* tmp (SLDataType*)realloc(psl-arr, newCapacity*sizeof(SLDataType));if(tmp NULL){perror(realloc fail!);return 1;}psl-arr tmp;psl-capacity newCapacity;}
}测试
4.3 尾部插入数据
我们实现的插入数据函数是单个数据的插入。插入一个新数据意味着表的有效数据个数size也要。这个功能是在顺序表的尾部插入一个数据尾插函数应该有两个参数被插入的表和被插入的数据
void SLPushBack(SL* psl, SLDataType x)
{assert(psl); //确保psl不为空SLCheckCapacity(psl);psl-arr[psl-size] x;psl-size;
}测试
4.4 头部插入数据
这个功能是在顺序表的头部插入一个数据参数也是要有两个
void SLPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheckCapacity(psl);for(int i psl-size; i0; i--){psl-arr[i] psl-arr[i-1];}psl-arr[0] x;psl-size;
}测试
4.5 尾部删除数据
这个功能是删除顺序表尾部的一个数据但实际上并不是“删除”而是修改size让这个数据在size的范围之外。这样我们用size的值访问arr时就访问不到这个数据了。
void SLPopBack(SL* psl)
{assert(psl psl-size);//psl不能为空size不能为0否则没有意义psl-size--;
}测试 4.6 头部删除数据
头删就是真的删除头部一个数据了会被第二个数据覆盖掉。
void SLPopFront(SL* psl)
{assert(psl psl-size);for(int i 0; i psl-size-1; i){psl-arr[i] psl-arr[i1];}psl-size--;
}测试
4.7 在指定位置插入数据
这个功能有三个参数一个是顺序表一个是指定的位置一个是要插入的数据。pos及之后的数据要整体向后挪动一位。
void SLInsert(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos0 pospsl-size);//确保pos有意义SLCheckCapacity(psl);for(int i psl-size; ipos; i--){psl-arr[i] psl-arr[i-1];}psl-arr[pos] x;psl-size;
}测试
4.8 在指定位置删除数据
同样地pos之后的数据要整体向前挪动一位
void SLErase(SL* psl, int pos)
{assert(psl);assert(pos0 pospsl-size);SLCheckCapacity(psl);for(int ipos; ipsl-size-1; i){psl-arr[i] psl-arr[i1];}psl-size--;
}测试
4.9 顺序表的销毁
void SLDestory(SL* psl)
{if(psl-arr ! NULL){free(psl-arr);}psl-arr NULL;psl-size psl-capacity 0;
}测试 以上就是顺序表的部分用法了但远不止这些大家可以设计出更多功能的。
本篇完感谢阅读。
