本文主要是介绍C++实现数据结构入门01——顺序存储实现线性表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
参考书:《数据结构》C语言版(第2版)
一、初始化
1.简写初始化
#include <iostream>using namespace std;int main(){//==============01准备工作=============//创建数组const int MAXSIZE = 100;//设置数据的长度 int arr[MAXSIZE] = {};//开辟100个整型的数组空间。 int length = 0;//存储线性表有多少个元素 return 0;
}
2.规范化初始化
2.1将经常操作的数据,存储到结构体里。
#include <iostream>using namespace std;//存储顺序表的相关数据,整合到一个结构体里
struct SqList{const int MAXSIZE = 100; //1.顺序表可能达到的最大长度 int * p;//2.保存存储空间的首地址(数组变量是一个地址)int length;//3.存储线性表有多少个元素
};int main(){SqList st;//创建一个结构体对象}
2.2初始化
【算法步骤】
①为数组L动态分配一个预定义大小的数据空间,使p指向这段空间的基地址。
②将表的当前长度设为0。
#include <iostream>using namespace std;//存储顺序表的相关数据,整合到一个结构体里
struct SqList{const int MAXSIZE = 100; //1.顺序表可能达到的最大长度 int * p;//2.保存存储空间的首地址(数组变量是一个地址)int length;//3.存储线性表有多少个元素
};//初始化方法
void InitSqList(SqList &L){//这里使用的是引用,表示处理的是原数据 L.p = new int[L.MAXSIZE];//初始化数组的大小(使用new,在堆内存创建) L.length = 0;//初始化数组的当前长度。 } int main(){SqList st;//创建一个结构体对象InitSqList(st);//初始化}
二、取值
取出第i个数据(这里的i是从0开头的i,对应数组中的i-1号位的数据)
【算法步骤】
①判断指定位置序号i值是否合理(1<=i<=L.length),若不合适,则返回false。
②若i值合理,则将第i个数据元素L.p[i-1]赋值给参数e,通过e返回第i个数据元素的传值。
#include <iostream>using namespace std;//存储顺序表的相关数据,整合到一个结构体里
struct SqList{const int MAXSIZE = 100; //1.顺序表可能达到的最大长度 int * p;//2.保存存储空间的首地址(数组变量是一个地址)int length;//3.存储线性表有多少个元素
};//初始化方法
void InitSqList(SqList &L){//这里使用的是引用,表示处理的是原数据 L.p = new int[L.MAXSIZE];//初始化数组的大小(使用new,在堆内存创建) L.length = 0;//初始化数组的当前长度。 } //取值(取第i号位的数据)
bool GetElem(SqList L,int i,int &e){//e储存查到的数据,使用引用,更改源数据。 L引不引用无所谓。 if(i<1 || i>= L.length ){//判断索引是否是有效范围 return false;}e = L.p[i-1];return true;
} int main(){SqList st;//创建一个结构体对象InitSqList(st);//初始化//赋值测试数据for(int i=0;i<10;i++){st.p[i] = i; } st.length = 10;//更改完数据,别忘了记录有效长度。 //测试 取值 int ee;//接受数据 bool r = GetElem(st,5,ee);//测试数据可以尝试0,1,5,11等 if(r) {cout << "取值结果:"<< ee << endl; }else{cout << "取值失败" << endl; }}
三、查找
根据值找到是几号位。
【算法步骤】
①从第一个元素起,依次和e相比较,若找到与e相等的元素L.p[i],则查找成功,返回该元素的序号i+1。
②若查找整个顺序表都没有找到,则找到失败,返回0。
#include <iostream>using namespace std;//存储顺序表的相关数据,整合到一个结构体里
struct SqList{const int MAXSIZE = 100; //1.顺序表可能达到的最大长度 int * p;//2.保存存储空间的首地址(数组变量是一个地址)int length;//3.存储线性表有多少个元素
};//初始化方法
void InitSqList(SqList &L){//这里使用的是引用,表示处理的是原数据 L.p = new int[L.MAXSIZE];//初始化数组的大小(使用new,在堆内存创建) L.length = 0;//初始化数组的当前长度。 } //取值(取第i号位的数据)
bool GetElem(SqList L,int i,int &e){//e储存查到的数据,使用引用,更改源数据。 L引不引用无所谓。 if(i<1 || i>= L.length ){//判断索引是否是有效范围 return false;}e = L.p[i-1];return true;
}
//查找(根据数据查找第几号位)
int GetIndex(SqList L,int e){//e储存查到的数据,使用引用,更改源数据。 L引不引用无所谓。 for(int i=0;i<L.length;i++){if(L.p[i]==e){return i+1;//循环结束,代表没查找到数据。}}return 0;//循环结束,代表没查找到数据。
} int main(){SqList st;//创建一个结构体对象InitSqList(st);//初始化//赋值测试数据for(int i=0;i<10;i++){st.p[i] = i; } st.length = 10;//更改完数据,别忘了记录有效长度。 //测试 查找 int r = GetIndex(st,8);//查找数字8所在的位置 if(r!=0) {cout << "查找结果:"<< r << endl; }else{cout << "取值失败" << endl; }}
四、插入
【算法步骤】
①判断插入位置i是否合法(i的合法范围是1<=i<=L.length+1),若不合法则返回false。
②判断顺序表的存储空间是否已满,若满则返回false。
③将第L.length-1号位 到 i-1号位的元素一次向后移动一个位置,空出第i-1号位置。
④将要插入的新元素e放入第i-1号位。
⑤表长加1。
#include <iostream>using namespace std;//存储顺序表的相关数据,整合到一个结构体里
struct SqList{const int MAXSIZE = 100; //1.顺序表可能达到的最大长度 int * p;//2.保存存储空间的首地址(数组变量是一个地址)int length;//3.存储线性表有多少个元素
};//初始化方法
void InitSqList(SqList &L){//这里使用的是引用,表示处理的是原数据 L.p = new int[L.MAXSIZE];//初始化数组的大小(使用new,在堆内存创建) L.length = 0;//初始化数组的当前长度。 } //取值(取第i号位的数据)
bool GetElem(SqList L,int i,int &e){//e储存查到的数据,使用引用,更改源数据。 L引不引用无所谓。 if(i<1 || i>= L.length ){//判断索引是否是有效范围 return false;}e = L.p[i-1];return true;
}
//查找(根据数据查找第几号位)
int GetIndex(SqList L,int e){//e储存查到的数据,使用引用,更改源数据。 L引不引用无所谓。 for(int i=0;i<L.length;i++){if(L.p[i]==e){return i+1;//循环结束,代表没查找到数据。}}return 0;//循环结束,代表没查找到数据。
} //插入(注意i是从1开头,和数据的索引要对应一下)
bool ListInsert(SqList &L,int i,int e){//判断位置是否合法(1<i<n+1),这里的i是1开头的i if (i<1 || i>L.length+1 ){//插入到列表末尾也是可以的 return false; }//判断空间是否已满if(L.length==L.MAXSIZE){return true;}//程序:将第i-1号位到n-1号位,往后挪一个 for(int j=L.length-1;j>i-2;j--){L.p[j+1] = L.p[j];}L.p[i-1] = e;L.length = L.length + 1;return true;
} int main(){SqList st;//创建一个结构体对象InitSqList(st);//初始化//赋值测试数据for(int i=0;i<10;i++){st.p[i] = i; } st.length = 10;//更改完数据,别忘了记录有效长度。 //插入测试bool a = ListInsert(st,5,100);if(a){//遍历出所有数据,查看结果 for(int i=0;i<st.length;i++){cout << st.p[i] << endl; } } else{cout << "插入失败" << endl; }}
五、删除
【算法步骤】
①判断删除位置i是否合法(i的合法范围是1<=i<=L.length),若不合法则返回false。
②将第 i号位 到 L.length-1号位的元素一次向前移动一个位置。
④将要插入的新元素e放入第i-1号位。
⑤表长减1。
#include <iostream>using namespace std;//存储顺序表的相关数据,整合到一个结构体里
struct SqList{const int MAXSIZE = 100; //1.顺序表可能达到的最大长度 int * p;//2.保存存储空间的首地址(数组变量是一个地址)int length;//3.存储线性表有多少个元素
};//初始化方法
void InitSqList(SqList &L){//这里使用的是引用,表示处理的是原数据 L.p = new int[L.MAXSIZE];//初始化数组的大小(使用new,在堆内存创建) L.length = 0;//初始化数组的当前长度。 } //取值(取第i号位的数据)
bool GetElem(SqList L,int i,int &e){//e储存查到的数据,使用引用,更改源数据。 L引不引用无所谓。 if(i<1 || i>= L.length ){//判断索引是否是有效范围 return false;}e = L.p[i-1];return true;
}
//查找(根据数据查找第几号位)
int GetIndex(SqList L,int e){//e储存查到的数据,使用引用,更改源数据。 L引不引用无所谓。 for(int i=0;i<L.length;i++){if(L.p[i]==e){return i+1;//循环结束,代表没查找到数据。}}return 0;//循环结束,代表没查找到数据。
} //插入(注意i是从1开头,和数据的索引要对应一下)
bool ListInsert(SqList &L,int i,int e){//判断位置是否合法(1<i<n+1),这里的i是1开头的i if (i<1 || i>L.length+1 ){//插入到列表末尾也是可以的 return false; }//判断空间是否已满if(L.length==L.MAXSIZE){return true;}//程序:将第i-1号位到n-1号位,往后挪一个 for(int j=L.length-1;j>i-2;j--){L.p[j+1] = L.p[j];}L.p[i-1] = e;L.length = L.length + 1;return true;
}
//删除(根据序号删除内容)
bool ListDelete(SqList &L,int i){//判断位置是否合法(1<i<n+1),这里的i是1开头的i if (i<1 || i>L.length ){//插入到列表末尾也是可以的 return false; }//程序:将第i号位到n-1号位,往前挪一个 for(int j=i;j<L.length;j++){L.p[j-1] = L.p[j];}L.length = L.length - 1;return true;
} int main(){SqList st;//创建一个结构体对象InitSqList(st);//初始化//赋值测试数据for(int i=0;i<10;i++){st.p[i] = i; } st.length = 10;//更改完数据,别忘了记录有效长度。 //删除测试bool a = ListDelete(st,5);//删除第5号位置 if(a){for(int i=0;i<st.length;i++){cout << st.p[i] << endl; } } else{cout << "删除失败" << endl; }}
这篇关于C++实现数据结构入门01——顺序存储实现线性表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!