链表实现模板(参考用)

拼搏现实的明天。 2022-05-13 11:08 164阅读 0赞

链表想象成火车,火车头看做是链表的表头,车厢里载的人和物就是元素的数据域

连接车厢的不见就是元素指针,由此,链表的特点是:元素之间前后依赖,串联而成

还有,我们可以发现,链表的元素不能随机访问,在火车中行走,只能挨个走过去,而不能直接跳过去

另外,除了火车头,每节车厢前面之连接一节车厢;除了最后的车厢。这也是链表的特点:

元素前面和后面不会出现多个元素相连的情况

1.  找到链表中要插入的位置
2.  令待插入结点的next指针指向插入位置的当前节点
3.  令插入位置之前的当前节点的next指针指向待插入结点

插入需要插入在指定位置之前:

链表的插入分为三个阶段：

1.  头为空:将插入的新元素标志为头(注意index 要等于0)
2.  只有一个头的链表:将新节点放到头后面,同时把新节点标志为头
3.  遍历操作:index表示要插入的位置,也表示插入后新元素所在的位置

首先遍历到要被插入元素的前一个元素,然后使新节点指向原index指点

前一个元素指向新节点

链表的删除操作:

1.  从表头遍历找到要删除的位置
2.  令删除位置前一个节点的next指针指向待删除位置后一个节点
3.  删除节点

翻转链表:

1.  定义一个用于遍历的指针,初始指向头节点后一个节点
2.  让头节点的next指针制空
3.  从当前遍历指针所指的节点开始遍历链表,将遍历到的节点next指针指向头节点。遍历过程中借助另外一个指针保存下一个遍历到的节点
4.  重复步骤3直至表尾,此时新链表就是原链表反转后的链表

#include<iostream>
    using namespace std;
    // 请在下面实现结点类 Node
    //一般涉及到遍历或者删除的操作:一般都要考虑->next
    
    template<typename Type>
    class Node {
    public:
    	Type data;
    	Node<Type>* next;
    	Node(const Type& _data) {
    		data = _data;
    		next = NULL;
    	}
    };
    
    // 请在下面实现链表类 LinkedList
    template<typename Type>
    class LinkedList {
    private:
    	Node<Type>* head;
    public:
    	LinkedList() {
    		head = NULL;
    	}
    	~LinkedList() {
    		Node<Type>* current_node = head;  //遍历指针
    		while (current_node != NULL) {
    			Node<Type>* delete_node = current_node;
    			current_node = current_node->next;
    			delete delete_node;
    		}
    	}
    	//链表的插入
    	void insert(Node<Type>* node, int index);
    	void output();
    	void deleteNode(int index);
    	void reverse();
    };
    
    template<typename Type>
    void LinkedList<Type>::reverse()   //列表的反转操作
    {
    	//链表为空
    	if (head == nullptr)
    		return;
    
    	Node<Type>* current_node = head->next;
    	Node<Type>* temp_node = nullptr; //用于暂存数据
    	head->next = nullptr;   //头节点指针制空
    	while (current_node != nullptr) {
    
    		temp_node = current_node->next;
    		current_node->next = head;
    		head = current_node;
    		current_node = temp_node;
    	}
    }
    
    template<typename Type>
    void LinkedList<Type>::deleteNode(int index)
    {
    	//两种特殊情况的处理
    	//(1)头为空
    	if (head == nullptr) {
    		return;
    	}
    	//(2)删除头节点 index=0;
    	if (index == 0) {
    		Node<Type>* current_node = head;
    		head = head->next;
    		delete current_node;
    	}
    	//(3)正常删除操作
    	Node<Type>* current_node = head;
    	int count = 0;
    
    	//移动到前一个节点
    	while (current_node->next != nullptr && count < index - 1) {
    		current_node = current_node->next;
    		count++;
    	}
    	//删除操作
    	if (count == index - 1 && current_node->next != nullptr) {
    		Node<Type>* delete_node = current_node->next;
    		current_node->next = delete_node->next;
    		delete delete_node;
    	}
    }
    
    //链表的遍历
    template<typename Type>
    void LinkedList<Type>::output()
    {
    	if (head == nullptr) {
    		return;
    	}
    	
    	Node<Type>* current_node = head;
    	while (current_node != nullptr) {
    		cout << current_node->data << " ";
    		current_node = current_node->next;
    	}
    	cout << endl;
    }
    
    template<typename Type>
    void LinkedList<Type>::insert(Node<Type>* node, int index)
    {
    	//情况1 表头为空
    	if (head == nullptr) {
    		if (index != 0)
    			return;
    		head = node;
    		return;
    	}
    	//情况2 只存在一个表头(插入表头)
    	if (index == 0) {
    		node->next = head;   //指向head所指向的元素
    		head = node;
    	}
    	//情况3 插入到中间
    	//从头开始遍历
    	Node<Type>* current_node = head;
    	int count = 0;
    	while (current_node->next != nullptr && count < index - 1) {   //遍历到前一个元素
    		current_node = current_node->next;
    		count++;
    	}
    	if (count == index - 1) {  
    		node->next = current_node->next;
    		current_node->next = node;
    	}
    }
    
    int main() {
    
    	LinkedList<int> linkedlist;
    	for (int i = 1; i <= 10; ++i) {
    		Node<int>* node = new Node<int>(i);
    		linkedlist.insert(node, i - 1);
    	}
    
    	linkedlist.output();
    	linkedlist.deleteNode(3);
    	linkedlist.output();
    	linkedlist.reverse();
    	linkedlist.output();
    
    	system("PAUSE");
    	return 0;
    }