数据结构实验二.doc

《数据结构》实验报告二 "学校： " "班级： " "学号： " "姓名： " "日期： " "程序名： " 一、上机实验的问题和要求： 单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的 查找、插入与删除。具体实现要求： 1. 从键盘输入20个整数，产生不带表头的单链表，并输入结点值。 2. 从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示"找到了"；否则 ，则显示"找不到"。 3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在 对应位置上，输出单链表所有结点值，观察输出结果。 4. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果 。 5. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有 结点值，观察输出结果。 6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。 7. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。 8. （ ）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而 数据结构实验二主要关注的是单链表的操作，包括查找、插入和删除等基本操作，以及对链表的变形处理。单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据元素和一个指向下一个节点的指针。在这个实验中，我们将详细探讨这些操作的实现。 我们需要创建一个不带表头结点的单链表。这个过程可以通过从键盘接收20个整数，然后依次插入链表中来完成。每个新插入的节点会连接到链表的末尾，直到形成一个包含20个元素的链表。 接下来是查找操作。用户输入一个整数，程序需要遍历链表，检查每个节点的值是否与输入值相匹配。如果找到匹配的节点，显示“找到了”，否则显示“找不到”。这个操作涉及到链表的遍历，通常从头结点开始，逐个检查节点直到找到目标或遍历完整个链表。 插入操作要求用户输入插入位置（索引）和值。在找到相应位置后，创建一个新节点，将值存储在新节点的数据域中，然后将新节点插入到链表中。插入操作可能涉及修改多个节点的指针以维护链表的正确链接。 删除操作同样需要用户输入要删除的节点位置。删除节点时，可能需要更新前一个节点的指针以指向被删除节点的下一个节点，从而断开被删除节点的连接。 在链表中删除重复的结点，需要遍历链表，一旦发现重复的值，就删除该节点，确保最终链表中的所有节点值都是唯一的。 删除所有数据值为偶数的节点，需要检查每个节点的值，如果值为偶数，则将其从链表中移除。 将单链表转换为带表头结点的循环链表，需要在链表末尾添加一个指针，使其指向链表的头部，形成一个闭合的环。 实验中的挑战是将单链表分解为两个新的单链表A和B，A链表包含原链表中序号为奇数的元素，B链表包含序号为偶数的元素，同时保持原有的相对顺序。这个操作需要两次遍历链表，一次构建A链表，一次构建B链表。 程序设计的基本思想是利用指针操作来实现链表的各种操作。数据结构方面，我们使用了带头结点的单链表，头结点的data域用于存储链表的长度。输入/输出设计中，用户通过键盘输入数据并选择操作，程序通过控制台输出结果。符号名说明包括对各个函数如CreateList、Locate、InsertList、DeleteList等的解释，它们分别对应链表的创建、查找、插入、删除等操作。 在实现这些操作的算法时，可能需要考虑到边界条件和错误处理，例如空链表处理、非法索引检测等。通过这样的实验，学生可以深入理解链表这一重要数据结构，掌握其操作技巧，并提升实际编程能力。