数据结构(C/C+)

gcc -v: gcc version 5.5.0 20171010 (Ubuntu 5.5.0-12ubuntu1~16.04)

线性表(Liner List)

线性表基本操作

• InitList(&L) 初始化线性表
• Length(L) 获取表长度
• LocateElem(L,e) 按值查找
• GetElem(L,i) 按位查找
• ListInsert(&L, i, e) 在第i个元素后插入元素e
• ListDelete(&L, i, &e) 删除第i个元素，用e返回被删除的元素
• PrintList(L) 按顺序输出表内所有元素值
• DestroyList(&L) 销毁线性表，即释放表所占内存

易错题

• 由100个字符串组成的序列可以称为一个线性表。
• 邻接表是一种存储结构，非线性表；线性表是一种逻辑结构。

线性表的顺序表示(Sequence List)

• 基于数组
• 顺序表逻辑上相邻的元素物理上也相邻
• 自动扩容，扩容策略始终为原来容量的2倍
• 顺序表位序从0开始（教材上要求从1开始）
• 插入T(n)= O(n)
• 删除T(n)= O(n)
• 顺序查找T(n)= O(n)

cpp

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define InitSize 10 // 定义顺序表的初始长度

typedef struct StudentInfo {
  char* name;
  int age;
} stu;

typedef struct SequenceList {
  stu* data;
  int Length; // 有效长度
} sqlist;

void InitList(sqlist &l);
void InitList(sqlist &l, int size);
int Length(sqlist &l);
int LocateElem(sqlist l, stu e); // 查找第一个包含e中元素的项
stu GetElem(sqlist l, int i);
void ListInsert(sqlist &l, stu e);
void ListInsert(sqlist &l, int i, stu e);
bool ListDelete(sqlist &l, int i, stu &e); // 按序号删除元素
void PrintList(sqlist &l);
void DestroyList(sqlist &l);

void InitList(sqlist &l) {
  InitList(l, InitSize);
}

void InitList(sqlist &l, int size) {
  sqlist mysqlist;
  mysqlist.Length = 0;
  mysqlist.data = (stu *)malloc(sizeof(stu) * size);
  l = mysqlist;
}

int Length(sqlist &l) {
  return l.Length;
}

int LocateElem(sqlist l, stu e) {
  int index = -1;
  for (int i = 0; i < l.Length; i++)
  {
    if (!strcmp(l.data[i].name, e.name) || l.data[i].age == e.age) {
      index = i;
      break;
    }
  }
  return index;
}

stu GetElem(sqlist l, int i) {
  if (i >=0 && i <= l.Length) {
    return l.data[i];
  } else {
    // 越界
    return stu();
  }
}

void ListInsert(sqlist &l, stu e) {
  ListInsert(l, l.Length, e);
}

void ListInsert(sqlist &l, int i, stu e) {
  int current_list_max_length = malloc_usable_size(l.data) / sizeof(l.data[0]);
  if (l.Length >= current_list_max_length)
  {
    // 溢出，扩容策略为容量×2
    sqlist new_sqlist;
    new_sqlist.Length = 0;
    new_sqlist.data = (stu *)malloc(sizeof(stu) * current_list_max_length * 2);
    for (int j = 0; j < l.Length + 1; j++) {
      if (j == i) {
        new_sqlist.data[j].name = e.name;
        new_sqlist.data[j].age = e.age;
      } else {
        new_sqlist.data[j].name = l.data[j < i ? j : j - 1].name;
        new_sqlist.data[j].age = l.data[j < i ? j : j - 1].age;
      }
      new_sqlist.Length++;
    }
    l = new_sqlist;
  }
  else
  {
    for (int j = l.Length; j > i; j--) {
      l.data[j].name = l.data[j-1].name;
      l.data[j].age = l.data[j-1].age;
    }
    l.data[i].name = e.name;
    l.data[i].age = e.age;
    l.Length++;
  }
}

bool ListDelete(sqlist &l, int i, stu &e) {
  if (i < 0 || i > l.Length)
    return false;
  for (int j = i; j < l.Length - 2; j++) {
    l.data[j].name = l.data[j + 1].name;
    l.data[j].age = l.data[j + 1].age;
  }
  l.Length--;
  return true;
}

void PrintList(sqlist &l) {
  for (int i = 0; i < l.Length; i++) {
    printf("[%02d] 姓名: %s, 年龄: %d\n", i+1, l.data[i].name, l.data[i].age);
  }
  printf("\n");
}

