首页 > 其他分享 >数据结构初阶--单链表（讲解+类模板实现）

数据结构初阶--单链表（讲解+类模板实现）

时间：2022-11-25 10:58:08浏览次数：40  
标签：head 单链 -- data pos next 初阶 NULL LinkNode

单链表

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

值得注意的是：

1.链表的在逻辑是连续的，物理上不一定是连续的；
2.现实中节点是从堆上申请的。

链表的实现

链表的单个结点的定义

就像这个图一样，一个空间用了存放数据（数据域），另一个空间用了存放下一个节点的地址（指针域）。

template <class DateType>
struct LinkNode
{
    //数据域
    DateType data;
    //指针域
    LinkNode<DateType>* next;
    //注意两个事项：1.如果程序员提供了有参构造，那么编译器就不会提供默认的构造函数，但是会提供默认的拷贝构造
    //2.注意事项2：如果程序员提供了拷贝构造，那么编译器不会提供默认的构造函数和拷贝构造
    LinkNode(LinkNode<DateType> *ptr = NULL):next(ptr) {  }
    //struct的构造函数，默认参数构造, //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    LinkNode(const DateType& item, LinkNode<DateType>* ptr = NULL)
    {
        next = ptr;
        data = item;
    }
};

链表的小框架

template <class DateType>
class LinkList
{
public:

private:
	//头节点
    LinkNode<DateType>* head;
};

链表的接口

LinkList(); //构造函数,初始化为空链表
LinkList(const DateType &item);//有参构造，初始化头节点
LinkList(const LinkList<DateType>& list);//拷贝构造,拷贝单链表
CreateLink(int n);//创建单链表
~LinkList();//析构函数,单链表的删除
void PushBack(const DateType& data);//尾插
void PopBack();//尾删
void PushFront(const DateType &data)；//头插
void PopFront();//头删
int Length()const;//求单链表的长度
bool GetElem(int pos, DateType& data);//获得pos位置的元素
LinkNode<DateType>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL
bool Insert(int pos, const DateType &data);//在序号pos位置插入元素值为data的结点
bool Delete(int pos, DateType& data);//删除pos位置的结点，并且返回结点
LinkNode<DateType>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL
void Clear();//清空链表
void PrintList()const;//输出单链表所有结点的元素值
void Exchangedata(int pos1, int pos2);//进行两结点元素值的交换

构造和析构

1.无参构造函数：没什么好说的，用new从堆分配一个结点的空间给我们都头结点指针，注意检查堆是否满是一个很好的习惯

2.含参构造函数：初始化头节点指向第一个结点

3.析构函数（单链表的删除）：单链表的删除很简单用两个指针，从头结点开始，一前一后依次释放申请的内存即可

4.拷贝构造：操作都很简单，依次分配内存拷贝链接即可，类似于链表的构建。区别在于拷贝构造还没有LinkList对象，需要创建，而赋值已经有了LinkList对象，需要将其链表删除再重新构造

    //构造函数,初始化为空链表
    LinkList()
    {
        head = new LinkNode<DateType>;
        if (head == NULL)
        {
            cout << "内存分配失败" << endl;
            exit(-1);
        }
    }
    //有参构造，初始化头节点
    LinkList(const DateType &item)
    {
        //LinkNode会调用构造函数，初始化结点内的内容
        head = new LinkNode<DateType>();
        LinkNode<DateType> *p = new LinkNode<DateType>(item);
        head->next = p;
        if (head == NULL)
        {
            cout << "内存分配失败" << endl;
            exit(-1);
        }
    }
    //拷贝构造,拷贝单链表
    LinkList(const LinkList<DateType>& list)
    {
        LinkNode<DateType>* p = list.head->next;
        if (p == NULL)
        {
            cout << "内存分配失败" << endl;
            exit(-1);
        }
        head = new LinkNode<DateType>;
        LinkNode<DateType>* h = head;
        while (p != NULL)
        {
            LinkNode<DateType>* t = new LinkNode<DateType>;
            h->next = t;
            t->data = p->data;
            p = p->next;
            h = h->next;
        }
    }
    //析构函数,单链表的删除
    ~LinkList()
    {
        //申请一个指针指向头节点
        LinkNode<DateType>* cur = head;
        LinkNode<DateType>* next;
        while (cur)
        {
            next = cur->next;
            delete cur;
            cur = next;
        } 
    }

