结点类和单链表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; } ~~~
';