oset.cpp

迷宫程序,C++实现 一个用VC写的关于迷宫的程序

//OSet.cpp
#include<iostream.h>
#include<stdlib.h>
#include"OSet.h"

void InitList(LNode* &HL)
{
	HL=NULL;
}

void ClearList(LNode* &HL)
{
	LNode *cp, *np;
	cp=HL;
	while(cp!=NULL)
	{
		np=cp->next;
		delete cp;
		cp=np;
	}
	HL=NULL;
}

int ListSize(LNode* HL)
{
	LNode *p=HL;
	int i=0;
	while(p)
	{
		i++;
		p=p->next;
	}
	return i;
}

bool ListEmpty(LNode* HL)
{
	return (HL==NULL);
}

ElemType GetElem(LNode* HL, int pos)
{
	if(pos<1)
	{
		cout<<"pos is out range!"<<endl;
		exit(1);
	}
	LNode *p=HL;
	int i=0;
	while(p)
	{
		i++;
		if(i==pos) break;
		p=p->next;
	}
	if(p!=NULL)
		return p->data;
	else
	{
		cout<<"pos is out range!"<<endl;
		exit(1);
	}
}

bool FindList(LNode* HL, ElemType &item)
{
	LNode *p=HL;
	while(p)
	{
		if(p->data==item) return true;
		else p=p->next;
	}
	return false;
}

void InsertList(LNode* &HL, const ElemType &item, int mark)
{
	LNode *newptr;
	newptr=new LNode;
	newptr->data=item;

	if(mark>0)  //向表头插入结点
	{
		newptr->next=HL; HL=newptr;
	}
    else if(mark<0)  //向表尾插入结点
	{
		if(HL==NULL) { newptr->next=NULL; HL=newptr; }  //改为HL=NULL试试,运行时出错.
		else
		{
			LNode *p=HL;
			while(p->next) p=p->next;
			p->next=newptr; newptr->next=NULL;
		}
	}
	else  //插入到合适位置
	{
		LNode *cp, *ap;
		ap=NULL; cp=HL;
		while(cp)
		{
			if(item< cp->data) break;
			else { ap=cp; cp=cp->next; }
		}
		if(ap==NULL) { newptr->next=HL; HL=newptr; }
		else { newptr->next=cp; ap->next=newptr; }
	}
}

bool DeleteList(LNode* &HL, ElemType &item, int mark)
{
	if(HL) return false;
	//删除表头结点
	if(mark>0)
	{
		LNode *p=HL;
		item=HL->data;
		HL=HL->next;
		delete p;
		return true;
	}
	//删除表尾结点
	else if(mark<0)
	{
		LNode *cp=HL, *ap=NULL;
		while(cp->next!=NULL)
		{
			ap=cp; cp=cp->next;
		}
		if(ap==NULL) HL=NULL;
		else ap->next=cp->next;
		item=cp->data;
		delete cp;
		return true;
	}
	//删除值为item的结点
	else
	{
		LNode *cp=HL, *ap=NULL;
		while(cp)
			if(cp->data==item) break;
			else { ap=cp; cp=cp->next; }
		if(cp==NULL) return false;
		else
		{
			if(ap) HL=HL->next; 
			else ap->next=cp->next;
			item=cp->data;
			delete cp;
			return true;
		}
	}
}

void TraverseList(LNode* HL)
{
	LNode *p=HL;
	cout<<"{ ";
	while(p)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<"}"<<endl;
}


void CreateSet(OrderedSet* &Set)
{
	InitList(Set);
	ElemType ch;
	cout<<"请输入字符(输入#结束):";
	while(1)
	{
		cin>>ch;
		if(ch=='#') break;
		else if(int(ch)>=97 && int(ch)<=122)
		{
			if(!FindList(Set,ch))
				InsertList(Set,ch,0);
		}
	}
}

void Union(OrderedSet* &Set3, OrderedSet* Set1, OrderedSet* Set2)
{
	InitList(Set3);
	LNode *p1=Set1, *p2=Set2, *p=NULL;
	while(p1 && p2)
	{
		if(p1->data == p2->data)
		{
			InsertList(Set3,p1->data,-1);
			p1=p1->next; p2=p2->next;
		}
		else if(p1->data < p2->data)
		{
			InsertList(Set3,p1->data,-1);
			p1=p1->next;
		}
		else
		{
			InsertList(Set3,p2->data,-1);
			p2=p2->next;
		}
	}
	p=p1?p1:p2;
	while(p)
	{
		InsertList(Set3,p->data,-1);
		p=p->next;
	}
}

void Intersection(OrderedSet* &Set3, OrderedSet* Set1, OrderedSet* Set2)
{
	InitList(Set3);
	LNode *p1=Set1, *p2=Set2;
	while(p1 && p2)
	{
		if(p1->data == p2->data) 
		{
			InsertList(Set3,p1->data,-1);
		    p1=p1->next; p2=p2->next;
		}
		else if(p1->data < p2->data) p1=p1->next;
		else p2=p2->next;
	}
}

void Difference(OrderedSet* &Set3, OrderedSet* Set1, OrderedSet* Set2)  //Set1-Set2.
{
	InitList(Set3);
	LNode *p1=Set1, *p2=Set2;
	while(p1 && p2)
	{
		if(p1->data < p2->data) 
		{
			InsertList(Set3,p1->data,-1);
			p1=p1->next;
		}
		else if(p1->data > p2->data) p2=p2->next;
		else{ p1=p1->next; p2=p2->next; }
	}
	if(p1)
		while(p1)
		{
			InsertList(Set3,p1->data,-1);
			p1=p1->next;
		}
}

//End.