线性表链表实现

桃扇骨 2022-04-24 03:36 243阅读 0赞

### 线性表链表实现 ###

list.h

#ifndef LIST_H_
    #define LIST_H_
    #include "Node.h"
    class List
    {
    public:
    	List();
    	~List();
    	void ClearList();
    	bool ListEmpty();
    	int ListLength();
    	bool GetElem(int i, Node *pNode);
    	int LocateElem(Node *pNode);
    	bool PriorElem(Node *pCurrentNode, Node *pPreNode);
    	bool NextElem(Node *pCurrentNode, Node *pNextNode);
    	void ListTraverse();
    	bool ListInsert(int i, Node *pNode);
    	bool ListDelete(int i, Node *pNode);
    	bool ListInsertHead(Node *pNode);
    	bool ListInsertTail(Node *pNode);
    private:
    	Node *m_pList;
    	int m_iLength;
    };
    
    
    #endif // !LIST_H_

list.cpp

#include "List.h"
    #include "Node.h"
    #include <iostream>
    using namespace std;
    List::List()
    {
    	m_pList = new Node;
    	m_pList->data = 0;
    	m_pList->next = nullptr;
    	m_iLength = 0;
    }
    
    List::~List()
    {
    	ClearList();
    	delete m_pList;
    	m_pList = nullptr;
    }
    
    void List::ClearList()
    {
    	Node *currentNode = m_pList->next;
    	while (currentNode != nullptr) {
    		Node *temp = currentNode->next;
    		delete currentNode;
    		currentNode = temp;
    	}
    	m_pList->next = nullptr;
    	m_iLength = 0;
    }
    
    bool List::ListEmpty()
    {
    	return m_iLength == 0 ? true : false;
    }
    
    int List::ListLength()
    {
    	return m_iLength;
    }
    
    bool List::GetElem(int i, Node * pNode)
    {
    	if (i < 0 || i >= m_iLength)
    	{
    		return false;
    	}
    	Node *currentNode = m_pList;
    	for (int k = 0; k <= i; k++)
    	{
    		currentNode = currentNode->next;
    	}
    	pNode->data = currentNode->data;
    	return true;
    }
    
    int List::LocateElem(Node * pNode)
    {
    	Node *currentNode = m_pList;
    	int count = 0;
    	while (currentNode->next != NULL)
    	{
    		currentNode = currentNode->next;
    		if (currentNode->data == pNode->data)
    		{
    			return count;
    		}
    		count++;
    	}
    	return -1;
    }
    
    bool List::PriorElem(Node * pCurrentNode, Node * pPreNode)
    {
    	Node *currentNode = m_pList;
    	Node *tempNode = nullptr;
    	while (currentNode->next != NULL)
    	{
    		tempNode = currentNode;
    		currentNode = currentNode->next;
    		if (currentNode->data == pCurrentNode->data)
    		{
    			if (tempNode==m_pList)
    			{
    				return false;//如果前驱是头结点，则返回false
    			}
    			pPreNode->data = tempNode->data;
    		}
    	}
    	return false;
    }
    
    bool List::NextElem(Node * pCurrentNode, Node * pNextNode)
    {
    	Node *tempNode = m_pList;
    	while (tempNode->next != NULL)
    	{
    		tempNode = tempNode->next;  //从第一个结点开始，递增
    		if (tempNode->data == pCurrentNode->data)
    		{
    			if (tempNode->next == NULL) //判断该结点是不是最后一个结点
    			{
    				return false;
    			}
    			pNextNode->data = tempNode->next->data;
    		}
    	}
    	return false;
    }
    
    void List::ListTraverse()
    {
    	Node *currentNode = m_pList;
    	while (currentNode->next != NULL)
    	{
    		currentNode = currentNode->next;
    		currentNode->printNode();
    	}
    }
    
    bool List::ListInsert(int i, Node * pNode)
    {
    	if (i < 0||i>m_iLength)
    	{
    		return false;
    	}
    	Node*currentNode = m_pList;
    	for (int k = 0; k < i; k++)
    	{
    		currentNode = currentNode->next;
    	}
    	Node *newNode = new Node;
    	if (!newNode)
    	{
    		return false;
    	}
    	newNode->data = pNode->data;
    	newNode->next = currentNode->next;
    	currentNode->next = newNode;
    	m_iLength++;
    	return true;
    }
    
    bool List::ListDelete(int i, Node * pNode)
    {
    	if (i < 0||i>=m_iLength)
    	{
    		return false;
    	}
    	Node *currentNode = m_pList;
    	Node *currentNodeBefore = nullptr;  //存储上一个节点
    	for (int k = 0; k <= i; k++)
    	{
    		currentNodeBefore = currentNode;
    		currentNode = currentNode->next;
    	}
    	currentNodeBefore->next = currentNode->next;
    	pNode->data = currentNode->data;
    	delete currentNode;
    	currentNode = nullptr;
    	m_iLength--;
    	return true;
    }
    
    bool List::ListInsertHead(Node * pNode)
    {
    	Node *newNode = new Node;
    	if (!newNode)
    	{
    		return false;
    	}
    	newNode->data = pNode->data;
    	newNode->next = m_pList->next;
    	m_pList->next = newNode;
    	m_iLength++;
    	return true;
    }
    
    bool List::ListInsertTail(Node * pNode)
    {
    	Node* currentNode = m_pList;
    	while (currentNode->next != NULL)
    	{
    		currentNode = currentNode->next;
    	}
    	Node *newNode = new Node;
    	if (!newNode)
    	{
    		return false;
    	}
    	currentNode->next = newNode;
    	newNode->data = pNode->data;
    	newNode->next = nullptr;
    	m_iLength++;
    	return true;
    }

