package?test;
創(chuàng)新互聯(lián)自2013年創(chuàng)立以來，先為安慶等服務(wù)建站，安慶等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為安慶企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
import?java.util.*;
public?class?GectorGraph?{
private?Point?root;
private?ListListString?circlePath;
public?GectorGraph(String?pointName)?{
root=new?Point(pointName);
}
public?GectorGraph(Point?point)?{
root=point;
}
public?boolean?hasCirclePath(){
findCirclePath();
return?circlePath.size()0;
}
public?void?findCirclePath(){
ListPoint?CirclePoints=findCirclePoint();
if(circlePath==null){circlePath=new?ArrayListListString();}
for(Point?tempPoint:CirclePoints){
ListString?pointPath=new?ArrayListString();
findPointPath(tempPoint,root,pointPath);
pointPath.add(root.pointName);
circlePath.add(pointPath);
}
}
public?boolean?findPointPath(Point?target,Point?currentPoint,ListString?pointPath){
if(currentPoint.equals(target)){return?true;}
if(!currentPoint.hasNext()){return?false;}
ListPoint?pointList=?currentPoint.getNextPointList();
for(Point?tempPoint:pointList){
if(tempPoint.equals(root)){continue;}
if(findPointPath(target,tempPoint,pointPath)){
pointPath.add(tempPoint.pointName);
return?true;
}
}
return?false;
}
private?ListPoint?findCirclePoint(){
if(!root.hasNext()){return?null;}
ListPoint?circlePoints=new?ArrayListPoint();
findCirclePoint(root,root,circlePoints);
return?circlePoints;
}
private?void?findCirclePoint(Point?root,Point?currentPoint,ListPoint?circlePoints){
if(!currentPoint.hasNext()){return;}
ListPoint?pointList=?currentPoint.getNextPointList();
for(Point?tempPoint:pointList){
if(tempPoint.equals(root)){circlePoints.add(currentPoint);}
else{findCirclePoint(root,tempPoint,circlePoints);}
}
}
public?void?showPath(){
if(circlePath==null){System.out.println("Error");}
for(ListString?tempList:circlePath){
StringBuffer?pathString=new?StringBuffer();
int?tempListIndex=tempList.size()-1;
for(;tempListIndex-1;tempListIndex--){
pathString.append(tempList.get(tempListIndex));
if(tempListIndex!=0){pathString.append("-");}
}
System.out.println(pathString.toString());
}
}
public?static?void?main(String[]?args)?{
Point?root=new?Point("root");
ListPoint?p3=new?ArrayListPoint();
for(int?i=0;i3;i++){
p3.add(new?Point("3/1/"+i));
}
ListPoint?p4=new?ArrayListPoint();
for(int?i=0;i3;i++){
p4.add(new?Point("3/2/"+i));
}
ListPoint?p2=new?ArrayListPoint();
for(int?i=0;i2;i++){
p2.add(new?Point("2/"+i));
}
p3.add(0,root);
p3.get(2).addNextPoint(root);
p4.get(0).addNextPoint(root);
p2.get(0).addNextPointList(p3);
p2.get(1).addNextPointList(p4);
root.addNextPointList(p2);
GectorGraph?gg=new?GectorGraph(root);
if(gg.hasCirclePath()){
gg.showPath();
}
}
}
class?Point{
public?String?pointName;
private?ListPoint?nextPointList;
public?Point(String?pointName)?{
this.pointName=pointName;
}
public?void?addNextPoint(Point?p){
if(nextPointList==null){nextPointList=new?ArrayListPoint();}
nextPointList.add(p);
}
public?void?addNextPointList(ListPoint?pList){
if(nextPointList==null){nextPointList=new?ArrayListPoint();}
nextPointList.addAll(pList);
}
public?boolean?hasNext(){
return?nextPointList!=null!nextPointList.isEmpty();
}
public?ListPoint?getNextPointList()?{
return?nextPointList;
}
public?void?setNextPointList(ListPoint?nextPointList)?{
this.nextPointList?=?nextPointList;
}
}
給你一個(gè)鄰接表的完整程序：
#include iostream.h
struct node
{
int data;
node *next;
};
class list
{
public:
list(){head=NULL;};
void MakeEmpty();
int Length();
void Insert(int x,int i);//將x插入到第i個(gè)結(jié)點(diǎn)（不含頭結(jié)點(diǎn)）的之后
void Insertlist(int a,int b);//將節(jié)點(diǎn)b插入a之前
int Delete(int x);
int Remove(int i);
int Find(int x);
void Display();
private:
node *head;
};
void list::Display()
{
node *current=head;
while (current!=NULL)
{
coutcurrent-data" ";
current=current-next;
}
coutendl;
}
void list::MakeEmpty()
{
head=NULL;
}
int list::Length()
{int n=1;
node *q=head;
if(q==NULL)
n=1;
else
while(q!=NULL)
{
n++;
q=q-next;
}
return n;
}
int list::Find(int x)//在鏈表中查找數(shù)值為x的結(jié)點(diǎn)，成功返回1，否則返回0
{
node *p=head;
while(p!=NULLp-data!=x)
p=p-next;
if(p-data==x)
return 1;
else
return 0;
}
void list::Insert (int x,int i)//將x插入到第i個(gè)結(jié)點(diǎn)（不含頭結(jié)點(diǎn)）的之后；
{
node *p;//p中放第i個(gè)結(jié)點(diǎn)
node *q;//q中放i后的結(jié)點(diǎn)
node *h;//h中存要插入的結(jié)點(diǎn)
h=new node;
h-data =x;
p=head;
if(p-next !=NULL) //鏈表不是只有一個(gè)結(jié)點(diǎn)或者空鏈表時(shí)候
{
int n=1;
while(p-next !=NULL)
{
n++;
p=p-next ;
}// 得到鏈表的結(jié)點(diǎn)的個(gè)數(shù)
p=head;//使p重新等于鏈?zhǔn)?/p>
if(i==n)//i=n時(shí)，直接加在最后面就行了
{
while(p-next !=NULL)
p=p-next;
p-next=h;
h-next =NULL;
}
else if(ini1)//先找到第i個(gè)結(jié)點(diǎn)，用p存第i個(gè)結(jié)點(diǎn)，用q存i后的結(jié)點(diǎn)，用h存要插入的結(jié)點(diǎn)
{
for(int j=1;ji;j++)
p=p-next;//找到第i個(gè)結(jié)點(diǎn)，用p存第i個(gè)結(jié)點(diǎn)
q=p-next;//q存i后的結(jié)點(diǎn)
p-next=h;
h-next=q;
}
else
cout"超出鏈表結(jié)點(diǎn)個(gè)數(shù)的范圍"endl;
}
else
cout"這個(gè)鏈表是空鏈表或者結(jié)點(diǎn)位置在首位"endl;
}
void list::Insertlist(int a,int b)//將b插入到結(jié)點(diǎn)為a之前
{
node *p,*q,*s;//p所指向的結(jié)點(diǎn)為a,s所指為要插入的數(shù)b,q所指向的是a前的結(jié)點(diǎn)
s=new node;
s-data=b;
p=head;
if(head==NULL)//空鏈表的時(shí)候
{
head=s;
s-next=NULL;
}
else
if(p-data==a)//a在鏈?zhǔn)讜r(shí)候
{
s-next=p;
head=s;
}
else
{
while(p-data!=ap-next!=NULL)//使p指向結(jié)點(diǎn)a,q指向a之前的結(jié)點(diǎn)
{
q=p;
p=p-next;
}
if(p-data==a)//若有結(jié)點(diǎn)a時(shí)候
{
q-next=s;
s-next=p;
}
else//沒有a的時(shí)候
{
p-next=s;
s-next=NULL;
}
}
}
int list::Delete(int x)//刪除鏈表中值為x的結(jié)點(diǎn)，成功返回1，否則返回0；
{
node *p,*q;
p=head;
if(p==NULL)
return 0;
if(p-data==x)
{
head=p-next;
delete p;
return 1;
}
else
{
while(p-data!=xp-next!=NULL)
{ q=p;
p=p-next;
}
if(p-data==x)
{
q-next =p-next;
delete p;
return 1;
}
else
return 0;
}
}
int list::Remove(int i)
{
node *p,*q;
p=head;
if(p!=NULL)
{ int n=1;
while(p-next !=NULL)
{
n++;
p=p-next ;
}//得到鏈表結(jié)點(diǎn)的個(gè)數(shù)
p=head;
if(i==n)//i結(jié)點(diǎn)在結(jié)尾的時(shí)候
{
while(p-next!=NULL)
{
q=p;
p=p-next;
}
q-next=NULL;
delete p;
return 1;
}
else if(ini1)//i結(jié)點(diǎn)在中間的時(shí)候
{
for(int j=1;ji;j++)
{
q=p;//q中放i前的結(jié)點(diǎn)
p=p-next ;//p中放第i個(gè)結(jié)點(diǎn)
}
q-next=p-next;
delete p;
return 1;
}
else if(i==1)//i結(jié)點(diǎn)在首位的時(shí)候
{
q=p-next;
head=q;
delete p;
return 1;
}
else
return 0;
}
else
return 0;
}
void main()
{
list A;
int data[10]={1,2,3,4,5,6,7,8,9,10};
A.Insertlist(0,data[0]);
for(int i=1;i10;i++)
A.Insertlist(0,data[i]);
A.Display();
menu:cout"1.遍歷鏈表"'\t'"2.查找鏈表"'\t'"3.插入鏈表"endl;
cout"4.刪除鏈表"'\t'"5.鏈表長度"'\t'"6.置空鏈表"endl;
int m;
do
{
cout"請輸入你想要進(jìn)行的操作（選擇對應(yīng)操作前面的序號）："endl;
cinm;
}while(m1||m6);//當(dāng)輸入的序號不在包括中，讓他重新輸入
switch(m)
{
case 1:
{
A.Display ();
goto menu;
};break;
case 2:
{
cout"請輸入你想要找到的結(jié)點(diǎn)："endl;
int c;
cinc;//輸入你想要找到的結(jié)點(diǎn)
if(A.Find (c)==1)
{
cout"可以找到"cendl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout"鏈表中不存在"cendl;
A.Display ();//重新顯示出鏈表A
}
goto menu;
};break;
case 3:
{
cout"請選擇你要插入的方式(選擇前面的序號進(jìn)行選擇）"endl;
cout"1.將特定的結(jié)點(diǎn)加入到特定的結(jié)點(diǎn)前"'\t'"2.將特定的結(jié)點(diǎn)加到特定的位置后"endl;
int b1;
do
{
cout"請輸入你想要插入的方式（選擇前面的序號進(jìn)行選擇）："endl;
cinb1;
}while(b11||b12);//當(dāng)輸入的序號不在包括中，讓他重新輸入
if(b1==1)
{
cout"請輸入你想要插入的數(shù)和想要插入的結(jié)點(diǎn)（為此結(jié)點(diǎn)之前插入）："endl;
int a1,a2;
cina1a2;
A.Insertlist (a1,a2);//將a1插入到結(jié)點(diǎn)為a2結(jié)點(diǎn)之前
cout"此時(shí)鏈表為："endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout"請輸入你想要插入的數(shù)和想要插入的位置（為此結(jié)點(diǎn)之后插入）："endl;
int a1,a2;
cina1a2;
A.Insert (a1,a2);//將a1插入到結(jié)點(diǎn)位置為a2的結(jié)點(diǎn)之后
cout"此時(shí)鏈表為："endl;
A.Display ();//重新顯示出鏈表A
}
goto menu;
};break;
case 4:
{
cout"請選擇你要?jiǎng)h除的方式(選擇前面的序號進(jìn)行選擇）"endl;
cout"1.刪除特定的結(jié)點(diǎn)"'\t'"2.刪除特定位置的結(jié)點(diǎn)"endl;
int b1;
do
{
cout"請輸入你想要插入的方式（選擇前面的序號進(jìn)行選擇）："endl;
cinb1;
}while(b11||b12);//當(dāng)輸入的序號不在包括中，讓他重新輸入
if(b1==1)
{
cout"請輸入你想要?jiǎng)h除的結(jié)點(diǎn)："endl;
int a;
cina;//輸入你想要?jiǎng)h除的結(jié)點(diǎn)
if(A.Delete (a)==1)
{
cout"成功刪除"aendl;
cout"刪除后的鏈表為："endl;
A.Display ();
}
else
{
cout"此鏈表為："endl;
A.Display ();//重新顯示出鏈表A
cout"鏈表中不存在"aendl;
}
}
else
{
cout"請輸入你想要?jiǎng)h除的結(jié)點(diǎn)位置："endl;
int b;
cinb;//輸入你想要?jiǎng)h除的結(jié)點(diǎn)的位置
if(A.Remove(b)==1)
{
cout"成功刪除第"b"個(gè)結(jié)點(diǎn)"endl;
cout"刪除后的鏈表為："endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout"當(dāng)前鏈表的結(jié)點(diǎn)個(gè)數(shù)為："A.Length ()endl;
cout"您輸入的結(jié)點(diǎn)位置越界"endl;
}
}
goto menu;
};break;
case 5:
{
cout"這個(gè)鏈表的結(jié)點(diǎn)數(shù)為:"A.Length ()endl;
goto menu;
};break;
case 6:
{
A.MakeEmpty ();
cout"這個(gè)鏈表已經(jīng)被置空"endl;
goto menu;
};break;
}
}
評論(3)|1
sunnyfulin |六級采納率46%
擅長：C/C++JAVA相關(guān)Windows數(shù)據(jù)結(jié)構(gòu)及算法百度其它產(chǎn)品
按默認(rèn)排序|按時(shí)間排序
其他1條回答
2012-04-23 17:41121446881|六級
我寫了一個(gè)C語言的，只給你兩個(gè)結(jié)構(gòu)體和一個(gè)初始化函數(shù)：
#include "stdio.h"
#include "malloc.h"
struct adjacentnext//鄰接表項(xiàng)結(jié)構(gòu)體
{
int element;
int quanvalue;
struct adjacentnext *next;
};
struct adjacenthead//鄰接表頭結(jié)構(gòu)體
{
char flag;
int curvalue;
int element;
struct adjacenthead *previous;
struct adjacentnext *son;
};
//初始化圖，用鄰接表實(shí)現(xiàn)
struct adjacenthead *mapinitialnize(int mapsize)
{
struct adjacenthead *ahlists=NULL;
struct adjacentnext *newnode=NULL;
int i;
int x,y,z;
ahlists=malloc(sizeof(struct adjacenthead)*mapsize);
if(ahlists==NULL)
return NULL;
for(i=0;imapsize;i++)
{
ahlists[i].curvalue=0;
ahlists[i].flag=0;
ahlists[i].previous=NULL;
ahlists[i].son=NULL;
ahlists[i].element=i+1;
}
scanf("%d%d%d",x,y,z);//輸入源結(jié)點(diǎn)，目的結(jié)點(diǎn)，以及源結(jié)點(diǎn)到目的結(jié)點(diǎn)的路權(quán)值
while(x!=0y!=0)//x,y至少有一個(gè)零就結(jié)束
{
newnode=malloc(sizeof(struct adjacentnext));
newnode-element=y;
newnode-quanvalue=z;
newnode-next=ahlists[x-1].son;
ahlists[x-1].son=newnode;
scanf("%d%d%d",x,y,z);
}
return ahlists;//返回鄰接表頭
}
一個(gè)頂點(diǎn)a在一個(gè)環(huán)上，那么存在以它為終點(diǎn)的邊, 假設(shè)這些邊的起點(diǎn)集合為PreA, 考察點(diǎn)a能否到達(dá)點(diǎn)PreA中的點(diǎn)，如果到達(dá)就找到了一個(gè)環(huán)，否則點(diǎn)a不在環(huán)上。
遍歷圖中的頂點(diǎn)進(jìn)行上述操作即可。
Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號方式，一種是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是貪心法的算法策略，大概過程如下：
1.聲明兩個(gè)集合，open和close，open用于存儲未遍歷的節(jié)點(diǎn)，close用來存儲已遍歷的節(jié)點(diǎn)
2.初始階段，將初始節(jié)點(diǎn)放入close，其他所有節(jié)點(diǎn)放入open
3.以初始節(jié)點(diǎn)為中心向外一層層遍歷，獲取離指定節(jié)點(diǎn)最近的子節(jié)點(diǎn)放入close并從新計(jì)算路徑，直至close包含所有子節(jié)點(diǎn)
代碼實(shí)例如下：
Node對象用于封裝節(jié)點(diǎn)信息，包括名字和子節(jié)點(diǎn)
[java] view plain copy
public class Node {
private String name;
private MapNode,Integer child=new HashMapNode,Integer();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public MapNode, Integer getChild() {
return child;
}
public void setChild(MapNode, Integer child) {
this.child = child;
}
}
MapBuilder用于初始化數(shù)據(jù)源，返回圖的起始節(jié)點(diǎn)
[java] view plain copy
public class MapBuilder {
public Node build(SetNode open, SetNode close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
圖的結(jié)構(gòu)如下圖所示：
Dijkstra對象用于計(jì)算起始節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑
[java] view plain copy
public class Dijkstra {
SetNode open=new HashSetNode();
SetNode close=new HashSetNode();
MapString,Integer path=new HashMapString,Integer();//封裝路徑距離
MapString,String pathInfo=new HashMapString,String();//封裝路徑信息
public Node init(){
//初始路徑,因沒有A-E這條路徑,所以path(E)設(shè)置為Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A-B");
path.put("C", 1);
pathInfo.put("C", "A-C");
path.put("D", 4);
pathInfo.put("D", "A-D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A-F");
path.put("G", 5);
pathInfo.put("G", "A-G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//將初始節(jié)點(diǎn)放入close,其他節(jié)點(diǎn)放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距離start節(jié)點(diǎn)最近的子節(jié)點(diǎn),放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
MapNode,Integer childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子節(jié)點(diǎn)在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())newCompute){//之前設(shè)置的距離大于新計(jì)算出來的距離
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"-"+child.getName());
}
}
}
computePath(start);//重復(fù)執(zhí)行自己,確保所有子節(jié)點(diǎn)被遍歷
computePath(nearest);//向外一層層遞歸,直至所有頂點(diǎn)被遍歷
}
public void printPathInfo(){
SetMap.EntryString, String pathInfos=pathInfo.entrySet();
for(Map.EntryString, String pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 獲取與node最近的子節(jié)點(diǎn)
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
MapNode,Integer childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distanceminDis){
minDis=distance;
res=child;
}
}
}
return res;
}
}
Main用于測試Dijkstra對象
[java] view plain copy
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}
分少懶得寫，添加一個(gè)畫布組件，節(jié)點(diǎn)用圓形素材，有向圖用箭頭素材。
先添加節(jié)點(diǎn)， 后連線，完畢
重慶分公司
重慶分公司
