title: 数据结构学习笔记 —— 线性表 tags: 数据结构
定义
由n(n≥0)个数据结构相同的元素构成的有限序列。
重要特点
1)除了第一个元素外,结构中的每一个数据元素均只有一个前驱
2)除了最后一个元素外,结构中的每一个数据元素均只有一个后驱
线性表 —— 顺序表
定义
用一组地址连续的存储单元依次存储线性表的数据元素。
特点
优点:随机存储
缺点:在做插入和删除操作时,需要移动大量元素。并且当元素多变化大是会造成存储空间浪费。(解决:链式存储)
描述
#define MAXSIZE 100
typedef struct
{
ElemType * elem; //存储空间的地址
int length; // 当前长度
}SqList; // 顺序表的结构类型 Sqlist
例:
//构造顺序表
#include<stdio.h>
#define MAXSIZE 100
typedef struct
{
int* elem; //声明动态数组
int length; //记录表的当前长度
int maxsize; //记录表的分配容量(最大长度)
}SqList;
顺序表的基本操作
这是下面所使用函数的原型
// 创建顺序表
typedef struct
{
int* elem; //声明动态数组
int length; //记录表的当前长度
int size; //记录表的分配容量(最大长度)
}SqList;
// 初始化顺序表
int Initlist(SqList &L)
{
L.elem = (int*)malloc(MAXSIZE * sizeof(int)); //构造一个空的顺序表,动态申请存储空间
if (!L.elem) //如果申请失败,作出提示并安全退出程序
{
printf("初始化失败!");
exit(0);
}
L.length = 0; //表的初始长度为0
L.size = MAXSIZE; // 表的存储空间(最大长度)为MAXSIZE
return L;
}
// 赋值
void get_value(SqList& L)
{
int i, n;
//scanf_s("%d",&n);
for (i = 0; i < L.size; i++)
{
L.elem[i] = i + 1;
L.length++;//长度随赋值情况增加
}
}
//取值
int GetElem(SqList L, int i, int& e)
{
if (i < 1 || i > L.length) //判断i的值是否合理(是否为负数或是否超出表长),不合理返回ERROR
{
printf("获取值失败!");
exit(0);
}
e = L.elem[i - 1]; // elem[i - 1]单元存储第i个数据元素
return e;
}
//按值查找
int LocateElem(SqList L, int e)
{
int i ;
for (i = 0; i < L.length; i++)
{
if (L.elem[i] == e)
{
return i + 1; //数组下标为i的元素,其序号为i + 1
}
}
return 0; //查找失败, 返回0
}
// 插入
void ListInsert(SqList& L, int i, int e)
{ //在顺序表L中第i个位置的新元素e,i值的合法范围是1≤ i ≤L.length + 1
int j;
if (i < 0 || i > L.length)
{
printf("插入失败!");
exit(0);
}
if (L.length == MAXSIZE) //当前存储空间已满
{
printf("空间已满!");
exit(0);
}
for ( j = L.length; j >= i; j--)
{
L.elem[j + 1] = L.elem[j]; // 插入位置及之后的元素后移
}
L.elem[j - 1] = e; // 将新元素e放入第i个位置
++L.length; //表长加一
}
void ListDelete(SqList& L, int i)
{
int j;
if ((i < 0) || (i > L.length)) //i值不合法
{
printf("删除失败!");
exit(0);
}
for ( j = i; j <= L.length - 1; j++)
{
L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移
}
--L.length; //表长减一
}
初始化
算法描述
Status InitList(SqList &L) // &L 引用参数类型(因为表L会改变)
{
L.elem = new ElemType[MAXSIZE];
if(! L.elem)
{
exit(OVERFLOW); //内存分配失败退出
}
l.length = 0; // 空表长度为0
return OK;
}
例:
#include<stdio.h>
#define MAXSIZE
int main(void)
{
SqList L; //声明顺序表
Initlist(L); //初始化
return 0;
}
取值(时间复杂度为 O(1) )
算法描述文章来源:https://www.toymoban.com/news/detail-727908.html
Status GetElem(Sqlist L, int i, ElemType &e)
{
if(i < 1 || i > L.length) //判断i的值是否合理(是否为负数或是否超出表长),不合理返回ERROR
{
return ERROR;
}
e = L.elem[i - 1]; // elem[i - 1]单元存储第i个数据元素
return OK;
}
例
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
int main(void)
{
int i= 64; //取值第64个元素
int e = 0;
int t = 0;
SqList L; // 声明顺序表
Initlist(L); //初始化
get_value(L); //赋值
t = GetElem(L, i, e); //取值
printf("输出:%d", t);
free(L.elem);
return 0;
}
查找(平均算法复杂度为 O(n) )
算法描述
//按值查找
Status LocateElem(SqList L, ElemType e)
{
int i;
for (i = 0; i < L.length; i++)
{
if (L.elem[i] == e)
{
return i + 1; //查找成功, 返回序号 i + 1
}
}
return 0; //查找失败, 返回0
}
例
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
int main(void)
{
int e; //要查找的元素
SqList L; // 声明顺序表
Initlist(L); //初始化
get_value(L); // 赋值
printf("请输入1-100中任意整数:");
scanf_s("%d", &e);
printf("查找结果:%d", LocateElem(L, e));
free(L.elem);
return 0;
}
插入(平均算法复杂度为 O(n) )
步骤
① 判断插入位置i是否合法(i值的合法范围是1≤i≤n+1),若不合法则返回ERROR(n为原顺序表长度)
②判断顺序表的存储空间是否已满,若满则返回ERROR
③将第n个至第i个位置的元素依次向后移动一个位置,空出第i个位置(i = n + 1时无需移动)
④将要插入的新元素e放入第i个位置
⑤表长加一
算法描述
//插入
Status ListInsert(SqList &L, int i, ElemType e)
{ //在顺序表L中第i个位置的新元素e,i值的合法范围是1≤ i ≤L.length + 1
if( (i < 1) || (i > L.length + 1) ) //i值不合法
{
return ERROR;
}
if(L.length == MAXSIZE) //当前存储空间已满
{
return ERROR;
}
for(j = L.length - 1; j >= i - 1; j--)
{
L.elem[j + 1] = L.elem[j]; // 插入位置及之后的元素后移
}
L.elem[i - 1] = e; // 将新元素e放入第i个位置
++L.length; //表长加一
return OK;
}
例
int main(void)
{
int n;
int i; //要插入位置
int e; //要插入的元素
SqList L; // 声明顺序表
Initlist(L); //初始化
get_value(L); // 需要将get_value中的L.size 改为L.size - 1,否则表满,不能插入
printf("初始表:");
for (n = 0; n < L.length; n++)
{
printf("%d", L.elem[n]);
}
printf("\n请输入插入位置(1-10间):");
scanf_s("%d", &i);
printf("请输入插入元素(1-10间):");
scanf_s("%d", &e);
ListInsert(L, i, e); //插入
printf("插入后的表:");
for (n = 0; n < L.length; n++)
{
printf("%d", L.elem[n]);
}
free(L.elem);
return 0;
}
删除
步骤
① 判断删除位置i是否合法(i值的合法范围是1≤i≤n+1),若不合法则返回ERROR(n为原顺序表长度)
②将第i + 1个至第n个位置的元素依次向前移动一个位置,(i = n时无需移动)
③表长减一
算法描述
//删除
Status ListDelete(SqList &L, int i)
{
if( (i < 1) || (i > L.length) ) //i值不合法
{
return ERROR;
}
for(j = i; j < L.length - 1: j++)
{
L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移
}
--L.length; //表长减一
return OK;
}
例文章来源地址https://www.toymoban.com/news/detail-727908.html
int main(void)
{
int n;
int i; //要删除位置
SqList L; // 声明顺序表
Initlist(L); //初始化
get_value(L); // 赋值
printf("初始表:");
for (n = 0; n < L.length; n++)
{
printf("%d", L.elem[n]);
}
printf("\n请输入删除位置(1-10间):");
scanf_s("%d", &i);
ListDelete(L, i); //删除第i个
printf("删除后的表:");
for (n = 0; n < L.length; n++)
{
printf("%d", L.elem[n]);
}
free(L.elem);
return 0;
}
顺序表完
到了这里,关于顺序表创建,初始化,赋值,取值,查找,插入与删除(附小例题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!