基於C++詳解資料結構(附帶例題)

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int  maxn = 10005;
const int  mod = 7654321;

typedef int ElementType;

typedef struct Node
{
	ElementType data[maxn];//元素
	int last;//最後一個元素的下標
}*List;

/*typedef是型別定義的意思。typedef struct 是為了使用這個結構體方便。
具體區別在於:
若struct node{}這樣來定義結構體的話。在申請node 的變數時，需要這樣寫，struct node n;
若用typedef，可以這樣寫，typedef struct node {}NODE; 。在申請變數時就可以這樣寫，NODE n;
區別就在於使用時，是否可以省去struct這個關鍵字。*/

//初始化一個空表
List CreatList()
{
	List L;
	L = (List)new int();
	//開闢一塊新空間
	L->last = -1;
	return L;
}

//查詢
ElementType Search(List L, ElementType x)
{
	int i = 0;
	while (i <= L->last)
	{
		if (L->data[i] == x)
			return i;
		i++;
	}
	return -1;
}

//插入
bool Insert(List L, int position, ElementType x)
{
	if (L->last == maxn - 1)
	{
		cout << "表已滿" << endl;
		return false;
	}
	if (position<0 || position>L->last + 1)
	{
		cout << "位置不合法" << endl;
		return false;
	}
	for (int i = L->last; i >= position; i--)
	{
		L->data[i + 1] = L->data[i];
	}
	L->data[position] = x;
	L->last++;
	return true;
}
//刪除
bool Delet(List L, int position)
{
	if (position<0 || position>L->last)
	{
		cout << "位置不合法" << endl;
		return false;
	}
	for (int i = position + 1; i <= L->last; i++)
	{
		L->data[i - 1] = L->data[i];
	}
	L->last--;
	return true;
}

int main()
{
	List L = CreatList();
	Insert(L, 0, 1);
	Insert(L, 1, 1);
	Insert(L, 2, 2);
	cout << L->data[0] << endl;
	Delet(L, 1);
	cout << L->data[1] << endl;

	cout << Search(L, 2) << endl;

	return 0;
}

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define maxn 10005
#define mod 7654321

typedef int ElementType;

typedef struct Node
{
	ElementType data;
	Node *next;
}*List;

//求表長
int Length(List L)
{
	List P = L;
	int num = 0;
	while (P)
	{
		P = P->next;
		num++;
	}
	return num;
}

//查詢
/*讀取，較順序儲存比較麻煩
1.宣告一個指標p指向連結串列的第一個節點，從1開始
2.當j<i時，就遍歷連結串列，讓p的指標向後移動，j++
3.若連結串列末尾為空，則說明第i個節點不存在
4.查詢成功，返回p的資料*/
List Search(List L, ElementType x)
{
	List P = L;
	while (L)
	{
		if (L->data == x)
			return P;
		L = L->next;
	}
	return NULL;
}

//插入
/*
1.宣告一指標p指向連結串列頭，初始化從1開始
2.p向後移動
3.查詢成功，插入
4.插入標準語句
s->next=p->next;
p->next=s
*/
bool Insert(List L, ElementType x, List P)
{
	List tem, Pre;

	/* 查詢P的前一個結點 */
	while (L)
	{
		if (L->next == P)
		{
			Pre = L;
			break;
		}
		L = L->next;
	}
	if (Pre == NULL)//不成功
		return false;
	else
	{
		tem = (List)malloc(sizeof(Node));
		tem->data = x;
		tem->next = P->next;
		Pre->next = tem;
		return true;
	}
}

//刪除
/*
類比於插入
刪除標準語句p->next=q->next
q中資料賦值給e
然後釋放q
*/
bool Delete(List L, List P)
{
	List Pre, tem;
	while (L)
	{
		if (L->next == P)
			Pre = L;
		L = L->next;
	}
	if (Pre == NULL)
		return false;
	else
	{
		Pre->next = P->next;
		return true;
	}
}

int main()
{

	return 0;
}

//首先中轉站C中，車廂符合先進後出的原則，是一個棧
#include<cstdio>
#include<stack>
using namespace std;
const int maxn = 1000 + 10;
int n, target[maxn];

int main()
{
	while (scanf_s("%d", &n) == 1)
	{
		stack<int> s;
		int a = 1, b = 1;
		for (int i = 1; i <= n; i++)
		{
			scanf_s("%d", &target[i]);
		}
		int ok = 1;
		while (b <= n)
		{
			if (a == target[b])
			{
				a++;
				b++;
			}
			else if (!s.empty() && s.top() == target[b])
			//運用empty和top函數，包含標頭檔案《stack》
			{
				s.pop();
				b++;

			}
			else if (a <= n)
				s.push(a++);
			else
			{
				ok = 0;
				break;
			}
	}
		printf("%sn", ok ? "yes" : "no");

	}
	return 0;
}

#include <iostream>
#include <stack>
using namespace std;
//表示式求值                                                                     
const int MaxSize = 100;
void trans(char exp[], char postexp[])
{
	stack<char> op;
	int i = 0, j = 0;
	//op.top = -1;
	while (*exp != '')
	{
		switch (*exp)
		{
		case '('://左括號進棧
			op.push(*exp);
			exp++;
			break;
		case ')'://將棧中「（」以前的運運算元依次刪除存入陣列exp中，然後將「（」刪除
			while (!op.empty() && op.top() != '(')
			{
				postexp[i++] = op.top();
				op.pop();
			}
			op.pop();
			exp++;
			break;
		case '+':
		case '-':
			while (!op.empty() && op.top() != '(')
			{//將棧中優先順序大於等於‘+'或'-'的運運算元退棧並存放到postexp中
				postexp[i++] = op.top();
				op.pop();
			}
			op.push(*exp);
			exp++;
			break;
		case '*':
		case '/':
			while (!op.empty() && (op.top() == '*' || op.top() == '/'))
			{//將棧中的「*」或者是「/」運運算元依次出棧並存放到postexp中
				postexp[i++] = op.top();
				op.pop();
			}
			op.push(*exp);
			exp++;
			break;
		case ' ':break;
		default:
			while (isdigit(*exp))
			{
				postexp[i++] = *exp;
				exp++;
			}
			postexp[i++] = '#';
		}
	}
	while (!op.empty())//最後的掃描工作
	{
		postexp[i++] = op.top();;
		op.pop();;
	}
	postexp[i] = '';
	cout << "字尾表示式" << endl;
	for (j = 0; j < i; j++)
	{
		if (postexp[j] == '#')
			j++;
		cout << postexp[j];
	}
	cout << endl;
}

