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

数据结构习题

news 2024/9/25 17:07:08

题目描述

有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。

运行代码

#include <stdio.h>#include <stdlib.h>// 定义链表节点结构体typedef struct ListNode {int data;struct ListNode *next;} ListNode;// 创建新节点的辅助函数ListNode* createNode(int val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->data = val;newNode->next = NULL;return newNode;}// 计算数据域为 x 的结点个数int countOccurrences(ListNode* head, int x) {int count = 0;ListNode* current = head;while (current != NULL) {if (current->data == x) {count++;}current = current->next;}return count;}// 打印链表的辅助函数void printList(ListNode* head) {ListNode* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");}// 释放链表内存的辅助函数void freeList(ListNode* head) {ListNode* current = head;while (current != NULL) {ListNode* next = current->next;free(current);current = next;}}int main() {// 创建一个单链表示例ListNode* head = createNode(1);head->next = createNode(2);head->next->next = createNode(3);head->next->next->next = createNode(2);head->next->next->next->next = createNode(5);head->next->next->next->next->next = createNode(2);int x = 2;int count = countOccurrences(head, x);// 输出结果printf("链表：");printList(head);printf("数据域为 %d 的结点个数: %d\n", x, count);// 释放链表内存freeList(head);return 0;}​

代码思路

  1. 结构体 ListNode:定义了一个链表节点结构体，包含数据成员 data 和指针成员 next。

  2. 函数 createNode:用于创建一个新的链表节点，并初始化其数据和指针。

  3. 函数 countOccurrences:

    • 接受两个参数：链表的头节点 head 和要计数的数据 x。
    • 初始化一个计数器 count 为 0。
    • 遍历链表，如果当前节点的数据等于 x，则计数器加 1。
    • 返回计数器的值。

  4. 函数 printList:用于打印链表的内容。

  5. 函数 freeList:用于释放链表的内存，避免内存泄漏。

  6. 主函数 main:

    • 创建一个单链表示例。
    • 调用 countOccurrences 函数计算数据域为 x 的结点个数。
    • 输出链表的内容和计数结果。
    • 释放链表内存，避免内存泄漏。

题目描述

有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。

运行代码

#include <stdio.h>#include <stdlib.h>// 定义链表节点结构体typedef struct ListNode {int data;struct ListNode *next;} ListNode;// 创建新节点的辅助函数ListNode* createNode(int val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->data = val;newNode->next = NULL;return newNode;}// 将元素 x 插入到有序链表中ListNode* insertSorted(ListNode* head, int x) {ListNode* newNode = createNode(x);if (head == NULL || x <= head->data) {newNode->next = head;return newNode;}ListNode* current = head;while (current->next != NULL && current->next->data < x) {current = current->next;}newNode->next = current->next;current->next = newNode;return head;}// 打印链表的辅助函数void printList(ListNode* head) {ListNode* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");}// 释放链表内存的辅助函数void freeList(ListNode* head) {ListNode* current = head;while (current != NULL) {ListNode* next = current->next;free(current);current = next;}}int main() {// 创建一个有序单链表示例ListNode* head = createNode(1);head->next = createNode(3);head->next->next = createNode(4);head->next->next->next = createNode(7);int x = 5;head = insertSorted(head, x);// 输出链表printf("链表：");printList(head);// 释放链表内存freeList(head);return 0;}​

代码思路

  1. 结构体 ListNode:定义了一个链表节点结构体，包含数据成员 data 和指针成员 next。

  2. 函数 createNode:用于创建一个新的链表节点，并初始化其数据和指针。

  3. 函数 insertSorted:

    • 接受两个参数：有序链表的头节点 head 和要插入的元素 x。
    • 创建一个新节点 newNode 并初始化其数据为 x。
    • 如果链表为空或 x 小于等于头节点的数据，则将新节点插入到链表头部。
    • 否则，遍历链表，找到合适的位置插入新节点，确保链表仍然有序。
    • 返回新的头节点。

  4. 函数 printList:用于打印链表的内容。

  5. 函数 freeList:用于释放链表的内存，避免内存泄漏。

  6. 主函数 main:

    • 创建一个有序单链表示例。
    • 调用 insertSorted 函数将元素 x 插入到链表中。
    • 输出链表的内容。
    • 释放链表内存，避免内存泄漏。

题目描述

编写一个函数将一个头指针为a的单链表A分解成两个单链表A和B，其头指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。

运行代码

