通过链表实现栈

构建数组栈类 代码 运行结果

对角矩阵类（部分方法C++） 代码 结果

创建矩阵类（C++）

创建和使用不规则二维数组

并查集解决在线等价类问题

箱排序 假定用一个链表保存一个班级学生清单。结点的数据有：学生姓名和考试分数。假设分数是0~100的整数。 采用箱排序可以把分数相同的结点放在同一个箱子里，然后把箱子连接起来就得到了有序的链表 链表定义 结点定义 箱排序方法定义 全部代码 输入 输出

单向链表实现

利用vector实现的基于数组的线性表

动态数组（C++）

一元多项式的乘法与加法运算 设计函数分别求两个一元多项式的乘积与和 输入格式 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。 输出格式 输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数…

二叉搜索树的操作集 本题要求实现给定二叉搜索树的5种常用操作 函数接口定义 其中`BinTree`结构定义如下： - 函数`Insert`将`X`插入二叉搜索树`BST`并返回结果树的根结点指针； - 函数`Delete`将`X`从二叉搜索树`BST`中删除，并返回结果树的根结点指针；如果`X`不在树中，则打…

先序输出叶结点 本题要求按照先序遍历顺序输出给定二叉树的叶节点 函数接口定义 其中`BinTree`结构定义如下： 函数`PreorderPrintLeaves`应按照先序遍历的顺序输出给定二叉树`BT`的叶结点，格式为一个空格跟着一个字符。 裁判测试程序样例 输出样例（对于图中给出的树） 代码

求二叉树高度 本题要求给定二叉树的高度 函数接口定义 其中`BinTree`结构定义如下： 要求函数返回给定二叉树BT的高度值。 裁判测试程序样例 输入样例（对于图中给出的树） 代码

二分查找 本题要求实现二分查找算法。 函数接口定义 其中`List`结构定义如下： `L`是用户传入的一个线性表，其中`ElementType`元素可以通过 、==、<进行比较，并且题目保证传入的数据是递增有序的。函数`BinarySearch`要查找`X`在`Data`中的位置，即数组下标（注意：元素从下标…

二叉树的遍历 本题要求给定二叉树的4种遍历 函数接口定义 其中`BinTree`结构定义如下： 要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。 裁判测试程序样例 输入样例 输出样例 代码

在一个数组中实现两个堆栈 本题要求在数组中实现两个堆栈 函数接口定义 其中`Tag`是堆栈编号，取1或2；`MaxSize`堆栈数组的规模；`Stack`结构定义如下： 注意：如果堆栈已满，`Push`函数必须输出“Stack Full”并且返回false；如果某堆栈是空的，则`Pop`函数必须输出“Stac…

快速排序（C语言实现）

带头结点的链式表操作集 本题要求实现带头结点的链式表操作集 函数接口定义 其中List结构定义如下 各个操作函数的定义为： `Position Find List L, ElementType X `：返回线性表中首次出现X的位置。若找不到则返回ERROR； `List Insert List L, Elem…

链式表操作集 本题要求实现链式表的操作集 函数接口定义 其中List结构定义如下 各个操作函数的定义为： `Position Find List L, ElementType X `：返回线性表中首次出现X的位置。若找不到则返回ERROR； `List Insert List L, ElementType X…

链式表的按序号查找 本题要求实现一个函数，找到并返回链式表的第K个元素、 函数接口定义 其中List结构定义如下： L是给定单链表，函数FindKth要返回链式表的第K个元素。如果该元素不存在，则返回ERROR 裁判测试程序样例 输入样例 1 3 4 5 2 -1 6 3 6 1 5 4 2 输出样例 代码

求链式表的表长 本题要求实现一个函数，求链式表的表厂。 函数式接口定义 其中List结构定义如下： L是给定单链表，函数Length要返回链式表的长度。 裁判测试程序样例 输入样例 输出样例 代码