尾插

首先，我们先来实现一个尾插的接口，尾插就是在链表的尾部插入一个节点。
在进行尾插的时候我们要考虑的几点：

  1. 此时链表是否为空，如果为空我们应该怎么做，不为空又应该怎么做，这两种情况我们要分开讨论；
  2. 如何申请节点，是在堆上还是栈上？

为了更好的理解尾插，我们先看一个动图展示：

void PushBack(const DateType& data)
   {
      LinkNode<DateType>* p = new LinkNode<DateType>(data);
      if (head->next == NULL)
      {
          head->next = p;
      }
      else
      {
          LinkNode<DateType>* cur = head;
          while (cur->next != NULL)
          {
              cur = cur->next;
          }
          cur->next = p;
      }
   }

创建单链表

首先定义一个指向Head的指针q；
然后不断重复以下三个步骤完成单链表的构造：
①用new申请一个LinkNode的空间返回指针p，并输入数据元素；
②q->next=p，将q指针对应结点的后继修改为p；
③q=q->next,将指针指向其直接后继，这样一个结点就被链接进了链表之中

//创建单链表
    void CreateLink(int n)
    {
        LinkNode<DateType>* q = head;
        int* nodetemp = new int[n];
        for (size_t i = 0; i < n; i++)
        {
            cout << "Enter the element:  " << endl;
            cin >> nodetemp[i];
        }
        //尾插法
        for (size_t i = 0; i < n; i++)
        {
            LinkNode<DateType>* p = new LinkNode<DateType>;
            p->data = nodetemp[i];
            p->next = q->next;
            q->next = p;
            q = q->next;
        }
        delete[] nodetemp;
    }

尾删

尾删无非就是在链表的尾部删除一个节点，听起来很简单，但是有很多细节是我们要注意的，我们要分三种情况来进行讨论：

  1. 没有节点
  2. 只有一个节点
  3. 两个及两个以上的节点

先看动图演示：

//尾删
void PopBack()
{
    //分三种情况
    //1.没有结点
    if (head->next == NULL)
    {
        return;
    }
     //2.只有一个结点
    else if (head->next->next == NULL) {
        delete head->next;
        head->next= NULL;
     }
     //3.两个以及两个以上的结点
     else
     {
         LinkNode<DateType>* prev = NULL;
         LinkNode<DateType>* cur = head;
         while (cur->next != NULL)
         {
             prev = cur;
             cur = cur->next;
         }
         delete cur;
         cur = NULL;
         prev->next = NULL;
     }
}

头插

先看动图演示：

//头插
void PushFront(const DateType &data)
{
    LinkNode<DateType>* p = new LinkNode<DateType>(data);
    p->next = head->next;
    head->next = p;
}

头删

头删就要分情况讨论：

  1. 链表为空
  2. 链表不为空

先看动图演示：

//头删
void PopFront()
{
     //分两种情况
     if (head->next == NULL)
     {
         return;
     }
     else
     {
         LinkNode<DateType>* p = head->next;
         head->next = p->next;
         delete p;
         p = NULL;
    }
}

定位位置

封装一个函数，返回第pos位置的地址，在下面用得到

//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL
    LinkNode<DateType>* Locate(int pos)
    {
        int i = 0;
        LinkNode<DateType>* p = head;
        if (pos < 0)
            return NULL;
        while (NULL != p && i < pos)
        {
            p = p->next;
            i++;
        }
        return p;
    }

单链表任意位置插入

//在序号index位置插入元素值为data的结点
    bool Insert(int pos, const DateType &data)
    {
        LinkNode<DateType>* p = Locate(pos);
        if (p == NULL)
        {
            return false;
        }
        LinkNode<DateType>* node = new LinkNode<DateType>(data);
        if (NULL == node)
        {
            cerr << "分配内存失败!" << endl;
            exit(-1);
        }
        node->next = p->next;
        p->next = node;
        return true;
    }

单链表的任意位置删除

先看动图演示：

//删除pos位置的结点，并且返回结点
    bool Delete(int pos, DateType& data)
    {
        LinkNode<DateType>* p = Locate(pos-1);
        if (NULL == p || NULL == p->next)
            return false;
        LinkNode<DateType>* del = p->next;
        p->next = del->next;
        data = del->data;
        delete del;
        return true; 
    }

