数据结构与算法(C++)代码练习(图)

所有代码均由Microsoft Visual Studio 2015编译通过      

图的遍历DFS和BFS

 

#include<iostream>
#include<iomanip>
#define N 16
using namespace std;
class listNode
{
public:
int data;
listNode* next;
};
class QueueNode
{
public:
int a;
QueueNode* next;
};
void enqueue(int a, QueueNode*& rear) {
rear->a = a;
rear->next = new QueueNode;
rear = rear->next;
rear->next = NULL;
}
int dequeue(QueueNode*& front) {
QueueNode* temp = front;
front = front->next;
temp->next = NULL;
return temp->a;
}
void inputLesson(listNode* head[])
{
head[0] = NULL;
head[1] = new listNode;
head[1]->data = 3;
head[1]->next = NULL;
head[2] = new listNode;
head[2]->data = 3;
head[2]->next = new listNode;
head[2]->next->data = 13;
head[2]->next->next = NULL;
head[3] = new listNode;
head[3]->data = 7;
head[3]->next = NULL;
head[4] = new listNode;
head[4]->data = 5;
head[4]->next = NULL;
head[5] = new listNode;
head[5]->data = 6;
head[5]->next = NULL;
head[6] = new listNode;
head[6]->data = 15;
head[6]->next = NULL;
head[7] = new listNode;
head[7]->data = 10;
head[7]->next = new listNode;
head[7]->next->data = 11;
head[7]->next->next = new listNode;
head[7]->next->next->data = 12;
head[7]->next->next->next = NULL;
head[8] = new listNode;
head[8]->data = 9;
head[8]->next = NULL;
head[9] = new listNode;
head[9]->data = 10;
head[9]->next = new listNode;
head[9]->next->data = 11;
head[9]->next->next = NULL;
head[10] = new listNode;
head[10]->data = 14;
head[10]->next = NULL;
head[11] = NULL;
head[12] = NULL;
head[13] = NULL;
head[14] = NULL;
head[15] = NULL;
}
void DFS(listNode* list[], int index, int visited[])
{
listNode* p;
if (visited[index]) {
return;
}
cout << index;
visited[index] = 1;
p = list[index];
while (p) {
DFS(list, p->data, visited);
p = p->next;
}
}
void BFS(listNode* list[], int index, int visited[])
{
int v;
listNode* p;
QueueNode* front,* rear;
front = rear = new QueueNode;
rear->next = NULL;
enqueue(index, rear);
visited[index] = 1;
while (front != rear) {
v = dequeue(front);
cout << v;
p = list[v];
while (p) {
if (!(visited[p->data])) {
enqueue(p->data, rear);
visited[p->data] = 1;
}
p = p->next;
}
}
}
void resetVisited(int visited[])
{
for (int i = 0; i < N; i++) {
visited[i] = 0;
}
}
void main()
{
listNode* list[N];
int n;
int visited[N];
inputLesson(list);
cout << "请输入深度优先搜索起始点序号:\n";
cin >> n;
resetVisited(visited);
DFS(list, n, visited);
cout << '\n';
cout << "请输入广度优先搜索起始点序号:\n";
cin >> n;
resetVisited(visited);
BFS(list, n, visited);
cout << '\n';
system("pause");
}

   

最小生成树Prim算法

 

