键盘输入构建十字链表算法：数组与矩阵操作优化

本文档主要介绍了从键盘接收信息并构建十字链表的算法，这是一种在数据结构中用于处理和组织数据的方式。在这个特定的算法中，关键步骤包括： 1. 初始化变量：设置预前节点(pre)为NULL，以及指向当前行最后一个元素的指针(p)为rh[r-1]，其中rh表示一个二维数组，r代表行号。 2. 寻找插入位置：判断p是否不为空且字符c大于p->col（p的列索引），如果满足条件，说明p需要向右移动，直到找到合适的插入位置。 3. 插入操作： a. 当p为空且pre也为空时，意味着当前行是空的，将新输入字符s直接添加到rh[r-1]。 b. 如果p为空但pre不为空，即到达了行尾，将s添加到pre的右链接（pre->right）。 c. 如果新字符c等于p->col，更新p的值。 d. 如果c小于p->col且pre为空，说明这是新行的第一个元素，将s设置为rh[r-1]，s->right设为p，并保持rh[r-1]不变。 e. 若c小于p->col且pre不为空，将s插入到p之前，s->right连接到p，同时可能需要调整q->right指向s。 算法的时间复杂度分析：T(n) = o(t*s)，其中t表示非零元个数，s为最大行数或列数（取两者较大值）。这表明算法的时间复杂度与输入数据的大小成正比，与数据的分布情况有关。 在讨论了算法的核心内容后，文档还提到了与数组相关的概念，包括： - 数组的定义和特点：数组被视为一种特殊的线性表，其数据元素自身也可以是线性表。数组有固定的结构，数据元素具有相同的类型，可以通过下标访问和修改元素。 - 顺序存储结构：分为行序和列序两种存储方式，分别通过行或列的顺序来确定元素的存储位置。 - 矩阵的压缩存储：针对对称矩阵和三角矩阵，通过存储非对角线上的元素来节省空间，如仅存储上三角或下三角的元素。 这部分内容展示了数组和矩阵在数据结构中的应用，以及如何根据矩阵的特性选择最有效的存储方式。在实际编程中，理解这些概念对于高效地实现数据结构和算法至关重要。