下面是本人编写的一个“链表”类，大家给点意见吧。
首先是“链表”类的声明
/**********************************************
*
* 文件名：CLinkList.h
*
* 功 能：声明链表类
*
**********************************************/
#ifndef CLINKLIST_H_
#define CLINKLIST_H_
class CLinkList //链表类
{
public:
//一般构造函数、拷贝构造函数、赋值运算符、析构函数
CLinkList();
CLinkList(const CLinkList &rhs);
CLinkList& operator=(const CLinkList &rhs);
~CLinkList();
//插入
bool Insert(int position, const char *element); //在指定位置上添加节点
bool Insert(const char *beforeElem, const char *element); //在指定节点的前面添加节点
//删除
bool Delete(int position); //删除指定位置上的节点
bool Delete(const char *element); //删除指定节点
//修改
bool Update(int position, const char *element); //修改指定位置上的节点
bool Update(const char *oldElem, const char *newElem); //修改指定的节点为新的节点值
//查找
bool Search(const char *element, int &position); //返回指定节点在链表上的位置
bool Search(int position, char **element); //返回指定位置上的节点
bool Sort(void); //对链表进行排序操作(冒泡排序)
bool Display(void); //顺序显示链表中所有节点的元素值
inline void Count(int &nodeCount) //返回链表中所有节点的个数
{
nodeCount = m_count;
};
private:
struct Node //节点结构
{
struct Node *last; //指向前一个节点的指针
char *element; //节点元素
struct Node *next; //指向后一个节点的指针
};
struct Node *m_head; //链表的表头指针
int m_count; //节点的个数
};
#endif
///////////////////////////////////////////////////////////////////////
下面是“链表”类的实现
/**********************************************
*
* 文件名：CLinkList.cpp
*
* 功 能：实现链表类的各种操作
*
**********************************************/
#include <iostream>
#include "CLinkList.h"
using namespace std;
//一般构造函数
CLinkList::CLinkList()
:m_count(0),m_head(NULL)
{
m_head = new Node; //申请表头指针的内存空间
if (m_head != NULL) //申请成功
{
//初始化表头指针
m_head->last = NULL;
m_head->element = NULL;
m_head->next = NULL;
}
else //申请失败
{
m_head = NULL;
}
}
//拷贝构造函数
CLinkList::CLinkList(const CLinkList &rhs)
:m_count(0),m_head(NULL)
{
int len = 0;
//临时的节点指针
struct Node *temp = NULL;
struct Node *back = NULL;
m_head = new Node; //申请表头指针的内存空间
if (m_head != NULL) //申请成功
{
//初始化表头指针
m_head->last = NULL;
m_head->element = NULL;
m_head->next = NULL;
temp = rhs.m_head->next; //temp指向rhs所引用的CLinkList对象中的链表的第一个节点
if (temp != NULL) //rhs所引用的CLinkList对象中的链表不为空
{
back = new Node; //为本对象中的链表的第一个节点申请内存空间
if (back != NULL) //申请成功
{
m_head->next = back; //表头指针指向第一个节点
back->last = m_head; //第一个节点指向表头指针
//拷贝节点元素值
len = strlen(temp->element);
back->element = new char[len+1];
strcpy(back->element, temp->element);
back->next = NULL; //后继节点暂时为空
++m_count; //节点个数加1
//下一个节点
temp = temp->next; //temp指向rhs所引用的CLinkList对象中的链表的第二个节点
while (temp != NULL) //节点存在
{
back->next = new Node;
if (back->next != NULL) //内存申请成功
{
back->next->last = back; //指向前一个节点
back = back->next; //指向下一个节点
len = strlen(temp->element);
back->element = new char[len+1];
strcpy(back->element, temp->element);
back->next = NULL; //后继节点暂时为空
++m_count; //节点个数加1
temp = temp->next; //temp指向rhs所引用的CLinkList对象中的链表的下一个节点
}
else //内存申请失败
{
break;
}
} //end of while
} //end of if
} //end of if
}
else //申请失败
{
m_head = NULL;
}
}
//赋值运算符
CLinkList& CLinkList::operator=(const CLinkList &rhs)
{
int len = 0;
//临时的节点指针
struct Node *temp = NULL;
struct Node *back = NULL;
if (this != &rhs) //检查是否自赋值
{
//删除m_head指向的链表原有的所有节点
temp = m_head->next; //temp指向本对象中的链表的第一个节点
m_head->next = NULL;
while (temp != NULL)
{
back = temp->next; //保存下一个节点的指针值
delete [] temp->element; //释放节点元素值所占有的内存空间
delete temp; //释放节点所占有的内存空间
temp = back; //指向下一个节点
}
m_count = 0; //节点个数变为0
temp = NULL;
back = NULL;
//拷贝rhs所引用的CLinkList对象中的链表的所有节点到当前CLinkList对象中去
temp = rhs.m_head->next; //temp指向rhs所引用的CLinkList对象中的链表的第一个节点
if (temp != NULL) //rhs所引用的CLinkList对象中的链表不为空
{
back = new Node; //为本对象中的链表的第一个节点申请内存空间
if (back != NULL) //申请成功
{
m_head->next = back; //表头指针指向第一个节点
back->last = m_head; //第一个节点指向表头指针
//拷贝节点元素值
len = strlen(temp->element);
back->element = new char[len+1];
strcpy(back->element, temp->element);
back->next = NULL; //暂时没有后继节点
++m_count; //节点个数加1
//下一个节点
temp = temp->next; //temp指向rhs所引用的CLinkList对象中的链表的第二个节点
while (temp != NULL)
{
back->next = new Node;
if (back->next != NULL) //内存申请成功
{
back->next->last = back; //指向前一个节点
back = back->next; //指向下一个节点
len = strlen(temp->element);
back->element = new char[len+1];
strcpy(back->element, temp->element);
back->next = NULL;
++m_count; //节点个数加1
temp = temp->next; //指向下一个节点
}
else //内存申请失败
{
break;
}
} //end of while
} //end of if
} //end of if
} //end of if
return *this; //返回本对象的引用(一般用于链式的赋值)
}
//析构函数
CLinkList::~CLinkList()
{
//临时的节点指针
struct Node *temp = NULL;
struct Node *back = NULL;
if (m_head != NULL) //表头指针不为空
{
//删除m_head指向的链表中的所有节点
temp = m_head->next; //指向第一个节点
//释放表头指针所占有的内存空间
delete m_head;
m_head = NULL;
while (temp != NULL) //节点存在
{
back = temp->next; //保存下一个节点的指针值
delete [] temp->element; //释放节点元素值所占有的内存空间
delete temp; //释放节点所占有的内存空间
--m_count; //节点个数减1
temp = back; //指向下一个节点
}
} //end of if
}
//在指定位置上添加节点
bool CLinkList::Insert(int position, const char *element)
{
int index = 0;
int len = 0;
//临时的节点指针
struct Node *temp = NULL;
struct Node *back = NULL;
struct Node *newNode = NULL;
if ((position < 1) || (position > (m_count+1))) //指定的位置不正确
{
return false;
}
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
//链表为空，没有任何节点时
if (NULL == temp)
{
newNode = new Node; //为第一个节点申请内存空间
if (newNode != NULL) //内存申请成功
{
m_head->next = newNode; //表头指针指向第一个节点
newNode->last = m_head; //第一个节点指向表头指针
//拷贝节点元素值
len = strlen(element);
newNode->element = new char[len+1];
strcpy(newNode->element, element);
newNode->next = NULL; //没有后继节点
++m_count; //节点个数加1
return true;
}
else //内存申请失败
{
return false;
}
} //end of if
//在 1、1与m_count之间、m_count 位置上插入节点时
while (temp != NULL)
{
++index;
if (position == index) //找到匹配的位置
{
newNode = new Node; //为插入的节点申请内存空间
if (newNode != NULL) //内存申请成功
{
temp->last->next = newNode; //使前一个节点指向新创建的节点
newNode->last = temp->last; //使新创建的节点指向前一个节点
//拷贝节点元素值
len = strlen(element);
newNode->element = new char[len+1];
strcpy(newNode->element, element);
newNode->next = temp; //使新创建的节点指向该位置上原来的节点，即现在的下一个节点。
temp->last = newNode; //该位置上原来的节点(即现在的下一个节点)指向新创建的节点
++m_count; //节点个数加1
return true;
}
else //内存申请失败
{
return false;
}
} //end of if
back = temp; //保存前一个节点的指针
temp = temp->next; //指向下一个节点
} //end of while
//在位置 m_count+1 上插入节点时
newNode = new Node; //为插入的节点申请内存空间
if (newNode != NULL) //内存申请成功
{
back->next = newNode; //使前一个节点指向新创建的节点
newNode->last = back; //使新创建的节点指向前一个节点
//拷贝节点元素值
len = strlen(element);
newNode->element = new char[len+1];
strcpy(newNode->element, element);
newNode->next = NULL; //没有后继节点
++m_count; //节点个数加1
return true;
}
else //内存申请失败
{
return false;
}
}
else //表头指针为空
{
return false;
}
}
//在指定节点的前面添加节点
bool CLinkList::Insert(const char *beforeElem, const char *element)
{
int len = 0;
//临时的节点指针
struct Node *temp = NULL;
struct Node *newNode = NULL;
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (NULL == temp) //链表为空，没有任何节点
{
return false;
}
else //链表不为空
{
while (temp != NULL)
{
if (strcmp(beforeElem, temp->element) == 0) //找到匹配的节点
{
newNode = new Node; //为插入的节点申请内存空间
if (newNode != NULL) //申请成功
{
temp->last->next = newNode; //使前一个节点指向新创建的节点
newNode->last = temp->last; //使新创建的节点指向前一个节点
//拷贝节点元素值
len = strlen(element);
newNode->element = new char[len+1];
strcpy(newNode->element, element);
newNode->next = temp; //使新创建的节点指向下一个节点
temp->last = newNode; //使下一个节点指向新创建的节点
++m_count; //节点个数加1
return true;
}
else //内存申请失败
{
return false;
}
} //end of if
temp = temp->next; //指向下一个节点
}
return false; //找不到匹配的节点时返回false
}
}
else //表头指针为空
{
return false;
}
}
//删除指定位置上的节点
bool CLinkList::Delete(int position)
{
int index = 0;
struct Node *temp = NULL; //临时的节点指针
if ((position < 1) || (position > m_count)) //指定的位置不正确
{
return false;
}
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (temp != NULL) //链表不为空
{
while (temp != NULL)
{
++index;
if (position == index) //找到匹配的位置
{
temp->last->next = temp->next; //使前一个节点指向下一个节点
if (temp->next != NULL) //存在下一个节点
{
temp->next->last = temp->last; //使下一个节点指向前一个节点
}
//释放要被删除的节点所占用的内存空间
delete [] temp->element;
delete temp;
--m_count; //节点个数减1
return true;
}
temp = temp->next; //指向下一个节点
} //end of while
return false;
}
else //链表为空
{
return false;
}
}
else //表头指针为空
{
return false;
}
}
//删除指定节点
bool CLinkList::Delete(const char *element)
{
struct Node *temp = NULL; //临时的节点指针
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (temp != NULL) //链表不为空
{
while (temp != NULL)
{
if (strcmp(element, temp->element) == 0) //找到匹配的节点
{
temp->last->next = temp->next; //使前一个节点指向下一个节点
if (temp->next != NULL) //存在下一个节点
{
temp->next->last = temp->last; //使下一个节点指向前一个节点
}
//释放要被删除的节点所占用的内存空间
delete [] temp->element;
delete temp;
--m_count; //节点个数减1
return true;
} //end of if
temp = temp->next; //指向下一个节点
} //end of while
return false; //找不到匹配的节点时返回false
}
else //链表为空
{
return false;
}
}
else //表头指针为空
{
return false;
}
}
//修改指定位置上的节点
bool CLinkList::Update(int position, const char *element)
{
int index = 0;
int len = 0;
struct Node *temp = NULL; //临时的节点指针
if ((position < 1) || (position > m_count)) //指定的位置不正确
{
return false;
}
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (temp != NULL) //链表不为空
{
while (temp != NULL)
{
++index;
if (position == index) //找到匹配的位置
{
//释放原来节点元素值占有的内存空间
delete [] temp->element;
temp->element = NULL;
//拷贝新的节点元素值
len = strlen(element);
temp->element = new char[len+1];
strcpy(temp->element, element);
return true;
} //end of if
temp = temp->next; //指向下一个节点
} //end of while
return false;
}
else //链表为空
{
return false;
}
}
else //表头指针为空
{
return false;
}
}
//修改指定的节点为新的节点值
bool CLinkList::Update(const char *oldElem, const char *newElem)
{
int len = 0;
struct Node *temp = NULL; //临时的节点指针
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (temp != NULL) //链表不为空
{
while (temp != NULL)
{
if (strcmp(oldElem, temp->element) == 0) //找到匹配的节点
{
//释放原来节点元素值占有的内存空间
delete [] temp->element;
temp->element = NULL;
//拷贝新的节点元素值
len = strlen(newElem);
temp->element = new char[len+1];
strcpy(temp->element, newElem);
return true;
}
temp = temp->next; //指向下一个节点
} //end of while
return false; //找不到匹配的节点时返回false
}
else //链表为空
{
return false;
}
}
else //表头指针为空
{
return false;
}
}
//返回指定节点在链表上的位置
bool CLinkList::Search(const char *element, int &position)
{
int index = 0;
struct Node *temp = NULL; //临时的节点指针
position = 0;
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (temp != NULL) //链表不为空
{
while (temp != NULL)
{
++index;
if (strcmp(element, temp->element) == 0) //找到匹配的节点
{
position = index; //返回指定节点的正确位置
return true;
}
temp = temp->next; //指向下一个节点
} //end of while
return false; //找不到匹配的节点时返回false
}
else //链表为空
{
return false;
}
}
else //表头指针为空
{
return false;
}
}
//返回指定位置上的节点元素
bool CLinkList::Search(int position, char **element)
{
int index = 0;
int len = 0;
struct Node *temp = NULL; //临时的节点指针
if ((position < 1) || (position > m_count)) //指定的位置不正确
{
return false;
}
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (temp != NULL) //链表不为空
{
while (temp != NULL)
{
++index;
if (position == index) //找到匹配的位置
{
//返回找到的节点元素值
strcpy(*element, temp->element);
return true;
} //end of if
temp = temp->next; //指向下一个节点
} //end of while
return false;
}
else //链表为空
{
return false;
}
}
else //表头指针为空
{
return false;
}
}
bool CLinkList::Sort(void) //对链表进行排序操作(冒泡排序)
{
int len = 0;
char *tempElem = NULL;
//临时的节点指针
struct Node *temp = NULL;
struct Node *back = NULL;
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (temp != NULL) //链表不为空
{
while (temp != NULL)
{
back = temp->next; //back 指向 temp 所指向的节点的下一个节点
while (back != NULL)
{
//temp->element 大于 back->element，两个节点元素之间交换
if (strcmp(temp->element, back->element) > 0)
{
//拷贝temp->element所指向的节点元素值到tempElem所指向的内存空间中去
len = strlen(temp->element);
tempElem = new char [len+1];
strcpy(tempElem, temp->element);
delete [] temp->element;
temp->element = NULL;
len = 0;
//拷贝back->element所指向的节点元素值到temp->element所指向的内存空间中去
len = strlen(back->element);
temp->element = new char [len+1];
strcpy(temp->element, back->element);
delete [] back->element;
back->element = NULL;
len = 0;
//拷贝tempElem所指向的节点元素值到back->element所指向的内存空间中去
len = strlen(tempElem);
back->element = new char [len+1];
strcpy(back->element, tempElem);
delete [] tempElem;
tempElem = NULL;
len = 0;
} //end of if
back = back->next; //back 指向下一个节点
} //end of while
temp = temp->next; //temp 指向下一个节点
} //end of while
return true; //排序完成就返回true
}
else //链表为空
{
return false;
}
}
else //表头指针为空
{
return false;
}
}
//顺序显示链表中所有节点的元素值
bool CLinkList::Display(void)
{
struct Node *temp = NULL; //临时的节点指针
if (m_head != NULL) //表头指针不为空
{
temp = m_head->next; //指向第一个节点
if (NULL == temp) //链表为空
{
return false;
}
//顺序输出各节点的元素值
while (temp != NULL)
{
cout << temp->element << '\t';
temp = temp->next; //指向下一个节点
}
cout << endl;
return true;
}
else //表头指针为空
{
return false;
}
}
///////////////////////////////////////////////////////////////////////////
