结点类和单链表ADT_SingleList
最后更新于：2022-04-01 20:51:10
单链表中，每个元素占用一个结点，每个结点由两个域组成，分别是存放元素的数据域element以及存放指向表中后继结点地址的指针域Link。逻辑上相邻的元素在物理上不一定相邻，结点与节点不要求被存放在相邻的存储空间，结点间的相邻关系通过指针来实现。
包含的函数：IsEmpty(), Length(), Find(), Search(), Insert(), Delete(), Update(), Clear()，Output()。
学完C语言后很少接触链表了，所以学起来有点吃力，需要想的地方已经加注释，觉的抽象的地方可以画图并参考代码帮助理解。
优点：插入和删除操作方便，克服了顺序表的缺点。
缺点：没有顺序表随机存储的特性。
实现代码：
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
template
class LinearList
{
public:
virtual bool IsEmpty() const = 0; // 为空则返回true
virtual int Length() const = 0; // 返回长度
virtual bool Find(int i, T &x) const = 0; // 若a[i]存在则x = a[i]，返回true，不存在返回flase
virtual int Search(T x) const = 0; // 若存在等于x的元素则返回下标，否则返回-1
virtual bool Insert(int i, T x) = 0; // i == -1则x插在第一个元素之前， 否则x插在a[i]后，插入成功返回true
virtual bool Delete(int i) = 0; // 删除元素a[i]，删除成功返回true
virtual bool Update(int i, T x) = 0; // 修改元素a[i]为x，若修改成功则返回true
virtual void Output(ostream &out) const = 0;
/* data */
protected:
int n;
};
template class SingleList; // 超前声明SingleList
template
class Node
{
private:
T element; // 数据域
Node *Link; // 指针域
friend class SingleList; // 结点类的友元，可访问Node类中私有成员
/* data */
};
template
class SingleList:public LinearList
{
public:
SingleList() {
first = NULL;
n = 0;
}
~SingleList();
bool IsEmpty() const;
int Length() const;
bool Find(int i, T &x) const;
int Search(T x) const;
bool Insert(int i, T x);
bool Delete(int i);
bool Update(int i, T x);
void clear();
void Output(ostream &out) const;
/* data */
private:
Node *first;
int n;
};
template
SingleList:: ~SingleList()
{
Node *p;
while(first) {
p = first -> Link;
delete first;
first = p;
}
}
template
int SingleList::Length() const
{
return n;
}
template
bool SingleList::IsEmpty() const
{
return n == 0;
}
template
bool SingleList::Find(int i, T &x) const
{
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl;
return false;
}
Node *p = first;
for(int j = 0; j < i; ++j)
p = p -> Link; // p最终为i的指针域
x = p -> element;
return true;
}
template
int SingleList::Search(T x) const
{
int j;
Node *p = first;
for(j = 0; p && p -> element != x; ++j) // p为空或p的数据域为x则提前停止循环
p = p -> Link;
if(p) return j; // p不为NULL说明存在等于x的数据域
return -1;
}
template
bool SingleList::Insert(int i, T x)
{
if(i < -1 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl;
return false;
}
Node *q = new Node;
q -> element = x;
Node *p = first;
for(int j = 0; j < i; ++j)
p = p -> Link; // p最终为i的指针域
if(i > -1) { // 在a[i]后插入x，相当于a[i]和a[i + 1]之间多了一个q
q -> Link = p -> Link; // q指向a[i]后的元素
p -> Link = q; // p指向q
}
else { // 在第一个元素前插入x，相当于在首个元素之前多了一个q
q -> Link = first; // q指向首个元素
first = q; // 将q作为首个元素的指针域
}
n++;
return true;
}
template
bool SingleList::Delete(int i)
{
if(!n) { // 链表为空
cout << "UnderFlow" << endl;
return false;
}
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl;
return false;
}
Node *p = first, *q = first;
for(int j = 0; j < i - 1; ++j)
q = q -> Link; // q最终为i - 1的指针域
if(i == 0) first = first -> Link; // 删除首个元素
else {
p = q -> Link; // p指向a[i]
q -> Link = p -> Link; // p -> Link为a[i + 1]，赋值完成后a[i - 1]直接指向a[i + 1]
}
delete p;
n--;
return true;
}
template
bool SingleList::Update(int i, T x)
{
if(i < 0 || i > n - 1) { // i不合法
cout << "Out of Bounds" << endl;
return false;
}
Node *p = first;
for(int j = 0; j < i; ++j)
p = p -> Link; // p最终指向a[i]
p -> element = x; // 将x赋值给a[i]
return true;
}
template
void SingleList::Output(ostream &out) const
{
Node *p = first;
while(p) {
out << p -> element << " ";
p = p -> Link;
}
out << endl;
}
int main(int argc, char const *argv[])
{
SingleList A;
A.Insert(-1, 0);
A.Insert(0, 1);
A.Insert(1, 2);
A.Insert(2, 3);
A.Insert(3, 4); // A = {0, 1, 2, 3, 4}
cout << "链表A为：" << endl;
A.Output(cout);
int flag = A.Search(2); // 元素中是否有2
if(flag != -1) cout << "有等于2的元素" << endl;
else cout << "无等于2的元素" << endl;
int x;
A.Find(1, x); // x = a[1]
cout << "a[1] == " << x << endl;
A.Update(1, 5); // A = {0, 5, 2, 3, 4}
A.Output(cout);
A.Delete(1); // A = {0, 2, 3, 4}
A.Output(cout);
return 0;
}
~~~
';