欢迎移步博主CSDN:CSDN博客
数据结构----链表
单链表
单链表是用一组任意的存储单元存放线性表的元素,这组存储单元可以连续也可以不连续,甚至可以零散的分布在内存中的任意位置。简单来说就是在逻辑上连续,在物理上不连续的存储单元。
代码实现:(以下代码起始位置为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]. 清华大学出版社.