数据结构HW2

2023-11-07 02:01
文章标签 数据结构 hw2

本文主要是介绍数据结构HW2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.h>int insert_odd(int a[], int n, int x) {// 检查边界条件和错误情况if (n <= 0) {printf("错误：数组长度必须是正整数。\n");return -1; // 返回-1表示错误}// 计算新数组的长度int new_n = n+n/2;// 移动奇数下标的元素以腾出空间int j = new_n-1;for(int i = n-1;i>=0;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是数组的实际长度

// 返回数组的新长度

}

#include<stdio.h>
int delete_all (int a[], int n, int x) {int k=0;for(int i=0;i<n;i++){if(a[i] == x){for(int j = i;j<n;j++){a[j] = a[j+1];}k++;}}n = n-k;return n;}
int main()
{int a[]={1,99,3,99,5,6,7,99,};int n=sizeof(a)/sizeof(a[0]); int x=99;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.h>void 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.h>typedef 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.h>typedef 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;
}

这篇关于数据结构HW2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/360515。

相关文章

C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2