float compvalue(char postexp[])
{
	stack<float> st;
	float a, b, c, d;

	while (*postexp != '')
	{
		switch (*postexp)
		{
		case '+':
			a = st.top();
			st.pop();
			b = st.top();;
			st.pop();;
			c = a + b;
			st.push(c);
			break;

		case '-':
			a = st.top();
			st.pop();
			b = st.top();;
			st.pop();;
			c = b - a;
			st.push(c);
			break;

		case '*':
			a = st.top();
			st.pop();
			b = st.top();;
			st.pop();;
			c = a * b;
			st.push(c);
			break;

		case '/':
			a = st.top();
			st.pop();
			b = st.top();;
			st.pop();;
			if (a != 0)
			{
				c = b / a;
				st.push(c);
			}
			else
			{
				cout << "除零錯誤!" << endl;
				exit(0);
			}
			break;
		default://進行最後的掃尾工作，將數位字元轉換成數值存放到d中
			d = 0;
			while (isdigit(*postexp))
			{
				d = 10 * d + *postexp - '0';
				postexp++;
			}
			st.push(d);
			break;

		}
		postexp++;
	}
	return (st.top());
}

int main()
{
	char exp[MaxSize] = "((18+6)*2-9)/2";
	char postexp[MaxSize] = { 0 };
	trans(exp, postexp);//exp存放中綴表示式,postexp存放字尾表示式
	printf("字尾表示式的值n");
	printf("%.2fn", compvalue(postexp));
	return 0;
}

#include<cstdio>
#include<cstring>
int a[100010][3],n,m;
//a[i][2]表示學號為i的同學右邊同學的學號
//a[i][3]表示學號為i的同學左邊同學的學號
int main()
{
    scanf("%d",&n); 
    int j=1;
    memset(a,0,sizeof(a));
    a[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        int x,y; scanf("%d %d",&x,&y);
        a[i][1]=i;
        if(y==0)
        //插入左邊
        { 
            a[a[x][3]][2]=i; a[i][2]=x;
            a[i][3]=a[x][3]; a[x][3]=i;
            if(x==j) j=i;
            //比較麻煩，要改連結串列
        }
        else
        //插入右邊
        {
            a[i][2]=a[x][2]; a[a[x][2]][3]=i;
            a[x][2]=i; a[i][3]=x;
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int x; scanf("%d",&x);
        if(a[x][1]!=0)
        //該同學還在 
        {
            a[x][1]=0;
            //踢掉
            a[a[x][3]][2]=a[x][2];
            a[a[x][2]][3]=a[x][3];
            n--;
            if(x==j) j=a[x][3];
        }
    }
    int i=1,x=j;
    while(i<=n)
    {
        printf("%d ",a[x][1]);
        x=a[x][2]; i++;
    }
    return 0;
}

//在c中許多是要單獨寫的，但是c++引入了string，其中包含了許多函數就不用自己直接寫了，為了學習我先用c寫，之後講解c++的string
#include <iostream>
#include <string>
using namespace std;
int main ()
{
    int size = 0;
    int length = 0;
    unsigned long maxsize = 0;
    int capacity=0;
    string str ("12345678");
    string str_custom;
    str_custom = str;
    str_custom.resize (5);
    size = str_custom.size();//大小
    length = str_custom.length();//長度
  
    cout << "size = " << size << endl;
    cout << "length = " << length << endl;
    return 0;
}

int i = pos;
int j = 1;
while (i <= s[0] && j <= t[0])//當i<s的長度，且j<t的長度，迴圈繼續
{
	if (s[i] = t[j])
	{
		i++;
		j++;//繼續
	}
	else//缺點：後退重新匹配
	{
		i = i - j + 2;//i回到上次匹配首位的下一位
		j = 1;//回到首位
	}
}
if (j > t[0])
return i - t[0];//不匹配
else
return 0;

typedef struct
{	
	char data[MaxSize];
	int length;			//串長
} SqString;
//SqString 是串的資料結構
//typedef重新命名結構體變數，可以用SqString t定義一個結構體。
void GetNext(SqString t,int next[])		//由模式串t求出next值
{
	int j,k;
	j=0;k=-1;
	next[0]=-1;//第一個字元前無字串，給值-1
	while (j<t.length-1) 
	//因為next陣列中j最大為t.length-1,而每一步next陣列賦值都是在j++之後
	//所以最後一次經過while迴圈時j為t.length-2
	{	
		if (k==-1 || t.data[j]==t.data[k]) 	//k為-1或比較的字元相等時
		{	
			j++;k++;
			next[j]=k;
			//對應字元匹配情況下，s與t指向同步後移
			//通過字串"aaaaab"求next陣列過程想一下這一步的意義
			//printf("(1) j=%d,k=%d,next[%d]=%dn",j,k,j,k);
       	}
       	else
		{
			k=next[k];
			**//我們現在知道next[k]的值代表的是下標為k的字元前面的字串最長相等前字尾的長度
			//也表示該處字元不匹配時應該回溯到的字元的下標
			//這個值給k後又進行while迴圈判斷，此時t.data[k]即指最長相等字首後一個字元**
			//為什麼要回退此處進行比較，我們往下接著看。其實原理和上面介紹的KMP原理差不多
			//printf("(2) k=%dn",k);
		}
	}
}
//kmp
int KMPIndex(SqString s,SqString t)  //KMP演演算法
{

	int next[MaxSize],i=0,j=0;
	GetNext(t,next);
	while (i<s.length && j<t.length) 
	{
		if (j==-1 || s.data[i]==t.data[j]) 
		{
			i++;j++;  			//i,j各增1
		}
		else j=next[j]; 		//i不變,j後退，現在知道為什麼這樣讓子串回退了吧
    }
    if (j>=t.length)
		return(i-t.length);  	//返回匹配模式串的首字元下標
    else  
		return(-1);        		//返回不匹配標誌
}

#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la,lb,j; 
char a[MAXN],b[MAXN];
int main()
{
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for (int i=2;i<=lb;i++)
	   {     
	   while(j&&b[i]!=b[j+1])
        j=kmp[j];    
       if(b[j+1]==b[i])j++;    
        kmp[i]=j;
       }
    j=0;
    for(int i=1;i<=la;i++)
	   {
          while(j>0&&b[j+1]!=a[i])
           j=kmp[j];
          if (b[j+1]==a[i]) 
           j++;
          if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];}
       }

    for (int i=1;i<=lb;i++)
    cout<<kmp[i]<<" ";
    return 0;
}

