网站四对联广告代码,开设一个网站的费用,智慧团建网站密码格式,静态企业网站模板下载考研是许多计算机科学专业学生追求高学历、寻求更好就业前景的途径。在考研过程中#xff0c;数据结构是一个非常重要的科目#xff0c;而代码实现题更是其中的难点之一。在这篇文章中#xff0c;我们将探讨如何通过实现数据结构代码问题来提升考研成绩。无论您是否有编程经… 考研是许多计算机科学专业学生追求高学历、寻求更好就业前景的途径。在考研过程中数据结构是一个非常重要的科目而代码实现题更是其中的难点之一。在这篇文章中我们将探讨如何通过实现数据结构代码问题来提升考研成绩。无论您是否有编程经验本文将为您提供一些简单但实用的技巧帮助您应对考研中遇到的数据结构题目。让我们一起踏上这个挑战性的学习旅程吧
为了照顾一些小白博主会在开篇也就是本文章尽量将一些细枝末节的东西讲解清楚其代表的含义是什么后期的一些文章可能就不会像本文这么啰嗦了大家按需学习即可
目录
初始C语言
初识顺序表
顺序表的两种写法
第一题删除顺序表中最小值
第二题逆置数据元素
第三题删除数组中指定元素的所有出现值
第四题删除指定范围值
第五题删除重复值
第六题合并两个顺序表
第七题逆置顺序表中指定范围元素
第八题折半查找指定元素
第九题找数组中未出现的最小正整数
第十题 寻找主元素 初始C语言 c语言运行的第一步就是导入我们的预处理指令(俗称头文件)程序可以使用其中定义的函数和类型而不需要自己实现这些功能。在本案例中我们需要导入两个头文件 stdio.h 和 stdlib.h 其中stdio.h是最最常用的头文件机会你要编写c程序百分百需要使用它。
//stdio.h 提供了输入输出函数如printf和scanf以及相关的类型和常量的定义。
#include stdio.h
//stdlib.h 提供了一些通用的函数如malloc和free用于内存分配、进程控制和其他常见任务。
#include stdlib.h c语言运行的第二步编写入口函数它是每个程序必须包含的部分。它表示程序的执行从这里开始。在main函数中你可以编写程序的主要逻辑和功能。在函数体内可以使用各种语句和表达式来完成所需的任务例如变量声明、函数调用和控制流语句等。
注意在C语言中main函数是唯一一个不可省略的函数它是程序的起点和终点。程序从main函数开始执行执行完main函数后程序结束。
int main() {// 逻辑代码执行
} c语言运行的第三步在主函数体中编写处理输入输出的代码与用户进行交互调用其他函数、模块或库来实现特定功能进行算术运算、逻辑判断等等。主函数体是整个程序的核心部分它负责协调和调度其他代码来实现程序的功能。
#include stdio.h// 主函数体区域int main(){}
初识顺序表 顺序表就是一种基于数组实现的线性数据结构。顺序表中的元素是按照在内存中的物理顺序进行连续存储的因此可以通过下标来随机访问元素。我们可以把数组看做是一种最简单的顺序表它只包含元素的类型和一个连续的内存块。 顺序表和数组不完全相同。数组是一种静态数据结构在声明数组时需要指定数组的大小而且数组的大小不能动态增加或缩小。而顺序表则可以通过动态内存分配进行动态增加或缩小因此顺序表是一种动态数据结构。
顺序表有两种常见的实现方式静态顺序表和动态顺序表。 静态顺序表Static Array静态顺序表使用静态数组来表示其大小在编译时就确定了无法动态调整。静态顺序表需要提前指定一个固定的最大容量如果超过了该容量就无法添加新的元素。静态顺序表的优点是操作简单直接利用数组的随机访问特性但缺点是容量固定无法动态扩展大小。 下列代码中定义了一个长度为5的静态数组arr并初始化了其中的元素。由于静态数组在编译时就确定了大小因此其大小无法动态调整。
#include stdio.h#define MAX_SIZE 5int main() {// 静态数组初始化分配了 MAX_SIZE 个元素的空间int arr[MAX_SIZE] {1, 2, 3, 4, 5};// 遍历数组并输出每个元素for (int i 0; i MAX_SIZE; i) {printf(%d , arr[i]);}printf(\n);return 0;
} 动态顺序表Dynamic Array动态顺序表使用动态内存分配来表示其大小可以根据需要动态增长或缩小。动态顺序表最常见的实现是通过使用malloc()和realloc()函数来动态分配和重新分配内存空间。动态顺序表的优点是可以根据需求灵活地改变大小但缺点是相比静态顺序表多了内存分配和释放的开销。 下列代码中使用malloc()函数在堆内存中申请了一个长度为5的动态数组arr并初始化了其中的元素。由于动态数组使用堆内存分配在运行时可以通过realloc()函数动态地调整数组大小。代码中使用realloc()函数将原本长度为5的数组扩容为长度为10的数组并向其中添加新元素。最后使用free()函数释放动态数组占用的内存。
#include stdio.h
#include stdlib.hint main() {// 动态数组初始化开始时分配了 5 个元素的空间int* arr (int*)malloc(sizeof(int) * 5);if (arr NULL) {printf(动态数组分配内存失败\n);return -1;}// 遍历数组并输出每个元素for (int i 0; i 5; i) {arr[i] i 1;printf(%d , arr[i]);}printf(\n);// 动态调整数组大小int* new_arr (int*)realloc(arr, sizeof(int) * 10);if (new_arr NULL) {printf(动态数组重新分配内存失败\n);free(arr);return -1;}arr new_arr;// 向数组中添加新元素for (int i 5; i 10; i) {arr[i] i 1;}// 遍历扩容后的数组并输出每个元素for (int i 0; i 10; i) {printf(%d , arr[i]);}printf(\n);// 释放动态数组占用的内存free(arr);return 0;
}
顺序表的两种写法
在c语言中实现顺序表的方式有两种
使用数组来存储数据例如
// 这里的 a 数组即是一个顺序表其下标从 0 到 MAXSIZE - 1
int a[MAXSIZE];// 可以通过下标访问其中的元素例如
int x a[0]; // 获取第一个元素
a[1] 2; // 修改第二个元素
使用结构体来存储顺序表中的数据以及长度信息例如
// 这里的 SeqList 即是一个顺序表类型其中 data 数组存储了顺序表中的元素length 变量表示顺序表的长度。
typedef struct {int data[MAXSIZE];int length;
} SeqList;// 可以通过操作结构体成员来访问和修改顺序表中的元素和长度信息例如
SeqList list;
list.data[0] 1;
list.data[1] 2;
list.length 2; 两种方式各有优缺点 使用数组实现的顺序表不需要定义额外的数据类型对于简单的操作来说可能更加方便但是对于需要对顺序表进行多种操作例如插入、删除、查找等时使用结构体实现的顺序表会更加灵活和易于维护。 接下来我会在前五题中使用数组实现顺序表后五题中使用结构体实现顺序表。
第一题删除顺序表中最小值 从顺序表中删除具有最小值的元素假设唯一并由函数返回被删除元素的值。空出的位置有最后一个元素填补若顺序表为空则显示出错信息并退出运行。 实现思路如下
首先在主函数中通过用户输入获取了数组的长度 n并动态分配了一个长度为 n 的整型数组 arr 来存储用户输入的元素值使用 for 循环依次读取用户输入的元素值并将其保存在数组 arr 中。
接着通过调用 delMin() 函数来删除顺序表中的最小元素。该函数接受数组 arr 和数组长度 n 的指针作为参数。在 delMin() 函数中首先判断数组长度是否为 0如果是则打印 数组为空 的提示信息并返回一个-1。如果数组长度不为 0那么就遍历数组寻找最小元素的位置并将最小元素与数组末尾的元素交换位置。然后将数组长度减一表示成功删除了一个元素。最后返回被删除的最小元素。
然后我们回到主函数将 delMin() 函数返回的最小元素保存在变量 min 中并输出 删除的最小值为 的提示信息以及最小值的具体数值。
最后使用 for 循环输出删除最小元素后的顺序表即数组 arr 的元素。同时释放动态分配的内存并将指针 arr 赋值为 NULL以避免出现野指针问题。
#include stdio.h
#include stdlib.hint delMin(int* arr, int* len) {if (*len 0) {printf(数组为空\n);return -1;}int min arr[0], minPos 0;for (int i 1; i *len; i) {if (min arr[i]) {min arr[i];minPos i;}}arr[minPos] arr[*len - 1];(*len)--;// 返回被删除的最小元素return min;
}int main() {int n;printf(请输入数组长度的个数n);scanf_s(%d, n);if (n 0) {printf(数组长度必须大于0\n);return 0;}int* arr (int*)malloc(sizeof(int) * n);printf(请输入数组的元素值\n);for (int i 0; i n; i) {scanf_s(%d, arr i);}printf(原始顺序表);for (int i 0; i n; i) {printf_s(%d , *(arr i));}printf(\n);int min delMin(arr, n);printf(删除的最小值为%d\n, min);printf(删除后顺序表);for (int i 0; i n; i) {printf_s(%d , arr[i]);}free(arr); // 释放动态分配的内存arr NULL; // 避免野指针问题return 0;
}
执行代码结果展示如下 第二题逆置数据元素 设计一个高效算法将顺序表L的所有元素逆置要求算法的空间复杂度为O(1) 实现思路如下
首先在主函数中通过用户输入获取了数组的长度 n并动态分配了一个长度为 n 的整型数组 arr 来存储用户输入的元素值。使用 for 循环依次读取用户输入的元素值并将其保存在数组 arr 中。
接着设置 reserve() 函数传入数组和数组长度的地址实现对数组的逆置操作。在 reserve() 函数内部首先判断数组长度是否为 0如果是则打印数组为空的提示信息。接下来使用一个循环遍历数组的前半部分并通过交换元素的方式实现逆置操作。
然后我们回到主函数调用 reserve() 函数
最后再次使用 printf_s() 打印逆置后的元素。同时使用 free() 函数释放动态分配的内存空间将指针 arr 设置为 NULL以避免悬挂指针的问题。返回 0表示程序正常结束。
#include stdio.h
#include stdlib.hvoid reserve(int* arr, int* len) {if (!*len) {printf_s(数组为空\n);}int tmp; // 定义一个暂存空间for (int i 0; i *len/2; i){ tmp *(arr i);*(arr i) *(arr *len - i - 1);*(arr *len - i - 1) tmp;}
}int main() {int n; // 定义数组的长度printf_s(请输入数组的长度n);scanf_s(%d, n);if (n 0) {printf(数组长度必须大于0\n);return 0;}int* arr (int*)malloc(sizeof(int) * n); // 动态分配数据空间printf_s(请输入数组的元素\n);for (int i 0; i n; i){scanf_s(%d, arr i);}printf_s(未逆置之前的元素);for (int i 0; i n; i){printf_s(%d, arr[i]);}reserve(arr, n);printf_s(\n逆置之后的元素);for (int i 0; i n; i){printf_s(%d, arr[i]);}free(arr);arr NULL;return 0;
}
执行代码结果展示如下 第三题删除数组中指定元素的所有出现值 对长度为n的顺序表L编写一个时间复杂度为O(n)空间复杂度为O(1)的算法该算法删除线性表中所有值为x的数据元素。 实现思路如下
首先通过 scanf_s() 函数获取用户输入的数组长度 n。
接着使用动态内存分配函数 malloc() 为数组分配内存空间分配大小为 sizeof(int) * n。
然后使用一个循环通过 scanf_s() 获取用户输入的元素并将其存储到数组中。在 main() 函数中调用 delX() 函数传入数组、数组长度和待删除的元素 x。在 delX() 函数中使用两个指针 i 和 k 来追踪数组的索引和删除元素的总数。通过遍历数组如果找到等于 x 的元素则增加 k 的计数否则将当前元素移动到数组的正确位置。
最后使用一个循环打印出删除元素之后的数组内容遍历范围是 n - k因为前 n - k 个元素是删除元素操作之后仍然存在的元素。返回 0表示程序正常结束。
#include stdio.h
#include stdlib.hint delX(int* arr, int* len, int x) {int k 0, i 0; // 定义要删除元素的总数m和要删除的下标iwhile (i *len) {if (*(arr i) x) {k;}else {*(arr i - k) *(arr i);}i;}for (int i *len - k; i *len; i){*(arr i) NULL;}return k;
}int main() {int n, m; // 定义数组的长度和要删除的元素printf_s(请输入数据的长度);scanf_s(%d, n);int* arr (int*)malloc(sizeof(int) * n);printf_s(请输入数组元素);for (int i 0; i n; i){scanf_s(%d, arr i);}printf_s(请输入要删除的元素);scanf_s(%d, m);int k delX(arr, n, m);printf_s(最终的结果);for (int i 0; i n - k; i){printf_s(%d, *(arr i));}free(arr);arr NULL;return 0;
}
执行代码结果展示如下 第四题删除指定范围值 从有序顺序表中删除其值在给定值 s 与 t 之间要求 s t的所有元素如果 s 或 t 不合理或顺序表为空则显示出错信息并退出运行。 实现思路如下
首先在主函数中获取用户输入的数组长度并分配相应大小的内存空间用于存储数组元素通过循环依次获取用户输入的每个数组元素。
接着使用一个循环取用户输入的删除区间的起始和终止位置并对输入进行合法性判断如果起始位置大于终止位置则重新输入。
然后函数 deletePoint 接收传入的数组 arr、起始位置 m、终止位置 k 和数组长度 len。如果起始位置大于等于终止位置或者数组长度为 0说明输入的删除区间不合法或者顺序表为空函数会打印相应的错误提示并返回。函数使用两个循环找到第一个大于等于 m 的元素的位置 i 和第一个小于等于 k 的元素的位置 t。函数使用一个循环将从位置 t 开始到数组末尾的元素覆盖到位置 i 开始的元素实现了删除指定区间范围内的元素。
最后调用 deletePoint 函数删除指定区间范围内的元素并释放动态分配的内存空间。
#include stdio.h
#include stdlib.hvoid deletePoint(int* arr, int m, int k, int len) {if (m k || len 0) {printf_s(输入的删除区间不合法或顺序表为空);return;}int i, t;for (i 0; i len *(arr i) m; i); // 找到第一个大于等于m的元素if (i len) return;for (t i; t len *(arr t) k; t); // 找到第一个小于等于t的元素for (; t len; i, t) *(arr i) *(arr t);printf_s(当前数组为);for (int j 0; j i; j) printf_s(%d , *(arr j));
}int main() {int n;printf_s(请输入数据的长度);scanf_s(%d, n);printf_s(请输入数组的元素);int* arr (int*)malloc(sizeof(int) * n);for (int i 0; i n; i){scanf_s(%d, arr i);}// 给定要删除元素的区间范围int m, k;do{printf_s(请输入要删除的数组元素起始范围);scanf_s(%d, m);printf_s(请输入要删除的数组元素终止范围);scanf_s(%d, k);} while (m k); // 如果 m k 的话需要进行重新输入deletePoint(arr, m, k, n);free(arr); // 动态分配的内存需要手动释放return 0;
}
执行代码结果展示如下 第五题删除重复值 从有序顺序表中删除所有其值重复的元素使表中所有元素的值均不相同。 实现思路如下
首先在函数 deleteRepitition 中通过循环遍历数组中的元素对于每个元素判断其与后一个元素是否相等如果不相等则将该元素保留。使用变量 k 记录保留下来的元素数量并将这些元素逐个放回原数组中。
接着在最后一个判断中判断最后两个元素是否相等如果相等则将最后一个元素也保留下来。
然后在主函数 main 中定义了一个数组 arr 并初始化获取其长度 len。之后调用 deleteRepitition 函数删除重复元素得到新的数组长度 len。最后使用循环打印删除重复元素后的数组内容。
最后整个程序结束并返回 0。
#include stdio.hint deleteRepitition(int* arr, int len) {int k 0; // 用来记录下标for (int i 0; i len; i){if (*(arr i) - *(arr i 1)) {*(arr k) *(arr i);}}if (*(arr len - 1) *(arr len)) {*(arr k) *(arr len - 1);}return k;
}int main() {int arr[] { 1,1,2,2,2,3,3,4,5 };// 定义一个数组int len sizeof(arr) / sizeof(int);len deleteRepitition(arr, len);for (int i 0; i len; i) printf_s(%d, *(arr i));return 0;
}
执行代码结果展示如下 第六题合并两个顺序表 将两个有序顺序表合并为一个新的有序顺序表并由函数返回结果顺序表。 实现思路如下
首先定义了一个SeqList结构体表示顺序表包含元素数组data和长度length。
接着定义了一个Merge函数该函数接受两个有序顺序表L1和L2作为参数返回一个新的合并后的有序顺序表L3。实现思路是创建一个新的顺序表L3然后使用i、j、k三个变量分别表示L1、L2、L3中元素的索引将L1和L2中较小的元素依次放入L3中最后将剩余的元素放入L3中。
然后在main函数中读入L1和L2的长度以及元素调用Merge函数对L1和L2进行合并最后输出合并后的有序顺序表L3中的元素。
最后程序结束。
#include stdio.h
#include stdlib.h#define MAXSIZE 100typedef struct {int data[MAXSIZE];int length;
} SeqList;// 合并两个有序顺序表为一个新的有序顺序表
SeqList Merge(SeqList L1, SeqList L2) {SeqList L3;int i 0, j 0, k 0;while (i L1.length j L2.length) {if (L1.data[i] L2.data[j]) {L3.data[k] L1.data[i];}else {L3.data[k] L2.data[j];}}while (i L1.length) {L3.data[k] L1.data[i];}while (j L2.length) {L3.data[k] L2.data[j];}L3.length k;return L3;
}int main() {int n1, n2;SeqList L1, L2, L3;printf(请输入 L1 的长度);scanf_s(%d, n1);printf(请按升序输入 %d 个元素, n1);for (int i 0; i n1; i) {scanf_s(%d, L1.data[i]);}L1.length n1;printf(请输入 L2 的长度);scanf_s(%d, n2);printf(请按升序输入 %d 个元素, n2);for (int i 0; i n2; i) {scanf_s(%d, L2.data[i]);}L2.length n2;L3 Merge(L1, L2);printf(合并后的顺序表为\n);for (int i 0; i L3.length; i) {printf(%d , L3.data[i]);}printf(\n);return 0;
}
执行代码结果展示如下 第七题逆置顺序表中指定范围元素 已知在一维数组A[mn]中依次存放两个线性表试编写一个函数将数组中的两个顺序表的位置互换即将后一个顺序表放在前一个顺序表的前面。 实现思路如下
首先代码定义了一个结构体 SeqList 用于表示顺序表包括顺序表元素和长度。
接着在 SwapSeqList 函数中首先进行参数的合法性检查然后使用动态内存分配创建临时数组将前面部分的顺序表元素暂存到临时数组中接着将后面的顺序表元素移到前面最后将临时数组中的元素移动到后面的顺序表。
然后在 main 函数中首先获取用户输入的两个顺序表的长度然后分配内存空间存储顺序表元素接着依次获取用户输入的元素调用 SwapSeqList 函数进行顺序表元素交换并输出交换后的顺序表。
最后释放动态分配的内存空间程序结束。
#include stdio.h
#include stdlib.htypedef struct {int* elements; // 顺序表元素int length; // 顺序表长度
} SeqList;void SwapSeqList(SeqList* list, int m, int n) {if (m 0 || n 0 || list-length m n) {printf_s(输入参数错误\n);return;}// 创建一个临时数组用于暂存前面的顺序表int* temp (int*)malloc(m * sizeof(int));if (temp NULL) {printf_s(内存分配失败\n);return;}for (int i 0; i m; i) {temp[i] list-elements[i];}// 将后面的顺序表移到前面for (int i 0; i list-length - m; i) {list-elements[i] list-elements[i m];}// 将临时数组中的元素移到后面的顺序表for (int i 0; i m; i) {list-elements[list-length - m i] temp[i];}free(temp);
}int main() {int m, n;printf_s(请输入第一个顺序表的长度);scanf_s(%d, m);printf_s(请输入第二个顺序表的长度);scanf_s(%d, n);if (m 0 || n 0) {printf_s(输入参数错误\n);return 1;}SeqList list;list.length m n;list.elements (int*)malloc(list.length * sizeof(int)); // 使用动态内存分配if (list.elements NULL) {printf_s(内存分配失败\n);return 1;}printf_s(请输入%d个元素作为第一个顺序表, m);for (int i 0; i m; i) {scanf_s(%d, list.elements[i]);}printf_s(请输入%d个元素作为第二个顺序表, n);for (int i 0; i n; i) {scanf_s(%d, list.elements[m i]);}SwapSeqList(list, m, n);printf_s(交换后的顺序表为);for (int i 0; i list.length; i) {printf_s(%d , list.elements[i]);}free(list.elements); // 释放动态分配的内存return 0;
}
执行代码结果展示如下 第八题折半查找指定元素 线性表中的元素递增有序且按顺序存储于计算机内。要求设计一算法完成用最少的时间在表中查找数值为 x 的元素若找到则将其与后继元素位置相交换若找不到则将其插入表中并使表中元素仍递增有序。 实现思路如下
首先代码定义了顺序表的数据结构SeqList包括元素数组指针、当前长度和最大容量并初始化了顺序表。
接着在SearchAndInsertOrSwap函数中实现了对顺序表的查找、插入或交换操作。遍历顺序表元素找到相等元素时进行交换操作未找到相等元素时找到大于该元素的位置并插入。
然后在main函数中首先让用户输入顺序表的长度然后依次输入顺序表的元素并且调用SearchAndInsertOrSwap函数对顺序表进行操作。
最后输出操作后的顺序表并释放动态分配的内存。
#include stdio.h
#include stdlib.h#define MAXSIZE 100 // 定义顺序表的最大长度typedef struct {int* elements; // 顺序表元素int length; // 顺序表当前长度int capacity; // 顺序表最大容量
} SeqList;// 初始化顺序表
void InitSeqList(SeqList* list, int maxSize) {list-elements (int*)malloc(maxSize * sizeof(int));if (list-elements NULL) {printf(内存分配失败\n);exit(1);}list-length 0;list-capacity maxSize;
}// 顺序表查找并插入或交换元素
void SearchAndInsertOrSwap(SeqList* list, int x) {int i;for (i 0; i list-length; i) {if (list-elements[i] x) { // 找到相等元素if (i list-length - 1) { // 不是最后一个元素int temp list-elements[i];list-elements[i] list-elements[i 1];list-elements[i 1] temp;return;}else {printf(已经是最后一个元素无法交换\n);return;}}else if (list-elements[i] x) { // 找到大于x的元素位置int j;for (j list-length; j i; j--) {list-elements[j] list-elements[j - 1]; // 元素后移}list-elements[i] x; // 插入xlist-length; // 长度增加return;}}if (i list-length) { // 未找到相等元素且未插入list-elements[i] x; // 直接插入末尾list-length; // 长度增加}
}// 打印顺序表
void PrintSeqList(SeqList* list) {for (int i 0; i list-length; i) {printf(%d , list-elements[i]);}printf(\n);
}int main() {SeqList list;int size;printf(请输入顺序表的长度);scanf_s(%d, size);InitSeqList(list, size);printf(请输入顺序表的元素);for (int i 0; i size; i) {scanf_s(%d, list.elements[i]);list.length;}int x;printf(请输入要查找/插入/交换的元素);scanf_s(%d, x);SearchAndInsertOrSwap(list, x);printf(操作后的顺序表为);PrintSeqList(list);free(list.elements); // 释放动态分配的内存return 0;
}
执行代码结果展示如下 第九题找数组中未出现的最小正整数 给定一个含n(n1)个整数的数组请设计一个在时间上尽可能高效的算法找出数组中未出现的最小正整数例如数据{-5,3,2,3}中未出现的最小正整数是1数组{1,2,3}中未出现的最小正整数是4。 实现思路如下
首先我们定义了一个名为SeqList的结构体用于表示顺序表其中包含了元素数组、当前长度和最大容量等信息。
接着在InitSeqList函数中我们实现了对顺序表的初始化操作包括动态分配内存、设置初始长度和容量等。
然后我们实现了FindSmallestPositive函数用于找出数组中未出现的最小正整数的算法。该算法通过遍历数组并通过交换元素的方式使得每个正整数在数组中处于正确的位置。
最后在main函数中我们进行了用户输入数组长度和元素的操作并调用了InitSeqList和FindSmallestPositive函数来完成整个流程。最后记得调用FreeSeqList来释放动态分配的内存。
#include stdio.h
#include stdlib.h// 定义顺序表的最大长度
#define MAXSIZE 100 // 顺序表结构体
typedef struct {int* elements; // 顺序表元素int length; // 顺序表当前长度int capacity; // 顺序表最大容量
} SeqList;// 初始化顺序表
extern void InitSeqList(SeqList* list, int maxSize) {list-elements (int*)malloc(maxSize * sizeof(int));if (list-elements NULL) {printf(内存分配失败\n);exit(1);}list-length 0;list-capacity maxSize;
}// 释放顺序表占用的内存
void FreeSeqList(SeqList* list) {free(list-elements);
}// 找出数组中未出现的最小正整数
int FindSmallestPositive(SeqList* list) {int i;for (i 0; i list-length; i) {while (list-elements[i] 0 list-elements[i] list-length list-elements[list-elements[i] - 1] ! list-elements[i]) {int temp list-elements[i];list-elements[i] list-elements[temp - 1];list-elements[temp - 1] temp;}}for (i 0; i list-length; i) {if (list-elements[i] ! i 1) {return i 1;}}return list-length 1;
}int main() {SeqList list;int n;printf(请输入数组的长度);scanf_s(%d, n);InitSeqList(list, n);printf(请输入数组的元素);for (int i 0; i n; i) {scanf_s(%d, list.elements[i]);list.length;}int result FindSmallestPositive(list);printf(数组中未出现的最小正整数是%d\n, result);FreeSeqList(list); // 释放动态分配的内存return 0;
}
执行代码结果展示如下 第十题 寻找主元素 若一个整数序列中有过半相同元素则称其为主元素设计算法找出数组A的主元素若存在主元素则输出否则返回 -1。 实现思路如下
首先我们定义了一个名为SeqList的结构体用于存储顺序表的元素、当前长度和最大容量并且定义了初始化顺序表和释放内存的函数。
接着在FindMajorityElement函数中我们使用Boyer-Moore投票算法来查找数组A的主元素通过两次遍历数组一次找出候选主元素一次验证候选主元素是否为真正的主元素。
然后在main函数中我们首先接收用户输入的数组长度并初始化顺序表。然后依次接收用户输入的数组元素并调用FindMajorityElement函数来查找主元素并输出结果。
最后我们释放了动态分配的内存确保程序运行结束时没有内存泄漏。
#include stdio.h
#include stdlib.h// 定义顺序表的最大长度
#define MAXSIZE 100 // 顺序表结构体
typedef struct {int* elements; // 顺序表元素int length; // 顺序表当前长度int capacity; // 顺序表最大容量
} SeqList;// 初始化顺序表
void InitSeqList(SeqList* list, int maxSize) {list-elements (int*)malloc(maxSize * sizeof(int));if (list-elements NULL) {printf(内存分配失败\n);exit(1);}list-length 0;list-capacity maxSize;
}// 释放顺序表占用的内存
void FreeSeqList(SeqList* list) {free(list-elements);
}// 查找数组A的主元素
int FindMajorityElement(SeqList* list) {int candidate 0;int count 0;for (int i 0; i list-length; i) {if (count 0) {candidate list-elements[i];count 1;}else if (list-elements[i] candidate) {count;}else {count--;}}count 0;for (int i 0; i list-length; i) {if (list-elements[i] candidate) {count;}}if (count list-length / 2) {return candidate;}else {return -1;}
}int main() {SeqList list;int n;printf(请输入数组的长度);scanf_s(%d, n);InitSeqList(list, n);printf(请输入数组的元素);for (int i 0; i n; i) {scanf_s(%d, list.elements[i]);list.length;}int result FindMajorityElement(list);if (result ! -1) {printf(数组的主元素是%d\n, result);}else {printf(数组没有主元素\n);}FreeSeqList(list); // 释放动态分配的内存return 0;
}
执行代码结果展示如下
