headlist.cpp

这是一个数据结构课程的关于带表头节点问题的的源代码

#include "Headlist.h"

Listnode::Listnode(int value):data(value),link(NULL){}

Listnode *Listnode::getnode(int value,Listnode *next=NULL)
{
	Listnode *newnode=new Listnode(value);
	newnode->link=next;
	return newnode;
}

List::List(int value)
{
	first=last=new Listnode(value);
}

Listnode *List::locate(int i)
{
	int m=0;
	Listnode *p=first->link;
	if(i<-1) return NULL;//输入不合理，返回NULL
	if(i==-1) return first;//查找的是表头节点
	else//其他情况
	{
		for(;m<i&&p!=NULL;m++)//逐一查找定位
		{
			p=p->link;
		}
	}
	return p;
}

Listnode *List::maxnode()
{
	Listnode *p=first->link,*q=p;//定义新结点p，q为链表的第一个结点，并默认该结点为最大值结点
	while(p!=NULL&&p->link!=NULL)//遍历链表
	{
		if(p->link->data>q->data) q=p->link;//若存在值比原默认最大值q->data大的结点，则将q重新定义为该结点的值
		p=p->link;
	}
	return q;//返回最大值结点
}

int List::number(int value)
{
	int count=0;//计数变量count
	Listnode *p=first->link;//从链表的第一个元素开始查找
	while(p!=NULL)
	{
		if(p->data==value) count++;//若有相同元素，则count++
		p=p->link;
	}
	return count;
}

int List::insert(int value,int i)//将值为value的元素插入到链表的第i个位置
{
	Listnode *p=locate(i-1);//先定位至第i-1个元素
	if(p==NULL) return 0;
	Listnode *newnode=p->getnode(value,p->link);//将新节点插入到第i-1各元素之后
	if(newnode->link==NULL) last=newnode;//若第i-1个元素为原链表的最后一个元素，则last=newnode
	p->link=newnode;
	return 1;
}

void List::create(int n,int *a)
{
	for(int i=0;i<n;i++) insert(a[i],i);//将数组元素逐个插入
}

void List::tidyup(int value)//清除链表中值为value的元素
{
	Listnode *p=first;
	while(p!=NULL&&p->link!=NULL)
	{
		if(p->link->data==value)//找到值为value的结点
		{
			Listnode *q=p->link;//定义临时结点q为该结点
			p->link=q->link;//重新建立连接关系
			if(p->link==NULL) last=p;
			delete q;//删除该结点
		}
		else p=p->link;
	}
}

ostream &operator<<(ostream &output,const List &l)
{
	Listnode *p=l.first->link;
	while(p!=NULL)
	{
		output<<p->data<<" ";
		p=p->link;
	}
	return output;
}