数据结构-习题

常用

// 比较字符串
strcmp(s1,s2); // 0 表示相等

// 快速排序
// 实现结构体排序 qsort
typedef struct{
  int id;
  int score;
} Student;
 
// 比较函数，必须返回int
// cont void *a 是通用指针，使用时必须强转
int cmp(const void* a,const void *b){
  Student *s1 = (Student*)a;
  Student *s2 = (Student*)b;
  // 编写排序逻辑
  if(s1->score != s2->score){
    return s2->score - s1->score;
  }else{
    return s2->score - s1->score;
  }
}
// qsort 调用：数组名，元素个数，每个元素大小，比较函数

字符串读取的空格问题

现象：用 scanf("%s", str) 读带有空格的句子（如 “Hello World”），只会读到 “Hello”。
解药：
- C语言用 gets(str) (不安全但考试通常可用) 或者 fgets(str, size, stdin)。
- 注意：fgets 会把末尾的回车符 \n 也读进去，可能需要手动处理掉：str[strlen(str)-1] = '\0';

链表

查找数

// 定义链表节点
typedef struct Node{
  int data;
  struct Node* next;
} Node;
 
// 创建链表
Node* CreateList(int n){
  Node* head = NULL;
  Node* current = NULL;
  for(int i = 0; i< n;i++){
    int x;
    scanf("%d", &x);
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = x;
    new_node->next = NULL;
    if(i == 0){
      head = current = new_node;
    }else {
      current->next = new_node;
      current = current->next;
    }
  }
  return head;
}
 
// 实现寻找指定数
Node* Search(Node* head,int x){
  Node* cur = head;
  while(cur != NULL){
    if(cur->data == x){
      return cur;
    }else{
      if(cur->next != NULL){
        cur = cur->next;
      }else{
        return NULL;
      }
    }
  }
}
 
// 释放链表内存
void FreeList(Node* head){
  Node* current = head;
  while(current != NULL){
    Node* temp = current;
    current = current->next;
    free(temp);
  }
}

在第 i 个位置插入数

没写出来，重写

二级指针的想法，将需插入位置看作一个指针地址，通过修改指针地址的内容，让其指向不同的位置，从而实现插入。

直接让 cur 指向 next 节点，就可以直接修改了。

注意

cur -> next 等同于 (*cur).next !可以省去一步解引用。

int Insert(Node** head, int i, int x) {
    Node** cur = head;  // cur 指向“指向当前节点的指针”
    int count = 1;
 
    if (i < 1) return 0; // 插入位置非法，返回失败
 
    // 1. 寻找插入位置：移动 i-1 次
    // 且要确保我们没有跳过链表末尾
    while (*cur != NULL && count < i) {
        cur = &((*cur)->next); // 让 cur 指向下一个节点的 next 域
        count++;
    }
 
    // 2. 检查是否找到了有效位置
    // 如果 count < i，说明链表太短了，没到第 i 个位置就结束了
    if (count < i) return 0;
 
    // 3. 执行插入
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) return 0; // 内存分配失败
 
    newNode->data = x;
    
    // 关键两步：
    newNode->next = *cur; // 新节点指向当前位置的节点
    *cur = newNode;       // 原本指向当前位置的指针，现在指向新节点
 
    return 1; // 插入成功
}

删除节点

核心是二级指针！直接修改节点。

void Remove(Node **head, int i) {
  if (i < 1) {
    printf("position error\n");
    return;
  }
  int cnt = 1;
  Node **cur = head;
  while (*cur != NULL) {
    if (cnt == i) {
      *cur = (*cur)->next;
      return;
    } else {
      cur = &((*cur)->next);
    }
    cnt++;
  }
  printf("position error\n");
  return;
}

求列表倒数n项

用双指针进行求倒数。

int Find(ListNode *head, int m, int *err) {
  int cnt = 0;
  *err = 0;
  ListNode *slow = head;
  ListNode *fast = head;
 
  while (cnt < m && fast != NULL) {
    fast = fast->next;
    cnt += 1;
  }
  if (cnt < m) {
    *err = 1;
    return 0;
  }
 
  while (fast != NULL) {
    slow = slow->next;
    fast = fast->next;
  }
  return slow->data;
}

栈

判断合法序列

// 栈结构体
typedef struct {
  int capacity;
  int top;
  int *data;
} Stack;
 
// 初始化栈
void init_stack(Stack *stack, int size) {
  stack->capacity = size;
  stack->top = -1;
  stack->data = (int *)malloc(size * sizeof(int));
}
 
// 判断是否满
int is_full(Stack *stack) { return stack->top + 1 == stack->capacity; }
 
// 判断是否为空
int is_empty(Stack *stack) { return stack->top == -1; }
 
// 入栈
int push(Stack *stack, int x) {
  if (is_full(stack))
    return 0;
  stack->data[++stack->top] = x;
  return 1;
}
 
// 出栈
int pop(Stack *stack) {
  if (is_empty(stack))
    return 0;
  stack->top--;
  return 1;
}
 
// 清空栈
void clear(Stack *stack) { stack->top = -1; }
 
// 销毁栈
void destroy_stack(Stack *stack) {
  free(stack->data);
  stack->data = NULL;
}
 