#include<iostream>
#include<iomanip>
#define N 8
#define MAX 100000
using namespace std;
class AdjList
{
public:
int data;
int dist;
AdjList* next;
AdjList() {
next = NULL;
}
};
class Vertex
{
public:
int id;
AdjList* adj;
int dist;
int visited;
int path;
Vertex() {
adj = NULL;
path = 0;
visited = 0;
dist = MAX;
}
};
class Edge
{
public:
int v;
int w;
void printEdge()
{
cout << v << '-' << w << "\n";
}
};
class Heap
{
public:
int size;
Vertex a[N];
};
void checkOdd(Heap& minHeap)
{
if (!(minHeap.size % 2)) {
minHeap.a[minHeap.size + 1].dist = MAX;
}
}
void incertMinHeap(Vertex v, Heap& minHeap)
{
int hole = ++minHeap.size;
while (hole != 1 && v.dist < minHeap.a[hole / 2].dist) {
minHeap.a[hole] = minHeap.a[hole / 2];
hole = hole / 2;
}
minHeap.a[hole] = v;
checkOdd(minHeap);
}
Vertex deleteMin(Heap& minHeap)
{
Vertex min = minHeap.a[1];
int hole = 1;
while (hole <= minHeap.size / 2 && (minHeap.a[minHeap.size].dist > minHeap.a[hole * 2 + 1].dist || minHeap.a[minHeap.size].dist > minHeap.a[hole * 2].dist)) {
if (minHeap.a[hole * 2 + 1].dist < minHeap.a[hole * 2].dist) {
minHeap.a[hole] = minHeap.a[hole * 2 + 1];
hole = hole * 2 + 1;
}
else {
minHeap.a[hole] = minHeap.a[hole * 2];
hole = hole * 2;
}
}
minHeap.a[hole] = minHeap.a[minHeap.size];
minHeap.size--;
checkOdd(minHeap);
return min;
}
void input(Vertex &v, int data, int dist)
{
AdjList*& p = v.adj;
if (data == 0 && dist == 0) {
p = NULL;
return;
}
if (!p) {
p = new AdjList;
p->data = data;
p->dist = dist;
}
else {
AdjList* temp = p;
while (p->next) {
p = p->next;
}
p->next = new AdjList;
p->next->data = data;
p->next->dist = dist;
p = temp;
}
}
void inputSample(Vertex v[])
{
for (int i = 0; i < N; i++)
{
v[i].id = i;
}
input(v[1], 2, 2);
input(v[1], 3, 4);
input(v[1], 4, 1);
input(v[2], 1, 2);
input(v[2], 4, 3);
input(v[2], 5, 10);
input(v[3], 1, 4);
input(v[3], 4, 2);
input(v[3], 6, 5);
input(v[4], 1, 1);
input(v[4], 2, 3);
input(v[4], 3, 2);
input(v[4], 5, 7);
input(v[4], 6, 8);
input(v[4], 7, 4);
input(v[5], 2, 10);
input(v[5], 4, 7);
input(v[5], 7, 6);
input(v[6], 3, 5);
input(v[6], 4, 8);
input(v[6], 7, 1);
input(v[7], 4, 4);
input(v[7], 5, 6);
input(v[7], 6, 1);
}
void Prim(Vertex &s, Vertex g[], Edge MST[])
{
int i = 0;
Vertex v;
AdjList* p;
Heap minHeap;
minHeap.size = 0;
s.dist = 0;
incertMinHeap(s, minHeap);
while (minHeap.size) {
v = deleteMin(minHeap);
while (g[v.id].visited) {
if (!minHeap.size) {
return;
}
v = deleteMin(minHeap);
}
g[v.id].visited = 1;
g[v.id].dist = 0;
if (v.path) {
i++;
MST[i].v = v.path;
MST[i].w = v.id;
}
p = v.adj;
while (p) {
if (g[p->data].visited == 0 && p->dist < g[p->data].dist) {
g[p->data].dist = p->dist ;
g[p->data].path = v.id;
incertMinHeap(g[p->data], minHeap);
}
p = p->next;
}
}
}
void check(Vertex v[])
{
AdjList* p;
for (int i = 1; i < N; i++)
{
cout << i << '\n';
p = v[i].adj;
while (p) {
cout << p->data << ' ' << p->dist << ' ' << p->next << '\n';
p = p->next;
}
}
system("pause");
}
void main()
{

Vertex v[N];
Edge MST[N - 1];
int n;
inputSample(v);
cout << "请输入源点序号:\n";
cin >> n;
Prim(v[n], v, MST);
cout << "最小生成树为:\n";
for (int i = 1; i < N - 1; i++)
{
MST[i].printEdge();
}
system("pause");

}

   

