网站网域名查询,网站 设计 工具,外贸公司怎么运作,惠州seo建站一#xff0c;概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构#xff0c;一般情况下采用数组存储#xff1b; 在数组上完成数据的增删查改。 1#xff0c; 静态顺序表#xff1a;使用定长数组存储元素。 2.#xff0c;动态顺序表#xff1…
一概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储 在数组上完成数据的增删查改。 1 静态顺序表使用定长数组存储元素。 2.动态顺序表使用动态开辟的数组存储。 二接口实现 静态顺序表只适用于确定知道需要存多少数据的场景 静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用 所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表 1顺序表的创建动态
//动态顺序表
typedef int SLDataType;typedef struct SqList
{SLDataType* a;int size; //存储有效数据个数int capacity; //容量空间大小
}SL;
这里我们将数据类型暂时定为int类型typedef为SLDataType便于我们后续对顺序表数据类型的修改
定义属性表为SL*的指针a有效数据个数size现有容量capacity; 2接口函数
// 顺序表初始化
void SLInit(SL* ps);
// 顺序表销毁
void SLDestroy(SL* ps);
// 检查空间如果满了进行增容
void SLChenkCapacity(SL* ps);
//顺序表尾插
void SLPushBack(SL* ps,SLDataType x);
//顺序表尾删
void SLPopBack(SL* ps);
//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表头删
void SLPopFront(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x);
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos); 3初始化 //定义SL s1;//初始化SLInit(s1);
// 顺序表初始化
void SLInit(SL* ps)
{assert(ps);ps-a (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps-a NULL){perror(malloc);exit(-1);}ps-size 0;ps-capacity 4;
}
首先要进行断言ps不能为空如果ps为空则下面对ps解引用就会报错
刚开始先给 a 申请4个SLDataType大小的空间这个自己可以任意修改然后对size和capacity进行赋值 4销毁
// 顺序表销毁
void SLDestroy(SL*ps)
{assert(ps);free(ps-a);ps-a NULL;ps-size ps-capacity 0;
}
然后就是销毁顺序表直接用 free 释放掉 a 即可再置为空指针再重置 size 和 capacity 5判断是否增容
// 检查空间如果满了进行增容
void SLChenkCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){ps-a (SLDataType*)realloc(ps-a, ps-capacity * 2 * (sizeof(SLDataType)));if (ps-a NULL){perror(realloc);exit(-1);}ps-capacity ps-capacity * 2;}
}
像后面如果进行尾插头插的话就需要检查空间是否需要增容了也很好判断当size等于capacity时就需要增容了我们这里是选择直接扩容一倍
然后再更新一下capacity的值就行了 6尾插
//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//检查空间SLChenkCapacity(ps);ps-a[ps-size] x;ps-size;
}
首先判断是否需要增容此时size的值就是末尾的数的下标加一
直接对其下标进行赋值再让size加一 7尾删
//顺序表尾删
void SLPopBack(SL* ps)
{assert(ps);//温柔的检查//if (ps-size 0)// return;//暴力检查assert(ps-size 0);ps-size--;
}
这里有两种检查方式推荐暴力检查法要删除值size的值必须大于0
然后直接令size减一即可访问不到即为删除 8头插
//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLChenkCapacity(ps);int end ps-size-1;while (end 0){ps-a[end 1] ps-a[end];end--; }ps-a[0] x;ps-size;
}
还是先判断是否需要增容然后先将整体的值往后推一位
给头赋值令size加一 9头删
//顺序表头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size 0);int i 0;while (i ps-size - 1){ps-a[i] ps-a[i 1];i;}ps-size--;
}
要删除数据首先数据不能为空要进行断言一下
然后将整体往前推一位再令size减一 10打印
//顺序表打印
void SLPrint(SL* ps)
{assert(ps);int i 0;for (i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}
size是数据个数其减一就是末尾数据的下标然后进行遍历打印即可 11查找
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1;
}
直接遍历数组进行查找然后返回下标没有则返回-1 12指定位置进行插入
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x)
{assert(ps);assert(pos0 pos ps-size);SLChenkCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;
}
首先判断pos要大于等于0且小于等于size是否需要增容
然后从pos数组的值往后推一位再对其位置重新赋值再令size 13指定位置进行删除
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int i pos;while (i ps-size - 1){ps-a[i] ps-a[i 1];i;}ps-size--;
}
首先还是要判断pos的值大于等于0小于size因为数组下标为size是没有值的所以pos不能等于size
然后在pos处往前推一位令size-- 三源码 1头文件
SqList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h//动态顺序表
typedef int SLDataType;typedef struct SqList
{SLDataType* a;int size; //存储有效数据个数int capacity; //容量空间大小
}SL;// 顺序表初始化
void SLInit(SL* ps);
// 顺序表销毁
void SLDestroy(SL* ps);
// 检查空间如果满了进行增容
void SLChenkCapacity(SL* ps);
//顺序表尾插
void SLPushBack(SL* ps,SLDataType x);
//顺序表尾删
void SLPopBack(SL* ps);
//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表头删
void SLPopFront(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x);
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos); 2执行文件
SqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSqList.h// 顺序表初始化
void SLInit(SL* ps)
{assert(ps);ps-a (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps-a NULL){perror(malloc);exit(-1);}ps-size 0;ps-capacity 4;
}// 顺序表销毁
void SLDestroy(SL*ps)
{assert(ps);free(ps-a);ps-a NULL;ps-size ps-capacity 0;
}// 检查空间如果满了进行增容
void SLChenkCapacity(SL* ps)
{assert(ps);if (ps-size ps-capacity){ps-a (SLDataType*)realloc(ps-a, ps-capacity * 2 * (sizeof(SLDataType)));if (ps-a NULL){perror(realloc);exit(-1);}ps-capacity ps-capacity * 2;}
}//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//检查空间SLChenkCapacity(ps);ps-a[ps-size] x;ps-size;
}//顺序表尾删
void SLPopBack(SL* ps)
{assert(ps);//温柔的检查//if (ps-size 0)// return;//暴力检查assert(ps-size 0);ps-size--;
}//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLChenkCapacity(ps);int end ps-size-1;while (end 0){ps-a[end 1] ps-a[end];end--; }ps-a[0] x;ps-size;
}//顺序表头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size 0);int i 0;while (i ps-size - 1){ps-a[i] ps-a[i 1];i;}ps-size--;
}//顺序表打印
void SLPrint(SL* ps)
{assert(ps);int i 0;for (i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1;
}// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x)
{assert(ps);assert(pos0 pos ps-size);SLChenkCapacity(ps);int end ps-size - 1;while (end pos){ps-a[end 1] ps-a[end];end--;}ps-a[pos] x;ps-size;
}// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);int i pos;while (i ps-size - 1){ps-a[i] ps-a[i 1];i;}ps-size--;
}
如有不足之处欢迎来补充交流
完结。。。
