2024.09.26 头插法、尾插法创建单链表

T1

题目描述

请参考 PPT、课本给的例子，给出单链表的数据结构定义，分别利用头插法、尾插法创建单链表，并遍历之及求表长（给出单链表中的元素个数）

在main函数中测试这些操作。本节课实现的操作包括：

• 初始化 InitList(&L)
• 创建链表头插 CreateList_H(&L)、尾插 CreateList_R(&L)
• 遍历 ListTraverse(L)
• 求表长 ListLength(L)

在 main 函数中实现：

1. 头插法创建单链表 A，输入：1, 2, 3, 4, 5。遍历 A，打印 A 的表长。
2. 尾插法创建单链表 B，输入：1, 2, 3, 4, 5。遍历 B，打印 B 的表长。
3. 声明一个单链表 L，初始化 L，打印 L 的表长。

参考作答

本代码中并没有采用课本中倒序输入的方式，而是采用数组输入，并在函数 for 循环中实现倒序的效果。笔者认为这样比较符合一般人的操作习惯，因为假设我要输入 1,2,5,8,1，还需要人类来手动倒序输入实在是违背人性的一种操作。

本代码由于使用了模板函数，故定义和实现文件必须合并，统一在 linkedList.h 内。

定义/实现文件 linkedList.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>
#include <stdexcept>

template <typename T>
struct Node
{
    T data;
    Node* next;
    Node(const T& data) : data(data), next(nullptr) {}
};

template <typename T>
class linkedList
{
private:
    using node = Node<T>;
    node* head;    // 链表头指针
    size_t length; // 当前元素个数

public:
    // 构造函数
    linkedList();

    // 析构函数
    ~linkedList();

    // 返回表内元素个数
    size_t size() const;

    // 清空表
    void clear();

    // 遍历表
    void traverse() const;

    // 头插法创建链表
    void createListHead(const T arr[],size_t size);

    // 尾插法创建链表
    void createListTail(const T arr[], size_t size);
};

// 构造函数
template <typename T>
linkedList<T>::linkedList() : head(nullptr), length(0) {}

// 析构函数
template <typename T>
linkedList<T>::~linkedList()
{
    clear();
}

// 重置表为空表
template <typename T>
void linkedList<T>::clear()
{
    node* current = head;
    while (current)
    {
        node* next = current->next;
        delete current;
        current = next;
    }
    head = nullptr;
    length = 0;
}

// 返回表内元素个数
template <typename T>
size_t linkedList<T>::size() const
{
    return length;
}

// 头插法创建链表
template <typename T>
void linkedList<T>::createListHead(const T arr[], size_t size)
{
    clear();
    for (size_t i = size; i-- > 0;)
    {
        node* newNode = new node(arr[i]);
        newNode->next = head;
        head = newNode;
        length++;
    }
}

// 尾插法创建链表
template <typename T>
void linkedList<T>::createListTail(const T arr[], size_t size)
{
    clear();
    node* tail = nullptr;
    for (size_t i = 0; i < size; i++)
    {
        node* newNode = new node(arr[i]);
        if (tail == nullptr)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail->next = newNode;
            tail = newNode;
        }
        length++;
    }
}

// 遍历表
template <typename T>
void linkedList<T>::traverse() const
{
    node* cur = head;
    while (cur)
    {
        std::cout << cur->data << " ";
        cur = cur->next;
    }
    std::cout << std::endl;
}

#endif // LINKED_LIST_H

主函数 main.cpp

#include "linkedList.h"
#include <iostream>

int main()
{
	// 初始化
	linkedList<int> list;

	// 下面分别演示表 {1,2,3,4,5} 的头插法和尾插法

	int text[5] = { 1,2,5,8,1 };

	// 头插法 //
	std::cout << "头插法：" << std::endl;
	list.createListHead(text, 5);

	// 遍历，求表长
	list.traverse();
	std::cout << list.size();


	// 尾插法 //
	std::cout << "\n尾插法：" << std::endl;
	list.createListTail(text, 5);

	// 遍历
	list.traverse();
	std::cout << list.size();

	return 0;
}

输出

头插法：
1 2 3 4 5
5
尾插法：
1 2 3 4 5
5