⚡️数据结构-第一章
⚡️抽象数据类型案例
⚡️数据结构-第二章（1）-线性结构
⚡️数据结构-第二章（2）-线性表的顺序表示和实现
⚡️数据结构-第二章（3）-顺序表（含代码）
- 数据结构
- 一、顺序表小结
- 二、顺序表案例
- 总结
顺序表的小结
-
①查找、插入、删除的平均算法复杂度为O(n)
-
②空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)
线性表的优缺点
优点:
-
①存储密度大(结点本身所占用的空间/结点结构所占存储量=1)无需为表示表中元素之间的逻辑关系，而增加额外的存储空间
-
②可以随机存取表中任意位置的元素
缺点
-
①插入、删除某一元素需移动大量元素
-
②当线性表长度变化较大时，难以确定存储空间的容量，数据元素的个数不能自由扩充(存储空间不灵活)
#includeusing namespace std; #include #define MAXSIZE 100//预设存储空间最大容量 typedef int ElemType;//给int类型起别名为ElemType，以方便后续更改其它数据类型 typedef struct { int *elem;//存储数组初始地址 int length;//顺序表长度 int listsize; //允许的最大存储容量（以sizeof(ElemType)为单位） }SqList;//typedef给这个结构体类型起名为SqList（顺序表） //界面制作 void showMenu() { cout << "***********************************" << endl; cout << "***** [1]----初始化顺序表----*****" << endl; cout << "***** [2]----求顺序表长度----*****" << endl; cout << "***** [3]----顺序表的判空----*****" << endl; cout << "***** [4]----对顺序表取值----*****" << endl; cout << "***** [5]----顺序表的查找----*****" << endl; cout << "***** [6]----顺序表的插入----*****" << endl; cout << "***** [7]----顺序表的删除----*****" << endl; cout << "***** [8]----对顺序表清空----*****" << endl; cout << "***** [9]----对顺序表销毁----*****" << endl; cout << "***** [0]-----退出顺序表-----*****" << endl; cout << "***********************************" << endl; } void InitList(SqList &L);//1、顺序表的初始化赋值 int GetLength(SqList &L);//2、求线性表L的长度 void IsEmpty(SqList &L);//3、判断线性表L是否为空 void GetElem(SqList &L);//4、顺序表取值 void LocateElem(SqList &L); //5、顺序表的查找 void ListInsert_Sq(SqList &L);//6、顺序表的插入 void ListDelete_Sq(SqList &L);//7、顺序表元素的删除 void ClearList(SqList &L);//8、清空线性表L void DestoryList(SqList &L);//9、销毁线性表 int main() { SqList L; int select = 0;//初始化用户输入变量 while (true) { showMenu(); cout << "请输入您的选择：" << endl; cin >> select; switch (select) { case 0: cout << "退出顺序表" << endl; break; case 1://1、顺序表的初始化赋值 InitList(L); break; case 2: { int list_len = GetLength(L);//2、求线性表L的长度 cout << "线性表当前长度为：" << list_len << endl; break; } case 3: IsEmpty(L);//3、判断线性表L是否为空 break; case 4: GetElem(L);//4、顺序表取值 break; case 5: LocateElem(L); //5、顺序表的查找 break; case 6: ListInsert_Sq(L);//6、顺序表的插入 break; case 7: ListDelete_Sq(L);//7、顺序表元素的删除 break; case 8: ClearList(L);//8、清空线性表L break; case 9: DestoryList(L);//9、销毁线性表 break; default: cout << "无效选项!" << endl; break; } } return 0; } //1、顺序表的初始化赋值 void InitList(SqList &L) { int max_size; cout << "请输入顺序表的最大长度：" << endl; cin >> max_size; if (max_size == 0 || max_size > MAXSIZE) { max_size = MAXSIZE; cout << "顺序表最大长度为：" << max_size << endl; } L.elem = new ElemType[MAXSIZE];//new一块内存，使用elem指针指向它 if (!L.elem) { cout << "内存分配失败" << endl; } cout << "请输入当前顺序表的长度：" << endl; while (true) { cin >> L.length; if (L.length >= 0 && L.length <= max_size) { break; } cout << "输入有误，请重新输入" << endl; } L.listsize = max_size; //该顺序表可以存储元素的最大容量 cout << "请输入当前顺序表的元素: "; for (int i = 0; i < L.length; i++) { cin >> L.elem[i]; } } //2、求线性表L的长度 int GetLength(SqList &L) { return (L.length); } //3、判断线性表L是否为空 void IsEmpty(SqList &L) { if (L.length == 0) { cout << "当前线性表为空" << endl; } else { cout << "当前线性表不为空" << endl; } } //4、顺序表取值 void GetElem(SqList &L) { int i = 0; cout << "请输入要取出的元素位置："; cin >> i; if (i<1 || i>L.length) { cout << "取址位置有误" << endl;//判断i值是否合理，如果不合理，返回error } else { int e = L.elem[i - 1];//下标从0开始 cout << "取出的元素为：" << e << endl; } } //5、顺序表的查找 void LocateElem(SqList &L) { int e = 0; int j = 0; cout << "请输入需要查找的元素" << endl; cin >> e; //在线性表中查找值为e的数据元素，返回其序号（是第几个元素） while (j < L.length && L.elem[j] != e) { ++j; //依次进行判定 } if (j < L.length) { cout << "该顺序表存在此元素，所找元素的位置为：" << j + 1 << "处";//找到满足判定条件的数据元素为第j个元素 } else { cout << "所找的元素不存在"; //该线性表中不存在满足判定的数据元素 } cout << endl; } //6、顺序表的插入 void ListInsert_Sq(SqList &L) { int pos = 0; ElemType e = 0; cout << "请输入要插入的位置："; cin >> pos; cout << "请输入插入的元素："; cin >> e; if (pos<1 || pos>L.length + 1) { cout << "插入不合法" << endl; } if (L.length == MAXSIZE) { cout << "当前存储空间已满，无法插入,请重新选择顺序表功能" << endl; } //从最后一个位置开始，终止条件为所要插入的位置， //如表为：1 2 3 4 5 6 7 8，我要在第4个位置上插入100 //我们从最后一个元素遍历，length是顺序表的长度，现在是8，但下标（序号）是从0开始的，所以-1，即现在为7 //pos是我们选择插入的位置我们选择的是4号位置，但下标任然是从0开始，所以-1，现在是3，终止条件是i=pos的时候 for (int i = L.length - 1; i >= pos - 1; i--) { L.elem[i + 1] = L.elem[i];//将第i个位置上的元素放到i+1位置上 //step:elem[8]=elem[7] } L.elem[pos - 1] = e;//插入的元素赋值到所插入的位置上 //elem[3]=100; ++L.length;//表长+1 cout << "插入后的顺序表长为：" << L.length << endl; cout << "插入后的顺序表为："; for (int i = 0; i < L.length; i++) { cout << L.elem[i] << " "; } cout << endl; } //7、顺序表元素的删除 void ListDelete_Sq(SqList &L) { int pos = 0; cout << "请输入要删除元素的位置："; cin >> pos; if (pos < 1 || pos>L.length) { cout << "删除位置不合法" << endl; } for (int i = pos; i <= L.length - 1; i++) { L.elem[i - 1] = L.elem[i];//被删除元素之后的元素前移 } L.length--; cout << "插入后的顺序表长为：" << L.length << endl; cout << "插入后的顺序表为："; for (int i = 0; i < L.length; i++) { cout << L.elem[i] << " "; } cout << endl; } //8、清空线性表L void ClearList(SqList &L) { L.length = 0; //将线性表的长度置空 cout << "线性表的长度为：" << L.length << endl; cout << "线性表已清空！" << endl; } //9、销毁线性表 void DestoryList(SqList &L) { if (L.elem != NULL) { delete[] L.elem; cout << "顺序表已销毁" << 'n'; } system("pause"); }
简单演示：
*********************************** ***** [1]----初始化顺序表----***** ***** [2]----求顺序表长度----***** ***** [3]----顺序表的判空----***** ***** [4]----对顺序表取值----***** ***** [5]----顺序表的查找----***** ***** [6]----顺序表的插入----***** ***** [7]----顺序表的删除----***** ***** [8]----对顺序表清空----***** ***** [9]----对顺序表销毁----***** ***** [0]-----退出顺序表-----***** *********************************** 请输入您的选择： 1 请输入顺序表的最大长度： 10 请输入当前顺序表的长度： 5 请输入当前顺序表的元素: 15 62 58 98 100 *********************************** ***** [1]----初始化顺序表----***** ***** [2]----求顺序表长度----***** ***** [3]----顺序表的判空----***** ***** [4]----对顺序表取值----***** ***** [5]----顺序表的查找----***** ***** [6]----顺序表的插入----***** ***** [7]----顺序表的删除----***** ***** [8]----对顺序表清空----***** ***** [9]----对顺序表销毁----***** ***** [0]-----退出顺序表-----***** *********************************** 请输入您的选择： 2 线性表当前长度为：5 *********************************** ***** [1]----初始化顺序表----***** ***** [2]----求顺序表长度----***** ***** [3]----顺序表的判空----***** ***** [4]----对顺序表取值----***** ***** [5]----顺序表的查找----***** ***** [6]----顺序表的插入----***** ***** [7]----顺序表的删除----***** ***** [8]----对顺序表清空----***** ***** [9]----对顺序表销毁----***** ***** [0]-----退出顺序表-----***** *********************************** 请输入您的选择： 3 当前线性表不为空 *********************************** ***** [1]----初始化顺序表----***** ***** [2]----求顺序表长度----***** ***** [3]----顺序表的判空----***** ***** [4]----对顺序表取值----***** ***** [5]----顺序表的查找----***** ***** [6]----顺序表的插入----***** ***** [7]----顺序表的删除----***** ***** [8]----对顺序表清空----***** ***** [9]----对顺序表销毁----***** ***** [0]-----退出顺序表-----***** *********************************** 请输入您的选择： 4 请输入要取出的元素位置：4 取出的元素为：98 *********************************** ***** [1]----初始化顺序表----***** ***** [2]----求顺序表长度----***** ***** [3]----顺序表的判空----***** ***** [4]----对顺序表取值----***** ***** [5]----顺序表的查找----***** ***** [6]----顺序表的插入----***** ***** [7]----顺序表的删除----***** ***** [8]----对顺序表清空----***** ***** [9]----对顺序表销毁----***** ***** [0]-----退出顺序表-----***** *********************************** 请输入您的选择： 5 请输入需要查找的元素 10 所找的元素不存在 *********************************** ***** [1]----初始化顺序表----***** ***** [2]----求顺序表长度----***** ***** [3]----顺序表的判空----***** ***** [4]----对顺序表取值----***** ***** [5]----顺序表的查找----***** ***** [6]----顺序表的插入----***** ***** [7]----顺序表的删除----***** ***** [8]----对顺序表清空----***** ***** [9]----对顺序表销毁----***** ***** [0]-----退出顺序表-----***** *********************************** 请输入您的选择： 5 请输入需要查找的元素 15 该顺序表存在此元素，所找元素的位置为：1处 *********************************** ***** [1]----初始化顺序表----***** ***** [2]----求顺序表长度----***** ***** [3]----顺序表的判空----***** ***** [4]----对顺序表取值----***** ***** [5]----顺序表的查找----***** ***** [6]----顺序表的插入----***** ***** [7]----顺序表的删除----***** ***** [8]----对顺序表清空----***** ***** [9]----对顺序表销毁----***** ***** [0]-----退出顺序表-----***** *********************************** 请输入您的选择： 6 请输入要插入的位置：4 请输入插入的元素：10000 插入后的顺序表长为：6 插入后的顺序表为：15 62 58 10000 98 100 *********************************** ***** [1]----初始化顺序表----***** ***** [2]----求顺序表长度----***** ***** [3]----顺序表的判空----***** ***** [4]----对顺序表取值----***** ***** [5]----顺序表的查找----***** ***** [6]----顺序表的插入----***** ***** [7]----顺序表的删除----***** ***** [8]----对顺序表清空----***** ***** [9]----对顺序表销毁----***** ***** [0]-----退出顺序表-----***** *********************************** 请输入您的选择： 7 请输入要删除元素的位置：5 插入后的顺序表长为：5 插入后的顺序表为：15 62 58 10000 100总结
期待大家和我交流，留言或者私信，一起学习，一起进步！