最小生成树Kruskal算法

 

#include<iostream>
#include<iomanip>
#define N 8
#define MAX 100000
using namespace std;
class AdjList
{
public:
int data;
int dist;
AdjList* next;
AdjList() {
next = NULL;
}
};
class Vertex
{
public:
int id;
AdjList* adj;
int root;
int visited;

```
Vertex() {
adj = NULL;
root = -1;
visited = 0;
}
```

};
class Edge
{
public:
int v;
int w;
int l;
Edge(int v = 0, int w = 0, int l = 0) :v(v), w(w), l(l) {}
void printEdge()
{
cout << v << '-' << w << "\n";
}
};
class Heap
{
public:
int size;
Edge a[N*(N - 1)];
Heap() {
size = 0;
}
};
void checkOdd(Heap& minHeap)
{
if (!(minHeap.size % 2)) {
minHeap.a[minHeap.size + 1].l = MAX;
}
}
void incertMinHeap(Edge e, Heap& minHeap)
{
int hole = ++minHeap.size;
while (hole != 1 && e.l < minHeap.a[hole / 2].l) {
minHeap.a[hole] = minHeap.a[hole / 2];
hole = hole / 2;
}
minHeap.a[hole] = e;
checkOdd(minHeap);
}
Edge deleteMin(Heap& minHeap)
{
Edge min = minHeap.a[1];
int hole = 1;
while (hole <= minHeap.size / 2 && (minHeap.a[minHeap.size].l > minHeap.a[hole * 2 + 1].l || minHeap.a[minHeap.size].l > minHeap.a[hole * 2].l)) {
if (minHeap.a[hole * 2 + 1].l < minHeap.a[hole * 2].l) {
minHeap.a[hole] = minHeap.a[hole * 2 + 1];
hole = hole * 2 + 1;
}
else {
minHeap.a[hole] = minHeap.a[hole * 2];
hole = hole * 2;
}
}
minHeap.a[hole] = minHeap.a[minHeap.size];
minHeap.size--;
checkOdd(minHeap);
return min;
}
int find(Vertex v, Vertex g[])
{
if (v.root == -1) {
return v.id;
}
return find(g[v.root], g);
}
void unionSet(int r1, int r2, Vertex g[])
{
g[r2].root = g[r1].id;
}
void input(Vertex &v, int data, int dist)
{
AdjList*& p = v.adj;
if (data == 0 && dist == 0) {
p = NULL;
return;
}
if (!p) {
p = new AdjList;
p->data = data;
p->dist = dist;
}
else {
AdjList* temp = p;
while (p->next) {
p = p->next;
}
p->next = new AdjList;
p->next->data = data;
p->next->dist = dist;
p = temp;
}
}
void inputSample(Vertex v[])
{
for (int i = 0; i < N; i++)
{
v[i].id = i;
}
input(v[1], 2, 2);
input(v[1], 3, 4);
input(v[1], 4, 1);
input(v[2], 1, 2);
input(v[2], 4, 3);
input(v[2], 5, 10);
input(v[3], 1, 4);
input(v[3], 4, 2);
input(v[3], 6, 5);
input(v[4], 1, 1);
input(v[4], 2, 3);
input(v[4], 3, 2);
input(v[4], 5, 7);
input(v[4], 6, 8);
input(v[4], 7, 4);
input(v[5], 2, 10);
input(v[5], 4, 7);
input(v[5], 7, 6);
input(v[6], 3, 5);
input(v[6], 4, 8);
input(v[6], 7, 1);
input(v[7], 4, 4);
input(v[7], 5, 6);
input(v[7], 6, 1);
}
void Kruskal(Vertex g[], Edge MST[])
{
Heap minHeap;
Edge e;
int i = 0;
for (int i = 1; i < N; i++) {
AdjList* p = g[i].adj;
while (p) {
if (!g[p->data].visited) {
Edge e(i, p->data, p->dist);
incertMinHeap(e, minHeap);
}
p = p->next;
}
g[i].visited = 1;
}
while (minHeap.size) {
e = deleteMin(minHeap);
int r1 = find(g[e.v], g);
int r2 = find(g[e.w], g);
if (r1 != r2) {
MST[++i] = e;
unionSet(r1, r2, g);
}
}

}
void main()
{
Vertex v[N];
Edge MST[N - 1];
inputSample(v);
Kruskal(v, MST);
cout << "最小生成树为:\n";
for (int i = 1; i < N - 1; i++)
{
MST[i].printEdge();
}
system("pause");
}

   

