单链表实现（c++）

#include <iostream> #include <string> #include <cstring> using namespace std; const int N = 110; // 模板类 template <typename T> struct node { T data; // 值域； node<T> *next; // 指针域； }; template <typename T> class linklist { node<T> *first; // 单链表头指针； public: linklist(); // 空构造函数，创建头节点； linklist(T a[], int n); // 带参构造函数，创建链表； ~linklist(); // 析构函数； int length(); // 返回链表长度； int getn(T num); // 按值查找； T getp(int pos); // 按位置查找； T del(int pos); // 删除pos位置的元素，并返回该位置元素的值； void insert(int pos, T num); // 在pos位置插入num； void display(); // 循环输出链表； }; template <typename T> linklist<T>::linklist() { first = new node<T>; // 创建头节点并初始化； first->next = nullptr; } template <typename T> linklist<T>::linklist(T a[],int n) // 尾插法； { first = new node<T>; node<T> *r = first; node<T> *s = nullptr; // s指针初始化； for(int i = 1; i <= n; i++) { s = new node<T>; s->data = a[i]; r->next = s; r = s; } r->next = nullptr; // 单链表创建完成，r指针置空； } template <typename T> linklist<T>::~linklist() { node<T> *p = first; // 释放每个节点； while(first != nullptr) { first = first->next; delete p; p = first; } } template <typename T> int linklist<T>::length() { node<T> *p = first->next; int cnt = 1; // 计数器； while(p != nullptr) { p = p->next; cnt++; } cnt--; // 循环结束条件为p==nullptr，则cnt比链表实际长度多1； return cnt; } template <typename T> int linklist<T>::getn(T num) { node<T> *p = first->next; int cnt = 1; // 计数器； while(p != nullptr) { if(p->data == num) // 找到值就返回该值的位置； return cnt; p = p->next; cnt++; } if(p == nullptr) // 若没找到则抛出异常； throw "查找值错误"; } template <typename T> T linklist<T>::getp(int pos) { node<T> *p = first->next; int cnt = 1; // 计数器； while(p != nullptr && cnt <= pos - 1) // 循环结束之后p指针处于pos位置； { p = p->next; cnt++; } if(p == nullptr) // 没找到则抛出异常，找到就返回相应值； throw "查找位置错误"; else return p->data; } template <typename T> T linklist<T>::del(int pos) { node<T> *p = first->next; node<T> *q = nullptr; T x; int cnt = 1; 计数器； while(p != nullptr && cnt < pos - 1) // 循环结束之后p处于pos-1位置； { p = p->next; cnt++; } if(p == nullptr) // p为空则抛出异常，不空就删除； throw "删除位置错误"; else { q = p->next; x = q->data; p->next = q->next; delete q; return x; } } template <typename T> void linklist<T>::insert(int pos, T num) { node<T> *p = first->next; node<T> *s = nullptr; // s指针初始化； int cnt = 1; while(p != nullptr && cnt < pos - 1) // 循环结束之后p处于pos-1位置； { p = p->next; cnt++; } if(p == nullptr || p->next == nullptr) // 若该位置和其下一位都为空，则抛出异常； throw "插入位置错误"; else { s = new node<T>; s->data = num; s->next = p->next; p->next = s; } } template <typename T> void linklist<T>::display() // 循环输出打印出链表； { node<T> *p = first->next; while(p != nullptr) { cout << p->data << " "; p = p->next; } } int main() { int a[N]; memset(a,0,sizeof(a)); for(int i = 1; i <= 5; i++) a[i] = i; linklist<int> A(a,5); cout << A.length() << endl; // 返回链表长度，除去头节点； cout << A.getp(3) << endl; // 按位置查找； cout << A.getn(5) << endl; // 按值查找 cout << A.del(5) << endl;; // 删除pos位置元素并返回pos位置元素的值 A.insert(4,111); // 在pos位置插入num； A.display(); // 循环输出列表； return 0; }