/*
Project: Tree_parent(樹-雙親表示法)
Date:    2019/02/25
Author:  Frank Yu
基本操作函數：
InitTree(Tree &T) 引數T，樹根節點 作用：初始化樹，先序遞迴建立
InsertNode(Tree &T, TElemType node) 插入樹的結點 引數：樹T,結點node 作用：在雙親陣列中插入結點，增加樹的結點值
InsertParent(Tree &T, TElemType node1, TElemType node2)//插入雙親陣列的雙親域 引數：樹T ，結點node1,結點node2
                                                       //作用：使雙親陣列中,node2對應的雙親域為node1的下標
GetIndegree(Tree &T, TElemType node)                   //得到某結點入度 引數：樹T，結點node 結點不存在返回-1
GetOutdegree(Tree &T, TElemType node)                  //得到某結點出度 引數：樹T，結點node 結點不存在返回-1
PreOrder(Tree T)  引數：樹T,根節點下標 作用：先序遍歷樹
PostOrder(Tree T) 引數：樹T,根節點下標 作用：後序遍歷樹
LevelOrder(Tree T)引數：樹T            作用：層序遍歷樹
功能實現函數：
CreateTree(Tree &T) 引數T，樹根節點 作用：建立樹，呼叫InsertNode,InsertParent
Traverse(Tree T)    引數T，樹根節點 作用：PreOrder InOrder PostOrder LevelOrder遍歷樹
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<iostream>
#define TElemType char
#define Max 100
using namespace std;
//樹的結點資料結構
typedef struct TNode
{
	TElemType data;//資料域
	int parent;    //雙親
}TNode;
//樹的資料結構
typedef struct Tree
{
 
	TNode parent[Max];
	int NodeNum;
 
}Tree;
//********************************基本操作函數********************************//
//初始化樹函數 引數：樹T 作用：規定資料域為#，則為空，雙親為-1,則為空
void InitTree(Tree &T)
{
	for (int i=0;i<Max;i++)
	{
		T.parent[i].data = '#';
		T.parent[i].parent = -1;
	}
	T.NodeNum = 0;
}
//插入樹的結點 引數：樹T,結點node 作用：在雙親陣列中插入結點，增加樹的結點值
bool InsertNode(Tree &T, TElemType node)
{
	
	if (node != '#')
	{
		T.parent[T.NodeNum++].data = node;//插入到雙親陣列中
		return true;
	}
	return false;
}
//插入雙親陣列的雙親域 引數：樹T ，結點node1,結點node2
//作用：使雙親陣列中,node2對應的雙親域為node1的下標
bool InsertParent(Tree &T, TElemType node1, TElemType node2)
{
	int place1, place2;
	place1 = -1;place2 = -1;
	for (int i=0;i<T.NodeNum;i++)//查詢兩點是否存在
	{
		if (node1 == T.parent[i].data)place1 = i;
		if (node2 == T.parent[i].data)place2 = i;
	}
	if (place1 != -1 && place2 != -1)//兩點均存在
	{
		T.parent[place2].parent = place1;
		return true;
	}
	return false;
}
//得到某結點入度 引數：樹T，結點node 結點不存在返回-1
int GetIndegree(Tree &T, TElemType node)
{
	int place = -1;
	for (int i = 0;i<T.NodeNum;i++)
	{
		if (T.parent[i].data == node)place = i;
	}
	if (place!=-1)//結點存在
	{
		if(T.parent[place].parent!=-1)return 1;//雙親只能有一個
		else return 0; //根節點沒有雙親，即沒有入度
	}
	return -1;
}
//得到某結點出度 引數：樹T，結點node 結點不存在返回-1
int GetOutdegree(Tree &T, TElemType node)
{
	int place = -1;
	int outdegree = 0;
	for (int i = 0;i<T.NodeNum;i++)
	{
		if (T.parent[i].data == node)place = i;
	}
	if (place != -1)
	{
		for (int i = 0;i < T.NodeNum;i++)
		{
			if (T.parent[i].parent == place)outdegree++;
		}
		return outdegree;
	}
	return -1;
}
//先序遍歷 引數：樹T,根節點下標
void PreOrder(Tree T,int i)
{
	if (T.NodeNum != 0)
	{
		cout << T.parent[i].data << " ";
		for(int j=0;j<T.NodeNum;j++)
		{
		  if(T.parent[j].parent==i)
		  PreOrder(T,j);//按左右先序遍歷子樹
		}
	}
}
//後序遍歷 引數：樹T,根節點下標
void PostOrder(Tree T,int i)
{
	if (T.NodeNum != 0)
	{
		
		for (int j = 0;j<T.NodeNum;j++)
		{
			if (T.parent[j].parent == i)
				PostOrder(T, j);//按左右先序遍歷子樹
		}
		cout << T.parent[i].data << " ";
	}
}
//層序遍歷 引數：樹T
void LevelOrder(Tree T)
{
	queue<TNode> q;//藉助佇列
	if (T.NodeNum!=0)
	{
		TNode temp;//暫存要出隊的結點
		q.push(T.parent[0]);//根結點入隊
		while (!q.empty())//佇列非空
		{
			temp = q.front();
			q.pop();
			cout<<temp.data<<" ";
			for (int j = 0;j<T.NodeNum;j++)
			{
				if (T.parent[T.parent[j].parent].data == temp.data)//當前結點的父節點的資料域與彈出的相同 
					//因為temp沒有儲存下標，只能按這種方式比較，預設結點名稱不同
					q.push(T.parent[j]);//佇列先進先出，先入左孩子
			}
		}
	}
}
//**********************************功能實現函數*****************************//
//建立樹，呼叫InsertNode,InsertParent
void CreateTree(Tree &T)
{
	int nodenum = 0;
	int parent;
	TElemType node,node1,node2;
	printf("請輸入樹的結點個數:");
	cin >> nodenum;
	parent = nodenum - 1;
	printf("請輸入樹的結點名稱（空格隔開）:");
	while (nodenum--)
	{
		cin >> node;
		InsertNode(T,node);
	}
	printf("請輸入樹的結點間的雙親關係（一對為一雙親關係，A B表示A為B的雙親）:n");
	while (parent--)
	{
		cin >> node1>>node2;
		InsertParent(T,node1,node2);
	}
	printf("n");
}
//入度
void Indegree(Tree &T)
{
	TElemType node;
	int indegree;
	printf("請輸入結點名稱:n");
	cin >> node;
	indegree = GetIndegree(T, node);
	if (-1 != indegree)
		cout << "該結點入度為：" << indegree << endl;
	else
		cout << "結點不存在。" << endl;
}
//出度
void Outdegree(Tree &T)
{
	TElemType node;
	int outdegree;
	printf("請輸入結點名稱:n");
	cin >> node;
	outdegree = GetOutdegree(T, node);
	if (-1 != outdegree)
		cout << "該結點出度為：" << outdegree << endl;
	else
		cout << "結點不存在。" << endl;
}
//遍歷功能函數 呼叫PreOrder InOrder PostOrder LevelOrder
void Traverse(Tree T)
{
	int choice;
	while (1)
	{
		printf("********1.先序遍歷    2.後序遍歷*********n");
		printf("********3.層次遍歷    4.返回上一單元*********n");
		printf("請輸入選單序號：n");
		scanf("%d", &choice);
		if (4 == choice) break;
		switch (choice)
		{
		case 1: {printf("樹先序遍歷序列:");PreOrder(T,0);printf("n");}break;
		case 2: {printf("樹後序遍歷序列:");PostOrder(T,0);printf("n");}break;
		case 3: {printf("樹層序遍歷序列:");LevelOrder(T);printf("n");}break;
		default:printf("輸入錯誤！！！n");break;
		}
	}
}
//選單
void menu()
{
	printf("********1.建立     2.某點入度*********n");
	printf("********3.某點出度 4.遍歷*************n");
	printf("********5.退出n");
}
//主函數
int main()
{
	Tree T;
	int choice = 0;
	InitTree(T);
	while (1)
	{
		menu();
		printf("請輸入選單序號：n");
 
		scanf("%d", &choice);
		if (5 == choice) break;
		switch (choice)
		{
		case 1:CreateTree(T);break;
		case 2:Indegree(T);break;
		case 3:Outdegree(T);break;
		case 4:Traverse(T);break;
		default:printf("輸入錯誤！！！n");break;
		}
	}
	return 0;
}