int is_valid_stack_sequence(const char *sequence, int max_capacity) {
  int i = 0;
  Stack *stack = (Stack *)malloc(sizeof(Stack));
  init_stack(stack, max_capacity);
 
  while (sequence[i] != '\0') {
    if (sequence[i] == 'S') {
      if (push(stack, 1)) {
        i++;
      } else {
        return 0;
      }
    } else if (sequence[i] == 'X') {
      if (pop(stack)) {
        i++;
      } else {
        return 0;
      }
    } else {
      return 0;
    }
  }
  if (is_empty(stack)) {
    destroy_stack(stack);
    return 1;
  } else {
    destroy_stack(stack);
    return 0;
  }
}

哈希表

线性探测

注意，当出现冲突的时候，不仅要检查 empty,还需要检查是否有重复键值对！同理，删除以后应该改为 Inactive 而不是 empty,为了防重复！

typedef enum { Empty, Active, Inactive } Status;
 
typedef struct {
  int key;
} Record;
 
typedef struct {
  Record data;
  Status status;
} DataNode;
 
typedef struct {
  DataNode *ht;   // 散列表数组
  int size;       // 当前元素个数
  int table_size; // 散列表长度
} HashTable;
 
int Hash(int key, int table_size) { return key % table_size; }
 
// 线性探查
int SolveColloision(int key, int count) { return 1; }
 
int SearchHash(HashTable *htable, int key) {
  int test = Hash(key, htable->table_size);
  if (htable->ht[test].status != Active || htable->ht[test].data.key == key) {
    return test;
  } else {
    int flag = 1;
    for (int i = test; i < htable->table_size; i++) {
      if (htable->ht[i].status != Active || htable->ht[i].data.key == key) {
        return i;
      }
    }
    if (flag) {
      for (int i = 0; i < test; i++) {
        if (htable->ht[i].status != Active || htable->ht[i].data.key == key) {
          return i;
        }
      }
    }
    return 0;
  }
}
 
// 插入
void InserHash(HashTable *htable, Record x) {
  int p = SearchHash(htable, x.key);
  printf("%d ", p);
  if (htable->ht[p].status != Active) {
    htable->ht[p].data = x;
    htable->ht[p].status = Active;
    htable->size++;
  }
}

排序

希尔排序

本质是分组 - 插入排序。实现时，需要不断缩小比较的分组间隙，以达到排序的效果。注意：需要从后向前比较，从前向后循环,就可以默认前面都是有序的了。

void ShellSort(int a[], int l, int r) {
    int n = r - l + 1; // 实际参与排序的元素个数
    // 1. 确定增量步长 tag
    for (int tag = n / 2; tag > 0; tag /= 2) {
        // 2. 从第 l + tag 个元素开始，逐个向后处理
        for (int i = l + tag; i <= r; i++) {
            int temp = a[i];
            int j;
            // 3. 组内插入排序：j 是在同一组内寻找 temp 应该插入的位置
            // j >= l + tag 确保 j-tag 不会越过左边界 l
            for (j = i; j >= l + tag && a[j - tag] > temp; j -= tag) {
                a[j] = a[j - tag]; // 将前面的大元素后移
            }
            a[j] = temp; // 插入到正确位置
        }
    }
}

快速排序

核心思想是分治。选数，然后将数组分为大于该数、小于该数的两部分，接着递归处理。

void QuickSort(int a[],int l,int r){
  // 递归出口
  if (l >= r) return;
  
  int i = l,j = r;
  int flag = a[l];
 
  while(i<j){
    // 从右往左找第一个小于基准的
    while(i<j && a[j] >= flag) j--;
    if(i<j) a[i++] = a[j];
 
    // 从左往右找第一个大于基准的
    while(i<j && a[i] <= flag) i++;
    if(i<j) a[j--] = a[i];
  }
  a[i] = flag; // 基准数回位
  
  // 递归处理
  QuickSort(a, l, i-1);
  QuickSort(a, i+1, r);
}

归并排序

核心是分治-递归，分成单个区间，然后两两合并。难点在理解递归。

还有非递归的步长式写法。

// from gemini
// 合并两个有序区间 [l, mid] 和 [mid+1, r]
void Merge(int a[], int l, int mid, int r) {
    int n = r - l + 1;
    int *temp = (int *)malloc(n * sizeof(int)); // 申请辅助空间
    int i = l, j = mid + 1, k = 0;
 
    // 两两比较，谁小谁进 temp
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
 
    // 处理剩余元素
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
 
    // 写回原数组
    for (int p = 0; p < n; p++) a[l + p] = temp[p];
    free(temp);
}
 
void MergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
 
    MergeSort(a, l, mid);       // 递归排左边
    MergeSort(a, mid + 1, r);   // 递归排右边
    Merge(a, l, mid, r);        // 合并
}

插入排序

前半部分是有序的，并始终保持其有序性向后

树

遍历

根据前序序列还原二叉树

需要一个全局变量来进行记录！依次遍历字符串的中（根）、左、右，抓住根节点在最前面即可。

这里是构建而非统计，所以递归的逻辑有些不同,需要先创建当前根节点，然后再递归左右子树。

