稀疏矩阵快速转置三元组 求最小绝对值数组 判断是否是二叉排序树 堆删除第个数 邻接表计算连通分量，请分别给出c语言代码简洁版

稀疏矩阵快速转置三元组: 稀疏矩阵在存储时通常有很多零元素，为了节省空间，可以只记录非零元素及其坐标。快速转置是指将矩阵的行索引和列索引对换，但仍然保持非零元素的顺序。这里提供一个简单的C语言版本（使用邻接列表表示稀疏矩阵）:

typedef struct SparseTriple {
int row, col, value;
} SparseTriple;

// 转置稀疏矩阵
void transposeSparseMatrix(SparseTriple** transposed, SparseTriple* original, int m, int n) {
int i, j;
SparseTriple* newTriple = malloc((m + n) * sizeof(SparseTriple));
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (original[j].row == i) {
newTriple[j].row = i;
newTriple[j].col = original[j].col;
newTriple[j].value = original[j].value;
}
}
}
*transposed = newTriple;
}
登录后复制

求最小绝对值数组: 可以通过遍历数组找到最小绝对值，同时保存它的索引。以下是C语言代码：

#include <stdio.h>

// 找到数组中最小绝对值和其索引
int* minAbsArray(int arr[], int size) {
int minAbs = INT_MAX, minIndex = -1;
for (int i = 0; i < size; i++) {
if (abs(arr[i]) < abs(minAbs)) {
minAbs = arr[i];
minIndex = i;
}
}
int* result = (int*)malloc(sizeof(int) * 2);
result[0] = minAbs;
result[1] = minIndex;
return result;
}
登录后复制

判断是否是二叉排序树: 可以递归地检查每个节点，左子树的值都小于当前节点，右子树的值都大于当前节点。以下是C代码：

typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

// 判断是否是二叉排序树
bool isBST(TreeNode* root) {
return helper(root, INT_MIN, INT_MAX);
}

// 辅助函数
bool helper(TreeNode* node, int lower, int upper) {
if (!node) return true;
if (node->val <= lower || node->val > upper) return false;
return helper(node->left, lower, node->val - 1) &amp;&amp; helper(node->right, node->val + 1, upper);
}
登录后复制

堆删除第k个数: 使用大顶堆（最大堆），删除堆顶（即最大值）元素并将最后一个元素移到顶部再调整堆，直到得到第k小的元素。以下是C代码：

#include <stdio.h>
#include <stdlib.h>

// 删除堆中第k小的元素
void deleteKthSmallest(int h[], int n, int k) {
int temp[n];
buildMaxHeap(h, n); // 构建初始最大堆
for (int i = 0; i < k - 1; ++i) { // 删除前k - 1个最大元素
swap(&amp;h[0], &amp;h[n - 1]);
maxHeapify(h, 0, n - 1);
n--;
}
printf("第 %d 小的元素是 %d\n", k, h[0]); // 输出第k小的元素
}

// 堆化操作
void maxHeapify(int h[], int i, int n) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n &amp;&amp; h[left] > h[largest])
largest = left;

if (right < n &amp;&amp; h[right] > h[largest])
largest = right;

if (largest != i) {
swap(&amp;h[i], &amp;h[largest]);
maxHeapify(h, largest, n);
}
}
登录后复制

邻接表计算连通分量: 对于无向图，可以使用DFS（深度优先搜索）或BFS（广度优先搜索）来找出各个连通分量。以下是C代码（基于邻接表）的DFS版本：

#include <stdbool.h>

// 计算连通分量（DFS）
void connectedComponentsUtil(int v, vector<int>&amp; adjList, vector<int>&amp; visited, vector<vector<int>>&amp; components, int&amp; count) {
visited[v] = true;
components[count].push_back(v);

for (int neighbor : adjList[v]) {
if (!visited[neighbor]) {
connectedComponentsUtil(neighbor, adjList, visited, components, count);
}
}
}

// 主函数
vector<vector<int>> connectedComponents(vector<int>&amp; adjList, int V) {
vector<vector<int>> components;
vector<bool> visited(V, false);
int count = 0;

for (int v = 0; v < V; ++v) {
if (!visited[v]) {
connectedComponentsUtil(v, adjList, visited, components, count);
count++;
}
}
return components;
}
登录后复制