中山大学数据结构与算法实验报告2
|
113
|
0
|
学习笔记,实验报告,数据结构与算法

3607 字
|
17 分钟

第一题 Delete Duplicate

1.实验题目

2. 实验目的

本实验的主要目的是实现删除单链表中所有冗余节点的高效算法，使得每个数据域相同的节点仅保留一个。通过本实验，学生能够：

  1. 理解链表数据结构及其操作。
  2. 掌握遍历链表、删除节点和内存管理的基本操作。
  3. 提高算法设计和实现的能力，熟悉链表操作的基本技巧。

3. 算法设计

为实现删除冗余节点的功能，我们遍历递增有序的链表，检测相邻节点的数据是否相同。具体的算法步骤如下：

  1. 输入处理:

    • 如果链表为空，直接返回。

  2. 指针遍历:

    • 使用指针cur从链表头开始遍历。
    • 对于每个节点，判断当前节点与其下一个节点的值是否相同。

  3. 删除冗余节点:

    • 如果相同，则将cur->next指向下下一个节点，从而跳过冗余节点，并释放内存。
    • 如果不同，则将cur移动到下一个节点。

  4. 结束处理:

    • 重复上述过程，直到遍历完整个链表。

  5. 时间复杂度：

  • 由于链表只需要遍历一次，因此时间复杂度为O(n)，其中n为链表中节点的数量。
  1. 代码实现：
#include <iostream>
#include "LinkNode.h"
using namespace std;

