以下的C++类LinkList实现了线性链表的一般操作。可以直接在其他的程序中直接建立它的对象,其中线性表中的数据在此为整型,具体应用的时候可以适当的修改,并可以在此基础上继续封装特定的功能。
头文件:LinkList.h
typedef strUCt LNode {
int data;
struct LNode *next;
}LNode, *pLinkList;
class LinkList {
private:
pLinkList m_pList;
int m_listLength;
public:
LinkList();
~LinkList();
bool InitList ();
bool DestroyList ();
bool ClearList();
bool IsEmpty ();
int GetLength ();
bool GetNode(int position, LNode** node);
int LocateElem(int elem);
bool SetNodeData(int position, int newData);
bool GetNodeData(int position, int &data);
bool InsertNode(int beforeWhich, int data);
bool DeleteNode(int position);
};
Cpp文件:LinkList.cpp
#include <iostream.h>
#include "LinkList.h"
LinkList::LinkList() {
m_pList = NULL;
m_listLength = 0;
InitList();
}
LinkList::~LinkList() {
if (!DestroyList()) {
DestroyList();
}
}
//初始化,分配一个头节点。
bool LinkList::InitList() {
if (!(m_pList = new LNode)) {
return false;
}
m_pList->next = NULL;
return true;
}
//销毁链表。
bool LinkList::DestroyList() {
if (!ClearList()) {
return false;
}
delete m_pList;
return true;
}
//判定链表是否为空。若为空,返回true,否则返回false。
bool LinkList::IsEmpty() {
if (m_pList->next == NULL) {
return true;
}
return false;
}
//返回链表的中当前节点数。
int LinkList::GetLength() {
return m_listLength;
}
//将链表清空,释放当前所有节点。
bool LinkList::ClearList() {
if (m_pList == NULL) {
return false;
}
LNode *pTemp = NULL;
while (m_pList->next != NULL) {
pTemp = m_pList->next;
m_pList->next = pTemp->next;
delete pTemp;
}
m_listLength = 0;
return true;
}
//将position指定的节点内的数据设置为newData。
//第一个有效节点的position为1。
bool LinkList::SetNodeData(int position, int newData) {
LNode *pTemp = NULL;
if (!(GetNode(position, &pTemp))) {
return false;
}
pTemp->data = newData;
return true;
}
//得到指定位置节点的数据。
//节点索引从1到listLength。
bool LinkList::GetNodeData(int position, int &data) {
LNode *pTemp = NULL;
if (!(GetNode(position, &pTemp))) {
return false;
}
data = pTemp->data;
return true;
}
//在链表中插入一个节点。
//插入的位置由beforeWhich指定,新节点插入在beforeWhich之前。
//beforeWhich的取值在1到ListLength+1之间。
bool LinkList::InsertNode(int beforeWhich, int data) {
LNode *pTemp = NULL;
if (beforeWhich < 1 beforeWhich > (m_listLength + 1)) {
return false;
}
if (!(GetNode(beforeWhich - 1, &pTemp))) {
return false;
}
LNode *newNode = new LNode;
newNode->data = data;
newNode->next = pTemp->next;
pTemp->next = newNode;
m_listLength++;
return true;
}
//删除一个指定的节点。
//节点位置由position指定。
//positon的值从1到listLength。
//若链表为空或指定的节点不存在则返回false。
bool LinkList::DeleteNode(int position) {
if (position < 1 position > m_listLength) {
return false;
}
LNode *pTemp = NULL;
if (!(GetNode(position - 1, &pTemp))) {
return false;
}
LNode *pDel = NULL;
pDel = pTemp->next;
pTemp->next = pDel->next;
delete pDel;
m_listLength--;
return true;
}
//得到指定位置节点的指针。
bool LinkList::GetNode(int position, LNode **node) {
LNode *pTemp = NULL;
int curPos = -1;
pTemp = m_pList;
while (pTemp != NULL) {
curPos++;
if (curPos == position)
break;
pTemp = pTemp->next;
}
if (curPos != position) {
return false;
}
*node = pTemp;
return true;
}
//定位与指定数据相等的数据节点。
//假如在当前链表中已经存在该数据则返回该数据节点的索引号。
//若不存在这样的节点则返回0。
//节点索引从0开始到listLength。
int LinkList::LocateElem(int elem) {
LNode *pTemp = NULL;
int curIndex = 1;
pTemp = m_pList->next;
while ((pTemp != NULL) && (pTemp->data != elem)) {
pTemp = pTemp->next;
curIndex++;
}
if (pTemp == NULL) {
return 0;
}
return curIndex;
}
/*
int main(){
LinkList l;
l.InsertNode(1, 10);
l.InsertNode(2, 20);
l.InsertNode(3, 30);
l.InsertNode(4, 40);
cout << l.GetLength() << endl;
int dataTemp = 0;
for (int i = 1; i <= l.GetLength(); i++) {
l.GetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
if (l.SetNodeData(3, 50)) {
cout <<"DONE\n";
} else {
cout << "Failed\n";
}
for (i = 1; i <= l.GetLength(); i++) {
l.GetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
if (l.DeleteNode(4)) {
cout <<"DONE\n";
} else {
cout << "Failed\n";
}
for (i = 1; i <= l.GetLength(); i++) {
l.GetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
cout << l.LocateElem(50) << endl;
return 0;
}
*/