Node.h
#ifndef NODE_H
#define NODE_H
class Node
{
public:
int data;//數(shù)據(jù)域
Node* next;//指針域 指向下一個(gè)節(jié)點(diǎn)
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;
//單向鏈表
//數(shù)據(jù)域 指針域（指向下一個(gè)節(jié)點(diǎn)）
//循環(huán)鏈表
//雙向鏈表
//靜態(tài)鏈表
class List
{
public:
List();//構(gòu)造函數(shù)
~List();
void ClearList();
bool ListEmpty();
int ListLength();
bool GetElem(int i, Node *pNode); //獲取指定的元素
int LocateElem(Node *pNode); //獲取指定元素的位置
bool PriorElem(Node *pCurrentNode, Node *pPreNode);//獲取元素的前驅(qū)
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運(yùn)算符在堆中申請(qǐng)內(nèi)存
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; //保留頭節(jié)點(diǎn)
Node *newNode = new Node; //為傳入數(shù)據(jù)的存儲(chǔ)開辟空間
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)//遍歷尾節(jié)點(diǎn)
{
currentNode = currentNode->next;
}
Node *newNode = new Node;
if (newNode == NULL)
return false;
newNode->data = pNode->data;
newNode->next = NULL;
currentNode->next = newNode; //newNode更新為整個(gè)鏈表的尾節(jié)點(diǎn)
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個(gè)節(jié)點(diǎn)
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)//遍歷尾節(jié)點(diǎn)
{
currentNode = currentNode->next;
if (currentNode->data == pNode->data)
{
return count;
}
count++;
}
return -1;//沒找到與pNode相同的數(shù)據(jù)域
}
bool List::PriorElem(Node *pCurrentNode, Node *pPreNode)
{
Node *currentNode = m_pList;
Node *tempNode = NULL;
while (currentNode->next != NULL)//遍歷尾節(jié)點(diǎn)
{
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)//遍歷尾節(jié)點(diǎn)
{
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; //調(diào)用默認(rèn)的構(gòu)造函數(shù)
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); //測(cè)試頭插
pList->ListInsertHead(&node2);
pList->ListInsertHead(&node3);
pList->ListInsertHead(&node4);*/
pList->ListInsertTail(&node1); //測(cè)試尾插
pList->ListInsertTail(&node2);
pList->ListInsertTail(&node3);
pList->ListInsertTail(&node4);
//pList->ListInsert(0, &node5); //測(cè)試任意位置插入
//pList->ListDelete(0, &temp); //測(cè)試刪除函數(shù) 刪除的值放在temp中
//pList->GetElem(1, &temp); //測(cè)試獲取元素
//pList->PriorElem(&node4, &temp); //測(cè)試取元素前驅(qū)
pList->NextElem(&node1, &temp);//測(cè)試取元素的后繼
pList->ListTraverse();
//cout <<"temp="<< temp.data << endl; //測(cè)試刪除函數(shù) 刪除的值是放在temp中的
//cout << "temp=" << temp.data << endl; //測(cè)試獲取元素 獲取的元素是放在temp中
//cout << "temp=" << temp.data << endl; //測(cè)試取元素前驅(qū) 獲取的前驅(qū)是放在temp中的
cout << "temp=" << temp.data << endl; //測(cè)試取元素后繼 獲取的后繼是放在temp中的
delete pList;
pList = NULL;
system("pause");
}
LinkList.png
