链表排序、链表删除、访问倒数第k个节点

心已赠人 2022-08-02 02:27 119阅读 0赞

1.设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。

2.已知线性表中的元素以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。

3.输出该链表中倒数第k个结点， tail为倒数第0个节点

//
 
 #include "stdafx.h"
 #include<iostream>
 using namespace std;
 template<class T>
 struct Node{
 	T value;
 	Node*next;
 };
 
 template<class T>
 class list
 {
 private:
 	Node<T>*head;
 	Node<T>*tail;
 	int len;//链表长度
 public:
 	list();
 	Node<T>*append(T ele);
 	Node<T>*findKthfromhead(int k);
 	Node<T>*findKthfromtail(int k);
 	Node<T>*sort_list(int endpos);//链表排序
 	Node<T>*delete_list(T x, T y);//删除表中所有大于x且小于y的元素（若表中存在这样的元素）
 	Node<T>*reverse_list();//反转

Node<T>*list<T>::delete_exist();//删除重复元素

int length();
 };
 
 template<class T>
 Node<T>*list<T>::reverse_list()
 {
 	int k1 = length()-1;
 	int k2 = 0;
 	while (k1 - k2 > 0)
 	{
 		int mm;
 		mm = findKthfromhead(k1)->value;
 		findKthfromhead(k1)->value = findKthfromhead(k2)->value;
 		findKthfromhead(k2)->value = mm;
 		--k1;
 		++k2;
 	}
 
 
 	return head;
 }
 template<class T>
 Node<T>*list<T>::delete_list(T x, T y)
 {
 	_ASSERT(y > x);
 	_ASSERT(len > 0);
 
 	sort_list(len - 1);
 	if (head->value >= y || tail->value <= x)
 		return head;
 	if (head->value > x)
 	{
 		Node<T>*m = new Node < T >;
 		while (head->value < y)
 		{
 			Node<T>*node = new Node < T > ;
 			node = head;
 			if (head->next == NULL)
 			{
 				head = NULL;
 				len = 0;
 				return head;
 			}
 			head->value = head->next->value;
 			head = head->next;
 			--len;
 			delete node;
 		}
 		return head;
 	}
 	
 	Node<T>*node = new Node < T >;
 	Node<T>*m = new Node < T >;
 	node = head;
 	while (node->value <= x)
 	{
 		m = node;
 		m->value = node->value;
 		node = node->next;
 	}
 	
 
 	while (node->value < y)
 	{
 		Node<T>*n = new Node < T > ;
 		n = node;
 		if (node->next == NULL)
 		{
 			m->next = NULL;
 			tail = m;
 			--len;
 			return head;
 		}
 		node->value = node->next->value;
 		node = node->next;
 		--len;
 		delete n;
 	}
 	m->next = node;
 
 	return head;
 }
 template<class T>
 Node<T>*list<T>::sort_list(int endpos)//递归实现排序
 {
 	int k = 0;
 	int pp;
 	if (endpos == 0)
 		return head;
 	Node<T>*node = new Node < T >;
 	node = head;
 	while (k < endpos)
 	{
 		if (node->value > node->next->value)
 		{
 			pp = node->value;
 			node->value = node->next->value;
 			node->next->value = pp;
 		}
 		++k;
 		node = node->next;
 	}
 	--endpos;
 	sort_list(endpos);
 	//delete node;
 }
 
 template<class T>
 Node<T>*list<T>::findKthfromhead(int k)
 {
 	//if (len == 0)
 	//	return NULL;
 	_ASSERT(k < len);
 	Node<T>*KthNode = new Node < T > ;
 	KthNode = head;
 	while (k)
 	{
 		KthNode = KthNode->next;
 		--k;
 	}
 
 	return KthNode;
 }
 
 template<class T>
 Node<T>*list<T>::findKthfromtail(int k)
 {
 	_ASSERT(k < len);
 	
 	return findKthfromhead(len-1-k);
 }
 
 template<class T>
 int list<T>::length()
 {
 	return len;
 }
 
 template<class T>
 Node<T>*list<T>::append(T ele)
 {
 	if (head == NULL)
 	{
 		head = new Node < T > ;
 		tail = new Node < T >;
 		head->value = ele;
 		head->next = NULL;
 		tail->value = ele;
 		tail->next = NULL;
 		len = 1;
 		return head;
 	}
 	if (head->next == NULL)
 	{
 		head->next = tail;
 		tail->value = ele;
 		tail->next = NULL;
 		len = 2;
 		return head;
 	}
 	else
 	{
 		Node<T>*node = new Node < T > ;
 		node->next = NULL;
 		node->value = ele;
 		tail->next = node;
 		tail = node;
 		++len;
 		return head;
 	}
 }
 
 template<class T>
 list<T>::list()
 {
 	head = NULL;
 	tail = NULL;
 	len = 0;
 }
 template<class T>
 Node<T>*list<T>::delete_exist()
 {
 	sort_list(len - 1);
 	
 	Node<T>* node,*n,*m;
 
 
 	n=node = head;
 	
 	while (node->next != NULL)
 	{
 		
 		if (node->value == node->next->value)
 		{
 			while (node->next != NULL&&node->value == node->next->value)
 			{
 				m = node;
 				node = node->next;
 
 
 				delete m;
 				--len;
 			}
 			n->next = node;
 			node = node->next;
 			
 		}
 		else
 		{
 			n = node;
 			node = node->next;
 
 
 		}
 	}
 	/*
 	while (node->next != NULL)
 	{
 
 
 		m = n->next;
 		m->value = n->next->value;
 		while (n->value == n->next->value)
 		{
 
 
 			m = n;
 			m->value = n->value;
 			n->value = n->next->value;
 			n = n->next;
 			if (n->next == NULL)
 			{
 				//delete m;  
 				--len;
 				return head;
 			}
 			//delete m;  
 			--len;
 		}
 		node->next = m;
 		node->next->value = m->value;
 
 
 		n = n->next;
 		n->value = n->next->value;
 	}
 	*/
 
 
 	return head;
 
 
 }
 int _tmain(int argc, _TCHAR* argv[])
 {
 	list<int>aa;
 	aa.append(6);
 	cout <<"长度为"<< aa.length() << endl;
 	aa.append(5);
 	cout << "长度为" << aa.length() << endl;
 	aa.append(4);
 	cout << "长度为" << aa.length() << endl;
 	aa.append(3);
 	cout << "长度为" << aa.length() << endl;
 	aa.append(2);
 	cout << "长度为" << aa.length() << endl;
 	cout <<"第三个数为"<< aa.findKthfromhead(3)->value << endl;
 	cout << "倒数第三个数为" << aa.findKthfromtail(3)->value << endl;
 	aa.sort_list(aa.length() - 1);
 	//aa.delete_list(1, 7);
 	aa.delete_list(1, 4);
 	cout << "长度为" << aa.length() << endl;
 	for (int i = 0; i < aa.length(); i++)
 		cout << aa.findKthfromhead(i)->value << endl;
 
 	system("pause");
 	return 0;
 }