- 博客(21)
- 收藏
- 关注
RSS订阅原创 桃黑黑反斗战
4.显示动态规划中构建的二维数组 dp[i][j] 的过程（物品编号 i、容量 j）。# 2.实现一个动态规划算法，求解在给定容量下，能够装入背包的最大总价值。# 1.给定若干个物品，每个物品有重量和价值，背包容量为一定的正整数。# 3.输出最终最大价值，以及用于构造该最优值的物品组合（可选）。
2025-05-28 22:12:32
400
原创 数据结构——排序
/通过一趟排序，将待排序记录分割成独立的两部分，其中一个部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列排序。按辅助空间：原地排序（辅助空间用量为O（1）的排序方法，所占辅助空间与参加排序的数据量大小无关）和非原地排序（辅助空间用量超过O（1）的排序方法）-2、改变划分元素的方法，至多只能改变算法平均情况下的时间性能，无法改变最坏情况下的时间性能，即最坏情况下，快速排序的时间复杂性总是O(n^2)如此反复，得到一个有序序列的过程。（即使不用递归，也需要用用户栈）
2024-12-17 23:09:42
961
原创 数据结构——查找
被删除的结点只有左子树或者右子树，用其左（右）子树替换它（结点替换），其双亲结点的相应指针域的值改为“指向被删结点的左（右）子树”根据给定的某个值，在查找表中确定一个其关键字（用来标识一个数据元素的某个数据项的值）等于给定值。查找失败比较n+1次；*假定每个元素的查找概率相等，查找成功时ASL=（n+1)/nlog2 (n+1)-1。（3）查找效率：ASL=Lb(对索引表查找的ASL）+Lw（对块内查找的ASL）越大，表中记录数越多，说明表装的越满，发生冲突的可能性越大，查找时比较次数越多。
2024-12-15 12:34:05
1106
原创 数据结构--图
1、图的结构比较复杂，任意两个顶点之间都可能存在联系，无法以数据结构在存储区中的物理位置表示元素之间的关系。——> 图没有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的位置。2、数组（邻接矩阵）表示法：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。最简单的链式映像结构：多重链表表示图。*若考虑无向图的邻接矩阵的对称性，则可以用压缩存储的方式只存入矩阵下三角（或上三角）元素。*以二维数组表示有n个顶点的图时，需要存放n个顶点信息和n*n个弧信息的存储量。
2024-12-02 12:54:08
95
原创 树和森林（包括哈夫曼树）的概念及算法实现
（3）孩子兄弟表示法（二叉树表示法、二叉链表表示法）：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向第一个孩子结点和下一个兄弟结点。在哈夫曼树的每个分支上标0或1:结点左分支标0，右分支标1，把从根到每个叶子接的路径上的标号连接起来，作为该叶子代表的字符的编码。沿分支找到的所有右孩子，都与p的双亲用线连起来。树的路径长度：从树根到每个结点的路径长度之和（结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树）结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
2024-11-27 18:43:59
1077
原创 树和森林（from大书）
b)若F非空，B的根root为森林中第一颗树的根ROOT(T1),B 的左子树LB是从T1中根结点的子树森林F1={T11,T12...}转换而成的二叉树，其右子树RB是从森林法F'={T2,T3...}转换而成的二叉树。（3）孩子兄弟表示法（又称二叉树表示法，以二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。若把森林中第二颗树的根结点看成是第一颗根结点的兄弟，同样可以导出森林和二叉树的对应关系。
2024-11-16 15:02:32
585
原创 树和二叉树部分算法代码整理（持续补充更新ing）
概念：利用二叉链表中的空指针域：如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱，如果右孩子为空，则将空的右孩子指针域指向其后继。（2）队不空时循环：从队列中列一个结点*p，访问它：若他有左孩子结点，将左孩子进队；否则，递归左子树的深度记为m,递归计算右子树的深度记为n，二叉树的深度则为m与n的较大值+1。思想：如果是空树，递归结束；基本思想：（1）建立一个栈（2）根结点进栈，遍历左子树（3）根结点出栈，输出根结点，遍历右子树。遍历方法：共有六种（L：遍历左子树，D：访根结点，R：遍历右子树。
2024-11-10 16:02:16
360
原创 串的算法及实现（数据结构）/更新ing
在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组描述。然而，串的基本操作和线性表有很大差距：在串的基本操作中，通常以“串的整体”作为操作对象，而线性表大多以“单个元素”作为操作对象。为了便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。算法：若串T已经存在，则先释放串T所占空间，当串不为空时，首先为串T分配大小和串S长度相等的存储空间，然后将串S的值复制到串T中。(3)比较两个串的长度。
2024-10-19 23:59:03
229
原创 队列的表示和操作的实现
（2）将队空间设想成一个循环的表，即分配给队列m个存储单元可以循环使用，当rear为maxqsize时，若响亮的开始端空着，又可从头使用空着的空间。即将base[0]接在base[MAXQSIZE-1]之后，若rear+1==M,则令rear=0;插入元素：Q.base[Q.rear]=x;（1）另外设一个标志以区别队空、队满（2）另设一个变量，记录元素个数（3）少用一个元素空间。1、队列：仅在表尾进行插入操作，在表头进行删除操作的线性表，是一种先进先出的线性表。入队：base[rear]=x;
2024-10-14 21:01:00
484
原创 栈（数据结构）
3、栈在使用过程中所需最大空间的大小很难估计：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。可以设置两个常量，一个是存储空间🧑🍳分配量，一个是存储空间分配增量。2、顺序栈：栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。1、栈是限定仅在表尾进行插入或删除操作的线性表，表尾端称为栈顶top，表头端称为栈底bottom。栈又称为后进先出的线性表（简称LIFO结构）4、顺序栈基本操作的算法描述。
2024-10-04 16:13:06
258
原创 线性表的链式表示和实现（一些概念及主要算法）/持续更新/
由于链表的长度为隐含的，则第一个循环执行的条件是pa和pb皆非空，当其中一个为空时，说明有一个表的元素已经归并完，则只要将另一个表的剩余段链接pc所指结点之后即可。2.用线性链表表示线性表时，数据元素之间的逻辑关系是由节点中的指针域指示的，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据其存储的物理位置不相邻，这种存储结构为非顺序映像或链式映像。1.线性表的链式存储结构的特点是用一组任意的存储单元线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。静态链表：用数组描述的链表。
2024-09-22 10:49:33
355
原创 数据结构-线性表（顺序表）
3.归并算法：已知线性表LA和LB的数据元素按值非递减有序排列，现要求将LA和LB归并成一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足，可进行再分配，即为顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间。数据元素由数据项组成，在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称文件。顺序表的初始化操作就是为顺序表分配一个顶定义大小的数组空间，并将线性表的当前长度设置为0。
2024-09-16 10:48:34
435
原创 数据结构-绪论（偏概念）
3.数据元素之间的关系在计算机中有两种不同的表示方式：顺序映像（借助元素在存储器中的相对位置）、非顺序映像（借助指示元素存储地方的指针）。数据结构：数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。2.数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据对象：性质相同的数据元素的集合，是数据的一个子集。
2024-09-15 16:04:33
417
1
原创 C++ 模版与群体数据
10、链表类的数据成员：链表类表示的是一个顺序访问的线形群体，由一组用指针域串联的Node模版对象构成，对链表的任何操作都要由头结点开始，因此对于所有应用链表的程序来说，链表的头指针是必然要使用的，尾指针对许多应用来说也是有用的信息。因此在链表中应该包括完成上述操作的成员函数，以及为了实现这些函数而添加的一些辅助函数，为了方便链表类对象间的赋值，还应重载“=”运算符，另外由于面向对象的封装特性，还要提供一些接口函数。类是对一组对象的公共性质的抽象，而类模版则是对不同类的公共性质的抽象。
2024-06-08 19:05:23
954
原创 C++类的继承知识整理（概念部分）
3、类型兼容规则是指在需要基类对象的任何地方，都可以使用公有派生类的对象来替代，替代包括：派生类的对象可以隐含转换为基类对象、派生类的对象可以初始化基类的引用、派生类的指针可以隐含转换为基类的指针。在类族中，直接参与派生出某类的基类称为直接基类，基类的基类甚至更高层的基类称间接基类继承方式规定了如何访问从基类继承的成员（如果不显式地给出继承方式关键字，系统的默认值就是私有继承）。如果某派生类的多个基类拥有同名的成员，同时，派生类又新增这样的同名成员，在这种情况下，派生类成员将隐藏所有基类的同名成员。
2024-05-28 20:53:12
937
原创 C++指针及字符串模版和例题
4、通过指针访问类的静态数据成员。7、用getline 输入字符串。6、计算arr中元素的平均值。2、指向常量的指针做形参。
2024-05-28 16:04:13
312
原创 C++数组、指针、字符串。
11.this指针：是一个隐含于每一个类的静态成员函数中的特殊指针（包括构造函数和析构函数），它用于指向正在被成员函数操作的对象，它明确指出了成员函数当前所操作的数据所属的对象。3、与基本类型数组一样，在使用对象数组时也只能引用单个数组元素，每个数组元素都是一个对象，通过这个对象，可以访问到它的公有成员，一般形式是：数组名[下标表达式].成员名。提示：当局部作用域中声明了与类成员同名的标识符时，对该标识符的直接饮用代表的是局部作用域中所声明的标识符，这时为了访问该类成员，可以通过this指针。
2024-05-27 16:33:21
974
原创 C++多态概念整理➕一些例题
如果是双目运算符（B），左操作数是对象本身的数据，由this指针指出，右操作数则需要通过运算符重载函数的参数表来传递 要实现oprd1 B oped2,其中oprd1为A类的对象，则应该把B重载为A类的成员函数，该函数只有一个形参，形参的类型是oprd2所属的类型，重载后，该表达式就相当于调用oprd.operator B(oprd2)要重载的操作符的第一个操作数不是可以更改的类型，例如"
2024-05-27 10:36:39
557
原创 C++数据的共享与保护 概念整理
7、若类B中内嵌了类A的对象，但是B的成员函数却无法直接访问A的私有成员x,所以需要引出：友元关系：提供了不同类或对象的成员函数之间、类的成员函数与一般函数之间进行数据共享的机制。是在类中用关键字friend修饰的非成员函数。8、若A类为B类的友元类，则A类中的所有成员函数都是B类的友元函数，都可以访问B类中的私有和保护成员。X::m的方式用于访问类的静态成员 ptr->m这样的表达式，其中ptr指向X类的一个对象的指针。类属性是描述类的所有成员共有特征的一个数据项，对于任何对象实例，他的属性值相同。
2024-05-24 11:07:35
408
1
原创 C++类与对象 概念及代码例子整理
13、析构函数的调用执行顺序与构造函数正好相反（析构函数的函数体被执行完毕后，内嵌对象的析构函数被一一执行，这些内嵌对象的析构函数调用顺序与他们在组合类的定义中出现的次序恰好相反。3、封装：将抽象得到的数据和行为（或功能）相结合，形成一个有机的整体，也就是将数据与操作数据的函数代码进行有机的结合，形成“类”，其中数据和函数都是类的成员。和类的唯一区别在于，具有不同的默认访问控制属性。作为类的成员函数，构造函数可以直接访问类的所有数据成员，可以是内联函数，可以带有参数表，可以带有默认的形参值，也可以重载。
2024-05-23 21:25:54
988
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人