欢迎移步博主小站：白亮吖雅黑丫の小站

数据结构之线性表的实现（二）

数据结构----链表单链表循环链表双链表参考文献

数据结构----链表

单链表

单链表是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散的分布在内存中的任意位置。简单来说就是在逻辑上连续，在物理上不连续的存储单元。

代码实现：（以下代码起始位置为0）

/* * @Author: zbl * @Date: 2019-11-01 16:03:37 * @Last Modified by: zbl * @Last Modified time: 2019-11-01 17:28:40 */ #include <iostream> using namespace std; //定义结点 template <class T> struct Node{ T data; Node<T>* next = NULL; }; //单链表的定义 template<class T> class LinkList{ private: //头结点 Node<T>* head; //链表长度 int length; public: //无参构造函数 LinkList(){} //有参构造函数 LinkList(T a[],int n); //析构函数 ~LinkList(); //定位元素x的位置 int locate(T x); //获取位置i的元素 T get(int i); //在i位置插入元素x void insert(int i , T x); //删除i位置的元素 T Delete(int i); //打印单链表 void display(); //获取单链表长度 int getLength(){return length;} }; //有参构造函数 template<class T> LinkList<T>::LinkList(T a[],int n){ length = n; Node<T>* tmp = new Node<T>(); head = tmp; int i = 0; while(i<n){ Node<T>* node = new Node<T>(); node->data = a[i++]; tmp->next = node; tmp = tmp->next; } delete tmp; //下标从0开始 head = head->next; } //析构函数 template <class T> LinkList<T>::~LinkList(){ length = 0; Node<T>* p = head; while(p->next != NULL){ Node<T>* tmp = p; p = p->next; tmp->next = NULL; delete tmp; } delete p; head = NULL; } //定位元素x的位置 template <class T> int LinkList<T>::locate(T x){ if(head == NULL) throw "链表为空!"; Node<T>* next = head; int i = 0; while(next != NULL){ if(next->data == x) return i; ++i; next = next->next; } //未找到 return -1; } //获取位置i的元素 template <class T> T LinkList<T>::get(int i){ if(i < 0) throw "下溢"; if(i > length - 1) throw "上溢"; Node<T>* next = head; while(i--){ next = next->next; } return next->data; } //在i位置插入元素x template <class T> void LinkList<T>::insert(int i , T x){ if(i < 0) throw "下溢"; if(i > length) throw "上溢"; //新建结点 Node<T>* node = new Node<T>(); node->data = x; //头插 if(i == 0){ node->next = head; head = node; } else{ Node<T>* tmp = head; while(--i){ tmp = tmp->next; } node->next = tmp->next; tmp->next = node; } length++; } //删除i位置的元素 template <class T> T LinkList<T>::Delete(int i){ if(i < 0) throw "下溢"; if(i > length - 1) throw "上溢"; Node<T>* del = head; //头删 if(i == 0){ head = head->next; } else{ Node<T>* tmp = head; while (--i) { tmp = head->next; } del = tmp->next; tmp->next = tmp->next->next; } T x = del->data; //释放空间 delete del; length--; return x; } //打印单链表 template <class T> void LinkList<T>::display(){ Node<T>* tmp = head; while(tmp != NULL) { cout<<tmp->data<<" "; tmp = tmp->next; } cout<<endl; } int main() { int a[10] = {1,2,3,4,5,6,7,8,9,10}; LinkList<int> linkList(a,10); linkList.display(); cout<<"头插：";linkList.insert(0,0);linkList.display();cout<<linkList.getLength()<<endl; cout<<"尾插：";linkList.insert(11,11);linkList.display();cout<<linkList.getLength()<<endl; cout<<"插入：";linkList.insert(2,22);linkList.display();cout<<linkList.getLength()<<endl; cout<<"删除位置2的元素"<<linkList.Delete(2)<<" ";linkList.display();cout<<linkList.getLength()<<endl; cout<<"查找位置为2的元素"<<linkList.get(2)<<endl;cout<<linkList.getLength()<<endl; cout<<"查找元素2所在的位置"<<linkList.locate(2)<<endl;cout<<linkList.getLength()<<endl; return 0; }

运行结果：

---

循环链表

在单链表的基础上，如果将终端节点的指针域由空指针改为指向头结点，就使得整个链表形成了一个环，这种头尾相接的单链表称为循环链表。

暂未进行编码实现

---

双链表

在单链表的基础上，添加一个指向其前驱结点的指针域，这样就形成了双链表。双链表使得找前驱结点变得简单。

暂未进行编码实现

---

参考文献

王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社.