基于最小堆的有权图单源最短路径Dijkstra算法

 

#include<iostream>
#include<iomanip>
#define N 16
#define MAX 100000
using namespace std;
class AdjList
{
public:
int data;
int dist;
AdjList* next;
AdjList() {
next = NULL;
}
};
class Vertex
{
public:
int id;
AdjList* adj;
int dist;
int visited;
int path;
Vertex() {
adj = NULL;
path = 0;
visited = 0;
dist = MAX;
}
};
class Heap
{
public:
int size;
Vertex a[N];
};
void checkOdd(Heap& minHeap)
{
if (!(minHeap.size % 2)) {
minHeap.a[minHeap.size + 1].dist = MAX;
}
}
void incertMinHeap(Vertex v, Heap& minHeap)
{
int hole = ++minHeap.size;
while (hole != 1 && v.dist < minHeap.a[hole / 2].dist) {
minHeap.a[hole] = minHeap.a[hole / 2];
hole = hole / 2;
}
minHeap.a[hole] = v;
checkOdd(minHeap);
}
Vertex deleteMin(Heap& minHeap)
{
Vertex min = minHeap.a[1];
int hole = 1;
while (hole <= minHeap.size / 2 && (minHeap.a[minHeap.size].dist > minHeap.a[hole * 2 + 1].dist || minHeap.a[minHeap.size].dist > minHeap.a[hole * 2].dist)) {
if (minHeap.a[hole * 2 + 1].dist < minHeap.a[hole * 2].dist) {
minHeap.a[hole] = minHeap.a[hole * 2 + 1];
hole = hole * 2 + 1;
}
else {
minHeap.a[hole] = minHeap.a[hole * 2];
hole = hole * 2;
}
}
minHeap.a[hole] = minHeap.a[minHeap.size];
minHeap.size--;
checkOdd(minHeap);
return min;
}
void input(Vertex &v, int data, int dist)
{
AdjList*& p = v.adj;
if (data == 0 && dist == 0){
p = NULL;
return;
}
if (!p) {
p = new AdjList;
p->data = data;
p->dist = dist;
}
else {
AdjList* temp = p;
while (p->next) {
p = p->next;
}
p->next = new AdjList;
p->next->data = data;
p->next->dist = dist;
p = temp;
}
}
void inputSample(Vertex v[])
{
for (int i = 0; i < N; i++)
{
v[i].id = i;
}
input(v[1], 2, 2);
input(v[1], 4, 1);
input(v[2], 4, 3);
input(v[2], 5, 10);
input(v[3], 1, 4);
input(v[3], 6, 5);
input(v[4], 3, 2);
input(v[4], 5, 2);
input(v[4], 6, 8);
input(v[4], 7, 4);
input(v[5], 7, 6);
input(v[7], 6, 1);
}
void Dijkstra(Vertex &s, Vertex g[])
{
Vertex v;
AdjList* p;
Heap minHeap;
minHeap.size = 0;
s.dist = 0;
incertMinHeap(s, minHeap);
while (minHeap.size) {
v = deleteMin(minHeap);
while (g[v.id].visited) {
if (!minHeap.size) {
return;
}
v = deleteMin(minHeap);
}
g[v.id].visited = 1;
p = v.adj;
while (p) {
if (g[p->data].visited == 0 && p->dist + v.dist < g[p->data].dist) {
g[p->data].dist = p->dist + v.dist;
g[p->data].path = v.id;
incertMinHeap(g[p->data], minHeap);
}
p = p->next;
}
}
}
void printPath(Vertex v, Vertex g[])
{
if (v.path) {
printPath(g[v.path], g);
cout << "->";
}
cout << v.id;
}
void check(Vertex v[])
{
AdjList* p;
for (int i = 1; i < N; i++)
{
cout << i << '\n';
p = v[i].adj;
while (p) {
cout << p->data << ' ' << p->dist << ' ' << p->next << '\n';
p = p->next;
}
}
system("pause");
}
void main()
{

Vertex v[N];
int n;
inputSample(v);
cout << "请输入源点序号:\n";
cin >> n;
Dijkstra(v[n], v);
cout << "请输入终点序号:\n";
cin >> n;
cout << "最短路径为:\n";
printPath(v[n], v);
cout << "路径权重:" << v[n].dist;
system("pause");

}

   

