线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。
线性表的顺序存储结构,实际上就是在内存中找一块连续的存储空间,然后将相同数据类型的数据元素存储在这块存储空间中。所以用C语言中的一维数组就可以实现顺序存储结构。
线性表的顺序存储结构优点在于可以快速随机访问表中任意位置的元素,并且因为其占用的一段连续的存储空间,所以不需要为表示元素之间的逻辑关系来增加额外的存储空间节省空间(相对) 。
而线性表的顺序存储结构的缺点就在于插入和删除操作需要移动大量元素,执行效率低,并且数组的容量需要提前确定,因此可能造成空间浪费。
线性表的基本结构:
typedef struct{
ElemType data[MAX];
int length;
}SqList;
准备工作:
#include<stdio.h>
#define MAX 20
//数组的最大长度
#define OK 1
#define error 0
//OK和error代表函数状态,分别为1(函数成功运行),0(函数出错)
typedef int Status;
//Status是函数类型,其值是函数结果状态代码,如OK代表成功,error代表出错。
typedef int ElemType;
//ElemType代表数组类型,根据实际情况确定,这里假设为int型
线性表的顺序存储结构的8种基本操作:
下面给出具体分析:
线性表的初始化:
即将线性表的长度赋值为0
Status initList(SqList *L){
L->length = 0;
return OK;
}
判断线性表是否为空:
这里我稍微做了一点改进,直接用bool返回线性表为空的真假:
长度为真,返回 true。
长度为假,返回 false。
//判断线性表是否为空
bool ListEmpty(SqList L){
if(L.length == 0)
return true;
else
return false;
}
清空线性表:
与初始化一样,将线性表的长度置为0。
Status ClearList(SqList *L){
L->length = 0;
return OK;
}
返回线性表的给定位置元素值:
1.首先判断该元素是否合理
2.然后将该位置元素的值赋值给e。
(因为要保留e的值,不能使e所占内存空间在函数调用完成后自动释放,所以这里采用指针)
Status GetElem(SqList L,int i,ElemType *e){
if(i < 1 || i > L.length || L.length == 0)
return error;
*e = L.data[i-1];
return OK;
}
插入元素:
1.判断限制条件,如果线性表已满,插入位置不合理,则插入失败。
2.如果是在最后一个位置,直接赋值即可
3.如果不在最后一个位置,从最后一个位置开始,全部后移一位。
4.长度加一,给即将插入的元素赋值
PS:因为数组是从0开始计数的,所以对应线性表的位置,永远减一
线性表改变,所以需要传指针。
//插入操作:在 L中的第 i 个位置插入新元素 e
Status ListInsert(SqList *L,int i,ElemType e){
if(L.length == MAX)
return error;
//判断线性表长度是否大于数组长度
if(i < 1 || i > L.length + 1)
return error;
//判断插入位置是否合理
if(i <= L.length){
for(int k = L.length - 1;k >= i - 1;k--)
L->data[k+1] = L->data[k];
//如果插入位置不在表的末尾,则从线性表的最后一个位置开始,所有元素向后移动一位
//一直到插入位置的前一个元素
}
L.length++;
L->data[i-1] = e;
//长度加一,为新插入的元素赋值
}
删除元素:
1.先判断删除位置是否合理,具体如上。
2.将要删除的元素的值赋值给e。
3.如果是在最后一个位置,直接删除即可
4.如果不在最后一个位置,从该位置的后一位开始,全部前移一位。
4.长度减一,给即将插入的元素赋值
PS:因为数组是从0开始计数的,所以对应线性表的位置,永远减一。线性表改变,所以需要传指针。需要获得e的值,e也要传指针。
//删除操作:删除 L 的第一个数据元素,并用 e返回其值
Status ListDelete(SqList *L,int i,ElemType *e){
if(L->length == 0)
return error;
if(i < 1 || i > length)
return error;
*e = L->data[i-1];
if(i < L->length){
for(int k = i; k < L->length ;k++){
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
}
查找元素:
1.线性表长度为0,查找失败
2.遍历数组,成功则返回其在线性表中的位置
Status LocateElem(SqList L,ElemType e){
if(L.length == 0)
return 0;
for(int i = 0;i < L.length;i++){
if(e == L.data[i])
return i + 1;
}
return 0;
}
合并两个线性表(将Lb中的元素插入La):
1.遍历Lb中数组,得到第i个位置对应元素的值,赋与e。
2.如果La中没有对应的元素,将e的值插入到La的最后一个位置。
3.La长度加一。
//合并两个数组
Status ListUnion(SqList *La,SqList Lb){
ElemType e;
int La_len = La->length;
int Lb_len = Lb.length;
for(int i = 1 ; i <= Lb_len ; i++){
GetElem(Lb,i,&e);
if(!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}
完整代码实现(加入测试):
#include<stdio.h>
#define MAX 20
//数组的最大长度
#define OK 1
#define error 0
typedef int Status;
//Status是函数类型,其值是函数结果状态代码,如OK代表成功,error代表出错。
typedef int ElemType;
//ElemType代表数组类型,根据实际情况确定,这里假设为int型
typedef struct{
ElemType data[MAX];
int length;
}SqList;
//初始化线性表
Status initList(SqList *L){
L->length = 0;
return OK;
}
//判断线性表是否为空
bool ListEmpty(SqList L){
if(L.length == 0)
return true;
else
return false;
}
//输出数组数据
void ListTraverse(SqList L){
for(int i = 0; i < L.length; i++)
printf("%d ",L.data[i]);
printf("\n");
}
//清空线性表
Status ClearList(SqList *L){
L->length = 0;
return OK;
}
//用e返回L中第 i个数据元素的值
Status GetElem(SqList L,int i,ElemType *e){
if(i < 1 || i > L.length || L.length == 0)
return error;
*e = L.data[i-1];
return OK;
}
//查找元素 e
Status LocateElem(SqList L,ElemType e){
if(L.length == 0)
return 0;
for(int i = 0;i < L.length;i++){
if(e == L.data[i])
return i + 1;
}
return 0;
}
//插入操作:在 L中的第 i 个位置插入新元素 e
Status ListInsert(SqList *L,int i,ElemType e){
if(L->length == MAX)
return error;
//判断线性表长度是否大于数组长度
if(i < 1 || i > L->length + 1)
return error;
//判断插入位置是否合理
if(i <= L->length){
for(int k = L->length - 1;k >= i - 1;k--)
L->data[k+1] = L->data[k];
//如果插入位置不在表的末尾,则从线性表的最后一个位置开始,所有元素向后移动一位
//一直到插入位置的前一个元素
}
L->length++;
L->data[i-1] = e;
//长度加一,为新插入的元素赋值
}
//删除操作:删除 L 的第一个数据元素,并用 e返回其值
Status ListDelete(SqList *L,int i,ElemType *e){
if(L->length == 0)
return error;
if(i < 1 || i > L->length)
return error;
*e = L->data[i-1];
if(i < L->length){
for(int k = i; k < L->length ;k++){
L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;
}
//合并两个数组
Status ListUnion(SqList *La,SqList Lb){
ElemType e;
int La_len = La->length;
int Lb_len = Lb.length;
for(int i = 1 ; i <= Lb_len ; i++){
GetElem(Lb,i,&e);
if(!LocateElem(*La,e))
ListInsert(La,La_len++,e);
}
}
int main(){
SqList L,Lb;
ElemType e;
Status r;
r = initList(&L);
int k;
printf("初始化L后,L.length = %d\n",L.length);
for(int i = 1; i <= 5 ; i++){
r = ListInsert(&L,1,i);
}
printf("在L的表头依次插入1-5后:L.data = ");
ListTraverse(L);
printf("L.length = %d\n",L.length);
if(ListEmpty(L))
printf("L为空\n");
else
printf("L不为空\n");
r = ClearList(&L);
printf("清空L后,L.length = %d\n",L.length);
if(ListEmpty(L))
printf("L为空\n");
else
printf("L不为空\n");
for(int i = 1; i <= 10 ; i++){
ListInsert(&L,i,i);
}
printf("在L的表头插入1-10后,L.data = ");
ListTraverse(L);
printf("L.length = %d\n",L.length);
ListInsert(&L,1,0);
printf("在L的表头插入0后:L.data= ");
ListTraverse(L);
printf("L.length=%d\n",L.length);
GetElem(L,5,&e);
printf("第5个元素的值为:%d\n",e);
for(int i = 3;i <= 4; i++){
r = LocateElem(L,i);
if(r == 0)
printf("没有值为%d的元素\n",r);
else
printf("第%d个元素的值为:%d\n",r,i);
}
k = L.length;
for(int i = k + 1 ; i >= k ;i--){
r = ListDelete(&L,i,&e);
if(r == error)
printf("删除第%d个元素失败!\n",i);
else
printf("删除第%d个元素的值为%d\n",i,e);
}
printf("依次输出L的元素: ");
ListTraverse(L);
r = 5;
ListDelete(&L,r,&e);
printf("删除第%d个元素的值为%d\n",r,e);
printf("依次输出L的元素: ");
ListTraverse(L);
r = initList(&Lb);
for(int i = 6;i <= 15; i++){
r = ListInsert(&Lb,1,i);
}
ListUnion(&L,Lb);
printf("依次输出合并了Lb的L的元素:");
ListTraverse(L);
return 0;
}
第一次发布博客,有问题还望大家指出。
(水平菜的一批,哈哈)
【排序算法】之lowb三人组冒泡、插入、选择 什么是lowb三人组 冒泡排序bubble so...
计算属性computed: 支持缓存,只有依赖数据发生改变,才会重新进行计算 不支持...
前言 相信大家都知道在IDE中代码的智能提示几乎都是标配,虽然一些文本编辑器也...
ADO对象: Connection Command Recordset Record Stream ASP支持的对象很多,可...
一石激起千层浪,继中国区浩浩荡荡的大裁员告一段落之后,甲骨文并未因此收起手...
vbs:把一段文字中指定字符颜色变成红色的正则 functionc(Tstr,Word) Dimre Setre...
一、正则表达式概述 二、正则表达式在VBScript中的应用 三、正则表达式在VavaScr...
微信文件传输助手是微信电脑版与手机微信之间相互传输图片等文件的好工具,但很...
本文将研究 ES6 的 for ... of 循环。 旧方法 在过去,有两种方法可以遍历 javas...
歌词编辑器 歌词编辑器 第一步:选择要播放的歌曲并播放 第二步:填写全部的歌词...