template <typename T> class NodeCls { public: T Data; NodeCls<T>* next; NodeCls(T data) : Data(data), next(nullptr) {} NodeCls<T>* NextNode() const { return next; } T GetData() const { return Data; } };
时间: 2024-04-28 07:24:36 浏览: 8
这是一个模板类 `NodeCls`,它表示一个链表中的节点。节点包含一个数据成员 `Data`,表示节点存储的数据,以及一个指向下一个节点的指针 `next`。构造函数接受一个类型为 `T` 的参数 `data`,用于初始化 `Data` 成员。`NextNode` 方法返回一个指向下一个节点的指针,`GetData` 方法返回当前节点存储的数据。该类可以用于实现链表数据结构。
相关问题
template <typename T> class SinglyLinkedList { public: SinglyLinkedList() : head(nullptr), rear(nullptr), curpos(nullptr), fontpos(nullptr), NCount(0) {} NodeCls<T>* NewNode(T data) { NodeCls<T>* p = new NodeCls<T>(data); return p; } void AscendingInsert(T data) { NodeCls<T>* p = NewNode(data); if (head == nullptr) { head = rear = p; } else if (p->Data <= head->Data) { p->next = head; head = p; } else if (p->Data >= rear->Data) { rear->next = p; rear = p; } else { curpos = head; while (curpos != nullptr && curpos->Data < p->Data) { fontpos = curpos; curpos = curpos->next; } fontpos->next = p; p->next = curpos; } NCount++; }
这是一个模板类 `SinglyLinkedList`,它表示一个单向链表。该类包含一个头指针 `head`、一个尾指针 `rear`、一个当前节点指针 `curpos`、一个当前节点前一个节点指针 `fontpos` 和一个整型成员 `NCount`,分别表示链表的头部、尾部、当前节点、当前节点前一个节点和链表中节点的数量。
类中定义了一个 `NewNode` 方法,用于创建一个新的节点,并返回指向该节点的指针。
类中定义了一个 `AscendingInsert` 方法,用于按照升序将一个新的节点插入到链表中。具体实现如下:
1. 调用 `NewNode` 方法创建一个新的节点 `p`。
2. 如果链表为空,将头指针和尾指针都指向新节点 `p`。
3. 如果新节点 `p` 的数据小于等于头节点的数据,将新节点 `p` 插入到头节点之前,然后更新头指针。
4. 如果新节点 `p` 的数据大于等于尾节点的数据,将新节点 `p` 插入到尾节点之后,然后更新尾指针。
5. 如果新节点 `p` 的数据在头节点和尾节点之间,从头节点开始遍历链表,找到第一个大于等于新节点 `p` 的节点 `curpos`,记录当前节点的前一个节点 `fontpos`,然后将新节点 `p` 插入到 `fontpos` 和 `curpos` 之间。
6. 更新节点数量计数器 `NCount`。
该类可以用于实现单向链表数据结构,并支持按照升序插入新节点。
#include <iostream> using namespace std; template <typename T> class LinkedList { template <typename U> friend ostream& operator << (ostream& out, const LinkedList<U> ll); struct Node { T data; Node* next; Node(T data = T()) : data(data), next(nullptr) {} } *head = new Node(); public: LinkedList() {} void append(T data) { Node* ptr = head; while (ptr -> next != nullptr) ptr = ptr -> next; ptr -> next = new Node(data); return; } T& operator [] (int index) { Node* ptr = head -> next; int length = 0; while (length != index) { ptr = ptr -> next; length ++; } return ptr -> data; } int size() { Node* ptr = head; int length = 0; while (ptr -> next != nullptr) { ptr = ptr -> next; length ++; } return length; } }; template <class T> ostream& operator << (ostream& out, const LinkedList<T> ll) { out << "[ "; for (int _ = 0; _ < ll.size(); _ ++) { cout << ll[_] << ' '; } cout << ']'; return out; } int main() { LinkedList<int> l = LinkedList<int>(); l.append(10); l.append(100); l.append(1000); cout << l << endl; return 0; }
这段代码定义了一个模板类LinkedList,用于实现一个链表数据结构。这个链表中每个节点包含一个数据元素和一个指向下一个节点的指针。这个类定义了若干个成员函数,包括:
- append:在链表末尾添加一个新的节点,其数据元素为参数data;
- operator[]:重载运算符[],用于访问链表中指定位置的节点的数据元素;
- size:返回当前链表中节点的数量。
此外,这个类还定义了一个友元函数operator<<,用于将整个链表输出到输出流中。这个函数使用了链表的operator[]运算符和size函数,依次输出链表中每个节点的数据元素,并以方括号括起来,中间使用一个空格隔开。
在main函数中,创建了一个int类型的链表l,并向其中添加了三个元素。随后,使用cout输出这个链表,调用了operator<<函数,将整个链表输出到控制台中。输出结果为"[ 10 100 1000 ]"。