成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

鄰接表的相關(guān)操作（類C語(yǔ)言）-創(chuàng)新互聯(lián)

目錄

站在用戶的角度思考問(wèn)題，與客戶深入溝通，找到江源網(wǎng)站設(shè)計(jì)與江源網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名與空間、雅安服務(wù)器托管、企業(yè)郵箱。業(yè)務(wù)覆蓋江源地區(qū)。

1.內(nèi)容

2.分析

3.代碼

1）頭文件（Head.H)

2）功能函數(shù)(function.cpp)

3）主函數(shù)(main.cpp)

4.運(yùn)行結(jié)果（DEV）

5.總結(jié)

1.內(nèi)容

針對(duì)于有向圖和無(wú)向圖的鄰接表的建立，求頂點(diǎn)的度以及廣度和深度遍歷圖。（由于有向網(wǎng)和無(wú)向網(wǎng)與有向圖和無(wú)向圖大致一致，只是多了權(quán)值，這里不再贅述）

2.分析

結(jié)構(gòu)：圖的所有頂點(diǎn)存儲(chǔ)在一個(gè)數(shù)組當(dāng)中，然后數(shù)組中的每一個(gè)元素又是一個(gè)鏈表的頭節(jié)點(diǎn)。

求頂點(diǎn)的度：對(duì)于有向圖來(lái)說(shuō)，出度就是頂點(diǎn)所在行所鏈接的元素的個(gè)數(shù)（使用鏈表的遍歷即可）

?入度就是指指向這個(gè)頂點(diǎn)的個(gè)數(shù)，需要遍歷每一行的鏈表，找到有多少結(jié)點(diǎn)鏈接了這? ?個(gè)頂點(diǎn)。（比如求D點(diǎn)的入度，也就是看有哪些行鏈接了D點(diǎn)）

深度遍歷：采用了遞歸的思想（類比二叉樹）

廣度遍歷：類似于二叉樹的層序遍歷。

在廣度和深度遍歷的時(shí)候，都需要考慮到圖不連通的情況，故我在下面的代碼中每個(gè)遍歷都由兩個(gè)函數(shù)構(gòu)成。

3.代碼

我在這兒是建立了一個(gè)項(xiàng)目，包括了頭文件、功能函數(shù)以及主函數(shù)

1）頭文件（Head.H)
#ifndef _FUNC_H 
#define _FUNC_H   

#define MVNum 100   //大頂點(diǎn)數(shù)
#define OK 1;
#define ERROR 0;

typedef char VerTexType;  //頂點(diǎn)數(shù)據(jù)類型 
typedef int Status; 
typedef int QElemType;

 
typedef struct ArcNode{  //邊結(jié)點(diǎn) 
	int adjvex;    //鄰接點(diǎn)的下標(biāo)
	struct ArcNode *nextarc;  //指向下一個(gè)鄰接點(diǎn) 
}ArcNode;

typedef struct VNode{  //頂點(diǎn)信息 
	VerTexType data;   //存放結(jié)點(diǎn)的內(nèi)容
	ArcNode *firstarc;  //指向第一個(gè)鄰接點(diǎn) 
}VNode,AdjList[MVNum];  //建立頭結(jié)點(diǎn)和包含頭結(jié)點(diǎn)的數(shù)組AdjList;  

typedef struct{
	AdjList vertices;   //包含頭節(jié)點(diǎn)的數(shù)組 
	int vexnum,arcnum;  //邊數(shù)和點(diǎn)數(shù) 
}ALGraph;

//隊(duì)列的結(jié)構(gòu)體
typedef struct QNode{
	QElemType data;  //數(shù)據(jù)
	struct QNode *next;  //指向下一個(gè)節(jié)點(diǎn) 
}QNode,*QueuePtr;
//鏈隊(duì)列中又存在著頭尾指針
typedef struct{
	QueuePtr front;  //隊(duì)頭指針
	QueuePtr rear;  //隊(duì)尾指針 
}LinkQueue;

