数据结构（二）： 链表篇

#include<iostream>

using namespace std;

class ListNode {
private:
	int value;	//值域
	struct ListNode* next;	//指针域

public:
	ListNode(int value) {
		this->value = value;
		this->next = NULL;
	}

	void add_node(ListNode* next_node) {
		this->next = next_node;
	}

	void set_value(int value) {
		this->value = value;
	}

	int get_value() {
		return this->value;
	}

	ListNode* get_next() {
		return this->next;
	}
	
	//创建结点
	ListNode* creat(int data ){								
		ListNode*p=NULL;
		
		p = new ListNode();
		
		if(NULL == p){
			cout<<"申请内存失败"<<endl;
			exit(-1);
		}
		
		p->value=data;
		p->next=NULL;	//处理干净身后事
		return p;
	}
	
	//新增节点	这里默认头已经有了
	void add(ListNode* the_head,int data )	{
		ListNode* pNode = the_head;
		
		//后面再接上一个
		while (pNode->next != NULL){							//遍历链表，找到最后一个节点
			pNode = pNode->next;
		}
		pNode->next = new ListNode(data);	
	}
	
	//删除节点
	void del(ListNode* the_head, int index){	//删除第index个节点
		ListNode* pFree = NULL;					//用来删除
		
		if(index < 1){
			return;
		}
		
		if(1 == index){
			pFree = the_head;
			head = the_head->next;
			
			free(pFree->pData);				//先释放数据
			free(pFree);					//释放指针
			
			return;
		}
		
		ListNode* pNode = the_head;
		
		while (pNode->next != NULL && index>2){
			pNode = pNode->next;
		}	
		
		pFree = pNode->next;				//再指向数据域就爆了
		pNode->next=pNode->next->next;	//这里要无缝衔接
		free(pFree->pData);				//先释放数据
		free(pFree);					//释放指针
	}
	
	//计算节点数
	int Count(ListNode* the_head){
		int count = 0;
		ListNode*pNode = the_head;
		
		while (pNode != NULL){
			pNode = pNode->next;
			count++;		
		}	
		return count;
	}
	
	//查找固定节点数据
	ListNode* find(ListNode* the_head,int index){

		ListNode* pNode=NULL;
	
		pNode=the_head;
		
		while(pNode != NULL && index){
			pNode = pNode->next;
			index--;		
		}

		if(NULL == pNode){
			cout<<"节点不存在"<<endl;	//可以写日志里
		}
		return pNode;
	}
};

//判断链表成环
bool is_ring(ListNode* a) {
	ListNode* fast = a,*slow = a;
	while (fast->get_next()) {
		fast = fast->get_next();
		if (fast->get_next() && slow->get_next() && fast != slow) {
			fast = fast->get_next();
			slow = slow->get_next();
		}

		if (fast == slow) {
			return true;
		}
	}
	return false;
}

//寻找入环点（默认成环）
int find_ring(ListNode* a) {
	ListNode* fast = a->get_next()->get_next(), * slow = a->get_next();

	while (fast != slow) {
		fast = fast->get_next()->get_next(); 
		slow = slow->get_next();
	}

	ListNode* slow2 = a;

	while (fast != slow2) {
		fast = fast->get_next()->get_next();
		slow2 = slow2->get_next();
	}

	return slow2->get_value();
}


//原地翻转链表
ListNode* reverse_list(ListNode* a) {
	ListNode* temp = new ListNode(0);

	ListNode* h = NULL;

	while(a->get_next()) {
		temp = a;
		a = a->get_next();
		temp->add_node(h); 
		h = temp;
	}
	return temp;
}

template <typename T>
struct __list_node
{
	typedef void* void_pointer;
	void_pointer prev;
	void_pointer neet;
	T date;
}

#include<list>

typedef struct rect
{
	···
}Rect;

list<Rect>test;	//声明一个链表，用于存放结构体数据

//如果想以其他方法初始化list列表，可以移步到下一行那个Vector的介绍

Rect a;
···
test.push_back(a);
test.push_front(a);
//头尾插入（双向链表）

//定点插入
test.insert(test.begin()+10,a);	//在第十个节点之前插入a

//删除test头部的元素
test.erase(test.begin());

//删除test从头到尾的元素
test.erase(test.begin(), test.end());

test.pop_back();
test.pop_front();

//迭代器
list<int>::iterator p；
for (p = test.begin(); p != test.end(); p++)
	cout << *p << " ";

#include<algorithm>
sort(test.begin(),test.end());	//从头到尾，默认从小到大排序

//一般排序都是要自定义排序的：
bool Comp(const int &a,const int &b)
{
    return a>b;
}
sort(test.begin(),test.end(),Comp);	//这样就降序排序。 

test.size();	//容器已存入数据量
test.capacity();	//容器还能存多少数据量

//其实不用担心容器不够大，容量要满的时候它会自己扩容

//去除重复的元素至只保留一个副本
test.unique();
//已经过大小排序的list才能使用

	(2)合并list

test.splice(test.end(),test2);//将test2剪切到test后面

#include<algorithm>
#include<list>