学步园

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指列表中的下一个结点；

#pragma once

//实现单向链表
class Onewayslinklist
{
public:
	Onewayslinklist(void);
	Onewayslinklist(int value);
	Onewayslinklist(int intarr[], int length);
	Onewayslinklist(Onewayslinklist* linklist);
	~Onewayslinklist(void);
public:
	//单向链表的两个属性
	//具体的元素，在此用整形数表示，
	int m_value;
	//另外一个就是指向下一个数据的指针
	Onewayslinklist* m_pnext;
public:	
	void output();
	void destroy();
	void inserthead(int value);
	void inserttail(int value);
	void insertorder(int value);
	bool remove(int value);
	bool find(int value, Onewayslinklist** pnode);
	int  getsize();
	bool isempty();
};

#include "stdafx.h"
#include "Onewayslinklist.h"


Onewayslinklist::Onewayslinklist(void)
{
	m_value = 0xFFFFFFFF;
	m_pnext = NULL;
}

Onewayslinklist::Onewayslinklist(int value)
{
	m_value = value;
	m_pnext = NULL;
}

Onewayslinklist::Onewayslinklist(int intarr[], int length)
{
	m_pnext = NULL;
	m_value = 0xFFFFFFFF;
	for(int i=0; i<length; i++)
	{
		insertorder(intarr[i]);
	}
}

Onewayslinklist::Onewayslinklist(Onewayslinklist* linklist)
{
	m_pnext = NULL;
	m_value = 0xFFFFFFFF;

	Onewayslinklist* pafter = linklist;
	while(pafter->m_pnext != NULL)
	{
		insertorder(pafter->m_pnext->m_value);
		pafter = pafter->m_pnext;
	}
}

Onewayslinklist::~Onewayslinklist(void)
{
	printf("destroy value=%d self=%08x next=%08x\n", m_value, this, this->m_pnext);
}

void Onewayslinklist::output()
{
	Onewayslinklist* ptemp = this;
	while(ptemp->m_pnext != NULL)
	{
		printf("value=%d self=%08x next=%08x\n", ptemp->m_value, ptemp, ptemp->m_pnext);
		ptemp = ptemp->m_pnext;
	}
	printf("value=%d self=%08x next=%08x\n", ptemp->m_value, ptemp, ptemp->m_pnext);
}

void Onewayslinklist::destroy()
{
}


//在单向链表的头部插入元素
void Onewayslinklist::inserthead(int value)
{
	Onewayslinklist* node = new Onewayslinklist(value);
	Onewayslinklist* temp = m_pnext;
	m_pnext = node;
	if (temp != NULL)//只有头元素的时候，不需要执行这句话
	{
		node->m_pnext = temp;
	}
}

//在单向链表的尾部插入元素
void Onewayslinklist::inserttail(int value)
{
	Onewayslinklist* node = new Onewayslinklist(value);
	Onewayslinklist* ptemp = this;
	while(ptemp->m_pnext != NULL)
	{
		ptemp = ptemp->m_pnext;
	}
	ptemp->m_pnext = node;
}

//在单向链表中按照从小到大的顺寻插入
void Onewayslinklist::insertorder(int value)
{
	Onewayslinklist* node = new Onewayslinklist(value);
	Onewayslinklist* ptemp = this;
	while(ptemp->m_pnext != NULL)
	{
		if (value <= ptemp->m_pnext->m_value)
		{
			break;
		}
		ptemp = ptemp->m_pnext;
	}
	Onewayslinklist* oldnext = ptemp->m_pnext;
	ptemp->m_pnext = node;
	node->m_pnext = oldnext;
}


bool Onewayslinklist::remove(int value)
{
	bool find = false;
	Onewayslinklist* ptemp = this;
	while(ptemp->m_pnext != NULL)
	{
		if (value == ptemp->m_pnext->m_value)
		{
			find = true;
			break;
		}
		ptemp = ptemp->m_pnext;
	}

	if (find)
	{
		Onewayslinklist* oldnext = ptemp->m_pnext;
		if (oldnext != NULL)
		{
			ptemp->m_pnext = oldnext->m_pnext;
		}
		delete oldnext;
	}
	return find;
}

bool Onewayslinklist::find(int value, Onewayslinklist** pnode)
{
	bool find = false;
	Onewayslinklist* ptemp = this;
	while(ptemp->m_pnext != NULL)
	{
		if (value == ptemp->m_pnext->m_value)
		{
			find = true;
			break;
		}
		ptemp = ptemp->m_pnext;
	}

	if (find)
	{
		*pnode = ptemp->m_pnext;
	}
	return find;
}

int  Onewayslinklist::getsize()
{
	int count = 0;
	Onewayslinklist* ptemp = this;
	while(ptemp->m_pnext != NULL)
	{
		count++;
		ptemp = ptemp->m_pnext;
	}
	return count;
}

bool Onewayslinklist::isempty()
{
	bool result = false;
	if (m_pnext == NULL)
	{
		result = true;
	}
	return result;
}

主函数测试：

// linklist.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Onewayslinklist.h"
#include "Twowayslinklist.h"

int _tmain(int argc, _TCHAR* argv[])
{
	Onewayslinklist list;
	
	//在单向链表的尾部插入测试
	/*for(int i=0; i<10; i++)
	{
		list.inserttail(i);
	}
	list.output();*/


	//在单向链表的头部插入测试
	/*for(int i=0; i<10; i++)
	{
		list.inserthead(i);
	}
	list.output();*/


	//在单向链表顺序插入元素
	/*list.insertorder(9);
	list.insertorder(8);
	list.insertorder(7);
	list.insertorder(6);
	list.insertorder(10);
	list.output();

	//删除一个不存在的元素
	Onewayslinklist *node = NULL;
	if (list.find(9, &node))
	{
		printf("find value=%d\n", node->m_value);
	}
	
	list.output();
	printf("count=%d\n", list.getsize());*/
	

	int valuearr[10];
	for(int i=0; i<10; i++)
	{
		valuearr[i] = i * 10;
	}
	Onewayslinklist list1(valuearr, 10);
	list1.output();

	Onewayslinklist list2(list1);
	list2.output();


	getchar();
	return 0;
}