//指標域的個數就等於樹的度，其中樹的度又等於樹各個結點度的最大值
struct ChildNode
{
	int data；
	ChildNode*;
}
ChildNode *D;//d為最大結點
d.ChildNode;

struct Node
{
	int data;
	*firstchild,*ringtsib;
}
Node *Tree;

 struct BinaryTreeNode
   {
    struct BinTreeNode* _pLeft; // 指向當前節點左孩子
    struct BinTreeNode* _pRight; // 指向當前節點右孩子
    BTDataType _data; // 當前節點值域
   }

BinaryTreeNode *tree;

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

typedef BTNode* QDataType;
// 鏈式結構：表示佇列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 佇列的結構 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;

BTNode* CreateBTNode(BTDataType x);
// 通過前序遍歷的陣列"ABD##E#H##CF##G##"構建二元樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二元樹銷燬
void BinaryTreeDestory(BTNode** root);
// 二元樹節點個數
int BinaryTreeSize(BTNode* root);
// 二元樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root);
// 二元樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二元樹查詢值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二元樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root);
// 二元樹中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二元樹後序遍歷
void BinaryTreePostOrder(BTNode* root);

// 初始化佇列 
void QueueInit(Queue* q);
// 隊尾入佇列 
void QueuePush(Queue* q, QDataType data);
// 隊頭出佇列 
void QueuePop(Queue* q);
// 獲取佇列頭部元素 
QDataType QueueFront(Queue* q);
// 獲取佇列隊尾元素 
QDataType QueueBack(Queue* q);
// 獲取佇列中有效元素個數 
int QueueSize(Queue* q);
// 檢測佇列是否為空，如果為空返回非零結果，如果非空返回0 
int QueueEmpty(Queue* q);
// 銷燬佇列 
void QueueDestroy(Queue* q);

// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
// 判斷二元樹是否是完全二元樹
int BinaryTreeComplete(BTNode* root);

// 初始化佇列 
void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
}
// 隊尾入佇列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode *newnode = ((QNode*)malloc(sizeof(QNode)));
	newnode->_data = data;
	newnode->_next = NULL;
	if (q->_rear == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		//q->_rear = q->_rear->_next;
		q->_rear = newnode;
	}
}
// 隊頭出佇列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->_front == q->_rear)
	{
		free(q->_front);
		//free(q->_rear);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode *cur = q->_front->_next;
		free(q->_front);
		q->_front = cur;
	}
}
// 獲取佇列頭部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_front->_data;
}
// 獲取佇列隊尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_rear->_data;
}
// 獲取佇列中有效元素個數 
int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QNode* cur = q->_front;
	while (cur)
	{
		++size;
		cur = cur->_next;
	}
	return size;
}
// 檢測佇列是否為空，如果為空返回非零結果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL ? 1 : 0;
}
// 銷燬佇列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode *cur = q->_front;
	while (cur)
	{
		QNode *next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_front = q->_rear = NULL;
}

