数据结构与算法

线性表

线性表的线性存储结构

#include<iostream>
using namespace std;

struct node{
  int data;
  node *next;  
};

typedef node *position;
typedef node *LIST;

void createList(LIST &); // 构建线性表
void readList(LIST &); // 读取线性表
position end(LIST); // 返回尾部节点，可以用于尾插法
void insert(int, position); // 在某一节点的下一位插入节点
void deleteNode(position); // 删除节点的下一个节点
position Local(int, LIST);// 返回元素为 x 的第一个节点
position makeNull(LIST &); // 线性表置空

int main(){
  LIST L = NULL;
  createList(L);
  readList(L); 
  return 0;
}

void createList(LIST &L){
  // 直接操作 L 会导致段错误
  position p1, p2;
	cout << "Enter the Data or -1 to end:" << endl;

	while(1){
		p1 = new node;
		cin >> p1->data;
		if(p1->data == -1){
			break;
		}
		if(L == 0){
			L = p1;
			p2 = p1;
		}
		else{
			p2->next = p1;
			p2 = p1;
		}
	}
	p2->next = NULL;
}

void readList(LIST &L){
  position p = L;
	for(; p ; p = p->next){
		cout << p->data << '\t';
	}
	cout << endl;
}

position end(LIST L){
  position q;
  q = L;
  while (q -> next != NULL){
    q = q -> next;
  }
  return q;
}

void insert(int x, position p){
  position q = new node;
  q -> data = x;
  q -> next = p -> next;
  p -> next = q;
} 

void deleteNode(position p){
  if (p -> next != NULL){
    position q = p -> next;
    p -> next = q -> next;
    delete q;
  }
}

position Local(int x, LIST L){
  position p;
  p = L;
  while (p -> next != NULL){
    if (p -> data == x){
      return p;
    } else {
      p = p -> next;
    }
  }
  return p;
}

position makeNull(LIST &L){
  L = new node;
  L -> next = NULL;
  return L;
}

线性表的顺序存储结构

#include<iostream>
using namespace std;

const int MaxSize = 50;

struct SqList{
  int data[MaxSize];
  int length;
};

void createList(SqList &); // 构建一个顺序表
void read(SqList); // 打印顺序表
bool listInsert(SqList &, int i, int e); // 第 i 个位置插入元素 e 返回成功与否, 从 1 开始计数
bool deleteList(SqList &, int i); // 删除第 i 个位置上的元素,从 1 开始计数
int localList(SqList, int k); // 查找第一个值为 i 的元素，返回位序

int main(){
  SqList L;
  createList(L);
  read(L);
  return 0;
}

void createList(SqList &L){
  cout << "------开始创建线性表------" << endl;
  int x = 0;
  for (int i = 0; ;i++){
    cout << "请输入顺序表存储元素，输入 -1 结束：";
    cin >> x;
    if (x == -1)
      break;
    else {
      L.data[i] = x;
      L.length = i + 1;
    }
  }
}

void read(SqList L){
  for (int i = 0; i < L.length; i++){
    cout << L.data[i] << "\t";
  }
}

