株洲网站平台搭建,广州市南沙区建设局网站,泉州手机端建站模板,泰安高品质网站建设超详细讲解线性表和顺序表#xff01;#xff01;线性表顺序表顺序表的概念及结构静态顺序表动态顺序表顺序表接口实现1、创建2、初始化3、扩容4、尾插5、打印6、销毁7、尾删8、头插9、头删10、插入任意位置11、删除任意位置12、查找13、修改线性表
线性表#xff08;linea…
超详细讲解线性表和顺序表线性表顺序表顺序表的概念及结构静态顺序表动态顺序表顺序表接口实现1、创建2、初始化3、扩容4、尾插5、打印6、销毁7、尾删8、头插9、头删10、插入任意位置11、删除任意位置12、查找13、修改线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储 地址的计算 线性表中第一个元素的存储地址基地址和表中每个元素所占存储单元的多少就可以计算出线性表中任意一个数据元素的存储地址从而实现对顺序表中数据元素的随机存取。 设线性表中有n个元素每个元素占k个单元第一个元素的地址为Loca_1,则第i个元素的地址Loca_iLoca_iLoca_1i-1*k
顺序表
顺序表的概念及结构
顺序表是在计算机内存中以数组的形式保存的线性表线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系采用顺序存储结构的线性表通常称为顺序表。 顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为静态顺序表与动态顺序表。
静态顺序表
静态顺序表使用定长数组存储元素。 静态顺序表从某种意义上来说就是数组 如果数组空间满了就无法继续插入。 无法很好地确定要给定的内存空间大了浪费空间小了空间不足。 静态顺序表的大小在编译时确定对静态顺序表的删除和插入是对其元素进行而不是其存储空间的删除和插入因此静态顺序表的大小在进行删除和插入操作后不会改变。 对于静态顺序表的查找若按序号查找则时间复杂度为O(1)。若按值查找则需要将待查元素与表中每一个元素进行比较直到找到或者遍历整个数组却找不到元素此操作的时间复杂度为O(N)。
动态顺序表 顺序表接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。
void SLInit(SL* ps);//名字简写 初始化
void SLPushBack(SL* ps, SLDatatype x); //尾插
void SLPopBack(SL* ps); //尾删
void SLPushFront(SL* ps, SLDatatype x); //头插
void SLPopFront(SL* ps); //头删
void SLPrit(SL* ps); //打印
void SLDestory(SL* ps); //释放
void SLCheckCapacity(SL* ps); //检查容量-扩容
void SLInsert(SL* ps, int pos, SLDatatype x);//任意位置插入
void SLErase(SL* ps, int pos); //任意位置删除
int SLFind(SL* ps, SLDatatype x); //查找
void SLModify(SL* ps,int pos, SLDatatype x); //修改在此之前明白何为接口函数 接口函数就是某个模块写了主要给其它模块用的函数可以实现隐藏信息封装等数据进行操作时进行调用的函数通过调用数据结构的接口帮助你完成一系列操作
1、创建
因为是一个比较大的板块在一开始创建时尽量分开不同板块编写。
#pragma once
#include stdlib.h
#include stdio.h
#include assert.h//#define N 200
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;//指向动态数组指针int size; //数据个数int capacity; //容量-空间大小
}SL;使用 typedef 定义一个新的数据类型这里我们把它取名为 SLDataType顺序表数据类型。
2、初始化
#include SeqList.h//初始化函数
void SLInit(SL* ps)
{ps-a NULL;ps-size ps-capacity 0;
}3、扩容
插入元素的时候理所应当需要考虑插入元素时空间是否足够如果空间不够则使用realloc函数扩容。realloc函数在一开始没空间申请空间时等作用于malloc函数的作用
//检查容量-扩容
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){int newcapacitv ps-capacity 0 ? 4 : ps-capacity * 2;SLDatatype* tmp (SLDatatype*)realloc(ps-a, newcapacitv * sizeof(SLDatatype));if (tmp NULL){perror(relloc:);exit(-1);//结束程序}ps-a tmp;ps-capacity newcapacitv;}
}4、尾插
void SLPushBack(SL* ps, SLDatatype x)
{SLCheckCapacity(ps);//检查容量空间ps - a[ps-size] x;ps-size;
}尾插有三种情况 ① 第一种情况是顺序表压根就没有空间。 ② 第二种情况就是我们创建的 capacity 空间满了。 ③ 第三种情况是空间足够直接插入数据即可。
5、打印
打印我们表中所存放的函数。
//打印函数
void SLPrit(SL* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}6、销毁
不销毁会存在内存泄漏的风险。
void SLDestory(SL* ps)//动态开辟的内存越界使用有时
{ //有时要在free的时候才能检查出来。if (ps-a){free(ps-a);ps-a NULL;ps-size ps-capacity 0;}
}7、尾删
删除最后一个元素。只需要元素数量–就好无法访问最后一个元素那么它便是无效的数据。
void SLPopBack(SL* ps)
{assert(ps-size);ps-size--;
}当然包括尾删以及其他步骤我们都必须要注意越界访问的问题。比如尾删步骤中如果内存中一个元素都没有了size有可能减到-1的位置上而出现错误需要断言一下。 当然温柔的检查以及暴力的检查读者们喜欢哪个就全取决于自己了。
// 温柔的检查if (ps-size 0){return;}// 暴力的检查assert(ps-size 0);//ps-a[ps-size - 1] 0;ps-size--;
}8、头插
将数组内容整体后移就可以在最前面出现一个空的位置。 首先创建一个 end 变量用来指向要移动的数据因为指向的是数据的下标所以是 size 要减 1 。随后进入 while 循环如果 end 0 说明还没有移动完就会进入循环。循环体内利用下标进行向后移动操作移动结束后再 end-- 进行下一个数据的向后移动。挪动数据成功后就可以插入了。此时顺序表第一个位置就被腾出来了就可以在下标0位置插入欲插入的数据 x 了。最后size 。
void SLPushFront(SL* ps, SLDatatype x)
{SLCheckCapacity(ps);//从后向前挪动数据int end ps-size - 1;while (end 0){ps-a[end 1] ps-a[end];end--;}ps-a[0] x;ps -size;
}9、头删
思路和头插类似。
//头删
void SLPopFront(SL* ps)
{assert(ps-size);int begin 1;while (begin ps-size){ps-a[begin-1] ps-a[begin];begin;}ps-size--;
}10、插入任意位置 //任意插入
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;ps-size;
}11、删除任意位置
删除指定位置的数据我们仍然要限制 pos 的位置。限制条件部分和 SeqListInsert 不同的是因为 psl-size 这个位置没有效数据所以删除的位置不能是 psl-size 任意位置删除的函数可以替代头删和尾删。
//任意删除
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;}*/int begin pos 1;while (begin ps-size){ps-a[begin - 1] ps-a[begin];begin;}ps-size--;
}12、查找
//查找
int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1;}13、修改
//修改
void SLModify(SL* ps, int pos, SLDatatype x)
{assert(ps);assert(pos 0 pos ps-size);ps-a[pos] x;}
