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

时间：2022-11-25 11:11:28

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

值得注意的是：

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;
}

相关文章