link.h

这是用c++制作的一个家电管理系统

// 链表操作的头文件
//作者  陆玥玥  学号06010811
#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
struct LNode
{
	ElemType data;
	LNode * next;
};
//初始化单链表
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!=NULL)
	{
		i++;
		p=p->next;
	}
	return i;
}
//检查单链表是否为空
int ListEmpty(LNode*HL)
{
	return(HL==NULL);
}
//得到单链表中第pos个节点中的元素
ElemType GetElem(LNode*HL,int pos)
{
	if(pos<1)
	{
		cerr<<"pos is out of range"<<endl;
		exit(1);
	}
	LNode*p=HL;
	int i=0;
	while(p!=NULL)
	{
		i++;
		if(i==pos)
			break;
		p=p->next;
	}
	if(p!=NULL)
		return p->data;
	else
	{
		cerr<<"pos is out of range!"<<endl;
		exit(1);
	}
}
//遍历一个单链表
void TraverseList(LNode*&HL)
{
	LNode *p=HL;
	while(p!=NULL)
	{
		cout<<p->data<<endl;
		p=p->next;
	}
}
//从单链表中查找具有给定值的第一个元素
 int Find(LNode*HL,ElemType&item)
 {
	 LNode *p=HL;
	 while(p!=NULL)
		 if(p->data==item)
		 {
			 item=p->data;
			 return 1;
		 }
		 else
			 p=p->next;
		 return 0;
 }
 //更新单链表中具有给定值的第一个元素
 int Update(LNode *&HL,const ElemType &item)
 {
	 LNode *p=HL;
	 while(p!=NULL)
		 if(p->data==item)
			 break;
		 else
			 p=p->next;
		 if(p==NULL)
			 return 0;
		 else
		 {
			 p->data=item;
			 return 1;
		 }
 }
 //向单链表末尾添加一个元素
 void InsertRear(LNode *&HL,const ElemType&item)
 {
	 LNode *newptr;
	 newptr=new LNode;
	 if(newptr==NULL)
	 {
		 cerr<<"Memory allocation failare!"<<endl;
		 exit(1);
	 }
	 newptr->data=item;
	 newptr->next=NULL;
	 if(HL==NULL)
		 HL=newptr;
	 else
	 {
		 LNode *p=HL;
		 while(p->next!=NULL)
			 p=p->next;
		 p->next=newptr;
	 }
 }
 //向单链表的表头插入一个元素
 void InsertFront(LNode *&HL,const ElemType &item)
 {
	 LNode *newptr;
	 newptr=new LNode;
	 if(newptr==NULL)
	 {
		 cerr<<"Memory allocation failare!"<<endl;
		 exit(1);
	 }
	 newptr->data=item;
	 newptr->next=HL;
	 HL=newptr;
 }
 //向单链表中满足条件的位置插入一个元素
 void Insert(LNode *&HL,const ElemType &item)
 {
	 LNode *newptr;
	 newptr=new LNode;
	 if(newptr==NULL)
	 {
		 cerr<<"memory allocation failare!"<<endl;
		 exit(1);
	 }
	 newptr->data=item;
	 LNode *cp;
	 LNode *ap;
	 ap=NULL;
	 cp=HL;
	 while(cp!=NULL)
		 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;
		 }
 }
 //从单链表中删除表头元素
 ElemType DeleteFront(LNode *&HL)
 {
	 if(HL==NULL)
	 {
		 cerr<<"Deleting from an empty list!"<<endl;
		 exit(1);
	 }
	 LNode *p=HL;
	 HL=HL->next;
	 ElemType temp=p->data;
	 delete p;
	 return temp;
 }
 //从单链表中删除等于给定值的第一个元素
 int Delete(LNode *&HL,const ElemType &item)
 {
	 if(HL==NULL)
	 {
		 cerr<<"HL is NULL!"<<endl;
		 return 0;
	 }
	 LNode *ap;
	 LNode *cp;
	 ap=NULL;
	 cp=HL;
	 while(cp!=NULL)
		 if(cp->data==item)
			 break;
		 else
		 {
			 ap=cp;
			 cp=cp->next;
		 }
		 if(cp==NULL)
		 {
			 cerr<<"Deleted element is not exist!"<<endl;
			 return 0;
		 }
		 if(ap==NULL)
			 HL=HL->next;
		 else
			 ap->next=cp->next;
		 delete cp;
		 return 1;
 }
 //利用单链表进行数据排序
 void LinkSort(ElemType a[],int n)
 {
	 LNode *head=NULL;
	 int i;
	 for(i=0;i<n;i++)
		 Insert(head,a[i]);
	 LNode *p=head;
	 i=0;
	 while(p!=NULL)
	 {
		 a[i++]=p->data;
		 p=p->next;
	 }
	 ClearList(head);
 }
 //有序单链表的插入
 void InsertOrder(LNode * &HL,ElemType x)
 {
	 LNode *p,*q,*s;
	 s=new LNode;
	 if(s==NULL)
	 {
		 cerr<<"memory allocation failed!"<<endl;
		 exit(1);
	 }
	 s->data=x;
	 s->next=NULL;
	 p=HL;
	 if(p==NULL||x.value>p->data.value)
	 {
		 s->next=p;
		 HL=s;
	 }
	 else
	 {
		 q=p->next;
		 while(q!=NULL&&x.value<p->data.value)
		 {
			 p=q;
			 q=q->next;
		 }
		 s->next=q;
		 p->next=s;
	 }
 }
//将一个单链表重新链成有序电链表
void OrderSort(LNode * &HL)
 {
	 LNode *p=HL;
	 HL=NULL;
	 while(p!=NULL)
	 {
		 LNode *q=p;
		 p=p->next;
		 LNode *ap=NULL,*cp=HL;
		 while(cp!=NULL)
		 {
			 if(q->data.value<cp->data.value)
				 break;
			 else
			 {
				 ap=cp;
				 cp=cp->next;
			 }
		 }
		 q->next=cp;
		 if(ap==NULL)
			 HL=q;
		 else
			 ap->next=q;
	 }
 }