// 前序遍历的反序列化
Node* PreOrderDeSerialize(char* preorder, int n){
  // 递归出口：数组为空、越界、或遇到空节点标识
  if(preorder == NULL || k >= n || preorder[k] == '#'){
    k++;
    return NULL;
  }
  // 创建当前根节点
  Node* root = (Node*)malloc(sizeof(Node));
  if(!root) return NULL;
 
  // 填入数据、移动下标;
  root->data = preorder[k];
 
  // 递归构造
  root->left = PreOrderDeSerialize(preorder, n);
  root->right = PreOrderDeSerialize(preorder, n);
  return root;
}

后序遍历

void PostOrder(Node* root){
  if(root != NULL){
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c ",root->data);
  }
}

中序遍历

非递归写法,用栈来代替递归，注意左-中-右的结构。

// 非递归中序遍历
void InOrder(Node *tree) {
  Node *stack[1000];
  int top = -1;
  Node *cur = tree;
 
  // 当cur不为空，或栈里还有没处理完的节点时，继续循环
  while (cur != NULL || top != -1) {
    // 一直到最左，所有节点入栈
    while (cur != NULL) {
      stack[++top] = cur;
      cur = cur->left;
    }
    // 左边到头，弹出栈顶节点
    cur = stack[top--];
    printf("%c ", cur->data);
    // 去右子树
    cur = cur->right;
  }
}

根据前、中序序列还原二叉树

还是递归构建的逻辑，由于不知道空节点，所以只能找根节点 - 递归左右子树。

// 构建二叉树
BinaryTreeNode* BuildTree(char* preorder, char* inorder,int n){
  // 递归出口
  if(n <= 0) return NULL;
  // 创建根节点
  BinaryTreeNode* root = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
  root->data = preorder[0];
  // 在中序序列中找到根节点位置
  int k = 0;
  while(k<n && inorder[k] != preorder[0]){
    k++;
  }
  // 递归后件左右子树
  root->left = BuildTree(preorder+1, inorder, k);
  root->right = BuildTree(preorder+1+k, inorder+k+1, n-k-1);
  return root;
}

统计

求高度

主要在于要取左右子树中的较大者。

int Height(Node* tree){
  if(tree == NULL){
    return 0;
  }
  int left = Height(tree->left);
  int right = Height(tree->right);
  int height = left > right ? left : right;
  return height + 1;
}
 
// 学一下用 fgets 读取数据
int main() {
  char preorder[1000];
  if (fgets(preorder, sizeof(preorder), stdin) == NULL) {
    // 输入为空
    return 0;
  }
 
  // 去掉换行符
  size_t len = strlen(preorder);
  if (len > 0 && preorder[len - 1] == '\n')
    preorder[len - 1] = '\n';
  if (strlen(preorder) == 0){
    printf("0\n");
    return 0;
  }
  k = 0; // 重置全局索引
  Node *tree = PreOrderDeSerialize(preorder, strlen(preorder));
  PostOrder(tree);
  printf("%d\n",Height(tree));
  return 0;
}

堆

1. 堆的逻辑结构与存储

堆在逻辑上是一棵完全二叉树，但在物理存储上，我们通常使用数组来表示它。

为了方便计算父子节点的下标，习惯上数组的 第 0 个位置不存数据（或存放一个哨兵值），数据从 下标 1 开始存储。

下标关系公式（核心）：

对于数组中下标为 $i$ 的节点：

它的父节点下标是： $i /2$ （整数除法）。
它的左孩子下标是： $2 i$ 。
它的右孩子下标是： $2 i + 1$ 。

2. 最小堆的插入算法（上浮/Percolate Up）

最小堆的性质是：任意节点的值都小于或等于其左右孩子的值。这意味着根节点永远是整棵树的最小值。

当你向堆中插入一个新数字时，步骤如下：

放在末尾：将新元素放到数组当前的最后一个位置（即下标 $n + 1$ ）。
向上比较（上浮）：
- 将该元素与其父节点（下标 $i /2$ ）比较。
- 如果新元素 < 父节点，则交换它们的位置。
- 重复这个过程，直到该元素大于父节点，或者已经到达根节点（下标 1）。

哨兵技巧：在 h[0] 存放一个极小值（如 -10001），这样在循环到根节点时，h[i] < h[i/2] 自然会失效，可以省去判断 i > 1。

3. 路径回溯

打印从下标 $i$ 到根节点的路径。由于堆是完全二叉树，路径是唯一的。

根据我们之前的下标公式，回溯极其简单：

当前节点是 $i$ 。
上一个节点是 $i /2$ 。
上上个节点是 $(i /2) /2$ 。
以此类推，直到下标变为 1。

示例

typedef struct{
  int* data;
  int size;     // 实际存储
  int capacity; // 容量
} MinHeap ;
 
// 创建最小堆
MinHeap* CreateMinHeap(int capacity){
  MinHeap* h = (MinHeap*)malloc(sizeof(MinHeap));
  h->capacity = capacity;
  h->size = 0;
  h->data = (int*)malloc((capacity+1)*sizeof(MinHeap));
  return h;
}
 
// 上调操作
void SiftUp(MinHeap* heap,int i){
  int elem = heap->data[i];
  while(i > 1 && elem < heap->data[i/2]){
    heap->data[i] = heap->data[i/2];
    i /= 2;
  }
  heap->data[i] = elem;
}
 