extern Status CreateUDG(ALGraph &G);
extern Status LocateVex(ALGraph &G,VerTexType v);
extern Status CreateDG(ALGraph &G);
extern Status CalculateUDGD(ALGraph &G,VerTexType v);
extern Status CalculateDGI(ALGraph &G,VerTexType v);
extern Status CalculateSum(ALGraph &G,VerTexType v);
extern void DFSTraverse(ALGraph G);
extern void DFS(ALGraph G,int v);
extern void BFSTraverse(ALGraph G);
extern void BFS(ALGraph G,int v);
extern Status Reverse(ALGraph G);
extern void print();

extern Status InitQueue(LinkQueue &Q);
extern Status EnQueue(LinkQueue &Q,int e);
extern Status DeQueue(LinkQueue &Q,QElemType &e);
extern Status  QueueEmpty(LinkQueue Q);
extern Status DestroyQueue(LinkQueue &Q);

#endif
2）功能函數(shù)(function.cpp)
#includeusing namespace std;
#include "Head.H"

bool visited[MVNum];  //查看點(diǎn)是否被遍歷過(guò) 

//菜單欄
void print(){
	cout<<"==========================="<>G.vexnum>>G.arcnum;  //輸入頂點(diǎn)數(shù)和邊數(shù)
	cout<<"請(qǐng)輸入各個(gè)頂點(diǎn)的內(nèi)容：";
	for(i=0;i>G.vertices[i].data;   //建立數(shù)組的頭節(jié)點(diǎn) 
		G.vertices[i].firstarc=NULL;  //使頭節(jié)點(diǎn)指針的指向均為空 
	}
	for(k=0;k>v1>>v2;	
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		ArcNode* p1=new ArcNode;  //開辟一個(gè)結(jié)點(diǎn)
		p1->adjvex=j;   
		p1->nextarc=G.vertices[i].firstarc;  //頭插法插入 
		G.vertices[i].firstarc=p1;
		ArcNode* p2=new ArcNode;  //開辟節(jié)點(diǎn)
		p2->adjvex=i;
		p2->nextarc=G.vertices[j].firstarc; 
		G.vertices[j].firstarc=p2;
	}
	return OK;	
}
//有向圖
Status CreateDG(ALGraph &G){
	int i,j,k;
	VerTexType v1,v2;
	cout<<"請(qǐng)輸入此有向圖的頂點(diǎn)和邊數(shù)：";
	cin>>G.vexnum>>G.arcnum;
	cout<<"請(qǐng)輸入每個(gè)頂點(diǎn)的內(nèi)容："; 
	for(i=0;i>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;
	}
		
	for(k=0;k>v1>>v2; //輸入相鄰兩點(diǎn)
		i=LocateVex(G,v1);  //定位
		j=LocateVex(G,v2);
		ArcNode *p=new ArcNode; //開辟一個(gè)空間
		p->adjvex=j;
		p->nextarc=G.vertices[i].firstarc;  //頭插法插入 
		G.vertices[i].firstarc=p; 
	} 
	return OK; 
} 
Status LocateVex(ALGraph &G,VerTexType v){
	int i;
	for(i=0;inextarc;
		n++;
	} 
	return n;
} 
//有向圖的入度
//需要把每個(gè)頂點(diǎn)遍歷一次，找到到點(diǎn)i的情況，增加1 
Status CalculateDGI(ALGraph &G,VerTexType v){
	if(LocateVex(G,v)==-1)  return -1;  //輸入的頂點(diǎn)錯(cuò)誤的情況
	int i,j=LocateVex(G,v);  
	int n=0;  //計(jì)數(shù)
	ArcNode *p; //臨時(shí)指針 
	for(i=0;iadjvex==j)
				n++;
			p=p->nextarc;	
		}	
	}
	return n; 
} 
//有向圖的總度 
Status CalculateSum(ALGraph &G,VerTexType v){
	if(LocateVex(G,v)==-1) return  -1;
	return CalculateUDGD(G,v)+CalculateDGI(G,v); 
}
//遍歷輸出(深度優(yōu)先搜索遍歷） 
void DFSTraverse(ALGraph G){
	int i;
	for(i=0;inextarc){
		if(visited[p->adjvex]==false) DFS(G,p->adjvex);
	} 
}
//廣度優(yōu)先算法
void BFSTraverse(ALGraph G){
	int i;
	for(i=0;inextarc){
			if(visited[p->adjvex]==false){
				visited[p->adjvex]=true;
				EnQueue(Q,p->adjvex);
			}
		}
	} 
}
//存儲(chǔ)結(jié)構(gòu)的遍歷
Status Reverse(ALGraph G){
	int i,j;
	ArcNode *p;
	for(i=0;i";
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
			cout<adjvex].data<<"->";
		cout<<""<next=NULL;  //頭指針的指針域置空
	return OK;
} 
//入隊(duì)列
Status EnQueue(LinkQueue &Q,int e){
	QueuePtr p=new QNode;  //開辟一個(gè)空間
	p->data=e;    //內(nèi)容存儲(chǔ)
	Q.rear->next=p;
	p->next=NULL;
	Q.rear=p;
	return OK; 
} 
//出隊(duì)列
//判斷是否為空
//不為空，判斷是否是只有一個(gè)元素 
Status DeQueue(LinkQueue &Q,QElemType &e){
	if(Q.front==Q.rear)  return ERROR;
	QueuePtr p=Q.front->next; 
	e=p->data;  //得到元素值 
	Q.front->next=p->next;
	if(p==Q.rear){
		Q.rear=Q.front;
	} 
	delete p;
	return OK;
} 
//判空
Status  QueueEmpty(LinkQueue Q){
	return (Q.front==Q.rear); 
}
//銷毀隊(duì)列
Status DestroyQueue(LinkQueue &Q){
	QueuePtr p;
	while(Q.front){
		p=Q.front;
		Q.front=Q.front->next;
		delete p;
	}
	return OK;
}
3）主函數(shù)(main.cpp)
#includeusing namespace std; 
#include "head.H"