Node.h

#ifndef NODE_H_
    #define NODE_H_
    class Node
    {
    public:
    	int data;   //数据域
    	Node *next;  //指向下一个结点
    	void printNode();
    };
    
    #endif // !NODE_H_
    #pragma once

Node.cpp

#include "Node.h"
    #include <iostream>
    using namespace std;
    void Node::printNode()
    {
    	cout << data << endl;
    }

demo.cpp

#include <stdlib.h>
    #include <iostream>
    #include "List.h"
    #include "Node.h"
    using namespace std;
    /*
    线性表 单链表
    	List();  //创建链表
    	~List();  //销毁链表
    	void ClearList();  //清空链表
    	bool ListEmpty();  //判空
    	int ListLength();  //返回链表长度
    	bool GetElem(int i, Node *pNode);  //获取指定位置结点
    	int LocateElem(Node *pNode);  //定位结点
    	bool PriorElem(Node *pCurrentNode, Node *pPreNode); //获取前一个结点
    	bool NextElem(Node *pCurrentNode, Node *pNextNode);  //获取后一个结点
    	void ListTraverse(); //遍历链表
    	bool ListInsert(int i, Node *pNode);  //插入结点
    	bool ListDelete(int i, Node *pNode);  //删除结点
    	bool ListInsertHead(Node *pNode); //头结点插入结点 
    	bool ListInsertTail(Node *pNode);  //尾结点插入结点
    */
    int main() {
    	Node node1;
    	node1.data = 3;
    
    	Node node2;
    	node2.data = 4;
    
    	Node node3;
    	node3.data = 5;
    
    	Node node4;
    	node4.data = 6;
    
    	Node node5;
    	node5.data = 7;
    
    	List *pList = new List();
    	//pList->ListInsertHead(&node1);
    	//pList->ListInsertHead(&node2);
    	//pList->ListInsertHead(&node3);
    	//pList->ListInsertHead(&node4);
    	pList->ListInsertTail(&node1);
    	pList->ListInsertTail(&node2);
    	pList->ListInsertTail(&node3);
    	pList->ListInsertTail(&node4);
    
    	pList->ListInsert(1, &node5);
    
    	Node temp;
    	//pList->ListDelete(1, &temp);
    	//pList->GetElem(0, &temp);
    	//pList->PriorElem(&node5, &temp);
    	pList->NextElem(&node5, &temp);
    
    	pList->ListTraverse();
    
    	cout << "temp data:" << temp.data << endl;
    
    
    	delete pList;
    	pList = NULL;
    	system("pause");
    	return 0;
    }