#include <iostream> #include <string> #include <cstring> #include <queue> using namespace std; template<class T> struct Node { T data; Node<T> *next_pos; }; template<class T> class LinkedList { public: LinkedList(); LinkedList(T arr[], int n); ~LinkedList() {}; T Get(int i); int Locate(T x); void Insert(T x,int i); T Delete(int i); void PrintList(); int length(); private: Node<T> *first,*p,*s; }; template<class T> LinkedList<T>::LinkedList() { first = new Node <T>; first->next_pos = NULL; } template<class T> LinkedList<T>::LinkedList(T arr[], int n) { first = new Node<T>; first->next_pos = NULL; for (int i = 0; i < n; i++) { p = new Node<T>; p->data = arr[i]; p->next_pos = first->next_pos; first->next_pos = p; } /*尾插法 first = new Node<T>; first->next_pos = NULL; p = first; for (int i = 1; i <= n; i++) { s = new Node<T>; s->data = arr[i]; s->next_pos = NULL; p->next_pos = s; p = p->next_pos; }*/ } template<class T> T LinkedList<T>::Get(int n) { p = first->next_pos; for (int i = 0; i < n - 1 && p != NULL; i++) { p = p->next_pos; } return p == NULL ? -1 : p->data; } template<class T> int LinkedList<T>::Locate(T x) { p = first->next_pos; int count = 1; while (p!=NULL) { if (p->data == x) { return count; } } return p == NULL ? -1 : p->data; } template<class T> void LinkedList<T>::Insert(T x,int i) { p = first->next_pos; int count = 1; while (p!=NULL && count <= i-1) { p = p->next_pos; count++; } if (p == NULL) throw "error"; else { s = new Node<T>; s->data = x; s->next_pos = p->next_pos; p->next_pos = s; } } template<class T> T LinkedList<T>::Delete(int i) { p = first->next_pos; int count = 0; while (p != NULL && count < i - 1) { p = p->next_pos; count++; } if (p == NULL||p->next_pos == NULL) throw "error"; else { s = p->next_pos; p->next_pos = p->next_pos->next_pos; T ans=s->data; delete s; return ans; } } template<class T> void LinkedList<T>::PrintList() { p=first->next_pos; while (p != NULL) { cout << p->data << " "; p = p->next_pos; } cout << endl; } template<class T> int LinkedList<T>::length() { p = first->next_pos; long long int count = 0; while (p != NULL) { p = p->next_pos; count++; } return count; } int main() { int a[9999]; for (int i = 0; i < 100; i++) a[i] = i; LinkedList<int> ab(a, 10); ab.PrintList(); ab.Insert(100, 2); ab.PrintList(); cout << ab.length() << endl; cout << ab.Get(2) << endl; ab.Delete(2); ab.PrintList(); cout << ab.length() << endl; cout << ab.Get(2) << endl; ab.PrintList(); }