基于C++詳解數(shù)據(jù)結(jié)構(gòu)(附帶例題)
前言
應(yīng)廣大支持者的要求，隨我自身學(xué)習(xí)之余，肝數(shù)據(jù)結(jié)構(gòu)，開(kāi)車(chē)只是暫時(shí)的，飆車(chē)才是認(rèn)真的，數(shù)據(jù)結(jié)構(gòu)開(kāi)始了，本文用c++編寫(xiě)，如果有不足的地方歡迎大家補(bǔ)充
數(shù)據(jù)結(jié)構(gòu)
通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率，這也是一個(gè)優(yōu)秀的程序員必須掌握的一項(xiàng)基本功，無(wú)論你學(xué)哪個(gè)語(yǔ)言，又提到了語(yǔ)言，這里在推銷一波如果你還在糾結(jié)到底哪門(mén)語(yǔ)言作為主語(yǔ)言的話可以看文末
本文我主要講解數(shù)據(jù)結(jié)構(gòu)中的
- 線性表
- 棧與隊(duì)列
- 串
- 樹(shù)
- 圖
這也就包含了所有的數(shù)據(jù)結(jié)構(gòu)了，那廢話不多說(shuō)，我們開(kāi)始吧！
線性表
首先它是線性的，就像線一樣，小時(shí)候都玩過(guò)牽著手并排走的游戲，話說(shuō)我都幾年沒(méi)有牽過(guò)女孩手了，當(dāng)時(shí)我們可以知道自己前面的人和后面的人是誰(shuí)，像有線一樣連在了一起
官方定義：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列
序列，有限是我們應(yīng)該著重注意的地方，還是小朋友牽手，他是一個(gè)有限的序列，其中小朋友視為數(shù)據(jù)元素，，例子有很多：月份，星座，直系關(guān)系等等都是線性表
下面在拿我自己舉一個(gè)例子，
碼神—>18—>155*********0111—>西安
順序存儲(chǔ)
這一通操作下來(lái)相信大家應(yīng)該對(duì)線性表有一個(gè)基礎(chǔ)的了解了吧，接著我們回到上述的拉手問(wèn)題中，話說(shuō)年輕碼手當(dāng)時(shí)喜歡一個(gè)女孩，我們姑且稱她為小苗吧，我就希望自己可以拉上小苗的手，首先我要找到她，然后重新站到小苗的身邊，這時(shí)線性表就發(fā)生了重排，但是啊，小苗不喜歡我，直接就出列了，所以又出現(xiàn)了刪除的操作，上面我們可以看出來(lái)，這個(gè)線性表的基操就有查找，插入，刪除了，秉承學(xué)著就練這的原則，我現(xiàn)在來(lái)幫大家實(shí)現(xiàn)一下
#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;//最后一個(gè)元素的下標(biāo)
}*List;
/*typedef是類型定義的意思。typedef struct 是為了使用這個(gè)結(jié)構(gòu)體方便。
具體區(qū)別在于:
若struct node{}這樣來(lái)定義結(jié)構(gòu)體的話。在申請(qǐng)node 的變量時(shí)，需要這樣寫(xiě)，struct node n;
若用typedef，可以這樣寫(xiě)，typedef struct node {}NODE; 。在申請(qǐng)變量時(shí)就可以這樣寫(xiě)，NODE n;
區(qū)別就在于使用時(shí)，是否可以省去struct這個(gè)關(guān)鍵字。*/
//初始化一個(gè)空表
List CreatList()
{
List L;
L = (List)new int();
//開(kāi)辟一塊新空間
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;
}我們來(lái)談一下優(yōu)缺點(diǎn)吧，實(shí)際上也很明顯，比如我要找到小苗，一眼就能看到，但是當(dāng)我要插入，或者小苗要出來(lái)時(shí)，變化的就是整個(gè)隊(duì)伍了，還有不太明顯的地方：當(dāng)線性表長(zhǎng)度不確定時(shí)，難以確定儲(chǔ)存空間的大學(xué)，還可能造成存儲(chǔ)空間的“碎片”，用new。
鏈?zhǔn)?/h3>
上面我們說(shuō)到順序存儲(chǔ)最大的缺點(diǎn)就是插入和刪除要?jiǎng)铀械脑?，為了解決這個(gè)問(wèn)題我們引出了鏈?zhǔn)酱鎯?chǔ)
總體思路就是讓相鄰的元素之間留夠空位置，可能實(shí)現(xiàn)有點(diǎn)困難，但是 換個(gè)思路就簡(jiǎn)單多了，也就是不要考慮相鄰位置了，哪里有空位置就插到哪里，而只是讓每個(gè)元素知道她下一個(gè)元素的位置，這樣做的話，我們可以在第一個(gè)元素時(shí)，就知道第二個(gè)元素的位置，從而再找到第三個(gè)元素的位置，有點(diǎn)像單線索的偵探游戲，下面我們用代碼來(lái)看一下具體的實(shí)現(xiàn)步驟吧。
#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;
//求表長(zhǎng)
int Length(List L)
{
List P = L;
int num = 0;
while (P)
{
P = P->next;
num++;
}
return num;
}
//查找
/*讀取，較順序存儲(chǔ)比較麻煩
1.聲明一個(gè)指針p指向鏈表的第一個(gè)節(jié)點(diǎn)，從1開(kāi)始
2.當(dāng)j<i時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，j++
3.若鏈表末尾為空，則說(shuō)明第i個(gè)節(jié)點(diǎn)不存在
4.查找成功，返回p的數(shù)據(jù)*/
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開(kāi)始
2.p向后移動(dòng)
3.查找成功，插入
4.插入標(biāo)準(zhǔn)語(yǔ)句
s->next=p->next;
p->next=s
*/
bool Insert(List L, ElementType x, List P)
{
List tem, Pre;
/* 查找P的前一個(gè)結(jié)點(diǎn) */
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;
}
}
//刪除
/*
類比于插入
刪除標(biāo)準(zhǔn)語(yǔ)句p->next=q->next
q中數(shù)據(jù)賦值給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;
}小結(jié)
若線性表需要頻繁的查找，很少進(jìn)行插入和刪除操作時(shí)，應(yīng)該選用順序儲(chǔ)存結(jié)構(gòu)。
若線性表需要頻繁的插入和刪除操作時(shí)，很少查找時(shí)，應(yīng)該選用鏈表結(jié)構(gòu)。
why？
從時(shí)間性能來(lái)考慮的話，查找：
順序結(jié)構(gòu)O（1），單鏈表（N)
插入刪除
順序：平均移動(dòng)一半的距離O（N）
單鏈表在找出位置的指針后，插入和刪除的時(shí)間復(fù)雜度僅為O（1）
從空間復(fù)雜度來(lái)看的話：
順序需要預(yù)分配存儲(chǔ)空間，，but數(shù)據(jù)是不確定的，分大浪費(fèi)，分小上溢。
單鏈表不需要分配儲(chǔ)存空間，只要有就可以分配，元素個(gè)數(shù)也不受限制
So，當(dāng)數(shù)據(jù)大小不確定的時(shí)候，最好使用單鏈表，但是像一年12月，一周7天這種還是用順序存儲(chǔ)比較效率高一點(diǎn)。
棧和隊(duì)列
棧：僅在表尾進(jìn)行插入和刪除操作的線性表
隊(duì)列：只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表
棧
如果說(shuō)棧最大特征應(yīng)該就是：先進(jìn)后出了，像以前的沙漠之鷹的彈夾一樣，先放入的子彈，后面才能打出
棧的應(yīng)用在軟件中也比較普遍，像瀏覽器中的后退一樣單擊后可以按訪問(wèn)順序的逆序加載瀏覽過(guò)的網(wǎng)頁(yè)
還有許多的文本編輯軟件的“ctrl+z”的撤銷功能，也是通過(guò)棧來(lái)實(shí)現(xiàn)的
了解了什么是棧之后，我們來(lái)說(shuō)棧的幾個(gè)概念
- 棧頂：允許插入和刪除的一端
- 棧底：棧頂?shù)牧硪欢?/li>
- 空棧：不含任何元素的
- 還可以說(shuō)是棧是限定僅在表尾（棧頂）進(jìn)行插入和刪除操作的線性表
- 插入就叫進(jìn)棧
- 刪除稱為出棧
就像沙漠之鷹的彈夾一樣，進(jìn)棧為子彈彈入彈夾，出棧為子彈彈出彈夾
看例題吧，嘗試一種新的寫(xiě)法，用算法題來(lái)解決棧的問(wèn)題，因?yàn)槲腋杏X(jué)實(shí)現(xiàn)和線性表的差不多
鐵軌：uva514
某城市有一個(gè)火車(chē)站，鐵軌鋪設(shè)如圖。有n節(jié)車(chē)廂從A方向駛?cè)胲?chē)站，按進(jìn)站的順序編號(hào)為1～n。你的任務(wù)是判斷是否能讓他們按照某種特定的順序進(jìn)入B方向的鐵軌并駛出車(chē)站。例如，出棧順序（5 4 1 2 3）是不可能的，但（5 4 3 2 1）是可能的。 為了重組車(chē)廂，你可以借助中轉(zhuǎn)站C。這是一個(gè)可以停放任意多節(jié)車(chē)廂的車(chē)站，但由于末端封頂，駛?cè)隒的車(chē)廂必須按照相反的順序駛出C。對(duì)于每節(jié)車(chē)廂，一旦從A移入C，就不能返回A了;一旦從C移入B，就不能返回C了。也就是說(shuō)，在任意時(shí)刻，只有兩種選擇：A到C和C到B。
//首先中轉(zhuǎn)站C中，車(chē)廂符合先進(jìn)后出的原則，是一個(gè)棧
#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])
//運(yùn)用empty和top函數(shù)，包含頭文件《stack》
{
s.pop();
b++;
}
else if (a <= n)
s.push(a++);
else
{
ok = 0;
break;
}
}
printf("%s\n", ok ? "yes" : "no");
}
return 0;
}后綴表達(dá)式
提棧還是繞不開(kāi)后綴表達(dá)式，我感覺(jué)我講的也不太好，看個(gè)b站視頻吧后綴表達(dá)式下面我用代碼實(shí)現(xiàn)一下
#include <iostream>
#include <stack>
using namespace std;
//表達(dá)式求值
const int MaxSize = 100;
void trans(char exp[], char postexp[])
{
stack<char> op;
int i = 0, j = 0;
//op.top = -1;
while (*exp != '\0')
{
switch (*exp)
{
case '('://左括號(hào)進(jìn)棧
op.push(*exp);
exp++;
break;
case ')'://將棧中“（”以前的運(yùn)算符依次刪除存入數(shù)組exp中，然后將“（”刪除
while (!op.empty() && op.top() != '(')
{
postexp[i++] = op.top();
op.pop();
}
op.pop();
exp++;
break;
case '+':
case '-':
while (!op.empty() && op.top() != '(')
{//將棧中優(yōu)先級(jí)大于等于‘+'或'-'的運(yùn)算符退棧并存放到postexp中
postexp[i++] = op.top();
op.pop();
}
op.push(*exp);
exp++;
break;
case '*':
case '/':
while (!op.empty() && (op.top() == '*' || op.top() == '/'))
{//將棧中的“*”或者是“/”運(yùn)算符依次出棧并存放到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] = '\0';
cout << "后綴表達(dá)式" << 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 != '\0')
{
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 << "除零錯(cuò)誤!" << endl;
exit(0);
}
break;
default://進(jìn)行最后的掃尾工作，將數(shù)字字符轉(zhuǎn)換成數(shù)值存放到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存放中綴表達(dá)式,postexp存放后綴表達(dá)式
printf("后綴表達(dá)式的值\n");
printf("%.2f\n", compvalue(postexp));
return 0;
}隊(duì)列
排隊(duì)？算了，用電腦來(lái)解釋吧，cpu就是一個(gè)隊(duì)列，一個(gè)執(zhí)行完再到下一個(gè)，和隊(duì)列一樣先進(jìn)先出也符合生活習(xí)慣，排在前面的優(yōu)先出列
隊(duì)列的專業(yè)術(shù)語(yǔ)和棧差不多類比吧
- 隊(duì)頭
- 隊(duì)尾
- 出隊(duì)
- 入隊(duì)
下面我們來(lái)實(shí)現(xiàn)一下隊(duì)列，還是用算法題來(lái)吧
排隊(duì)
一個(gè)學(xué)校里老師要將班上NN個(gè)同學(xué)排成一列，同學(xué)被編號(hào)為1\sim N1∼N，他采取如下的方法：
- 先將11號(hào)同學(xué)安排進(jìn)隊(duì)列，這時(shí)隊(duì)列中只有他一個(gè)人；
- 2−N號(hào)同學(xué)依次入列，編號(hào)為i的同學(xué)入列方式為：老師指定編號(hào)為i的同學(xué)站在編號(hào)為1\sim (i -1)1∼(i−1)中某位同學(xué)（即之前已經(jīng)入列的同學(xué)）的左邊或右邊；
- 從隊(duì)列中去掉M(M<N)M(M<N)個(gè)同學(xué)，其他同學(xué)位置順序不變。
在所有同學(xué)按照上述方法隊(duì)列排列完畢后，老師想知道從左到右所有同學(xué)的編號(hào)。
先分析：因?yàn)閚還是比較大的(n<=100000),又因?yàn)橐煌５牟迦牒蛣h除，所以我們可以用鏈表。讀入每一個(gè)同學(xué)時(shí)，都把他左邊和右邊的同學(xué)更新；刪除同學(xué)時(shí)，先把這個(gè)同學(xué)賦為0，再把他左邊的同學(xué)連上右邊的同學(xué)；最后找到排在最左邊的同學(xué)，挨個(gè)輸出。時(shí)間復(fù)雜度O(n)。
#include<cstdio>
#include<cstring>
int a[100010][3],n,m;
//a[i][2]表示學(xué)號(hào)為i的同學(xué)右邊同學(xué)的學(xué)號(hào)
//a[i][3]表示學(xué)號(hào)為i的同學(xué)左邊同學(xué)的學(xué)號(hào)
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)
//該同學(xué)還在
{
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;
}還有就是隊(duì)列是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表
棧是僅在表尾（棧頂）進(jìn)行插入和刪除操作的線性表
又想起了我入門(mén)時(shí)候的一首小詩(shī)——來(lái)自大話數(shù)據(jù)結(jié)構(gòu)
人生，就像是一個(gè)很大的棧演變。 出生時(shí)你赤條條地來(lái)到人世，慢慢地長(zhǎng)大，漸浙地變老，最終還得赤條條地離開(kāi)世間。
人生，又仿佛是一天一天小小的棧重現(xiàn)。童年父母每天抱你不斷地進(jìn)出家門(mén)，壯年你每天奔波于家與事業(yè)之間，老年你每天獨(dú)自蹣珊于養(yǎng)老院的門(mén)里屋前。
人生，更需要有進(jìn)棧出棧精神的體現(xiàn)。在哪里跌倒，就應(yīng)該在哪里爬起來(lái)。無(wú)論陷入何等困境，只要抬頭能仰望藍(lán)天，就有希望，不斷進(jìn)取，你就可以讓出頭之日重現(xiàn)。困難不會(huì)永遠(yuǎn)存在，強(qiáng)者才能勇往直前。
人生，其實(shí)就是一個(gè)大大的隊(duì)列演變。無(wú)知童年、快樂(lè)少年，稚傲青年，成熟中年，安逸晚年。
人生，又是一個(gè)又一個(gè)小小的隊(duì)列重現(xiàn)。春夏秋冬輪回年，早中晚夜循環(huán)天天。變化的是時(shí)間，不變的是你對(duì)未來(lái)執(zhí)著的信念。
人生，更需要有隊(duì)列精神的體現(xiàn)。南極到北極，不過(guò)是南緯90º到北緯90º的隊(duì)列，如果你中逢猶豫，臨時(shí)轉(zhuǎn)向，也許你就只能和企鵝相伴永遠(yuǎn)。可事實(shí)上，無(wú)論哪個(gè)方向，只要你堅(jiān)持到底，你都可以到達(dá)終點(diǎn)。
好了感慨完，該開(kāi)串了
串
串：由零個(gè)或多個(gè)字符串組成的有限序列，又稱字符串
我打算就分倆個(gè)方面講解
- 串的基本使用
- kmp算法
串的基本用法
串一般記為 s="absd"其中s是串的名字，c++中用雙引號(hào)擴(kuò)展起來(lái)的是串的內(nèi)容，雙引號(hào)不屬于串的內(nèi)容
還有幾個(gè)概念：
- 空格串：區(qū)別于空串，空格串是有內(nèi)容有長(zhǎng)度的，只是都是空格，但是空串沒(méi)有內(nèi)容
- 子串與主串：串中任意個(gè)數(shù)的連續(xù)字符組成的子序列稱為該串的子串，包含子串的串稱為主串
像Lover中的over就是主串與子串的關(guān)系
ASCII碼
在計(jì)算機(jī)中，所有的數(shù)據(jù)在存儲(chǔ)和運(yùn)算時(shí)都要使用二進(jìn)制數(shù)表示（因?yàn)橛?jì)算機(jī)用高電平和低電平分別表示1和0），例如，像a、b、c、d這樣的52個(gè)字母（包括大寫(xiě)）以及0、1等數(shù)字還有一些常用的符號(hào)（例如*、#、@等）在計(jì)算機(jī)中存儲(chǔ)時(shí)也要使用二進(jìn)制數(shù)來(lái)表示，而具體用哪些二進(jìn)制數(shù)字表示哪個(gè)符號(hào)，當(dāng)然每個(gè)人都可以約定自己的一套（這就叫編碼），而大家如果要想互相通信而不造成混亂，那么大家就必須使用相同的編碼規(guī)則，于是美國(guó)有關(guān)的標(biāo)準(zhǔn)化組織就出臺(tái)了ASCII編碼，統(tǒng)一規(guī)定了上述常用符號(hào)用哪些二進(jìn)制數(shù)來(lái)表示
在c++中char字符型變量，一個(gè)變量對(duì)應(yīng)一個(gè)ascll碼值
串的基本實(shí)現(xiàn)
實(shí)話實(shí)話，我感覺(jué)串的邏輯結(jié)構(gòu)和線性表的很類似，不同之處是串針對(duì)的是字符集，但是代碼實(shí)現(xiàn)還是有些不同之處，比如：查找
這就是一個(gè)串的查找，可以看到它自動(dòng)給我補(bǔ)齊的操作，這也與之后的kmp算法有關(guān)
現(xiàn)在我先來(lái)用簡(jiǎn)單的傻瓜式搜索實(shí)現(xiàn)一下所有代碼
//在c中許多是要單獨(dú)寫(xiě)的，但是c++引入了string，其中包含了許多函數(shù)就不用自己直接寫(xiě)了，為了學(xué)習(xí)我先用c寫(xiě)，之后講解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();//長(zhǎng)度
cout << "size = " << size << endl;
cout << "length = " << length << endl;
return 0;
}傻瓜模式匹配算法
int i = pos;
int j = 1;
while (i <= s[0] && j <= t[0])//當(dāng)i<s的長(zhǎng)度，且j<t的長(zhǎng)度，循環(huán)繼續(xù)
{
if (s[i] = t[j])
{
i++;
j++;//繼續(xù)
}
else//缺點(diǎn)：后退重新匹配
{
i = i - j + 2;//i回到上次匹配首位的下一位
j = 1;//回到首位
}
}
if (j > t[0])
return i - t[0];//不匹配
else
return 0;利用入門(mén)知識(shí)分析一下吧，最好的情況下，最好的結(jié)果是O（m），最壞的結(jié)果是O（n+m），取個(gè)平均是（n+m）/2，時(shí)間復(fù)雜度是O(n+m)
那么最壞的情況？就是每次不匹配成功都發(fā)生在串s，的最后一個(gè)字節(jié)上，這樣的話，時(shí)間復(fù)雜度就成了O（（n-m+1)*m）
KMP模式算法匹配
模式匹配的算法雖然簡(jiǎn)單但是實(shí)際上是非常糟糕的，實(shí)際上和算法中的動(dòng)態(tài)規(guī)劃有點(diǎn)像，動(dòng)態(tài)規(guī)劃就是減少了重復(fù)的計(jì)算，來(lái)?yè)Q取高效，這里的kmp也一樣，分析我們不難發(fā)現(xiàn)，模式匹配算法主要就是重復(fù)匹配太多了，kmp減少了重復(fù)的匹配來(lái)實(shí)現(xiàn)高效
正題：KMP算法是怎樣優(yōu)化這些步驟的。其實(shí)KMP的主要思想是：“空間換時(shí)間”，也和dp一樣
首先，為什么樸素的模式匹配這么慢呢？
你再回頭看一遍就會(huì)發(fā)現(xiàn)，哦，原來(lái)是回溯的步驟太多了。所以我們應(yīng)該盡量減少回溯的次數(shù)。
怎樣做呢？比如：goodgoole當(dāng)字符’d’與’g’不匹配，我們保持主串的指向不變，
主串依然指向’d’，而把子串進(jìn)行回溯，讓’d’與子串中’g’之前的字符再進(jìn)行比對(duì)。
如果字符匹配，則主串和子串字符同時(shí)右移。
上代碼吧，作圖能力實(shí)在不行，如果沒(méi)有看明白，還請(qǐng)?jiān)u論，我再講解
typedef struct
{
char data[MaxSize];
int length; //串長(zhǎng)
} SqString;
//SqString 是串的數(shù)據(jù)結(jié)構(gòu)
//typedef重命名結(jié)構(gòu)體變量，可以用SqString t定義一個(gè)結(jié)構(gòu)體。
void GetNext(SqString t,int next[]) //由模式串t求出next值
{
int j,k;
j=0;k=-1;
next[0]=-1;//第一個(gè)字符前無(wú)字符串，給值-1
while (j<t.length-1)
//因?yàn)閚ext數(shù)組中j最大為t.length-1,而每一步next數(shù)組賦值都是在j++之后
//所以最后一次經(jīng)過(guò)while循環(huán)時(shí)j為t.length-2
{
if (k==-1 || t.data[j]==t.data[k]) //k為-1或比較的字符相等時(shí)
{
j++;k++;
next[j]=k;
//對(duì)應(yīng)字符匹配情況下，s與t指向同步后移
//通過(guò)字符串"aaaaab"求next數(shù)組過(guò)程想一下這一步的意義
//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
}
else
{
k=next[k];
**//我們現(xiàn)在知道next[k]的值代表的是下標(biāo)為k的字符前面的字符串最長(zhǎng)相等前后綴的長(zhǎng)度
//也表示該處字符不匹配時(shí)應(yīng)該回溯到的字符的下標(biāo)
//這個(gè)值給k后又進(jìn)行while循環(huán)判斷，此時(shí)t.data[k]即指最長(zhǎng)相等前綴后一個(gè)字符**
//為什么要回退此處進(jìn)行比較，我們往下接著看。其實(shí)原理和上面介紹的KMP原理差不多
//printf("(2) k=%d\n",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后退，現(xiàn)在知道為什么這樣讓子串回退了吧
}
if (j>=t.length)
return(i-t.length); //返回匹配模式串的首字符下標(biāo)
else
return(-1); //返回不匹配標(biāo)志
}算了算了，這樣我都有點(diǎn)暈
看算法題目吧
kmp字符串匹配
#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;
}
其實(shí)我們也可以發(fā)現(xiàn)， KMP算法之所以快，不僅僅由于它的失配處理方案，更重要的是利用前綴后綴的特性，從不會(huì)反反復(fù)復(fù)地找，我們可以看到代碼里對(duì)于匹配只有一重循環(huán)，也就是說(shuō) KMP 算法具有一種“最優(yōu)歷史處理”的性質(zhì)，而這種性質(zhì)也是基于 KMP的核心思想的。
樹(shù)
終于擺脫線性表了，線性表是一對(duì)一，但是樹(shù)就不一樣了，一對(duì)多的性質(zhì)撲面而來(lái)，先看一下百度的說(shuō)法吧，
樹(shù)：它是由n(n≥1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。
就用這張圖來(lái)描述樹(shù)的特征：
- 當(dāng)n=0，就稱為空樹(shù)
- 有且只有一個(gè)稱為根的結(jié)點(diǎn)，這里為A
- 當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可以分為m(m>0)個(gè)互不相交的有限集，其中每個(gè)集合又是一棵樹(shù)，稱為子樹(shù)
舉個(gè)例子：
是以B為結(jié)點(diǎn)的子樹(shù)
下面我們來(lái)將結(jié)點(diǎn)分一下類：
- 樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)結(jié)構(gòu)及若干指向其子樹(shù)的分支
- 結(jié)點(diǎn)擁有的子樹(shù)稱為結(jié)點(diǎn)的度
- 度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)
- 度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)
看圖
結(jié)點(diǎn)的關(guān)系：
這塊有點(diǎn)像我們的家庭關(guān)系，比較好理解
像上圖A為B，C的雙親，B，C互為兄弟，對(duì)于#來(lái)說(shuō)，D，B，A，都是它的祖先，反之A的子孫有B，D，#
其他相關(guān)概念，特定情況才會(huì)用到
引入了深度，可以說(shuō)是有幾層就有多少深度.
無(wú)序樹(shù)：如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左到右都是沒(méi)有次序，都可以隨意互換，則稱為無(wú)序樹(shù)，反之為有序樹(shù)
樹(shù)的基本操作
雙親表示法
樹(shù)真的太像人了，人可能暫時(shí)沒(méi)有孩子但是一定有且只有一個(gè)父母，樹(shù)也一樣除了根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)，它不一定有孩子，但是一定有且只有一個(gè)雙親
/*
Project: Tree_parent(樹(shù)-雙親表示法)
Date: 2019/02/25
Author: Frank Yu
基本操作函數(shù)：
InitTree(Tree &T) 參數(shù)T，樹(shù)根節(jié)點(diǎn) 作用：初始化樹(shù)，先序遞歸創(chuàng)建
InsertNode(Tree &T, TElemType node) 插入樹(shù)的結(jié)點(diǎn) 參數(shù)：樹(shù)T,結(jié)點(diǎn)node 作用：在雙親數(shù)組中插入結(jié)點(diǎn)，增加樹(shù)的結(jié)點(diǎn)值
InsertParent(Tree &T, TElemType node1, TElemType node2)//插入雙親數(shù)組的雙親域 參數(shù)：樹(shù)T ，結(jié)點(diǎn)node1,結(jié)點(diǎn)node2
//作用：使雙親數(shù)組中,node2對(duì)應(yīng)的雙親域?yàn)閚ode1的下標(biāo)
GetIndegree(Tree &T, TElemType node) //得到某結(jié)點(diǎn)入度 參數(shù)：樹(shù)T，結(jié)點(diǎn)node 結(jié)點(diǎn)不存在返回-1
GetOutdegree(Tree &T, TElemType node) //得到某結(jié)點(diǎn)出度 參數(shù)：樹(shù)T，結(jié)點(diǎn)node 結(jié)點(diǎn)不存在返回-1
PreOrder(Tree T) 參數(shù)：樹(shù)T,根節(jié)點(diǎn)下標(biāo) 作用：先序遍歷樹(shù)
PostOrder(Tree T) 參數(shù)：樹(shù)T,根節(jié)點(diǎn)下標(biāo) 作用：后序遍歷樹(shù)
LevelOrder(Tree T)參數(shù)：樹(shù)T 作用：層序遍歷樹(shù)
功能實(shí)現(xiàn)函數(shù)：
CreateTree(Tree &T) 參數(shù)T，樹(shù)根節(jié)點(diǎn) 作用：創(chuàng)建樹(shù)，調(diào)用InsertNode,InsertParent
Traverse(Tree T) 參數(shù)T，樹(shù)根節(jié)點(diǎn) 作用：PreOrder InOrder PostOrder LevelOrder遍歷樹(shù)
*/
#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;
//樹(shù)的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
typedef struct TNode
{
TElemType data;//數(shù)據(jù)域
int parent; //雙親
}TNode;
//樹(shù)的數(shù)據(jù)結(jié)構(gòu)
typedef struct Tree
{
TNode parent[Max];
int NodeNum;
}Tree;
//********************************基本操作函數(shù)********************************//
//初始化樹(shù)函數(shù) 參數(shù)：樹(shù)T 作用：規(guī)定數(shù)據(jù)域?yàn)?，則為空，雙親為-1,則為空
void InitTree(Tree &T)
{
for (int i=0;i<Max;i++)
{
T.parent[i].data = '#';
T.parent[i].parent = -1;
}
T.NodeNum = 0;
}
//插入樹(shù)的結(jié)點(diǎn) 參數(shù)：樹(shù)T,結(jié)點(diǎn)node 作用：在雙親數(shù)組中插入結(jié)點(diǎn)，增加樹(shù)的結(jié)點(diǎn)值
bool InsertNode(Tree &T, TElemType node)
{
if (node != '#')
{
T.parent[T.NodeNum++].data = node;//插入到雙親數(shù)組中
return true;
}
return false;
}
//插入雙親數(shù)組的雙親域 參數(shù)：樹(shù)T ，結(jié)點(diǎn)node1,結(jié)點(diǎn)node2
//作用：使雙親數(shù)組中,node2對(duì)應(yīng)的雙親域?yàn)閚ode1的下標(biāo)
bool InsertParent(Tree &T, TElemType node1, TElemType node2)
{
int place1, place2;
place1 = -1;place2 = -1;
for (int i=0;i<T.NodeNum;i++)//查找兩點(diǎn)是否存在
{
if (node1 == T.parent[i].data)place1 = i;
if (node2 == T.parent[i].data)place2 = i;
}
if (place1 != -1 && place2 != -1)//兩點(diǎn)均存在
{
T.parent[place2].parent = place1;
return true;
}
return false;
}
//得到某結(jié)點(diǎn)入度 參數(shù)：樹(shù)T，結(jié)點(diǎn)node 結(jié)點(diǎn)不存在返回-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)//結(jié)點(diǎn)存在
{
if(T.parent[place].parent!=-1)return 1;//雙親只能有一個(gè)
else return 0; //根節(jié)點(diǎn)沒(méi)有雙親，即沒(méi)有入度
}
return -1;
}
//得到某結(jié)點(diǎn)出度 參數(shù)：樹(shù)T，結(jié)點(diǎn)node 結(jié)點(diǎn)不存在返回-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;
}
//先序遍歷 參數(shù)：樹(shù)T,根節(jié)點(diǎn)下標(biāo)
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);//按左右先序遍歷子樹(shù)
}
}
}
//后序遍歷 參數(shù)：樹(shù)T,根節(jié)點(diǎn)下標(biāo)
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);//按左右先序遍歷子樹(shù)
}
cout << T.parent[i].data << " ";
}
}
//層序遍歷 參數(shù)：樹(shù)T
void LevelOrder(Tree T)
{
queue<TNode> q;//借助隊(duì)列
if (T.NodeNum!=0)
{
TNode temp;//暫存要出隊(duì)的結(jié)點(diǎn)
q.push(T.parent[0]);//根結(jié)點(diǎn)入隊(duì)
while (!q.empty())//隊(duì)列非空
{
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)//當(dāng)前結(jié)點(diǎn)的父節(jié)點(diǎn)的數(shù)據(jù)域與彈出的相同
//因?yàn)閠emp沒(méi)有保存下標(biāo)，只能按這種方式比較，默認(rèn)結(jié)點(diǎn)名稱不同
q.push(T.parent[j]);//隊(duì)列先進(jìn)先出，先入左孩子
}
}
}
}
//**********************************功能實(shí)現(xiàn)函數(shù)*****************************//
//創(chuàng)建樹(shù)，調(diào)用InsertNode,InsertParent
void CreateTree(Tree &T)
{
int nodenum = 0;
int parent;
TElemType node,node1,node2;
printf("請(qǐng)輸入樹(shù)的結(jié)點(diǎn)個(gè)數(shù):");
cin >> nodenum;
parent = nodenum - 1;
printf("請(qǐng)輸入樹(shù)的結(jié)點(diǎn)名稱（空格隔開(kāi)）:");
while (nodenum--)
{
cin >> node;
InsertNode(T,node);
}
printf("請(qǐng)輸入樹(shù)的結(jié)點(diǎn)間的雙親關(guān)系（一對(duì)為一雙親關(guān)系，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("請(qǐng)輸入結(jié)點(diǎn)名稱:\n");
cin >> node;
indegree = GetIndegree(T, node);
if (-1 != indegree)
cout << "該結(jié)點(diǎn)入度為：" << indegree << endl;
else
cout << "結(jié)點(diǎn)不存在。" << endl;
}
//出度
void Outdegree(Tree &T)
{
TElemType node;
int outdegree;
printf("請(qǐng)輸入結(jié)點(diǎn)名稱:\n");
cin >> node;
outdegree = GetOutdegree(T, node);
if (-1 != outdegree)
cout << "該結(jié)點(diǎn)出度為：" << outdegree << endl;
else
cout << "結(jié)點(diǎn)不存在。" << endl;
}
//遍歷功能函數(shù) 調(diào)用PreOrder InOrder PostOrder LevelOrder
void Traverse(Tree T)
{
int choice;
while (1)
{
printf("********1.先序遍歷 2.后序遍歷*********\n");
printf("********3.層次遍歷 4.返回上一單元*********\n");
printf("請(qǐng)輸入菜單序號(hào)：\n");
scanf("%d", &choice);
if (4 == choice) break;
switch (choice)
{
case 1: {printf("樹(shù)先序遍歷序列:");PreOrder(T,0);printf("\n");}break;
case 2: {printf("樹(shù)后序遍歷序列:");PostOrder(T,0);printf("\n");}break;
case 3: {printf("樹(shù)層序遍歷序列:");LevelOrder(T);printf("\n");}break;
default:printf("輸入錯(cuò)誤?。。n");break;
}
}
}
//菜單
void menu()
{
printf("********1.創(chuàng)建 2.某點(diǎn)入度*********\n");
printf("********3.某點(diǎn)出度 4.遍歷*************\n");
printf("********5.退出\n");
}
//主函數(shù)
int main()
{
Tree T;
int choice = 0;
InitTree(T);
while (1)
{
menu();
printf("請(qǐng)輸入菜單序號(hào)：\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("輸入錯(cuò)誤?。?！\n");break;
}
}
return 0;
}
所用圖
孩子表示法
顧名思義，就是每個(gè)結(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一棵子樹(shù)的根結(jié)點(diǎn)，我們也把這種方法叫做多重鏈表表式法，有點(diǎn)像線性表中的鏈?zhǔn)奖硎痉?/p>
那么這樣的話，我這里就寫(xiě)偽代碼了
//指針域的個(gè)數(shù)就等于樹(shù)的度，其中樹(shù)的度又等于樹(shù)各個(gè)結(jié)點(diǎn)度的最大值
struct ChildNode
{
int data；
ChildNode*;
}
ChildNode *D;//d為最大結(jié)點(diǎn)
d.ChildNode;
不難看出這樣的話，如果各個(gè)樹(shù)度之間的差距不大，還可以，但是如果各個(gè)樹(shù)度之間的差距很大，那么很浪費(fèi)空間，原因是許多的結(jié)點(diǎn)域都是空的
孩子兄弟表示法
這個(gè)可以說(shuō)是學(xué)二叉樹(shù)的基礎(chǔ)，有的兄弟可能要說(shuō)了，為什么不是兄弟表示法？還要帶上我的孩子一起？
因?yàn)榭赡艽嬖谙旅孢@種情況，只有了兄弟，孩子沒(méi)有辦法往下延申了，那么如何孩子和兄弟一起開(kāi)呢？
是這樣的，任意一棵樹(shù)，它的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，記得不是堂兄弟昂，是親兄弟，下面我們
看圖
觀察后，我們可以發(fā)現(xiàn)每個(gè)結(jié)點(diǎn)最多有倆個(gè)孩子，也就是一個(gè)簡(jiǎn)單的二叉樹(shù)，這也可以說(shuō)是，孩子兄弟表示法最大的好處
struct Node
{
int data;
*firstchild,*ringtsib;
}
Node *Tree;
二叉樹(shù)
惡魔來(lái)了，有關(guān)二叉樹(shù)及其衍生的東西往往是樹(shù)中的難點(diǎn)，下面來(lái)個(gè)大家講個(gè)故事：還是以前的小苗，話說(shuō)我以前剛看上小苗時(shí)，幾乎沒(méi)有人知道，但是我對(duì)我的兄弟說(shuō)我看上了一個(gè)女孩，讓他猜，但是我每次只回答”對(duì)“或”錯(cuò)“，然后就相當(dāng)于降低了難度莫，身高，體重，魅力，頭發(fā)等等，都可以用一個(gè)人來(lái)比較，這樣的話又降低了難度，二叉樹(shù)也是一樣的，只不過(guò)它是通過(guò)比較大小來(lái)降低難度的，下面我們回歸正題
特點(diǎn)：
- 每個(gè)結(jié)點(diǎn)最多有倆棵子樹(shù)
- 左右子樹(shù)都是有順序的，不能任意顛倒
- 即使只有一棵子樹(shù)，也要區(qū)分它是左子樹(shù)還是右子樹(shù)
一般情況下，有以下幾種基本形態(tài)
空二叉樹(shù)，沒(méi)有辦法畫(huà)圖了
只有一個(gè)根結(jié)點(diǎn)
根結(jié)點(diǎn)只有左子樹(shù)
根結(jié)點(diǎn)只有右子樹(shù)
根結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)
再思考一下，如果有三個(gè)結(jié)點(diǎn)的二叉樹(shù)，又有幾種形態(tài)呢？
5種，怎么來(lái)的？先看圖
由于他必須是有序的所以要單個(gè)計(jì)算，左右分開(kāi)，加起來(lái)就是5種
下面來(lái)說(shuō)幾個(gè)特殊的二叉樹(shù)：
滿二叉樹(shù)：一個(gè)二叉樹(shù)，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹(shù)就是滿二叉樹(shù)。也就是說(shuō)，如果一個(gè)二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹(shù)。
完全二叉樹(shù)：完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹(shù)。 要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。
斜樹(shù)：有點(diǎn)像線性表，這個(gè)斜可以不分左右，所以更像線性表了
如何判斷完全二叉樹(shù)，下面是它的特征：
- 葉子結(jié)點(diǎn)只能出現(xiàn)在最下倆層、
- 最下層的葉子一定集中在左部的連續(xù)位置
- 倒數(shù)倆層，若有葉子結(jié)點(diǎn)，一定都在右部連續(xù)位置
- 如果結(jié)點(diǎn)度為一，則該結(jié)點(diǎn)只有左孩子
- 同樣結(jié)點(diǎn)數(shù)的二叉樹(shù)，完全二叉樹(shù)的深度最小
下面我們來(lái)看一下，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)吧，也分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)
順序存儲(chǔ)
由于樹(shù)是一對(duì)多的關(guān)系，順序存儲(chǔ)實(shí)現(xiàn)有點(diǎn)困難，但是二叉樹(shù)是一種特殊的樹(shù)，由于它的特殊性，順序存儲(chǔ)可以實(shí)現(xiàn)。
順序結(jié)構(gòu)存儲(chǔ)就是使用數(shù)組來(lái)存儲(chǔ)，一般使用數(shù)組只適合表示完全二叉樹(shù)，因?yàn)椴皇峭耆鏄?shù)會(huì)有空間的浪費(fèi)。而現(xiàn)實(shí)中使用中只有堆才會(huì)使用數(shù)組來(lái)存儲(chǔ)。二叉樹(shù)順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹(shù)。
鏈表存儲(chǔ)
由于二叉樹(shù)每個(gè)結(jié)點(diǎn)最多有倆個(gè)孩子，所以給它設(shè)計(jì)一個(gè)數(shù)據(jù)域和倆個(gè)指針域，組成二叉鏈表
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
}
BinaryTreeNode *tree;
遍歷二叉樹(shù)
所謂遍歷(Traversal)是指沿著某條搜索路線，依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn)題。從而引出了次序問(wèn)題，像碼神剛剛結(jié)束的高考志愿問(wèn)題，哪個(gè)城市，哪個(gè)學(xué)校，哪個(gè)專業(yè)，或者那個(gè)她，由于選擇不同，所以最后的遍歷次序也截然不同。
方法：
- 前序遍歷——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前。
從根開(kāi)始先左后右 - 中序遍歷——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之中。
中序遍歷根結(jié)點(diǎn)的左子樹(shù)，然后是訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù) - 后序遍歷——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后。
從左到右先子葉后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹(shù)，最后是根結(jié)點(diǎn) - 層序遍歷——設(shè)二叉樹(shù)的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹(shù)的根節(jié)點(diǎn)出發(fā)，首先訪問(wèn)第一層的樹(shù)根節(jié)點(diǎn)，然后從左到右訪問(wèn)第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問(wèn)樹(shù)的結(jié)點(diǎn)的過(guò)程就是層序遍歷。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
typedef BTNode* QDataType;
// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
// 隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
BTNode* CreateBTNode(BTDataType x);
// 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù)
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉樹(shù)銷毀
void BinaryTreeDestory(BTNode** root);
// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root);
// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹(shù)查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹(shù)前序遍歷
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹(shù)中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹(shù)后序遍歷
void BinaryTreePostOrder(BTNode* root);
// 初始化隊(duì)列
void QueueInit(Queue* q);
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QDataType data);
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q);
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q);
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q);
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q);
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q);
// 銷毀隊(duì)列
void QueueDestroy(Queue* q);
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
// 判斷二叉樹(shù)是否是完全二叉樹(shù)
int BinaryTreeComplete(BTNode* root);// 初始化隊(duì)列
void QueueInit(Queue* q)
{
assert(q);
q->_front = q->_rear = NULL;
}
// 隊(duì)尾入隊(duì)列
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;
}
}
// 隊(duì)頭出隊(duì)列
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;
}
}
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_front->_data;
}
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->_rear->_data;
}
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q)
{
assert(q);
int size = 0;
QNode* cur = q->_front;
while (cur)
{
++size;
cur = cur->_next;
}
return size;
}
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->_front == NULL ? 1 : 0;
}
// 銷毀隊(duì)列
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;
}
// 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù)
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;
}
// 二叉樹(shù)銷毀
void BinaryTreeDestory(BTNode** root)
{
if (*root != NULL)
{
if ((*root)->_left) // 有左孩子
BinaryTreeDestory(&(*root)->_left); // 銷毀左孩子子樹(shù)
if ((*root)->_right) // 有右孩子
BinaryTreeDestory(&(*root)->_right); // 銷毀右孩子子樹(shù)
free(*root); // 釋放根結(jié)點(diǎn)
*root = NULL; // 空指針賦NULL
}
}
// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
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);
}
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)
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);
}
// 二叉樹(shù)查找值為x的節(jié)點(diǎn)
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;
}
// 二叉樹(shù)前序遍歷
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
//printf("NULL ");
return;
}
printf("%c ", root->_data);
BinaryTreePrevOrder(root->_left);
BinaryTreePrevOrder(root->_right);
}
// 二叉樹(shù)中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
//printf("NULL ");
return;
}
BinaryTreeInOrder(root->_left);
printf("%c ", root->_data);
BinaryTreeInOrder(root->_right);
}
// 二叉樹(shù)后序遍歷
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);
}
}
}
// 判斷二叉樹(shù)是否是完全二叉樹(shù)
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;
}還有最后一個(gè)樹(shù)——線索二叉樹(shù)
它的出現(xiàn)還是為了簡(jiǎn)約成本，實(shí)際上想一下算法和數(shù)據(jù)結(jié)構(gòu)存在就是為了節(jié)約時(shí)間或空間，這個(gè)是節(jié)約不用的空指針域，
空的左孩子指針指向該結(jié)點(diǎn)的前驅(qū),空的右孩子指針指向該結(jié)點(diǎn)的后繼。這種附加的指針值稱為線索，帶線索的二叉樹(shù)稱為線索二叉樹(shù)。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100
typedef char ElemType;
typedef enum
{
Link,/*指向孩子結(jié)點(diǎn)*/Thread/*指向前驅(qū)或后繼*/
} 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[]);//創(chuàng)建搜索二叉樹(shù)
void InThreading(BitThrTree p);//中序線索化二叉樹(shù)
int InOrderThreading(BitThrTree *Thrt,BitThrTree T);//通過(guò)中序遍歷二叉樹(shù)T，使T中序線索化。Thrt是指向頭結(jié)點(diǎn)的指針
int InOrderTraverse(BitThrTree T,int (*visit)(BitThrTree e));//中序遍歷線索二叉樹(shù)
int Print(BitThrTree T);//打印二叉樹(shù)的結(jié)點(diǎn)和線索標(biāo)志
BitThrNode* FindPoint(BitThrTree T,ElemType e);//在線索二叉樹(shù)中查找結(jié)點(diǎn)為e的指針
BitThrNode* InOrderPre(BitThrNode *p);//中序前驅(qū)
BitThrNode* InOrderPost(BitThrNode *p);//中序后繼
void DestroyBitTree(BitThrTree *T);//銷毀二叉樹(shù)
#include "LinkBiTree.h"
void CreateBitTree2(BitThrTree *T,char str[])//創(chuàng)建搜索二叉樹(shù)
{
char ch;
BitThrTree stack[MAXSIZE];
int top = -1;
int flag,k;
BitThrNode *p;
*T = NULL,k = 0;
ch = str[k];
while(ch != '\0')
{
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)//中序線索化二叉樹(shù)
{
if(p)//左子樹(shù)線索化
{
InThreading(p->lchild);
if(!p->lchild)//前驅(qū)線索化
{
p->ltag = Thread;
p->lchild = pre;
}
if(!pre->rchild)//后繼線索化
{
pre->rtag = Thread;
pre->rchild = p;
}
pre = p;
InThreading(p->rchild);//右子樹(shù)線索化
}
}
int InOrderThreading(BitThrTree *Thrt,BitThrTree T)//通過(guò)中序遍歷二叉樹(shù)T，使T中序線索化。Thrt是指向頭結(jié)點(diǎn)的指針
{
if(!(*Thrt = (BitThrTree)malloc(sizeof(BitThrNode))))
{
exit(-1);//為頭結(jié)點(diǎn)分配單元
}
(*Thrt)->ltag = Link;//修改前驅(qū)線索標(biāo)志
(*Thrt)->rtag = Thread;//修改后繼線索標(biāo)志
(*Thrt)->rchild = *Thrt;//將頭結(jié)點(diǎn)的rchild指針指向自己
if(!T)//如果二叉樹(shù)為空，則將lchild指針指向自己
{
(*Thrt)->lchild = *Thrt;
}
else
{
(*Thrt)->lchild = T;//將頭結(jié)點(diǎn)的左指針指向根結(jié)點(diǎn)
pre = *Thrt;//將pre指向已經(jīng)線索化的結(jié)點(diǎn)
InThreading(T);//中序遍歷進(jìn)行中序線索化
/*將最后一個(gè)結(jié)點(diǎn)線索化*/
pre->rchild = *Thrt;//將最后一個(gè)結(jié)點(diǎn)的右指針指向頭結(jié)點(diǎn)
pre->rtag = Thread;//修改最后一個(gè)結(jié)點(diǎn)的rtag標(biāo)志域
(*Thrt)->rchild = pre;//將頭結(jié)點(diǎn)的rchild指針指向最后一個(gè)結(jié)點(diǎn)
}
return 1;
}
int InOrderTraverse(BitThrTree T,int (*visit)(BitThrTree e))//中序遍歷線索二叉樹(shù)
{
BitThrTree p;
p = T->lchild ;//p指向根結(jié)點(diǎn)
while(p != T)//空樹(shù)或遍歷結(jié)束時(shí)，p == T
{
while(p->ltag == Link)
{
p = p->lchild ;
}
if(!visit(p))//打印
{
return 0;
}
while(p->rtag == Thread && p->rchild != T)//訪問(wèn)后繼結(jié)點(diǎn)
{
p = p->rchild ;
visit(p);
}
p = p->rchild ;
}
return 1;
}
int Print(BitThrTree T)//打印二叉樹(shù)的結(jié)點(diǎn)和線索標(biāo)志
{
static int k = 1;
printf("%2d\t%s\t %2c\t %s\t\n",k++,T->ltag == 0 ? "Link":"Thread",T->data ,T->rtag == 1 ? "Thread":"Link");
return 1;
}
BitThrNode* FindPoint(BitThrTree T,ElemType e)//在線索二叉樹(shù)中查找結(jié)點(diǎn)為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)//中序前驅(qū)
{
if(p->ltag == Thread)//如果p的標(biāo)志域ltag為線索，則p的左子樹(shù)結(jié)點(diǎn)為前驅(qū)
{
return p->lchild ;
}
else
{
pre = p->lchild ;//查找p的左孩子的最右下端結(jié)點(diǎn)
while(pre->rtag == Link)//右子樹(shù)非空時(shí)，沿右鏈往下查找
{
pre = pre->rchild ;
}
return pre;//pre就是最右下端結(jié)點(diǎn)
}
}
BitThrNode* InOrderPost(BitThrNode *p)//中序后繼
{
if(p->rtag == Thread)//如果p的標(biāo)志域rtag為線索，則p的右子樹(shù)結(jié)點(diǎn)為后驅(qū)
{
return p->rchild ;
}
else
{
pre = p->rchild ;//查找p的右孩子的最左下端結(jié)點(diǎn)
while(pre->ltag == Link)//左子樹(shù)非空時(shí)，沿左鏈往下查找
{
pre = pre->lchild ;
}
return pre;//pre就是最左下端結(jié)點(diǎn)
}
}
void DestroyBitTree(BitThrTree *T)//銷毀二叉樹(shù)
{
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("線索二叉樹(shù)的輸出序列：\n");
InOrderThreading(&Thrt,T);
printf("序列 前驅(qū)標(biāo)志 結(jié)點(diǎn) 后繼標(biāo)志\n");
InOrderTraverse(Thrt,Print);
p = FindPoint(Thrt,'D');
pre = InOrderPre(p);
printf("元素D的中序直接前驅(qū)元素是：%c\n",pre->data);
post = InOrderPost(p);
printf("元素D的中序直接后驅(qū)元素是：%c\n",post->data);
p = FindPoint(Thrt,'E');
pre = InOrderPre(p);
printf("元素E的中序直接前驅(qū)元素是：%c\n",pre->data);
post = InOrderPost(p);
printf("元素E的中序直接后驅(qū)元素是：%c\n",post->data);
DestroyBitTree(&Thrt);
return 0;
} 哈夫曼樹(shù)
到這數(shù)據(jù)結(jié)構(gòu)算過(guò)去一半了，我們先來(lái)總結(jié)一下
圖
終于樹(shù)結(jié)束了，累壞我了，開(kāi)始圖
如果說(shuō)樹(shù)是一對(duì)多的話，那么圖就是多對(duì)多。
都見(jiàn)過(guò)地圖吧，像陜西就和山西連在了一起，還和內(nèi)蒙古等等連，典型的多對(duì)多
如果說(shuō)線性表和樹(shù)的專業(yè)術(shù)語(yǔ)比較繁瑣的話，那么圖可能顛覆你的三觀，——還有這么多的概念？介于圖的概念比較多，我們先來(lái)放概念，再講解
圖按照有無(wú)方向分為有向圖和無(wú)向圖。有向圖由頂點(diǎn)和弧構(gòu)成，無(wú)向圖由頂點(diǎn)和邊檢成?；∮谢∥埠突☆^之分。
圖按照邊或須的多少分為稀疏圖和稠密圖。如果任意兩個(gè)頂點(diǎn)之間都存在邊叫完全圖有向的叫有向完全圖。若無(wú)重復(fù)的邊或頂點(diǎn)到自身的邊則叫簡(jiǎn)單圖。
圖中頂點(diǎn)之間有鄰接點(diǎn)、依附的概念。無(wú)向圖頂點(diǎn)的邊數(shù)叫做度，有向圖頂點(diǎn)分為入度和出度。
圖上的邊或弧上帶權(quán)則稱為網(wǎng)。
圖中頂點(diǎn)間存在路徑，兩頂點(diǎn)存在路徑則說(shuō)明是連通的，如果路徑最終回到起始點(diǎn)則稱為環(huán)，當(dāng)中不重復(fù)叫簡(jiǎn)單路徑。若任意兩頂點(diǎn)都是連通的，則圖就是連通圖，有向則稱強(qiáng)連通圖。圖中有子圖，若子圖極大連通則就是連通分量，有向的則稱強(qiáng)連通分量。
無(wú)向圖中連通且n個(gè)頂點(diǎn)n-1條邊叫生成樹(shù)。有向圖中一頂點(diǎn)入度為0其余頂點(diǎn)入度為1的叫有向樹(shù)。一個(gè)有向圖由若干棵有向樹(shù)構(gòu)成生成森林。
概念很多，一一刨析
頂點(diǎn)
像樹(shù)中的結(jié)點(diǎn)，聰明的彥祖一下就懂了，就是圖中的數(shù)據(jù)元素嘛，但是有不同之處，線性表中有空表，樹(shù)中有空樹(shù)，，但是可沒(méi)有空?qǐng)D這一說(shuō)法，why？舉個(gè)例子：像皇帝的新衣一樣，你總不能拿一張紙給別人說(shuō)只有聰明的人才能看到吧？還有就是在線性表中有線性關(guān)系，在樹(shù)中有層的關(guān)系，那么在圖中呢？在圖中都有關(guān)系，一般來(lái)說(shuō)我們將任意倆個(gè)頂點(diǎn)的關(guān)系用術(shù)語(yǔ)邊來(lái)表示，邊的集合可以為空
有向圖，無(wú)向圖
簡(jiǎn)單的來(lái)看就是圖上沒(méi)有箭頭就為無(wú)向圖，反之有箭頭為有向圖。
如果非要我解釋的話，容我先引出無(wú)向邊和有向邊的概念
無(wú)向邊：反之就是這條邊無(wú)箭頭，如果是A——D，用（A，D）來(lái)表示
有向邊：簡(jiǎn)單來(lái)說(shuō)就是這條邊有箭頭，還是A->D，但是要用<A,D>來(lái)表示，注意：不能用<D,A>表示，其中，這條有向邊稱為弧，A是弧尾，D是弧頭也就是說(shuō)箭頭指向的為弧頭
那么有向圖和無(wú)向圖就簡(jiǎn)單了，如果一個(gè)圖都由有向邊組成，則稱為有向圖，反之為無(wú)向圖
下面再引出倆個(gè)概念：完全有向圖，完全無(wú)向圖，
完全有向圖：
在有向圖中如果任意倆個(gè)頂點(diǎn)都存在方向相反的倆條弧，為完全有向圖
完全無(wú)向圖：
在無(wú)向圖中任意倆個(gè)頂點(diǎn)都存在邊相連，則稱為完全無(wú)向圖
還有倆個(gè)計(jì)算邊數(shù)的公式為：n*(n-1)/2 and n*(n-1)，猜出來(lái)了吧，第一個(gè)是計(jì)算完全無(wú)向圖的，第二個(gè)是計(jì)算完全有向圖的
下面我們看倆個(gè)圖，自己判斷一下：
還有個(gè)稠密圖和稀疏圖，都是相對(duì)而言的，就像有錢(qián)一樣，如果我和乞丐比的話，我比較有錢(qián)，但是如果我和馬云來(lái)比的話，可能都沒(méi)有辦法比較。
頂點(diǎn)和邊
下面我們把頂點(diǎn)和邊串起來(lái)講一下，他們之間也是有聯(lián)系的
對(duì)于無(wú)向圖來(lái)說(shuō)，當(dāng)倆個(gè)頂點(diǎn)通過(guò)一條邊相連時(shí)，稱為頂點(diǎn)相關(guān)聯(lián)，頂點(diǎn)度是和另一個(gè)頂點(diǎn)相關(guān)聯(lián)邊的條數(shù)，頂點(diǎn)可稱為互為鄰結(jié)點(diǎn)
對(duì)于有向圖來(lái)說(shuō)，如果A->D稱為頂點(diǎn)A鄰接到頂點(diǎn)D，以A為頭的弧為入度，以D為尾的為出度
再來(lái)說(shuō)路徑，路徑的長(zhǎng)度為路徑的邊或弧的數(shù)目，其中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)，序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑為簡(jiǎn)單路徑，除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，又稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)
連通圖
圖中從一個(gè)頂點(diǎn)到達(dá)另一頂點(diǎn)，若存在至少一條路徑，則稱這兩個(gè)頂點(diǎn)是連通著的。例如圖 1 中，雖然 V1 和 V3 沒(méi)有直接關(guān)聯(lián)，但從 V1 到 V3 存在兩條路徑，分別是 V1-V2-V3 和 V1-V4-V3，因此稱 V1 和 V3 之間是連通的。
無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間都能夠連通，則稱此無(wú)向圖為連通圖。例如，圖 2 中的無(wú)向圖就是一個(gè)連通圖，因?yàn)榇藞D中任意兩頂點(diǎn)之間都是連通的。若無(wú)向圖不是連通圖，但圖中存儲(chǔ)某個(gè)子圖符合連通圖的性質(zhì)，則稱該子圖為連通分量。
強(qiáng)連通圖
有向圖中，若任意兩個(gè)頂點(diǎn) Vi 和 Vj，滿足從 Vi 到 Vj 以及從 Vj 到 Vi 都連通，也就是都含有至少一條通路，則稱此有向圖為強(qiáng)連通圖。如圖 4 所示就是一個(gè)強(qiáng)連通圖。
與此同時(shí)，若有向圖本身不是強(qiáng)連通圖，但其包含的最大連通子圖具有強(qiáng)連通圖的性質(zhì)，則稱該子圖為強(qiáng)連通分量。
剩下的就是圖有關(guān)的算法題了，用例題來(lái)說(shuō)吧
- 圖的遍歷
給出N個(gè)點(diǎn)，M條邊的有向圖，對(duì)于每個(gè)點(diǎn)v，求A(v)表示從點(diǎn)v出發(fā)，能到達(dá)的編號(hào)最大的點(diǎn)。
按題目來(lái)每次考慮每個(gè)點(diǎn)可以到達(dá)點(diǎn)編號(hào)最大的點(diǎn)，不如考慮較大的點(diǎn)可以反向到達(dá)哪些點(diǎn)循環(huán)從N到1，則每個(gè)點(diǎn)i能訪問(wèn)到的結(jié)點(diǎn)的A值都是i
每個(gè)點(diǎn)訪問(wèn)一次，這個(gè)A值就是最優(yōu)的，因?yàn)橹笕绻僭L問(wèn)到這個(gè)結(jié)點(diǎn)那么答案肯定沒(méi)當(dāng)前大了
#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; //訪問(wèn)過(guò)
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;
}
- 鄰接矩陣
給定一個(gè)整數(shù)矩陣
#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("%d\n",anss);
return 0;
}
來(lái)自：矩陣
再來(lái)一個(gè)深搜結(jié)束吧
- 深度優(yōu)先遍歷
給出N個(gè)點(diǎn)，M條邊的有向圖，對(duì)于每個(gè)點(diǎn)v，求A(v)表示從點(diǎn)v出發(fā)，能到達(dá)的編號(hào)最大的點(diǎn)
比較簡(jiǎn)單：反向建邊 + dfs
按題目來(lái)每次考慮每個(gè)點(diǎn)可以到達(dá)點(diǎn)編號(hào)最大的點(diǎn)，不如考慮較大的點(diǎn)可以反向到達(dá)哪些點(diǎn)循環(huán)從N到1，則每個(gè)點(diǎn)i能訪問(wèn)到的結(jié)點(diǎn)的A值都是i每個(gè)點(diǎn)訪問(wèn)一次，這個(gè)A值就是最優(yōu)的，因?yàn)橹笕绻僭L問(wèn)到這個(gè)結(jié)點(diǎn)那么答案肯定沒(méi)當(dāng)前大了
#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; //訪問(wèn)過(guò)
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;
}
深搜有了，不上廣搜有點(diǎn)過(guò)意不去，算了再來(lái)個(gè)廣搜
- 廣搜
有一個(gè) n×m 的棋盤(pán)，在某個(gè)點(diǎn) (x,y) 上有一個(gè)馬，要求你計(jì)算出馬到達(dá)棋盤(pán)上任意一個(gè)點(diǎn)最少要走幾步。
#include<iostream>//P1443
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>//運(yùn)用了隊(duì)列
#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個(gè)方向
queue<pair<int,int> > q;
int f[500][500];//存步數(shù)
bool vis[500][500];//走沒(méi)走過(guò)
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();//取隊(duì)首并出隊(duì)
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;//出界或走過(guò)就不走
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");}//注意場(chǎng)寬?。?
return 0;
}
- 最短路徑
實(shí)際上對(duì)于最短路徑，讓我看的話，它和深搜，廣搜差不多
主要是這倆個(gè)大佬發(fā)明的東西
- 迪杰斯特拉算法
- 弗洛伊德算法
下面就按順序來(lái)看一下
Dijkstra算法采用的是一種貪心的策略，聲明一個(gè)數(shù)組dis來(lái)保存源點(diǎn)到各個(gè)頂點(diǎn)的最短距離和一個(gè)保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合：T，初始時(shí)，原點(diǎn) s 的路徑權(quán)重被賦為 0 （dis[s] = 0）。若對(duì)于頂點(diǎn) s 存在能直接到達(dá)的邊（s,m），則把dis[m]設(shè)為w（s, m）,同時(shí)把所有其他（s不能直接到達(dá)的）頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大。初始時(shí)，集合T只有頂點(diǎn)s。然后，從dis數(shù)組選擇最小值，則該值就是源點(diǎn)s到該值對(duì)應(yīng)的頂點(diǎn)的最短路徑，并且把該點(diǎn)加入到T中，OK，此時(shí)完成一個(gè)頂點(diǎn)，然后，我們需要看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)并且看看通過(guò)該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長(zhǎng)度是否比源點(diǎn)直接到達(dá)短，如果是，那么就替換這些頂點(diǎn)在dis中的值。最后，又從dis中找出最小值，重復(fù)上述動(dòng)作，直到T中包含了圖的所有頂點(diǎn)。
這個(gè)總體上是一個(gè)：廣度優(yōu)先搜索解決賦權(quán)有向圖或者無(wú)向圖的單源最短路徑問(wèn)題，算法最終得到一個(gè)最短路徑樹(shù)
#pragma once
#include<iostream>
#include<string>
using namespace std;
//鄰接矩陣保存
//記錄起點(diǎn)到每個(gè)頂點(diǎn)的最短路徑的信息
struct Dis {
string path;
int value;
bool visit;
Dis() {
visit = false;
value = 0;
path = "";
}
};
class Graph_DG {
private:
int vexnum; //圖的頂點(diǎn)個(gè)數(shù)
int edge; //圖的邊數(shù)
int **arc; //鄰接矩陣
Dis * dis; //記錄各個(gè)頂點(diǎn)最短路徑的信息
public:
//構(gòu)造函數(shù)
Graph_DG(int vexnum, int edge);
//析構(gòu)函數(shù)
~Graph_DG();
// 判斷我們每次輸入的的邊的信息是否合法
//頂點(diǎn)從1開(kāi)始編號(hào)
bool check_edge_value(int start, int end, int weight);
//創(chuàng)建圖
void createGraph();
//打印鄰接矩陣
void print();
//求最短路徑
void Dijkstra(int begin);
//打印最短路徑
void print_path(int);
};#include"Dijkstra.h"
//構(gòu)造函數(shù)
Graph_DG::Graph_DG(int vexnum, int edge) {
//初始化頂點(diǎn)數(shù)和邊數(shù)
this->vexnum = vexnum;
this->edge = edge;
//為鄰接矩陣開(kāi)辟空間和賦初值
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++) {
//鄰接矩陣初始化為無(wú)窮大
arc[i][k] = INT_MAX;
}
}
}
//析構(gòu)函數(shù)
Graph_DG::~Graph_DG() {
delete[] dis;
for (int i = 0; i < this->vexnum; i++) {
delete this->arc[i];
}
delete arc;
}
// 判斷我們每次輸入的的邊的信息是否合法
//頂點(diǎn)從1開(kāi)始編號(hào)
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 << "請(qǐng)輸入每條邊的起點(diǎn)和終點(diǎn)（頂點(diǎn)編號(hào)從1開(kāi)始）以及其權(quán)重" << 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 << "輸入的邊的信息不合法，請(qǐng)重新輸入" << endl;
cin >> start >> end >> weight;
}
//對(duì)鄰接矩陣對(duì)應(yīng)上的點(diǎn)賦值
arc[start - 1][end - 1] = weight;
//無(wú)向圖添加上這行代碼
//arc[end - 1][start - 1] = weight;
++count;
}
}
void Graph_DG::print() {
cout << "圖的鄰接矩陣為：" << endl;
int count_row = 0; //打印行的標(biāo)簽
int count_col = 0; //打印列的標(biāo)簽
//開(kāi)始打印
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數(shù)組
int i;
for (i = 0; i < this->vexnum; i++) {
//設(shè)置當(dāng)前的路徑
dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
dis[i].value = arc[begin - 1][i];
}
//設(shè)置起點(diǎn)的到起點(diǎn)的路徑為0
dis[begin - 1].value = 0;
dis[begin - 1].visit = true;
int count = 1;
//計(jì)算剩余的頂點(diǎn)的最短路徑（剩余this->vexnum-1個(gè)頂點(diǎn)）
while (count != this->vexnum) {
//temp用于保存當(dāng)前dis數(shù)組中最小的那個(gè)下標(biāo)
//min記錄的當(dāng)前的最小值
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對(duì)應(yīng)的頂點(diǎn)加入到已經(jīng)找到的最短路徑的集合中
dis[temp].visit = true;
++count;
for (i = 0; i < this->vexnum; i++) {
//注意這里的條件arc[temp][i]!=INT_MAX必須加，不然會(huì)出現(xiàn)溢出，從而造成程序異常
if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
//如果新得到的邊可以影響其他為訪問(wèn)的頂點(diǎn)，那就就更新它的最短路徑和長(zhǎng)度
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<<"為起點(diǎn)的圖的最短路徑為：" << 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 << "是無(wú)最短路徑的" << endl;
}
}
}#include"Dijkstra.h"
//檢驗(yàn)輸入邊數(shù)和頂點(diǎn)數(shù)的值是否有效，可以自己推算為啥：
//頂點(diǎn)數(shù)和邊數(shù)的關(guān)系是：((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 << "輸入圖的頂點(diǎn)個(gè)數(shù)和邊的條數(shù)：" << endl;
cin >> vexnum >> edge;
while (!check(vexnum, edge)) {
cout << "輸入的數(shù)值不合法，請(qǐng)重新輸入" << endl;
cin >> vexnum >> edge;
}
Graph_DG graph(vexnum, edge);
graph.createGraph();
graph.print();
graph.Dijkstra(1);
graph.print_path(1);
system("pause");
return 0;
}弗洛伊德算法，我就使用偽代碼來(lái)寫(xiě)了，
//總體上是一個(gè)二重循環(huán)加上一個(gè)三重循環(huán)，主要運(yùn)用于所有頂點(diǎn)到所有頂點(diǎn)的最短路徑問(wèn)題
void ShortestPath FLOYD(MGraph G, PathMatrix &p[], DistanceMatrix &D){
//用Floyd算法求有向網(wǎng)中各對(duì)頂點(diǎn)v和w之間的最短路徑P[v][w]及其帶權(quán)長(zhǎng)
//度D[v][w].若P[v][w][u]為T(mén)RUE,則u是從v到w當(dāng)前求得最短路徑上的頂點(diǎn)。
for(v = 0; v < G.vexnum; ++v) //各對(duì)結(jié)點(diǎn)之間初始已知路徑及距離
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經(jīng)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
圖用網(wǎng)上十分流行的一句話來(lái)結(jié)尾，
世界上最遙遠(yuǎn)的距離是我找不到與你的最短路徑 ， 哭了
附：如果你還在糾結(jié)到底哪門(mén)語(yǔ)言作為主語(yǔ)言的話不妨來(lái)看看（入門(mén)時(shí)刻）
一、為什么要學(xué)主流語(yǔ)言？
1.古老
實(shí)際上由于我的年紀(jì)也比較小，所以在選擇語(yǔ)言時(shí)肯定會(huì)選擇大方向的語(yǔ)言，不能像前幾年的VB一樣，像我小學(xué)時(shí)候的語(yǔ)言，如果現(xiàn)在學(xué)他的話，那么你真的要吃土了
2.超前
上面的VB是比較古老的語(yǔ)言了，還有一種就是比較超前的語(yǔ)言，像近幾年的號(hào)稱取代c++的高性能語(yǔ)言，go，rust，但是我不太認(rèn)可，因?yàn)榇髲S的架構(gòu)不可能直接更換語(yǔ)言，小廠又會(huì)選擇主流語(yǔ)言，以便于獲取更廉價(jià)的勞動(dòng)力，所以說(shuō)我也不建議用超前的語(yǔ)言來(lái)進(jìn)行入門(mén)
3.過(guò)于簡(jiǎn)單的
這時(shí)就要請(qǐng)出我們的python ，php，這類語(yǔ)言一般很簡(jiǎn)單的可以入門(mén)，也可以快速的開(kāi)發(fā)出一個(gè)比較實(shí)用的應(yīng)用，所以受到廣大初學(xué)者和科研人員的追捧，但是由于入門(mén)簡(jiǎn)單加上深入困難，所以可替代性高，可能這時(shí)有的同學(xué)就要說(shuō)了那我簡(jiǎn)單入門(mén)后再轉(zhuǎn)其他的語(yǔ)言不好嗎？ 兄弟，簡(jiǎn)單語(yǔ)言學(xué)過(guò)了以后你還會(huì)想難的嗎？
總結(jié)
上面主要說(shuō)了3點(diǎn)，當(dāng)然還有，但是我就不在啰嗦了，所以說(shuō)大家如果初學(xué)編程的話最好學(xué)你目前看來(lái)，2-4年行情還是不錯(cuò)的語(yǔ)言
我大致想到以下幾個(gè)
- java
- c/c++
建議這倆個(gè)中挑一個(gè)主要學(xué)習(xí)，深度學(xué)習(xí)
java
優(yōu)點(diǎn)：由于Java面向移動(dòng)端兼容的性能真的太好了，這也就造就了，java崗位的井噴式的增長(zhǎng)
平臺(tái)： 軟件/應(yīng)用程序，Web和移動(dòng)開(kāi)發(fā)。
難度：和c++差不多，但是沒(méi)有c++難，因?yàn)镴ava也是c++開(kāi)發(fā)出來(lái)的，其中移除了c++指針，總體還是難
工資：平均工資高于大部分的語(yǔ)言
c
是上一輩人使用的編程語(yǔ)言了，所以說(shuō)它在單片機(jī)——集成電路芯片，使用還是比較廣泛的，和c++一樣它也具有高性能的優(yōu)點(diǎn)，但是我們這一輩人我建議直接開(kāi)c++，
c++
今天仍然在使用原始的C語(yǔ)言，但是大多數(shù)現(xiàn)代開(kāi)發(fā)人員已改用C ++。
計(jì)算機(jī)程序，移動(dòng)應(yīng)用程序，視頻游戲，操作系統(tǒng)，整個(gè)瀏覽器，甚至在一定程度上還可以進(jìn)行Web開(kāi)發(fā)-如果您能想到的東西，C ++就能做到。且它運(yùn)行快速。
平臺(tái) 主要是軟件開(kāi)發(fā)；可以在各種情況下使用。
學(xué)習(xí)難度： 比較難學(xué)，特別是對(duì)于初學(xué)者。
平均工資 ：好像c++平均工資比Java高已經(jīng)是不爭(zhēng)的事實(shí)了，畢竟物以稀為貴莫。
優(yōu)點(diǎn)： 純粹的多功能性。您可以將其用于任何事情?？梢院芎玫胤g成其他語(yǔ)言。快速而強(qiáng)大。
缺點(diǎn)： 對(duì)于初學(xué)者來(lái)說(shuō)，不是正確的第一語(yǔ)言。由于年代久遠(yuǎn)，因此在應(yīng)用程序中具有普遍性，也異常復(fù)雜。對(duì)于Web開(kāi)發(fā)而言并不理想。
后續(xù)
如果你第一語(yǔ)言已經(jīng)掌握的差不多了，在大二下，那么此時(shí)可以根據(jù)時(shí)勢(shì)來(lái)考慮第二語(yǔ)言，下面我只提出我自己的薄見(jiàn)
- 還是上面的如果你學(xué)了Java，或c++那就繼續(xù)或者學(xué)習(xí)他們的拓展，QT，數(shù)據(jù)庫(kù)，底層框架，Web基礎(chǔ)等等
- 或者你就緊跟時(shí)代潮流，什么火，去學(xué)什么，前幾天的鴻蒙，就可以學(xué)的搭建，還要rust語(yǔ)言，go語(yǔ)言等等，前提是你能保證第一語(yǔ)言，餓不死你，不然就繼續(xù)扎根第一語(yǔ)言
最后
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)C++數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++begin和end運(yùn)算符的返回迭代器的類型如何判斷?
今天小編就為大家分享一篇關(guān)于C++begin和end運(yùn)算符的返回迭代器的類型如何判斷?，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-04-04
C語(yǔ)言實(shí)現(xiàn)紅黑樹(shù)的實(shí)例代碼
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)紅黑樹(shù)的實(shí)例代碼，有需要的朋友可以參考一下2013-12-12
C語(yǔ)言結(jié)構(gòu)體數(shù)組常用的三種賦值方法(包含字符串)
C語(yǔ)言只有在定義字符數(shù)組的時(shí)候才能用“=”來(lái)初始化變量,其它情況下是不能直接用“=”來(lái)為字符數(shù)組賦值的,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言結(jié)構(gòu)體數(shù)組常用的三種賦值方法,需要的朋友可以參考下2022-06-06
C語(yǔ)言結(jié)構(gòu)體詳細(xì)圖解分析
C 數(shù)組允許定義可存儲(chǔ)相同類型數(shù)據(jù)項(xiàng)的變量，結(jié)構(gòu)是 C 編程中另一種用戶自定義的可用的數(shù)據(jù)類型，它允許你存儲(chǔ)不同類型的數(shù)據(jù)項(xiàng)，本篇讓我們來(lái)了解C 的結(jié)構(gòu)體2022-03-03
C++ Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解
今天小編就為大家分享一篇關(guān)于C++Primer中&、*符號(hào)的多重定義與int *p和int* p的區(qū)別講解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-04-04
Qt+QWidget實(shí)現(xiàn)簡(jiǎn)約美觀的加載動(dòng)畫(huà)
這篇文章主要為大家詳細(xì)介紹了Qt如何結(jié)合QWidget實(shí)現(xiàn)簡(jiǎn)約美觀的加載動(dòng)畫(huà),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-02-02
C++實(shí)現(xiàn)職工工資管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單的職工工資管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C++實(shí)現(xiàn)LeetCode(103.二叉樹(shù)的之字形層序遍歷)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(103.二叉樹(shù)的之字形層序遍歷),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
用C語(yǔ)言模仿Python函數(shù)的實(shí)例
下面小編就為大家?guī)?lái)一篇用C語(yǔ)言模仿Python函數(shù)的實(shí)例。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-05-05
這篇文章主要介紹了C++求兩數(shù)之和并返回下標(biāo)題目的代碼詳解，本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08