// 下调操作
// 需要判断是要去左儿子还是右儿子，并持续下沉
void SiftDown(MinHeap* heap,int i){
  int elem = heap->data[i];
  int last = heap->size;
  while(1){
    int child = i*2;
    if(child < last && heap->data[child + 1] < heap->data[child])
      child++;
    if(child > last)
      break;
    if(heap->data[child] < elem){
      heap->data[i] = heap->data[child];
      i = child;
    }else{
      break;
    } 
    heap->data[i] = elem;
  }
}
 
// 插入
void Insert(MinHeap* heap,int x){
  if(heap->size == heap->capacity){
    printf("错误：堆已满，无法插入。\n");
  }
  heap->size++;
  heap->data[heap->size] = x;
  SiftUp(heap,heap->size);
}
 
// 删除栈顶元素
// 用最后的数进行代替
int ExtractMin(MinHeap* heap){
  int minKey = heap->data[1];
  heap->data[1] = heap->data[heap->size];
  heap->size--;
  SiftDown(heap,1);
  return minKey;
}
 
// 查询路径
void Path(MinHeap* h,int i){
  while(i>=1){
    printf("%d",h->data[i]);
    if(i>1){
      printf(" ");
    }
    i /= 2;
  }
  printf("\n");
}

背包

连续背包

物品是可以分割的，即可以拿走一部分。所以选择的标准是物品的单位价值。

将性价比排序，然后拿取，记录比例

注意 qsort、cmd

// 比较函数，用于按价值/重量比排序（降序）
int cmp(const void *a, const void *b) {
  Object *obj1 = (Object *)a;
  Object *obj2 = (Object *)b;
  double r1 = obj1->v / obj1->w;
  double r2 = obj2->v / obj2->w;
  if (r1 < r2)
    return 1;
  else if (r1 > r2)
    return -1;
  else
    return 0;
}
 
double Knapsack(double W, Object s[], double x[], int n){
  // 按性价比排序
  qsort(s, n, sizeof(Object), cmp);
 
  double totalValue = 0.0; // 背包总价值
  double currentW = W; //背包剩余容量;
  
  for(int i = 0;i<n;i++){
    // 通过idx找到物品在结果数组中的索引
    int original_idx = s[i].idx;
    if(s[i].w <= currentW){
      x[original_idx] = 1.0;
      totalValue += s[i].v;
      currentW -= s[i].w;
    }else{
      if(currentW > 0){
        x[original_idx] = currentW / s[i].w;
        totalValue += x[original_idx] * s[i].v;
        currentW = 0;
      }else{
        x[original_idx] = 0.0;
      }
    }
  }
  return totalValue;
}

图

// 深搜、广搜
// DFS
void dfs(int u){
  vis[u] = 1;
  printf("%d ",u);
  
  int v;
  for(v=1;v<=n;v++){
    if(G[u][v] == 1 && vis[v] == 0){
      dfs(v);
    }
  }
}
 
// BFS
void bfs(int start){
  // 用队列实现
  int q[MAXN];
  int front = 0,rear = 0;
  q[rear++] = start; // 起点入队
  vis[start] = 1;
 
  while(front < rear){
    // 出队
    int u = q[front++];
    printf("%d ",u);
    // 遍历邻接点
    int v;
    for(v=1;v<=n;v++){
      if(G[u][v] == 1 && vis[v] == 0){
        vis[v] = 1;
        q[rear++] = v;
      }
    }
  }
}

邻接矩阵的实现

删除节点的逻辑会复杂一点，要考虑清楚，用后面的节点替代前面的节点。然后是图的定义要清晰，包含边、顶点数，以及存储信息等等。

