程序设计考试总结
程序设计考试总结 1.排序（冒泡算法） 冒泡排序是一种简单直观的排序算法，核心思想是通过重复遍历待排序序列，每次比较相邻的两个元素，若顺序错误则交换它们的位置，直到没有元素需要交换，排序完成。因其每轮会将最大（或最小）的元素 “浮” 到序列末端，类似气泡上升，故得名 “冒泡排序”。 一、核心原理 比较与交换：从序列起始位置开始，依次比较相邻的两个元素，若前一个元素大于后一个元素（升序排序），则交换两者位置。 一轮 “冒泡”：每完成一轮遍历，当前序列中最大的元素会被 “推” 到序列的末尾（无需再参与后续比较）。 重复执行：减少待排序序列的长度（排除已 “冒泡” 到末尾的元素），重复上述过程，直到整个序列有序。 二、排序步骤（以升序为例） 假设有待排序数组 [3, 1, 4, 1, 5, 9, 2, 6]，步骤如下： 第 1 轮：比较所有相邻元素，将最大元素 9 “浮” 到末尾，数组变为 [1, 3, 1, 4, 2, 5, 6, 9]（最后一个元素 9 已确定）。 第 2 轮：比较前 7 个元素，将次大元素 6 “浮” 到第 7 位，数组变为 [1, 1, 3, 2, 4, ...
数据结构--串（有KMP算法）
数据结构之串详解 一、串的定义与核心概念 串是数据结构中一种特殊的线性表，其特殊性体现在数据元素的类型被限定为字符。以下从多个维度详细解析串的核心概念： 1.1 串的基本定义 串的本质：由零个或多个字符组成的有限序列，通常记为 S = "a₁a₂...aₙ"（n≥0）。其中，S 为串名，aᵢ（1≤i≤n）为单个字符（可是字母、数字、标点等），n 为串的长度。例：S = "Data Structure" 是一个串，包含 14 个字符（空格也计入长度）。 特殊串的区分： 空串：长度为 0 的串，记为 ""（不含任何字符）。 空格串：由一个或多个空格组成的串，如 " " （长度为 3）。 注意：空串与空格串的本质区别 —— 空串无字符，空格串有字符（空格也是字符）。 1.2 子串与主串 子串：串中任意连续的字符组成的子序列。例如，串 "abcdef" 中，"bcd"、"f" 都是其子串。 主串：包含子串的原串。若 A 是 ...
PTA-学校-数据结构（带头结点的链队列的基本操作、循环队列入队出队、另类循环队列、舞伴问题）
1-5 带头结点的链队列的基本操作 分数 4 作者 黄复贤 单位 菏泽学院 实现链队列的入队列及出队列操作。 函数接口定义： Status QueueInsert(LinkQueue *Q,ElemType e)；Status QueueDelete(LinkQueue *Q,ElemType *e)； 其中 Q 和 e 都是用户传入的参数。 LinkQueue 的类型定义如下： typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode * next;}LNode,*LinkList;typedef struct { LinkList front,rear; /* 队头、队尾指针 */ }LinkQueue; 裁判测试程序样例： #include <stdio.h>#include<malloc.h>#define OK 1#define ERROR 0typedef int Status;typedef int E...
PTA-学校-数据结构（括号匹配、进制转换、用链栈实现将非负的十进制数转换为指定的进制数、在一个数组中实现两个堆栈）
1-1 括号匹配 分数 4 作者 黄龙军 单位 绍兴文理学院 要求实现函数，借助如下自定义栈SqStack判断一个中、小括符[、]、(、)组成的字符串中的括弧是否匹配，是则返回true，否则返回false。例如，[[()]]、([[()]])、(()[[]])是匹配的，而(((、()]、 ([(]))是不匹配的。 typedef char ElemType; // 为char取别名ElemTypestruct SqStack{ ElemType *base; // 顺序栈的首地址，动态数组的首地址 int top; // 栈顶指针，栈非空时，为栈顶元素的下标(从0开始) void Init( ); // 初始化栈 ElemType GetTop(); // 取栈顶元素 void Push(ElemType e)...
约瑟夫环的数学解法
#include <stdio.h>int main(){ int N, p; scanf("%d %d", &N, &p); int people[3001] = { 0 }; int i; for (i = 0; i < 3001; i++) { people[i] = i; } int k = N; int start = 1; int flag = 1; while (k > 0) { int pos = (start + p - 2) % k + 1; if (flag == 1) { printf("%d", people[pos]); flag = 0; } else { printf(" %d", people[pos]); } for (i = pos; i < k; i++) { people[i] = people...
数据结构遍历二叉树中序遍历的技巧
二叉树中序遍历总结（含栈的深度理解 一、什么是二叉树中序遍历 中序遍历的核心规则是 “左 - 根 - 右”：先中序遍历左子树，再访问根节点，最后中序遍历右子树。 以简单二叉树（根A，左孩子B，右孩子C）为例，中序遍历结果为 B → A → C（即BAC）。 二、普通递归方法（基于修正后的二叉树结构） 修正后的二叉树结构： A / \ B C / / \ D E F / \ \G H I 递归逻辑：通过 “函数调用栈” 隐式实现 “左 - 根 - 右” 的顺序。每调用一次遍历函数，就将当前节点压入系统栈，先处理左子树，再访问根，最后处理右子树。 步骤拆解： 遍历A的左子树B → 遍历B的左子树D → 遍历D的左子树G（无左子树，访问G）→ 访问D → 遍历D的右子树H（访问H）→ 访问B → 访问A → 遍历A的右子树C → 遍历C的左子树E（无左子树，访问E）→ 遍历E的右子树I（访问I）→ 访问C → 遍历C的右子树F（访问F）。 最终结果：GDHBAEICF。 三、非递归方法（显式栈模拟） 递归的本质是系统栈...