hello.cpp

用c++实现链表的源程序

#include <iostream.h>

class List;		//声明类List
class Item		//定义类Item
{
public:
	friend class List;	//List类作为Item类的友元类
private:
	Item(int d=0) { data = d; next=0; }		//注意成员函数Item可以设置参数的缺省值。
											//值为0的指针为空指针。
	Item * next;
	int data;
};

class List
{
public:
	List() { list = 0; }
	List(int d) { list = new Item(d); }
	int print();
	int insert(int d = 0);
	int append(int d = 0);
	void cat(List &il);
	void reverse();
	int length();
private:
	Item * end();		//返回值为Item型指针的函数
	Item * list;
};

////////////类的各成员函数的实现///////////
int List::print()
{
	if(list==0)
	{
		cout<<"Empty\n";
		return 0;
	}
	cout<<"(";
	int cnt = 0;
	Item * pt = list;
	while(pt)
	{
		if(++cnt%40==1&&cnt!=1)
			cout<<endl;
		cout<<pt->data<<" ";
		pt=pt->next;
	}
	cout<<")\n";
	return cnt;
}

//对一个空表插入链项项
int List::insert(int d)
{
	Item * pt = new Item(d);
	pt->next = list;
	list = pt;
	return d;
}

//对一个空链表追加链表项
int List::append(int d)
{
	Item * pt = new Item(d);
	if (list==0)
		list = pt;
	else
		(end())->next = pt;
	return d;
}

Item * List::end()
{
	Item * prv, * pt;
	for(prv=pt=list; pt; prv=pt, pt=pt->next)
		;
	return prv;
}

//连接链表
void List::cat(List & il)
{
	Item * pt = il.list;
	while(pt)
	{
		append(pt->data);
		pt = pt->next;
	}
}

//将一个链表的各链表的各链表项逆向输出
void List::reverse()
{
	Item *pt, *prv, *tmp;
	prv = 0;
	pt = list;
	list = end();
	while(pt!=list)
	{
		tmp=pt->next;
		pt->next = prv;
		prv = pt;
		pt = tmp;
	}
	list->next=prv;
}

//求得一个链表的数据项数
int List::length()
{
	int cnt = 0;
	Item * pt = list;
	for(; pt; pt=pt->next, cnt++)
		;
	return cnt;
}

///////////main主程序//////////////
void main()
{	
	List list1;
	list1.print();
	for(int i=10; i<18; i++)
		list1.insert(i);
	cout<<"list1:";
	list1.print();
	List list2;
	for(i=15; i<20; i++)
		list2.append(i);
	cout<<"list2:";
	list2.print();
	cout<<"list length:"<<list1.length()<<endl;
	list2.cat(list1);
	cout<<"list2:";
	list2.reverse();
	cout<<"list2:";
	list2.print();
	cout<<"list2 length:"<<list2.length()<<endl;
}