数据结构——单链表模板类

绝地灬酷狼 2022-06-08 11:46 230阅读 0赞

# 数据结构相关笔记整理（一） #

这里主要是整理自己在学习数据结构的时候的笔记，这篇博客主要整理单链表的模板类附带几个内置函数的测试，新手上路，多多包涵，发现错误及时交流.....

第一部分是主类代码：(直接贴了哈~~)

\#include <iostream>  
\#include <iomanip>  
\#include "linearList.h"  
using namespace std;

//定义单链表的模板类  
template<class T>  
struct LinkNode\{  
T data; //数据域  
struct LinkNode<T> \*link; //指针域  
LinkNode(struct LinkNode<T> \*ptr = NULL)\{ link = ptr; \} //只初始化指针成员的构造函数  
LinkNode(const T &item, struct LinkNode<T> \*ptr = NULL) //数据和地址都初始化的构造函数  
\{  
data = item;  
link = ptr;  
\}  
\};  
//单链表类定义  
template<class T>  
class List \{  
public:  
List() \{ first = new LinkNode<T>; \} //构造函数  
List(const T &x) \{first = new LinkNode<T>(x)\} //构造函数  
List(List<T> &L); //复制构造函数  
~List()\{ makeEmpty(); \} //析构函数  
void makeEmpty(); //将链表置空  
int Length() const; //计算链表的长度  
LinkNode<T> \* getHead() const\{ return first; \}  
LinkNode<T> \* Search(T x); //搜素数据为x的节点  
LinkNode<T> \* Locate(int i)const; //搜索第i个元素的地址  
bool getData(int i, T &x) const; //取出第i个节点的数据  
void setData(int i, T &x); //用x修改第i个元素的值  
bool Insert(int i, T &x); //在第i个节点后插入新节点  
bool Remove(int i, T &x); //删除第i个节点数据返回到x中  
bool IsEmpty() const //判断表是否为NULL  
\{  
return first->link == NULL ? true : false;  
\}  
bool IsFull() const \{ return false; \} //判断表满  
void Sort(); //排序  
void InputFront(T endFlag); //倒序创建单链表  
void InputRear(T endFlag); //正序创建单链表  
void Output(); //输出  
List<T>& operator=(List<T> & L); //重载赋值运算符  
protected:  
struct LinkNode<T> \*first;  
\};  
//class的函数定义  
template<class T>  
List<T>::List(List<T> & L) \{  
//复制构造函数  
T value;  
LinkNode<T> \*srcptr = L.getHead();  
LinkNode<T> \*destptr = first = new LinkNode<T>;  
while (srcptr->link != NULL) \{ //逐一赋值  
value = srcptr->link->data;  
destptr->link = new LinkNode<T>(value);  
destptr = destptr->link; //左值游动指针移动到下一个  
srcptr = srcptr->link; //右值游动指针移动到下一个  
\}  
destptr->link = NULL;  
\}

template<class T>  
void List<T>::makeEmpty() \{  
//将链表置为NULL表,最终只保留头节点  
LinkNode<T> \* q;  
while (first->link != NULL) \{ //如果链表不为NULL则开始释放节点  
q = first->link; //释放first所指向的节点  
first->link = q->link; //利用fist记住p的下一个节，防止内存泄漏  
delete q; //释放q所指向的节点  
\}  
\}

template<class T>  
int List<T>::Length() const\{  
//计算带附加头节点的单链表的长度  
LinkNode<T> \* p = first->link;  
int count = 0;  
while (p != NULL) \{  
count++;  
p = p->link;  
\}  
return count;  
\}

template<class T>  
LinkNode<T> \* List<T>::Search(T x) \{  
//在表中搜索含数据x的节点，搜索成功时返回该节点的地址，否则返回NULL  
LinkNode<T> \* current = first->link;  
while (current != NULL) \{  
if (current->data == x) \{  
break;  
\}  
else \{  
current = current->link;  
\}  
\}  
return current;  
\}

template<class T>  
LinkNode<T> \* List<T>::Locate(int i) const \{  
//定位函数 返回表中第i个节点的地址 如果i < 0 或者i 超过链表长度则返回NULL  
if (i < 0) \{  
return NULL;  
\}  
LinkNode<T> \* current = first;  
int m = 0;  
while (current != NULL && m < i) \{  
current = current->link;  
m++;  
\}  
return current;  
\}

template<class T>  
bool List<T>::getData(int i, T & x) const\{  
//取出链表中第i个节点的data  
if (i <= 0) \{  
return NULL; //数据非法返回false  
\}  
LinkNode<T> \* current = Locate(i); //借助定位函数直接定位到相应的节点  
if (NULL == current) \{  
return false; //i超过单链表的长度返回false  
\}  
else \{  
x = current->data;  
return true;  
\}  
\}

template<class T>  
void List<T>::setData(int i, T & x) \{  
//设置链表的第i个元素为x  
if (i <= 0) \{  
return;  
\}  
LinkNode<T> \* current = Locate(i); //体现出来定位函数的优越性  
if (NULL == current) \{  
return;  
\}  
else \{  
current->data = x;  
\}  
\}

template<class T>  
bool List<T>::Insert(int i, T & x) \{  
//在i个节点之后插入新节点  
LinkNode<T> \* current = Locate(i);  
if (NULL == current) \{  
return false;  
\}  
LinkNode<T> \* newNode = new LinkNode<T>(x);  
if (NULL == newNode) \{  
cerr << "存储分配错误" << endl;  
exit(1);  
\}  
newNode->link = current->link;  
current->link = newNode;  
return true;  
\}

