數(shù)據(jù)結(jié)構(gòu)樹課件(java)

構(gòu)造圖結(jié)構(gòu)(鄰接矩陣或鄰接表表示)，并實(shí)現(xiàn)以下操作

1.圖的深度優(yōu)先和廣度優(yōu)先遍歷

2.圖的最小生成樹(prim算法或kruskal算法)

packageseventh;

interfaceSqelist<T>{〃鏈表類接口--2018--10-15-高金磊

publicvoidinsert(Tt);〃尾插

publicvoidinsert(inti,Tt)throwsException;//插入成為第i個元素

publicTdelect(inti)throwsException;//取出第i個并刪除

publicTgetNode(inti)由rowsExceplion;〃取出第i個元素但不刪除

publicbooleanisEmptyO;

)

packageseventh;

classNode{/*鏈表基本單元類

*記錄鏈表基本數(shù)據(jù)和地址

*數(shù)據(jù)存儲為int型

*高金磊--2018-11-25

**/

charname;〃列名

Nodenext=null;

publicNode(){

)

publicNode(chardata){

this(data,null);

)

publicNode(chardata,NodenextNode){

=data;

this.next=nextNode;

)

publicintgetData(){

returnname;

}

publicNodegetNext(){

returnnext;

}

publicvoidsetData(chardata){

=data;

}

publicvoidsetNext(Nodenext){

this.next=next;

}packageseventh;

publicclassMatriximplementsAbstractMatrix<Integer>{

intlength;〃容器長度

publicIntegerelement口口;〃矩陣對象

publicMatrix(int1){〃構(gòu)造長度為1的矩陣

if(l>=D{

this.length=l;

element=newIntegerfl][l];

}else{

try(

thrownewException("構(gòu)造矩陣長度小于等于1是一種錯誤");

}catch(Exceptione){

//TODO自動生成的catch塊

e.printStackTrace();

@Override

publicvoidset(intx,inty,Integert){

while(x>=length||y>=length){〃擴(kuò)大容量

getmoreMaxMatrix();

)

element[x][y]=t;

)

@Override

publicIntegerget(intx,inty){

returnelement[x][y];〃數(shù)組越界用自帶的異常處理機(jī)制

)

?Override

publicIntegerfindelect(intx,inty){//刪除x行y列元素并將后面的元素整體

前移--不返回任何信息

Integer[][]middle二newIntegerfelement.length][element.length];

for(inti=0;i<element.length-1;i++){

for(intj=0;j<element.length-1;j++){

intis=i>=x?i+l:i;

intjs=j>=y?j+l:j;

middle[i][j]=element[is][js];

element=middle;

returnnull;

@Override

publicintgetRows(){

returnthis.length;

)

?Override

publicintgetColumns(){

returnthis.length;

)

@Override

publicintgetLengh(){

//TODO自動生成的方法存根

return0;

)

?Override

publicvoidgetmoreMaxMatrix(){〃擴(kuò)容二倍

Integer[][]middle=newInteger[element.length*2][element.length*2];

for(inti=0;i<element.length;i++){

fbr(intj=0;j<element.length;j++){

middlefi][j]=element[i][j];

element二middle;

this,length=element,length;//通知擴(kuò)容完畢

)

@Override

publicStringtoStringO{

for(inti=0;i<element.length;i++){

Integerf]js=element[i];

fbr(intj=0;j<js.length;j++){

intm=js[j]!=null?js[j]:Graph.MAXWEIGHT;

System.out.print(m+,,\tH);

)

System.out.println();

returnsuper.toString();

packageseventh;

publicclassListimplementsSqelist<Node>{〃順序表用于保存結(jié)點(diǎn)的信息

Nodeheade=newNode。;//頭部結(jié)點(diǎn)

intlength=0;

@Override

publicvoidinsert(NodetNode){

Nodenode=heade;

while(node.next!=null){

node=node.next;

)

node.next=tNode;

length++；

)

@Override

publicvoidinsert(inti,NodetNode)throwsException{

if(i>length+l){

thrownewException(“越界"+”\t線性表的總長為”+length+”\n"+”向第

”+i+”個位置插入元素是一種錯誤)

)

else{

Nodenode=heade;

intmiddle=0;

while(middle!=i-l){

middle++;

node=node.next;

)

tNode.next=node.next;

node.next=tNode;

)

length++;

)

?Override

publicNodedelect(inti)throwsException{

NodedelectNode=null;

if(i>length+l){

thrownewException(“越界"+”\t線性表的總長為“+怕華山+”\11”+"刪除

第"+i+”個位置的元素是一種錯誤)

else{

Nodenode=heade;

intmiddle=0;

while(middle!=i-l){

middle++;

node=node.next;

)

delectNode=node.next;

node.next=node.next.next;

)

length—;

returndelectNode;

)

@Override

publicNodegetNode(inti)throwsException{

Noderesult=null;

if(i>length+l){

thrownewException("越界"+”\t線性表的總長為“+歸期出+”\/+”刪除

第"+i+”個位置的元素是一種錯誤)

}

else{

Nodenode=heade;

intmiddle=0;

while(middle!=i-l&&i!=O){

middle++;

node=node.next;

)

result=node.next;

)

returnresult;

)

@Override

publicbooleanisEmpty(){

returnheade.next=null;

)

?Override

publicStringtoStringO{

Stringresult="”；

Nodenode=heade;

while(node.next!=null){

node=node.next;

result=result+^Xn'^;

returnresult;

packageseventh;

publicclassGraphimplementsAbstractGraph<Node>{

protectedstaticintMAXWEIGHT=Oxffff;〃設(shè)置正無窮

protectedListlist=newList。;//存放頂點(diǎn)的順序表

protectedMatrixedge=newMatrix(2);〃生成矩陣用來表示每個邊的權(quán)值

?Override

publicintvertexCount。{〃頂點(diǎn)個數(shù)

returnlist.length;

)

(?Override

publicNodegetvertex(inti)throwsException{〃返回第i個頂點(diǎn)--越界異常

returnlist.getNode(i);

)

@Ovemde

publicvoidsetVertex(inti,Nodex)throwsException{〃插入x為第i個元素一

越界異常

list.insert(i,x);

)

@Override

publicintinsertVertex(Nodex){//插入一個頂點(diǎn)x--尾插一返回插入的位置

list.insert(x);

edge.set(list.length-1,list.length-1,null);//通知并判斷是否擴(kuò)容

returnlist.length;

)

@Override

publicvoidremoveVertex(inti)throwsException{〃刪除第i個頂點(diǎn)

list.delect(i);

edge.delect(i-1,i-1);

)

?Override

publicintnext(inti,intj,boolean口visited){〃返回第i-1行j-1列之后是否元素

的位置

for(intn=0;n<list.length;n++){

if(!visited[n]&&edge.get(i,n)!=null){

returnn;

return-1;

)

@Override

publicvoidinsertEdge(inti,intj,intweight){

edge.set(i-l,j-l,weight);

edge.set(j-l,i-1,weight);

)

?Override

publicvoidremoveEdge(inti,intj){

edge.set(i-l,j-1,null);

edge.set(j-l,i-1,null);

)

@Override

publicintgetweight(inti,intj){

returnedge.get(i-l,j-1);

}''

@Ovemde

publicvoidDFSTraverse(inti)throwsException{

booleanvisited[]=newboolean[this.vertexCount()];

intj=i;

do{

if(!visited[j]){〃還存在沒有遍歷的樹一兼容森林

System.out.print("{")；

this.depthfs(j,visited);

System,out.print。}”);

)

j-(j+l)%(this.vertexCount());

}while(j!=i)；

System.out.println();

privatevoiddepthfs(intj,boolean[]visited)throwsException{

System.out.print((char)this.getvertex(j+l).getData()+',n)；

visited[j]=true;

inti=this.next(j,-1,visited);

while(i!=-l){

if(!visited[i]){

depthfs(i,visited);

i=this.next(j,i,visited);

@Ovemde

publicvoidBFSTraverse(inti)throwsException{〃廣度優(yōu)先算法

booleanvisted[]=newboolean[this.list.length];〃訪問標(biāo)記數(shù)組

intj=i;

do{

if(!visted[j]){

System.out.print("{")；

breadthfs(j,visted);

System.out.print(n}n);

)

j-(j+l)%this.vertexCount();

}while(j!=i);

System.out.printlnO;

)

privatevoidbreadthfs(intj,boolean[]visited)throwsException{

System.out.print((char)list.getNode(j4-l).getData());

visited[j]=true;

for(inti=0;i<visited.length;i++){//遍歷該行所有元素

if(!visited[i]&&edge.get(j,i)!=null){

System.out.print((char)list.getNode(i+l).getData());

visited[i]=true;

@Override

publicvoidminSpanTree(){//最小生成樹

intsumweight=0;

Edgeedges[]=newEdge[veilexCount()*vertexCount()];〃用于存儲邊

intn=0;

for(inti=0;i<vertexCount();i++){

for(intj=0;j<vertexCount();j++){

edges[n]=newEdge();

edges[n].x=j;

edges[n].y=i;

edges[n+-i-].weight=edge.get(j,i)==null?MAXWEIGHT:edge.get(j,i);

//需要n-1個邊連接n個結(jié)點(diǎn)來組成最小生成樹

for(inti=0;i<vertexCount()-l;i++){

intmiddlex=0;

intmiddley=0;

intweight二MAXWEIGHT;

for(intj=0;j<edges.length;j++){

if(weight>edges[j].weight){

middlex=edges[j].x;

middley=edges[j].y;

weight=edges[j].weight;

)

)

〃輸出一條結(jié)果

System.out.println(,,X:',+middlex+n\tY:,'+middley+,,\t權(quán)值:"weight);

sumweight+=weight;

〃取消通往〈X,Y>和vy,x>的邊

//取消所有通往y結(jié)點(diǎn)的邊

for(intm=0;m<edges.length;m++){

edgesfm].weight=(edges[ml.y==middley)?MAXWEIGHT:edges[m].weight;

edgesfm].weight=(edges[m].x==middlex&&edges[m].y=middley)?MAXWEIG

HT:edges[m].weight;

edges[m].weight=(edges[m].x==middley&&edges[m].y==middlex)?MAXWEIG

HT:edges\m].weight;

System.out.printin("總權(quán)值和為:\t"+sumweight);

?Override

publicvoidshortestPath(inti){

@Override

publicvoidshortestPath(){

//TODO自動生成的方法存根

packageseventh;

publicclassEdge{〃邊數(shù)據(jù)存儲對象

publicintx=0;

publicinty=0;

publicintweight=0;

)

packageseventh;

publicinterfaceAbstractMatrixvT＞{〃矩陣接口

voidset(intx,inty,Tt);〃設(shè)置＜x,y＞處的元素值

Tget(intx,inty);〃獲?。紉,y＞處的值

intgetRows();〃返回當(dāng)前總的行數(shù)

intgetColumns();〃返回當(dāng)前總的列數(shù)

intgetLengh();//返回總可用長度(默認(rèn)為方陣)

voidgetmoreMaxMatrix();〃擴(kuò)容

T[][]delect(intx,inty);〃刪除vx,y＞并將后面的前移

StringtoString();

)

packageseventh;

publicinterfaceAbstractGraph＜T＞{

intvertexCount。;//返回頂點(diǎn)數(shù)

Tgetvertex(inti)throwsException，返回頂點(diǎn)Vi元素

voidsetVertex(inti,Tx)throwsException;〃設(shè)置頂點(diǎn)Vi元素為x

intinsertVertex(Tx);〃插入頂點(diǎn)x

voidremoveVertex(inti)throwsException;//冊!]除頂點(diǎn)Vi及其臨邊

voidinsertEdge(inti,intj,intweight);//插入邊vVi,Vj＞,權(quán)值為weight

voidremoveEdge(inti,intj);〃冊!j除邊vVi,Vj＞

intgetweight(inti,intj);〃返回vVi,Vj＞的權(quán)值

voidDFSTraverse(inti)throwsException;〃以Vi為頂點(diǎn)進(jìn)行深度優(yōu)先遍歷

voidBFSTraverse(inti)throwsException;〃廣度優(yōu)先遍歷

voidminSpanTree。;//求最小生成樹

voidshortestPath(inti);〃求帶權(quán)圖頂點(diǎn)Vi的單源最短路徑

voidshortestPath。;//求帶權(quán)圖的每對頂點(diǎn)的最短路徑以及長度

intnext(inti,intj,boolean口visted);//返回Vi在Vj后的后繼鄰接頂點(diǎn)序號

)

packageseventh;

publicclassTest{

publicstaticvoidmain(String[]args){

Listlist=newList();

System.out.println(list.toStringO);

list.insert(newNode('a'));

list.insert(newNode('b'));

list.insert(newNode('c'));

list.insert(newNode(d));

System,out.printin("測試單鏈表的插入功能:”+list.toString());

try{

list.delect(3);

}catch(Exceptione){

//TODO自動生成的catch塊

e.printStackTrace();

)

System,out.printin("測試單鏈表的刪除功能:“+list.toString());

try(

Matrixmatrix二newMatrix(lO);

fbr(inti=0;i<matrix.length;i++){

for(intj=0;j<matrix.length;j++){

matrix.set(i,j,i+j)；

))

matrix.set(19,19,100);

System.out.printin("測試矩陣的插入刪除和自動擴(kuò)容功能”);

matrix.toStringO;

matrix.delect(3,3);

matrix.toString();

}catch(Exceptione){

//TODO自動生成的catch塊

e.printStackTrace();

)

try(

Sy