typedef struct {
  int n_verts;                             // 顶点数
  int m_edges;                             // 边数
  int edge_matrix[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
  char *ver_list[MAX_VERTEX];              // 存储顶点信息
  int no_edge_value;                       // 没有边时的权重
  int directed;                            // 1为有向图，0为无向图
} MGraph;
 
// 初始化图
MGraph *InitGraph(int kMaxVertex, int no_edge_value, int directed) {
  MGraph *graph = (MGraph *)malloc(sizeof(MGraph));
  graph->n_verts = 0;
  graph->m_edges = 0;
  graph->no_edge_value = no_edge_value;
  graph->directed = directed;
  for (int i = 0; i < kMaxVertex; i++) {
    graph->ver_list[i] = NULL;
    for (int j = 0; j < kMaxVertex; j++) {
      graph->edge_matrix[i][j] = no_edge_value;
    }
  }
  return graph;
}
 
// 本题要求实现
int NumberOfEdges(MGraph *graph){
  return graph->m_edges;
}
 
// 本题要求实现
int NumberOfVerts(MGraph *graph){
  return graph->n_verts;
}
 
// 判断边是否存在 本题要求实现
int ExistEdge(MGraph *graph, int u, int v){
  if(u < 0 || u >= graph->n_verts || v < 0 || v >= graph->n_verts) return 0;
  return graph->edge_matrix[u][v] != graph->no_edge_value;
}
 
// 找顶点的第一个邻接点  本题要求实现
int FirstAdjVert(MGraph *graph, int v){
  if(v < 0 || v >= graph->n_verts) return -1;
  
  for(int j = 0;j<graph->n_verts;j++){
    if(graph->edge_matrix[v][j] != graph->no_edge_value) return j;
  }
  return -1;
}
 
// 向图中插入边  本题要求实现
void InsertEdge(MGraph *graph, int u, int v, int weight){
  if(u<0 || u>=graph->n_verts || v<0 || v>=graph->n_verts) return;
 
  // 边已存在，不插入
  if(ExistEdge(graph, u, v)) return;
 
  graph->edge_matrix[u][v] = weight;
  if(graph->directed == 0){
    graph->edge_matrix[v][u] = weight;
  }
  graph->m_edges++;
}
 
// 从图中删除边  本题要求实现
void RemoveEdge(MGraph *graph, int u, int v){
  if(!ExistEdge(graph, u, v)) return;
  graph->edge_matrix[u][v] = graph->no_edge_value;
  if(graph->directed == 0){
    graph->edge_matrix[v][u] = graph->no_edge_value;
  }
  graph->m_edges--;
}
 
// 从图中删除顶点及所有邻接边  本题要求实现
void RemoveVert(MGraph *graph, int v){
  if(v<0 || v>= graph->n_verts){
    printf("error: %d is not exist\n", v);
    return;
  }
  // 统计并扣除与v关联的边数
  for(int i = 0;i<graph->n_verts;i++){
    if(graph->edge_matrix[v][i] != graph->no_edge_value) graph->edge_matrix[v][i] = graph->m_edges--;
    if(graph->directed && graph->edge_matrix[i][v] != graph->no_edge_value) graph->edge_matrix[i][v] = graph->m_edges--;
  }
 
  free(graph->ver_list[v]);
 
  // 最后一个节点覆盖当前位置
  int last = graph->n_verts - 1;
  if(v!=last){
    graph->ver_list[v] = graph->ver_list[last];
    // 移动行,列
    for(int j = 0;j<graph->n_verts;j++){
      graph->edge_matrix[v][j] = graph->edge_matrix[last][j];
    }
    for(int i = 0;i<graph->n_verts;i++){
      graph->edge_matrix[i][v] = graph->edge_matrix[i][last];
    }
  }
  graph->ver_list[last] = NULL;
  graph->n_verts--;
}
 
// 构建图
MGraph *BuildGraph() {
  int kMaxVertex, no_edge_value, directed;
  scanf("%d %d %d", &kMaxVertex, &no_edge_value, &directed);
  MGraph *graph = InitGraph(kMaxVertex, no_edge_value, directed);
 
  int n, m;
  scanf("%d %d", &n, &m);
 
  char temp[50];
  for (int i = 0; i < n; i++) {
    scanf("%s", temp);
    graph->ver_list[i] = (char *)malloc(strlen(temp) + 1);
    strcpy(graph->ver_list[i], temp);
  }
  graph->n_verts = n;
 
  for (int i = 0; i < m; i++) {
    int u, v, weight;
    scanf("%d %d %d", &u, &v, &weight);
    InsertEdge(graph, u, v, weight);
  }
  return graph;
}
 
// 打印图
void PrintGraph(MGraph *g) {
  printf("adjacency matrix:\n");
  for (int u = 0; u < g->n_verts; u++) {
    for (int v = 0; v < g->n_verts; v++) {
      printf("%d ", g->edge_matrix[u][v]);
    }
    printf("\n");
  }
  printf("vex num = %d, edge num = %d\n", NumberOfVerts(g), NumberOfEdges(g));
}

Dijkstra 算法

Dijkstra 是一种求解非负权图单源最短路径的经典算法。它通过不断扩展距离源点最近的“未访问”顶点，来逐步确定到所有点的最短路。

核心步骤：

初始化：
- dist[]：存储源点到各点的最短距离。初始时，源点 dist[0] = 0，其余设为无穷大（INF）。
- path[]：记录路径前驱。初始全为 -1。
- visited[]：记录顶点是否已确定最短路径。初始全为 false。
找最小：在所有 visited == false 的顶点中，找一个 dist[i] 最小的顶点 $u$ 。
标记：将 $u$ 标记为 visited = true。
松弛（Relaxation）：遍历 $u$ 的所有邻接点 $v$ 。如果通过 $u$ 抵达 $v$ 的路径比当前的 dist[v] 更短，则更新 dist[v] 和 path[v]。

核心在逐个遍历，标记是否访问。dist[] 标记最短路径，path[] 标记上一个点。

void Dijkstra(MGraph *graph, int s, int path[], int dist[]) {
  int visited[MAX_VERTEX] = {0};
  int n = graph->n_verts;
  // 初始化，源点距离为0,其他已初始化为INF
  dist[s] = 0;
  // 每次确定一个定点的最短路径，共执行n次
  for (int count = 0; count < n; count++) {
    // 在所有visited==0的点中，找最小dist
    int u = -1;
    int min_dist = INF;
    for (int i = 0; i < n; i++) {
      if (!visited[i] && dist[i] < min_dist) {
        min_dist = dist[i];
        u = i;
      }
    }
    // 若找不到可达的点，说明剩下的点不联通
    if (u == -1)
      break;
    visited[u] = 1;
    // 渗透，继续深入更新邻居
    for (int v = 0; v < n; v++) {
      // 如果 u->v 有边，且v最短路还没确定
      if (!visited[v] && graph->edge_matrix[u][v] != graph->no_edge_value) {
        int weight = graph->edge_matrix[u][v];
        int new_dist = dist[u] + weight;
        // 发现更短的路
        if(new_dist < dist[v]){
          dist[v] = new_dist;
          path[v] = u;
        }
        else if(new_dist == dist[v] && path[v] != -1){
          if(dist[u] < dist[path[v]]){
            path[v] = u;
          }
        }
      }
    }
  }
}

Bellman-Ford 算法

Bellman-Ford 的原理基于一个简单的观察：在一个含有 $n$ 个顶点的图中，任意两点之间的最短路径（如果不含负环）最多包含 $n - 1$ 条边。

操作流程：对图中的所有边进行 $n - 1$ 轮“松弛”操作。
松弛公式：对于每一条边 $(u, v)$ 权重为 $w$ ，如果 dist[u] + w < dist[v]，则更新 dist[v] = dist[u] + w。
为什么是 $n - 1$ 次？：第一轮松弛可以确定最多经过 1 条边的最短路径，第二轮确定最多经过 2 条边的最短路径……以此类推， $n - 1$ 轮后可以确定所有点的最短路径。

int BellmanFord(MGraph *graph, int s, int dist[]) {
  int n = graph->n_verts;
  int no_edge = INF;
  // 初始化距离数组
  for (int i = 0; i < n; i++) {
    dist[i] = INF;
  }
  dist[s] = 0;
  // 进行n-1轮遍历，每一轮尝试通过现有的边来缩短距离
  for (int i = 0; i < n - 1; i++) {
    int updated = 0;
    // 遍历邻接矩阵中所有边
    for (int u = 0; u < n; u++) {
      // 只有当起点u可达，才有意义
      if (dist[u] == INF)
        continue;
      for (int v = 0; v < n; v++) {
        int weight = graph->edge_matrix[u][v];
        if (u != v && weight != no_edge) {
          dist[v] = dist[u] + weight;
          updated = 1;
        }
      }
    }
    if (!updated)
      break;
  }
  // 负环检测,若第n轮还能更新，则说明存在负环
  for (int u = 0; u < n; u++) {
    if (dist[u] == INF)
      continue;
    for (int v = 0; v < n; v++) {
      int weight = graph->edge_matrix[u][v];
      if (dist[u] + weight < dist[v]) {
        return 0;
      }
    }
  }
  return -1;
}

Floyd 算法

Floyd 算法的本质是动态规划。它通过不断尝试引入新的“中转点”来优化路径。

逻辑描述：假设你想从顶点 $i$ 到顶点 $j$ 。
初始状态：你只知道 $i$ 到 $j$ 的直接距离（如果有边的话）。
演进过程：
1. 允许经过顶点 $0$ 中转，看看路径 $i \to 0 \to j$ 是否比直接走更短。
2. 再允许经过顶点 $1$ 中转，看看路径是否能更短。
3. …直到允许经过图中所有的顶点中转。
最终结果：当所有顶点都作为“中转候选人”被考虑过之后， $i$ 到 $j$ 之间留下的就是全局最短路径。

void FloydWarshall(MGraph* graph, int dist[MAX_VERTEX][MAX_VERTEX], int path[MAX_VERTEX][MAX_VERTEX]){
  int n = graph->n_verts;
  // 初始化dist、path矩阵
  for(int i =0;i<n;i++){
    for(int j=0;j<n;j++){
      dist[i][j] = graph->edge_matrix[i][j];
      if(i!=j && graph->edge_matrix[i][j] != INF){
        path[i][j] = i;
      }else{
        path[i][j] = -1;
      }
    }
  }
  for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      // 若起点到不了中转点，跳过
      if(dist[i][k] == INF) continue;
      for(int j=0;j<n;j++){
        if(dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]){
          dist[i][j] = dist[i][k] + dist[k][j];
          path[i][j] = path[k][j];
        }
      }
    }
  }
}

