数据结构基础：线性表、堆栈、队列与图的遍历

"数据结构1" 在数据结构中，我们主要关注如何组织和操作数据，以便于高效地执行各种计算任务。以下是一些关键概念： 1. **顶点与边**：在图论中，顶点（Vertex）是图的基本组成单元，而边（Edge）表示顶点之间的关系。描述图的属性时，会提及顶点数（G.vexnum）和边数（G.arcnum）。访问某个顶点通常通过全局变量visited数组实现，其中visited[i]=1表示顶点i已被访问。 2. **线性表**：线性表是一种基本的数据结构，包含有序元素序列。它可以顺序存储或链式存储。 - **顺序存储**：线性表的元素存储在一块连续的内存区域中，例如数组。插入操作（StatusInsert）在数组中找到合适的位置插入元素，表长可以通过va.length获取，访问元素使用va.elem[i]。 - **链式存储**：每个元素（节点）包含一个指向下一个元素的指针，例如在函数StatusDelet中处理链表操作。空表的标志是头结点的next指针为null，访问元素通过遍历链表实现。 3. **堆栈**：堆栈是一种后进先出（LIFO）的数据结构，常用于临时存储和恢复信息。堆栈的操作包括初始化（InitStack）、压栈（Push）、弹栈（Pop）、获取栈顶元素（GetTop）和判断栈空（StackEmpty）。链式存储的堆栈，头结点默认存在，直接通过S->next访问。 4. **队列**：队列是一种先进先出（FIFO）的数据结构。循环队列简化了边界处理，使用front和rear指针管理队列的头部和尾部，队列元素存放在Q->Data[Q->rear]，队列的最大容量是Q->MaxSize。常见的队列操作有初始化（InitQueue）、入队（EnQueue）、出队（DeQueue）和判断队列为空。 5. **广义表**：广义表可以存储原子和子列表，是一种更通用的链表形式。访问广义表的tag字段可以判断元素类型（原子为0，表为1），访问原子、子列表或其他元素则通过L->tag、L->atom、L->ptr.hp和L->ptr.tp。递归处理广义表时，注意表头要加1。 6. **三元组存储**：在数据库中，三元组存储法用于存储二维矩阵，如(i, j, aij)，其中1≤i≤n, 1≤j≤m，表示第i行第j列的值。 7. **二叉树**：二叉树每个节点最多有两个子节点。叶子节点的数量可以通过递归函数StatusCaculateLeafNodeNumber计算，访问子节点使用T->lchild和T->rchild，判空条件是!T。 8. **孩子-兄弟链表表示的树**：这种表示方法中，每个节点包含firstchild和nextsibling指针，分别指向第一个孩子和下一个兄弟节点。函数LeafNum(CSTree&T)可计算树中的叶子节点数。 9. **邻接表表示的图**：在图的邻接表表示中，每个顶点都有一个firstarc指针，指向其第一条邻接边，通过循环遍历G.vertices[i].firstarc并使用p->nextarc移动到下一条边，p->adjvex获取邻接顶点。全局变量visited数组用于标记顶点是否被访问过。 10. **顺序表**（SSTable）：顺序表是另一种数组实现的线性表，元素按顺序存储，适用于小规模数据，操作简单但插入和删除效率相对较低。 以上是数据结构1中涉及的主要概念和操作，它们是计算机科学中解决问题的基础工具。