#include <stdio.h>#include <stdlib.h>// 定义链表节点结构体typedef struct ListNode {int data;struct ListNode *next;} ListNode;// 创建新节点的辅助函数ListNode* createNode(int val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->data = val;newNode->next = NULL;return newNode;}// 将一个链表分解成两个链表void splitList(ListNode* a, ListNode** b) {if (a == NULL) {*b = NULL;return;}ListNode* odd = a;  // 奇数链表的头节点ListNode* even = a->next;  // 偶数链表的头节点*b = even;  // 将偶数链表的头节点赋值给 b// 遍历链表，将奇数和偶数节点分开while (even != NULL && even->next != NULL) {odd->next = even->next;  // 连接奇数节点odd = odd->next;even->next = odd->next;  // 连接偶数节点even = even->next;}odd->next = NULL;  // 结束奇数链表}// 打印链表的辅助函数void printList(ListNode* head) {ListNode* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");}// 释放链表内存的辅助函数void freeList(ListNode* head) {ListNode* current = head;while (current != NULL) {ListNode* next = current->next;free(current);current = next;}}int main() {// 创建一个单链表示例ListNode* a = createNode(1);a->next = createNode(2);a->next->next = createNode(3);a->next->next->next = createNode(4);a->next->next->next->next = createNode(5);ListNode* b = NULL;splitList(a, &b);// 输出 A 链表printf("A 链表：");printList(a);// 输出 B 链表printf("B 链表：");printList(b);// 释放链表内存freeList(a);freeList(b);return 0;}​

代码思路

  1. 结构体 ListNode:定义了一个链表节点结构体，包含数据成员 data 和指针成员 next。

  2. 函数 createNode:用于创建一个新的链表节点，并初始化其数据和指针。

  3. 函数 splitList:

    • 接受两个参数：原始链表的头节点 a 和一个指向指针的指针 b，用于存储拆分后的偶数位置链表的头节点。
    • 使用两个指针 odd 和 even 分别指向奇数位置和偶数位置的节点。
    • 通过遍历链表，将奇数位置和偶数位置的节点分别连接起来。
    • 最后，将 odd 的 next 指针设为 NULL，结束奇数链表。

  4. 函数 printList:用于打印链表的内容。

  5. 函数 freeList:用于释放链表的内存，避免内存泄漏。

  6. 主函数 main:

    • 创建一个示例链表 a。
    • 调用 splitList 函数将链表 a 拆分为两个链表 a 和 b。
    • 输出两个链表的内容。
    • 释放链表内存，避免内存泄漏。

题目描述

已知两个顺序表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的顺序表形式存储。

运行代码

#include <stdio.h>#include <stdlib.h>// 函数原型声明int* intersect(int A[], int sizeA, int B[], int sizeB, int *returnSize);int main() {int A[] = {1, 2, 3, 4, 5};int B[] = {3, 4, 5, 6, 7};int sizeA = sizeof(A) / sizeof(A[0]);int sizeB = sizeof(B) / sizeof(B[0]);int returnSize;int *C = intersect(A, sizeA, B, sizeB, &returnSize);// 打印交集printf("Intersection: ");for (int i = 0; i < returnSize; i++) {printf("%d ", C[i]);}printf("\n");// 释放分配的内存free(C);return 0;}int* intersect(int A[], int sizeA, int B[], int sizeB, int *returnSize) {int *C = (int *)malloc((sizeA < sizeB ? sizeA : sizeB) * sizeof(int));int i = 0, j = 0, k = 0;while (i < sizeA && j < sizeB) {if (A[i] < B[j]) {i++;} else if (B[j] < A[i]) {j++;} else {if (k == 0 || C[k-1] != A[i]) {  // 避免添加重复的元素C[k++] = A[i];}i++;j++;}}*returnSize = k;return C;}​

代码思路

  1. 结构体 ListNode:

    • 定义了一个链表节点结构体，包含数据成员 data 和指针成员 next。
    • 构造函数用于初始化节点的数据和指针。

  2. 函数 splitList:

    • 接受两个参数：原始链表的头节点 a 和一个引用参数 b，用于存储拆分后的偶数位置链表的头节点。
    • 使用两个指针 odd 和 even 分别指向奇数位置和偶数位置的节点。
    • 通过遍历链表，将奇数位置和偶数位置的节点分别连接起来。
    • 最后，将 odd 的 next 指针设为 nullptr，并更新 b 为 evenHead。

  3. 主函数 main:

    • 创建一个示例链表 a。
    • 调用 splitList 函数将链表 a 拆分为两个链表 a 和 b。
    • 输出两个链表的内容。
    • 释放链表内存，避免内存泄漏。

http://www.mrgr.cn/news/35937.html

相关文章：

  • Vue74 路由的props配置
  • 父母血型与子女血型对照表
  • AWS账单不支付账号会停用吗？
  • Spring Boot驱动的在线房产租赁服务
  • 【CentOS7】nginx部署前端 gunicorn部署flask后端并使用nginx反向代理
  • 引用reference作为函数返回
  • 细说机房安装带孔的通风防静电地板的原因
  • 【C++进阶】2024年了set、map还搞不懂底层细节？
  • 接口中心四大闭环：如何确保接口生命周期的完美呈现
  • C语言中的转义字符
  • 如何恢复被删除的 GitLab 项目？
  • 基于丹摩智算的`YoloV8-训练与测试
  • Python面向对象编程：类和对象①
  • ant design vue组件中table组件设置分组头部和固定总结栏
  • _RET_IP_ 和_THIS_IP_ 作用
  • 通信工程高级职称评审条件详细解读
  • Databend 为什么能帮用户降低 90% 成本？
  • 直播平台美颜功能开发方案：基于视频美颜SDK的集成详解
  • mybatis-plus公共字段自动填充fillStrategy()方法和strictFill()方法
  • FTP服务搭建