当前位置: 首页 > news >正文

实验报告4(使用顺序表和单链表,进行有序表的合并)

一、实验目的:

熟练使用顺序表和单链表,进行有序表的合并。

二、实验仪器或设备:

操作系统:Windows11

编程环境:Dev-cpp 5.11

三、算法总体设计

(一)使用单链表进行有序表的合并

1. 打印链表

2. 合并两个有序链表

3. 释放链表内存

(二)使用顺序表进行有序表的合并

1.利用顺序表合并有序表

2. 释放合并后数组的内存

四、实验步骤(包括主要步骤、命令分析等)

(一)使用单链表进行有序表的合并

 1 #include <iostream>
 2  using namespace std;
 3 // 单链表节点定义
 4 struct ListNode {
 5     int val;
 6     ListNode* next;
 7     ListNode(int x) : val(x), next(NULL) {}
 8 }; 
 9 // 打印链表
10 void printList(ListNode* head) {
11     ListNode* current = head;
12     while (current != NULL) {
13        cout << current->val << " ";
14         current = current->next;
15     }
16    cout << endl;
17 } 
18 // 合并两个有序链表
19 ListNode* mergeSortedLists(ListNode* l1, ListNode* l2) {
20     // 创建一个哑节点作为新链表的头部
21     ListNode dummy(0);
22     ListNode* tail = &dummy;
23     while (l1 != NULL && l2 != NULL) {
24         if (l1->val <= l2->val) {
25             tail->next = l1;
26             l1 = l1->next;
27         } else {
28             tail->next = l2;
29             l2 = l2->next;
30         }
31         tail = tail->next;
32     }
33     // 添加剩余节点
34     tail->next = (l1 != NULL) ? l1 : l2; 
35     return dummy.next;
36 }
37 // 创建链表
38 ListNode* createList(int* values, int size) {
39     if (size == 0) return NULL;
40     ListNode* head = new ListNode(values[0]);
41     ListNode* current = head;
42     for (int i = 1; i < size; ++i) {
43         current->next = new ListNode(values[i]);
44         current = current->next;
45     }
46     return head;
47 }
48 // 释放链表内存
49 void freeList(ListNode* head) {
50     ListNode* current = head;
51     while (current != NULL) {
52         ListNode* next = current->next;
53         delete current;
54         current = next;
55     }
56 }
57 int main() {
58     // 创建第一个有序链表
59     int arr1[] = {1, 3, 5, 7};
60     ListNode* list1 = createList(arr1, 4);
61     // 创建第二个有序链表
62     int arr2[] = {2, 4, 6, 8};
63     ListNode* list2 = createList(arr2, 4);
64     // 合并两个有序链表
65     ListNode* mergedList = mergeSortedLists(list1, list2);
66     // 打印合并后的链表
67     cout << "合并后的链表: ";
68     printList(mergedList);
69     freeList(mergedList); // 合并后的链表
70     return 0;
71 }

(二)使用顺序表进行有序表的合并

 1 #include <cstdlib> 
 2 #include <iostream>
 3  using namespace std;
 4 int* mergeSortedArrays(int* arr1, int size1, int* arr2, int size2) {
 5     int totalSize = size1 + size2;
 6     int* mergedArray = (int*)std::malloc(totalSize * sizeof(int)); // 动态分配内存
 7     if (!mergedArray) {
 8         // 处理内存分配失败的情况
 9         cerr << "Memory allocation failed" << endl;
10         exit(EXIT_FAILURE);
11     }
12     int i = 0, j = 0, k = 0;
13     while (i < size1 && j < size2) {
14         if (arr1[i] < arr2[j]) {
15             mergedArray[k++] = arr1[i++];
16         } else {
17             mergedArray[k++] = arr2[j++];
18         }
19     }
20     while (i < size1) {
21         mergedArray[k++] = arr1[i++];
22     }
23     while (j < size2) {
24         mergedArray[k++] = arr2[j++];
25     }
26     return mergedArray; // 返回指向合并后数组的指针
27 }
28 int main() {
29     int arr1[] = {1, 3, 5, 7};
30     int arr2[] = {2, 4, 6, 8};
31     int size1 = sizeof(arr1) / sizeof(arr1[0]);
32     int size2 = sizeof(arr2) / sizeof(arr2[0]);
33 
34     int* mergedArray = mergeSortedArrays(arr1, size1, arr2, size2);
35     cout << "合并后的链表: ";
36     for (int i = 0; i < size1 + size2; ++i) {
37        cout << mergedArray[i] << " ";
38     }
39     cout << endl;
40   free(mergedArray);
41 
42     return 0;
43 }

(1)使用单链表运行的结果如图所示

第一个有序链表为1,3,5,7。

第二个有序链表为2,4,6,8。

更具题意进行合并则为:1,2,3,4,5,6,7,8。

2)使用顺序表运行的结果如图所示

第一个顺序表为:1,3,5,7。

第二个顺序表为:2,4,6,8。

更具题意进行合并则为:1,2,3,4,5,6,7,8。 

总结:通过本次实验,我掌握了使用顺序表和单链表进行有序表合并的基本方法和技巧。顺序表合并主要依赖于数组元素的比较和插入操作,而单链表合并则需要正确连接节点并处理尾节点。 这些知识和技能对于后续的数据结构学习和算法设计具有重要的参考价值...

http://www.hskmm.com/?act=detail&tid=28314

相关文章:

  • 函数
  • 20232314 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 2025秋_9
  • 10月10日
  • 详细介绍:【Windows10】MySQL9.4安装配置
  • ChatTime的一些理解
  • ChatTS的一些理解
  • 一生一芯学习:基础设施(2)
  • 实验报告3(使用单链表简单实现图书管理系统)
  • 大端与小端
  • 【黑马python】2.Python 字符串
  • 实验报告2(简单实现图书馆管理系统)
  • 实验报告1(switch语句,二维数组)
  • 【实现自己的 kafka!】kafka 的关键概念
  • 12. 对话框
  • 2024ICPC区域赛香港站
  • AI产品经理要了解的算法有哪些?
  • 一位印度小哥逆袭成为谷歌数据科学家的心路历程 - 教程
  • 基于selenium的网页自动搜索
  • MacOS Nginx
  • 缓存的击穿、雪崩、穿透在你项目中的场景是什么
  • [WC2021] 表达式求值
  • Set集合
  • AI时代下,如何看待“算法利维坦”?
  • JAVA - LinkedList 与 ArrayList 区别和 LinkedList 的四大接口解析
  • 苍穹外卖第三天(Swagger、@RequestParam和@RequestBody的使用场景、@PostMapping和@RequestMapping的区别、对象属性拷贝、@Insert注解)
  • Git 多账号管理
  • Hyper Server 2019安装I226-V网卡驱动
  • P10201 永恒
  • CF1209H tj