响应式网站建设有利于seo,网站建设的学习方法,合肥seo排名优化,开发高端网站建设文章目录一#xff1a;线性表二#xff1a;顺序表1#xff1a;概念与结构1#xff1a;静态顺序表2#xff1a;动态顺序表2#xff1a;动态顺序表的代码实现1#xff1a;结构2#xff1a;接口实现1#xff1a;初始化2#xff1a;释放内存3#xff1a;检查容量4#…
文章目录一线性表二顺序表1概念与结构1静态顺序表2动态顺序表2动态顺序表的代码实现1结构2接口实现1初始化2释放内存3检查容量4尾插5尾删6头插7头删8顺序表在任意位置(pos)插入x9顺序表在任意位置(pos)删除x10在顺序表中查找指定值3接口优化1尾插尾删优化尾插尾删2头插头删优化头插头删一线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储 二顺序表
1概念与结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
1静态顺序表
静态顺序表使用定长数组存储元素
#pragma once //为了避免同一个头文件被包含(include)多次//静态顺序表:使用定长数组存储元素.(不太实用)
// Max太小了不够用 太大了怕浪费
#define Max 10
//定长数组不只是int类型的,
//因此用结构体来方便修改其他数据类型
typedef int SLDataType;//顺序表SL的DataType
typedef struct SeqList
{//int a[Max];//定长数组SLDataType a[Max];size_t size;//记录数组中的有效数据
}SL;静态顺序表一般不太实用 我们经常用的是动态顺序表
2动态顺序表
动态顺序表使用动态开辟的数组存储
2动态顺序表的代码实现
1结构
//结构
typedef int SLDataType;//顺序表SL的DataType
typedef struct SeqList
{SLDataType* a;//定义一个指针指向动态开辟的数组size_t size;//记录数组中的有效数据(指向最后数据的下一个位置)size_t capcity;//空间容量的大小
}SL;2接口实现
1初始化
将有效数据个数和容量都初始化为0,并将指针指空
void SLInit(SL* ps)
{assert(ps);ps-a NULL;ps-size ps-capcity 0;
}2释放内存
释放顺序表的空间,并将指针指空,容量和数据个数置0 (只有在数组不为空的情况下才会销毁)
void SLDestroy(SL* ps)
{//if (ps-a ! NULL)if (ps-a)//非0为真{free(ps-a);ps-a NULL;ps-size ps-capcity 0;}
}3检查容量
在增加数据的时候首先需要判断顺序表的容量是否够用如果不够用就需要增容。
每次扩容扩成原来容量二倍的原因
如果一次扩多了会造成空间的浪费扩的少了在增加数据的时候就需要频繁扩容降低了程序的效率。realloc函数扩容存在原地扩容和异地扩容俩种情况如果是异地的话无疑会更加增加扩容的成本需要花费更多时间。综合考虑俩种因素扩成原来的二倍是比较合理的
我们知道开辟动态空间使用的是malloc或者calloc函数而realloc是用来扩容的而我们这里仅使用realloc既实现开辟又实现扩容。-
仅用realloc不用malloc的原因
malloc仅在初始化后容量为0的时候开辟动态空间使用之后的扩容都是使用到realloc如果分情况写就会比较冗余realloc同样可以实现malloc的功能当传给realloc的指针是空指针NULL的时候realloc的功能和malloc是一样的所以我们在初始化时也是将管理数据的指针设为空指针的
void SLCheckCapacity(SL* ps)
{assert(ps);//扩容if (ps-size ps-capcity)//如果越界了或者为NULL{//一般2倍扩容//如果是0,则空间为4个(随机)int newCapcity ps-capcity * 2 0 ? 4 : ps-capcity * 2;//空间容量应当将个数*字节//realloc:返回新开的数组空间的地址,可能第一次为NULL,也有可能接收失败//因此用tmp变量接收SLDataType* tmp realloc(ps-a, newCapcity * sizeof(SLDataType));if (tmp NULL){perror(realloc is fail);exit(-1);//异常终止返回-1,正常结束返回0}ps-a tmp;ps-capcity newCapcity;}
}4尾插
在数组尾部插入数据,首先要考虑扩容问题,再插入数据,同时元素个数增加
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//防止数组越界ps-a[ps-size] x;ps-size;
}5尾删
删除数组尾部的数据,同时元素个数减小,要考虑数组为空不能删的情况
void SLPopBack(SL* ps)
{//温柔的检查//if (ps-size 0) //{// return;//}//暴力检查assert(ps-size 0);//为真就通过运行,为假就结束运行了ps-size--;
}6头插
在数组尾部插入数据,首先要考虑扩容问题,再将数组的每个元素依次向后移动一位再在第一个位置插入数据即可,同时元素个数增加
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//从最后一个数据开始依次向后挪动一位数据进行覆盖int end ps-size - 1;while (end 0){ps-a[end 1] ps-a[end];end--;}ps-a[0] x;//头部插入数据ps-size;
}7头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size 0);//从第一个元素开始删int begin 0;while (begin ps-size - 1){ps-a[begin] ps-a[begin 1];begin;}//或者从第二个元素开始删/*int begin 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}*/ps-size--;
}8顺序表在任意位置(pos)插入x
//任意位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{//防止越界assert(ps);assert(pos 0 pos ps-size);//检查容量SLCheckCapacity(ps);//从最后一个数据到目标位置结束开始依次向后挪动一位数据覆盖int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;//在pos处插入数据ps-size;
}9顺序表在任意位置(pos)删除x
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int begin pos;while (begin ps-size - 1){ps-a[begin] ps-a[begin 1];begin;}ps-size--;//或者/*int begin pos 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;*/
}
10在顺序表中查找指定值
//查找指定值
int SLFind(SL* ps, SLDataType x, int begin)
{assert(ps);for (int i begin; i ps-size; i){if (ps-a[i] x){return i;//找到直接返回下标}}//查找不到返回-1return -1;
}3接口优化
1尾插尾删优化
尾插
void SLPushBack(SL* ps, SLDataType x)
{//在下标为size的位置插入数据(末尾元素的下一个)SLInsert(ps, ps-size, x);
}尾删
void SLPopBack(SL* ps)
{//删除下标为size-1的数据(末尾元素)SLErase(ps, ps-size - 1);
}2头插头删优化
头插
void SLPushFront(SL* ps, SLDataType x)
{ //在下标为0的位置插入数据(首元素)SLInsert(ps, 0, x);
}头删
void SLPopFront(SL* ps)
{//删除下标为0的数据(首元素)SLErase(ps, 0);
}具体代码可见https://gitee.com/calcium-oxide-2411/test_c