int main(int argc, char** argv) {
	VerTexType v;
	ALGraph G;
	char order1,order2;  //選擇用char類型，使得當(dāng)選擇輸入為字母時(shí)，不會(huì)出錯(cuò)。 
	cout<<"============================"<>order1;			
	}while(order1!='1'&&order1!='2'&&order1!='0');
	switch(order1){
		case '1':
			do{
				print();
				cout<<"請(qǐng)輸入你的選擇：";
				cin>>order2;
				switch(order2){
					case '1':
						CreateUDG(G);
						cout<<"此無(wú)向圖的鄰接表建立成功?。。?<>v;
						if(CalculateUDGD(G,v)==-1)
							cout<>order2;
				switch(order2){
					case '1':
						CreateDG(G);
						cout<<"此有向圖的鄰接表建立成功！??！"<>v;
						if(CalculateUDGD(G,v)==-1)
							cout<
4.運(yùn)行結(jié)果（DEV）

無(wú)向圖：

建立

?

求度

遍歷

有向圖：

創(chuàng)建

?

求度

遍歷

5.總結(jié)

總的來(lái)說(shuō)，這個(gè)實(shí)驗(yàn)綜合性較強(qiáng)，需要用到之前說(shuō)學(xué)的鏈表和隊(duì)列的操作，結(jié)構(gòu)也更加復(fù)雜。

謝謝閱讀，希望對(duì)大家有幫助吖！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：鄰接表的相關(guān)操作（類C語(yǔ)言）-創(chuàng)新互聯(lián)
本文鏈接：http://jinyejixie.com/article4/gpjie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計(jì)、服務(wù)器托管、定制開發(fā)、云服務(wù)器、網(wǎng)站導(dǎo)航、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

临颍县| 通辽市| 五台县| 开平市| 平度市| 长兴县| 綦江县| 高密市| 慈利县| 黄冈市| 太康县| 偃师市| 靖江市| 彭水| 青岛市| 海宁市| 盖州市| 紫阳县| 偃师市| 太保市| 溆浦县| 台东县| 乐陵市| 遵义县| 凤山市| 沛县| 太白县| 石楼县| 建昌县| 武平县| 缙云县| 大悟县| 济南市| 丰县| 板桥市| 贺兰县| 凤庆县| 盱眙县| 金秀| 垫江县| 长岛县|