拓扑排序

就是求实现任务所必须的执行顺序，要按照次序执行。

入度：指指向该节点的边的条数。
物理意义：在拓扑排序中，一个节点的入度代表了它还有多少个“前置任务”没有完成。
逻辑：只有当一个节点的入度为 0 时，它才被认为是“准备就绪”的，可以被处理。

使用队列（Queue）实现的拓扑排序通常遵循以下步骤：

统计入度：扫描全图，记录每个节点的初始入度。
初始入队：将所有入度为 0 的节点放入队列。
循环处理：
- 从队列中弹出一个节点 $u$ 。
- 计数：记录已处理的节点数量。
- “斩断”边：遍历 $u$ 指向的所有邻接点 $v$ 。
- 更新入度：将 $v$ 的入度减 1（相当于任务 $u$ 完成了， $v$ 的前置条件少了一个）。
- 触发入队：如果减 1 后 $v$ 的入度变成了 0，则将 $v$ 入队。
结果判定：
- 如果最终处理过的节点数量等于图中的总节点数 $n$ ，说明拓扑排序成功（图是 DAG）。
- 如果数量小于 $n$ ，说明图中存在环路，无法完成拓扑排序。

int TopSort(Graph* graph, int* top_s){
  int n = graph->n_verts;
  int in_degree[KMAXVERTEX];//存储入度
  int queue[KMAXVERTEX];
  int front = 0,rear = 0;
  int count = 0; // 记录已排序的节点数
 
  GetInDegree(graph, in_degree);
 
  // 初始入度为0的按序号入队
  for(int i=0;i<n;i++){
    if(in_degree[i] == 0){
      queue[rear++] = i;
    }
  }
  // 循环处理队列
  while(front < rear){
    int u = queue[front++];
    top_s[count++] = u;
    // 遍历 u 的所有邻接点
    EdgeNode* p = graph->ver_list[u].adj;
    while(p!=NULL){
      int v = p->dest;
      // 模拟入度减少
      in_degree[v]--;
      // 若入度变为0,入队 
      if(in_degree[v] == 0){
        queue[rear++] = v;
      }
      p = p->next;
    }
  }
  if(count == n){
    return 1;
  }else{
    return 0;
  }
}