template<class T>  
bool List<T>::Remove(int i, T & x) \{  
//将链表中第i个节点删除 删除成功返回true并将删除的data存储在x中  
LinkNode<T> \* current = Locate(i - 1); //定位到指向i节点的节点  
if (NULL == current || NULL == current->link) \{  
return false; //不存在待删除的节点  
\}  
LinkNode<T> \* del = current->link; //标记待删除的节点  
current->link = del->link; //重新拉链  
x = del->data; //记录下删除节点的data  
delete del; //释放删除节点  
return true;  
\}

template<class T>  
void List<T>::Output() \{  
//单链表的输出函数 ：将单链表中所有节点的data按逻辑顺序输出到Screen上  
LinkNode<T> \* current = first->link; //创建遍历指针  
while (current != NULL) \{  
cout << current->data << ' ';  
current = current->link;  
\}  
cout << endl;  
\}

template<class T>  
List<T> & List<T>::operator=(List<T> & L) \{  
//赋值运算符重载函数  
//过程 ：形如 A = B 其中A 是调用此操作的List对象B是与参数表中的L结合的List  
T value; //传递每个节点中的数据  
LinkNode<T> \* srcptr = L.getHead();  
LinkNode<T> \* destptr = first = new LinkNode<T>;  
while (srcptr->link != NULL) \{ //逐个节点赋值  
value = srcptr->link->data;  
destptr->link = new LinkNode<T>(value); //开辟新的节点并初始化  
destptr = destptr->link;  
srcptr = srcptr->link; //新旧链游动指针分别向后移动  
\}  
destptr->link = NULL;  
return \*this;  
\}

template<class T>  
void List<T>::InputFront(T endFlag) \{  
//endFlag是约定的输入元素结束的标志  
LinkNode<T> \* newNode;  
T val;  
makeEmpty();  
cin >> val;  
while (val != endFlag) \{  
newNode = new LinkNode<T>(val); //创建新的节点  
if (NULL == newNode) \{  
cerr << "内存分配错误" << endl;  
exit(1);  
\}  
newNode->link = first->link; //注意这两部执行的顺序  
first->link = newNode;  
cin >> val;  
\}  
\}

template<class T>  
void List<T>::InputRear(T endFlag) \{  
//函数功能 ： 顺序建立单链表  
//函数参数 ： 输入结束标志的数据  
LinkNode<T> \*newNode, \*last; //需要一个指针时刻标记结尾  
T val;  
makeEmpty();  
cin >> val;  
last = first; //首先令last指针指向头节点  
while (val != endFlag) \{  
newNode = new LinkNode<T>(val);  
if (NULL == newNode) \{  
cerr << "内存分配错误" << endl;  
exit(1);  
\}  
last->link = newNode;  
last = newNode;  
cin >> val;  
\}  
last->link = NULL;  
\}

template<class T>  
void List<T>::Sort() \{  
//对单链表按照数据域从小到大排序  
//思路 ： 冒泡排序算法，用游动指针遍历整个链表  
LinkNode<T> \*current, \*current\_2;  
T temp;  
current = current\_2 = first->link;  
while (current != NULL) \{  
while (current\_2->link != NULL) \{  
if (current\_2->data > current\_2->link->data) \{  
//交换2个data  
temp = current\_2->data;  
current\_2->data = current\_2->link->data;  
current\_2->link->data = temp;  
\}  
current\_2 = current\_2->link;  
\}  
current = current->link;  
current\_2 = first->link;  
\}  
\}

第二部分是main测试函数代码：

int main()  
\{  
//List<int> list1; //单链表排序测试  
//list1.InputRear(0); //正序建立单链表，以0为结束标志（注意此处0不能作为data）  
//list1.Sort(); //排序函数调用  
//list1.Output();

//int insertValue = 100, delValue = 0;  
//List<int> list2; //单链表的插入与删除节点测试  
//list2.InputFront(0); //倒序建立单链表  
//list2.Insert(3, insertValue); //在第三个节点后面插入data为100的节点  
//list2.Output();  
//list2.Remove(4, delValue); //删除第4个节点  
//list2.Output();  
//cout << delValue << endl; //输出删除的数据

//int modityValue = 0, getValue = 0;  
//List<int> list3; //节点数据的修改与提取测试  
//list3.InputRear(0); //正序建立单链表  
//list3.setData(4, modityValue); //修改第4个节点的数据为0  
//list3.Output();  
//list3.getData(1, getValue); //提取第1个数据到getValue变量中  
//cout << getValue << endl;

//int len = 0;  
//List<int> list4; //计算链表长度测试  
//list4.InputFront(0); //倒序建立单链表  
//len = list4.Length();  
//cout << "此链表的长度为 ： " << len << endl;

List<int> list5; //判NULL、FULL和set NULL操作测试  
list5.InputFront(0);  
list5.Output();  
if (!list5.IsFull()) \{ //单链表可以扩展，此处恒为false  
cout << "Full" << endl;  
\}  
list5.makeEmpty();  
cout << list5.Length() << endl;  
if (list5.IsEmpty()) \{  
cout << "Empty..." << endl;  
\}

system("pause");  
return 0;  
\}

相信代码是交流技术最好的语言，其他废话就不多说了，10：30了，估计宿舍快关了。

也希望其他同学能够相互交流，相互借鉴，共同进步！