void DestroyList(sqlist &l) {
  if (l.data == NULL)
    return;
  free(l.data);
}

void TestSequenceList() {
  sqlist mySqlist;
  InitList(mySqlist, 3);
  printf("当前顺序表长度(有效)为: %d\n", mySqlist.Length);
  // 插入以及动态扩容
  stu e, e1;
  e.name = (char*)"Mary";
  e.age = 18;
  e1.name = (char*)"Billy";
  e1.age = 19;
  for (int i = 0; i < 10; i++) {
    ListInsert(mySqlist, e);
    e.age++;
  }
  ListInsert(mySqlist, 3, e1);
  // 打印
  PrintList(mySqlist);
  printf("当前顺序表长度(有效)为: %d\n\n", mySqlist.Length);
  // 按位查找
  stu mystu = GetElem(mySqlist, 3);
  printf("4号学生姓名: %s, 年龄: %d\n\n", mystu.name, mystu.age);
  // 按关键字查找
  stu locateByAge;
  locateByAge.age = 19;
  int index = LocateElem(mySqlist, locateByAge);
  printf("第一个年龄为19的人是: %s，序号为: %d\n\n", mySqlist.data[index].name, index);
  // 删除
  ListDelete(mySqlist, 3, e1);
  PrintList(mySqlist);
  printf("当前顺序表长度(有效)为: %d\n\n", mySqlist.Length);
  DestroyList(mySqlist);
  printf("\n");
}

int main() {
  TestSequenceList();
  return 0;
}

P19 综合应用题

cpp

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define MaxSize 30 // 定义顺序表的MAX长度

typedef struct SequenceList {
  int* data;
  int Length; // 有效长度
} sqlist;

void InitList(sqlist &L);
int Length(sqlist &L);
int LocateElem(sqlist L, int e); // 查找第一个包含e中元素的项
int GetElem(sqlist L, int i);
void ListInsert(sqlist &L, int e);
void ListInsert(sqlist &L, int i, int e);
bool ListDelete(sqlist &L, int i, int &e); // 按序号删除元素
void PrintList(sqlist &L);
void DestroyList(sqlist &L);

void InitList(sqlist &L) {
  sqlist mysqlist;
  mysqlist.data = (int*)malloc(sizeof(int) * MaxSize);
  mysqlist.Length = 0;
  L = mysqlist;
}

int Length(sqlist &L) {
  return L.Length;
}

int LocateElem(sqlist L, int e) {
  int pos = -1;
  for (int i = 0; i < L.Length; i++)
  {
    if (L.data[i] == e) {
      pos = i;
      break;
    }
  }
  return pos;
}

int GetElem(sqlist L, int i) {
  i--;
  if (i < 0 || i > L.Length ) {
    printf("下标越界\n");
    return -1;
  }
  return L.data[i-1];
}

void ListInsert(sqlist &L, int e) {
  if (L.Length >= MaxSize) {
    printf("容量不足, %d插入失败\n", e);
    return;
  }
  L.data[L.Length] = e;
  L.Length++;
}

void ListInsert(sqlist &L, int i, int e) {
  if (L.Length >= MaxSize) {
    printf("容量不足, %d插入失败\n", e);
    return;
  }
  for (int j = L.Length; j > i - 1; j--) {
    L.data[j] = L.data[j - 1];
  }
  L.data[i - 1] = e;
  L.Length++;
}

bool ListDelete(sqlist &L, int i, int &e) {
  if (i < 0 || i > L.Length ) {
    printf("下标越界\n");
    return false;
  }
  e = L.data[i-1];
  for (int j = i; j < L.Length; j++)
  {
    L.data[j-1] = L.data[j];
  }
  L.Length--;
  return true;
}

void PrintList(sqlist &L) {
  printf("[ ");
  for (int j = 0; j < L.Length; j++) {
    printf("%d  ", L.data[j]);
  }
  printf("]\n");
}

void DestroyList(sqlist &L) {
  if (L.data != NULL) {
    free(L.data);
  }
}

bool Del_min_P19_1(sqlist &L, int &del_val) {
  if (L.Length < 1) {
    printf("顺序表为空!\n");
    return false;
  }
  int min_index = 0;
  for (int i = 1; i < L.Length; i++) {
    if (L.data[i] < L.data[min_index]) {
      min_index = i;
    }
  }
  del_val = L.data[min_index];
  L.data[min_index] = L.data[L.Length - 1];
  L.Length--;
  return true;
}

