分享

一般线性链表类的C++实现 - Full House Of Fe

 accesine 2005-10-14
一般线性链表类的C++实现

以下的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;
}
*/

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多