[C++知识库]C++链表(无头链表有问题版)

/*
/*
1.C++的链表连接过程是由构造函数完成的
2.成员访问要注意访问权限
*/
#include<iostream>
#include<string>
using namespace std;

//描述数据的长相  类似C语言链表中的1 这个数据
struct Data  //数据域data描述
{
	//数据由两部分组成的 一个是key 一个是data
	const int key;
	string data;
	//key的初始化必须采用初始化参数列表
	Data(int key, string name) :key(key), data(name)  {}//构造函数 data必须初始化为name才能打印输入测值
};


//描述节点的长相
class Node //创建节点(data+next)
{
public:
	Node(int key, string data) :nodeData(key, data)//类的组合必须要调用组合类的构造函数 对象加参数，参数的数目是由对象的构造函数的决定，也就是构造几个参数，他也要几个参数
	{
		next = nullptr;//指针先赋值为空 创建新节点
	}
	Node(Data data) :nodeData(data), next(nullptr) {}
	Node(int key, string data, Node* next) :nodeData(key, data)//Node* next为节点 用来做链表的连接 Data类的对象必须要用初始化参数列表 Node自己里面的对象可以不用 
	{
		this->next = next;
	}
	Data getNodedata()//提供一个公有接口去访问数据 返回一个节点中的数据
	{
		return nodeData;
	}

	Node*& getNext() //返回节点中的指针
	{
		return next;
	}
protected:
	Data nodeData;			//类的组合: 以另一个类的对象为数据成员 。必须采用初始化参数列表的方式
	Node* next;
}; 

//描述所有链表的特性
class List
{
public:
	List()//创建节点
	{
		headNode = nullptr;//该headNode为头节点的位置 先指向空
		size = 0; 
	}

	//头节点插入
	void insertByHead(int key, string data)
	{
		headNode = new Node(key, data, headNode); //表头插入由构造函数完成
		//newNode->next = headNode; 错误，指针不可以访问
		size++;
	}

	//表尾插入
	void insertByTail(int key, string data)
	{
		if(size==0)
			headNode = new Node(key, data, headNode);
		else 
		{
			Node* pmove = headNode;
			while (pmove->getNext() != nullptr) 
			{
				pmove = pmove->getNext();
				//pmove=pmove->next;
			}
			Node* newNode = new Node(key, data);
			pmove->getNext() = newNode;
		}
		size++;
	}

	//指定节点插入
	void  insertByAppoin(Data xdata, int posKey)  //Data xdata 是Data这个结构体创建的变量，int posKey 是要插入节点的下一个节点
	{
		Node* upNode = headNode->getNext();
		Node* downNode = headNode;
		while (upNode != nullptr && upNode->getNodedata().key != posKey)//getNodedata().key != posKey 通过节点的数据做对比来比较
		{
			downNode = upNode->getNext();
			upNode = downNode->getNext();
		}
		if (upNode != nullptr)
		{
			//Node* newNode = new Node(xdata.key, xdata.data);
			Node* newNode = new Node(xdata);
			downNode->getNext() = newNode;
			newNode->getNext() = upNode;
			size++;
		}
		else
		{
			cout << "插入失败，节点不存在！" << endl;
		}
	}

	/*删除*/
	//头节点删除
	void headdelete(List* list)
	{
		
		Node* newNode = headNode->getNext();
		if (newNode!= nullptr)
		{
			cout << endl;
			cout << "头节点删除" << endl;
			headNode->getNext() = newNode->getNext();
			delete(newNode);
			newNode = nullptr;
			size--;
		}
		else
		{
			cout << "节点不存在，无法删除！" << endl;
		}
	}

	//尾节点删除
	void weidelete(List* list)
	{
		Node* updelete = headNode;
		Node* downdelete = nullptr;
		while (updelete->getNext() != nullptr)
		{
			downdelete = updelete;
			updelete = downdelete->getNext();
		}
		if (updelete != nullptr)
		{
			cout << endl;
			cout << "尾节点删除" << endl;
			downdelete->getNext() = nullptr;
			delete(updelete);
			updelete = nullptr;
		}
		else
		{
			cout << "节点没有找到，无法删除" << endl;
		}
	}

//指定节点删除
	void autodelete(List* list, int posdata)
	{
		Node* updelete = headNode->getNext();
		Node* downdelete = headNode;
		while (updelete != nullptr && updelete->getNodedata().key != posdata)
		{
			downdelete = updelete;
			updelete = downdelete->getNext();
		}
		if (updelete!=nullptr)
		{
			cout << endl;
			cout << "指定位置删除" << endl;
			downdelete->getNext()=updelete->getNext() ;
			delete(updelete);
			updelete = nullptr;
		}
		else
		{
			cout << "指定的节点不存在，无法删除节点！" << endl;
		}
	}


	void printList()
	{
		Node* pmove = headNode;
		while (pmove != NULL)
		{
			cout << pmove->getNodedata().key <<"\t"<<pmove->getNodedata().data<<"\t";
			pmove=pmove->getNext();//指针往下走，不能够直接pmove = pmove->next 因为类外无法直接访问的 必须以函数放回值的方式
		}
		cout << endl;
	}
protected://在这里增加要实现功能的模块
	Node* headNode;
	int size = 0;//万金油参数
};
//class MM 
//{
//public:
//	//MM(string name, int age) 
//	//{
//	//	this->name = name;
//	//	this->age = age;
//	//}
//	MM(string name, int age) :age(age), name(name) //等效于上面的程序
//	{
//
//	}
//protected:
//	string name;
//	int age;
//};



int main()
{
	List* plist = new List; 
	//Data info[]{ { 1,"初七" }, { 2,"小康" }, { 3,"小翠" }, {4,"4"} };
	//for (int i = 0; i < 4; i++)
	//{
	//	plist->insertByHead(info[i].key,info[i].data);
	//}

	Data info = { 1,"小翠" };
	plist->insertByHead(info.key, info.data);//因为是采用初始化参数列表的方式，所以要使用剥洋葱的方式把数据传到函数中去
	Data Iloveyou = { 520,"我爱你" };
	plist->insertByHead(Iloveyou.key, Iloveyou.data);
	plist->printList();

	Data xiaokang = { 2,"小康" };
	plist->insertByTail(xiaokang.key, xiaokang.data);
	/*Data xiaokan = { 3,"小康" };
	plist->insertByTail(xiaokan.key, xiaokan.data);*/
	plist->printList();

	Data moying = { 3,"初七" };
	plist->insertByAppoin(moying, 1);//当插入的节点为1时，程序会崩掉
	plist->printList();

	//头节点删除
	plist->headdelete(plist);
	plist->printList();

	//尾节点删除
	plist->weidelete(plist);
	plist->printList();

	//指定删除节点

	plist->autodelete(plist, 1);
	plist->printList();

	return 0;
}
}