BTNode* CreateBTNode(BTDataType x)
{
	BTNode *node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
	return node;
}


// 通過前序遍歷的陣列"ABD##E#H##CF##G##"構建二元樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		return NULL;
	}
	BTNode *node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = a[*pi];
	++*pi;
	node->_left = BinaryTreeCreate(a, n, pi);
	++*pi;
	node->_right = BinaryTreeCreate(a, n, pi);
	return node;
}
// 二元樹銷燬
void BinaryTreeDestory(BTNode** root)
{
	if (*root != NULL)
	{
		if ((*root)->_left) // 有左孩子
			BinaryTreeDestory(&(*root)->_left); // 銷燬左孩子子樹
		if ((*root)->_right) // 有右孩子
			BinaryTreeDestory(&(*root)->_right); // 銷燬右孩子子樹

		free(*root); // 釋放根結點
		*root = NULL; // 空指標賦NULL
	}
}
// 二元樹節點個數
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
// 二元樹葉子節點個數
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL&&root->_right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
// 二元樹第k層節點個數
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
// 二元樹查詢值為x的節點
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* ret=BinaryTreeFind(root->_left,x);
	if (ret != NULL)
	{
		return ret;
	}
	ret = BinaryTreeFind(root->_right, x);
	if (ret != NULL)
	{
		return ret;
	}
	return NULL;
}
// 二元樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	printf("%c  ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
// 二元樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c  ", root->_data);
	BinaryTreeInOrder(root->_right);
}
// 二元樹後序遍歷
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c  ", root->_data);
}
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		printf("%c  ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
}
// 判斷二元樹是否是完全二元樹
int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		printf("%s ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return 0;
		}
	}
	return 1;
}

#include <stdio.h>  
#include <stdlib.h>  
#include <malloc.h>  
#define MAXSIZE 100  
typedef char ElemType;  
typedef enum  
{  
    Link,/*指向孩子結點*/Thread/*指向前驅或後繼*/  
} PointerTag;  
typedef struct Node  
{  
    ElemType data;  
    struct Node *lchild;  
    struct Node *rchild;  
    PointerTag ltag,rtag;  
}*BitThrTree,BitThrNode;  
  
BitThrTree pre;  
void CreateBitTree2(BitThrTree *T,char str[]);//建立搜尋二元樹  
void InThreading(BitThrTree p);//中序線索化二元樹  
int InOrderThreading(BitThrTree *Thrt,BitThrTree T);//通過中序遍歷二元樹T，使T中序線索化。Thrt是指向頭結點的指標  
int InOrderTraverse(BitThrTree T,int (*visit)(BitThrTree e));//中序遍歷線索二元樹  
int Print(BitThrTree T);//列印二元樹的結點和線索標誌  
BitThrNode* FindPoint(BitThrTree T,ElemType e);//線上索二元樹中查詢結點為e的指標  
BitThrNode* InOrderPre(BitThrNode *p);//中序前驅  
BitThrNode* InOrderPost(BitThrNode *p);//中序後繼  
void DestroyBitTree(BitThrTree *T);//銷燬二元樹  
 
 
#include "LinkBiTree.h"  
  
