数据结构树课件(java)

构造图结构(邻接矩阵或邻接表表示)，并实现以下操作

1.图的深度优先和广度优先遍历

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{/*链表基本单元类

*记录链表基本数据和地址

*数据存储为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){〃构造长度为1的矩阵

if(l>=D{

this.length=l;

element=newIntegerfl][l];

}else{

try(

thrownewException("构造矩阵长度小于等于1是一种错误");

}catch(Exceptione){

//TODO自动生成的catch块

e.printStackTrace();

@Override

publicvoidset(intx,inty,Integert){

while(x>=length||y>=length){〃扩大容量

getmoreMaxMatrix();

)

element[x][y]=t;

)

@Override

publicIntegerget(intx,inty){

returnelement[x][y];〃数组越界用自带的异常处理机制

)

©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(){〃扩容二倍

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;//通知扩容完毕

)

@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>{〃顺序表用于保存结点的信息

Nodeheade=newNode。;//头部结点

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;〃设置正无穷

protectedListlist=newList。;//存放顶点的顺序表

protectedMatrixedge=newMatrix(2);〃生成矩阵用来表示每个边的权值

©Override

publicintvertexCount。{〃顶点个数

returnlist.length;

)

(©Override

publicNodegetvertex(inti)throwsException{〃返回第i个顶点--越界异常

returnlist.getNode(i);

)

@Ovemde

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

越界异常

list.insert(i,x);

)

@Override

publicintinsertVertex(Nodex){//插入一个顶点x--尾插一返回插入的位置

list.insert(x);

edge.set(list.length-1,list.length-1,null);//通知并判断是否扩容

returnlist.length;

)

@Override

publicvoidremoveVertex(inti)throwsException{〃删除第i个顶点

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{〃广度优先算法

booleanvisted[]=newboolean[this.list.length];〃访问标记数组

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个结点来组成最小生成树

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;

)

)

〃输出一条结果

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

sumweight+=weight;

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

//取消所有通往y结点的边

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("总权值和为:\t"+sumweight);

©Override

publicvoidshortestPath(inti){

@Override

publicvoidshortestPath(){

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

packageseventh;

publicclassEdge{〃边数据存储对象

publicintx=0;

publicinty=0;

publicintweight=0;

)

packageseventh;

publicinterfaceAbstractMatrixvT＞{〃矩阵接口

voidset(intx,inty,Tt);〃设置＜x,y＞处的元素值

Tget(intx,inty);〃获取＜x,y＞处的值

intgetRows();〃返回当前总的行数

intgetColumns();〃返回当前总的列数

intgetLengh();//返回总可用长度(默认为方阵)

voidgetmoreMaxMatrix();〃扩容

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

StringtoString();

)

packageseventh;

publicinterfaceAbstractGraph＜T＞{

intvertexCount。;//返回顶点数

Tgetvertex(inti)throwsException，返回顶点Vi元素

voidsetVertex(inti,Tx)throwsException;〃设置顶点Vi元素为x

intinsertVertex(Tx);〃插入顶点x

voidremoveVertex(inti)throwsException;//册!]除顶点Vi及其临边

voidinsertEdge(inti,intj,intweight);//插入边vVi,Vj＞,权值为weight

voidremoveEdge(inti,intj);〃册!j除边vVi,Vj＞

intgetweight(inti,intj);〃返回vVi,Vj＞的权值

voidDFSTraverse(inti)throwsException;〃以Vi为顶点进行深度优先遍历

voidBFSTraverse(inti)throwsException;〃广度优先遍历

voidminSpanTree。;//求最小生成树

voidshortestPath(inti);〃求带权图顶点Vi的单源最短路径

voidshortestPath。;//求带权图的每对顶点的最短路径以及长度

intnext(inti,intj,boolean口visted);//返回Vi在Vj后的后继邻接顶点序号

)

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("测试矩阵的插入删除和自动扩容功能”);

matrix.toStringO;

matrix.delect(3,3);

matrix.toString();

}catch(Exceptione){

//TODO自动生成的catch块

e.printStackTrace();

)

try(

Sy