域名备案查询网站,wordpress子主题安装,wordpress页面与文章,家具网站开发环境与工具1、顺序表的概念及结构
1.1 线性表 线性表#xff08; linear list #xff09;是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构#…1、顺序表的概念及结构
1.1 线性表 线性表 linear list 是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 案例蔬菜分为绿叶类、⽠类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合 2、顺序表分类 2.1顺序表和数组的区别 顺序表的底层结构是数组对数组的封装实现了常用的增删改查等接⼝ 2.2顺序表分类
1.静态顺序表:
概念使用定长数组存储元素
代码示例
typrdef int SLDataType;
#define N 8
typedef struct SeqList
{SLDataType a[N];//定长数组int size; //有效数据个数
}SL;这就是一个静态顺序表它又一定的缺陷。 容易出现空间给少了不够用给多了造成空间浪费 2.动态顺序表
它的特点是按需申请 3.动态顺序表的实现
我们首先创建相应的头文件和程序文件 我们现在头文件中引用头文件定义所需要的结构体和函数
#includestdio.h
#includeassert.h
#includestdlib.h
typedef int SLDataType;typedef struct SeqList
{SLDataType* arr; //存储数据的底层结构int capacity; //记录顺序表的空间大小int size; //记录顺序表当前有效的数据个数
}SL;
//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);
//顺序表的头部 / 尾部插入
void SLPushFront(SL* ps, SLDataType x);
void SLPushBack(SL* ps, SLDataType x);
//顺序表的头部 / 尾部删除
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);//打印
void SLPrint(SL* ps);
//删除指定位置的值
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
我们先定义一个动态顺序表
注意这行代码是为了设定我们的数据类型
1.初始化
接下来我们要初始化我们的顺序表。所以我们定义了这个函数 接着我们去源文件写完这个函数让指针指向NULL大小设定为0完成初始化
void SLInit(SL* ps)
{ps-arr NULL;ps-size ps-capacity 0;
}
写完了初始化我们可以开始写功能
首先就是头插和尾插 我们接着完善 2.头插
我们先来写头插函数 void SLPushFront(SL* ps, SLDataType x) 首先我们来思考以下问题一个数组如何头插以及目前的内存大小能否插入新的数据
假设足够 数组头插我们一般将数组的各个元素后移一位然后将数组arr[0]赋值成我们要插入的数据
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);
for (int i ps-size; i 0; i--) //i 1{ps-arr[i] ps-arr[i - 1]; //ps-arr[1] ps-arr[0]}ps-arr[0] x;ps-size;
}我们不难写出这个函数但是它对吗
显然存在一定的问题我们前面的条件是设置在空间充足的情况下如果空间不足的话我们该怎么办呢
当然是扩容啦
所以我们再写一个检查空间是否充足的函数如果不足顺便扩容。 那么既然说到扩容我们应该怎样扩容呢
我这里有三种扩容方式 1.一次扩容一个空间 2.一次扩容多个大小的空间 3.成倍的增加空间1.5倍2倍 这里我推荐第三种方法。
理由 第一种一次扩容一个空间好处是不会造成空间的浪费缺点是如果我们输入大量数据时它需要多次开辟导致程序效率低下。 第二种一次开辟多个空间有效解决了第一种导致程序小路低下的问题但是它也有相应的问题我们不能确定一次开辟多大的空间合适如果开辟小了一样也会和第一种一样多次扩容影响程序效率但如果一下周四开辟空间过大也会导致空间被浪费。 我们先定义函数
void SLCheckCapacity(SL* ps)
接着判断是否需要扩容然后扩容空间但是由于我们初始化直接是NULL所以这里我再加上一个三目操作符总体代码如下
void SLCheckCapacity(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!);exit(1);}//扩容成功ps-arr tmp;ps-capacity newCapacity;}
}
这里我设置了tmp变量是为了防止扩容失败。这里我选择的就是扩容原来的两倍。 接下来我们按照上面的思路把头插完善
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i 0; i--) //i 1{ps-arr[i] ps-arr[i - 1]; //ps-arr[1] ps-arr[0]}ps-arr[0] x;ps-size;
} 3.尾插
做完了头插我们可以来试试尾插数组中尾插是神简单的如图 如果空间充足我们可以直接再尾部插入我们的数据然后吧size不够的话先扩容然后再执行
void SLPushBack(SL * ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps-arr[ps-size] x;
}
这样头插和尾插就完成了 4.头删
完成了插入那么我们还需要完成删除删除相比较插入它有什么不同删除不需要太在意空间。
现在我们先来完成头删。
在数组中我们怎么完成头删的呢如图
我们一般是把每个数向前移动一位数组有效长度-1及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--;
}
注意我们要确保ps和ps-size不为NULL 5.尾删
这个操作实现起来其实非常简单我们可以直接size--;
代码示例
void SLPopBack(SL* ps)
{assert(ps);assert(ps-size); ps-size--;} 完成这些那么我要上难度了删除指定位置的值/插入指定位置的值 6.删除指定位置的值
具体思路就是遍历去寻找所需数值然后并将该数值之后的数据的下标前移siza--如图 代码示例
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-arr[i-2] ps-arr[i-1];}ps-size--;
}7.在指定位置插入值
思路找到数值将该数值及其后的向后移动一位。size
如图 代码示例
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);//pos及之后的数据往后挪动一位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;
}
注这是插入要检查空间是否足够 8.打印
完成这些我们可以来尝试打印我们的顺序表类似打印数组。
代码示例
void SLPrint(SL* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
} 9.销毁顺序表
在我们之前讲过动态内存开辟最后要再释放。
代码示例
void SLDestroy(SL* ps)
{assert(ps);if (ps-arr) {free(ps-arr);}ps-arr NULL;ps-size ps-capacity 0;
}
最后来展示程序代码
#includeSeqList.h
void SLInit(SL* ps)
{ps-arr NULL;ps-size ps-capacity 0;
}
void SLDestroy(SL* ps)
{assert(ps);if (ps-arr) {free(ps-arr);}ps-arr NULL;ps-size ps-capacity 0;
}
void SLCheckCapacity(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!);exit(1);}//扩容成功ps-arr tmp;ps-capacity newCapacity;}
}
void SLPushBack(SL * ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps-arr[ps-size] x;
}
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i 0; i--) //i 1{ps-arr[i] ps-arr[i - 1]; //ps-arr[1] ps-arr[0]}ps-arr[0] x;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 SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);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);for (int i pos; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}
void SLPrint(SL* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}
void SLDestroy(SL* ps)
{assert(ps);if (ps-arr) {free(ps-arr);}ps-arr NULL;ps-size ps-capacity 0;
}
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x) {assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);//pos及之后的数据往后挪动一位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-arr[i-2] ps-arr[i-1];}ps-size--;
}这样一个循序表完成了你可以用设计的函数来进行操作。
