濮阳市做网站公司,做网站卖掉,有赞微商城登录首页登录入口,h5作品文章目录 线性表线性表的定义线性表分类 顺序表顺次表的存储结构实现顺序表的主要接口函数初始化顺序表顺序表尾插顺序表尾删顺序表头插顺序表头删在指定位置插入数据在指定的位置删除数据头插#xff0c;头删#xff0c;尾插#xff0c;尾删新写法打印顺序表销毁顺序表 线性… 文章目录 线性表线性表的定义线性表分类 顺序表顺次表的存储结构实现顺序表的主要接口函数初始化顺序表顺序表尾插顺序表尾删顺序表头插顺序表头删在指定位置插入数据在指定的位置删除数据头插头删尾插尾删新写法打印顺序表销毁顺序表 线性表
线性表的定义
线性表是n个具有相同属性的数据元素的有限序列。线性表在逻辑上是线性结构也就是说连续的一条直线。但是在物理结构上不一定是连续的线性表在物理结构(存储结构)上一般采用顺序和链式的形式存储 线性表分类 顺序表
顺序表是用一段物理地址连续的存储单元存储元素的线性结构一般采用数组进行存储。在数组上完成数据元素的增删查改 顺序表一般分为
静态顺序表使用定长的数组存储动态顺序表使用动态开辟的数组存储
静态顺序表只适合确定需要存储多少数据的场景如果存储数据量不确定的话空间开太大浪费开太小不够用。一般都会去使用动态顺序表根据情况分配多大的空间。下面将介绍动态顺序表
顺次表的存储结构
图示
typedef int ElemType;
typedef struct SeqList
{ElemType* a;int size;int capacity;
}SeqList;定义一个动态顺序表需要三个属性 1.存储空间的地址需要一段空间来维护顺序表需要知道顺序表的起始地址 2.顺序表的元素个数记录顺序表的元素个数 3.顺序表的空间容量用来分配空间
实现顺序表的主要接口函数
//顺序表初始化
void SeqListInit(SeqList* ps);
//顺序表尾插
void SeqListPushBack(SeqList* ps, ElemType x);
//检查容量
void CheckCapicity(SeqList* ps);
//顺序表尾删
void SeqListPopBack(SeqList* ps);
//顺序表头插
void SeqListPushFront(SeqList* ps, ElemType x);
//顺序表头删
void SeqListPopFront(SeqList* ps);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, ElemType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);
//打印顺序表
void SeqListprintf(SeqList* ps);
//销毁顺序表
void DestroyedSeqList(SeqList* ps);初始化顺序表
这里先为顺序表申请了2个元素类型的空间大小。
void SeqListInit(SeqList* ps)
{ps-a (ElemType*)malloc(sizeof(ElemType)*2);ps-size 0;ps-capacity 2;
}顺序表尾插
在尾部插入的时候要考虑两种情况分别是 顺序表未满尾插直接将元素放入尾部即可 顺序表已满的情况下则需要申请更大的空间来存放数据 代码实现
void SeqListPushBack(SeqList* ps, ElemType x)
{assert(ps);//检查容量CheckCapicity(ps);//尾插ps-a[ps-size] x;ps-size;
}这里将检查容量封装成一个函数方便后面插入检查继续复用
void CheckCapicity(SeqList* ps)
{if (ps-size ps-capacity){int newcapacity ps-capacity * 2;ElemType* tmp (ElemType*)realloc(ps-a,sizeof(ElemType)*newcapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newcapacity;}
}顺序表尾删
在尾删时也应该考虑两种情况分别是 -顺序表已空时无需删除 -顺序表未空直接删除尾部元素即可 代码实现: 这里提供两种写法一种是暴力检查程序直接崩溃一种是防止越界程序可以正常运行
暴力检查版
void SeqListPopBack(SeqList* ps)
{//判空assert(ps-size 0);//如果尾删空顺序表程序直接崩溃//删除--(ps-size);
}防止越界版
void SeqListPopBack(SeqList* ps)
{//判空if (ps-size 0){return;}//删除--(ps-size);
}顺序表头插
和尾插一样要考虑是否有空间但是与尾插不同的地方在于需要挪动数据进行插入 图解 代码实现
void SeqListPushFront(SeqList* ps, ElemType x)
{//检查容量CheckCapicity(ps);//挪动数据int end ps-size - 1;while (end 0){ps-a[end 1] ps-a[end];end--;}//插入ps-a[0] x;ps-size;
}顺序表头删
头删和尾删一样先判空。与尾删不一样的地方在于删完后需要挪动数据 图解 代码实现
void SeqListPopFront(SeqList* ps)
{//判空if (ps-size 0){return;}//挪动数据覆盖删除int start 0;while (start ps-size) {ps-a[start] ps-a[start 1];start;}--ps-size;
}在指定位置插入数据
和头插的思想基本一样 图解 代码实现
void SeqListInsert(SeqList* ps, int pos, ElemType x)
{//检查容量CheckCapicity(ps);//挪动数据int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}//插入ps-a[pos] x;ps-size;
}在指定的位置删除数据
思想与头删基本一样 图解 代码实现
void SeqListErase(SeqList* ps, int pos)
{//判空if (ps-size 0){return;}//挪动数据覆盖删除while (pos ps-size){ps-a[pos] ps-a[pos 1];pos;}--ps-size;
}有了在指定位置插入和删除前提下头插头删尾插尾删新写法
头插头删尾插尾删新写法
//头插
void SeqListPushFront(SeqList* ps, ElemType x)
{SeqListInsert(ps, 0, x);
}
//头删
void SeqListPopFront(SeqList* ps)
{SeqListErase(ps, 0);
}
//尾插
void SeqListPushBack(SeqList* ps, ElemType x)
{SeqListInsert(ps, ps-size,x);
}
//尾删
void SeqListPopBack(SeqList* ps)
{SeqListErase(ps, ps-size);
}打印顺序表
void SeqListprintf(SeqList* ps)
{for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}销毁顺序表
动态开辟的内存需要我们主动去释放空间 这里需要主动free
void DestroyedSeqList(SeqList* ps)
{free(ps-a);ps-a NULL;ps-capacity ps-size 0;
}