void CreateBitTree2(BitThrTree *T,char str[])//建立搜尋二元樹  
{  
    char ch;  
    BitThrTree stack[MAXSIZE];  
    int top = -1;  
    int flag,k;  
    BitThrNode *p;  
    *T = NULL,k = 0;  
    ch = str[k];  
    while(ch != '')  
    {  
        switch(ch)  
        {  
        case '(':  
            stack[++top] = p;  
            flag = 1;  
            break;  
        case ')':  
            top--;  
            break;  
        case ',':  
            flag = 2;  
            break;  
        default:  
            p = (BitThrTree)malloc(sizeof(BitThrNode));  
            p->data = ch;  
            p->lchild = NULL;  
            p->rchild = NULL;  
            if(*T == NULL)  
            {  
                *T = p;  
            }  
            else  
            {  
                switch(flag)  
                {  
                case 1:  
                    stack[top]->lchild = p;  
                    break;  
                case 2:  
                    stack[top]->rchild = p;  
                    break;  
                }  
                if(stack[top]->lchild)  
                {  
                    stack[top]->ltag = Link;  
                }  
                if(stack[top]->rchild)  
                {  
                    stack[top]->rtag = Link;  
                }  
            }  
        }  
        ch = str[++k];  
    }  
}  
void InThreading(BitThrTree p)//中序線索化二元樹  
{  
    if(p)//左子樹線索化  
    {  
        InThreading(p->lchild);  
        if(!p->lchild)//前驅線索化  
        {  
            p->ltag = Thread;  
            p->lchild = pre;  
        }  
        if(!pre->rchild)//後繼線索化  
        {  
            pre->rtag = Thread;  
            pre->rchild = p;  
        }  
        pre = p;  
        InThreading(p->rchild);//右子樹線索化  
    }  
}  
int InOrderThreading(BitThrTree *Thrt,BitThrTree T)//通過中序遍歷二元樹T，使T中序線索化。Thrt是指向頭結點的指標  
{  
    if(!(*Thrt = (BitThrTree)malloc(sizeof(BitThrNode))))  
    {  
        exit(-1);//為頭結點分配單元  
    }  
    (*Thrt)->ltag = Link;//修改前驅線索標誌  
    (*Thrt)->rtag = Thread;//修改後繼線索標誌  
    (*Thrt)->rchild = *Thrt;//將頭結點的rchild指標指向自己  
    if(!T)//如果二元樹為空，則將lchild指標指向自己  
    {  
        (*Thrt)->lchild = *Thrt;  
    }  
    else  
    {  
        (*Thrt)->lchild = T;//將頭結點的左指標指向根結點  
        pre = *Thrt;//將pre指向已經線索化的結點  
        InThreading(T);//中序遍歷進行中序線索化  
        /*將最後一個結點線索化*/  
        pre->rchild = *Thrt;//將最後一個結點的右指標指向頭結點  
        pre->rtag  = Thread;//修改最後一個結點的rtag標誌域  
        (*Thrt)->rchild = pre;//將頭結點的rchild指標指向最後一個結點  
    }  
    return 1;  
}  
int InOrderTraverse(BitThrTree T,int (*visit)(BitThrTree e))//中序遍歷線索二元樹  
{  
    BitThrTree p;  
    p = T->lchild ;//p指向根結點  
    while(p != T)//空樹或遍歷結束時，p == T  
    {  
        while(p->ltag == Link)  
        {  
            p = p->lchild ;  
        }  
        if(!visit(p))//列印  
        {  
            return 0;  
        }  
        while(p->rtag == Thread && p->rchild != T)//存取後繼結點  
        {  
            p = p->rchild ;  
            visit(p);  
        }  
        p = p->rchild ;  
    }  
    return 1;  
}  
int Print(BitThrTree T)//列印二元樹的結點和線索標誌  
{  
    static int k = 1;  
    printf("%2dt%st %2ct %stn",k++,T->ltag == 0 ? "Link":"Thread",T->data ,T->rtag == 1 ? "Thread":"Link");  
    return 1;  
}  
BitThrNode* FindPoint(BitThrTree T,ElemType e)//線上索二元樹中查詢結點為e的指標  
{  
    BitThrTree p;  
    p = T->lchild ;  
    while(p != T)  
    {  
        while(p->ltag == Link)  
        {  
            p = p->lchild ;  
        }  
        if(p->data == e)  
        {  
            return p;  
        }  
        while(p->rtag == Thread && p->rchild != T)  
        {  
            p = p->rchild ;  
            if(p->data == e)  
            {  
                return p;  
            }  
        }  
        p = p->rchild ;  
    }  
    return NULL;  
}  
BitThrNode* InOrderPre(BitThrNode *p)//中序前驅  
{  
    if(p->ltag == Thread)//如果p的標誌域ltag為線索，則p的左子樹結點為前驅  
    {  
        return p->lchild ;  
    }  
    else  
    {  
        pre = p->lchild ;//查詢p的左孩子的最右下端結點  
        while(pre->rtag == Link)//右子樹非空時，沿右鏈往下查詢  
        {  
            pre = pre->rchild ;  
        }  
        return pre;//pre就是最右下端結點  
    }  
}  
BitThrNode* InOrderPost(BitThrNode *p)//中序後繼  
{  
    if(p->rtag == Thread)//如果p的標誌域rtag為線索，則p的右子樹結點為後驅  
    {  
        return p->rchild ;  
    }  
    else  
    {  
        pre = p->rchild ;//查詢p的右孩子的最左下端結點  
        while(pre->ltag == Link)//左子樹非空時，沿左鏈往下查詢  
        {  
            pre = pre->lchild ;  
        }  
        return pre;//pre就是最左下端結點  
    }  
}  
void DestroyBitTree(BitThrTree *T)//銷燬二元樹  
{  
    if(*T)  
    {  
        if(!(*T)->lchild)  
        {  
            DestroyBitTree(&((*T)->lchild));  
        }  
        if(!(*T)->rchild)  
        {  
            DestroyBitTree(&((*T)->rchild));  
        }  
        free(*T);  
        *T = NULL;  
    }  
}  
 
 
#include "LinkBiTree.h"  
  
