C++ 顺序表（动态分配）

总结归纳顺序表的定义是线性表的顺序存储即用一组地址连续的存储单元依次存储线性表的数据元素。特点是地址连续所以对于动态分配的顺序表实际上只是申请了一个指针指向该连续地址的首地址要注意与单链表的动态分配进行区分。动态分配对内存有着更大的控制权但也会花费相应的时间。顺序表的查找时间复杂度为O(1)这是单链表所不具备的。顺序表的插入要从后往前遍历因为数据要后移顺序表的删除要从前往后遍历因为数据要前移。代码实现代码语言javascriptAI代码解释/* 顺序表————动态分配 */ #define InitSize 5 // 顺序表初始长度 #include iostream #include stdio.h using namespace std; struct SqList { int *data; // 数组 int MaxSize; // 顺序表的最大长度 int length; // 顺序表的当前长度 }; // 初始化顺序表 void InitList(SqList L) { L.data new int[InitSize]; L.MaxSize InitSize; L.length 0; } // 为顺序表中的数据赋值 void AssginList(SqList L) { for (int i 0; i InitSize; i) { L.data[i] i; L.length; } } // 求表长 int Length(SqList L) { return L.length; } // 动态增加顺序表长度 void IncreaseSize(SqList L, int len) { int *p L.data; L.data new int[L.MaxSize len]; for (int i 0; i L.length; i) { L.data[i] p[i]; // 将原数据赋值到新内存中 } L.MaxSize L.MaxSize len; delete p; } // 按位查找查找第i个位置的元素 int GetElem(SqList L, int i) { return L.data[i - 1]; } // 按值查找查找值为i的元素位置 int LocateElem(SqList L, int i) { for (int j 0; j L.length; j) { if (L.data[j] i) { return j 1; } } return 0; // 没有查找到则返回0 } // 插入在第i个位置插入e void ListInsert(SqList L, int i, int e) { if (L.length L.MaxSize) { // 内存已满需要扩充 IncreaseSize(L, 1); } for (int j L.length; j i; j--) { L.data[j] L.data[j - 1]; // 插入位置之后的数据后移 } L.data[i - 1] e; L.length; } // 删除删除第i个位置的元素 bool ListDelete(SqList L, int i, int e) { if (i 0 || i L.length) { // 删除超出范围 return false; } e L.data[i - 1]; for (int j i; j L.length; j) { L.data[j - 1] L.data[j]; // 数据前移 } L.data[L.length] 0; //最后一个元素初始化 L.length--; return true; } // 按顺序输出 void PrintList(SqList L) { for (int i 0; i L.length; i) { cout L.data[i] ; } cout endl; } int main() { struct SqList L; InitList(L); AssginList(L); PrintList(L); // 求表长 int len Length(L); cout 表长 len endl; // 插入数据 ListInsert(L, 3, 44); Length(L); PrintList(L); // 删除数据 int e -1; if (ListDelete(L, 3, e)) { cout 删除的数据 e endl; PrintList(L); } else { cout 删除数据超出范围 endl; } // 按值查找 int locate_elem; locate_elem LocateElem(L, 3); cout 查找到的位置 locate_elem endl; // 按位查找 int get_elem; get_elem GetElem(L, 3); cout 查找到的数据 get_elem endl; }