void delete_duplicate(LinkList &head) {
    if (head == nullptr) return;
    LinkNode *cur = head;
    while (cur->next) {
        if (cur->data == cur->next->data) {
            LinkNode *temp = cur->next; // 保存重复节点
            cur->next = cur->next->next; // 跳过重复节点
            delete temp; // 释放重复节点内存
        } else {
            cur = cur->next; // 移动到下一个节点
        }
    }
    return;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同结构的链表：

  • 输入链表：

    • 1 -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> 5

  • 输出链表：

    • 1 -> 2 -> 3 -> 4 -> 5

程序运行

  • 使用上述函数delete_duplicate()对链表进行处理，可以看到冗余节点被正确删除，只保留了每个数值的一个节点。
  • 通过多次测试，包括链表为空、链表中没有重复元素、链表中所有元素都相同等情况，程序均能得到正确的结果。

5. 实验总结与心得

通过本次实验，我进一步掌握了链表的数据结构及其操作，尤其是在删除节点和内存管理方面有了更深入的理解。由于链表的特点，不同于数组，删除节点时需要特别注意指针的操作，以及内存的释放，否则很容易出现内存泄漏的问题。

在本实验中，链表中的元素是递增有序排列的，因此可以通过简单的一次遍历就完成删除操作，这种有序性的利用使得算法更加高效。在实际应用中，充分利用数据的特点往往能够设计出更为简洁、高效的算法，这是本次实验的重要收获之一。

此外，通过对边界情况的测试，例如空链表或全部元素相同的链表，我学会了在设计代码时要考虑各种可能的情况，使代码更加健壮可靠。

第二题 Insert for single link list with head node

1.实验题目

 

2. 实验目的

本实验的主要目的是实现带虚拟头结点的单链表中插入新节点的算法。通过本实验，学生能够：

  1. 理解单链表的基本结构及其操作。
  2. 掌握如何在指定位置插入新节点，熟悉链表的插入操作。
  3. 提高对链表操作的实现能力，熟悉指针操作的基本技巧。

3. 算法设计

为实现带虚拟头结点的单链表中插入新节点的功能，我们采用指针遍历链表找到插入位置，并在相应位置插入新节点。具体的算法步骤如下：

  1. 输入处理:

    • 接收待插入的值toadd以及插入的位置pos。
    • 确保pos大于0并且小等于链表实际节点数。

  2. 节点创建:

    • 创建一个新节点p，并将其数据域赋值为toadd。

  3. 指针遍历:

    • 使用指针cur从链表头开始遍历，找到第pos-1个节点。
    • 将新节点插入到第pos个位置之前。

  4. 插入操作:

    • 将新节点的next指针指向cur->next。
    • 将cur->next指向新节点p。

  5. 时间复杂度：

  • 由于需要遍历链表找到插入位置，因此时间复杂度为O(n)，其中n为链表中节点的数量。
  1. 代码实现：
#include <iostream>
#include "ListNode.h"
using namespace std;

void List::insert(int toadd, int pos) {
    ListNode *p = new ListNode;
    p->data = toadd;
    ListNode *cur = head;
    pos--;
    while (pos--) {
        cur = cur->next;
    }
    p->next = cur->next;
    cur->next = p;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同结构的链表：

  • 输入链表：

    • 1 -> 2 -> 3 -> 5
    • 插入值：4，插入位置：4

  • 输出链表：

    • 1 -> 2 -> 3 -> 4 -> 5

程序运行

  • 使用上述函数insert()对链表进行处理，可以看到新节点被正确插入到指定位置。
  • 通过多次测试，包括插入到链表头部、中间、尾部，以及插入空链表等情况，程序均能得到正确的结果。

5. 实验总结与心得

通过本次实验，我进一步掌握了链表的数据结构及其插入操作，尤其是在链表中间插入节点时对指针的操作有了更深入的理解。在链表操作中，插入节点涉及到多个指针的修改，稍有不慎就可能导致链表结构损坏，因此需要特别注意指针的正确性。

在本实验中，带虚拟头结点的链表使得插入操作更加简便，避免了对链表头节点的特殊处理。在实际应用中，使用带虚拟头结点的链表往往能够简化代码逻辑，提高代码的可读性和可维护性。

此外，通过对边界情况的测试，例如插入空链表或插入到链表末尾，我学会了在设计代码时要考虑各种可能的情况，使代码更加健壮可靠。

第三题 Loops in the Linked List

1.实验题目

2. 实验目的

本实验的主要目的是实现一个函数来检查给定链表中是否存在环。通过本实验，学生能够：

  1. 了解链表数据结构的循环检测问题及其实际应用。
  2. 掌握使用快慢指针解决链表中环检测问题的技巧。
  3. 提高链表操作的实现能力，特别是边界条件的处理能力。

3. 算法设计

为实现对链表环的检测，我们使用快慢指针（Floyd 判圈算法）的方法来遍历链表。具体的算法步骤如下：

  1. 输入处理:

    • 首先对输入链表的头节点进行检查。
    • 如果链表为空或者链表只有一个节点，则直接返回false，表示链表中不存在环。

  2. 快慢指针遍历:

    • 初始化两个指针，slow和fast，都指向链表的头部。
    • slow每次向前移动一步，而fast每次向前移动两步。
    • 在遍历的过程中，如果两个指针相遇，说明链表中存在环，返回true。
    • 如果fast或者fast->next为空，说明已经遍历到链表的末尾且没有环，返回false。

  3. 时间复杂度：

  • 由于快慢指针最多遍历链表一次，因此时间复杂度为O(n)，其中n为链表中的节点数量。
  1. 代码实现：
#include <iomanip>
#include <iostream>
#include "Node.h"
using namespace std;

bool check(node*head) {
    if(head==nullptr||head->next==nullptr)return false;
    node*slow=head;
    node*fast=head->next;
    while (slow != fast) {
        if (fast == nullptr || fast->next == nullptr) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true; 
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同结构的链表：

  • 测试用例 1：空链表

    • 输入链表：nullptr
    • 输出结果：false

  • 测试用例 2：无环链表

    • 输入链表：1 -> 2 -> 3 -> 4 -> 5
    • 输出结果：false

  • 测试用例 3：有环链表

    • 输入链表：1 -> 2 -> 3 -> 4 -> 2（4指向2形成环）
    • 输出结果：true

程序运行

  • 测试用例 1：对于空链表的输入，程序正确返回false，说明边界处理正确。
  • 测试用例 2：对于无环链表，程序能够正确返回false，说明程序能够处理一般链表的遍历情况。
  • 测试用例 3：对于有环链表，程序能够正确返回true，说明快慢指针的检测逻辑有效。
  • 通过多次测试，包括空链表、只有一个节点的链表、无环和有环的不同情况，程序均能得到正确的结果。

5. 实验总结与心得

通过本次实验，我进一步理解了链表的结构及其操作，尤其是对链表中的循环检测问题有了更深入的认识。在检测链表环的过程中，快慢指针法是一种非常巧妙且高效的算法，通过不同速度的指针遍历，能够在O(n)的时间内判断链表中是否存在环。

本次实验让我认识到边界条件处理的重要性。在处理链表问题时，往往需要考虑特殊情况，例如空链表或只有一个节点的情况，否则可能导致程序崩溃或错误。此外，快慢指针的应用不仅可以用于链表环的检测，还可以用于寻找链表的中间节点等操作，这些都是非常实用的技巧。

总的来说，通过此次实验，我对链表的操作有了更深入的了解，也掌握了一些常用的链表算法技巧。未来在实际编程中，我会更加注重代码的健壮性和边界情况的处理，以编写出更加高效和可靠的代码。

第四题 Remove for single link list with head node

1.实验题目

2. 实验目的

本实验的主要目的是实现一个函数来删除带虚拟头结点的单链表中的指定节点。通过本实验，学生能够：

  1. 理解单链表的基本结构及其删除操作。
  2. 掌握如何通过遍历链表找到指定位置的节点，并进行删除操作。
  3. 提高对链表操作的实现能力，特别是指针操作和内存管理能力。

3. 算法设计

为实现带虚拟头结点的单链表中删除指定节点的功能，我们采用指针遍历链表找到待删除节点的前一个节点，并执行删除操作。具体的算法步骤如下：

  1. 输入处理:

    • 接收要删除节点的位置pos。
    • 确保pos大于0且小于等于链表的实际节点数。

  2. 指针遍历:

    • 使用指针cur从虚拟头结点开始遍历，找到第pos-1个节点。

  3. 删除操作:

    • 将cur->next指向待删除节点的下一个节点。
    • 释放待删除节点的内存，确保不会发生内存泄漏。

  4. 时间复杂度：

  • 由于需要遍历链表找到删除位置，因此时间复杂度为O(n)，其中n为链表中节点的数量。
  1. 代码实现：
#include <iostream>
#include "ListNode.h"
using namespace std;

void List::remove(int pos) {
    ListNode* cur = head;
    pos--;
    while (pos--) {
        cur = cur->next;
    }
    if (cur->next) {
        ListNode* temp = cur->next; // 保存待删除节点
        cur->next = cur->next->next; // 跳过待删除节点
        delete temp; // 释放待删除节点内存
    }
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同位置的节点删除：

  • 测试用例 1：删除链表中间的节点

    • 输入链表：1 -> 2 -> 3 -> 4 -> 5
    • 删除位置：3
    • 输出链表：1 -> 2 -> 4 -> 5

  • 测试用例 2：删除链表头部后的第一个节点

    • 输入链表：1 -> 2 -> 3
    • 删除位置：1
    • 输出链表：2 -> 3

  • 测试用例 3：删除链表尾部节点

    • 输入链表：1 -> 2 -> 3 -> 4
    • 删除位置：4
    • 输出链表：1 -> 2 -> 3

程序运行

  • 测试用例 1：程序能够正确删除链表中的中间节点，输出链表为1 -> 2 -> 4 -> 5。
  • 测试用例 2：程序能够正确删除链表头部后的第一个节点，输出链表为2 -> 3。
  • 测试用例 3：程序能够正确删除链表尾部节点，输出链表为1 -> 2 -> 3。
  • 通过多次测试，包括链表为空、删除链表头部后的节点、删除尾节点等情况，程序均能得到正确的结果。

5. 实验总结与心得

通过本次实验，我进一步掌握了链表的结构及其删除操作，尤其是在链表中间删除节点时对指针的操作有了更深入的理解。链表的删除操作需要找到待删除节点的前一个节点，这涉及到对指针的操作，需要确保指针的正确性，否则容易导致链表结构破坏。

在本实验中，带虚拟头结点的链表使得删除操作更加方便，尤其是在删除第一个实际节点时，可以避免对头节点的特殊处理。在实际编程中，使用虚拟头结点的链表能够简化代码逻辑，提高代码的可读性和可维护性。

此外，通过对边界情况的测试，例如删除链表尾部节点、删除空链表中的节点，我学会了如何处理这些特殊情况，以确保代码的健壮性和正确性。总的来说，通过这次实验，我对链表操作的实现有了更深入的理解，并掌握了一些处理链表操作的实用技巧。

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
数据结构算法链表
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
栈与队列

							
							

							
树与二叉树

							
							

							
顺序表与链表

							
							

							
回溯算法初步(Ⅰ)

							
							

							
递归函数设计技巧

							
							

							
回溯算法初步(Ⅱ)

							
							

							
数据的表示

							
							

							
CPU设计与结构

							
							

					
				

			

		

		
					
			
						
					
		
	




 


 






 
  
、