这篇文章是把之前发表在CSDN上面的一些东西搬运过来，是本科时候做的一些C++实验。
主要有以下几个实验：
1 C++实验一：面向过程的整型队列
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include<malloc.h>
struct Queue {
int* const elems; //elems申请内存用于存放队列的元素
const int max; //elems申请的最大元素个数max
int head, tail; //队列头head和尾tail，队空head=tail;初始head=tail=0
};
void initQueue(Queue* const p, int m); //初始化p指队列：最多申请m个元素
void initQueue(Queue* const p, const Queue& s); //用s深拷贝初始化p指队列
void initQueue(Queue* const p, Queue&& s); //用s移动初始化p指队列
int number(const Queue* const p); //返回p指队列的实际元素个数
int size(const Queue* const p); //返回p指队列申请的最大元素个数max
Queue* const enter(Queue* const p, int e); //将e入队列尾部，并返回p
Queue* const leave(Queue* const p, int& e); //从队首出元素到e，并返回p
Queue* const assign(Queue* const p, const Queue& q); //深拷贝赋s给队列并返回p
Queue* const assign(Queue* const p, Queue&& q); //移动赋s给队列并返回p
char* print(const Queue* const p, char* s);//打印p指队列至s并返回s
void destroyQueue(Queue* const p); //销毁p指向的队列
void initQueue(Queue* const p, int m) {
if (p == nullptr){
throw"The pointer must have allocated memory!";
return;
}
(int&)p->max = m; //强制类型转换为可写的指针
(int*&)p->elems = new int[m];
//*(int**)&(p->elems) = new int[m]; 这两种写法一样
// 相当于把只读的指针变量，强制转换为可写的指针变量
//cout << p->max << endl;
p->head = 0;
p->tail = 0;
}
void initQueue(Queue* const p, const Queue& s) {
//深拷贝的核心是：拷贝的内存块不要共用
if (p == nullptr){
throw"The pointer must have allocated memory!";
return;
}
p->head = s.head;
p->tail = s.tail;
(int&)p->max = s.max;
(int*&)p->elems = new int[s.max];
//初始化p
int i = s.head;
while (i != s.tail) {
//当i指向数组头时，说明已经复制完毕
p->elems[i] = s.elems[i];
i++;
i = i % p->max;
}
//深拷贝完成
}
void initQueue(Queue* const p, Queue&& s) {
//核心是两个对象用同一个内存块，相当于把前一个对象的内存块移动走了
if (p == nullptr){
throw"The pointer must have allocated memory!";
return;
}
if (p == &s) {
throw"Can't init a queue which is already inited!";
return;
}
p->head = s.head;
p->tail = s.tail;
(int&)p->max = s.max;
//构造p
(int*&)p->elems = s.elems;
//内存移动
(int *&)s.elems = nullptr;
s.head = 0;
s.tail = 0;
(int&)s.max = 0;
//处理s
}
int number(const Queue* const p) {
if (p->elems == nullptr)return NULL;//防止出现已经析构的队列访问number
int head = p->head;
int tail = p->tail;
int max = p->max;
return (tail - head + max) % max;
}
int size(const Queue* const p) {
return p->max;
}
Queue* const enter(Queue* const p, int e) {
int head = p->head;
int tail = p->tail;
//cout << number(p)<<endl;
//cout << p->max << endl;
if ((tail+1) % p->max == head) {
throw"Queue is full!";
return p;
}
p->elems[tail] = e;
p->tail = (p->tail+1) % (p->max);
//改变的时候都要确保不会出现访问到数组外
return p;
}
Queue* const leave(Queue* const p, int& e) {
if (p->head == p->tail) {
throw"Queue is empty!";
return p;
}
e = p->elems[p->head];
p->head = (p->head+1) % (p->max);
return p;
}
Queue* const assign(Queue* const p, const Queue& q) {
//深拷贝
p->head = q.head;
p->tail = q.tail;
(int &)p->max = q.max;
for (int i = 0; i < p->max; i++) {
p->elems[i] = q.elems[i];
}
return p;
}
Queue* const assign(Queue* const p, Queue&& q) {
//移动语义
if (p == &q)return p;
if (p->elems!=nullptr)delete []p->elems;
//initQueue(p, q);
(int*&)(p->elems) = q.elems;
(int&)(p->max) = q.max;
p->head = q.head;
p->tail = q.tail;
(int*&)(q.elems) = nullptr;
(int&)(q.max) = 0;
q.head = q.tail = 0;
return p;
}
char* print(const Queue* const p, char* s) {
if (p->max == 0) {
throw"Can't print a nonexistent Queue!";
return nullptr;
}
char* q = s;
int i = p->head;
while (i != p->tail) {
if(i==p->head)sprintf(q, "%d", p->elems[i]);//第一个不能加（+strlen(q)）否则会出现烫烫烫烫
else sprintf(q+strlen(q), "%d", p->elems[i]);//向s字符串中打印元素
if (i!=(p->tail-1)%p->max)
sprintf(q+strlen(q), ",");//向s字符串中打印逗号
i++;
if (i == p->max) i = 0;//下标回传
}//会自动打印'\0'的，不需要再额外添加
return s;
}
void destroyQueue(Queue* const p) {
if (p->elems != nullptr) {
delete[]p->elems;
(int*&)p->elems = nullptr;
(int &)p->max = 0;
}
else throw"Can't deconstruct an invild queue!";
}
2 c++实验二：面向对象的整形队列
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
class QUEUE {
int* const elems; //elems申请内存用于存放队列的元素
const int max; //elems申请的最大元素个数为max
int head, tail; //队列头head和尾tail，队空head=tail;初始head=tail=0
public:
QUEUE(int m); //初始化队列：最多申请m个元素
QUEUE(const QUEUE& q); //用q深拷贝初始化队列
QUEUE(QUEUE&& q)noexcept; //用q移动初始化队列
virtual operator int() const noexcept; //返回队列的实际元素个数
virtual int size() const noexcept; //返回队列申请的最大元素个数max
virtual QUEUE& operator<<(int e); //将e入队列尾部，并返回当前队列
virtual QUEUE& operator>>(int& e); //从队首出元素到e，并返回当前队列
virtual QUEUE& operator=(const QUEUE& q);//深拷贝赋值并返回被赋值队列
virtual QUEUE& operator=(QUEUE&& q)noexcept;//移动赋值并返回被赋值队列
virtual char* print(char* s) const noexcept;//打印队列至s并返回s
virtual ~QUEUE(); //销毁当前队列
};
QUEUE::QUEUE(int m):max(m),head(0),tail(0),elems(new int [m]){}
QUEUE::QUEUE(const QUEUE& q) : max(q.max), head(q.head), tail(q.tail), elems() {
(int *&)elems = new int[max];
for (int i = 0; i < max; i++) {
elems[i] = q.elems[i];
}
}
QUEUE::QUEUE(QUEUE&& q)noexcept :max(q.max), head(q.head), tail(q.tail),elems(){
if (this == &q) {
throw"Can't init an alive QUEUE!";
return;
}
(int*&)this->elems = q.elems;
//处理源队列q
(int *&)q.elems = 0;
(int&)q.max = 0;
q.head = q.tail = 0;
}
QUEUE::operator int() const noexcept {
if (elems == nullptr)return NULL;//防止出现已经析构的队列访问number
return (tail - head + max) % max;
}
int QUEUE::size() const noexcept {
return max;
}
QUEUE& QUEUE::operator<<(int e) {
if ((tail + 1) % max == head) {
throw"QUEUE is full!";
return *this;
}
elems[tail] = e;
tail = (tail + 1) % max;
//改变的时候都要确保不会出现访问到数组外
return *this;
}
QUEUE& QUEUE::operator>>(int& e) {
if (head == tail) {
throw"QUEUE is empty!";
return *this;
}
e = elems[head];
head = (head + 1) % max;
return *this;
}
QUEUE& QUEUE::operator=(const QUEUE& q) {
head = q.head;
tail = q.tail;
(int &)max = q.max;
for (int i = 0; i < max; i++) {
elems[i] = q.elems[i];
}
return *this;
}
QUEUE& QUEUE::operator=(QUEUE&& q)noexcept {
//移动语义
if (this == &q)return *this;
if (elems != nullptr)delete []elems;
(int*&)(elems) = q.elems;
(int&)(max) = q.max;
head = q.head;
tail = q.tail;
(int*&)(q.elems) = nullptr;
(int&)(q.max) = 0;
q.head = q.tail = 0;
return *this;
}
char* QUEUE::print(char* s)const noexcept {
if (max == 0) {
return nullptr;
}
char* q = s;
int i = head;
while (i != tail) {
if (i == head)sprintf(q, "%d", elems[i]);
else sprintf(q + strlen(q), "%d", elems[i]);//向s字符串中打印元素
if (i != (tail - 1) % max)
sprintf(q + strlen(q), ",");//向s字符串中打印逗号
i++;
if (i == max) i = 0;//下标回传
}
return s;
}
QUEUE::~QUEUE() {
if (elems != nullptr) {
delete[]elems;
(int*&)elems = nullptr;
(int&)max = 0;
}
}
3 c++实验三：面向对象的整形栈（双队列模拟）
要用双队列模拟整型栈，需要用到整型队列作为父类：队列实现程序
栈实现程序（子类）👇
#pragma once
#include"队列父类"//请自行替换
class STACK : public QUEUE {
QUEUE q;
public:
STACK(int m); //初始化栈：最多存放2m-2个元素
STACK(const STACK& s); //用栈s深拷贝初始化栈
STACK(STACK&& s)noexcept; //用栈s移动拷贝初始化栈
int size()const noexcept; //返回栈的容量即2m
operator int() const noexcept; //返回栈的实际元素个数
STACK& operator<<(int e); //将e入栈，并返回当前栈
STACK& operator>>(int& e); //出栈到e，并返回当前栈
STACK& operator=(const STACK& s); //深拷贝赋值并返回被赋值栈
STACK& operator=(STACK&& s)noexcept;//移动赋值并返回被赋值栈
char* print(char* b)const noexcept; //从栈底到栈顶打印栈元素
~STACK()noexcept; //销毁栈
};
STACK::STACK(int m):q(m),QUEUE(m){}
STACK::STACK(const STACK& s):q(s.q),QUEUE(s){}
STACK::STACK(STACK&& s)noexcept :q((QUEUE &&)s.q),QUEUE((QUEUE &&)s){}
int STACK::size()const noexcept {
return 2 * q.size();
}
STACK::operator int() const noexcept {
int first, second;
first = q.QUEUE::operator int();
second = QUEUE::operator int();
return first+second;
}
STACK& STACK::operator<<(int e){
if (this->operator int() >= this->size() - 2) {
throw"STACK is full!";
return *this;
}
if (this->QUEUE::operator int()>=this->QUEUE::size()-1) {
//如果this 满。直接插入q
q.QUEUE::operator<<(e);
return *this;
}
this->QUEUE::operator <<(e);
return *this;
}
STACK& STACK::operator>>(int& e) {
QUEUE* live = this;
if (this->operator int() == 0) {
throw"STACK is empty!";
return *this;
}
if (q.QUEUE::operator int() != 0) {
live = &q;
}
for (int i = 0; i < live->QUEUE::operator int()-1; i++) {
int temp;
live->QUEUE::operator>>(temp);
live->QUEUE::operator<<(temp);
}
live->QUEUE::operator>>(e);
return *this;
}
STACK& STACK::operator=(const STACK& s) {
this->QUEUE::operator=(s);
q.QUEUE::operator=(s.q);
return *this;
}
STACK& STACK::operator=(STACK&& s)noexcept {
this->QUEUE::operator=((QUEUE&&)s);
q.QUEUE::operator=((QUEUE&&)s.q);
return *this;
}
char* STACK::print(char* b)const noexcept {
if (this->operator int() == 0) {
b[0] = '\0';
return b;
}
if (q.QUEUE::operator int() == 0) {
this->QUEUE::print(b);
return b;
}
else if(this->QUEUE::operator int() == 0){
q.QUEUE::print(b);
return b;
}
else if (q.QUEUE::size() - 1 <= q.QUEUE::operator int()) {
char s[1024];
q.QUEUE::print(s);
this->QUEUE::print(b);
sprintf(b + strlen(b), ",");
strcat(b, s);
return b;
}
else {
char s[1024];
q.QUEUE::print(b);
this->QUEUE::print(s);
sprintf(b + strlen(b), ",");
strcat(b, s);
return b;
}
}
STACK::~STACK()noexcept {}
4 c++实验四：面向对象的矩阵运算
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <iomanip>
#include <exception>
#include <typeinfo>
#include <string.h>
template <typename T>
class MAT {
T* const e; //指向所有整型矩阵元素的指针
const int r, c; //矩阵的行r和列c大小
public:
MAT(int r, int c); //矩阵定义
MAT(const MAT& a); //深拷贝构造
MAT(MAT&& a)noexcept; //移动构造
virtual ~MAT()noexcept;
virtual T* const operator[ ](int r);//取矩阵r行的第一个元素地址，r越界抛异常
virtual MAT operator+(const MAT& a)const; //矩阵加法，不能加抛异常
virtual MAT operator-(const MAT& a)const; //矩阵减法，不能减抛异常
virtual MAT operator*(const MAT& a)const; //矩阵乘法，不能乘抛异常
virtual MAT operator~()const; //矩阵转置
virtual MAT& operator=(const MAT& a); //深拷贝赋值运算
virtual MAT& operator=(MAT&& a)noexcept; //移动赋值运算
virtual MAT& operator+=(const MAT& a); //“+=”运算
virtual MAT& operator-=(const MAT& a); //“-=”运算
virtual MAT& operator*=(const MAT& a); //“*=”运算
//print输出至s并返回s：列用空格隔开，行用回车结束
virtual char* print(char* s)const noexcept;
};
template <typename T>
MAT<T>::MAT(int r, int c) :r(r), c(c), e(nullptr) {
(T*&)e = new T[r * c];
}
template <typename T>
MAT<T>::MAT(const MAT& a) : r(a.r), c(a.c),e(nullptr) {
//if (*this == a) {
// throw"错误";
// return;
//}
(T*&)e = new T[r * c];
//不要在参数表中分配内存，要首先保证之前的指针是空指针
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
this->e[i * c + j] = a.e[i * c + j];
}//深拷贝赋值
}
}
template<typename T>
MAT<T>::MAT(MAT&& a)noexcept :r(a.r), c(a.c), e() {
(T*&)e = a.e;//移动赋值
//析构a
(T*&)a.e = nullptr;
(int&)a.r = 0;
(int&)a.c = 0;
}
template<typename T>
MAT<T>::~MAT()noexcept {
//printf("析构函数被调用\n");
if (this->e!=nullptr)delete[]e;
(T*&)e = nullptr;
//只需要显式写出new分配的内存
}
template<typename T>
T* const MAT<T>::operator[](int r) {
if (r >= this->r) {
throw"数组越界";
return nullptr;
}
return &(e[r * c]);//返回第r行第一个元素地址
}
template<typename T>
MAT<T> MAT<T>::operator+(const MAT& a)const {
//矩阵加法要保证行列相等才能相加
//printf("矩阵加法被调用\n");
if (a.r != r || a.c != c) {
throw"error";
return *this;
}
MAT<T> temp(r, c);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
temp[i][j] = e[i * c + j] + a.e[i * c + j];
}
}
//printf("+被调用\n");
return temp;
}
template<typename T>
MAT<T> MAT<T>::operator-(const MAT& a)const {
//矩阵减法要保证行列相等才能相加
//printf("矩阵减法被调用\n");
if (a.r != r || a.c != c) {
throw"error";
return *this;
}
MAT<T> temp(r, c);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
temp[i][j] = e[i * c + j] - a.e[i * c + j];
}
}
//printf("-被调用\n");
return temp;
}
template<typename T>
MAT<T> MAT<T>::operator*(const MAT& a)const {
//printf("矩阵乘法被调用\n");
//printf("a:\n");
/*for (int i = 0; i < a.r; i++) {
for (int j = 0; j < a.c; j++) {
printf("%d,", a.e[i * c + j]);
}
printf("\n");
}
printf("this:\n");
for (int i = 0; i < this->r; i++) {
for (int j = 0; j < this->c; j++) {
printf("%d,", this->e[i * c + j]);
}
printf("\n");
}*/
//if (a.r == 0 || r == 0) { return *this; }
if (c != a.r) {
throw"行列数不匹配，无法相乘";
return *this;
}
MAT<T> temp(r, a.c);
for (int i = 0; i < r; i++) {
for (int j = 0; j < a.c; j++) {
temp.e[i * a.c + j] = 0;
for (int k = 0; k < a.c; k++) {
temp.e[i * a.c + j] += e[i * a.c + k] * a.e[k * r + j];
}
}
}
/*printf("temp:\n");
for (int i = 0; i < temp.r; i++) {
for (int j = 0; j < temp.c; j++) {
printf("%d,", temp[i][j]);
}
printf("\n");
}*/
return temp;
}
template <typename T>
MAT<T> MAT<T>::operator~()const {
//printf("矩阵转置被调用\n");
if (r == 0 || c == 0) {
return *this;
}
MAT<T> temp(c, r);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
temp.e[j * r + i] = e[i * c + j];
}
}
return temp;
}
template<typename T>
MAT<T>& MAT<T>::operator=(const MAT& a) {
//printf("矩阵拷贝赋值被调用\n");
if (e == a.e) {
return *this;
}
if (this->e)delete[]e;
(T*&)e = new T[r * c];
(int&)r = a.r;
(int&)c = a.c;
//重新构造新的矩阵
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
this->e[i * c + j] = a.e[i * c + j];
}
}
return *this;
}
template<typename T>
MAT<T>& MAT<T>::operator=(MAT&& a)noexcept {
//printf("矩阵移动赋值被调用\n");
if (this->e == a.e) {
return *this;
}
if (this->e)delete[]e;
(int&)r = a.r;
(int&)c = a.c;
(T*&)e = a.e;
//析构原始矩阵
(T*&)a.e = nullptr;
(int&)a.r = (int&)a.c = 0;
return *this;
}
template<typename T>
MAT<T>& MAT<T>::operator+=(const MAT& a) {
//矩阵加法要保证行列相等才能相加
//printf("矩阵+=被调用\n");
if (a.r != r || a.c != c) {
throw"error";
return *this;
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
e[i * c + j] += a.e[i * c + j];
}
}
return *this;
}
template<typename T>
MAT<T>& MAT<T>::operator-=(const MAT& a) {
//矩阵减法要保证行列相等才能相加
//printf("矩阵-=被调用\n");
if (a.r != r || a.c != c) {
throw"error";
return *this;
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
e[i * c + j] -= a.e[i * c + j];
}
}
return *this;
}
template<typename T>
MAT<T>& MAT<T>::operator*=(const MAT& a) {
//printf("矩阵*=被调用\n");
if (this->c != a.r) {
throw"行列数不匹配，无法相乘";
return *this;
}
MAT<T> temp(r, a.c);
for (int i = 0; i < r; i++) {
for (int j = 0; j < a.c; j++) {
temp.e[i * a.c + j] = 0;
for (int k = 0; k < a.c; k++) {
temp.e[i * a.c + j] += e[i * a.c + k] * a.e[k * r + j];
}
}
}
//移动赋值给this
//printf("%d,%d\n", temp.r, a.r);
this->operator=((MAT<T>&&)temp);
/*if (this->e)delete[]e;
(int&)r = a.r;
(T*&)e = temp.e;
//析构原始矩阵
(T*&)temp.e = nullptr;
(int&)temp.r = (int&)temp.c = 0;
*/
//printf("%d\n",a.r);
return *this;
}
template<>
char* MAT<_int64>::print(char* s)const noexcept {
//printf("矩阵打印被调用\n");
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i + j == 0)sprintf(s, "%d ", e[i * c + j]);
else sprintf(s + strlen(s), "%d ", e[i * c + j]);
}
sprintf(s + strlen(s), "\n");
}
return s;
}
template<>
char* MAT<
int>::print(char* s)const noexcept {
//printf("矩阵打印被调用\n");
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i + j == 0)sprintf(s, "%d ", e[i * c + j]);
else sprintf(s + strlen(s), "%d ", e[i * c + j]);
}
sprintf(s + strlen(s), "\n");
}
return s;
}
template<>
char* MAT<long>::print(char* s)const noexcept {
//printf("矩阵打印被调用\n");
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i + j == 0)sprintf(s, "%f ", e[i * c + j]);
else sprintf(s + strlen(s), "%f ", e[i * c + j]);
}
sprintf(s + strlen(s), "\n");
}
return s;
}
5 C++实验5：弗洛伊德算法实验
弗洛伊德算法解析见弗洛伊德算法
采用邻接矩阵存储图，矩阵的行和列为图的节点，矩阵的内容为图的权重。
//#pragma comment(linker,"/STACK:614400000,614400000")
//在运行PRINT_ALL_PAIRS_SHORTEST_PATH的时候如果发生stack overflow，请使用上一行的语句扩展栈
#define INF 999999999//无穷大定义
#define NIL -1//Pi矩阵的不可达定义
#define _CRT_SECURE_NO_DEPRECATE
#define frow 11484 //这里是我的图的行数，改成自己图的行数即可
#define N 1000 //这是我节点的数量，改成自己节点的数量即可
#include <iostream>
#include<fstream>
#include<stdio.h>
#include<string>
using namespace std;
int* read(string filename, int n) {
ifstream fp(filename, ios::in);
int p1, p2, weight; //数据缓冲区
int *MAT = new int[n * n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
MAT[i * n + j] = INF;
if (i == j)MAT[i * n + j] = 0;
}
}
if (!fp) { // 判断文件是否存在
cerr << "open error." << endl;
return nullptr;
}
for (int i = 0; i < frow; i++) {
fp >> p1;
fp >> p2;
fp >> weight;
//cout << p1 << " " << p2 << " " << weight << endl;
if (p1 < 0 || p1>1000 || p2 < 0 || p2>1000) {
throw"读取数据错误";
}
MAT[p1 * n + p2] = weight;
}
return MAT;
}
void write(string filename, int* MAT,int n) {
ofstream fout(filename, ios::out);
if (!fout) { // 判断文件是否存在
cerr << "open error." << endl;
//exit(1); // 退出程序
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++){
if (MAT[i * n + j] == INF)fout << "INF" << ",";
else fout << MAT[i * n + j] << ",";
}
fout << endl;
}
fout.close();
}
void print(int *D, int n) {
//打印矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (D[i * n + j] == INF)cout << "INF ";
else
cout << D[i*n+j]<<" ";
}
cout << endl;
}
}
int** FLOYD_WARSHALL(int* W, int n) {
int* D;
int* PI;
int** res = new int* [2];
D = new int [n*n];
PI = new int[n * n];
res[0] = D;
res[1] = PI;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (W[i * n + j] == INF || i == j)PI[i * n + j] = NIL;
else PI[i * n + j] = i;
D[i * n + j] = W[i * n + j];
}
}//初始化D矩阵
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (D[i * n + j] > D[i * n + k] + D[k * n + j]) {
PI[i * n + j] = PI[k * n + j];
D[i * n + j] = D[i * n + k] + D[k * n + j];
}
}
}
printf("正在运算%d/%d\r", k+1,n);
}
return res;
}
void PRINT_ALL_PAIRS_SHORTEST_PATH(int *PI,int i,int j) {
if (i == j) {
cout << i<<" ";
}
else if (PI[i*N+j] == NIL) {
cout << "No path from " << i << " to " << j << " exits" << endl;
}
else
{
PRINT_ALL_PAIRS_SHORTEST_PATH(PI, i, PI[i * N + j]);
cout << j<<" ";
}
}
int main() {
/*int W[25] = { 0 ,3 ,8 ,INF,-4,INF,0 ,INF,1 ,7 ,INF,4 ,0 ,INF,INF,2 ,INF,-5 ,0 ,INF,INF,INF,INF,6 ,0 };
//print(W,5);
//cout << endl;
int** res;
res = FLOYD_WARSHALL(W, 5);
print(res[0], 5);
cout << endl;
print(res[1], 5);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cout << "从" << i << "到" << j << "的最短路径为:" << endl;
PRINT_ALL_PAIRS_SHORTEST_PATH(res[1], i, j, 5);
cout << endl;
}
}
delete[]res;*/
/*ifstream fp("weight_graph.txt", ios::in);
string buff;
int p1, p2, weight; //数据缓冲区
int* W = new int[N*N];
int** res;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
W[i * N + j] = INF;
if (i == j)W[i * N + j] = 0;
}
}
if (!fp) { // 判断文件是否存在
cerr << "open error." << endl;
return 1;
}
for (int i = 0; i < 11484; i++) {
for (int j = 0; j < 3; j++) {
if (j == 0)fp >> p1;
else if (j == 1)fp >> p2;
else fp >> weight;
}
//cout << p1 << " " << p2 << " " << weight << endl;
W[p1 * N + p2] = weight;
}
*/
int* W;
int** res;
W = read("weight_graph.txt", N);
res = FLOYD_WARSHALL(W,N);
//for (int i = 0; i < N; i++) {
//for (int j = 0; j < N; j++) {
//PRINT_ALL_PAIRS_SHORTEST_PATH(res[1], i, j);
//cout << endl;
//}
//}
cout << "正在存储D矩阵" << endl;
write("D-result.txt", res[0],N);
cout << "D矩阵存储完成" << endl;
cout << "正在存储Pi矩阵" << endl;
write("Pi-result.txt", res[1], N);
cout << "Pi矩阵存储完成" << endl;
if (W != nullptr) {
delete[]W;
}
if (res != nullptr) {
delete[]res;
}
/*ofstream dout("D-result.txt", ios::out);
ofstream pout("Pi-result.txt", ios::out);
string D;
string Pi;
if (!dout) { // 判断文件是否存在
cerr << "open error." << endl;
//exit(1); // 退出程序
}
if (!pout) { // 判断文件是否存在
cerr << "open error." << endl;
//exit(1); // 退出程序
}
dout << result[0];
dout << result[1];
fp.close();
dout.close();
pout.close();*/
return 0;
}