int main(void)  
{  
    BitThrTree T,Thrt;  
    BitThrNode *p,*pre,*post;  
    CreateBitTree2(&T,"(A(B(,D(G)),C(E(,H),F)))");  
    printf("線索二元樹的輸出序列：n");  
    InOrderThreading(&Thrt,T);  
    printf("序列  前驅標誌  結點  後繼標誌n");  
    InOrderTraverse(Thrt,Print);  
    p = FindPoint(Thrt,'D');  
    pre = InOrderPre(p);  
    printf("元素D的中序直接前驅元素是：%cn",pre->data);  
    post = InOrderPost(p);  
    printf("元素D的中序直接後驅元素是：%cn",post->data);  
    p = FindPoint(Thrt,'E');  
    pre = InOrderPre(p);  
    printf("元素E的中序直接前驅元素是：%cn",pre->data);  
    post = InOrderPost(p);  
    printf("元素E的中序直接後驅元素是：%cn",post->data);  
    DestroyBitTree(&Thrt);  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define MAXL 100010

int N, M, A[MAXL];
vector<int> G[MAXL]; //vector存圖 

void dfs(int x, int d) {
	if(A[x]) return; //存取過 
	A[x] = d;
	for(int i=0; i<G[x].size(); i++)
		dfs(G[x][i], d);
}

int main() {
	int u, v;
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++) {
		scanf("%d%d", &u, &v);
		G[v].push_back(u); //反向建邊 
	}
	for(int i=N; i; i--) dfs(i, i); 
	for(int i=1; i<=N; i++) printf("%d ", A[i]);
	printf("n");
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int Len = 200 * 200 * 5 + 5,Inf = 1e9;
int dep[Len],cnt = 1,head[Len],s,t,S,T,cur[Len],val[Len],a[205][205],sumh[205],suml[205],LL,RR,n,m,sum,ans,minn;
struct node
{
	int next,to,w;
}edge[Len << 1];
void add(int from,int to,int w)
{
	edge[++ cnt].to = to;
	edge[cnt].w = w;
	edge[cnt].next = head[from];
	head[from] = cnt;
}
int BFS()
{
	queue<int> q;
	memset(dep , 0 , sizeof dep);
	q.push(S);dep[S] = 1;cur[S] = head[S];
	while(!q.empty())
	{
		int p = q.front() ; q.pop();
		for(int e = head[p] ; e ; e = edge[e].next)
		{
			int to = edge[e].to;
			if(!dep[to] && edge[e].w)
			{
				dep[to] = dep[p] + 1;
				cur[to] = head[to];
				if(T == to) return dep[T];
				q.push(to);
			}
		}
	}
	return dep[T];
}
int dfs(int u,int In)
{
	if(u == T) return In;
	int Out = 0;
	for(int e = cur[u] ; e && In > 0 ; e = edge[e].next)
	{
		cur[u] = e;
		int to = edge[e].to;
		if(edge[e].w && dep[to] == dep[u] + 1)
		{
			int res = dfs(to , min(In , edge[e].w));
			In -= res;
			Out += res;
			edge[e].w -= res;
			edge[e ^ 1].w += res; 
		}
	}
	return (!Out) ? dep[u] = 0 : Out;
}
int Clone(int x,int y){return (x - 1) * n + y;}
bool check(int res)
{
	memset(head , 0 , sizeof head) ; cnt = 1;
	memset(val , 0 , sizeof val);
	sum = ans = 0;
	for(int i = 1 ; i < n ; i ++)//處理行
	{
		int now = Clone(i , m) , L = sumh[i] - res , R = sumh[i] + res;//L = sumh[i] - res , R = sumh[i] + res
		add(s , now , R - L) , add(now , s , 0);
		val[now] += L , val[s] -= L;
	}
	for(int i = 1 ; i < m ; i ++)
	{
		int now = Clone(n , i) , L = suml[i] - res , R = suml[i] + res;
		add(now , s , R - L) , add(s , now , 0);
		val[s] += L , val[now] -= L; 
	}
	for(int i = 1 ; i < n ; i ++)
	{
		int now = Clone(i , m);
		for(int j = 1 ; j < m ; j ++)
		{
			int to = Clone(i , j);
			add(now , to , RR - LL) , add(to , now , 0);
			val[to] += LL , val[now] -= LL; 
		}
	} 
	for(int i = 1 ; i < m ; i ++)
	{
		int now = Clone(n , i);
		for(int j = 1 ; j < n ; j ++)
		{
			int to = Clone(j , i);
			add(to , now , RR - LL) , add(now , to , 0);
			val[now] += LL , val[to] -= LL;
		}
	}
	for(int i = 1 ; i <= n * m + 1 ; i ++)
	{
		if(val[i] > 0) add(S , i , val[i]) , add(i , S , 0) , sum += val[i];
		if(val[i] < 0) add(i , T , -val[i]) , add(T , i , 0);
	}
	while(BFS()) ans += dfs(S , Inf);
	if(ans == sum) return true;
	return false;
}
signed main()
{
	minn = 1e9;
	scanf("%d %d",&n,&m);
	n ++ , m ++;
	s = n * m , t = n * m + 1 , S = n * m + 2 , T = n * m + 3; 
	for(int i = 1 ; i <= n - 1 ; i ++)
		for(int j = 1 ; j <= m - 1 ; j ++) 
		{
			scanf("%d",&a[i][j]);
			sumh[i] += a[i][j] , suml[j] += a[i][j];
		}
	for(int i = 1 ; i <= n - 1 ; i ++) minn = min(minn , sumh[i]);
	for(int i = 1 ; i <= m - 1 ; i ++) minn = min(minn , suml[i]);
	scanf("%d %d",&LL,&RR);
	int l = 0 , r = minn,anss;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(check(mid)) anss = mid , r = mid - 1;
		else l = mid + 1; 
	}
	printf("%dn",anss);
	return 0;
}

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define MAXL 100010

int N, M, A[MAXL];
vector<int> G[MAXL]; //vector存圖 

void dfs(int x, int d) {
	if(A[x]) return; //存取過 
	A[x] = d;
	for(int i=0; i<G[x].size(); i++)
		dfs(G[x][i], d);
}

int main() {
	int u, v;
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++) {
		scanf("%d%d", &u, &v);
		G[v].push_back(u); //反向建邊 
	}
	for(int i=N; i; i--) dfs(i, i); 
	for(int i=1; i<=N; i++) printf("%d ", A[i]);
	printf("n");
	return 0;
}

#include<iostream>//P1443
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>//運用了佇列
#include<cmath>
using namespace std;
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int dy[8]={2,1,-1,-2,2,1,-1,-2};//8個方向
queue<pair<int,int> > q;
int f[500][500];//存步數
bool vis[500][500];//走沒走過
int main()
{
	int n,m,x,y;
	memset(f,-1,sizeof(f));memset(vis,false,sizeof(vis));
	cin>>n>>m>>x>>y;
	f[x][y]=0;vis[x][y]=true;q.push(make_pair(x,y));
	while(!q.empty())
	{
		int xx=q.front().first,yy=q.front().second;q.pop();//取隊首並出隊
		for(int i=0;i<8;i++)
		{
			int u=xx+dx[i],v=yy+dy[i];
			if(u<1||u>n||v<1||v>m||vis[u][v])continue;//出界或走過就不走
		    vis[u][v]=true;q.push(make_pair(u,v));f[u][v]=f[xx][yy]+1;
		}
	}
	for(int i=1;i<=n;i++)
	 {for(int j=1;j<=m;j++)printf("%-5d",f[i][j]);printf("n");}//注意場寬！！
	return 0;
}

#pragma once
#include<iostream>
#include<string>
using namespace std;

//鄰接矩陣儲存
//記錄起點到每個頂點的最短路徑的資訊
struct Dis {
    string path;
    int value;
    bool visit;
    Dis() {
        visit = false;
        value = 0;
        path = "";
    }
};

class Graph_DG {
private:
    int vexnum;   //圖的頂點個數
    int edge;     //圖的邊數
    int **arc;   //鄰接矩陣
    Dis * dis;   //記錄各個頂點最短路徑的資訊
public:
    //建構函式
    Graph_DG(int vexnum, int edge);
    //解構函式
    ~Graph_DG();
    // 判斷我們每次輸入的的邊的資訊是否合法
    //頂點從1開始編號
    bool check_edge_value(int start, int end, int weight);
    //建立圖
    void createGraph();
    //列印鄰接矩陣
    void print();
    //求最短路徑
    void Dijkstra(int begin);
    //列印最短路徑
    void print_path(int);
};

#include"Dijkstra.h"

