![R和Rstudio终端显示语言的更改[Windows]](/aiimages/R%E5%92%8CRstudio%E7%BB%88%E7%AB%AF%E6%98%BE%E7%A4%BA%E8%AF%AD%E8%A8%80%E7%9A%84%E6%9B%B4%E6%94%B9%5BWindows%5D.png)
import java.util.ArrayList
import java.util.Iterator
import my.queue.*
import my.stack.StackX
/**
* 邻接表表示
* @author xiayi
*
*/
public class Graph {
private int MAX_VERTS = 20
private Vertex vertexList[]
private boolean is = false//是否为有向图
private int nVerts = 0
private StackX stackX
private Vertex dfs[]
private Vertex bfs[]
private Queue queue
public Graph(){
vertexList = new Vertex[MAX_VERTS]
dfs = new Vertex[MAX_VERTS]
bfs = new Vertex[MAX_VERTS]
}
public Graph(int n){
vertexList = new Vertex[n]
dfs = new Vertex[n]
bfs = new Vertex[n]
}
public Graph(int n, boolean is){
this.is = is
vertexList = new Vertex[n]
dfs = new Vertex[n]
bfs = new Vertex[n]
}
//////////////////////////////////////////////
public boolean isIs() {
return is
}
public void setIs(boolean is) {
this.is = is
}
public Vertex[] getVertexList() {
return vertexList
}
public Vertex[] getDfs() {
return dfs
}
public Vertex[] getBfs() {
return bfs
}
////////////////////////////////////////////////////
/**
* 添加顶点
*/
public void addVertex(Vertex vertex){
vertex.setIndex(nVerts)
vertexList[nVerts] = vertex
nVerts++
}
/**
* 添加边
*/
public void addEdge(int start, int end){
vertexList[start].addAdj(vertexList[end])
if (!is) {vertexList[end].addAdj(vertexList[start])}
}
/**
* 返回节点个数
* @return
*/
public int getVertsCount(){
return vertexList.length
}
/**
* 深度优先迭代器
* @return
*/
public Iterator dfsIterator(){
dfs()
return new DfsIterator()
}
/**
* 广度优先迭代器
* @return
*/
public Iterator bfsIterator(){
bfs()
return new BfsIterator()
}
////////////////////////////////////////////////////////
public void displayGraph(){
ArrayList<Vertex>next = null
for (int i = 0i <vertexList.lengthi++) {
printVertx(vertexList[i])
}
}
public void printVertx(Vertex vertex){
ArrayList<Vertex>next = vertex.getAdj()
if(next == null){ System.out.println(vertex.toString()+" 无连接点")}
else{
System.out.print(vertex.toString()+"有邻接点:")
for (int i = 0i <next.size()i++) {
System.out.print("顶点"+next.get(i).label+", ")
}
System.out.println()
}
}
///////////////////////////////////////////////////////////
public void dfs(){
stackX = new StackX(MAX_VERTS)
vertexList[0].isVisted = true
dfs[0] = vertexList[0]
stackX.push(vertexList[0])
int dfsIndex = 0
Vertex vertex
while(!stackX.isEmpty()){
vertex = getAdjVertex((Vertex)stackX.peek())
if(vertex == null){
stackX.pop()
}else{
vertex.isVisted = true
dfs[++dfsIndex]=vertex
stackX.push(vertex)
}
}
for (int i = 0i <getVertsCount()i++) {
vertexList[i].isVisted = false
}
}
public void bfs() {
queue = new Queue(MAX_VERTS)
vertexList[0].isVisted = true
bfs[0] = vertexList[0]
queue.insert(vertexList[0])
int bfsIndex = 0
Vertex vertex
while(!queue.isEmpty()){
Vertex vertex2 = (Vertex)queue.remove()
while((vertex = getAdjVertex(vertex2))!=null){
vertex.isVisted = true
bfs[++bfsIndex] = vertex
queue.insert(vertex)
}
}
for (int i = 0i <getVertsCount()i++) {
vertexList[i].isVisted = false
}
}
/**
* 得到一个邻接点
* @param vertex
* @return
*/
public Vertex getAdjVertex(Vertex vertex){
ArrayList<Vertex>adjVertexs = vertex.getAdj()
for (int i = 0i <adjVertexs.size()i++) {
if(!adjVertexs.get(i).isVisted){
return adjVertexs.get(i)
}
}
return null
}
/////////////////////////////////////////////////////////////
private abstract class GraphIterator implements Iterator{
int count = 0
public GraphIterator(){
}
public boolean hasNext() {
return count != getVertsCount()-1
}
public Object next() {
// TODO Auto-generated method stub
return null
}
public void remove() {
// TODO Auto-generated method stub
}
}
//深度优先迭代
private class DfsIterator extends GraphIterator{
public DfsIterator(){
super()
}
public Vertex next() {
return dfs[count++]
}
}
//广度优先迭代
private class BfsIterator extends GraphIterator{
public BfsIterator(){
super()
}
public Object next() {
return bfs[count++]
}
}
/////////////////////////////////////////////////////////
public static void main(String[] args) {
int nVerts = 10
int c = 'A'-1
Vertex vertex
Graph myGraph = new Graph(nVerts, false)
for (int i = 0i <nVertsi++) {
c++
vertex = new Vertex((char)(c))
myGraph.addVertex(vertex)
}
myGraph.addEdge(0, 1)
myGraph.addEdge(0, 4)
myGraph.addEdge(1, 2)
myGraph.addEdge(2, 3)
myGraph.addEdge(4, 5)
myGraph.addEdge(4, 6)
myGraph.addEdge(5, 8)
myGraph.addEdge(6, 7)
myGraph.addEdge(7, 8)
myGraph.addEdge(8, 9)
System.out.println("深度优先迭代遍历：")
for (Iterator iterator = myGraph.dfsIterator()iterator.hasNext()) {
vertex = (Vertex) iterator.next()
System.out.println(vertex.toString())
}
System.out.println("/n广度优先迭代遍历：")
for (Iterator iterator = myGraph.bfsIterator()iterator.hasNext()) {
vertex = (Vertex) iterator.next()
System.out.println(vertex.toString())
}
}
}
class Vertex{
public char label
public boolean isVisted
public int index
private ArrayList<Vertex>next = null
public Vertex(char lab) // constructor
{
label = lab
isVisted = false
}
//为节点添加邻接点
public void addAdj(Vertex ver){
if(next == null) next = new ArrayList<Vertex>()
next.add(ver)
}
public ArrayList<Vertex>getAdj(){
return next
}
public void setIndex(int index){
this.index = index
}
public String toString(){
return "顶点 "+label+",下标："+index+"."
}
}
代码来自：http://blog.csdn.net/Java2King/article/details/5683429
如何使邻接表的结构定义更加清晰。(java版)用邻接表实现无向图的创建出现的问题是关于内部类的使用，如何使邻接表的结构定义更加清晰，不分散。
在邻接表中，对图中每个顶点V建立一个单链表，把与V相邻接的顶点放在这个链表中。
给你一个邻接表的完整程序：#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个结点（不含头结点）的之后
void Insertlist(int a,int b)//将节点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)
{
cout<<current->data<<" "
current=current->next
}
cout<<endl
}
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)//在链表中查找数值为x的结点，成功返回1，否则返回0
{
node *p=head
while(p!=NULL&&p->data!=x)
p=p->next
if(p->data==x)
return 1
else
return 0
}
void list::Insert (int x,int i)//将x插入到第i个结点（不含头结点）的之后；
{
node *p//p中放第i个结点
node *q//q中放i后的结点
node *h//h中存要插入的结点
h=new node
h->data =x
p=head
if(p->next !=NULL) //链表不是只有一个结点或者空链表时候
{
int n=1
while(p->next !=NULL)
{
n++
p=p->next
}// 得到链表的结点的个数
p=head//使p重新等于链首
if(i==n)//i=n时，直接加在最后面就行了
{
while(p->next !=NULL)
p=p->next
p->next=h
h->next =NULL
}
else if(i<n&&i>1)//先找到第i个结点，用p存第i个结点，用q存i后的结点，用h存要插入的结点
{
for(int j=1j<ij++)
p=p->next//找到第i个结点，用p存第i个结点
q=p->next//q存i后的结点
p->next=h
h->next=q
}
else
cout<<"超出链表结点个数的范围"<<endl
}
else
cout<<"这个链表是空链表或者结点位置在首位"<<endl
}
void list::Insertlist(int a,int b)//将b插入到结点为a之前
{
node *p,*q,*s//p所指向的结点为a,s所指为要插入的数b,q所指向的是a前的结点
s=new node
s->data=b
p=head
if(head==NULL)//空链表的时候
{
head=s
s->next=NULL
}
else
if(p->data==a)//a在链首时候
{
s->next=p
head=s
}
else
{
while(p->data!=a&&p->next!=NULL)//使p指向结点a,q指向a之前的结点
{
q=p
p=p->next
}
if(p->data==a)//若有结点a时候
{
q->next=s
s->next=p
}
else//没有a的时候
{
p->next=s
s->next=NULL
}
}
}
int list::Delete(int x)//删除链表中值为x的结点，成功返回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!=x&&p->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
}//得到链表结点的个数
p=head
if(i==n)//i结点在结尾的时候
{
while(p->next!=NULL)
{
q=p
p=p->next
}
q->next=NULL
delete p
return 1
}
else if(i<n&&i>1)//i结点在中间的时候
{
for(int j=1j<ij++)
{
q=p//q中放i前的结点
p=p->next //p中放第i个结点
}
q->next=p->next
delete p
return 1
}
else if(i==1)//i结点在首位的时候
{
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=1i<10i++)
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<<"请输入你想要进行的操作（选择对应操作前面的序号）："<<endl
cin>>m
}while(m<1||m>6)//当输入的序号不在包括中，让他重新输入
switch(m)
{
case 1:
{
A.Display ()
goto menu
}break
case 2:
{
cout<<"请输入你想要找到的结点："<<endl
int c
cin>>c//输入你想要找到的结点
if(A.Find (c)==1)
{
cout<<"可以找到"<<c<<endl
A.Display ()//重新显示出链表A
}
else
{
cout<<"链表中不存在"<<c<<endl
A.Display ()//重新显示出链表A
}
goto menu
}break
case 3:
{
cout<<"请选择你要插入的方式(选择前面的序号进行选择）"<<endl
cout<<"1.将特定的结点加入到特定的结点前"<<'\t'<<"2.将特定的结点加到特定的位置后"<<endl
int b1
do
{
cout<<"请输入你想要插入的方式（选择前面的序号进行选择）："<<endl
cin>>b1
}while(b1<1||b1>2)//当输入的序号不在包括中，让他重新输入
if(b1==1)
{
cout<<"请输入你想要插入的数和想要插入的结点（为此结点之前插入）："<<endl
int a1,a2
cin>>a1>>a2
A.Insertlist (a1,a2)//将a1插入到结点为a2结点之前
cout<<"此时链表为："<<endl
A.Display ()//重新显示出链表A
}
else
{
cout<<"请输入你想要插入的数和想要插入的位置（为此结点之后插入）："<<endl
int a1,a2
cin>>a1>>a2
A.Insert (a1,a2)//将a1插入到结点位置为a2的结点之后
cout<<"此时链表为："<<endl
A.Display ()//重新显示出链表A
}
goto menu
}break
case 4:
{
cout<<"请选择你要删除的方式(选择前面的序号进行选择）"<<endl
cout<<"1.删除特定的结点"<<'\t'<<"2.删除特定位置的结点"<<endl
int b1
do
{
cout<<"请输入你想要插入的方式（选择前面的序号进行选择）："<<endl
cin>>b1
}while(b1<1||b1>2)//当输入的序号不在包括中，让他重新输入
if(b1==1)
{
cout<<"请输入你想要删除的结点："<<endl
int a
cin>>a//输入你想要删除的结点
if(A.Delete (a)==1)
{
cout<<"成功删除"<<a<<endl
cout<<"删除后的链表为："<<endl
A.Display ()
}
else
{
cout<<"此链表为："<<endl
A.Display ()//重新显示出链表A
cout<<"链表中不存在"<<a<<endl
}
}
else
{
cout<<"请输入你想要删除的结点位置："<<endl
int b
cin>>b//输入你想要删除的结点的位置
if(A.Remove(b)==1)
{
cout<<"成功删除第"<<b<<"个结点"<<endl
cout<<"删除后的链表为："<<endl
A.Display ()//重新显示出链表A
}
else
{
cout<<"当前链表的结点个数为："<<A.Length ()<<endl
cout<<"您输入的结点位置越界"<<endl
}
}
goto menu
}break
case 5:
{
cout<<"这个链表的结点数为:"<<A.Length ()<<endl
goto menu
}break
case 6:
{
A.MakeEmpty ()
cout<<"这个链表已经被置空"<<endl
goto menu
}break
}
}
评论(3)|1
sunnyfulin |六级采纳率46%
擅长：C/C++JAVA相关Windows数据结构及算法百度其它产品
按默认排序|按时间排序
其他1条回答
2012-04-23 17:41121446881|六级
我写了一个C语言的，只给你两个结构体和一个初始化函数：
#include "stdio.h"
#include "malloc.h"
struct adjacentnext//邻接表项结构体
{
int element
int quanvalue
struct adjacentnext *next
}
struct adjacenthead//邻接表头结构体
{
char flag
int curvalue
int element
struct adjacenthead *previous
struct adjacentnext *son
}
//初始化图，用邻接表实现
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=0i<mapsizei++)
{
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)//输入源结点，目的结点，以及源结点到目的结点的路权值
while(x!=0&&y!=0)//x,y至少有一个零就结束
{
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//返回邻接表头
}
