频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
C++进阶学习——单向链表的实现
2015-11-08 10:01:55         来源:秋叶原 — Mike VS 麦克  
收藏   我要投稿

示例代码如下:

 

#include 
using namespace std;

class Node //节点类
{
public:
	//普通构造函数:无参数,带1个参数,带2个参数
	Node(){}
	Node(int n){ num = n; next = NULL; }
	Node(int n, Node *p){ num = n; next = p; }
	
	void setNum(int n = 0) { num = n; }
	int getNum() const { return num; }
	
	void setNext(Node *p = NULL){ next = p; } //设置指针域
	Node *getNext() const { return next; }//获取指针域
	
private:
	int num;    //数据域
	Node *next; //指针域
};

class Linklist //链表类
{
public:
	//构造函数和析构函数
	Linklist(){ head = NULL; }
	Linklist(int n){ head = new Node(n); }
	~Linklist() { clear(); }
	
	void addAtEnd(int n);//往链表尾添加节点
	void addAtHead(int n);//往链表头添加节点
	void addByNum(int n);//升序插入节点
	
	void visitAllNode() const;//遍历所有的节点
	Node *searchByNum(int n) const; //查找值为num的节点
	
	void deleteByNum(int n);//删除值为n的节点
	void clear();//删除链表所有节点
	
private:
	Node *head;
};

//往链表尾添加节点
void Linklist::addAtEnd(int n)  
{
	if(NULL == head)
	{ 
		head = new Node(n);
	}
	else
	{
		Node *temp=head;
		while( temp->getNext() != NULL)
		{ 
			temp = temp->getNext(); //用temp来指向下一个节点
		}
		//执行到这时,说明temp是最后一个节点,temp的下一个节点为NULL
		
		temp->setNext( new Node(n) );//插入节点
	}
 
}

//往链表头添加节点
void Linklist::addAtHead(int n) 
{
	if(NULL == head)
	{ 
		head = new Node(n);
	}
	else
	{
		Node *temp = new Node(n);//待插入的节点
		temp->setNext(head);//temp的下一个节点执行头
		head = temp; //新节点当做头结点
	}
 
}

//升序插入节点
void Linklist::addByNum(int n)
{
	if(NULL == head)//头结点为NULL
	{
		head = new Node(n);
	}
	else
	{
		Node *pf, *pb; //pf前一个结点, pb为后一个节点
		pf = pb = head;
		while(NULL != pb)
		{
			if(pb->getNum() >= n)//>=升序,<降序
			{
				break;
			}
			pf = pb; //pf保存当前节点
			pb = pb->getNext(); //pb指向下一个节点
		}
		
		if(NULL == pb)//尾结点
		{
			pf->setNext( new Node(n) );//插入节点
		}
		else
		{
			Node *temp = new Node(n);//待插入的节点
			
			if(pb == head) //头节点
			{
				temp->setNext(head);//temp的下一个节点执行头
				head = temp; //新节点当做头结点
			}
			else //中间
			{
				pf->setNext(temp);
				temp->setNext(pb);
			}
			
		}
			
	}
}

//遍历所有的节点
void Linklist::visitAllNode() const
{
	if(NULL == head)
	{
		cout<<空链表!<getNum()<< --> ;
			temp=temp->getNext();
		}
		cout << NULL << endl;
	}
}

//查找值为num的节点
Node * Linklist::searchByNum(int n) const
{
	Node *temp = head;
	while(temp != NULL)
	{
		if(temp->getNum() == n)
		{
			return temp;
		}
		
		temp = temp->getNext();
	}
	
	return NULL;
}

//删除节点
void Linklist::deleteByNum(int n) 
{
	Node *pf, *pb;
	pf = pb = head;
	
	while(NULL != pb)
	{
		if(pb->getNum() == n)
		{
			break;
		}
		pf = pb;
		pb = pb->getNext();
	}
	
	if(NULL == pb)
	{
		cout << n << :此值不存在 << endl;
	}
	else
	{
		//头结点
		if(pb == head)
		{
			pf = head->getNext();
			delete head;
			head = pf;
		}
		else
		{
			pf->setNext( pb->getNext() );
			delete pb;
		}
	}	
}

//删除链表所有节点
void Linklist::clear()
{
	Node *temp = NULL;
	temp = head; //用一个临时节点保存头结点

    //遍历链表,每次先保存头结点的next结点,然后删除头结点
    while (NULL != temp)
    {
        temp = head->getNext();//先保存头结点的next结点
        delete head;//删除头结点
		head = temp;//之前头结点的next节点重新作为head
    }
	
	cout << 链表已经清空
;
}

int main()
{
	Linklist myList(1); //创建链表对象
	
	myList.visitAllNode(); //遍历所有的节点
	
	cout << endl;
	
	myList.addAtEnd(2); //尾部插入
	myList.addAtHead(0);//头部插入
	myList.visitAllNode(); //遍历所有的节点
	
	cout << endl;
	
	for(int i = 3; i < 10; i++)
	{
		myList.addByNum(i); //升序插入节点
	}
	myList.visitAllNode(); //遍历所有的节点
	
	cout << endl;
	
	Node *temp = myList.searchByNum(5); //查找值为5的节点
	if(NULL != temp)
	{
		cout << 此节点的值为: << temp->getNum() << endl;
	}
	else
	{
		cout << 值为5的节点不存在 << endl;
	}
	
	temp = myList.searchByNum(100); //查找值为100的节点
	if(NULL != temp)
	{
		cout << 此节点的值为: << temp->getNum() << endl;
	}
	else
	{
		cout << 值为100的节点不存在 << endl;
	}
	
	cout << endl;
	
	myList.deleteByNum(5);//删除值为5的节点
	cout << 删除值为5的节点:;
	myList.visitAllNode(); //遍历所有的节点
	
	cout << endl;
	myList.deleteByNum(100);//删除值为100的节点
	
	cout << endl;
	
	return 0;
}

编译运行结果如下:

 

/

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 进阶 C++ 单向
上一篇:[LeetCode] Valid Parentheses
下一篇:[LeetCode] Move Zeroes
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站