关键活动

求从起点到终点耗时最长的路径（决定了整个工程的最短工期）。本质是逆拓扑排序，求出必须走过的路径。

第一步：拓扑排序 + 正推求 $v e []$

建立邻接表，统计每个节点的入度。
将入度为 0 的节点入队列（题目要求使用队列）。
初始化所有 $v e [i] = 0$ 。
BFS流程（拓扑排序）：
- 从队列弹出节点 $u$ 。
- 保存拓扑序列（因为后面逆推需要用到逆拓扑序，可以用一个栈或数组存下来）。
- 遍历 $u$ 的所有邻接点 $v$ ：
  - 更新 $v e [v] = max (v e [v], v e [u] + w)$
  - $v$ 的入度减 1，如果减为 0，入队。

第二步：逆向拓扑排序 + 逆推求 $v l []$

初始化所有 $v l [i]$ 为汇点（终点）的 $v e$ 值（即 $v l [i] = v e [end_node]$ ）。
- 即最早、最晚开始时间，判断是否相等.
- 最早开始时间指的是前面所有任务都完成的时间，及最大时间
逆序遍历刚才保存的拓扑序列（从终点向起点扫）：
- 取出节点 $u$ 。
- 遍历 $u$ 的所有邻接点 $v$ ：
  - 更新 $v l [u] = min (v l [u], v l [v] - w)$
计算 $e = v e [u]$ 。
计算 $l = v l [v] - w$ 。
如果 $e == l$ ，输出该边（即为关键路径上的一段）。

// 拓扑排序
int TopSort(LGraph* graph, int* top_s) {
    int n = graph->n_verts;
    int in_degree[KMAXVERTEX];
    GetInDegree(graph, in_degree);
    int queue[KMAXVERTEX], front=0, rear=0;
    for(int i=0;i<n;i++)
        if(in_degree[i]==0) queue[rear++]=i;
    int count_v=0;
    while(front<rear){
        int u=queue[front++];
        top_s[count_v++]=u;
        EdgeNode* p = graph->ver_list[u].adj;
        while(p!=NULL){
            int v=p->dest;
            in_degree[v]--;
            if(in_degree[v]==0) queue[rear++]=v;
            p=p->next;
        }
    }
    return count_v==n;
}
 
 
// 关键路径分析
int CriticalAnalysis(LGraph* graph) {
    int n = graph->n_verts;
    int earliest[KMAXVERTEX]={0}, latest[KMAXVERTEX]={0};
    int top_s[KMAXVERTEX];
    if(!TopSort(graph, top_s)) return 0; // 有环，无法计算
 
    // 求最早发生时间
    for(int i=0;i<n;i++){
        int u=top_s[i];
        EdgeNode* p = graph->ver_list[u].adj;
        while(p!=NULL){
            int v=p->dest, weight=p->weight;
            if(earliest[v]<earliest[u]+weight)
                earliest[v]=earliest[u]+weight;
            p=p->next;
        }
    }
 
    // 求完成时间
    int completion_time=0;
    for(int i=0;i<n;i++)
        if(completion_time<earliest[i]) completion_time=earliest[i];
 
    // 初始化最迟发生时间
    for(int i=0;i<n;i++) latest[i]=completion_time;
 
    // 求最迟发生时间（逆拓扑）
    for(int i=n-1;i>=0;i--){
        int u=top_s[i];
        EdgeNode* p = graph->ver_list[u].adj;
        while(p!=NULL){
            int v=p->dest, weight=p->weight;
            if(latest[u] > latest[v]-weight)
                latest[u] = latest[v]-weight;
            p=p->next;
        }
    }
 
    // 输出关键活动
    for(int u=0; u<n; u++){
        EdgeNode* p = graph->ver_list[u].adj;
        while(p!=NULL){
            int v=p->dest, weight=p->weight;
            if(earliest[u] == latest[v]-weight)
                printf("<%d, %d>\n", u, v);
            p=p->next;
        }
    }
    return 1;
}

七桥问题-欧拉回路

