cpp1.cpp

无线与网络、寻找节点之间的最短距离

#include<iostream>
using namespace std;
#define N 7
#define M 8

struct node					//队列中的节点
{
	int data;
	node *next;
};
struct  point				//链表中的节点
{
	int data;
	int length;
	point * next;
};
	

class list
{
private:
	node *head;
	node *rear;
public:
	list(){head=NULL;rear=NULL;}
	int ifempty(void);			//判断队空
	void inlist(int n);			//入队
	int outlist(void);			//出队	
};



int list::ifempty(void)            	//判断队空
{
	return (head==NULL);    
}

void list::inlist(int n)        //入队
{
	node *p=new node;
	p->data=n;
	p->next=NULL;
	if (rear==NULL) rear=head=p;
	else rear->next=p;
	rear=p;
}

int list::outlist(void)               //出队
{
	if (ifempty())                    //如果队空      
	{
		cout<<"empty!"<<endl;
		exit(0);
	}
	else                          //队不空就出队
	{
		node *t=head->next;	
		int d=head->data;
		delete head;
		head=t;
		if(head==NULL) rear=NULL;
		return d;
	}
}

void insert (int t1 , int t2, int t3, point *l[])        //插入链表的函数
{
	
	int i=0;
	point *p=l[t1],*q=NULL;
	while(p!=NULL) 
	{
		q=p;
		p=p->next;
	}
	point *pp=new point;          //建立一个新结点
	pp->data=t2;
	pp->length=t3;
	pp->next=NULL;
	if (q==NULL) l[t1]=pp;	       //连接上去
	else q->next=pp;
}



void main()

{
	point *l[N];					//各单名链表的头指针组成的数组
	int target;						//目标结点
	list s;					//优先搜索处理队列

	cout<<"请输入目标结点号";
	cin>>target;
	while (target>=N) 
	{
		cout<<"错误，目标不存在,重新输入";
		cin>>target;
	}
	int i;                    	//循环变量
	int e[N];                      //存储到目标的最短长度
	for (i=0;i<N;i++)	
	{
		l[i]=NULL;
		e[i]=10000;
	}
	e[target]=0;
					
	int t1,t2,t3;                //临时存储三元组中的三个变量
	cout<<"输入"<<M<<"个三元组"<<endl;
	for (i=0;i<M;i++)					//建立邻接表
	{
		cin>>t1>>t2>>t3;
		insert(t1,t2,t3,l);
		insert(t2,t1,t3,l);
	}

	int temp;
	point *tempadd;

	s.inlist(target);           //目标入队
	while(!s.ifempty())			
	{
		temp=s.outlist();               //出队
		tempadd=l[temp];
		while(tempadd!=NULL)	//所有的邻接点都要处理
		{
			if(tempadd->length+e[temp]<e[tempadd->data])  //如果找到了更短的路线
			{
				e[tempadd->data]=tempadd->length+e[temp];  //更新
				s.inlist(tempadd->data);		//入队
			}
			tempadd=tempadd->next;			//指向下一个邻接点
		}

	}

	cout<<"目标"<<target<<"到所有结点的最短距离分别是"<<endl;
	for (i=0;i<N;i++)
	{
		if (e[i]==10000) cout<<"到"<<i<<"没有可以到达的路径"<<endl;
		else if (i!=target) cout<<"到"<<i<<"的最短路径长度是"<<e[i]<<endl;
	}

}