淘宝网站建设流程,金水区网站建设,网站备案 必须在接入商处,wordpress 获取文章时间前言
介绍 #x1f343;数据结构专区#xff1a;数据结构
参考
该部分知识参考于《数据结构#xff08;C语言版 第2版#xff09;》24~28页
补充
此处的顺序表创建是课本中采用了定义方法为SqList Q来创建#xff0c;并没有使用顺序表指针的方法#xff0c;具体两个…
前言
介绍 数据结构专区数据结构
参考
该部分知识参考于《数据结构C语言版 第2版》24~28页
补充
此处的顺序表创建是课本中采用了定义方法为SqList Q来创建并没有使用顺序表指针的方法具体两个方法的差别我在此处补充一下 说明顺序表指针L和顺序表Q都可以表示一个顺序表但前者是通过指针L间接地表示顺序表其定义方式为SqList* L后者是直接地表示顺序表其定义方式为SqList Q。
前者引用length域的方式为L-length,后者引用length的方式是Q.length。
前者开辟空间的方式是L (SqList*)malloc(sizeof(SqList))后者开辟空间使用new.
前者释放空间仅仅需要free(L)后者释放空间需要使用delete[]。
每一个清晨都是世界对你说的最温柔的早安ૢ(≧▽≦)و✨ 目录
前言
1、顺序表的基本概念
2、顺序表的基本操作
2.1 宏定义与结构体
2.2 初始化
2.3 销毁
2.4 判空
2.5 求表长
2.6 按序号查找取值
2.7 按值查找
2.8 插入
2.9 删除
2.10 输出顺序表
2.11 整体代码含测试
结语 1、顺序表的基本概念 顺序表又称顺序存储结构的线性表是一种线性数据结构用于存储具有相同类型的数据元素。它使用一段地址连续的存储单元依次存储线性表的数据元素。以下是顺序表的基本概念 存储结构 顺序表使用一段连续的存储空间如数组来存储数据元素。每个数据元素在存储空间中都有一个唯一的索引或位置可以通过索引快速访问数据元素。基本操作 初始化创建一个空的顺序表并设置其初始容量。插入在顺序表的指定位置插入一个数据元素。可能需要移动元素以腾出空间。删除从顺序表的指定位置删除一个数据元素。可能需要移动元素以填补空缺。查找根据数据元素的值或索引查找数据元素的位置。遍历按顺序访问顺序表中的每个数据元素。特点 访问速度快由于数据元素存储在连续的内存块中可以通过索引直接访问任意位置的数据元素时间复杂度为O(1)。插入和删除操作可能较慢在顺序表中插入或删除数据元素时可能需要移动其他数据元素时间复杂度为O(n)其中n是顺序表的长度。存储密度高顺序表中的数据元素在内存中是连续存储的没有额外的指针开销存储密度较高。 2、顺序表的基本操作
2.1 宏定义与结构体
#includeiostream
#include cstdlib
using namespace std;//控制最大值
#define MAXSIZE 1000
//声明Status用于记录返回结果
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1typedef int ElemType;
typedef struct
{ElemType *elem; //存储空间的基地址int length;
}SqList;2.2 初始化 O(1)
//初始化
Status InitList(SqList L)
{//构造一个空的顺序表L.elem new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间if (!L.elem) //如果分配失败就退出{exit(OVERFLOW);}L.length 0;return OK;
}2.3 销毁 O(1)
//销毁
Status DestroyList(SqList L)
{delete[] L.elem; // 释放elem指向的数组 L.elem NULL; // 将指针设为NULL避免野指针这一步最好是置为nullptr L.length 0; // 长度设为0虽然这一步在销毁时不是必需的但可以作为一种清理措施 return OK;
}
2.4 判空 O(1)
//判空
Status ListEmpty(SqList L)
{if (L.length 0){return OK;}else{return ERROR;}
}2.5 求表长 O(1)
//求线性表长度
int ListLength(SqList L)
{return(L.length);
}2.6 按序号查找取值 O(1)
//取值 ~ 按序号查找
//该算法根据指定的位置序号来获取顺序表中第i个位置的元素的值
//将第i个数据返还给e
Status GetElem(SqList L, int i, ElemType e)
{//1.判断i值是否合理不合理报错if (i 1 || i L.length){return ERROR;}e L.elem[i - 1]; //第i-1位置存储第i个数据return OK;
}
2.7 按值查找 O(n)
//按值查找
//从第1个元素开始不断比较e查找成功返回元素的序号i 1
int LocateElem(SqList L, ElemType e)
{for (int i 0; i L.length; i){if (L.elem[i] e){return i 1;}}return 0; //查找失败返回0
}
2.8 插入 O(n)
//插入
//在表的第i个位置插入一个新的数据元素e
//第i个位置的下标是i - 1
Status ListInsert(SqList L, int i, ElemType e)
{//判断位置是否合理//i的合法位置是 1 i L.length 1 if (i 1 || i L.length 1){return ERROR;}//判断空间是否充足if (L.length MAXSIZE){return ERROR;}//将要插入位置后面的数据依次向后移动for (int j L.length - 1; j i - 1; j--){L.elem[j 1] L.elem[j];}L.elem[i - 1] e;L.length;return OK;
}
2.9 删除 O(n)
//删除
//将第i个位置的元素删除即将i1至第n个元素依次向前移动一位
Status ListDelete(SqList L, int i)
{//判断i位置是否合法if (i 1 || i L.length){return ERROR;}for (int j i; j L.length; j){L.elem[j - 1] L.elem[j];}--L.length;return OK;
}
2.10 输出顺序表 O(n)
//输出线性表
void DispList(SqList L)
{for (int i 0; i L.length; i){cout L.elem[i] ;}cout endl;
}
2.11 整体代码含测试
#includeiostream
#include cstdlib
using namespace std;//控制最大值
#define MAXSIZE 1000
//声明Status用于记录返回结果
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1typedef int ElemType;
typedef struct
{ElemType *elem; //存储空间的基地址int length;
}SqList;//初始化
Status InitList(SqList L)
{//构造一个空的顺序表L.elem new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间if (!L.elem) //如果分配失败就退出{exit(OVERFLOW);}L.length 0;return OK;
}//销毁
Status DestroyList(SqList L)
{delete[] L.elem; // 释放elem指向的数组 L.elem NULL; // 将指针设为NULL避免野指针这一步最好是置为nullptr L.length 0; // 长度设为0虽然这一步在销毁时不是必需的但可以作为一种清理措施 return OK;
}//判空
Status ListEmpty(SqList L)
{if (L.length 0){return OK;}else{return ERROR;}
}//求线性表长度
int ListLength(SqList L)
{return(L.length);
}//取值 ~ 按序号查找
//该算法根据指定的位置序号来获取顺序表中第i个位置的元素的值
//将第i个数据返还给e
Status GetElem(SqList L, int i, ElemType e)
{//1.判断i值是否合理不合理报错if (i 1 || i L.length){return ERROR;}e L.elem[i - 1]; //第i-1位置存储第i个数据return OK;
}//按值查找
//从第1个元素开始不断比较e查找成功返回元素的序号i 1
int LocateElem(SqList L, ElemType e)
{for (int i 0; i L.length; i){if (L.elem[i] e){return i 1;}}return 0; //查找失败返回0
}//插入
//在表的第i个位置插入一个新的数据元素e
//第i个位置的下标是i - 1
Status ListInsert(SqList L, int i, ElemType e)
{//判断位置是否合理//i的合法位置是 1 i L.length 1 if (i 1 || i L.length 1){return ERROR;}//判断空间是否充足if (L.length MAXSIZE){return ERROR;}//将要插入位置后面的数据依次向后移动for (int j L.length - 1; j i - 1; j--){L.elem[j 1] L.elem[j];}L.elem[i - 1] e;L.length;return OK;
}//删除
//将第i个位置的元素删除即将i1至第n个元素依次向前移动一位
Status ListDelete(SqList L, int i)
{//判断i位置是否合法if (i 1 || i L.length){return ERROR;}for (int j i; j L.length; j){L.elem[j - 1] L.elem[j];}--L.length;return OK;
}//输出线性表
void DispList(SqList L)
{for (int i 0; i L.length; i){cout L.elem[i] ;}cout endl;
}int main() {SqList L;ElemType e;int position;cout 开始测试顺序表操作函数 endl;// 测试初始化函数cout \n1. 测试初始化函数 InitList endl;if (InitList(L) OK) {cout 顺序表初始化成功 endl;}else {cout 顺序表初始化失败 endl;return 1;}// 测试插入函数cout \n2. 测试插入函数 ListInsert endl;for (int i 1; i 5; i) {if (ListInsert(L, i, i * 10) OK) {cout 成功在位置 i 插入元素 i * 10 endl;}else {cout 在位置 i 插入元素失败 endl;}}// 测试输出函数cout \n3. 测试输出函数 DispList endl;cout 当前顺序表内容;DispList(L);// 测试取值函数cout \n4. 测试取值函数 GetElem endl;if (GetElem(L, 3, e) OK) {cout 第3个元素的值为 e endl;}else {cout 获取第3个元素失败 endl;}// 测试查找函数cout \n5. 测试查找函数 LocateElem endl;e 30;position LocateElem(L, e);if (position) {cout 元素 e 在顺序表中的位置是 position endl;}else {cout 元素 e 不在顺序表中 endl;}// 测试删除函数cout \n6. 测试删除函数 ListDelete endl;if (ListDelete(L, 2) OK) {cout 成功删除第2个元素 endl;cout 删除后的顺序表内容;DispList(L);}else {cout 删除第2个元素失败 endl;}// 测试求长度函数cout \n7. 测试求长度函数 ListLength endl;cout 当前顺序表的长度为 ListLength(L) endl;// 测试判空函数cout \n8. 测试判空函数 ListEmpty endl;if (ListEmpty(L) OK) {cout 顺序表为空 endl;}else {cout 顺序表不为空 endl;}// 测试销毁函数cout \n9. 测试销毁函数 DestroyList endl;if (DestroyList(L) OK) {cout 顺序表销毁成功 endl;}else {cout 顺序表销毁失败 endl;}// 验证销毁后的状态cout \n10. 验证销毁后的状态 endl;cout 销毁后顺序表的长度 L.length endl;cout 销毁后顺序表的指针 (L.elem NULL ? NULL : 非NULL) endl;cout \n所有测试完成 endl;return 0;
} 结语
顺序表的基本操作是后续学习各类型数据结构的基础希望大家可以认真来研读每一处代码和每一处逻辑也希望大家都有所进步
