# 2850 题解

题解 # 2850

由于制图麻烦,本题解将以文字叙述。

解题思路

问题分析

这道题主要包含五个过程

init_linked_list
read_structs_into_list
insertion_sort
write_list_into_structs
clear_list

涉及简单链表操作和输入输出问题

数据结构

链表所有单元均以指针形式存放

以结构组定义学生数据

struct student
{
    long id;
    string name;
    string dept;
    string group;
    string type;
    string email;
    long long cell;
};

以双向链表存储数据

struct link_node
{
    student * data;
    link_node * next;
    link_node * prev;
};

并以头尾哨兵维护链表

link_node * init_linked_list()
{
    link_node * head = new link_node;
    link_node * tail = new link_node;

    head->next = tail;
    head->prev = NULL;
    head->data = NULL;

    tail->next = NULL;
    tail->prev = head;
    tail->data = NULL;

    return head;
}

标准输入输出

读取

输入每个学生信息占一行,每个字段以制表符 \t 分割,因此以文件结束 EOF 作为数据末标志,即 while (not cin.eof()),并在输入时不断更新链表信息

node->data = stu;
node->next = tail;
node->prev = ptr;
ptr->next = node;
tail->prev = node;
ptr = node;

即先维护新增节点 node 的链接,再将前后指针指向 node

输出

定义了顺序输出和倒序输出两种方案,以参数 reverse 作为标志

对于顺序输出,从 head 遍历到指针尾 tail 即可

if (head->next->next == NULL)
{
    cout << "EMPTY!" << endl;
}
else
{
    link_node * ptr = head->next;
    while (ptr->next != NULL)
    {
        print_student(ptr->data);
        ptr = ptr->next;
    }
}

对于倒序输出,采用递归的方案

if (head->next == NULL)
{
    return;
}
else
{
    if (head->prev == NULL)
    {
        write_list_into_structs(head->next, reverse = true);
    }
    else
    {
        write_list_into_structs(head->next, reverse = true);
        print_student(head->data);
    }
}

插入排序

算法相对朴素,不断向前比较键值大小,为保持排序稳定注意在相等时结束比较

需要注意的是链表交换数据块的操作

node->prev->next = node->next;
node->next->prev = node->prev;
node->next = pos->next;
node->prev = pos;
pos->next->prev = node;
pos->next = node;

先把当前块 node 的前后两块链接,然后维护 node 使其前后指针指向正确区块,再将前后区块指向 node 即可

释放内存

从头遍历链表并释放内存,最后重新头尾相接

link_node * ptr = head;
link_node * node = ptr;
while (ptr->next != NULL)
{
    node = ptr->next;
    delete ptr;
    ptr = node;
}
head->next = ptr;
ptr->prev = head;

测试过程

完整性测试

首先顺序输出,证明顺序指针完整

由于插入排序依赖倒序指针,因此再次插入排序,证明倒序指针完整

稳定性测试

构建数据进行测试

内存清理测试

在清理完内存后再次输出,若为空则内存清理完毕

数据结构作用

双向链接

在插入排序中需要不断与前一个数据块比较顺序,若为单向指针则必须不断从头遍历,而双向指针可以直接寻找到上一个数据块

头尾哨兵

每次对链表操作都需要头哨兵作为内存地址开始

尾哨兵在测试中发挥了一些作用

添加新评论