数组广义表

提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档数组Array详解数组是由相同类型的数据元素组成的有序集合存储在连续内存中。多维数组可以看作“数组的数组”。核心特点元素同构类型一致大小固定创建后不可变随机访问下标访问时间复杂度为 O(1)物理空间连续存储C 示例#include iostream using namespace std; int main() { // 一维数组 int a[5] {1, 2, 3, 4, 5}; // 二维数组 int b[2][3] {{1, 2, 3}, {4, 5, 6}}; cout 一维数组; for (int i 0; i 5; i) cout a[i] ; cout endl; cout 二维数组\n; for (int i 0; i 2; i) { for (int j 0; j 3; j) cout b[i][j] ; cout endl; } return 0; }广义表Generalized List详解广义表是 n 个元素的有限序列LS (a₁, a₂, …, aₙ)。元素可以是原子不可再分或子表另一个广义表。重要概念长度最外层元素个数深度括号最大嵌套层数表头 Head第一个元素表尾 Tail除表头外剩余元素组成的表核心特点元素异构原子 子表支持递归嵌套动态结构长度深度可变采用链式存储广义表完整 C 实现结构定义#include iostream using namespace std; // 节点类型原子 / 子表 enum Type { ATOM, LIST }; // 广义表节点 struct GLNode { Type type; union { int data; // 原子 GLNode* sub; // 子表 } val; GLNode* next; // 下一个兄弟 // 原子节点 GLNode(int d) : type(ATOM), next(nullptr) { val.data d; } // 子表节点 GLNode(GLNode* s) : type(LIST), next(nullptr) { val.sub s; } };打印广义表void printGL(GLNode* p) { if (!p) return; if (p-type ATOM) { cout p-val.data ; } else { cout ( ; printGL(p-val.sub); cout ) ; } printGL(p-next); }求长度int length(GLNode* p) { if (!p) return 0; return 1 length(p-next); }求深度int depth(GLNode* p) { if (!p) return 1; if (p-type ATOM) return 0; int maxD depth(p-val.sub); for (GLNode* q p-next; q; q q-next) { int d (q-type ATOM) ? 0 : depth(q-val.sub); if (d maxD) maxD d; } return maxD 1; }复制广义表GLNode* copyGL(GLNode* p) { if (!p) return nullptr; GLNode* newNode; if (p-type ATOM) { newNode new GLNode(p-val.data); } else { newNode new GLNode(copyGL(p-val.sub)); } newNode-next copyGL(p-next); return newNode; }销毁广义表void destroy(GLNode* p) { if (!p) return; if (p-type LIST) destroy(p-val.sub); // 递归销毁子表 GLNode* q p-next; delete p; p nullptr; destroy(q); // 销毁下一个节点 }取表头GLNode* getHead(GLNode* p) { if (!p) return nullptr; GLNode* head nullptr; if (p-type ATOM) head new GLNode(p-val.data); else head new GLNode(copyGL(p-val.sub)); return head; }取表尾GLNode* getTail(GLNode* p) { if (!p) return nullptr; return copyGL(p-next); // 表尾 除第一个外的所有元素 }主函数测试int main() { // 构造LS (10, (20,30), 40, ((50))) GLNode* n50 new GLNode(50); GLNode* sub50 new GLNode(n50); GLNode* n20 new GLNode(20); n20-next new GLNode(30); GLNode* LS new GLNode(10); LS-next new GLNode(n20); LS-next-next new GLNode(40); LS-next-next-next new GLNode(sub50); cout 原广义表; printGL(LS); cout endl; cout 长度 length(LS) endl; cout 深度 depth(LS) endl; // 复制 GLNode* copy copyGL(LS); cout \n复制后的表; printGL(copy); cout endl; // 取表头 GLNode* head getHead(LS); cout 表头; printGL(head); cout endl; // 取表尾 GLNode* tail getTail(LS); cout 表尾; printGL(tail); cout endl; // 销毁 destroy(LS); destroy(copy); destroy(head); destroy(tail); return 0; }运行结果原广义表10 ( 20 30 ) 40 ( ( 50 ) ) 长度4 深度3 复制后的表10 ( 20 30 ) 40 ( ( 50 ) ) 表头10 表尾( 20 30 ) 40 ( ( 50 ) )数组 vs 广义表完整对比特性数组广义表元素类型同构异构原子 子表结构固定维度、矩形递归、树状、嵌套大小静态固定动态可变存储连续内存链式存储访问随机 O(1)遍历 / 递归 O(n)操作读写、遍历表头、表尾、复制、销毁本质线性表扩展线性表的递归推广