sy1.cpp

关于学校的一个最短路径查询小系统

// sy1.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "iostream.h"
#include "stdlib.h"
#include <math.h>
#define TRUE	1
#define FALSE	0
#define	OK		1
#define	ERROR	0
#define	N		26
typedef	char	ElemType;
typedef	int		Status;
typedef	struct	LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

Status InitList_L(LinkList &L){				//构建一个空的链表L
	L=(LinkList)malloc(sizeof(LNode));		//为L动态开辟一个空间
	if(!L)	return OVERFLOW;
	L->next=NULL;							//L的指针域为空
	return OK;
}

Status GetElem(LinkList &L,int i,ElemType &e){			//获取链表第i个结点的元素
	LinkList p;
    p=L->next;                     //初始化,p指向第一个结点  
    int j=1;                       // j为计数器 
    while(p && j<i)
    {
	p=p->next;
	++j;
    }
    if(!p||j>i) return ERROR;            //i大于表长或小于1
    e=p->data;                           //取第i个元素
    return OK; 
}


void ShowElem_L(LinkList &L)        //显示函数
{
   LinkList p;
   int i;
   ElemType e;
   p=L->next;
   i=0;
   if(p==NULL)cout<<endl<<"\t\t\t表中没有元素"<<endl;        //空表
   else
      while(p)											//遍历单链表
	  {           
            i++;
            e=p->data;
            cout<<e<<"  ";                              //输出表中的元素
            p=p->next;               
	  } 
	  cout<<endl;
}


Status  ListLength_L(LinkList L){			//返回L中数据元素个数
    LinkList p;
    p=L->next;         //p指向第一个结点
     int i=0;             
     while(p){           //遍历单链表,统计结点数
           i++;
           p=p->next;   
    } 
    return i;                             
 }



Status ListInsert_L(LinkList &L,int i,ElemType e){		//在链表的第i个位置之前插入字母
	LinkList p,s;
	p=L;
	int j=0;
	while(p&&j<i-1){									//寻找第i个结点
	p=p->next;
	++j;}
	if(!p||j>i-1)	return OVERFLOW;					//i小于1或者大于表长
	s=(LinkList)malloc(sizeof(LNode));					//生成1个新结点
	s->data=e;								//将欲插入的字母放到新结点的数值域
	s->next=p->next;							//将新接的结点的指针域指向原链表第i+1个结点
	p->next=s;								//将链表的第i-1个结点的指针域指向s
	return OK;
}


Status ListDelete_L(LinkList &L,int i,ElemType e)		                //删除链表的第i个结点
{	
        LinkList p,q;
	p=L;
	int j=0;
	while(p&&j<i-1){							//寻找第i个结点
	p=p->next;
	++j;}
	if(!p||j>i-1)	return OVERFLOW;					//i小于1或者大于表长
	q=p->next;							        //用q表示即将删除的结点
	e=q->data;							        //用e存储结点q中的数值
	p->next=q->next;
	free(q);
	return OK;
}


Status LocateELem(LinkList L, ElemType e) {
  LinkList p,q;
  int i=0;
  p=L->next;
  q=L;
  while(p &&p->data!=e) 
  {
   p=p->next;								//寻找满足条件的结点
   q=q->next;
   i++;
  }
	if(p==NULL&&q->data!=e)					//链表中不存在要查找的元素	
		 return (-1);						
	else  return(i);						//返回L中值为e的数据元素的结点位置
}


void Sorted(LinkList &L)					//将链表中的元素进行排序
{	
        int i,j;
	LinkList p,q;
	q=p=L->next;
	char a[50],c;							//定义一个数组，用来对链表的数据排序
	for(i=0;i<ListLength_L(L)&&p;i++)		
	{
         a[i]=p->data;
	 p=p->next;						
	}
	for(j=0;j<ListLength_L(L);j++)			//把链表的值赋给数组，由数组实现交换和排序
		for(i=0;i<ListLength_L(L)-1;i++)
			if((int)a[i]>(int)a[i+1])
			{
                            c=a[i];
			    a[i]=a[i+1];
			    a[i+1]=c;
			}
	free(p);					//释放指针p所占据的空间
	cout<<endl;
	for(i=0;i<ListLength_L(L);i++)			//重新将数组的值赋给链表
	{
            q->data=a[i];
	    q=q->next;
	}
	ShowElem_L(L);
}



