宁波南部商务区网站建设,北海市网站建设,导航单页模板wordpress,深圳 建设银行国际互联网站3. (10分) 编程实现一个数组插入算法#xff08;源文件命名insert.c#xff09;#xff0c;要求在数组a[]的所有奇数下标里插入某个数x。函数定义如下#xff1a; int insert_odd (int a[], int n, int x) { // n是数组的实际长度#xff0c;在所有n的奇数下标a[1], a…3. (10分) 编程实现一个数组插入算法源文件命名insert.c要求在数组a[]的所有奇数下标里插入某个数x。函数定义如下 int insert_odd (int a[], int n, int x) { // n是数组的实际长度在所有n的奇数下标a[1], a[3], …里插入x // 设a[]的最大长度足够大 // 返回数组的新长度 }
#include stdio.hint insert_odd(int a[], int n, int x) {// 检查边界条件和错误情况if (n 0) {printf(错误数组长度必须是正整数。\n);return -1; // 返回-1表示错误}// 计算新数组的长度int new_n nn/2;// 移动奇数下标的元素以腾出空间int j new_n-1;for(int i n-1;i0;i--){if(i%2!0){a[j] a[i];// 插入新元素x到奇数下标位置a[j-1] x;j - 2;}else {a[j] a[i];j--;}}// 返回新数组的长度return new_n;
}int main() {// 测试样例int a[99] {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};int n 11; // 数组长度int x 99; // 要插入的数printf(原始数组);for (int i 0; i n; i) {printf(%d , a[i]);}printf(\n);int new_n insert_odd(a, n, x);if (new_n ! -1) {printf(插入后的数组);for (int i 0; i new_n; i) {printf(%d , a[i]);}printf(\n);}return 0;
}
4. (10分) 编程实现一个数组的删除算法源文件命名delete_array.c要求删除数组a[]的所有x。函数定义如下 int delete_all (int a[], int n, int x) { // n是数组的实际长度 // 返回数组的新长度 }
#includestdio.h
int delete_all (int a[], int n, int x) {int k0;for(int i0;in;i){if(a[i] x){for(int j i;jn;j){a[j] a[j1];}k;}}n n-k;return n;}
int main()
{int a[]{1,99,3,99,5,6,7,99,};int nsizeof(a)/sizeof(a[0]); int x99;n delete_all(a,n,x);printf(数组新长度为%d ,n);printf(\n删除 %d 后的数组\n, x);for (int i 0; i n; i) {printf(%d , a[i]);}printf(\n);return 0;}
5. (10分) 编程实现有重复元素的二分查找并找到所有目标元素的位置源文件命名bsearch_duplicate.c函数定义如下。并给出算法的平均时间复杂度要写出分析过程。 void bsearch_dup (int a[], int n, int x, int res[]) { // 在a[]的前n个元素中寻找x返回x的最早位置和最晚位置存在res[]里 // 因此res[]是个只有两个元素的数组。若x不存在令res[-1, -1] // a已经排好序但可能有重复元素 }
#include stdio.hvoid bsearch_dup(int a[], int n, int x, int res[]) {int first_occurrence -1; // 初始值表示未找到int last_occurrence -1; // 初始值表示未找到int left 0;int right n - 1;while (left right) {int mid left (right - left) / 2;if (a[mid] x) {// 找到x后更新first_occurrence和last_occurrencefirst_occurrence mid;last_occurrence mid;// 继续在左半部分查找更早的位置int left_index mid - 1;while (left_index 0 a[left_index] x) {first_occurrence left_index;left_index--;}// 继续在右半部分查找更晚的位置int right_index mid 1;while (right_index n a[right_index] x) {last_occurrence right_index;right_index;}break; // 因为a已排序不必继续查找} else if (a[mid] x) {left mid 1;} else {right mid - 1;}}res[0] first_occurrence;res[1] last_occurrence;
}int main() {int a[] {1, 2, 2, 3, 3, 3, 4, 5, 5, 6};int n sizeof(a) / sizeof(a[0]);int x 3;int res[2] {-1, -1};bsearch_dup(a, n, x, res);if (res[0] ! -1 res[1] ! -1) {printf(元素 %d 的最早位置%d\n, x, res[0]);printf(元素 %d 的最晚位置%d\n, x, res[1]);} else {printf(元素 %d 不存在。\n, x);}return 0;
}6. (10分) 编程实现带头结点链表的一个删除算法要求删除所有等于x的结点源文件命名delete_linkedlist.c函数定义如下 typedef struct Node { int data; struct Node* next; } Node; int delete_all (Node** head, int x){ // head是无用的头结点删除所有等于x的结点 // 返回删除的结点数目 }
#include stdio.h
#include stdlib.htypedef struct Node {int data;struct Node* next;
} Node;int delete_all(Node** head, int x) {int deleted_count 0;// 处理头结点之后的结点Node* current *head;while (current-next ! NULL) {// 检查下一个结点的数据是否等于xif (current-next-data x) {Node* temp current-next; // 保存要删除的结点current-next current-next-next; // 删除结点free(temp); // 释放内存deleted_count;} else {current current-next; // 没有删除结点继续遍历}}return deleted_count;
}// 打印链表
void print_list(Node* head) {Node* current head-next;while (current ! NULL) {printf(%d - , current-data);current current-next;}printf(NULL\n);
}// 创建新结点
Node* create_node(int data) {Node* new_node (Node*)malloc(sizeof(Node));if (new_node ! NULL) {new_node-data data;new_node-next NULL;}return new_node;
}int main() {// 创建带头结点的链表Node* head create_node(-1); // 头结点Node* node1 create_node(1);Node* node2 create_node(2);Node* node3 create_node(2);Node* node4 create_node(3);// 连接结点head-next node1;node1-next node2;node2-next node3;node3-next node4;printf(原始链表\n);print_list(head);int x 2;int deleted_count delete_all(head, x);if (deleted_count 0) {printf(删除所有等于 %d 的结点后的链表\n, x);print_list(head);printf(删除的结点数目%d\n, deleted_count);} else {printf(没有找到等于 %d 的结点。\n, x);}// 释放链表内存Node* current head;while (current ! NULL) {Node* temp current;current current-next;free(temp);}return 0;
}7. (10分) 编程实现不带头结点链表反转的递归算法源文件命名linkedlist_reverse.c函数定义如下。并给出算法的时间复杂度要写出分析过程 Node** reverse (Node** head){ // 返回新的头结点 }
#include stdio.h
#include stdlib.htypedef struct Node {int data;struct Node* next;
} Node;// 反转链表
Node* reverse(Node* head) {if (head NULL || head-next NULL) {return head; // 如果链表为空或只有一个结点直接返回}Node* new_head reverse(head-next); // 递归反转剩余部分// 将当前结点的下一个结点的指针指向当前结点反转链接head-next-next head;head-next NULL;return new_head; // 返回新的头结点
}// 打印链表
void print_list(Node* head) {Node* current head;while (current ! NULL) {printf(%d - , current-data);current current-next;}printf(NULL\n);
}// 创建新结点
Node* create_node(int data) {Node* new_node (Node*)malloc(sizeof(Node));if (new_node ! NULL) {new_node-data data;new_node-next NULL;}return new_node;
}int main() {// 创建链表Node* node1 create_node(1);Node* node2 create_node(2);Node* node3 create_node(3);Node* node4 create_node(4);// 连接结点node1-next node2;node2-next node3;node3-next node4;printf(原始链表\n);print_list(node1);Node* new_head reverse(node1);printf(反转后的链表\n);print_list(new_head);// 释放链表内存Node* current new_head;while (current ! NULL) {Node* temp current;current current-next;free(temp);}return 0;
}
