数据结构与算法

学习时间：2021年9月16日21:40:03

作者：聪头

参考：王道考研2022–数据结构篇

1.绪论

数据

n个数据对象
- n个数据元素
  - n个数据项

算法5个重要特性

有穷性
确定性
可行性
输入
输出

2.线性表

2.1 顺序表

#pragma once
//顺序表实现
#include <stdlib.h>

#define MAX_SIZE 10

using namespace std;

typedef struct  
{
  int * data;
  int length, MaxSize;
}SqList;

//初始化顺序表
void InitList(SqList &L)
{
  L.MaxSize = MAX_SIZE;
  L.length = 0;
  L.data = (int *)malloc(sizeof(int) * L.MaxSize);
}
//销毁顺序表
void DestroyList(SqList &L)
{
  L.MaxSize = 0;
  L.length = 0;
  free(L.data);
}
//插入元素
bool ListInsert(SqList &L, int i, int e)
{
  if (i < 1 || i > L.length + 1)
    return false;
  if (L.length >= L.MaxSize)
    return false;
  for (int j = L.length; j  >= i; j--)
  {
    L.data[j] = L.data[j - 1];
  }
  L.data[i - 1] = e;
  L.length++;
  return true;
}
//删除元素
bool ListDelete(SqList &L, int i, int &e)
{
  if (i < 1 || i > L.length) 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;
}
//按值查找，返回位序
int LocateElem(SqList &L, int e)
{
  for (int i = 0; i < L.length; i++)
  {
    if (e == L.data[i])
      return i + 1;
  }
  return 0;
}
//打印输出
void PrintList(SqList L)
{
  cout << "打印输出: " << endl;
  for (int i = 0; i < L.length; i++)
  {
    cout << L.data[i] << endl;
  }
  cout << "------------------" << endl;
}

2.2 链表

#pragma once
//单链表实现
#include <stdlib.h>
#include <stdio.h>

typedef struct LNode
{
  int data;
  LNode *next;
}LNode, *LinkList;

//带头结点的链表初始化
void InitLinkList(LinkList &L)
{
  L = (LNode *)malloc(sizeof(LNode));
  L->next = NULL;
}
//不带头结点的链表初始化
void InitLinkListNoHead(LinkList &L)
{
  L = NULL;
}

