线性表的顺序存储C++代码

技术分享 2年前 (2023-03-02) 0 999+

关注

我学习顺序表时找不到相关的代码，以及我不清楚写一个线性表需要的知识，当我写出来可以使用的线性表我就把这些内容贴了出来。

前置知识点：结构体，常量指针，new和delete

顺序表的特点：

需要一片连续的存储空间
逻辑上相连的数据的存储位置也是相邻的。

所以如果我们想要创建一个顺序表我们需要做两件事：

向系统申请一片空间供数组使用。
创建一个指针记录空间地址。

而删除顺序表就是把空间释放,并让指针指向空。

顺序表的创建和销毁：

#include<iostream> #include<cstdlib> #define EleType int//方便日后使用 #define Maxsize 1000 using namespace std;  //定义结构体 struct sql{     int* elem;     int len;//防止越界访问 };   //初始化 void InitList(sql &l) {     l.elem=new int [Maxsize];     if(!l.elem) cout<<"申请空间失败"<<endl;     l.len=0; }  //销毁线性表 void DestroyList(sql &l) {     delete [] l.elem;     l.elem=nullptr; }  int main() {     sql l;     InitList(l);     return 0;  }

数据的插入和删除：

因为在顺序存储所有的数据的存储地址是连续的，所以在插入和删除数据时你需要改变后续的所有数据的位置。在插入时把后面的数据往后挪，删除时把数据向前挪。

void adds(sql &l,EleType target,int sit) {     if(sit>l.len+1 || sit <1)     {         cout<<"sit is wrong"<<endl;//插入位置错误         exit(0);     }     if(l.len+1>Maxsize)     {         cout<<"Too many"<<endl;//存储空间已满         exit(0);     }     //把后面的数据往后挪     for(int i=l.len-1;i>=sit-1;i--)     {         l.elem[i+1]=l.elem[i];     }     l.elem[sit-1]=target;     l.len++;//更新表长 }  //删除元素 void DeletElem(sql &l,int sit) {     if(sit>l.len+1 || sit <1)     {         cout<<"sit is wrong"<<endl;         exit(0);     }     for(int i=sit-1;i<l.len;i++)     {         l.elem[i]=l.elem[i+1];     }     l.len--;//更新表长 }

其他操作：

查找和更改：

//查找 int finding(sql l,EleType target) {     for(int i=0;i<l.len;i++)     {         if(l.elem[i]==target) return i+1;     }     return 0; }  //更改 void Changing(sql& l,int sit,EleType target) {     if(sit>l.len+1 || sit <1)     {         cout<<"sit is wrong"<<endl;         exit(0);     }     l.elem[sit-1]=target; }

清空、获取长度、判断是否为空：

//清空线性表 void ClearLine(sql &l) {     l.len=0; }  //获取线性表的长度 int Getlen(sql l) {     return l.len; }  //判断线性表是否为空 bool IsEmpty(sql l) {     if(l.len==0) return true;     return false; }

完整代码

#include<iostream> #include<cstdlib> #define Maxsize 1000 #define EleType int//方便日后使用 using namespace std;  //创建结构体 struct sql{     EleType* elem;//创建一个指针     int len; };  //初始化 void InitList(sql &l) {         l.elem=new EleType [Maxsize];     if(!l.elem) cout<<"申请空间失败"<<endl;     l.len=0; }   //输出 void print(sql l) {     for(int i=0;i<l.len;i++)     {         cout<<l.elem[i]<<" ";     }     cout<<endl; }  //插入 void adds(sql &l,EleType target,int sit) {     if(sit>l.len+1 || sit <1)     {         cout<<"sit is wrong"<<endl;         exit(0);     }     if(l.len+1>Maxsize)     {         cout<<"Too many"<<endl;         exit(0);     }     for(int i=l.len-1;i>=sit-1;i--)     {         l.elem[i+1]=l.elem[i];     }     l.elem[sit-1]=target;     l.len++; }  //删除元素 void DeletElem(sql &l,int sit) {     if(sit>l.len+1 || sit <1)     {         cout<<"sit is wrong"<<endl;         exit(0);     }     for(int i=sit-1;i<l.len;i++)     {         l.elem[i]=l.elem[i+1];     }     l.len--; }  //销毁线性表 void DestroyList(sql &l) {     delete [] l.elem; }  //清空线性表 void ClearLine(sql &l) {     l.len=0; }  //获取线性表的长度 int Getlen(sql l) {     return l.len; }  //判断线性表是否为空 bool IsEmpty(sql l) {     if(l.len==0) return true;     return false; }  //查找 int finding(sql l,EleType target) {     for(int i=0;i<l.len;i++)     {         if(l.elem[i]==target) return i+1;     }     return 0; }  //更改 void Changing(sql& l,int sit,EleType target) {     if(sit>l.len+1 || sit <1)     {         cout<<"sit is wrong"<<endl;         exit(0);     }     l.elem[sit-1]=target; }  int main() {     sql l;     InitList(l);     EleType j=0;     for(int i=1;i<10;i++,j++)         adds(l,j,i);     DeletElem(l,2);     print(l);     return 0;  }