//建構函式
Graph_DG::Graph_DG(int vexnum, int edge) {
    //初始化頂點數和邊數
    this->vexnum = vexnum;
    this->edge = edge;
    //為鄰接矩陣開闢空間和賦初值
    arc = new int*[this->vexnum];
    dis = new Dis[this->vexnum];
    for (int i = 0; i < this->vexnum; i++) {
        arc[i] = new int[this->vexnum];
        for (int k = 0; k < this->vexnum; k++) {
            //鄰接矩陣初始化為無窮大
                arc[i][k] = INT_MAX;
        }
    }
}
//解構函式
Graph_DG::~Graph_DG() {
    delete[] dis;
    for (int i = 0; i < this->vexnum; i++) {
        delete this->arc[i];
    }
    delete arc;
}

// 判斷我們每次輸入的的邊的資訊是否合法
//頂點從1開始編號
bool Graph_DG::check_edge_value(int start, int end, int weight) {
    if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
        return false;
    }
    return true;
}

void Graph_DG::createGraph() {
    cout << "請輸入每條邊的起點和終點（頂點編號從1開始）以及其權重" << endl;
    int start;
    int end;
    int weight;
    int count = 0;
    while (count != this->edge) {
        cin >> start >> end >> weight;
        //首先判斷邊的資訊是否合法
        while (!this->check_edge_value(start, end, weight)) {
            cout << "輸入的邊的資訊不合法，請重新輸入" << endl;
            cin >> start >> end >> weight;
        }
        //對鄰接矩陣對應上的點賦值
        arc[start - 1][end - 1] = weight;
        //無向圖新增上這行程式碼
        //arc[end - 1][start - 1] = weight;
        ++count;
    }
}

void Graph_DG::print() {
    cout << "圖的鄰接矩陣為：" << endl;
    int count_row = 0; //列印行的標籤
    int count_col = 0; //列印列的標籤
    //開始列印
    while (count_row != this->vexnum) {
        count_col = 0;
        while (count_col != this->vexnum) {
            if (arc[count_row][count_col] == INT_MAX)
                cout << "∞" << " ";
            else
            cout << arc[count_row][count_col] << " ";
            ++count_col;
        }
        cout << endl;
        ++count_row;
    }
}
void Graph_DG::Dijkstra(int begin){
    //首先初始化我們的dis陣列
    int i;
    for (i = 0; i < this->vexnum; i++) {
        //設定當前的路徑
        dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
        dis[i].value = arc[begin - 1][i];
    }
    //設定起點的到起點的路徑為0
    dis[begin - 1].value = 0;
    dis[begin - 1].visit = true;

    int count = 1;
    //計算剩餘的頂點的最短路徑（剩餘this->vexnum-1個頂點）
    while (count != this->vexnum) {
        //temp用於儲存當前dis陣列中最小的那個下標
        //min記錄的當前的最小值
        int temp=0;
        int min = INT_MAX;
        for (i = 0; i < this->vexnum; i++) {
            if (!dis[i].visit && dis[i].value<min) {
                min = dis[i].value;
                temp = i;
            }
        }
        //cout << temp + 1 << "  "<<min << endl;
        //把temp對應的頂點加入到已經找到的最短路徑的集合中
        dis[temp].visit = true;
        ++count;
        for (i = 0; i < this->vexnum; i++) {
            //注意這裡的條件arc[temp][i]!=INT_MAX必須加，不然會出現溢位，從而造成程式異常
            if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
                //如果新得到的邊可以影響其他為存取的頂點，那就就更新它的最短路徑和長度
                dis[i].value = dis[temp].value + arc[temp][i];
                dis[i].path = dis[temp].path + "-->v" + to_string(i + 1);
            }
        }
    }

}
void Graph_DG::print_path(int begin) {
    string str;
    str = "v" + to_string(begin);
    cout << "以"<<str<<"為起點的圖的最短路徑為：" << endl;
    for (int i = 0; i != this->vexnum; i++) {
        if(dis[i].value!=INT_MAX)
        cout << dis[i].path << "=" << dis[i].value << endl;
        else {
            cout << dis[i].path << "是無最短路徑的" << endl;
        }
    }
}

#include"Dijkstra.h"

//檢驗輸入邊數和頂點數的值是否有效，可以自己推算為啥：
//頂點數和邊數的關係是：((Vexnum*(Vexnum - 1)) / 2) < edge
bool check(int Vexnum, int edge) {
    if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
        return false;
    return true;
}
int main() {
    int vexnum; int edge;

    cout << "輸入圖的頂點個數和邊的條數：" << endl;
    cin >> vexnum >> edge;
    while (!check(vexnum, edge)) {
        cout << "輸入的數值不合法，請重新輸入" << endl;
        cin >> vexnum >> edge;
    }
    Graph_DG graph(vexnum, edge);
    graph.createGraph();
    graph.print();
    graph.Dijkstra(1);
    graph.print_path(1);
    system("pause");
    return 0;
}

//總體上是一個二重回圈加上一個三重回圈，主要運用於所有頂點到所有頂點的最短路徑問題
void ShortestPath FLOYD(MGraph G, PathMatrix &p[], DistanceMatrix &D){
	//用Floyd演演算法求有向網中各對頂點v和w之間的最短路徑P[v][w]及其帶權長
	//度D[v][w].若P[v][w][u]為TRUE,則u是從v到w當前求得最短路徑上的頂點。
	for(v = 0; v < G.vexnum; ++v)		//各對結點之間初始已知路徑及距離
		for(w = 0; w < G.vexnum; ++w){
			D[v][w] = G.arcs[v][w];
			for(u = 0; u < G.vexnum; ++w)	P[v][w][u] = FALSE;
			if(D[v][w] < INFINITY){				//從v到w有直接路徑
				P[v][w][v] = TRUE; P[v][w][w] = TRUE;
			}//if
		}//for
	
	for(u = 0; u < G.vexnum; ++u)
		for(v = 0; v<G.vexnum; ++v)
			for(w = 0; w<G.vexnum; ++w)
				if(D[v][u] + D[u][w] < D[v][w]){		//從v經u到w的一條路徑更短
					D[v][w] = D[v][u] + D[u][w];
					for(i = 0; i<G.vexnum; ++i)
						P[v][w][i] = P[v][u][i] || P[u][w][i];
						}//if
}//ShortestPath.FLOYD