前言
这篇文章是整理了关于线性表的基本操作,运用线性表的顺序存储。
主要是用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;
}
在这上面的代码中,不包括求表长、判断空表以及销毁操作。 但是对于顺序表的静态分配内存的方式来说,不需要销毁操作,因为此程序运行完毕后,会自动释放占有的内存空间 。
将求表长和判断空表的操作单独写在下面。
求表长
int Length(SqList L){
return L.length;
}
判断是否空表
bool isEmpty(SqList L){
if(L.length == 0) return true;
else return false;
}
如果有错误,请在评论区指出,感谢~~