Node.h
#ifndef NODE_H
#define NODE_H
class Node
{
public:
int data;//数据域
Node* next;//指针域 指向下一个节点
void printNode();
};
#endif //NODE_F
Node.cpp
#include "Node.h"
#include <iostream>
using namespace std;
void Node::printNode()
{
cout << data << endl;
}
LinkList.h
#ifndef LINKLIST_H
#define LINKLIST_H
#include "Node.h"
#include <iostream>
using namespace std;
//单向链表
//数据域 指针域（指向下一个节点）
//循环链表
//双向链表
//静态链表
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 //LINKLIST_H
LinkList.cpp
#include "LinkList.h"
List::List()
{
m_pList = new Node;//new运算符在堆中申请内存
m_pList->data = 0;
m_pList->next = NULL;
m_iLength = 0;
}
void List::ClearList()
{
Node *currentNode = m_pList->next;
while (currentNode != NULL)
{
Node *temp = currentNode->next;
delete currentNode;
currentNode = temp;
}
m_pList->next = NULL;
}
List::~List()
{
ClearList();
delete m_pList;
m_pList = NULL;
}
bool List::ListEmpty()
{
if (m_iLength == 0)
return true;
else
return false;
}
int List::ListLength()
{
return m_iLength;
}
bool List::ListInsertHead(Node *pNode)
{
Node *temp=m_pList->next; //保留头节点
Node *newNode = new Node; //为传入数据的存储开辟空间
if (newNode == NULL)
return false;
newNode->data = pNode->data;//赋值
m_pList->next = newNode;
newNode->next = temp;
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 == NULL)
return false;
newNode->data = pNode->data;
newNode->next = NULL;
currentNode->next = newNode; //newNode更新为整个链表的尾节点
m_iLength ++;
return true;
}
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 == NULL)
return false;
newNode->data = pNode->data;
newNode->next = currentNode->next;
currentNode->next = newNode; // 插入;
}
bool List::ListDelete(int i, Node *pNode)
{
if (i<0 || i>=m_iLength)
return false;
Node* currentNode = m_pList;
Node* currentNodeBefore = NULL;
for (int k = 0; k <= i; k++)
{
currentNodeBefore = currentNode;
currentNode = currentNode->next;
}
currentNodeBefore->next = currentNode->next;
pNode->data = currentNode->data;
delete currentNode;
currentNode = NULL;
m_iLength--;
return true;
}
bool List::GetElem(int i, Node *pNode)
{
if (i<0 || i >= m_iLength)
return false;
//找到第i个节点
Node* currentNode = m_pList;
Node* currentNodeBefore = NULL;
for (int k = 0; k <= i; k++)
{
currentNodeBefore = currentNode;
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;//没找到与pNode相同的数据域
}
bool List::PriorElem(Node *pCurrentNode, Node *pPreNode)
{
Node *currentNode = m_pList;
Node *tempNode = NULL;
while (currentNode->next != NULL)//遍历尾节点
{
tempNode = currentNode;
currentNode = currentNode->next;
if (currentNode->data == pCurrentNode->data)
{
if (tempNode == m_pList)
{
return false;
}
pPreNode->data = tempNode->data;
return true;
}
}
return false;
}
bool List::NextElem(Node *pCurrentNode, Node *pNextNode)
{
Node *currentNode = m_pList;
while (currentNode->next != NULL)//遍历尾节点
{
currentNode = currentNode->next;
if (currentNode->data == pCurrentNode->data)
{
if (currentNode->next == NULL)
{
return false;
}
pNextNode->data = currentNode->next->data;
return true;
}
}
}
void List::ListTraverse()
{
Node *currentNode = m_pList;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
currentNode->printNode();
}
}
test.cpp
#include "LinkList.h"
#include <stdlib.h>
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;
Node temp;
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(0, &node5); //测试任意位置插入
//pList->ListDelete(0, &temp); //测试删除函数 删除的值放在temp中
//pList->GetElem(1, &temp); //测试获取元素
//pList->PriorElem(&node4, &temp); //测试取元素前驱
pList->NextElem(&node1, &temp);//测试取元素的后继
pList->ListTraverse();
//cout <<"temp="<< temp.data << endl; //测试删除函数 删除的值是放在temp中的
//cout << "temp=" << temp.data << endl; //测试获取元素 获取的元素是放在temp中
//cout << "temp=" << temp.data << endl; //测试取元素前驱 获取的前驱是放在temp中的
cout << "temp=" << temp.data << endl; //测试取元素后继 获取的后继是放在temp中的
delete pList;
pList = NULL;
system("pause");
}
LinkList.png