void Reverse_P19_2(sqlist &L) {
  int temp;
  for (int i = 0; i <= (L.Length - 1) / 2; i++) {
    temp = L.data[L.Length - 1 - i];
    L.data[L.Length - 1 - i] = L.data[i];
    L.data[i] = temp;
  }
}

void Del_value_equal_x_P19_3_method_1(sqlist &L, int x) {
  int x_times = 0;
  for (int i = 0; i < L.Length; i++)
  {
    if (L.data[i] != x) {
      L.data[i - x_times] = L.data[i];
    }
    else
    {
      x_times++;
    }
  }
  L.Length -= x_times;
}

void Del_value_equal_x_P19_3_method_2(sqlist &L, int x) {
  int k = 0;
  for (int i = 0; i < L.Length - 1; i++) {
    if (L.data[i] != x) {
      L.data[k] = L.data[i];
      k++;
    }
  }
  L.Length = k;
}

bool Del_between_s_t_with_sorted_list_P19_4(sqlist &L, int s, int t) {
  if (s >= t) {
    printf("s、t不合理\n");
    return false;
  }
  if (L.Length < 1) {
    printf("顺序表为空\n");
    return false;
  }
  int i, j;
  for (i = 0; i < L.Length && L.data[i] < s; i++);
  for (j = 0; j < L.Length && L.data[j] <= t; j++);
  for (; j < L.Length; i++, j++)
  {
    L.data[i] = L.data[j];
  }
  L.Length = i;
  return true;
}

bool Del_between_s_t_P19_5_method1(sqlist &L, int s, int t) {
  if (s >= t) {
    printf("s、t不合理\n");
    return false;
  }
  if (L.Length < 1) {
    printf("顺序表为空\n");
    return false;
  }
  // l为无序顺序表
  int between_s_t_times = 0;
  for (int i = 0; i < L.Length; i++) {
    if (L.data[i] >= s && L.data[i] <= t) {
      between_s_t_times++;
    } else {
      L.data[i - between_s_t_times] = L.data[i];
    }
  }
  L.Length -= between_s_t_times;
}

bool Del_between_s_t_P19_5_method2(sqlist &L, int s, int t) {
  if (s >= t) {
    printf("s、t不合理\n");
    return false;
  }
  if (L.Length < 1) {
    printf("顺序表为空\n");
    return false;
  }
  // l为无序顺序表
  int k = 0;
  for (int i = 0; i < L.Length; i++)
  {
    if (L.data[i] < s || L.data[i] > t) {
      L.data[k] = L.data[i];
      k++;
    }
  }
  L.Length = k;
}

bool Del_same_P19_6(sqlist &L) {
  if (L.Length < 1) {
    return false;
  }
  int del_times = 0;
  for (int i = 0; i < L.Length; i++)
  {
    if (L.data[i] == L.data[i+1]) {
      del_times++;
    } else {
      L.data[i - del_times] = L.data[i];
    }
  }
  L.Length -= del_times;
  return true;
}

bool Combine_two_sorted_list_P19_7(sqlist L1, sqlist L2, sqlist &L) {
  if (L1.Length + L2.Length > MaxSize)
  {
    return false;
  }
  int i = 0, j = 0, k = 0;
  while(i < L1.Length && j < L2.Length)
  {
    if (L1.data[i] < L2.data[j]) {
      // L.data[k++] = L1.data[i++] 等价于 L.data[k] = L1.data[i]; k++; i++;
      L.data[k++] = L1.data[i++];
    }
    else
    {
      L.data[k++] = L2.data[j++];
    }
  }
  while (i < L1.Length) {
    L.data[k++] = L1.data[i++];
  }
  while (j < L2.Length) {
    L.data[k++] = L2.data[j++];
  }
  L.Length = k;
  return true;
}

void Exchange_P19_8(sqlist &L, int m, int n) {
  class {
    public:
      void run(sqlist &L, int start, int end) {
        if (L.Length < 1 || start < 0 || start >= end || end > L.Length) {
          return;
        }
        int temp;
        for (int i = 0; i < (end - start + 1) / 2; i++)
        {
          temp = L.data[start + i];
          L.data[start + i] = L.data[end - i];
          L.data[end - i] = temp;
        }
      }
  } Reverse;
  Reverse.run(L, 0, L.Length - 1);
  Reverse.run(L, 0, n - 1);
  Reverse.run(L, n, m + n - 1);
}