打印链表

//输出单链表所有结点的元素值
    void PrintList()const
    {
        int count = 0;
        LinkNode<DateType>* p = head->next;
        while (p)
        {
            cout << p->data<<"  ";
            p = p->next;
            //打印十个元素换行
            if (++count % 10 == 0)
            {
                cout << endl;
            }
        }
    }

清空链表

//清空链表
    void Clear()
    {
        //所有结点的next清空，最后头节点head清空
        LinkNode<DateType>* p = NULL;
        while (head->next != NULL)
        {
            p = head->next;
            head->next = p->next;
            delete p;
        }
    }

单链表的长度

    //求单链表的长度
    int Length()const
    {
        int count = 0;
        LinkNode<DateType>* p = head;
        while (p->next != NULL)
        {
            p = p->next;
            ++count;
        }
        return count;
    }

两结点元素值的互换

    //进行两结点元素值的交换
    void Exchangedata(int pos1, int pos2)
    {
        LinkNode<DateType>* p1 = Locate(pos1);
        LinkNode<DateType>* p2 = Locate(pos2);
        DateType tmp = p1->data;
        p1->data = p2->data;
        p2->data = tmp;
    }

整体代码以及测试

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
using namespace std; //标准命名空间
template <class DateType>
struct LinkNode
{
    //数据域
    DateType data;
    //指针域
    LinkNode<DateType>* next;
    //注意两个事项：1.如果程序员提供了有参构造，那么编译器就不会提供默认的构造函数，但是会提供默认的拷贝构造
    //2.注意事项2：如果程序员提供了拷贝构造，那么编译器不会提供默认的构造函数和拷贝构造
    LinkNode(LinkNode<DateType> *ptr = NULL):next(ptr) {  }
    //struct的构造函数，默认参数构造, //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    LinkNode(const DateType& item, LinkNode<DateType>* ptr = NULL)
    {
        next = ptr;
        data = item;
    }
};
template <class DateType>
class LinkList
{
public:
    //构造函数,初始化为空链表
    LinkList()
    {
        head = new LinkNode<DateType>;
        if (head == NULL)
        {
            cout << "内存分配失败" << endl;
            exit(-1);
        }
    }
    //有参构造，初始化头节点
    LinkList(const DateType &item)
    {
        //LinkNode会调用构造函数，初始化结点内的内容
        head = new LinkNode<DateType>();
        LinkNode<DateType> *p = new LinkNode<DateType>(item);
        head->next = p;
        if (head == NULL)
        {
            cout << "内存分配失败" << endl;
            exit(-1);
        }
    }
    //拷贝构造,拷贝单链表
    LinkList(const LinkList<DateType>& list)
    {
        LinkNode<DateType>* p = list.head->next;
        if (p == NULL)
        {
            cout << "内存分配失败" << endl;
            exit(-1);
        }
        head = new LinkNode<DateType>;
        LinkNode<DateType>* h = head;
        while (p != NULL)
        {
            LinkNode<DateType>* t = new LinkNode<DateType>;
            h->next = t;
            t->data = p->data;
            p = p->next;
            h = h->next;
        }
    }
    //创建单链表
    void CreateLink(int n)
    {
        LinkNode<DateType>* q = head;
        int* nodetemp = new int[n];
        for (size_t i = 0; i < n; i++)
        {
            cout << "Enter the element:  " << endl;
            cin >> nodetemp[i];
        }
        //尾插法
        for (size_t i = 0; i < n; i++)
        {
            LinkNode<DateType>* p = new LinkNode<DateType>;
            p->data = nodetemp[i];
            p->next = q->next;
            q->next = p;
            q = q->next;
        }
        delete[] nodetemp;
    }
    //析构函数,单链表的删除
    ~LinkList()
    {
        //申请一个指针指向头节点
        LinkNode<DateType>* cur = head;
        LinkNode<DateType>* next;
        while (cur)
        {
            next = cur->next;
            delete cur;
            cur = next;
        } 
    }
    //尾插
   void PushBack(const DateType& data)
    {
       LinkNode<DateType>* p = new LinkNode<DateType>(data);
       if (head->next == NULL)
       {
           head->next = p;
       }
       else
       {
           LinkNode<DateType>* cur = head;
           while (cur->next != NULL)
           {
               cur = cur->next;
           }
           cur->next = p;
       }
    }
   //尾删
   void PopBack()
   {
       //分三种情况
       //1.没有结点
       if (head->next == NULL)
       {
           return;
       }
       //2.只有一个结点
       else if (head->next->next == NULL) {
           delete head->next;
           head->next= NULL;
       }
       //3.两个以及两个以上的结点
       else
       {
           LinkNode<DateType>* prev = NULL;
           LinkNode<DateType>* cur = head;
           while (cur->next != NULL)
           {
               prev = cur;
               cur = cur->next;
           }
           delete cur;
           cur = NULL;
           prev->next = NULL;
       }
   }
    //头插
   void PushFront(const DateType &data)
   {
       LinkNode<DateType>* p = new LinkNode<DateType>(data);
       p->next = head->next;
       head->next = p;
   }
    //头删
   void PopFront()
   {
       //分两种情况
       if (head->next == NULL)
       {
           return;
       }
       else
       {
           LinkNode<DateType>* p = head->next;
           head->next = p->next;
           delete p;
           p = NULL;
       }
   }
    //求单链表的长度
    int Length()const
    {
        int count = 0;
        LinkNode<DateType>* p = head;
        while (p->next != NULL)
        {
            p = p->next;
            ++count;
        }
        return count;
    }
    //得到序号为index的结点元素值
    bool GetElem(int pos, DateType& data)
    {
        LinkNode<DateType>* p = Locate(pos);
        if (p == NULL)
        {
            return false;
        }
        data = p->data;
        return true;
    }
    //返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL
    LinkNode<DateType>* Locate(int pos)
    {
        int i = 0;
        LinkNode<DateType>* p = head;
        if (pos < 0)
            return NULL;
        while (NULL != p && i < pos)
        {
            p = p->next;
            i++;
        }
        return p;
    }
    //在序号index位置插入元素值为data的结点
    bool Insert(int pos, const DateType &data)
    {
        LinkNode<DateType>* p = Locate(pos);
        if (p == NULL)
        {
            return false;
        }
        LinkNode<DateType>* node = new LinkNode<DateType>(data);
        if (NULL == node)
        {
            cerr << "分配内存失败!" << endl;
            exit(-1);
        }
        node->next = p->next;
        p->next = node;
        return true;
    }
    //删除pos位置的结点，并且返回结点
    bool Delete(int pos, DateType& data)
    {
        LinkNode<DateType>* p = Locate(pos-1);
        if (NULL == p || NULL == p->next)
            return false;
        LinkNode<DateType>* del = p->next;
        p->next = del->next;
        data = del->data;
        delete del;
        return true; 
    }
    //清空链表
    void Clear()
    {
        //所有结点的next清空，最后头节点head清空
        LinkNode<DateType>* p = NULL;
        while (head->next != NULL)
        {
            p = head->next;
            head->next = p->next;
            delete p;
        }
    }
    //输出单链表所有结点的元素值
    void PrintList()const
    {
        int count = 0;
        LinkNode<DateType>* p = head->next;
        while (p)
        {
            cout << p->data<<"  ";
            p = p->next;
            //打印十个元素换行
            if (++count % 10 == 0)
            {
                cout << endl;
            }
        }
    }
    //进行两结点元素值的交换
    void Exchangedata(int pos1, int pos2)
    {
        LinkNode<DateType>* p1 = Locate(pos1);
        LinkNode<DateType>* p2 = Locate(pos2);
        DateType tmp = p1->data;
        p1->data = p2->data;
        p2->data = tmp;
    }
private:
    //头节点
    LinkNode<DateType>* head;
};
/*
LinkList(); //构造函数,初始化为空链表
LinkList(const DateType &item);//有参构造，初始化头节点,      有问题
LinkList(const LinkList<DateType>& list);//拷贝构造,拷贝单链表
CreateLink(int n);//创建单链表
~LinkList();//析构函数,单链表的删除
void PushBack(const DateType& data);//尾插
void PopBack();//尾删
void PushFront(const DateType &data)；//头插
void PopFront();//头删
int Length()const;//求单链表的长度
bool GetElem(int pos, DateType& data);//获得pos位置的元素
LinkNode<DateType>* Locate(int pos);//返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL
bool Insert(int pos, const DateType &data);//在序号pos位置插入元素值为data的结点
bool Delete(int pos, DateType& data);//删除pos位置的结点，并且返回结点
void Clear();//清空链表
void PrintList()const;//输出单链表所有结点的元素值
void Exchangedata(int pos1, int pos2);//进行两结点元素值的交换
*/
int main()
{

    LinkList<int> list;
    list.CreateLink(5);
    list.PrintList();
    cout << "-------------------" << endl;
    list.PushBack(299);
    list.PrintList();
    cout << "-------------------" << endl;
    list.PopBack();
    list.PrintList();
    cout << "-------------------" << endl;
    list.PushFront(19);
    list.PrintList();
    cout << "-------------------" << endl;
    list.PopFront();
    cout << list.Length() << endl;
    list.PrintList();
    cout << "-------------------" << endl;
    int b = 0;
    list.GetElem(2,b);
    cout << b << endl;
    list.PrintList();
    cout << "-------------------" << endl;
    list.Insert(2, 99);
    list.PrintList();
    cout << "-------------------" << endl;
    list.Exchangedata(1, 2);
    list.PrintList();
    cout << "-------------------" << endl;
    list.Clear();
    list.PrintList();
    cout << "-------------------" << endl;
    LinkList<int> list2(list);
    list2.PrintList();
    LinkList<int> list(90);
    list.PrintList();
	system("pause");
	return EXIT_SUCCESS;
}