bool listInsert(SqList &L, int i, int e){
  if (i < 1 || i > L.length + 1)
    return false;
  if (L.length >= 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 deleteList(SqList &L, int i){
  if (i < 1 || i > L.length)
    return false;
  for (int j = i; j < L.length; j++)
    L.data[j - 1] = L.data[j];

  L.length--;
  return true;
}

int localList(SqList L, int key){
  for (int i = 0; i < L.length; i++)
    if (L.data[i] == key)
      return i + 1;
  return 0;
}

栈的链式存储

#include <iostream>
using namespace std;

typedef int eleType;

struct Linknode{
  eleType data;
  Linknode *next;
};

typedef Linknode *Lhead; 

Lhead initStack();  //  初始化栈元素
bool isEmpty(Lhead);  // 判断栈是否为空
void pushStack(Lhead &, eleType);  //  进栈
eleType popStack(Lhead &);  // 出栈

int main(){
  Lhead L = initStack();
  cout << "栈为空栈： " << isEmpty(L) << endl;
  pushStack(L, 1);
  pushStack(L, 2);
  pushStack(L, 3);
  cout << "栈为空栈： " << isEmpty(L) << endl;
  eleType x = popStack(L);
  eleType y = popStack(L);
  eleType z = popStack(L);
  cout << "出栈序列： " << x << "\t" << y << "\t" << z << endl;
  cout << "栈为空栈： " << isEmpty(L) << endl;

  return 0;
}

Lhead initStack(){
  Lhead L = new Linknode;
  L -> next = NULL;
  L -> data = NULL;
  return L;
}

bool isEmpty(Lhead L){
  if (L -> data == NULL && L -> next == NULL)
    return true;
  return false;
}

void pushStack(Lhead &L, eleType x){
  if (isEmpty(L)){
    L -> data == x;
  }
  Linknode *p = new Linknode;
  p -> data = x;
  p -> next = L;
  L = p; 
}

eleType popStack(Lhead &L){
  eleType x;
  if (isEmpty(L))
    cout << "栈为空！" << endl;
  if (L -> next != NULL){
    x = L -> data;
    Linknode *p = L;
    L = L -> next;
    delete p;
    return x;
  }
  x = L -> data;
  L -> data = NULL;
  return x;
    
}

队列的线性结构

#include <iostream>
using namespace std;

typedef int eletype;

struct node{
  eletype data;
  node *next;
};

struct LinkQueue{
  node *front, *rear;
};

typedef LinkQueue *Queue;

void initQueue(Queue &); // 初始化队列，带头结点
bool isEmpty(Queue); // 判断队列是否为空
void enQueue(Queue &, eletype); // 入队
eletype deQueue(Queue &); // 出队

int main(){
  Queue Q = new LinkQueue;
  initQueue(Q);
  cout << "队列为空： " << isEmpty(Q) << endl;
  enQueue(Q, 1);
  enQueue(Q, 2);
  enQueue(Q, 3);
  cout << "队列为空： " << isEmpty(Q) << endl;
  eletype x = deQueue(Q);
  eletype y = deQueue(Q);
  eletype z = deQueue(Q);
  cout << x << "\t" << y << "\t" << z << endl;

  return 0;
}

void initQueue(Queue &Q){
  Q -> front = Q -> rear = new node; // 新建头结点
  Q -> front -> next = NULL;
}

bool isEmpty(Queue Q){
  if (Q -> front == Q -> rear)
    return true;
  return false;
}

void enQueue(Queue &Q, eletype x){
  node *p = new node;
  p -> data = x;
  p -> next = NULL;
  Q -> rear -> next = p;
  Q -> rear = p;
}

eletype deQueue(Queue &Q){
  if (Q -> front == Q -> rear){
    cout << "队列为空！" << endl;
    return -1;
  }
  node *p = Q -> front -> next;
  eletype x = p -> data;
  Q -> front -> next = p -> next;
  if (Q -> rear == p)
    Q -> rear = Q -> front; // 若队列只有一个结点，删除后变空
  delete p;
  return x;
}

循环队列

#include<iostream>
using namespace std;

typedef int eletype;

const int Maxsize = 50;

struct SqQueue{
  eletype data[Maxsize];
  int front, rear;
};

// typedef SqQueue *Queue;

void initQueue(SqQueue &); // 初始化队列
bool isEmpty(SqQueue);  // 判断队列是否为空
void enQueue(SqQueue &, eletype); // 入队
eletype deQueue(SqQueue &); // 出队

int main(){
  SqQueue Q;
  initQueue(Q);
  cout << "队列为空： " << isEmpty(Q) << endl;
  enQueue(Q, 1);
  enQueue(Q, 2);
  enQueue(Q, 3);
  cout << "队列为空： " << isEmpty(Q) << endl;
  cout << "出队： ";
  for ( int i = 0; i < 3; i++){
    eletype x = deQueue(Q);
    cout << x << "\t";
  }
  return 0;
}

void initQueue(SqQueue &Q){
  Q.rear = Q.front = 0;
}

bool isEmpty(SqQueue Q){
  if (Q.front == Q.rear)
    return true;
  return false;
}

void enQueue(SqQueue &Q, eletype x){
  if ((Q.rear + 1) % Maxsize == Q.front)
    cout << "队列已满！" << endl;
  else{
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % Maxsize;
  }
}

eletype deQueue(SqQueue &Q){
  if (Q.rear == Q.front){
    cout << "队列为空！" << endl;
    return -1;
  } else {
    eletype x = Q.data[Q.front];
    Q.front = (Q.front + 1) % Maxsize;
    return x;
  } 
}

树

二叉树的定义和遍历

#include <iostream> 
using namespace std;

typedef char elementType; // 数据域的数据类型为字符串

struct BitNode // 树节点
{
  elementType data; // 数据域
  BitNode *lChild, *rChild; // 左右孩子的指针
};

typedef BitNode *BitTree; // 定义一个指向根节点的指针

// 先根遍历构造二叉树
void CreatTree(BitTree &BT, char* &str) // 这里的传参不太好理解，记住： 指针是指向某个变量的内存地址的，所以 *p = &a 所以 (BitTree &BT) == (*BitTree &BT)， (char* &str) == (char *&str)
{
  char ch = *str++; // 每次递归指针向后移动一个字符
  if ( ch == '#' )
   BT = NULL;
  else
  {
    BT = new BitNode;
    BT -> data = ch;
    CreatTree( BT -> lChild, str);
    CreatTree( BT -> rChild, str);
  };
};
// 将树置空
void makeNull(BitTree &BT)
{
  BT = NULL;
};
// 判断是否为空树
bool isEmpty(BitTree &BT)
{
  if (BT != NULL)
    return false;
  else 
    return true;
};
// 将左子树和右子树合并
BitTree merge(elementType x, BitTree &lChild, BitTree &rChild)
{
  BitTree root = new BitNode;
  root -> data = x;
  root -> lChild = lChild;
  root -> rChild = rChild;
  return root;
};
// 返回数据域
elementType Data(BitTree &BT)
{
  return BT -> data;
};
// 返回左子树
BitTree LTree(BitTree &BT)
{
  return BT -> lChild;
};
// 返回右子树
BitTree RTree(BitTree &BT)
{
  return BT -> rChild;
};
// 访问数据域
void visit(elementType x)
{
  cout << x;
};
// 先根遍历
void PreOrderTraverse( BitTree &BT)
{
  visit ( BT -> data);
  PreOrderTraverse ( BT -> lChild);
  PreOrderTraverse ( BT -> rChild);
};
// 中根遍历
void InOrderTraverse( BitTree &BT)
{
  InOrderTraverse( BT -> lChild);
  visit ( BT -> data);
  InOrderTraverse( BT -> rChild);
}
// 后根遍历
void PostOrderTraverse( BitTree &BT)
{
  PostOrderTraverse( BT -> lChild);
  PostOrderTraverse( BT -> rChild);
  visit( BT -> data);
}
int main()
{
  BitTree BT = NULL; // 根节点的指针先置空
  char *str = (char*) "abc##de#g##f###"; // 先根遍历，定义一个指向 char 型的指针，该指针指向一串字符串

  CreatTree(BT, str); // 构造树，传入指向根节点的指针和指向字符串第一个字符的指针

  return 0;
}

图

图的邻接表结构

#include<iostream>
#include<cstring>
using namespace std;

#define MaxVertexNum 100 // 最大顶点数
typedef string vertexType; // 顶点的类型
typedef int edgeType; // 边权值的类型

// 边表结点
struct EdgeNode{
  int adjex;
  EdgeNode *next;
  // edgeType info; // 边权值
};

// 顶点表结点
struct VNode {
  vertexType data;
  EdgeNode *first;
};

// 将上面两个结构合起来就是邻接表了
struct ALGraph{
  VNode vertices[MaxVertexNum]; // 长度为一百的顶点表
  int vexnum, edgenum; // 定点数和弧度数
};

void CreateALGraph(ALGraph *);
void read(ALGraph);

int main () {
  ALGraph GL;
  CreateALGraph(&GL);
  read(GL);
  return 0;
}

void CreateALGraph(ALGraph *Gp)
{
  int i, j, k;
  cout << "输入顶点数和边数:" << endl;
  cin >> Gp -> vexnum >> Gp -> edgenum;

  for(i = 0; i < Gp -> vexnum; i++)
  {
    cout << "请输入顶点信息:"; 
    cin >> Gp -> vertices[i].data;
    Gp -> vertices[i].first = NULL; // 边表置空
  }

  for(k = 0; k < Gp -> edgenum; k++)
  {
    cout << "请输入边(Vi,Vj)的序号(0开始计数)" << endl;
    cin >> i >> j;

    EdgeNode *p = new EdgeNode;
    p -> adjex = j; // 邻接序号为 j
    p -> next = Gp -> vertices[i].first; // 使用头插法
    Gp -> vertices[i].first = p; // 将顶点指针指向 p
  }
}

void read(ALGraph GL){
  for(int i = 0; i < GL.vexnum; i++){
    cout << GL.vertices[i].data << '\t';
    EdgeNode *p = GL.vertices[i].first;
    while( p != NULL){
      cout << p -> adjex << '\t';
      p = p -> next;
    }
    cout << endl;
  }
}

邻接表的广度优先算法

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

#define MaxVertexNum 100 // 最大顶点数
typedef string vertexType; // 顶点的类型
typedef int edgeType; // 边权值的类型

// 边表结点
struct EdgeNode
{
  int adjex;
  EdgeNode *next;
  // edgeType info; // 边权值
};

// 顶点表
struct VNode 
{
  vertexType data;
  EdgeNode *first;
};

// 将上面两个结构合起来就是邻接表了
struct ALGraph
{
  VNode vertices[MaxVertexNum]; // 长度为一百的顶点表
  int vexnum, edgenum; // 定点数和弧度数
};

// 辅助队列
queue<string> Q;
// 访问标记数组
bool visited[MaxVertexNum];

void CreateALGraph(ALGraph *);
void read(ALGraph);
void BFSTraverse(ALGraph);
void BFS(ALGraph, int);


int main () 
{
  ALGraph GL;
  CreateALGraph(&GL);
  read(GL);
  BFSTraverse(GL);
  return 0;
}

void CreateALGraph(ALGraph *Gp)
{
  int i, j, k;
  cout << "输入顶点数和边数:" << endl;
  cin >> Gp -> vexnum >> Gp -> edgenum;

  for(i = 0; i < Gp -> vexnum; i++)
  {
    cout << "请输入第 " << i << " 个顶点信息:"; 
    cin >> Gp -> vertices[i].data;
    Gp -> vertices[i].first = NULL; // 边表置空
  }

  for(k = 0; k < Gp -> edgenum; k++)
  {
    cout << "请输入边(Vi,Vj)的序号(0开始计数)" << endl;
    cin >> i >> j;

    EdgeNode *p = new EdgeNode;
    p -> adjex = j; // 邻接序号为 j
    p -> next = Gp -> vertices[i].first; // 使用头插法
    Gp -> vertices[i].first = p; // 将顶点指针指向 p
  }
}

void read(ALGraph GL)
{
  for(int i = 0; i < GL.vexnum; i++)
  {
    cout << GL.vertices[i].data << '\t';
    EdgeNode *p = GL.vertices[i].first;
    while( p != NULL){
      cout << p -> adjex << '\t';
      p = p -> next;
    }
    cout << endl;
  }
}

void BFSTraverse(ALGraph G)
{
  cout << "广度优先遍历次序： ";
  for (int i = 0; i < G.vexnum; i++)
    visited[i] = false;
  while(!Q.empty())
    Q.pop();
  for (int i = 0; i < G.vexnum; i++)
    if (!visited[i])
      BFS(G, i);
}

void BFS(ALGraph G, int v)
{
  cout << G.vertices[v].data << '\t';
  visited[v] = true;
  Q.push(G.vertices[v].data);
  while (!Q.empty())
  {
    Q.pop();
    EdgeNode *wp = G.vertices[v].first;
    while (wp != NULL)
    {
      int w = wp -> adjex;
      if (!visited[w])
      {
        cout << G.vertices[w].data << '\t';
        visited[w] = true;
        Q.push(G.vertices[w].data);
      }
      wp = wp -> next;
    }      
  }
}

邻接表的深度优先算法

#include<iostream>
#include<cstring>
using namespace std;

#define MaxVertexNum 100 // 最大顶点数
typedef string vertexType; // 顶点的类型
typedef int edgeType; // 边权值的类型

// 边表结点
struct EdgeNode
{
  int adjex;
  EdgeNode *next;
  // edgeType info; // 边权值
};

// 顶点表
struct VNode 
{
  vertexType data;
  EdgeNode *first;
};

// 将上面两个结构合起来就是邻接表了
struct ALGraph
{
  VNode vertices[MaxVertexNum]; // 长度为一百的顶点表
  int vexnum, edgenum; // 定点数和弧度数
};

// 访问标记数组
bool visited[MaxVertexNum];

void CreateALGraph(ALGraph *);
void read(ALGraph);
void DFSTraverse(ALGraph);
void DFS(ALGraph, int);


int main () 
{
  ALGraph GL;
  CreateALGraph(&GL);
  read(GL);
  DFSTraverse(GL);
  return 0;
}

void CreateALGraph(ALGraph *Gp)
{
  int i, j, k;
  cout << "输入顶点数和边数:" << endl;
  cin >> Gp -> vexnum >> Gp -> edgenum;

  for(i = 0; i < Gp -> vexnum; i++)
  {
    cout << "请输入第 " << i << " 个顶点信息:"; 
    cin >> Gp -> vertices[i].data;
    Gp -> vertices[i].first = NULL; // 边表置空
  }

  for(k = 0; k < Gp -> edgenum; k++)
  {
    cout << "请输入边(Vi,Vj)的序号(0开始计数)" << endl;
    cin >> i >> j;

    EdgeNode *p = new EdgeNode;
    p -> adjex = j; // 邻接序号为 j
    p -> next = Gp -> vertices[i].first; // 使用头插法
    Gp -> vertices[i].first = p; // 将顶点指针指向 p
  }
}

void read(ALGraph GL)
{
  for(int i = 0; i < GL.vexnum; i++)
  {
    cout << GL.vertices[i].data << '\t';
    EdgeNode *p = GL.vertices[i].first;
    while( p != NULL){
      cout << p -> adjex << '\t';
      p = p -> next;
    }
    cout << endl;
  }
}

void DFSTraverse(ALGraph G)
{
  cout << "深度优先遍历次序： ";
  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(ALGraph G, int v)
{
  cout << G.vertices[v].data << '\t';
  visited[v] = true;
 
  EdgeNode *wp = G.vertices[v].first;
  while (wp != NULL)
  {
    int w = wp -> adjex;
    if (!visited[w])
    {
      DFS(G, w);        
    }
    wp = wp -> next;
  }      
}

图的邻接矩阵结构

#include <iostream>
#include <cstring>
using namespace std;

#define MaxVertexNum 100
typedef string vertexType;
typedef int edgeType;

// 邻接矩阵
struct MGraph
{
  vertexType Vex[MaxVertexNum];              // 顶点表
  edgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
  int vexnum, arcnum;                        // 顶点数和弧度数
  // MGraph(v, a) : vexnum(v), arcnum(a){};
};

void createMGraph(MGraph &);  // 构建图结构
void read(MGraph);  //  显示图结构  

int main()
{
  MGraph Graph; // 邻接矩阵
  createMGraph(Graph);
  read(Graph);

  return 0;
}

void createMGraph(MGraph &G)
{
  int vexnum, arcnum;
  cout << "请输入顶点个数和边的个数：";
  cin >> vexnum >> arcnum;
  G.vexnum = vexnum;
  G.arcnum = arcnum;
  for (int i = 0; i < vexnum; i++)
  {
    G.Vex[i] = "v" + to_string(i);
    int j;
    do
    {
      cout << "请输入顶点 " << G.Vex[i] << " 相关联的点的序号(从 0 开始计数，一次一个数，输入-1结束):";
      cin >> j; // 这里应该检验 j 的合法性
      G.Edge[i][j] = 1;
    } while (j != -1);
  }
}

void read(MGraph G)
{
  cout << "图的邻接矩阵如下: \n";
  for (int i = 0; i < G.vexnum; i++)
  {
    cout << G.Vex[i] << "\t";
  }
  cout << endl;

  for (int j = 0; j < G.vexnum; j++)
  {
    for (int k = 0; k < G.vexnum; k++)
    {
      cout << G.Edge[j][k] << "\t";
    };
    cout << endl;
  }
}

邻接矩阵的广度优先算法

// 邻接矩阵的广度优先
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define MaxVertexNum 100
typedef string vertexType;
typedef int edgeType;

// 邻接矩阵
struct MGraph
{
  vertexType Vex[MaxVertexNum];              // 顶点表
  edgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
  int vexnum, arcnum;                        // 顶点数和弧度数
  // MGraph(v, a) : vexnum(v), arcnum(a){};
};

void createMGraph(MGraph &);  // 构建图的邻接矩阵结构
void read(MGraph);  // 显示图的邻接矩阵
void BFSTraverse(MGraph);  // 广度优先遍历
void BFS(MGraph, int);  // 第二个参数是从第几号顶点开始遍历
int firstNeighbor(MGraph, int);  // 顶点 v 的第一个邻接点
int nextNeighbor(MGraph, int, int);  // 顶点 v 的下一个邻接点

// 访问标记数组
bool visited[MaxVertexNum];
// 辅助队列
queue<string> Q;

int main()
{
  MGraph Graph; // 邻接矩阵
  createMGraph(Graph);
  read(Graph);
  BFSTraverse(Graph);
  return 0;
}

void createMGraph(MGraph &G)
{
  int vexnum, arcnum;
  cout << "请输入顶点个数和边的个数：";
  cin >> vexnum >> arcnum;
  G.vexnum = vexnum;
  G.arcnum = arcnum;
  for (int i = 0; i < vexnum; i++)
  {
    G.Vex[i] = "v" + to_string(i);
    int j;
    do
    {
      cout << "请输入顶点 " << G.Vex[i] << " 相关联的点的序号(从 0 开始计数，一次一个数，输入-1结束):";
      cin >> j; // 这里应该检验 j 的合法性
      G.Edge[i][j] = 1;
    } while (j != -1);
  }
}

void read(MGraph G)
{
   cout << "图的邻接矩阵如下: \n";
  for (int i = 0; i < G.vexnum; i++)
  {
    cout << G.Vex[i] << "\t";
  }
  cout << endl;

  for (int j = 0; j < G.vexnum; j++)
  {
    for (int k = 0; k < G.vexnum; k++)
    {
      cout << G.Edge[j][k] << "\t";
    };
    cout << endl;
  }
}

void BFSTraverse(MGraph G)
{
  // 初始化访问标记数组
  for (int i = 0; i < G.vexnum; i++)
    visited[i] = false;
  // 初始化队列
  while (!Q.empty())
    Q.pop();
  // 从零号顶点开始遍历
  for (int i = 0; i < G.vexnum; i++)
    if(!visited[i])
      BFS(G, i);
}

void BFS(MGraph G, int v)
{
  cout << G.Vex[v] << '\t';
  visited[v] = true;
  Q.push(G.Vex[v]);

  while(!Q.empty())
  {
    Q.pop();
    for (int w = firstNeighbor(G, v); w >= 0; w = nextNeighbor(G, v, w))
    {
      if (!visited[w])
      {
        cout << G.Vex[w] << '\t';
        visited[w] = true;
        Q.push(G.Vex[w]);
      }
    }
  }
}

int firstNeighbor(MGraph G, int v)
{
  for (int i = 0; i < G.vexnum; i++)
    if (G.Edge[v][i] == 1)
      return i;
  // return -1;  // 有没有必要当没有连接点的时候返回一个值？？？
}

int nextNeighbor(MGraph G, int v, int w)
{
  for (int i = w + 1; i < G.vexnum; i++)
    if (G.Edge[v][i] == 1)
      return i;
  return -1;
}

邻接矩阵的深度优先算法

// 邻接矩阵的深度优先
#include <iostream>
#include <cstring>
using namespace std;

#define MaxVertexNum 100
typedef string vertexType;
typedef int edgeType;

// 邻接矩阵
struct MGraph
{
  vertexType Vex[MaxVertexNum];              // 顶点表
  edgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
  int vexnum, arcnum;                        // 顶点数和弧度数
  // MGraph(v, a) : vexnum(v), arcnum(a){};
};

void createMGraph(MGraph &);  // 构建图的邻接矩阵结构
void read(MGraph);  // 显示图的邻接矩阵
void DFSTraverse(MGraph);  // 广度优先遍历
void DFS(MGraph, int);  // 第二个参数是从第几号顶点开始遍历
int firstNeighbor(MGraph, int);  // 顶点 v 的第一个邻接点
int nextNeighbor(MGraph, int, int);  // 顶点 v 的下一个邻接点

// 访问标记数组
bool visited[MaxVertexNum];

int main()
{
  MGraph Graph; // 邻接矩阵
  createMGraph(Graph);
  read(Graph);
  DFSTraverse(Graph);
  return 0;
}

void createMGraph(MGraph &G)
{
  int vexnum, arcnum;
  cout << "请输入顶点个数和边的个数：";
  cin >> vexnum >> arcnum;
  G.vexnum = vexnum;
  G.arcnum = arcnum;
  for (int i = 0; i < vexnum; i++)
  {
    G.Vex[i] = "v" + to_string(i);
    int j;
    do
    {
      cout << "请输入顶点 " << G.Vex[i] << " 相关联的点的序号(从 0 开始计数，一次一个数，输入-1结束):";
      cin >> j; // 这里应该检验 j 的合法性
      G.Edge[i][j] = 1;
    } while (j != -1);
  }
}

void read(MGraph G)
{
   cout << "图的邻接矩阵如下: \n";
  for (int i = 0; i < G.vexnum; i++)
  {
    cout << G.Vex[i] << "\t";
  }
  cout << endl;

  for (int j = 0; j < G.vexnum; j++)
  {
    for (int k = 0; k < G.vexnum; k++)
    {
      cout << G.Edge[j][k] << "\t";
    };
    cout << endl;
  }
}

void DFSTraverse(MGraph G)
{
  cout << "深度优先遍历序列：  ";
  // 初始化访问标记数组
  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 v)
{
  cout << G.Vex[v] << '\t';
  visited[v] = true;
 
  for (int w = firstNeighbor(G, v); w >= 0; w = nextNeighbor(G, v, w))
    if (!visited[w])
      DFS(G, w);
}

int firstNeighbor(MGraph G, int v)
{
  for (int i = 0; i < G.vexnum; i++)
    if (G.Edge[v][i] == 1)
      return i;
  // return -1;  // 有没有必要当没有连接点的时候返回一个值？？？
}

int nextNeighbor(MGraph G, int v, int w)
{
  for (int i = w + 1; i < G.vexnum; i++)
    if (G.Edge[v][i] == 1)
      return i;
  return -1;
}

查找

二叉查找树

#include<iostream>
using namespace std;

// 定义树节点
struct BitNode
{
  int data = -2;  // 数据域
  BitNode *lChild, *rChild;   
};

typedef BitNode *BST; // 指向树节点的指针

BitNode* searchBST(int, BST); // 查找
void insertBST(int, BST); // 插入
BST createBST(); // 构建二叉查找树
void visit(int); // 访问节点数据域
void InOrderTraverse(BST); // 中根遍历
void Delete(int, BST); // 删除结点
int deletemin(BST); // 删除继承结点并返回

int main()
{
  BST F = createBST(); 
  InOrderTraverse(F);
  return 0;
}

BST createBST()
{
  BST F = new BitNode;
  cout << "请输入二叉查找树的所有值(一次输入一个)：";
  int key;
  cin >> key;
  while ( key != -1)
  { 
    insertBST(key, F);
    cout << "\n输入下一个值(输入 -1 结束)：";
    cin >> key;
  }
  return F;
}

BitNode* searchBST(int key, BST F)
{
  BitNode *p = F;
  if (p == NULL || p -> data == key )
    return p;
  if (key < p -> data)
    searchBST(key, p -> lChild);
  else
    searchBST(key, p -> rChild);
}

void insertBST(int key, BST F)
{
  if (F -> data == -2)
  {
    F -> data = key;
    F -> lChild = new BitNode;
    F -> rChild = new BitNode;
  }
  else if (key < F -> data)
    insertBST(key, F -> lChild);
  else if (key > F -> data)
    insertBST(key, F -> rChild);
  if (key == F -> data)
    return;
}

void visit(int x)
{ 
  cout << x << '\t';
} 

void InOrderTraverse(BST F)
{
  if (F -> data == -2)
    return;
  InOrderTraverse(F -> lChild);
  visit(F -> data);
  InOrderTraverse(F -> rChild);
}

void Delete(int key, BST F)
{
  if (F -> data != -2)
  {
    if (key < F -> data)
      Delete(key, F -> lChild);
    else if (key > F -> data)
      Delete(key, F -> rChild);
    else
    {
      if (F -> lChild -> data == -2)
        F = F -> rChild;
      else if ( F -> rChild -> data == -2)
        F = F -> lChild;
      else
        F -> data = deletemin(F -> rChild);
    }
  }
}

int deletemin(BST F)
{
  int tmp;
  if (F -> lChild -> data == -2)
  { 
    tmp = F -> data;
    F = F -> rChild;
    return tmp;
  }
  else
    return deletemin(F -> lChild);
}

(未完待续…^_^)