邻接表存储有向无环图以队列法拓扑排序

 

#include<iostream>
#include<iomanip>
#define N 16
using namespace std;
class listNode
{
public:
int data;
listNode* next;
};
class QueueNode
{
public:
int a;
QueueNode* next;
};
void enqueue(int a, QueueNode*& rear) {
rear->a = a;
rear->next = new QueueNode;
rear = rear->next;
rear->next = NULL;
}
int dequeue(QueueNode*& front) {
QueueNode* temp = front;
front = front->next;
temp->next = NULL;
return temp->a;
}
void inputLesson(listNode* head[])
{
head[0] = NULL;
head[1] = new listNode;
head[1]->data = 3;
head[1]->next = NULL;
head[2] = new listNode;
head[2]->data = 3;
head[2]->next = new listNode;
head[2]->next->data = 13;
head[2]->next->next = NULL;
head[3] = new listNode;
head[3]->data = 7;
head[3]->next = NULL;
head[4] = new listNode;
head[4]->data = 5;
head[4]->next = NULL;
head[5] = new listNode;
head[5]->data = 6;
head[5]->next = NULL;
head[6] = new listNode;
head[6]->data = 15;
head[6]->next = NULL;
head[7] = new listNode;
head[7]->data = 10;
head[7]->next = new listNode;
head[7]->next->data = 11;
head[7]->next->next = new listNode;
head[7]->next->next->data = 12;
head[7]->next->next->next = NULL;
head[8] = new listNode;
head[8]->data = 9;
head[8]->next = NULL;
head[9] = new listNode;
head[9]->data = 10;
head[9]->next = new listNode;
head[9]->next->data = 11;
head[9]->next->next = NULL;
head[10] = new listNode;
head[10]->data = 14;
head[10]->next = NULL;
head[11] = NULL;
head[12] = NULL;
head[13] = NULL;
head[14] = NULL;
head[15] = NULL;
}
void scanAll(listNode* list[], int inDegree[])
{
for (int i = 1; i < N; i++)
{
listNode* p;
p = list[i];
while (p)
{
inDegree[p->data]++;
p = p->next;
}
}
}
void topSort(listNode* list[])
{
int v;
int inDegree[N];
listNode* p;
QueueNode* front, *rear;
front = rear = new QueueNode;
for (int i = 0; i < N; i++) {
inDegree[i] = 0;
}
scanAll(list, inDegree);
for (int i = 1; i < N; i++) {
if (!inDegree[i]) {
enqueue(i, rear);
}
}
while (front != rear) {
v = dequeue(front);
cout << v << '\n';
p = list[v];
while (p) {
if (!(--inDegree[p->data])) {
enqueue(p->data, rear);
}
p = p->next;
}
}

}
void main()
{
listNode* list[N];
inputLesson(list);
topSort(list);
system("pause");
}

       

2016年3月