标签：head,单链,--,data,pos,next,初阶,NULL,LinkNode
From： https://www.cnblogs.com/yzsn12138/p/16924424.html

相关文章

  • 重构：改善既有代码的设计 第三章 读书笔记
    目录代码的坏味道3.1神秘命名(MysteriousName)需要好的命名方式，有意义的命名方式3.2重复代码(DuplicatedCode)场景方法同一个类中出现重复代码提......
  • 浅谈cookie、sessionStorage、localStorage的生命周期
    最近忙于毕业设计，要写一个用户行为分析平台，需要合理使用这三种技术来追踪用户行为，于是查询相关资料并做了些小测试来熟悉这三种技术。我将自己学习内容和使用时遇到的一些......
  • 软件测试学习思维导图
    1、测试分析图： 2、软件测试全景图： 3、软件开发流程图： ......
  • C++自定义字面量用法（operator""）
    下面举个c++内部的字面量用的例子：unsignedintv1=20U;longv2=30L;unsignedlongv3=40UL;是不是很好奇数字后面U、L、UL。在举个栗子实现字面量方法：在c+......
  • Git命令 reset 和 revert 的区别
    前言在团队开发中，使用Git作为版本开发工具，可以便捷地协同多人管理并行开发，但是由于自己或者其他人代码提交污染了远程分支，就需要对远程代码进行恢复操作，Git提供了res......
  • Zabbix与乐维监控对比分析（一）——架构、性能篇
    近年来，Zabbix凭借其近乎无所不能的监控及优越的性能一路高歌猛进，在开源监控领域独占鳌头；而作为后起的新锐IT监控平台——乐维监控，则不断吸收Zabbix，Prometheus等优秀开源平......
  • FlowPortal-BPM——获取树状结构的物料分类
    ///<summary>///获取物料分类-树形结构///</summary>///<returns></returns>publicJObjectgetMaterialBasicClass(HttpContextcontext)......
  • JAVA收录影记
    Controller层代码就该这么写，简洁又优雅描述了定义项目控制器时正确的打开方式，便于统一对请求参数、响应参数、异常做统一的处理，让控制器更多关注参数的接收和响应的返回......
  • KingbaseES数据库使用KWR性能报告
    SYS_KWR是KingbaseES自动负载信息库（KingbaseAutoWorkloadRepertories）的简称，它通过周期性自动记录性能统计相关的快照，分析出KingbaseES的操作系统运行环境、数......
  • iTOP3A5000_7A2000开发板龙芯全国产处理器LoongArch架构核心主板
       主要参数    处理器:龙芯3A5000主频:2.3GHz-2.5GHz桥片:7A2000内存:8GB、16GBDDR4带ECC纠错（配置可选）系统:Loongnix典型功耗:35W核心板:1......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99