void Insert(LinkList &L)
{
	ElemType c;
	int i;
	cout<<"\t\t\t请输入元素"<<endl;
	cin>>c;
	cout<<"\t\t\t请输入您想插入的位置"<<endl;
	cin>>i;
	ListInsert_L(L,i,c);
	ShowElem_L(L);
}


void Delete(LinkList &L)
{
	ElemType c;
	cout<<"\t\t\t请输入要删除的元素"<<endl;
	cin>>c;
	cout<<endl;
	int i=LocateELem(L,c)+1;					        //选择要删除的元素的位置
	if(i==0)	cout<<"\t\t"<<"对不起，没有该数据"<<endl<<endl;		//如果选择的字母不在链表中提示信息

	else {ListDelete_L(L,i,c);
		  ShowElem_L(L);
		 }
}



void Searching(LinkList &L)
{
	ElemType c;
	int i;
	cout<<"要查找第几个位置上的元素"<<endl;
	cin>>i;
	GetElem(L,i,c);
	cout<<"第"<<i<<"个位置上的元素是"<<c<<endl;
	cout<<endl;
}



void CreatList(LinkList &L)                                       //建立带表头结点的单链表L
{			
	LinkList p,q;
	char c,a;
	int i=0;
	q=L;
	cout<<endl<<endl<<"\t请首先输入字母："<<endl;
	do{
	cout<<"请输入："<<endl;
	p=(LinkList)malloc(sizeof(LNode));				//生成新结点
	q->next=p;										//原指针指向添加元素
	cin>>a;											//输入元素值
	if((a>='A'&&a<='Z')||(a>='a'&&a<='z'))			//if条件语句限制输入链表的为字母
		{p->data=a;
		 q=q->next;
		 p->next=NULL;								//新结点的指针域为空
		 cout<<"\t继续输入?(Y/N)";
		 cin>>c;
		 if(c=='y'||c=='Y')		i++;
		 else	i=0;
		 cout<<endl;
	}
	else{									//如果输入的不是字母，输出提示信息
	cout<<"\t\t\t输入错误！请输入字母！"<<endl;
	i++;
	}
	}while(i);
	ShowElem_L(L);
}



int main(int argc, char* argv[])
{
	LinkList l;									//定义一个结点
	InitList_L(l);									//初始化结点
	int	a,i;			
	char c;
	CreatList(l);
	cout<<endl<<"\t\t\t\t请选择操作:"<<endl;
	cout<<"\t\t\t1.正确排序"<<endl;
	cout<<"\t\t\t2.插入元素"<<endl;
	cout<<"\t\t\t3.删除元素"<<endl;
	cout<<"\t\t\t4.查找字母"<<endl;
	cout<<"\t\t\t5.查看链表长度"<<endl;
	cout<<"\t\t\t0.退出程序"<<endl;
	do{
		cout<<"\t\t\t请输入操作："<<endl;
		cin>>a;
		switch(a){													//调用switch语句对操作进行选择
				case 1:Sorted(l);
						break;
				case 2:Insert(l);
						break;
				case 3:Delete(l);
						break;
				case 4:Searching(l);
						break;
				case 5: cout<<"\t\t\t链表的长度为:";
						cout<<ListLength_L(l)<<endl;
						break;
				case 0:exit(0);
				default:cout<<"\t\t\t\t输入错误！"<<endl;			//出错处理
						exit(0);
				}
		cout<<"\t\t\t还想继续吗?(Y/N)"<<endl;
		cin>>c;
		if(c=='Y'||c=='y')	i=1;
		else				i=0;
	   }while(i);
	return 0;
}