数据结构之单链表

admin123

2019 年 11 月 01 日

2799 次浏览

暂无评论

加载中

3098字数

学习笔记

欢迎移步博主CSDN：[CSDN博客](https://blog.csdn.net/weixin_42327790/article/details/102862704)

# 数据结构----链表

## 单链表

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

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

```c++
/*
 * @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;
}
```

运行结果：
![image.png](https://www.520315.xyz/usr/uploads/2023/03/807669300.png)

---

## 循环链表

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

暂未进行编码实现

---

## 双链表

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

暂未进行编码实现

---

## 参考文献

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