顺序表操作集 本题要求实现顺序表的操作集 函数接口定义 其中List结构定义如下 各个操作函数的定义为： `List MakeEmpty `：创建并返回一个空的线性表； `Position Find List L, ElementType X `：返回线性表中X的位置。若找不到则返回ERROR； `bool…

单链表逆转 本题要求实现一个函数，将给定的单链表逆转 函数接口定义 其中List结构定义如下： L是给定单链表，函数Reverse要返回被逆转后的链表 裁判测试程序样例： 输入样例： 5 1 3 4 5 2 输出样例： 代码： 图示

自测-1 打印沙漏 要求写个程序把给定的符号打印成沙漏的形状。例如给定17个“ ”，要求按下列格式打印 所谓“沙漏形状”，是指每行输出奇数个符号；各行符号中心对齐；相邻两行符号数差2；符号数先从大到小顺序递减到1，再从小到大顺序递增；首尾符号数相等。 给定任意N个符号，不一定能正好组成一个沙漏。要求打印出的沙…

AvlTree

Divide-and-conquer algorithm in multiplication $$ x^n=x\cdot x\cdot x\cdots x $$ 时间复杂度为O n ，有n-1个乘法 $$ x^n=x^\frac n2\cdot x^\frac n2\qquad\mbox if x is ev…

BinarySearchTree

一元多项式的加法与乘法运算 题意理解 设计函数分别求两个一元多项式的乘积与和 求解思路 1. 多项式表示 2. 程序框架 3. 读多项式 4. 加法实现 5. 乘法实现 6. 多项式输出 多项式的表示 仅表示非零项 - 数组 - 编程简单、调试容易 - 需要事先确定数组大小 一种比较好的实现方法是：动态数组…

多项式加法运算 采用不带头结点的 单向链表 ，按照 指数递减 的顺序排列各项 算法思路 ：两个指针P1和P2分别指向这两个多项式第一个结点，不断循环： - P1- expon == P2- expon：系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项 - P1- expo…

队列 队列（Queue） ：具有一定操作约束的线性表 - 插入和删除操作 ：只能在 一端插入 ，而在 另一端删除 - 数据插入：入队（AddQ） - 数据删除：出队列（DeleteQ） - 先来先服务 - 先进先出 ：FIFO 类型名称：队列（Queue） 数据对象集：一个有0个或多个元素的有穷线性表 操作集…

堆栈 堆栈的抽象数据类型描述 类型名称 ：堆栈（Stack） 对象数据集 ：一个有0个或多个元素的有穷线性表 操作集 ：长度为MaxSize的堆栈$S\in Stack$，堆栈元素$item\in ElementType$ 1. Stack CreateStack int MaxSize ：生成空堆栈，其最大…

广义表 - 广义表是 线性表的推广 ； - 对于线性表而言，n个元素都是基本的 单元素； - 广义表中，这些元素不仅可以是单元素也可以是 另一个广义表 ； 多重链表 多重链表：链表中的结点可能同时隶属于多个链 - 多重链表中结点的 指针域会有多个 ，如前面包含了 Next 和 SubList 两个指针域 -…

线性表 什么是线性表 “线性表（Linear List）”：由同类型数据元素构成有序序列的线性结构 - 表中元素个数称为线性表的长度 - 线性表没有元素时，称为空表 - 表起始位置称表头，表结束位置称表尾 线性表的抽象数据类型描述 类型名称：线性表 数据对象集：线性表是$n \ge0 $个元素构成的有序序列$…

求最大子列和 给定$N$个整数的序列$ A 1,A 2,\cdots,A N $，求函数$f i,j =\max \ 0,\sum k=i ^jA k\ $ 算法一 算法二 算法三 递归算法： $O N =O \frac N2 +O \frac N2 +cN=2O \frac N2 +cN\\=2^kO 1…

计算给定多项式在给定点$x$处的值 方法1 $$f x =a 0+a 1x+\cdots+a n-1 x^ n-1 +a nx^n$$ 方法2 多项式可以拆成如下形式： $$ f x =a 0+x a 1+x \cdots a n-1 +x a n \cdots $$ 计算给定多项式$f x =\sum i=…

数列求和 描述 给定某数字a（1≤a≤9）以及非负整数n（0≤n≤100000），求数列之和sum=a+aa+aaa+⋯+aa⋯a（n个a）。例如a=2, n=3时，sum=2+22+222=246。 输入格式 输入有两行：‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮…

鸡兔同笼 描述 大约在1500年前，《孙子算经》中就记载了这个有趣的问题。书中是这样叙述的： 今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？ 这四句话的意思是： 有若干只鸡兔同在一个笼子里，从上面数，有35个头，从下面数，有94只脚。问笼中各有多少只鸡和兔？‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪…

棋盘放米 描述 相传古代印度国王舍罕要褒赏他的聪明能干的宰相达依尔 （国际象棋发明者），问他需要什么，达依尔回答说：“国王只要在国际象棋的棋盘第一个格子里放一粒麦子，第二个格子里放两粒，第三个格子里放四粒，按此比例以后每一格加一倍，一直放到64格（国际象棋棋盘是8×8=64格），我就感恩不尽，其他的我什么也不…

鸡兔同笼 描述 一个笼子里面关了若干只鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里脚的总数为a,则笼子里面至少有多少只动物，至多有多少只动物？ 输入格式 第1行输入一个正整数n（n≤1000）,表示测试数据的组数n，接下来n组测试数据每组一行，每行一个正整数a a<32768）。提示： 输…