网站建设推广什么意思,外贸流程的英文,郑州竞价托管,定制衣柜哪种板材最好本章会介绍的知识点如下图#xff1a; 1#xff1a; 顺序表的概念#xff1a;顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构#xff0c;通常我们使用数组来表示#xff0c;对数组进行增删查改。 顺序表的结构#xff1a;逻辑结构与物理结构都是内存中一块…本章会介绍的知识点如下图 1 顺序表的概念顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构通常我们使用数组来表示对数组进行增删查改。 顺序表的结构逻辑结构与物理结构都是内存中一块连续开辟的空间都是11对应的线性结构。
2 顺序表的两种定义方式静态的顺序表与动态的顺序表一般情况下我们很少会用静态的顺序表因为静态的顺序表会将空间固定导致如果我们使用顺序表的时候可能会浪费很多的空间也可能在我们增容的时候会出现空间不够的情况这种情况下如果我们还是在继续使用的话那么数组将会越界这种情况是error的。
两种定义顺序表的方式代码如下 静态的顺序表
typedef int SqListDataType;//这里是给我们的顺序表元素的类型起个名字
// 假设元素是其他类型我们就可以修改这里
//静态的
struct SqList1
{SqListDataType arr1[1000];//开辟了一个整形的数组int size;//用来记录顺序表当前使用了多少的空间
};
动态的顺序表 struct SqList2
{SqListDataType* arr2;int size;int Capacity;//用来记录当前数组开辟了多少个空间
};
在这两种结构中通常我们是会选择动态的顺序表来管理数据的。
3顺序表的接口实现
我们最终选择这个定义的顺序表 1这个接口的定义是应为当我们在增加元素的时候我们所存储的元素会变多总有一种情况下我们空间会慢所以这时候我们就需要扩容使用了realloc这个函数扩容有两种情况一种是原地扩一种是换个空间扩。不管怎么样我们都定义一个空间用来存储新开辟的地址让后在给ps //检查容量的代码
void check_capacity(SqList* ps)
{assert(ps);//空间不够扩容,一次扩两倍if (ps-Capacity ps-size){SqListDataType* tmp(SqListDataType*)realloc(ps-arr, (ps-Capacity)* 2*sizeof(SqListDataType));if (tmp NULL){perror(realloc fail);exit(-1);}else{printf(扩容成功\n);ps-arr tmp;ps-Capacity * 2;}}}
2头插思路先检查空间是否足够在从后往前移动元素将第一个位置给空出来最后在添加元素即可。
void PushFrontSqList(SqList* ps, SqListDataType x)
{//先检查空间够不够,空间不够扩容check_capacity(ps);//先判断空间是否满了//先移动元素int end ps-size - 1;while (end 0){ps-arr[end 1] ps-arr[end];end--;}ps-arr[0] x;ps-size;
}
上述代码的意思如下图 3尾插思路这个挺简单的我们只要在size位置插入即可size在即可这里要注意的就是我们插入要以数组的下标。
代码
void PushBackSqList(SqList* ps, SqListDataType x)
{assert(ps);check_capacity(ps);ps-arr[ps-size] x;ps-size;//SqListInsert(ps, ps-size, x);
}4头删思路我们首先得判断顺序表是否有元素如果有的话才能进行删除我们只需要遍历数组从前往后将后一个元素移动到前一个就行这里需要注意的就是我们移动时位置的不同可能导致代码的不一样而我的代码是从第一个开始所以我最后的位置因该是size-2处然后size--就可以了。
代码
void PopFrontSqList(SqList* ps)
{assert(ps);assert(ps-size 0);int i 0;for (i 0; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}
5尾删思路这个挺简单的首先还是得判断顺序表是否存在元素如果有将size--就行了。
代码
void PopBackSqList(SqList* ps)
{assert(ps);assert(ps-size 0);ps-size--;
}
6顺序表得查找思路遍历数组就行了如果存在则返回下标如果不存在我们返回-1.
代码
int FindSqList(SqList* ps, SqListDataType x)
{assert(ps);//防止ps没有意义//思路遍历顺序表找int i 0;for (i 0; i ps-size; i){if (ps-arr[i] x){return i;}}//未找到printf(未找到\n);return -1;
}
7顺序表插入思路在pos位置处插入一个元素pos为下标首先先我们得判断pos是否存在如果存在我们先从前往后将元素向后移动然后在pos位置处插入即可。
代码
void SqListInsert(SqList* ps, int pos, SqListDataType x)
{assert(ps);assert(pos 0 pos ps-size);check_capacity(ps);int end ps-size - 1;while (end pos){ps-arr[end 1] ps-arr[end];end--;}ps-arr[pos] x;ps-size;
}
图 8顺序表的删除思路先判断pos是否在顺序表中我们只要从前完后移动pos后面的元素即可然后我们在把size--
代码
void SqListErase(SqList* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int i pos;for (i pos; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}
9顺序表的修改思路先判断pos是否在顺序表中然后在根据数组随机访问的特点修改即可。
代码
void ModifySqlist(SqList* ps, int pos, SqListDataType x)
{assert(ps);assert(pos 0 pos ps-size);ps-arr[pos] x;}
10打印遍历数组即可
代码
void SqListPrint(SqList* ps)
{assert(ps);int i 0;for (i 0; i ps-size; i){printf(%d , ps-arr[i]);}printf(\n);
}
11销毁顺序表这一步也不能省略防止内存泄漏。
代码
//销毁
void DestorySqList(SqList* ps)
{assert(ps);free(ps-arr);ps-arr NULL;ps-Capacity ps-size 0;
}
以上就是顺序表的大致结构了。
通过上面我们可以发现顺序表适合尾插尾删修改这是因为顺序表随机访问的特点造成的。 本章完感谢大家的观看。