一个无向图存在欧拉回路，必须同时满足以下两个条件：

条件一：所有顶点的度数必须是“偶数”

为什么？
- 欧拉回路要求“进”每一个节点，必须能“出”这个节点，最后还要回到起点。
- 这意味着，对于任何一个中间节点，有一条路进来（度+1），就必须有一条路出去（度再+1）。
- 进进出出，度数一定是成对出现的（2, 4, 6…）。
- 如果有任何一个节点的度数是奇数（比如 3，进去了2次，出来的只有1次，最后被困在里面了），那么就不可能形成回路。

条件二：所有“有边的节点”必须是连通的

为什么？
- 如果图分成了两块互不相连的区域（比如左边一个三角形，右边一个正方形），虽然它们的度数可能都是偶数，但你没法从左边走到右边去画完所有边。
- _注意：如果是一个孤立的点（度为0），它不影响欧拉回路的存在（因为它没有边需要画），我们在检查连通性时通常忽略度为0的点。
- 解法：通过BFS跑一遍，看是否经过了所有节点。

// DFS 遍历
void DFSv(MGraphNode* graph, int v) {
    graph->visited[v] = 1;
    for(int u=0; u<graph->n_verts; u++){
        if(graph->edge_matrix[v][u] != graph->no_edge_value && !graph->visited[u])
            DFSv(graph, u);
    }
}
 
// 判断欧拉回路
int HasEulerCircuit(MGraphNode* graph) {
    // 1. 检查连通性
    for(int i=0; i<graph->n_verts; i++)
        graph->visited[i] = 0;
    DFSv(graph, 0);
    for(int i=0; i<graph->n_verts; i++)
        if(!graph->visited[i])
            return 0;
 
    // 2. 检查所有顶点度是否为偶数
    for(int u=0; u<graph->n_verts; u++){
        int degree = 0;
        for(int v=0; v<graph->n_verts; v++){
            if(graph->edge_matrix[u][v] != graph->no_edge_value)
                degree++;
        }
        if(degree % 2 != 0)
            return 0;
    }
    return 1;
}

动态规划

计算矩阵的最小相乘次数

void PrintOrder(int i, int j) {
    if(i < j){
        int k = p[i][j];
        printf("(");
        PrintOrder(i, k);
        printf(")x(");
        PrintOrder(k+1, j);
        printf(")");
    } else {
        printf("M%d", i);
    }
}
 
void OptimalMatrixOrdering(int n, int* r) {
    for(int i=0;i<n;i++)
        m[i][i] = 0; // 只有一个矩阵，不需要乘法
 
    for(int length=1; length<n; length++){ // length = j-i
        for(int i=0; i<n-length; i++){
            int j = i + length;
            m[i][j] = INT_MAX;
            for(int k=i; k<j; k++){
                int this_m = m[i][k] + m[k+1][j] + r[i]*r[k+1]*r[j+1];
                if(this_m < m[i][j]){
                    m[i][j] = this_m;
                    p[i][j] = k;
                }
            }
        }
    }
}

带权活动安排问题

typedef struct {
    int start;
    int finish;
    int weight;
} Activity;
 
// 用于 qsort 的比较函数，按 finish 升序
int cmpFinish(const void* a, const void* b) {
    Activity* aa = (Activity*)a;
    Activity* bb = (Activity*)b;
    return aa->finish - bb->finish;
}
 
// 返回最大值函数
int max(int a, int b) {
    return a > b ? a : b;
}
 
// 带权活动选择
int WeightedActivitySelection(Activity* a, int n) {
    qsort(a+1, n, sizeof(Activity), cmpFinish); // a[1..n] 排序
    int* w = (int*)malloc((n+1)*sizeof(int));
    w[0] = 0;
 
    for(int i=1; i<=n; i++){
        int k = i-1;
        while(k>0){
            if(a[k].finish <= a[i].start)
                break;
            k--;
        }
        w[i] = max(w[i-1], w[k] + a[i].weight);
    }
    int result = w[n];
    free(w);
    return result;
}

Calendar's Blog

Explorer

数据结构-习题

常用

链表

查找数

在第 i 个位置插入数

删除节点

求列表倒数n项

栈

判断合法序列

哈希表

线性探测

排序

希尔排序

快速排序

归并排序

插入排序

树

遍历

根据前序序列还原二叉树

后序遍历

中序遍历

根据前、中序序列还原二叉树

统计

求高度

堆

1. 堆的逻辑结构与存储

2. 最小堆的插入算法（上浮/Percolate Up）

3. 路径回溯

示例

背包

连续背包

图

邻接矩阵的实现

Dijkstra 算法

核心步骤：

Bellman-Ford 算法

Floyd 算法

拓扑排序

关键活动

第一步：拓扑排序 + 正推求 ve[]

第二步：逆向拓扑排序 + 逆推求 vl[]

七桥问题-欧拉回路

条件一：所有顶点的度数必须是“偶数”

条件二：所有“有边的节点”必须是连通的

动态规划

计算矩阵的最小相乘次数

带权活动安排问题

Graph View

Table of Contents

第一步：拓扑排序 + 正推求 $v e []$

第二步：逆向拓扑排序 + 逆推求 $v l []$