《数据结构实验报告——单链表的插入与删除》
数据结构是计算机科学中的核心概念，它涉及到如何高效地组织和存储数据以便于处理。在本实验报告中，我们将聚焦于单链表这一数据结构，探讨如何进行插入和删除操作，并通过C语言实现相关算法。
单链表是一种线性数据结构，每个元素称为结点，包含两部分：数据域（存储信息）和指针域（指向下一个结点）。实验的目标是理解和掌握线性表的逻辑结构，特别是链式存储结构，以及单链表的基本操作和它们的时间复杂性。
实验要求建立一个数据域为字符串的单链表，其中不允许有重复的字符串。具体任务包括：
1. 理解和分析给出的示例程序，该程序包含以下功能：
- 不允许插入重复字符串。
- 根据输入的字符串找到相应结点并删除。
2. 调试程序并设计测试数据，如：“bat”，“cat”，“eat”，“fat”，“hat”，“jat”，“lat”，“mat”，“#”（“#”作为输入结束标志）。
3. 修改程序以增加新功能：
- 添加插入结点的功能，采用头插入法。
- 改变建立链表的方法，从尾插入法改为头插入法。
程序代码中，定义了一个结构体`ListNode`表示链表结点，包含一个字符串数据域`data`和一个指向下一个结点的指针`next`。`LinkList`是一个指向`ListNode`类型的指针，用于表示链表。
实验的主要步骤如下：
1. 使用`CreatListR1()`函数通过尾插入法创建一个带头结点的单链表。
2. 使用`LocateNode()`函数查找链表中指定值的结点。
3. `DeleteList()`函数根据输入的字符串删除相应结点。
4. `printlist()`函数遍历并打印链表的所有元素。
5. `DeleteAll()`函数删除所有结点并释放内存。
6. `AddNode()`函数在链表头部插入新的结点，采用头插入法。
在主函数`main()`中，首先调用`CreatList()`使用头插入法建立链表，然后打印链表内容。用户可以选择删除或添加结点，程序会根据用户输入执行相应操作。所有结点会被删除，内存得到释放。
通过这个实验，我们不仅可以掌握单链表的创建、遍历、查找和修改等基本操作，还能了解到这些操作的时间复杂性。例如，头插入法插入结点的时间复杂度为O(1)，而查找和删除结点通常需要O(n)的时间，因为可能需要遍历整个链表。这些基础知识对于理解和优化算法至关重要，对日后的编程工作有着深远的影响。
