数据结构(C++版)实现顺序表的创建，输入，输出，插入，删除，取值
- 顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
- 顺序表存储结构(顺序结构)
将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。
- 顺序表的特点
只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素占用存储单元的长度。
1.编译运行
2.代码块
- 顺序表的存储结构
typedefstruct { //存储空间的基址 ElemType*elem; //当前长度 intlength; }SqList; //顺序表的结构类型为SqList
- 顺序表初始化
StatusinitList(SqList&L){ //构造一个空的顺序表L //为顺序表分配一个大小为MAXSIZE的数组空间 L.elem=newElemType[MAXSIZE]; //存储分配失败返回Error if(!L.elem) returnError; //空表长度为0 L.length=0; returnOk; }
- 顺序表的取值
StatusGetElem(SqListL,inti,ElemType&e){ //判断i值是否合理，若不合理，返回Error if(i<1||i>L.length) returnError; //elem[i-1]单元存储顺序表第i个元素 e=L.elem[i-1]; returnOk; }
- 顺序表的查找
intLocateElem(SqListL,ElemTypee){ //在顺序表L中查早值为e的数据元素，返回其下标 for(inti=0;i<L.length;i++){ //查找成功返回下标i+1 if(L.elem[i]==e) returni+1; } //查找失败返回0 return0; }
- 顺序表的插入
StatusListInsert(SqList&L,inti,ElemTypee){ //在顺序表L中第i个位置插入新的元素e,i的合法范围是1<=i<=L.length+1;//i的值不合法返回Error if(i<1||i>L.length+1) returnError; //当前存储空间已满 if(L.length==MAXSIZE) returnError; //插入位置及以后的元素后移 for(intj=L.length-1;j>=i-1;j--){ L.elem[j+1]=L.elem[j]; } //将新元素e放入第i个位置 L.elem[i-1]=e; //表长加1 L.length++; returnOk; }
- 顺序表的删除
StatusListInsert(SqList&L,inti){ //在顺序表L中删除第i个元素，i的合法取值范围是1<=i<=L.length//i的值不合法 if(i<1||i>L.length) returnError; for(intj=i-1;j<L.length;j++){ //被删除元素之后的元素前移 L.elem[j]=L.elem[j+1]; } //表长-1 L.length--; returnOk; }
- 顺序表输出
voidprintList(SqListL){ for(inti=0;i<L.length;i++){ cout<<L.elem[i]<<" "; } cout<<endl; }
- 顺序表输入
StatusinListValue(SqList&L,intn){ if(n<0||n>MAXSIZE) returnError; if(L.length==MAXSIZE) returnError; for(inti=0;i<n;i++){ L.elem[i]=rand(); L.length++; } returnOk; }
3.源码
#include<iostream>#include<stdlib.h>usingnamespacestd; //顺序表可能达到的最大长度 #defineMAXSIZE100#defineError0#defineOk1typedefintElemType; typedefintStatus; //顺序表的存储结构 typedefstruct { //存储空间的基址 ElemType*elem; //当前长度 intlength; }SqList; //顺序表的结构类型为SqList//顺序表初始化StatusinitList(SqList&L){ //构造一个空的顺序表L //为顺序表分配一个大小为MAXSIZE的数组空间 L.elem=newElemType[MAXSIZE]; //存储分配失败返回Error if(!L.elem) returnError; //空表长度为0 L.length=0; returnOk; } //顺序表的取值StatusGetElem(SqListL,inti,ElemType&e){ //判断i值是否合理，若不合理，返回Error if(i<1||i>L.length) returnError; //elem[i-1]单元存储顺序表第i个元素 e=L.elem[i-1]; returnOk; } //顺序表的查找intLocateElem(SqListL,ElemTypee){ //在顺序表L中查早值为e的数据元素，返回其下标 for(inti=0;i<L.length;i++){ //查找成功返回下标i+1 if(L.elem[i]==e) returni+1; } //查找失败返回0 return0; } //顺序表的插入StatusListInsert(SqList&L,inti,ElemTypee){ //在顺序表L中第i个位置插入新的元素e,i的合法范围是1<=i<=L.length+1;//i的值不合法返回Error if(i<1||i>L.length+1) returnError; //当前存储空间已满 if(L.length==MAXSIZE) returnError; //插入位置及以后的元素后移 for(intj=L.length-1;j>=i-1;j--){ L.elem[j+1]=L.elem[j]; } //将新元素e放入第i个位置 L.elem[i-1]=e; //表长加1 L.length++; returnOk; } //顺序表的删除StatusListInsert(SqList&L,inti){ //在顺序表L中删除第i个元素，i的合法取值范围是1<=i<=L.length//i的值不合法 if(i<1||i>L.length) returnError; for(intj=i-1;j<L.length;j++){ //被删除元素之后的元素前移 L.elem[j]=L.elem[j+1]; } //表长-1 L.length--; returnOk; } //顺序表输出voidprintList(SqListL){ for(inti=0;i<L.length;i++){ cout<<L.elem[i]<<" "; } cout<<endl; } //顺序表输入StatusinListValue(SqList&L,intn){ if(n<0||n>MAXSIZE) returnError; if(L.length==MAXSIZE) returnError; for(inti=0;i<n;i++){ L.elem[i]=rand(); L.length++; } returnOk; } intmain(){ inte,n,x,y; cout<<"正在初始化顺序表......"<<endl; SqListL; initList(L); cout<<"-------顺序表初始化成功--------"<<endl; cout<<"-------顺序表随机赋值多少个元素:--------"<<endl; cin>>n; inListValue(L,n); cout<<"-------顺序表随机赋值完成:"<<endl; printList(L); cout<<"顺序表要获取元素值的序号为:"<<endl; cin>>n; GetElem(L,n,e); cout<<"获取的元素值为："<<e<<endl; cout<<"-------顺序表插入元素--------"<<endl; cout<<"要插入的位置:"<<endl; cin>>n; cout<<"要插入的元素:"<<endl; cin>>e; ListInsert(L,n,e); cout<<"顺序表插入完成......"<<endl; cout<<"插入之后的顺序表："<<endl; printList(L); cout<<"-------顺序表删除元素--------"<<endl; cout<<"删除元素的位置"<<endl; cin>>n; ListInsert(L,n); cout<<"顺序表删除完成......"<<endl; cout<<"删除之后的顺序表："<<endl; printList(L); return0; }
