线性表的顺序存储—

前言

这篇文章是整理了关于线性表的基本操作，运用线性表的顺序存储。

主要是用C语言实现，但是也涉及了部分C++中的内容。

线性表的主要操作有：

InitList(&L)：初始化表。构造一个空的线性表。

Length(L)：求表长。返回线性表L的长度，即表中数据元素的个数。

DestoryList(&L)：销毁表。销毁线性表并释放其所占用的内存空间。

LocateElem(L,e)：按值查找。

GetElem(L,i)：按位查找。获取线性表中第i个位置的元素。

ListInsert(&L,i,e)：插入。在线性表的第i个位置插入元素e。

ListDelete(&L,i,&e)：删除。删除线性表中第i个位置的元素，并将其值用e返回。

isEmpty(L)：判断空表。若表为空，返回true；反之返回false。

PrintList(L)：输出。按前后顺序输出线性表L的所有元素值。

线性表的顺序表示

线性表的顺序存储也称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

静态分配顺序表的存储结构

//线性表的顺序存储，利用数组
typedef struct{
int data[MaxSize]; //顺序表的数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的静态分配方式；Sq指sequence——顺序，次序

整体代码

//2025.3.15 写下，线性表的顺序表示 
#include<iostream>
#define MaxSize 10
#define ElemError 99999 //设置一个特殊数当作按位置查找失败的标志 using namespace std;int op = 0; //用来记录操作数 
//线性表的顺序存储，利用数组 
typedef struct{int data[MaxSize];  //顺序表的数据元素int length;         //顺序表的当前长度 
}SqList; //顺序表的静态分配方式；Sq指sequence——顺序，次序//初始化顺序表
void InitList(SqList &L){L.length = 0;    //初始化当前顺序表的长度为0 
} 
//创建顺序表
void CreateList(SqList &L,int n){int i=0;printf("请依次输入元素值：\n");for(i=0;i<n;i++){scanf("%d",&L.data[i]);L.length++; //顺序表的长度自增一 }
}
//遍历顺序表 
bool traList(SqList L){int i=0;if(L.length==0){printf("该表为空表，无法遍历！\n"); return false;}printf("顺序表的遍历如下：\n");for(i=0;i<L.length;i++){printf("%d\t",L.data[i]);}cout << endl; //在C++中的换行 return true;
}
//插入操作
bool ListInsert(SqList &L,int location,int e){int i=0;if(location<1 || location>L.length+1) //判断要插入的位置是否合法{printf("插入位置不合法！\n"); return false;}for(i=L.length-1;i>=location-1;i--) //插入第location个位置，对应的下标为location-1{L.data[i+1] = L.data[i];} L.data[location-1] = e;L.length++; //顺序表长度加一 return true;
}
//删除操作
bool ListDelete(SqList &L,int location,int &e){int i=0;if(location<1 || location>L.length) //判断要删除的位置是否合法{printf("删除位置不合法！\n"); return false;}	e = L.data[location-1]; for(i=location-1;i<L.length-1;i++) //插入第location个位置，对应的下标为location-1{L.data[i] = L.data[i+1];} L.length--; //顺序表长度减一 return true;
}
//按值查找,返回的是第一个查找到的值对应的位置 
int LocateElem(SqList L,int e){int i=0;for(i=0;i<L.length;i++){if(L.data[i] == e) return i+1; //下标为i的元素，返回其位序i+1 }return 0; //查找失败 
}
//按位查找，返回的是位置对应的元素值,设置一个不常用的值表示查找错误 
int GetElem(SqList L,int location){int i=0;if(location<1 || location>L.length) //判断要查找的位置是否合法{printf("查找位置不合法！\n"); return ElemError;}return L.data[location-1]; 
}int main(){SqList L; //声明一个顺序表L，系统已经为它开辟了一整片连续的内存空间InitList(L); //初始化顺序表 int n=0,i=0,e=0; //n用来接收要输入的元素的个数，i用来接收元素位置，e接收元素值 while(op!=-1){printf("\n-----------操作目录-----------\n");printf("1.创建顺序表\n"); printf("2.遍历顺序表\n"); printf("3.插入新元素\n"); printf("4.删除元素\n"); printf("5.按值查找\n"); printf("6.按位查找\n"); printf("输入 -1 退出操作\n"); scanf("%d",&op);switch(op){case 1: printf("要输入元素的个数：\n"); //创建顺序表scanf("%d",&n);CreateList(L,n);break; case 2: traList(L);break; //遍历顺序表case 3:  //插入新元素if(L.length == MaxSize) //先判断是否能进行插入操作{printf("顺序表已满！\n");break;}printf("请输入要插入的新元素的位置和值：\n");scanf("%d %d",&i,&e);ListInsert(L,i,e);break;case 4:  //删除元素if(L.length==0) //若为空表{printf("顺序表为空！\n");break;}printf("请输入要删除的元素的位置：\n");scanf("%d",&i);if(ListDelete(L,i,e) == false) break;else{printf("要删除的元素的值：%d\n",e);break;}case 5: printf("请输入要查找的元素值：\n"); //按值查找scanf("%d",&e);i = LocateElem(L,e);if(i == 0){printf("查找失败！\n");}else{printf("值为%d的元素所在的位置为%d\n",e,i);}break;case 6: printf("请输入要查找的位置号：\n"); //按位查找scanf("%d",&i);e = GetElem(L,i);\if(e != ElemError)printf("位置号为%d对应的元素值为%d\n",i,e);break;}}return 0;
}