linklist.cpp

模拟动态存储管理 一、 题目 编制一个模拟动态存储管理的程序

//程序：LINKLIST.CPP
//功能：提供链表类LINKLIST的实现

#include”LINKLIST.HPP”

LINKLIST::LINKLIST()
{top=NULL;
bottom=NULL;
num=0;
}

LINKLIST::~LINKLIST()
{NODE* temp;
 while(top!=NULL)
 {temp=top;
 top=top->next;
 delete temp;
 }
}

int LINKLIST::is_empty()
{ return (top==NULL);
}

NODE* LINKLIST::get_top()
{return top;
}

NODE* LINKLIST::get_bottom()
{return bottom;
}

unsigned long LINKLIST::get_num()
{return num;
}

NODE* LINKLIST::insert(NODE* insertor)
{NODE* temp;   temp=top;
NODE* pre=NULL;
if(is_empty())     //链空时的处理
{top=insertor;  insertor->next=NULL;  bottom=insertor; 
}  else{                               //在链中查找对应的节点
	while((temp!=NULL)&&((insertor->element1)>(temp->element1))) 
//这里用到短路求值，否则会产生/指针指向的空间不可访问的错误
	{pre=temp;
	temp=temp->next;
	}
	if(pre==NULL&&temp!=NULL)            //在链头插入节点
	{insertor->next=top; top=insertor;
	} else if(pre!=NULL&&temp==NULL)       //在链尾插入节点
	{pre->next=insertor;  insertor->next=NULL;
	bottom=insertor;
	} else                                  //在链中间插入节点
	{pre->next=insertor;  insertor->next=temp;
	}
      }
num++;
return pre;
}    

NODE* LINKLIST::del(ELEMENT ad)
{NODE* temp;   temp=top;
 NODE* pre=NULL;
if(is_empty()){
  cout<<"\nThe link is NULL!"; return NULL;}
else{                                          //在链中查找对应的节点
    while((temp!=NULL)&&(ad!=temp->element1))  //判断条件时用到短路求值，否则会产生空指针指向的空间不可访问的错误
	{pre=temp;
	temp=temp->next;
	}
	if (temp==NULL){                         //找不到对应的节点
	cout<<"\nAddress not been found!"; return NULL;
	} else{
	if(temp==top)                            //删除链头
	{top=top->next;
	} else if(temp==bottom)                    //删除链尾
	{pre->next=NULL;  bottom=pre;
	} else{                                  //删除链中对应的节点
	pre->next=temp->next;
	}
        num--;
	return temp;
	}
}
}

void LINKLIST::print()    // print the list
{ NODE* p;       p=top;
  cout<<"\nThe list is:\n";
  if ( top==NULL )  cout<<"The list is NULL!\n";
  else  do
	{ cout<<setw(10)<<p->element1<<"\t"<<p->element2<<"\n";
	  p=p->next;
	} while( p!=NULL );
}        // print end.

NODE* LINKLIST::combine(NODE* left, NODE* right){
if(left!=NULL&&right!=NULL&&(left->element1+left->element2==right->element1))
{left->element2+=right->element2;
left->next=right->next;
delete right;
num--;
return left;
} else return right; 
}