void Search_X_Exchange_Or_Insert_P20_9(sqlist &L, int x) {
  if (L.Length < 1) {
    return;
  }
  int low = 0;
  int high = L.Length - 1;
  int mid;
  while (low <= high)
  {
    mid = (low + high) / 2;
    if (x == L.data[mid]) break;
    if (x > L.data[mid])
    {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  if (L.data[mid] == x)
  {
    if (mid < L.Length - 1) {
      int temp = L.data[mid + 1];
      L.data[mid + 1] = L.data[mid];
      L.data[mid] = temp;
    }
  }
  else
  {
    for (int i = L.Length - 1; i >= low; i--) L.data[i + 1] = L.data[i];
    L.data[low] = x;
    L.Length++;
  }
}

void P20_10(int arr[], int n, int p) {
  class {
    public:
      int t;
      void run(int arr[], int start, int end) {
        for (int i = 0; i <= (end - start - 1) / 2; i++) {
          t = arr[start + i];
          arr[start + i] = arr[end - i];
          arr[end - i] = t;
        }
      }
  } Reverse;
  Reverse.run(arr, 0, n - 1);
  Reverse.run(arr, 0, n - p - 1);
  Reverse.run(arr, n - p, n - 1);
}

// 非最优解，该方法T(n) = O(n)
int P20_11_MyAnswer(int A[], int B[], int combineAB[], int n) { // n为A或B的长度
  int i = 0, j = 0, k = 0;
  while (i < n && j < n) {
    if (A[i] < B[j]) {
      combineAB[k++] = A[i++];
    } else {
      combineAB[k++] = B[j++];
    }
  }
  while (i < n) {
    combineAB[k++] = A[i++];
  }
  while (j < n) {
    combineAB[k++] = B[j++];
  }
  return combineAB[(2 * n - 1) / 2];
}

// 参考答案
int P20_11_Correct(int A[], int B[], int n) {
  int start1 = 0, end1 = n-1;
  int start2 = 0, end2 = n-1;
  int mid1, mid2;
  while (start1 <= end1 && start2 <= end2)
  {
    mid1 = (start1 + end1) / 2;
    mid2 = (start2 + end2) / 2;
    if (A[mid1] == B[mid2]) {
      return A[mid1];
    } else if (A[mid1] > B[mid2]) {
      // 扔掉A中较大的一半 不包括a
      // 扔掉B中较小的一半 包括b
      // 对于有奇数个元素的数组，去除同等数量的元素时，恰好可以以mid为分界线
      // 对于有偶数个元素的数组，若去除同等数量的元素时，其中一个数组要多去掉一个，这里我们始终让舍弃较小的一半者多舍弃一个，这样保证A、B舍弃的元素数相同
      if ((start1 + end1) % 2 == 0) { // 元素个数为奇数
        end1 = mid1;
        start2 = mid2;
      } else { // 元素个数为偶数，需要多舍掉B一个
        end1 = mid1;
        start2 = mid2 + 1;
      }
    }
    else
    {
      // 扔掉A中较小的一半 包括a
      // 扔掉B中较大的一半 不包括b
      if ((start1 + end1) % 2 == 0) { // 元素个数为奇数
        start1 = mid1;
        end2 = mid2;
      } else { // 元素个数为偶数，需要多舍掉B一个
        start1 = mid1 + 1;
        end2 = mid2;
      }
    }
  }
  return A[start1] < B[start2] ? A[start1] : B[start2];
}

// T(n)=O(n)最优，S(n)=O(n)非最优
void P20_12_MyAnswer(int arr[], int n) {
  int counter[n] = {0};
  int main_number = arr[0];
  for (int i = 0; i < n; i++)
  {
    counter[arr[i]]++;
  }
  for (int i = 0; i < n; i++) {
    if (counter[i] > counter[main_number]) {
      main_number = i;
    }
    if (counter[main_number] > n / 2) {
      break;
    }
  }
  printf("主元素为: %d\n", (counter[main_number] > n / 2) ? main_number : -1);
}

// 参考答案, T(n) = O(1)
// 只有一个主元素，且主元素至少连续出现两次
void P20_12_Correct(int A[], int n) {
  int i, c, count = 1;
  c = A[i];
  for (int i = 1; i < n; i++) {
    if (A[i] != c) {
      count--;
      if (count < 1) {
        c = A[i];
      }
    } else {
      count++;
    }
  }
  count = 0;
  // 确定c是否为主元素
  for (int i = 0; i < n; i++) {
    if (A[i] == c) {
      count++;
    }
  }
  printf("主元素为: %d\n", (count > n / 2) ? c : -1);
}

// 非最优速度
// T(n)=O(n^2)
void P21_13_MyAnswer(int arr[], int n) {
  int no_see_min = 0;
  int temp;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  for (int i = 1; i < n; i++) {
    if (arr[i] > 0 && arr[i] - 1 != arr[i - 1]) {
      no_see_min = arr[i] - 1;
      break;
    }
  }
  printf("未出现的最小正整数: %d\n", no_see_min == 0 ? arr[n - 1] + 1 : no_see_min);
}

// 参考答案
// 速度最优先: T(n)=O(n)
void P21_13_Correct(int arr[], int n) {
  // counter[0]表示1出现的次数，ounter[n-1]表示n出现的次数，...
  // 如果数组长度为n，并且数组元素集合不完全是1到n这n个数，那么表示1-n中至少有一个数，在数组中没有出现
  int counter[n] = {0};
  int no_see_min = 0;
  for (int i = 0; i < n; i++)
  {
    if (arr[i] >= 1 && arr[i] <= n) {
      counter[arr[i] - 1]++;
    }
  }
  for (int i = 0; i < n; i++) {
    if (counter[i] == 0) {
      no_see_min = i + 1;
      break;
    }
  }
  printf("未出现的最小正整数: %d\n", no_see_min == 0 ? arr[n - 1] + 1 : no_see_min);
}

int main() {
  sqlist mysqlist;
  InitList(mysqlist);
  // [ 1  2  3  4  5  6  6  7  8  8  ] 该数组通用所有题目
  for (int i = 1; i < 9; i++) {
    if (i == 6 || i == 8) { // 6、8插入双次
      ListInsert(mysqlist, i);
    }
    ListInsert(mysqlist, i);
  }
  PrintList(mysqlist);
  // ================================
  // int del_value;
  // Del_min_P19_1(mysqlist, del_value);
  // printf("删除了最小元素: %d\n", del_value);
  // ================================
  // Reverse_P19_2(mysqlist);
  // ================================
  // Del_value_equal_x_P19_3_method_1(mysqlist, 6);
  // Del_value_equal_x_P19_3_method_2(mysqlist, 6);
  // ================================
  // Del_between_s_t_with_sorted_list_P19_4(mysqlist, 4, 6);
  // ================================
  // Del_between_s_t_P19_5_method1(mysqlist, 4, 6);
  // Del_between_s_t_P19_5_method2(mysqlist, 4, 6);
  // ================================
  // Del_same_P19_6(mysqlist);
  // ================================
  // sqlist combine, combine1;
  // InitList(combine);
  // InitList(combine1);
  // Combine_two_sorted_list_P19_7(mysqlist, mysqlist, combine);
  // Combine_two_sorted_list_P19_7(mysqlist, combine, combine1);
  // PrintList(combine1);
  // ================================
  // 设a1 a2 ... an = mysqlist
  // 设b1 b2 ... bm = mysqlist
  // 则 a1 a2 ... an b1 b2 ... bm = mysqlist mysqlist
  // for (int i = 1; i < 9; i++) {
  //   if (i == 6 || i == 8) { // 6、8插入双次
  //     ListInsert(mysqlist, i);
  //   }
  //   ListInsert(mysqlist, i);
  // }
  // int m = mysqlist.Length / 2;
  // int n = mysqlist.Length / 2;
  // Exchange_P19_8(mysqlist, m, n);
  // ================================
  // Search_X_Exchange_Or_Insert_P20_9(mysqlist, 5);
  // Search_X_Exchange_Or_Insert_P20_9(mysqlist, 9);
  // ================================
  // int n = 10;
  // int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
  // P20_10(arr, n, 3);
  // printf("[ ");
  // for (int i = 0; i < n; i++) {
  //   printf("%d  ", arr[i]);
  // }
  // printf("]\n");
  // ================================
  // int n = 10;
  // int A[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
  // int B[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
  // int combineAB[n * 2];
  // // int mid = P20_11_MyAnswer(A, B, combineAB, n);
  // int mid = P20_11_Correct(A, B, n);
  // printf("mid = %d\n", mid);
  // ================================
  // int n = 10;
  // int test1[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
  // int test2[] = {6, 6, 3, 6, 5, 6, 6, 7, 8, 6};
  // // P20_12_MyAnswer(test1, n);
  // // P20_12_MyAnswer(test2, n);
  // P20_12_Correct(test1, n);
  // P20_12_Correct(test2, n);
  // ================================
  // int n = 10;
  // int test1[] = {-1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
  // int test2[] = {-1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 8};
  // // P21_13_MyAnswer(test1, n);
  // // P21_13_MyAnswer(test2, n);
  // P21_13_Correct(test1, n);
  // P21_13_Correct(test2, n);
  // ================================
  PrintList(mysqlist);

  return 0;
}

单链表

双向链表

循环单链表

循环双向链表

静态链表

图

邻接矩阵无向图操作及BFS、DFS

cpp

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

// 邻接矩阵存储图
#define MaxVertex 100

typedef char VertexType;
typedef int EdgeType;
typedef struct {
  VertexType Vex[MaxVertex]; // 顶点标
  EdgeType Edge[MaxVertex][MaxVertex]; // 邻接矩阵，边表
  int vernum, arcnum; // 图的当前定点数、弧数
} Graph;

void PrintMatrix(Graph &graph);                                    // 打印邻接矩阵
int InsertVertex(Graph &graph, VertexType vertexName);             // 插入顶点
int DeleteVertex(Graph &graph, VertexType vertexName);             // 删除顶点
int FindVertexIndex(Graph &graph, VertexType vertexName);           // 查找节点对应的索引号，没找到返回-1
int AddEdge(Graph &graph, VertexType x, VertexType y);             // 添加一条无向边
int RemoveEdge(Graph &graph, VertexType x, VertexType y);          // 移除一条无向边
VertexType FirstNeighbor(Graph &graph, VertexType x);              // 某点的第一个邻接点
VertexType NextNeighbor(Graph &graph, VertexType x, VertexType y); // 某点除y以外的下一个邻接点
void BFS(Graph &graph);                                            // 广度优先搜索
void BFS_1(Graph &graph);                                          // 广度优先搜索(不借助辅助函数)
void DFS(Graph &graph, int v);                                     // 深度优先搜索
void Visit(Graph &graph, VertexType x);                            // 访问节点

VertexType NextNeighbor(Graph &graph, VertexType x, VertexType y) {
  // 要保证上一个节点就是y，才可以
  int index = FindVertexIndex(graph, x);
  if (index > -1) {
    char pre = '\0';
    for (int i = 0; i < graph.vernum; i++)
    {
      if (graph.Edge[index][i] == 1) {
        if (pre == y) {
          return graph.Vex[i];
        }
        pre = graph.Vex[i];
      }
    }
    return '\0';
  } else {
    printf("节点%c不存在\n", x);
    return '\0';
  }
}

VertexType FirstNeighbor(Graph &graph, VertexType x) {
  int index = FindVertexIndex(graph, x);
  if (index > -1) {
    for (int i = 0; i < graph.vernum; i++) {
      if (graph.Edge[index][i] == 1) {
        return graph.Vex[i];
      }
    }
    return '\0';
  } else {
    printf("节点%c不存在\n", x);
    return '\0';
  }
}

int DeleteVertex(Graph &graph, VertexType vertexName) {
  int index = FindVertexIndex(graph, vertexName);
  if (index > -1) {
    // 右侧向左平移覆盖删除节点的整列
    for (int i = 0; i < graph.vernum; i++) {
      for (int j = index; j < graph.vernum-1; j++) {
        graph.Edge[i][j] = graph.Edge[i][j+1]; // 第i行j列 被 第i行j+1列的值覆盖
      }
    }
    // 下侧向上平移覆盖删除节点的整行
    for (int i = index; i < graph.vernum; i++) {
      for (int j = 0; j < graph.vernum-1; j++) {
        graph.Edge[i][j] = graph.Edge[i+1][j]; // 第i行j列 被 第i+1行j列的值覆盖
      }
    }
    // 将目前有效范围内的矩阵最外侧全部置0
    for (int i = 0; i < graph.vernum; i++) {
      graph.Edge[graph.vernum - 1][i] = 0;
      graph.Edge[i][graph.vernum - 1] = 0;
    }
    // 将删除节点后面的节点向前移
    for (int i = index; i < graph.vernum - 1; i++) {
      graph.Vex[i] = graph.Vex[i + 1];
    }
    graph.vernum--;
  } else {
    printf("要删除的节点%c不存在，请检查\n", vertexName);
    return 0;
  }
}

int FindVertexIndex(Graph &graph, VertexType vertexName) {
  int index = -1;
  for (int i = 0; i < graph.vernum; i++)
  {
    if (graph.Vex[i] == vertexName)
    {
      index = i;
      break;
    }
  }
  return index;
}

int RemoveEdge(Graph &graph, VertexType x, VertexType y) {
  int x_index = FindVertexIndex(graph, x);
  int y_index = FindVertexIndex(graph, y);
  if (x_index > -1 && y_index > -1) {
    // x y 均存在
    graph.Edge[x_index][y_index] = 0;
    graph.Edge[y_index][x_index] = 0;
    graph.arcnum--;
    return 1;
  }
  else
  {
    // 有点不存在
    printf("节点%c或%c不存在，请检查\n", x, y);
    return 0;
  }
}

int AddEdge(Graph &graph, VertexType x, VertexType y) {
  int x_index = FindVertexIndex(graph, x);
  int y_index = FindVertexIndex(graph, y);
  if (x_index > -1 && y_index > -1) {
    // x y 均存在
    graph.Edge[x_index][y_index] = 1;
    graph.Edge[y_index][x_index] = 1;
    graph.arcnum++;
    return 1;
  }
  else
  {
    // 有点不存在
    printf("节点%c或%c不存在，请检查\n", x, y);
    return 0;
  }
}

void PrintMatrix(Graph &graph) {
  printf("邻接矩阵为:\n");
  printf("  ");
  // 打印表头
  for (int i = 0; i < graph.vernum; i++)
  {
    printf("%c ", graph.Vex[i]);
  }
  printf("\n");
  for (int i = 0; i < graph.vernum; i++)
  {
    printf("%c ", graph.Vex[i]);
    for (int j = 0; j < graph.vernum; j++) {
      printf("%d ", graph.Edge[i][j]);
    }
    printf("\n");
  }
  printf("\n");
}

int InsertVertex(Graph &graph, VertexType vertexName) {
  // 顶点名称不允许重复
  for (int i = 0; i < graph.vernum; i++) {
    if (graph.Vex[i] == vertexName) {
      printf("顶点插入重复\n");
      return 0;
    }
  }
  graph.Vex[graph.vernum++] = vertexName;
  return 1;
}

void Visit(Graph &graph, VertexType x) {
  if (FindVertexIndex(graph, x) > -1) {
    printf("%c", x);
  }
}

void BFS(Graph &graph) {
  printf("广度优先遍历(1): ");
  queue<VertexType> Q;
  bool visited[graph.vernum];
  Q.push(graph.Vex[0]);
  Visit(graph, Q.front());
  visited[FindVertexIndex(graph, Q.front())] = true;
  while (!Q.empty())
  {
    VertexType v = Q.front();
    Q.pop();
    int times = 0;
    for (VertexType w = FirstNeighbor(graph, v);; w = NextNeighbor(graph, v, w))
    {
      // 当前节点的下一个节点循环到FirstNeighbor 或者 当前节点无下一个节点时，循环中断
      if (w == FirstNeighbor(graph, v) && times++ > 0 || w == '\0') break;
      if (!visited[FindVertexIndex(graph, w)]) {
        Visit(graph, w);
        visited[FindVertexIndex(graph, w)] = true;
        Q.push(w);
      }
    }
  }
  printf("\n");
}

void BFS_1(Graph &graph) {
  printf("广度优先遍历(2): ");
  queue<int> Q;
  bool visited[graph.vernum];
  Q.push(0);
  printf("%c", graph.Vex[0]);
  visited[0] = true;
  while (!Q.empty())
  {
    int v = Q.front();
    Q.pop();
    for (int i = 0; i < graph.vernum; i++)
    {
      if (graph.Edge[v][i] && !visited[i]) {
        printf("%c", graph.Vex[i]);
        visited[i] = true;
        Q.push(i);
      }
    }
  }
  printf("\n");
}

bool visited[MaxVertex];
void DFS(Graph &graph, int v) {
  printf("%c", graph.Vex[v]);
  visited[v] = true;
  int times = 0;
  for (VertexType w = FirstNeighbor(graph, graph.Vex[v]);; w = NextNeighbor(graph, graph.Vex[v], w)) {
    // 当前节点的下一个节点循环到FirstNeighbor 或者 当前节点无下一个节点时，循环中断
    if (w == FirstNeighbor(graph, graph.Vex[v]) && times++ > 0 || w == '\0') break;
    int w_index = FindVertexIndex(graph, w);
    if (!visited[w_index])
      DFS(graph, w_index);
  }
}

int main() {
  // 初始化一个无向图 P227 图6.11
  Graph graph;
  InsertVertex(graph, 'A');
  InsertVertex(graph, 'B');
  InsertVertex(graph, 'C');
  InsertVertex(graph, 'D');
  InsertVertex(graph, 'E');
  InsertVertex(graph, 'F');
  InsertVertex(graph, 'G');
  InsertVertex(graph, 'H');
  AddEdge(graph, 'A', 'B');
  AddEdge(graph, 'A', 'C');
  AddEdge(graph, 'B', 'D');
  AddEdge(graph, 'B', 'E');
  AddEdge(graph, 'C', 'F');
  AddEdge(graph, 'C', 'G');
  AddEdge(graph, 'D', 'E');
  AddEdge(graph, 'D', 'H');
  AddEdge(graph, 'E', 'H');

  // PrintMatrix(graph);
  // DeleteVertex(graph, 'B');
  // RemoveEdge(graph, 'A', 'C');

  PrintMatrix(graph);

  // char vex = 'B';
  // char res = FirstNeighbor(graph, vex);
  // printf("%c节点的首个邻接节点为%c\n", vex, res);
  // char res1 = NextNeighbor(graph, vex, res);
  // printf("%c节点的下一个邻接节点为%c\n", vex, res1);
  // printf("%c节点的下下一个邻接节点为%c\n", vex, NextNeighbor(graph, vex, res1));

  BFS(graph);
  BFS_1(graph);
  printf("深度优先遍历(1): ");
  DFS(graph, 0);
  printf("\n");

  return 0;
}

查找

二分查找/折半查找(Binary Search)

• mid = (low+high)/2 向下取整，即强转int即可
• T(n) = O(log2n)

cpp

#include <stdio.h>
#include <math.h>
#include "../tools.h"

/* 二分查找 */
int binary_search(int arr[], int len, int find) {
  int low = 0, high = len - 1, mid;
  while (low <= high)
  {
    mid = (low + high) / 2;
    if (find == arr[mid]) {
      return mid;
    } else if (find > arr[mid]) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

附录一

• tools.h

cpp

tools.h

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include<malloc.h>
#include <iso646.h>

#define TYPE_INT 0
#define TYPE_FLOAT 1
#define TYPE_DOUBLE 2

using namespace std;

/* ==================================== */
/* 预定义 */

template <typename T>
void printf(T *list);

template <typename T>
int count(T *list);

void* rand_list(int size, int type);

template <typename T>
void swap(T *a, T *b);

/* ==================================== */


/* 快速打印数组 */
template <typename T>
void printf(T *list)
{
  cout << "[";
  for (int i = 0; i < count(list); i++)
  {
    if (i > 0)
    {
      cout << ", ";
    }
    cout << *(list + i);
  }
  cout << "]" << endl;
}

/* 获取数组长度 */
template <typename T>
int count(T *p)
{
  return malloc_usable_size(p) / sizeof(*p) - 1;
}

/** 随机数组
 * @param int size : size of array
 * @param int type : the array-item's type
 * @param bool can_repeat : repeat number in the array
 */
void* rand_list(int len, int type, bool can_repeat)
{
  srand((unsigned)time(NULL));
  if (type == TYPE_INT && len < 10)
  {
    int *p = (int*)malloc(sizeof(int) * len);
    int rand_number = 0;
    int repeat_flag = 0;
    int sgn = 0; // 随机符号，0正 1负
    for (int i = 0; i < len; i++)
    {
      regenerate:
      sgn = rand() % (2 - 0) + 0;
      rand_number = rand() % (10 - 0) + 0;
      rand_number = (sgn == 0 ? rand_number : rand_number * (-1));
      if (can_repeat)
      {
        // 允许数字重复
        *(p + i) = rand_number;
      }
      else
      {
        repeat_flag = 0;
        for (int j = 0; j < i; j++)
        {
          if (*(p + j) ==  rand_number) {
            repeat_flag = 1;
            break;
          }
        }
        if (repeat_flag) {
          // 重复了
          goto regenerate;
        } else {
          *(p + i) = rand_number;
        }
      }
    }
    return p;
  }
  else if (type == TYPE_FLOAT)
  {
    return NULL;
  }
  else if (type == TYPE_DOUBLE)
  {
    return NULL;
  }
}

/* 交换参数值 */
template <typename T>
void swap(T *a, T *b) {
  T temp = *a;
  *a = *b;
  *b = temp;
}