数据结构 单一列表

大家好，又见面了，我是全栈君。

#ifndef LINKLIST_H #define LINKLIST_H #include<iostream> using namespace std; template <typename T> struct Node { T data; Node<T> *next; }; template <typename T> class LinkList { public: LinkList(); //无參构造函数，建立仅仅有头结点的空链表 LinkList(T a[], int n); //有參构造函数，建立由n个元素的单链表 ~LinkList(); //析构函数 int Length(); //求单链表的长度 T Get(int i); //按位查找，查找单链表中的第i个元素的数值 int Locate(T x); //查找该元素在单链表中的位置 void Insert(int i, T x); //在第i个位置插入该元素 T Delete(int i); //删除第i个元素 void PrintList(); //打印单链表 private: Node<T> *first; //创建单链表的头指针 }; template <typename T> LinkList<T>::LinkList() { Node<T> *first; //申明头结点 first = new Node<T>; //生成头结点 first->next = NULL; //初始化头节点 } template <typename T> LinkList<T>::LinkList(T a[], int n) { Node<T> *r, *s; //申明两个暂时结点 first = new Node<T>; //生成头结点 r = first; //尾指针初始化 for (int i = 0; i < n; i++) { s = new Node<T>; //生成S结点来存储数组中相应的元素 s->data = a[i]; //将数组中相应的元素赋值到相应结点的数值部位 r->next = s; r = s; //上两部是将s插入到终端结点之后 } r->next = NULL; } template <typename T> LinkList<T>::~LinkList() { Node<T> *q = NULL; //建立一个空的结点 while (first != NULL) //该循环释放结点的存储空间 { q = first; first = first->next; delete q; } } template <typename T> int LinkList<T>::Length() { Node<T>*p=first->next; int count = 0; //初始化 while (p != NULL) { p = p->next; //p指针后移 count++; } return count; } template <typename T> T LinkList<T>::Get(int i) { Node<T> *p = first->next; int count = 1; while (p != NULL&&count < i) { p = p->next; count++; } if (p == NULL)throw”位置”; else return p->data; //单恋表中first是空结点，不算在单链表中的。所以第一个元素是在第一个结点中的。序号是相应的 } template <typename T> int LinkList<T>::Locate(T x) { Node<T> *p = first->next; int count = 1; //上述初始化工作量 while (p != NULL) { if (p->data == x) return count; p = p->next; count++; } return 0; //推出循环查找，表示查找失败。

} template <typename T> void LinkList<T>::Insert(int i, T x) { Node<T> *p = first; int count = 0; //上述初始化工作量 while (p != NULL&&count < i – 1) { p = p->next; count++; } if (p == NULL)throw”位置”; else { Node<T> *s; s = new Node<T>; s->data = x; s->next = p->next; p->next = s; } } template <typename T> T LinkList<T>::Delete(int i) { Node<T> *p = first; T x; int count = 0; while (p != NULL&&count < i – 1) { p = p->next; count++; } if (p == NULL || p->next == NULL)throw”位置”; else { Node<T> *q; q = p->next; x = q->data; p->next = q->next; delete q; return x; } } template <typename T> void LinkList<T>::PrintList() { Node<T> *p; p = first->next; while (p != NULL) { cout << p->data<<“->”; p = p->next; } } #endif ******************************************************************* #include”LinkList.h” #include<iostream> #include<iomanip> using namespace std; void main() { int a[10] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 }; int ch; LinkList<int> zxh(a,10); cout << “生成的单链表为:”; zxh.PrintList(); cout << endl; cout << “1-求长度”<<setw(17); cout << “2-按位查找” << endl; cout << “3-按值查找” << setw(15); cout << “4-插入操作” << endl; cout << “5-删除操作” << setw(15); cout << “6-遍历操作” << endl; cout << “请输入您想进行的操作:”; cin >> ch; switch (ch) { case 1:zxh.Length(); break; case 2:int m1; cout << “请输入您想按位查找的位号:”; cin >> m1; zxh.Get(m1); break; case 3: int m2; cout << “请输入您想查找的值:”; cin >> m2; zxh.Locate(m2); break; case 4:int m3, m4; cout << “请输入想插入的位置:”; cin >> m3; cout << “请输入想插入的元素:”; cin >> m4; zxh.Insert(m3, m4); break; case 5: int m5; cout << “请输入想删除的位置:”; cin >> m5; zxh.Delete(m5); break; case 6: zxh.PrintList(); } } 这个单恋表中我自己刚才測试了一下。

基本上没什么大问题。

但似乎球的时间长短是不正确的。我希望我们能提出作证。

版权声明：本文博客原创文章。博客，未经同意，不得转载。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/117352.html原文链接：https://javaforall.cn