///插入
//带头结点 按位序插入
bool LinkListInsert(LinkList &L, int i, int e)
{
  if (i < 1) return false;
  int j = 0;	//当前p是第几个结点
  LNode *p = L;	//指针p指向当前扫描到的结点;
  while (p != NULL && j < i - 1)
  {
    p = p->next;
    j++;
  }
  if (p == NULL)
  {
    //i值非法
    return false;
  }
  LNode *s = (LNode*)malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

//不带头结点 按位序插入
bool LinkListInsertNoHead(LinkList &L, int i, int e)
{
  if (i < 1) return false;
  //第一个位序单独处理
  if (i == 1)
  {
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = L;
    L = s;
    return true;
  }
  int j = 1;	//当前p是第几个结点
  LNode *p = L;	//指针p指向当前扫描到的结点;
  while (p != NULL && j < i - 1)
  {
    p = p->next;
    j++;
  }
  if (p == NULL)
  {
    //i值非法
    return false;
  }
  LNode *s = (LNode*)malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

//指定结点的后插操作
bool InsertNextNode(LNode *p, int e)
{
  if (p == NULL) return false;
  LNode *s = (LNode*)malloc(sizeof(LNode));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

//指定结点的前插操作（交换值）
bool InsertPriorNode(LNode *p, int e)
{
  if (p == NULL) return false;
  LNode *s = (LNode*)malloc(sizeof(LNode));
  //交换值
  int temp = p->data;
  p->data = e;
  s->data = temp;
  //修改指针
  s->next = p->next;
  p->next = s;
  return true;
}

///删除
//带头结点 按位序删除
bool LinkListDelete(LinkList &L, int i, int &e)
{
  if (i < 1) return false;
  int j = 0;
  LNode *p = L;
  while (p != NULL && j < i - 1)
  {
    p = p->next;
    j++;
  }
  if (p == NULL) return false;
  LNode *q = p->next;
  if (q == NULL) return false;
  e = q->data;
  p->next = q->next;
  free(q);
  return true;

}

//指定结点删除（交换值）
bool DeleteNode(LNode *p)
{
  if (p == NULL) return false;
  LNode *q = p->next;
  if (q == NULL) return false;
  p->data = q->data;
  p->next = q->next;
  free(q);
  return true;
}

///查找
//带头结点 按位序查找
LNode * GetElem(LinkList L, int i)
{
  if (i < 0) return false;
  LNode *p;
  int j = 0;
  p = L;
  while (p != NULL && j < i)
  {
    p = p->next;
    j++;
  }
  return p;
}
//带头结点 按值查找
LNode * LocateElem(LinkList L, int e)
{
  LNode *p = L->next;
  while (p != NULL && p->data != e)
  {
    p = p->next;
  }
  return p;
}

///单链表的建立
//带头结点 尾插法
void LinkListTailInsert(LinkList &L)
{
  cout << "带头结点 尾插法建表: " << endl;
  L = (LinkList)malloc(sizeof(LNode));
  LNode *r = L;
  LNode *s = NULL;
  int e;
  scanf("%d", &e);
  while (e != 9999)
  {
    s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    r->next = s;
    r = s;
    scanf("%d", &e);
  }
  if(s != NULL)
    s->next = NULL;
}

//带头结点 头插法
void LinkListHeadInsert(LinkList &L)
{
  cout << "带头结点 头插法建表: " << endl;
  L = (LinkList)malloc(sizeof(LNode));
  L->next = NULL;
  LNode *s;
  int e;
  scanf("%d", &e);
  while (e != 9999)
  {
    s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = L->next;
    L->next = s;
    scanf("%d", &e);
  }
}

///拓展
//带头结点 原地逆置
void LinkListReverse(LinkList &L)
{
  int length = 0;
  LNode *p = L;			//当前结点
  LNode *q = NULL;  //当前结点的前一个结点

  //找到链表最后一个结点同时获取链表长度
  while (p->next != NULL)
  {
    q = p;
    p = p->next;
    length++;
  }

  LNode *head = L;	//经过头插法后的链表头结点
  for (int i = 0; i < length; i++)
  {
    q->next = NULL;
    p->next = head->next;
    head->next = p;
    head = p;
    while (p->next != NULL)
    {
      q = p;
      p = p->next;
    }
  }
}

///打印
//带头结点 打印
void PrintLinkList(LinkList L)
{
  LNode *p = L->next;
  cout << "带头结点的链表打印: " << endl;
  while (p != NULL)
  {
    cout << p->data << endl;
    p = p->next;
  }
}

2.3 双链表

有两个指针prior和next，分别指向前驱和后继

#pragma once
#include <stdio.h>
#include <stdlib.h>
//双链表实现
typedef struct DLNode
{
  int data;
  DLNode *next;
  DLNode *prior;
}DLNode, *DLinkList;

//初始化
void DLinkListInit(DLinkList &DL)
{
  DL = (DLinkList)malloc(sizeof(DLNode));
  DL->next = NULL;
  DL->prior = NULL;
}

//带头结点 插入
bool DLinkListInsert(DLinkList &DL, int i, int e)
{
  if (i < 1) return false;
  DLNode* p = DL;
  int j = 0;
  //找到插入结点的前一个结点
  while (p != NULL && j < i - 1)
  {
    p = p->next;
    j++;
  }
  if (p == NULL) return false;

  DLNode* s = (DLNode*)malloc(sizeof(DLNode));
  s->data = e;
  s->next = p->next;
  s->prior = p;
  if (p->next != NULL)
    p->next->prior = s;
  p->next = s;
  return true;
}

//带头结点 删除
bool DLinkListDelete(DLinkList &DL, int i, int &e)
{
  if (i < 1) return false;
  DLNode* p = DL;
  int j = 0;
  //找到删除结点的前一个结点
  while (p != NULL && j < i - 1)
  {
    p = p->next;
    j++;
  }
  if (p->next == NULL) return false;

  DLNode *q = p->next;
  p->next = q->next;
  if (q->next != NULL)
    q->next->prior = p;
  free(q);
  return true;
}

//打印
void PrintDLinkList(DLinkList DL)
{
  DLNode *p = DL->next;
  while (p != NULL)
  {
    cout << p->data << endl;
    p = p->next;
  }
  cout << "------------------" << endl;
}

3.栈和队列

3.1 顺序栈

#pragma once
//顺序栈实现
#define MAX_SIZE 10

typedef struct
{
	int data[MAX_SIZE];
	int top;
}SqStack;

//初始化
void InitStack(SqStack &S)
{
	S.top = -1;	//初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S)
{
	if (S.top == -1) return true;
	else return false;
}

//进栈
bool Push(SqStack &S, int x)
{
	if (S.top == MAX_SIZE - 1) return false; //栈满，报错
	S.data[++S.top] = x; //栈顶指针先上移，再存储数据
	return true;
}

//出栈
bool Pop(SqStack &S, int &x)
{
	if (S.top == -1) return false; //栈空，报错
	x = S.data[S.top--]; //先得到移出元素，再下移栈顶指针
	return true;
}

//读栈顶元素
bool GetTop(SqStack S, int &x)
{
	if (S.top == -1) return false;
	x = S.data[S.top];
	return true;
}

3.2 链式栈

#pragma once
#include <stdlib.h>
//链栈的实现
typedef struct  LinkNode
{
  int data;
  struct LinkNode * next;
} *LinkStack;

//不带头结点 初始化
void InitStack(LinkStack &S)
{
  S = NULL;
}

//不带头结点 判断栈空
bool StackEmpty(LinkStack S)
{
  if (S == NULL) return true;
  else return false;
}

//不带头结点 进栈
bool Push(LinkStack &S, int x)
{
  LinkNode *node = (LinkNode*)malloc(sizeof(LinkNode));
  node->data = x;
  if (S == NULL)
  {
    node->next = NULL;
  }
  else
  {
    node->next = S;
  }
  S = node;
  return true;
}

//不带头结点 出栈
bool Pop(LinkStack &S, int &x)
{
  if (S == NULL) return false; //栈空，报错
  LinkNode *node = S;
  x = node->data;
  S = S->next;
  free(node);
  return true;
}

//不带头结点 读栈顶元素
bool GetTop(LinkStack S, int &x)
{
  if (S == NULL) return false;
  x = S->data;
  return true;
}

3.3 顺序队列

#pragma once
//顺序队列实现（rear指向待插入位置）
#define MAX_SIZE 10
typedef struct
{
  int data[MAX_SIZE];
  int front, rear;
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q)
{
  Q.front = 0;
  Q.rear = 0;
}

//判空
bool QueueEmpty(SqQueue Q)
{
  if (Q.front == Q.rear) return true;
  return false;
}

//入队
bool EnQueue(SqQueue &Q, int x)
{
  if ((Q.rear + 1) % MAX_SIZE == Q.front) return false; //队满，报错
  Q.data[Q.rear] = x;
  Q.rear = (Q.rear + 1) % MAX_SIZE;
  return true;
}

//出队
bool DeQueue(SqQueue &Q, int &x)
{
  if (Q.front == Q.rear) return false; //队空，报错
  x = Q.data[Q.front];
  Q.front = (Q.front + 1) % MAX_SIZE;
  return true;
}

//读队头元素
bool GetHead(SqQueue Q, int &x)
{
  if (Q.front == Q.rear) return false; //队空，报错
  x = Q.data[Q.front];
  return true;
}

3.4 链式队列

#pragma once
#include <stdlib.h>
//链式队列实现
typedef struct LinkNode
{
  int data;
  struct LinkNode *next;
}LinkNode;

typedef struct
{
  LinkNode *front, *rear;
  int length;
}LinkQueue;

///带头结点 后缀1
//初始化1
void InitQueue1(LinkQueue &Q)
{
  Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
  Q.front->next = NULL; //初始为空
  Q.length = 0;
}

//判空1
bool IsEmpty1(LinkQueue Q)
{
  if (Q.front == Q.rear) return true;
  return false;
}

//入队1
bool EnQueue1(LinkQueue &Q, int x)
{
  LinkNode *node = (LinkNode*)malloc(sizeof(LinkNode));
  node->data = x;
  node->next = NULL;
  Q.rear->next = node;
  Q.rear = node;
  Q.length++;
  return true;
}

//出队1
bool DeQueue1(LinkQueue &Q, int &x)
{
  if (Q.front == Q.rear) return false; //队空，报错
  LinkNode *p = Q.front->next;
  x = p->data;
  Q.front->next = p->next;
  if (p == Q.rear) //正好是最后一个元素，修改尾指针
    Q.rear = Q.front;
  free(p);
  Q.length--;
  return true;
}

//获得队头值1
bool GetHead1(LinkQueue Q, int &x)
{
  if (Q.front == Q.rear) return false;
  x = Q.front->next->data;
  return true;
}

///不带头结点 后缀2
//初始化2
void InitQueue2(LinkQueue &Q)
{
  Q.front = Q.rear = NULL;
  Q.length = 0;
}

//判空2
bool IsEmpty2(LinkQueue Q)
{
  if (Q.front == NULL) return true;
  return false;
}

//入队2
bool EnQueue2(LinkQueue &Q, int x)
{
  LinkNode *node = (LinkNode*)malloc(sizeof(LinkNode));
  node->data = x;
  node->next = NULL;
  if (Q.rear == NULL) //第一个节点单独处理
  {
    Q.rear = Q.front = node;
  }
  else
  {
    Q.rear->next = node;
    Q.rear = node;
  }
  Q.length++;
  return true;
}

//出队2
bool DeQueue2(LinkQueue &Q, int &x)
{
  if (Q.front == NULL) return false; //队空，报错
  LinkNode *p = Q.front;
  x = p->data;
  Q.front = p->next;
  if (p == Q.rear) //正好是最后一个元素，修改尾指针
    Q.rear = Q.front;
  free(p);
  Q.length--;
  return true;
}

//获得队头值2
bool GetHead2(LinkQueue Q, int &x)
{
  if (Q.front == NULL) return false;
  x = Q.front->data;
  return true;
}

补充：第三章main函数

#include <iostream>
#include "SqStack.h"
//#include "LinkStack.h"
#include "SqQueue.h"
#include "LinkQueue.h"

using namespace std;

void SqStackTest();
void LinkStackTest();
void SqQueueTest();
void LinkQueueTest1();
void LinkQueueTest2();

int main()
{
  //SqStackTest();
  //LinkStackTest();
  //SqQueueTest();
  //LinkQueueTest1();
  LinkQueueTest2();
}

//顺序栈测试
void SqStackTest()
{
  SqStack stack;
  InitStack(stack);

  for (int i = 0; i < 10; i++)
  {
    Push(stack, i);
  }

  int x;
  for (int i = 0; i < 10; i++)
  {
    Pop(stack, x);
    cout << "S.top: " << stack.top << "--" << x << endl;
  }
}

//链栈测试
//void LinkStackTest()
//{
//	LinkStack stack;
//	InitStack(stack);
//
//	for (int i = 0; i < 10; i++)
//	{
//		Push(stack, i);
//	}
//
//	int x;
//	for (int i = 0; i < 10; i++)
//	{
//		Pop(stack, x);
//		cout << x << endl;
//	}
//}

//顺序队列测试
void SqQueueTest()
{
  SqQueue queue;
  InitQueue(queue);

  for (int i = 0; i < 10; i++)
  {
    EnQueue(queue, i);
  }

  int x;
  GetHead(queue, x);
  cout << "当前队头: " << x << endl;

  for (int i = 0; i < 10; i++)
  {
    DeQueue(queue, x);
    cout << x << endl;
  }
}

//链式队列测试（带头结点）
void LinkQueueTest1()
{
  LinkQueue queue;
  InitQueue1(queue);
  int x;

  for (int i = 0; i < 10; i++)
  {
    EnQueue1(queue, i);
  }

  GetHead1(queue, x);
  cout << "当前队头: " << x << endl;
  cout << "当前长度: " << queue.length << endl;

  for (int i = 0; i < 10; i++)
  {
    DeQueue1(queue, x);
    cout << "出队: " <<  x << endl;
  }

  cout << "当前长度: " << queue.length << endl;
}

//链式队列测试（不带头结点）
void LinkQueueTest2()
{
  LinkQueue queue;
  InitQueue2(queue);
  int x;

  for (int i = 0; i < 10; i++)
  {
    EnQueue2(queue, i);
  }

  GetHead2(queue, x);
  cout << "当前队头: " << x << endl;
  cout << "当前长度: " << queue.length << endl;

  for (int i = 0; i < 10; i++)
  {
    DeQueue2(queue, x);
    cout << "出队: " << x << endl;
  }

  cout << "当前长度: " << queue.length << endl;
}

实战：栈实现括号匹配

///应用
//栈实现括号匹配
bool bracketCheck(char str[], int length)
{
  SqStack S;
  InitStack(S);
  int x;

  for (int i = 0; i < length; i++)
  {
    if (str[i] == '(' || str[i] == '[' || str[i] == '{')
    {
      Push(S, str[i]);
    }
    else
    {
      if (StackEmpty(S)) return false;
      x = Pop(S, x);
      if (str[i] == ')' && (char)x != '(')
        return false;
      if (str[i] == ']' && (char)x != '[')
        return false;
      if (str[i] == '}' && (char)x != '{')
        return false;
    }
  }
  return StackEmpty(S);
}

实战：表达式求值（C#）

///使用栈实现括号匹配的检查
public static bool BracketCheck(string str)
{
  Stack<char> stack = new Stack<char>();
  char[] arr = str.ToCharArray();

  for(int i = 0; i < arr.Length; i++)
  {
    if(arr[i] == '(' || arr[i] == '[' || arr[i] == '{')
    {
      stack.Push(arr[i]);
    }
    else
    {
      if (stack.Count == 0) return false; //栈空，报错
      if (arr[i] == ')' && stack.Pop() != '(') return false;
      if (arr[i] == ']' && stack.Pop() != '[') return false;
      if (arr[i] == '}' && stack.Pop() != '{') return false;
    }
  }
  return stack.Count == 0 ? true : false; //最终栈空，成功
}

///使用栈实现表达式求值（范围0-9，中缀）
public static double CalExpression(string expr)
{
  Stack<char> opStack = new Stack<char>(); //运算符栈
  Stack<double> numStack  = new Stack<double>(); //操作数栈
  char[] strs = expr.ToCharArray();
  char op;

  for (int i = 0; i < strs.Length; i++)
  {
    if(!IsOp(strs[i])) //如果是操作数，直接压入操作数栈
    {
      numStack.Push((double) strs[i] - 48);
    }
    else //运算符
    {
      //如果栈为空，直接压入
      if(opStack.Count == 0)
      {
        opStack.Push(strs[i]);
        continue;
      }

      //如果是括号，左括号直接压入，右括号弹出运算符运算，直到左括号
      if(strs[i] == '(')
      {
        opStack.Push(strs[i]);
        continue;
      }
      else if (strs[i] == ')')
      {
        //依次弹出运算符，直到左括号
        while ((op = opStack.Peek()) != '(')
        {
          CalResult(opStack, numStack);
        }
        opStack.Pop();
        continue;
      }

      //如果栈顶运算符优先级大于或等于该运算符，就弹出并计算结果，压入操作数栈
      while (opStack.Count > 0 && CompareOp(opStack.Peek(), strs[i]))
      {
        CalResult(opStack, numStack);
      }
      opStack.Push(strs[i]);
    }
  }

  while(opStack.Count != 0)
  {
    CalResult(opStack, numStack);
  }
  return numStack.Pop();
}

//是否是运算符
private static bool IsOp(char c)
{
  string op = "+-*/()";
  if (op.Contains(c)) return true;
  else return false;
}

//运算符比较，前者是否大于等于后者
private static bool CompareOp(char ch1, char ch2)
{
  if (ch1 == '(') return false;
  //该算法只涉及四则运算，故*/始终返回true
  if (ch1 == '*' || ch1 == '/') return true;
  else
  {
    if (ch2 == '*' || ch2 == '/') return false;
    else return true;
  }
}

//计算结果
private static double CalResult(char op, double left, double right)
{
  switch(op)
  {
    case '+':
      return left + right;
    case '-':
      return left - right;
    case '*':
      return left * right;
    case '/':
      return left / right;
  }
  return 0;
}

//计算结果的封装
private static void CalResult(Stack<char> opStack, Stack<double> numStack)
{
  char op;
  double left, right;
  op = opStack.Pop();
  right = numStack.Pop();
  left = numStack.Pop();
  numStack.Push(CalResult(op, left, right));
}

main函数

static void Main(string[] args)
{
  //使用栈实现括号匹配
  string str1 = "{[()]}";
  Console.WriteLine(str1 + ":" + Ch3.BracketCheck(str1));
  string str2 = "{[()]";
  Console.WriteLine(str1 + ":" + Ch3.BracketCheck(str2));

  //Console.WriteLine((double)'0');
  //使用栈实现表达式求值
  //string str3 = "1+2*(4-3)-6/3";
  //Console.WriteLine(str3 + ":" + Ch3.CalExpression(str3));
  //string str4 = "1-2*((5-3)*2)-8/(4*2)";
  string str4 = "1-2*((5-3)*2)-1"; //-8
  Console.WriteLine(str4 + ":" + Ch3.CalExpression(str4));

  Console.ReadKey();
}

4.串

通用代码

//串，均从下标为1开始
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdlib.h>
#include <string.h>
#define  MAX_SIZE 100

using namespace std;

typedef struct  
{
  char ch[MAX_SIZE];
  int length;
}MyString;

4.1 朴素模式匹配

//朴素模式匹配
int Violence(MyString S, MyString T)
{
  int i = 1, j = 1;
  while (i <= S.length && j <= T.length)
  {
    if (S.ch[i] == T.ch[j])
    {
      i++;
      j++;
    }
    else //不相等就回溯
    {
      i = i - j + 2;
      j = 1;
    }
  }
  if (j > T.length) return i - T.length;
  else return 0;
}

4.2 KMP算法

//KMP算法
int KMP(MyString str, MyString sub, int next[])
{
	int i = 1, j = 1;
	while (i <= str.length && j <= sub.length)
	{
		if (j == 0 || str.ch[i] == sub.ch[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j > sub.length) return i - sub.length;
	else return 0;
}

//根据子串得到Next数组
int* getNext(MyString sub)
{
	int *next = (int*)malloc(sizeof(int) * (sub.length + 1));
	next[1] = 0;
	next[2] = 1;
	int a, b, k, maxNum;
	for (int i = 3; i <= sub.length; i++)
	{
		//前后缀匹配求next值
		maxNum = 1;	//最大前后缀匹配长度
		for(int j = 0; j < i - 2; j++) //前后缀匹配总次数
		{
			k = 1; //记录每一趟最大前后缀匹配长度
			a = 1;	//前缀指针
			b = i - 1 - j;	//后缀指针
			while (b < i) //计算该趟的前后缀匹配个数，后缀指针不能到达当前i所指位置
			{
				if (sub.ch[a] != sub.ch[b])
				{
					break;
				}
				else
				{
					k++;
					a++;
					b++;
					if (k > maxNum) maxNum = k;
				}
			}
		}
		next[i] = maxNum;
	}
	return next;
}

//优化next数组（适用于子串数据大量重复，如aaaaab）
int* getNextval(MyString sub, int *next)
{
	int len = sub.length + 1;
	for (int j = 2; j < len; j++)
	{
		//next数组中所指下标的值等于自身，则优化下标(继续前移)
		while (sub.ch[j] == sub.ch[next[j]] && next[j] != 0)
		{
			next[j] = next[next[j]];
		}
	}
	return next;
}

补充：第四章main函数

int main()
{
  char s1[] = "0abcdabcaaad";
  char s2[] = "0aaab";
  MyString str;
  strcpy(str.ch, s1);
  str.length = strlen(s1) - 1;
  MyString sub;
  strcpy(sub.ch, s2);
  sub.length = strlen(s2) - 1;
  cout << "主串: " << (str.ch + 1) << endl;
  cout << "子串: " << (sub.ch + 1) << endl;

  cout << "朴素模式匹配: " << endl;
  cout << "结果: " << Violence(str, sub) << endl << "**********************" << endl;

  cout << "KMP模式匹配: " << endl;
  cout << "next数组: ";
  int *next = getNext(sub);
  for (int i = 1; i <= sub.length; i++)
  {
    cout << next[i];
    if (i != sub.length)
      cout << ",";
    else cout << endl;
  }
  cout << "结果: " << KMP(str, sub, next) << endl;

  cout << "优化的nextval数组: ";
  int *nextval = getNextval(sub, next);
  for (int i = 1; i <= sub.length; i++)
  {
    cout << nextval[i];
    if (i != sub.length)
      cout << ",";
    else cout << endl;
  }
  cout << "结果: " << KMP(str, sub, nextval) << endl;
  free(next);
}

5.树

5.1 二叉树的遍历

二叉树数据结构

适用于线索二叉树

#pragma once
//二叉树实现
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <iostream>

using namespace std;

typedef char ElemType;
typedef struct BiTNode {
  ElemType data;
  struct BiTNode *lchild, *rchild;
  int ltag,  rtag; //线索二叉树用 0孩子 1表示前驱或后继
}BiTNode, *BiTree;

BiTree CreateTree();
BiTNode* CreateNode(int level);

//前序生成
BiTree CreateTree()
{
	cout << "前序遍历生成树" << endl;
	BiTree T = CreateNode(1);
	return T;
}

//生成结点
BiTNode* CreateNode(int level)
{
	BiTNode* node = NULL;
	cout << "生成第" << level << "层结点: ";
	ElemType data;
	cin >> data; //获取用户输入
	if (data == '0')
		return NULL;
	else
	{
		node = (BiTNode*)malloc(sizeof(BiTNode));
		node->data = data;
		node->ltag = node->rtag = 0;
		cout << "左孩子: " << endl;
		node->lchild = CreateNode(level + 1);
		cout << "右孩子: " << endl;
		node->rchild = CreateNode(level + 1);
		return node;
	}
}

//访问
void Visit(BiTNode* node)
{
	cout << node->data << " ";
}

遍历代码

//前序遍历
void PreOrder(BiTree T)
{
  if (T != NULL)
  {
    Visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
  }
}
//中序遍历
void InOrder(BiTree T)
{
  if (T != NULL)
  {
    InOrder(T->lchild);
    Visit(T);
    InOrder(T->rchild);
  }
}
//后序遍历
void PostOrder(BiTree T)
{
  if (T != NULL)
  {
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    Visit(T);
  }
}
//层序遍历
void LevelOrder(BiTree T)
{
  if (T != NULL)
  {
    queue<BiTNode*> myQ;
    myQ.push(T); //压入队列
    while (!myQ.empty())
    {
      BiTNode* node = myQ.front();
      myQ.pop(); //弹出队列
      Visit(node); //访问结点
      if (node->lchild != NULL) myQ.push(node->lchild);
      if (node->rchild != NULL) myQ.push(node->rchild);
    }
  }
}

补充：5.1节main函数

//ABD0G00E00CF000
BiTree tree = CreateTree();
cout << "前序遍历: ";
PreOrder(tree);
cout << endl << "中序遍历: ";
InOrder(tree);
cout << endl << "后序遍历: ";
PostOrder(tree);
cout << endl << "层次遍历: ";
LevelOrder(tree);

5.2 线索二叉树（以中序为例）

//中序线索化
void InThread(BiTNode *&p, BiTNode *&pre)
{
  if (p != NULL)
  {
    InThread(p->lchild, pre); //优先找到左孩子
    //如果没有左孩子，则记录前驱
    if (p->lchild == NULL)
    {
      p->ltag = 1;
      p->lchild = pre;
    }
    //如果pre不空且没有右孩子，则记录后继
    if (pre != NULL && pre->rchild == NULL)
    {
      pre->rtag = 1;
      pre->rchild = p;
      //cout << pre->data << "的后继是: " << p->data << endl;
    }
    pre = p; //更新pre
    InThread(p->rchild, pre);
  }
}

//生成中序线索二叉树
void CreateInThread(BiTree T)
{
  BiTNode *pre = NULL;
  if (T != NULL)
  {
    InThread(T, pre);
    //最后一个结点的右孩子指向NULL
    if (pre != NULL)
    {
      pre->rchild = NULL;
      pre->rtag = 1;
    }
  }
}

//获得某结点中序遍历下的第一个结点
//白话：找到最左边结点
BiTNode* FirstNode(BiTNode *p)
{
  while (p->ltag == 0) p = p->lchild;
  return p;
}

//获得某结点的后继结点（中序线索二叉树）
//白话：若有右孩子，往右走一步一直往左；若无右孩子，直接访问后继
BiTNode* NextNode(BiTNode *p)
{
  if (p->rtag == 0) return FirstNode(p->rchild);
  else return p->rchild;
}

//中序线索二叉树的遍历
void InOrderThread(BiTree T)
{
  for (BiTNode *p = FirstNode(T); p != NULL; p = NextNode(p))
  {
    Visit(p);
  }
}

补充：5.2节main函数

//生成中序线索二叉树
CreateInThread(tree);
cout << endl << "中序遍历线索二叉树: ";
InOrderThread(tree);

5.3 平衡二叉树

参考b站URL：https://www.bilibili.com/video/BV1NV411E7DQ?from=search&seid=4549868522115408456

AVL数据结构

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
typedef int ElemType;
typedef struct AVLNode
{
  int height;
  ElemType data;
  AVLNode *left, *right;
}AVLNode, *AVLTree;

代码实现

//获得高度
int GetHeight(AVLNode* node)
{
  if (node == NULL) return 0;
  else return node->height;
}

//LL 右单旋转
AVLNode* RotateRight(AVLNode* root)
{
  AVLNode* first = root->left; //root左子树根结点
  root->left = first->right;	//将root左子树根结点的右孩子设为root的左孩子
  first->right = root; //将root左子树根结点作为新的根结点（即root成为其右子树）

  //更新高度 （先root，因为root是first的子孙）
  root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
  first->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
  return first;
}

//RR 左单旋转
AVLNode* RotateLeft(AVLNode* root)
{
  AVLNode* first = root->right;
  root->right = first->left;
  first->left = root;

  //更新高度 （先root，因为root是first的子孙）
  root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
  first->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
  return first;
}

//LR 先左后右双旋转
AVLNode* RotateLeftRight(AVLNode* root)
{
  AVLNode* first = root->left; //root左子树根结点
  AVLNode* second = first->right; //root 左子树的右子树根结点
  //先左旋
  first->right = second->left; //second左孩子成为first的右孩子
  second->left = first;
  //再右旋
  root->left = second->right; //second的右孩子成为root的左孩子
  second->right = root; //second作为根结点（即root为其右孩子）

  first->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
  root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
  second->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;

  //视频给出的方案
  //root->left = RotateLeft(root->left); //左旋左子树
  //return RotateRight(root); //右旋整颗树
  return second;
}

//RL 先右后左双旋转
AVLNode* RotateRightLeft(AVLNode* root)
{
  AVLNode* first = root->right; //root左子树根结点
  AVLNode* second = first->left; //root 左子树的右子树根结点
  //先左旋
  first->left = second->right;
  second->right = first;
  //再右旋
  root->right = second->left;
  second->left = root;

  first->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
  root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
  second->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;

  //视频给出的方案
  //root->right = RotateRight(root->right);
  //return RotateLeft(root);

  return second;
}

//插入结点
AVLNode* Insert(AVLTree root, ElemType data)
{
  AVLNode* parent = NULL;
  if (root == NULL) //根结点为空，生成并插入
  {
    root = (AVLNode*)malloc(sizeof(AVLNode));
    root->data = data;
    root->height = 1; //默认高度1（区别于空结点）
    root->left = root->right = NULL;
  }
  else if (data < root->data) //插入数值小的结点，递归往左走
  {
    //插入结点
    root->left = Insert(root->left, data);
    //更新高度
    root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    //当往左子树插入结点导致不平衡，立刻调整（最小不平衡子树）
    if (GetHeight(root->left) - GetHeight(root->right) == 2) //左高
    {
      //左左 LL
      if (data < root->left->data)
      {
        root = RotateRight(root); //右单旋转
      }
      //左右 LR
      else
      {
        root = RotateLeftRight(root); //先左后右双旋转
      }
    }
  }
  else
  {
    //插入结点
    root->right = Insert(root->right, data);
    //更新高度
    root->height = std::max(GetHeight(root->left), GetHeight(root->right)) + 1;
    //当往右子树插入结点导致不平衡，立刻调整（最小不平衡子树）
    if (GetHeight(root->left) - GetHeight(root->right) == -2) //右高
    {
      //右右 RR
      if (data > root->right->data)
      {
        root = RotateLeft(root); //左单旋转
      }
      //右左 RL
      else
      {
        root = RotateRightLeft(root); //先右后左双旋转
      }
    }
  }
  return root;
}

补充：5.3节main函数

int n, num;
cin >> n;
AVLNode* root = NULL;
for (int i = 0; i < n; i++)
{
  cin >> num;
  root = Insert(root, num);
}
cout << root->data << endl;

5.4 树、森林与二叉树转换

树 -> 二叉树规则：左孩子，右兄弟

森林 -> 二叉树规则：每棵树采用“左孩子，右兄弟”规则转化为二叉树（此时树根必无右孩子），再将各棵树之间看作兄弟，使用同样规则相连。

二叉树 -> 树/森林：根据“左孩子，右兄弟”还原即可

6.图

邻接矩阵(顶点和边下标均从0开始)

//图 默写
//2021年9月18日20:23:26
#include <iostream>
#include <queue> //-- BFS引入
#include <stdlib.h>  //-- MST引入
#include <stack> //-- 最短路径 Dijkstra引入
using namespace std;
//邻接矩阵 下标均从0开始
#define MAX_VERTEX_NUM 100 //顶点数目最大值
#define  INT_INFINITY 32767 //边权值最大值 -- MST引入
typedef char VertexType; //顶点数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct
{
	VertexType Vex[MAX_VERTEX_NUM]; //顶点表
	EdgeType Edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵，边表
	int vexnum, arcnum; //图当前定点数和弧数
}MGraph;

6.1 图的遍历

邻接矩阵初始化和通用操作

参考王道2022 P206 图6.5(b)

//邻接矩阵初始化
//参考王道2022 P206 图6.5(b)
void InitMGraph_1(MGraph &G)
{
	//初始化所有顶点
	for (int i = 0; i < MAX_VERTEX_NUM; i++)
	{
		G.Vex[i] = '0';
	}

	G.Vex[0] = '1';
	G.Vex[1] = '2';
	G.Vex[2] = '3';
	G.Vex[3] = '4';
	G.Vex[4] = '5';

	//初始化所有边
	for (int i = 0; i < MAX_VERTEX_NUM; i++)
	{
		for (int j = 0; j < MAX_VERTEX_NUM; j++)
		{
			G.Edge[i][j] = 0;
		}
	}

	G.Edge[0][1] = 1;
	G.Edge[0][3] = 1;

	G.Edge[1][0] = 1;
	G.Edge[1][2] = 1;
	G.Edge[1][4] = 1;

	G.Edge[2][1] = 1;
	G.Edge[2][3] = 1;
	G.Edge[2][4] = 1;

	G.Edge[3][0] = 1;
	G.Edge[3][2] = 1;

	G.Edge[4][1] = 1;
	G.Edge[4][2] = 1;

	G.vexnum = 5;
	G.arcnum = 6;
}

//返回某顶点第一个邻接点的下标
int FirstNeighbor(MGraph G, int vpos)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (G.Edge[vpos][i] != 0 && G.Edge[vpos][i] != INT_INFINITY) return i;
	}
	//cout << "该顶点无邻接点: " + vpos << endl;
	return -1;
}

//返回某顶点邻接点的下一个点坐标
int NextNeighbor(MGraph G, int vpos, int advpos)
{
	for (int i = advpos + 1; i < G.vexnum; i++)
	{
		if (G.Edge[vpos][i] != 0 && G.Edge[vpos][i] != INT_INFINITY) return i;
	}
	//cout << "顶点: " << vpos << "从" << advpos << "开始找不到下一个邻接点" << endl;
	return -1;
}

图的访问操作

bool visited[MAX_VERTEX_NUM] = { false }; //全局visited
void Visit(MGraph G, int vpos)
{
	cout << G.Vex[vpos] << ",";
	visited[vpos] = true;
}

深度优先搜索 DFS

//1.DFS遍历
void DFSTraverse(MGraph G)
{
  for (int i = 0; i < G.vexnum; i++)
    visited[i] = false;
  //遍历所有顶点，确保非连通图也全部遍历
  for (int i = 0; i < G.vexnum; i++)
  {
    if (!visited[i])
      DFS(G, i);
  }
}
void DFS(MGraph G, int vpos)
{
  Visit(G, vpos); //访问结点
  //遍历该顶点的所有边
  for (int i = FirstNeighbor(G, vpos); i >= 0; i = NextNeighbor(G, vpos, i))
  {
    if (!visited[i])
    {
      DFS(G, i); //递归遍历
    }
  }
}

广度优先搜索 BFS

//BFS遍历
queue<int> vqueue; //队列
void BFSTraverse(MGraph G)
{
  for (int i = 0; i < G.vexnum; i++)
    visited[i] = false;
  for (int i = 0; i < G.vexnum; i++)
    if (!visited[i])
      BFS(G, i);
}
void BFS(MGraph G, int vpos)
{
  Visit(G, vpos); //访问
  vqueue.push(vpos); //压入队列
  while (!vqueue.empty())
  {
    int front = vqueue.front(); //取队头元素
    vqueue.pop(); //出队
    for (int i = FirstNeighbor(G, front); i >= 0; i = NextNeighbor(G, front, i))
    {
      if (!visited[i])
      {
        Visit(G, i); //访问
        vqueue.push(i);
      }
    }
  }
}

6.2 最小生成树 MST

邻接矩阵初始化

参考王道2022 P227 图6.15

//邻接矩阵初始化
//参考王道2022 P227 图6.15
void InitMGraph_MST(MGraph &G)
{
  G.vexnum = 6;
  G.arcnum = 10;

  for (int i = 0; i < G.vexnum; i++)
  {
    G.Vex[i] = '0';
  }

  G.Vex[0] = '1';
  G.Vex[1] = '2';
  G.Vex[2] = '3';
  G.Vex[3] = '4';
  G.Vex[4] = '5';
  G.Vex[5] = '6';

  for (int i = 0; i < G.vexnum; i++)
  {
    for (int j = 0; j < G.vexnum; j++)
    {
      G.Edge[i][j] = INT_INFINITY;
    }
  }

  G.Edge[0][1] = 6;
  G.Edge[0][2] = 1;
  G.Edge[0][3] = 5;
  G.Edge[1][0] = 6;
  G.Edge[1][2] = 5;
  G.Edge[1][4] = 3;
  G.Edge[2][0] = 1;
  G.Edge[2][1] = 5;
  G.Edge[2][3] = 5;
  G.Edge[2][4] = 6;
  G.Edge[2][5] = 4;
  G.Edge[3][0] = 5;
  G.Edge[3][2] = 5;
  G.Edge[3][5] = 2;
  G.Edge[4][1] = 3;
  G.Edge[4][2] = 6;
  G.Edge[4][5] = 6;
  G.Edge[5][2] = 4;
  G.Edge[5][3] = 2;
  G.Edge[5][4] = 6;
}

Prim算法 O(V^2^) 边稠密

///Prim O(n^2) = O(n-1) * O(2n)
//求最小生成树的代价 - Prim算法
//思路：每次选择代价最小的顶点并入生成树
int Prim(MGraph G, int beginIndex)
{
  int sum = 0;
  bool isJoin[MAX_VERTEX_NUM]; //是否并入最小生成树
  for (int i = 0; i < G.vexnum; i++)
  {
    isJoin[i] = false;
  }
  int lowCost[MAX_VERTEX_NUM]; //当前到各顶点的最小代价
  for (int i = 0; i < G.vexnum; i++)
  {
    lowCost[i] = INT_INFINITY;
  }

  //将第一个结点并入最小生成树，并赋值lowCost
  isJoin[beginIndex] = true;
  for (int i = 0; i < G.vexnum; i++)
  {
    if (G.Edge[beginIndex][i] < lowCost[i]) //存在可达边
    {
      lowCost[i] = G.Edge[beginIndex][i]; //赋值lowCost
    }
  }

  //还有n - 1个顶点未并入生成树
  for (int i = 0; i < G.vexnum - 1; i++) ///O(n - 1)
  {
    int val = INT_INFINITY;
    int minIndex = 0;
    //找到未并入生成树，且当前最小代价的结点
    for (int j = 0; j < G.vexnum; j++) ///O(n-1) * O(n)
    {
      if (!isJoin[j] && lowCost[j] < val)
      {
        val = lowCost[j];
        minIndex = j; 
      }
    }

    isJoin[minIndex] = true; //将最小结点并入生成树
    sum += val; //累加最小代价
    //更新lowCost
    for (int j = 0; j < G.vexnum; j++) ///O(n-1) * O(2n) = O(n^2)
    {
      if (!isJoin[j] && G.Edge[minIndex][j] < lowCost[j]) //从该点出发，到某顶点的值更小，就更新
      {
        lowCost[j] = G.Edge[minIndex][j]; //无需累加，直接覆盖lowCost的值
      }
    }
  }
  return sum;
}

Kruskal算法 O(ElogE) 边稀疏

需要使用并查集

///Kruskal 堆排序：O(E|logE|)
//思路：每次找权值最小的边，若该边的两个顶点不属于同一集合，就并入生成树
//比较函数
bool RoadCompare(Road a, Road b)
{
  return a.weight < b.weight;
}

//Debug函数（测试用）
void Debug_Road(Road* roads)
{
  for (int i = 0; i < 10; i++)
  {
    cout << "a: " << roads[i].a << "-b: " << roads[i].b << "weight: ";
    cout << roads[i].weight << " " << endl;
  }
}

//求是否同根: 并查集
int GetRoot(int *unionTree, int index)
{
  //直到前驱结点等于自身下标，到达根
  while (unionTree[index] != index)
    index = unionTree[index];
  return index; //返回所在集合
}

//求最小生成树的代价 - Kruskal算法
int Kruskal(MGraph G, int beginIndex)
{
  int sum = 0;
  Road * roads = (Road*)malloc(sizeof(Road) * G.arcnum); //边集合
  int* unionTree = (int*)malloc(sizeof(int) * G.vexnum); //并查集，用于判断是否属于同一集合

  //初始化并查集，均指向自身
  for (int i = 0; i < G.vexnum; i++)
  {
    unionTree[i] = i;
  }

  int k = 0;
  //录入所有边信息
  for (int i = 0; i < G.vexnum; i++)  ///O(E^2) ，书上说使用堆排序，就是O(ElogE)
  {
    for (int j = 0; j < G.vexnum; j++)
    {
      //只访问上三角矩阵的边
      if (j > i && G.Edge[i][j] < INT_INFINITY)
      {
        roads[k].a = i;
        roads[k].b = j;
        roads[k].weight = G.Edge[i][j];
        k++;
      }
    }
  }
  //根据权重排序（升序）
  //参数①：起始地址	参数②：最终地址	参数③：比较函数
  sort(roads, roads + G.arcnum, RoadCompare);
  //DEBUG 查看排序结果
  //Debug_Road(roads);

  //选取权值最小的边，通过并查集，将符合条件的顶点并入生成树
  for (int i = 0; i < G.arcnum; i++)
  {
    int rootA = GetRoot(unionTree, roads[i].a); //获得顶点A所在集合
    int rootB = GetRoot(unionTree, roads[i].b); //获得顶点B所在集合
    //二者属于不同集合，符合条件
    if (rootA != rootB)
    {
      unionTree[rootB] = rootA;// 更新并查集，顶点B的前驱为A(A,B同属一个集合)
      sum += roads[i].weight; //累加权值
    }
  }
  return sum;
}

6.3 最短路径

Dijkstra算法单源 O(V^2^)

时间复杂度：O(V^2^)
不允许带有负权值的边
解决单源最短路问题

邻接矩阵

//邻接矩阵初始化
//参考王道2022视频2.6.10 3:10
void InitMGraph_Dijkstra(MGraph &G)
{
  G.vexnum = 5;
  G.arcnum = 10;

  for (int i = 0; i < G.vexnum; i++)
  {
    G.Vex[i] = '0';
  }

  G.Vex[0] = '1';
  G.Vex[1] = '2';
  G.Vex[2] = '3';
  G.Vex[3] = '4';
  G.Vex[4] = '5';

  for (int i = 0; i < G.vexnum; i++)
  {
    for (int j = 0; j < G.vexnum; j++)
    {
      G.Edge[i][j] = INT_INFINITY;
    }
  }

  G.Edge[0][1] = 10;
  G.Edge[0][4] = 5;
  G.Edge[1][2] = 1;
  G.Edge[1][4] = 2;
  G.Edge[2][3] = 4;
  G.Edge[3][0] = 7;
  G.Edge[3][2] = 6;
  G.Edge[4][1] = 3;
  G.Edge[4][2] = 9;
  G.Edge[4][3] = 2;

}

核心代码（完整）

//迪杰斯特拉算法(单源最短路问题)
//思路：每次选择最短路径的顶点并入，判断经过该点到其他顶点是否存在更短路径，有则更新
//visited数组：记录是否访问过
//dist数组：记录从源点v0到其他各顶点当前的最短路径长度(dist[自身] = 0 )
//path数组：表示从源点到顶点i之间的最短路径的前驱结点(path[自身] = -1)
void Dijkstra(MGraph G, int source, int *&dist, int *&path)
{
  //visited数组：记录是否访问过
  bool* visited = (bool*)malloc(sizeof(bool) * G.vexnum);
  //dist数组：记录从源点v0到其他各顶点当前的最短路径长度
  dist = (int *)malloc(sizeof(int) * G.vexnum);
  //path数组：表示从源点到顶点i之间的最短路径的前驱结点
  path = (int *)malloc(sizeof(int) * G.vexnum);

  //初始化
  for (int i = 0; i < G.vexnum; i++)
  {
    visited[i] = false;
    dist[i] = INT_INFINITY;
    path[i] = -1;
  }

  //将source加入
  visited[source] = true;
  dist[source] = 0;
  for (int i = 0; i < G.vexnum; i++)
  {
    if (G.Edge[source][i] < dist[i])
    {
      dist[i] = G.Edge[source][i];
      path[i] = 0;
    }
  }

  //选取最小dist值，开始Dijkstra
  for (int i = 0; i < G.vexnum - 1; i++)  ///O(n)
  {
    //获取当前dist最小的结点
    int minIndex = 0;
    int minVal = INT_INFINITY;
    for (int j = 0; j < G.vexnum; j++) ///O(n) * O(n)
    {
      if (!visited[j] && dist[j] < minVal)
      {
        minVal = dist[j];
        minIndex = j;
      }
    }

    //并入结果集，并更新dist和path
    visited[minIndex] = true;
    for (int k = 0; k < G.vexnum; k++)  ///O(n) * O(2n) = O(n^2)
    {
      //如果k未访问，且从minIndex -> k比当前到k存在更短的路径，就更新dist和path
      if (!visited[k] && dist[k] > dist[minIndex] + G.Edge[minIndex][k])
      {
        dist[k] = dist[minIndex] + G.Edge[minIndex][k]; //更新路径
        path[k] = minIndex; //更新前驱
      }
    }
  }
}

//得到最短路径，源点由Dijkstra确定
void GetMinPath_Dijkstra(MGraph G, int sourceIndex, int distIndex, int *dist, int *path)
{
  cout << "从" << G.Vex[sourceIndex] << "到" << G.Vex[distIndex] << "的最短路径长度为: " << dist[distIndex] << endl;
  cout << "具体路径为: ";
  int x = distIndex;
  stack<VertexType> output;
  while (x != -1)
  {
    output.push(G.Vex[x]);
    x = path[x];
  }

  int length = output.size();
  for (int i = 0; i < length; i++)
  {
    cout << output.top();
    output.pop();
    if (i != length - 1)
      cout << "->";
  }
}

Floyd算法多源 O(V^3^)

时间复杂度：O(V^3^)
允许图中带有负权值的边，但不允许有包含带负权值的边组成的回路
解决多源最短路问题

参考王道2022视频2.6.11 13:00

//邻接矩阵初始化
//参考王道2022视频2.6.11 13:00
void InitMGraph_Floyd(MGraph &G)
{
  G.vexnum = 5;
  G.arcnum = 7;

  for (int i = 0; i < G.vexnum; i++)
  {
    G.Vex[i] = '0';
  }

  G.Vex[0] = '1';
  G.Vex[1] = '2';
  G.Vex[2] = '3';
  G.Vex[3] = '4';
  G.Vex[4] = '5';

  for (int i = 0; i < G.vexnum; i++)
  {
    for (int j = 0; j < G.vexnum; j++)
    {
      G.Edge[i][j] = INT_INFINITY;
    }
  }

  G.Edge[0][2] = 1;
  G.Edge[0][4] = 10;
  G.Edge[1][3] = 1;
  G.Edge[1][4] = 5;
  G.Edge[2][1] = 1;
  G.Edge[2][4] = 7;
  G.Edge[3][4] = 1;
}

核心代码（完整）

//弗洛伊德算法(多源最短路径)
//思路：每个顶点作中转跑一次
//A数组：记录最小路径
//path数组：记录中转点(无中转点为-1)
void Floyd(MGraph G, int ** &A, int ** &path)
{
  A = (int **)malloc(sizeof(int*) * G.vexnum); //A数组：记录最小路径
  path = (int **)malloc(sizeof(int*) * G.vexnum); //path数组：记录中转点
  //初始化
  for (int i = 0; i < G.vexnum; i++)
  {
    A[i] = (int *)malloc(sizeof(int) * G.vexnum);
    path[i] = (int *)malloc(sizeof(int) * G.vexnum);
  }

  for (int i = 0; i < G.vexnum; i++)
  {
    for (int j = 0; j < G.vexnum; j++)
    {
      A[i][j] = INT_INFINITY;
      path[i][j] = -1;

      if (G.Edge[i][j] < A[i][j])
        A[i][j] = G.Edge[i][j];
    }
  }

  //将每一个顶点都设为中转点，更新A和path的值
  for (int k = 0; k < G.vexnum; k++) ///O(n^3)
  {
    for (int i = 0; i < G.vexnum; i++)
    {
      for (int j = 0; j < G.vexnum; j++)
      {
        //从i -> j 比从 i ->k -> j的值大，就更新
        if (A[i][j] > A[i][k] + A[k][j])
        {
          A[i][j] = A[i][k] + A[k][j]; //更新路径值
          path[i][j] = k;	//更新中转点
        }
      }
    }
  }
}

//输出路径
void GetPath(MGraph G, int sourceIndex, int distIndex, int **A, int **path)
{
  int mid = path[sourceIndex][distIndex];
  if (mid != -1) //如果有中转点，递归
  {
    GetPath(G, sourceIndex, mid, A, path);
    cout << G.Vex[mid] << "->";
    GetPath(G, mid, distIndex, A, path);
  }
}

//得到最短路径，源点任意
void GetMinPath_Floyd(MGraph G, int sourceIndex, int distIndex, int **A, int **path)
{
  cout << "从" << G.Vex[sourceIndex] << "到" << G.Vex[distIndex] << "的最短路径长度为: " << A[sourceIndex][distIndex] << endl;
  cout << "具体路径为: ";
  cout << G.Vex[sourceIndex] << "->";
  GetPath(G, sourceIndex, distIndex, A, path);
  cout << G.Vex[distIndex];
}

6.4 拓扑排序

//邻接矩阵初始化
//参考王道2022书P232 图6.22
void InitMGraph_Topological(MGraph &G)
{
  G.vexnum = 5;
  G.arcnum = 7;

  for (int i = 0; i < G.vexnum; i++)
  {
    G.Vex[i] = '0';
  }

  G.Vex[0] = '1';
  G.Vex[1] = '2';
  G.Vex[2] = '3';
  G.Vex[3] = '4';
  G.Vex[4] = '5';

  for (int i = 0; i < G.vexnum; i++)
  {
    for (int j = 0; j < G.vexnum; j++)
    {
      G.Edge[i][j] = INT_INFINITY;
    }
  }

  G.Edge[0][1] = 1;
  G.Edge[0][3] = 1;
  G.Edge[1][3] = 1;
  G.Edge[1][2] = 1;
  G.Edge[3][2] = 1;
  G.Edge[3][4] = 1;
  G.Edge[2][4] = 1;
}

//拓扑排序
bool TopologicalSort(MGraph G, int *&print)
{
  print = (int*)malloc(sizeof(int) * G.vexnum);
  int* indegree = (int*)malloc(sizeof(int) * G.vexnum);
  for (int i = 0; i < G.vexnum; i++)
    indegree[i] = 0;
  for (int i = 0; i < G.vexnum; i++)
  {
    for (int j = 0; j < G.vexnum; j++)
    {
      if (G.Edge[i][j] < INT_INFINITY)
      {
        indegree[j]++;
      }
    }
  }

  //将所有入度为0的顶点入栈
  stack<int> s;
  for (int i = 0; i < G.vexnum; i++)
    if (indegree[i] == 0)
      s.push(i);
  int count = 0;
  while (!s.empty())
  {
    int top = s.top();
    s.pop();
    print[count++] = top;
    //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
    for (int i = FirstNeighbor(G, top); i >= 0; i = NextNeighbor(G, top, i))
    {
      indegree[i]--;
      if (indegree[i] == 0)
        s.push(i);
    }
  }
  if (count < G.vexnum)
    return false; //拓扑排序失败,有向图中存在回路
  else return true; //拓扑排序成功
}

补充：第六章main函数

int main()
{
  MGraph G;
  //初始化图
  InitMGraph_1(G);
  //DFS遍历
  cout << "DFS: ";
  DFSTraverse(G); //1,2,3,4,5
  cout << endl;

  //BFS遍历
  cout << "BFS: ";
  BFSTraverse(G); //1,2,4,3,5
  cout << endl;

  //MST
  InitMGraph_MST(G);
  cout << "Prim: ";
  cout << Prim(G, 0); //15
  cout << endl;

  cout << "Kruskal: ";
  cout << Kruskal(G, 0); //15
  cout << endl;

  //最短路径
  InitMGraph_Dijkstra(G);
  cout << "Dijkstra: ";
  int *dist = NULL;
  int *path = NULL;
  Dijkstra(G, 0, dist, path);
  GetMinPath_Dijkstra(G, 0, 2, dist, path);
  cout << endl;

  InitMGraph_Floyd(G);
  cout << "Floyd: ";
  int **A = NULL;
  int **path2 = NULL;
  Floyd(G, A, path2);
  GetMinPath_Floyd(G, 0, 3, A, path2);
  cout << endl;

  //拓扑排序
  InitMGraph_Topological(G);
  int *print = NULL;
  cout << TopologicalSort(G, print);
  cout << endl;
  for (int i = 0; i < G.vexnum; i++)
  {
    cout << print[i];
    if (i != G.vexnum - 1) cout << ",";
  }
  cout << endl;
  return 0;
}

7.查找

7.1 顺序查找

//顺序查找
int Search_Seq(int arr[], int length, int val)
{
  //设置哨兵
  arr[0] = val;
  int i;
  for (i = length; arr[i] != val; i--);
  return i;
}

7.2 折半查找

//折半查找
int Search_Binary(int arr[], int length, int val)
{
  int low = 1, high = length, mid;
  while (low <= high)
  {
    mid = (low + high) / 2;
    if (arr[mid] == val) return mid;
    else if (arr[mid] < val)
      low = mid + 1;
    else
      high = mid - 1;
  }
  return -1;
}

8.排序

所有数组元素均从下标1处开始
所有排序默认升序排序
部分通用代码

#include <iostream>
#include <stdlib.h>
typedef int ElemType;
using namespace std;

//测试数据
ElemType arr[] = { 0, 49, 38, 65, 97, 76, 13, 27, 49 }; //从下标1处开始
int length = sizeof(arr) / sizeof(ElemType) - 1; //length和元素个数相同

—– 插入排序 —–

8.1 直接插入排序 O(n^2^)

平均时间复杂度：O(n^2^)

稳定性：稳定

适用性：顺序表和链表

思路：选择无序列表中的第一个元素，插入到有序列表中

void InsertSort(ElemType arr[], int length)
{
	int i, j;
	for (i = 2; i <= length; i++) //默认第一个位置有序
	{
		if (arr[i] < arr[i - 1]) //只有该位置元素比有序队列最大值小，才需要移动元素
		{
			arr[0] = arr[i]; //设置哨兵
			for (j = i - 1; arr[0] < arr[j]; j--) //只要该值小于有序队列的值，就后移元素
			{
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = arr[0];
		}
	}
}

改进：折半插入排序

平均时间复杂度：同上

稳定性：稳定

适用性：顺序表

思路：同上，只是每次在有序列表选择插入位置时使用折半查找

void InsertSort_Binary(ElemType arr[], int length)
{
  int i, j, low, high, mid;
  for (i = 2; i <= length; i++) //默认第一个位置有序
  {
    if (arr[i] < arr[i - 1]) //只有比有序队列最大值小，才需要移动元素
    { 
      arr[0] = arr[i]; //设置哨兵
      low = 1;
      high = i - 1;
      while (low <= high) //折半查找，最后high+1或low为最终插入位置
      {
        mid = (low + high) / 2;
        if (arr[0] < arr[mid]) high = mid - 1;
        else low = mid + 1;
      }
      //移动元素
      for (j = i; j > low; j--)
      {
        arr[j] = arr[j - 1];
      }
      //赋值
      arr[low] = arr[0];
    }
  }
}

8.2 希尔排序

平均时间复杂度：可能约O(n^1.3^)，略优于O(n^2^)；当d=1时退化为直接插入排序

稳定性：不稳定

适用性：顺序表

思路：选取不断缩小的增量，使列表从部分有序到整体有序

void ShellShort(ElemType arr[], int length)
{
  int i, j, d;
  for (d = length / 2; d >= 1; d /= 2) //增量每次取1/2
  {
    for (i = 1 + d; i <= length; i++) //从每组第二个位置开始插入排序
    {
      arr[0] = arr[i];
      //i位置所在组的元素进行插入排序，移动大于arr[0]的元素
      for (j = i - d; j > 0 && arr[j] > arr[0]; j -= d)
      {
        arr[j + d] = arr[j];
      }
      arr[j + d] = arr[0];
    }
  }
}

—– 交换排序 —–

8.3 冒泡排序 O(n^2^)

平均时间复杂度：O(n^2^)

稳定性：稳定

思路：每次选择一个最小（大）的元素，通过逐个交换到列表一端

void BubbleSort(ElemType arr[], int length)
{
  bool flag = false;
  //只需length - 1轮，最后一个元素自动有序
  for (int i = 1; i < length; i++)
  {
    flag = false;
    for (int j = length; j > i; j--)
    {
      //后者比前者小，就交换
      if (arr[j] < arr[j - 1]) // <确保稳定性
      {
        int temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
        flag = true;
      }
    }
    if (!flag) break;
  }
}

8.4 快速排序 O(nlogn)

平均时间复杂度：O(nlogn)

稳定性：不稳定

思路：每次选取一个值为枢轴，递归调用，左小右大，确定其位置

void QuickSortCore(ElemType arr[], int low, int high);
int Partition(ElemType arr[], int low, int high);
void QuickSort(ElemType arr[], int length)
{
  QuickSortCore(arr, 1, length);
}

void QuickSortCore(ElemType arr[], int low, int high) 
{
  if (low < high) //递归退出条件
  {
    //进行一次划分，获得枢轴最终位置，小的到左边，大的到右边
    int pivotpos = Partition(arr, low, high);
    //分别对左右进行快速排序（递归）
    QuickSortCore(arr, low, pivotpos - 1);
    QuickSortCore(arr, pivotpos + 1, high);
  }
}

int Partition(ElemType arr[], int low, int high)
{
  //将low所处元素设为枢轴元素
  ElemType pivot = arr[low];
  while (low < high)
  {
    while (low < high && arr[high] >= pivot) high--;
    arr[low] = arr[high];	//比枢轴小的元素移动到左端
    while (low < high && arr[low] <= pivot) low++;
    arr[high] = arr[low];	//比枢轴大的元素移动到右端
  }
  arr[low] = pivot; //枢轴元素放到最终位置
  return low; //返回枢轴元素最终位置
}

—– 选择排序 —–

8.5 简单选择排序 O(n^2^)

平均时间复杂度：O(n^2^)

稳定性：不稳定

思路：每次选择无序列表中最小的并入有序列表

void SelectSort(ElemType arr[], int length)
{
  for (int i = 1; i < length; i++)
  {
    int minIndex = i; //默认无序列表中第一个最小，记录其下标
    for (int j = i + 1; j <= length; j++) //遍历整个数组
    {
      if (arr[minIndex] > arr[j]) //发现比当前下标元素更小的元素，就更新下标
        minIndex = j;
    }
    SwapElem(arr[i], arr[minIndex]); //交换元素（实现详见堆排序）
  }
}

8.6 堆排序 O(nlogn)

平均时间复杂度：O(n^2^)

分析：建堆O(n)，排序需要 n - 1 次向下调整的操作，为O(nlogn)。共O(n) + O(nlogn) ~ O(nlogn)

稳定性：不稳定

思路：

建堆，从非叶结点往前，确保根 >=(或<=) 左、右
排序，每次排序交换头尾两个元素，再调整堆

void MaxHeapSort(ElemType arr[], int length); //堆排序
void BuildMaxHeap(ElemType arr[], int length); //建大顶堆
void AdjustMaxHeap(ElemType arr[], int length, int k); //调整堆
void SwapElem(ElemType &a, ElemType &b); //交换元素

//2.堆排序（大顶堆为例）
void MaxHeapSort(ElemType arr[], int length)
{
	BuildMaxHeap(arr, length); //建堆
	//cout << "建堆后: " << endl;
	//PrintArrary(arr, length);
	for (int i = 1; i < length; i++)
	{
		SwapElem(arr[1], arr[length - i + 1]); //交换堆中第一个元素和最后一个元素
		AdjustMaxHeap(arr, length - i, 1); //重新调整堆
	}
}
//建大顶堆
void BuildMaxHeap(ElemType arr[], int length)
{
	//从后往前，从非叶结点开始遍历
	for (int i = length / 2; i >= 1; i--)
	{
		AdjustMaxHeap(arr, length, i);
	}
}
//调整堆，规则：根 >= 左、右孩子
void AdjustMaxHeap(ElemType arr[], int length, int k)
{
	arr[0] = arr[k];
	//完全二叉树性质，左孩子 = 2*i	右孩子 = 2*i+1
	for (int i = 2 * k; i <= length; i *= 2)
	{
		//选出左右孩子较大者
		if (i < length && arr[i] < arr[i+1])
			i++;
		//if (arr[k] >= arr[i]) break; //易错点
		if (arr[0] >= arr[i]) break; //待调整结点已经是最大值了，就break
		//父结点与较大的孩子结点交换
		else
		{
			arr[k] = arr[i];
			k = i;
		}
	}
	arr[k] = arr[0];
}
//交换元素
void SwapElem(ElemType &a, ElemType &b)
{
	ElemType c = a;
	a = b;
	b = c;
}

—– 特殊排序 —–

8.7 归并排序 O(nlogn)

平均时间复杂度：O(nlogn)

分析：分析：每趟归并的时间复杂度为O(n)，共需logn(向上取整)趟归并，故为O(nlogn)

空间复杂度：O(n)

稳定性：稳定

思路：递归，分别对左右归并排序

void MergeSort(ElemType arr[], int length); //归并排序入口
void MergeSortCore(ElemType arr[], ElemType B[], int low, int high); //归并排序递归过程
void Merge(ElemType arr[], ElemType B[], int low, int mid, int high); //归并操作

void MergeSort(ElemType arr[], int length) //归并排序入口
{
	ElemType* B = (ElemType*)malloc(sizeof(ElemType) * (length + 1));
	MergeSortCore(arr, B, 1, length);
	free(B);
}
void MergeSortCore(ElemType arr[], ElemType B[], int low, int high) //归并排序递归过程
{
	if (low < high) //只有low < high时才有必要归并，这也是递归退出条件
	{
		int mid = (low + high) / 2;
		MergeSortCore(arr, B, low, mid); //对左边归并
		MergeSortCore(arr, B, mid + 1, high); //对右边归并
		Merge(arr, B, low, mid, high); //对左右归并
	}
}
void Merge(ElemType arr[], ElemType B[], int low, int mid, int high) //归并操作
{
	//将arr拷贝到B
	for (int i = low; i <= high; i++)
		B[i] = arr[i];
	//归并操作
	int i, j, k; //i,j分别指向B中low,mid+1的位置；k指向arr中low的位置
	for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++)
	{
		if (B[i] <= B[j]) //<=可以确保算法的稳定性
		{
			arr[k] = B[i++];
		}
		else
		{
			arr[k] = B[j++];
		}
	}
	while (i <= mid) arr[k++] = B[i++];
	while (j <= high) arr[k++] = B[j++];
}

数据结构与算法

1.绪论

2.线性表

2.1 顺序表

2.2 链表

2.3 双链表

3.栈和队列

3.1 顺序栈

3.2 链式栈

3.3 顺序队列

3.4 链式队列

补充：第三章main函数

实战：栈实现括号匹配

实战：表达式求值（C#）

main函数

4.串

4.1 朴素模式匹配

4.2 KMP算法

补充：第四章main函数

5.树

5.1 二叉树的遍历

二叉树数据结构

遍历代码

补充：5.1节main函数

5.2 线索二叉树（以中序为例）

补充：5.2节main函数

5.3 平衡二叉树

AVL数据结构

代码实现

补充：5.3节main函数

5.4 树、森林与二叉树转换

6.图

6.1 图的遍历

邻接矩阵初始化和通用操作

图的访问操作

深度优先搜索 DFS

广度优先搜索 BFS

6.2 最小生成树 MST

邻接矩阵初始化

Prim算法 O(V^2^) 边稠密

Kruskal算法 O(ElogE) 边稀疏

6.3 最短路径

Dijkstra算法 单源 O(V^2^)

Floyd算法 多源 O(V^3^)

6.4 拓扑排序

补充：第六章main函数

7.查找

7.1 顺序查找

7.2 折半查找

8.排序

—– 插入排序 —–

8.1 直接插入排序 O(n^2^)

改进：折半插入排序

8.2 希尔排序

—– 交换排序 —–

8.3 冒泡排序 O(n^2^)

8.4 快速排序 O(nlogn)

—– 选择排序 —–

8.5 简单选择排序 O(n^2^)

8.6 堆排序 O(nlogn)

—– 特殊排序 —–

8.7 归并排序 O(nlogn)

Dijkstra算法单源 O(V^2^)

Floyd算法多源 O(V^3^)