3 vector<>

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 12w+

【数据结构】-树-计算huffman树的wpl

wpl=非叶子结点的权值之和使用上面这个方法的前提是,是一棵huffman树才行,对普通的树没有这个说法。int wpl = 0;void WPL(BiTree T) { if (T != NULL) { if (T-&gt;lchild || T-&gt;rchild) wpl=wpl+T-&gt;data; WPL(T-&gt;lchild); WPL(T-&gt;rchild); }}int main() { BiTree T; cout &lt;&lt

2020-08-07 17:06:00

【数据结构】-单链表-【2019真题】按要求重新排列单链表

思路:p指针指向第一个结点,q为p的后继节点,r指针指向未处理的最后一个结点,每一轮都将p的后继指针指向r,r的后继指针指向q, 随后将p,q向后移动一个结点,并重新将r定位到未处理的最后一个结点。LinkList reSort(LinkList L) { LNode*p = L-&gt;next; LNode *q = p-&gt;next; LNode *r = L-&gt;next; LNode *new_r = NULL; while (r-&gt;next) r = ...

2020-08-04 22:43:01

【数据结构】-树-【2017真题】表达式树转中缀表达式

1.思路:按照中序遍历输出整棵树,并在适当的位置加上括号即可,关键在于如何加括号,第一次做题的时候没有想出来怎么加括号。加括号的方法:观察表达式的结构可以知道,根节点将表达式分成左右两个部分,因此根节点不可能包含在任何一个括号内,并且只要不是叶子结点就说明有“子表达式”存在。除了叶子结点和根节点之外,在其他节点的左子树遍历之前加上左括号,在右子树遍历之后加上右括号。因此算法就是对普通的中序遍历进行改进,改进过程关键是如何识别根节点和叶子结点。参考答案给出识别根节点的办法是对每一个结点求深度...

2020-08-02 21:41:49

【数据结构】-排序-【2016真题】-划分满足要求的两个子集

1.思路: //划分规则:元素个数尽可能相同,元素值和尽可能相差大,整数集合中不会有相同元素,因此可以按照下面的思路划分 //第一步,将数组A中的所有元素从小到大排序; //第二步,如果是偶数个元素,则前n/2个划分在A1,后n/2个划分在A2;如果是奇数个元素,前n/2向下取整个在A1,后n/2向下取整+1个在A2 //第一种情况元素个数相差0,第二种情况元素个数相差1。2.要使排序效率尽可能高,肯定是快速排序,笔者之前详细写过快速排序的过程,但是答案用的是非递归的快速...

2020-07-28 21:53:52

【数据结构】-线性表-【2013真题】找出数组的主元

值得注意的是,这个题目就算写出来是n2的时间复杂度,最后给的分数也只扣了一分,所以花大量时间来思考时间复杂度最高的算法是得不偿失的,应该在短时间内精进自己第一时间想到的那个算法。 //思路: //由于ai的取值只可能是0-n-1中中间的整数,因此可以创建一个大小为n的整数数组showtime来记录ai出现的次数 //shotime[j]&gt;n/2说明j就是主元,若找不到这样的j则返回-1. //时间复杂度n;空间复杂度:n答案: //出现的次数大于所有元素...

2020-07-27 21:45:51

【数据结构】-单链表-【2012真题】-查找共同后缀的起始位置

https://blog.csdn.net/qq_39328436/article/details/106715561与之前做的一个练习题,去单链表的公共节点大同小异。练习题时还写得更加简洁一点。2012年真题思路:分别求得两个链表的长度,长链表长度为longer,短链表长度为shorter,设置两个遍历指针,long和short,长链表从第longer-shorter+1个位置开始,锻炼表从第一个位置开始,同时遍历,当两个指向同一个节点的时候就是目标节点。时间复杂度:主要消耗在求两个单链表

2020-07-26 20:33:57

【数据结构】-单链表-【2015真题】删除绝对值第二次出现的节点

1.算法思路:创建一个大小为n的数组showtime,标记绝对值出现的次数,并且初试化为0;遍历指针p,以及p的前驱指针pre。遍历单链表,求链表节点绝对值x,以x为下标查找showtime中的值,若showtime[x]=0,则修改showtime[x]为1,并继续遍历若showtime[x]=1时要删除p指针指向的节点。2.单链表节点的数据类型定义:typedef struct LNode{int data;struct LNode* next;}LNode,*LinkList;3

2020-07-25 14:41:45

【数据结构】-线性表-【2018真题】找出未出现的最小正整数

原本我的思路:创建一个大数组show,表示整数数组是否出现的标记。遍历整数数组,把以该整数为下标的show中的值改为1(如果是负数统一修改0位置上的标记)遍历show,第一个不为1的位置就是答案,时间复杂度为o(n),空间复杂度由整数数组的最大值决定。虽然把握住了“空间换时间”的精髓,但是未免也要得太多了,发生错误的关键在于,没有把握结果只可能是1-n+1中的一个正整数。int find_min(vector&lt;int&gt; A) { vector&lt;int&gt; B(A..

2020-07-24 17:43:53

【数据结构】-单链表-不断删除并输出循环单链表的最小节点

刚开始做这个题目的时候,设置了五个指针,pre_p,p,min.pre_min还有q,用q来做内循环,当p==q的时候标记内循环结束,后来发现多此一举了。既然内循环每次从第一个节点开始,那么内循环结束的标价就是p==L,想得太复杂了。编程注意事项:外循环标记:L-&gt;next!=L内循环标记:p!=L;例子如下:...

2020-07-23 14:30:08

【数据结构】-单链表-查找链表中倒数第k个位置上的节点

2009统考真题思路很巧妙两个指针:p指针先向前走k步,然后pq一起移动,这样,q永远都在p前面k个位置,所以当p到达链表尾部的时候,q就是尾部之前的k位置,也就是倒数k位置。 bool findTail_K(LinkList List,int k) { LNode *p = List-&gt;next; LNode *q = List-&gt;next; int step = 0; while (step&lt;k) { p = p-&gt;next; .

2020-07-21 20:47:52

【数据结构】-单链表-按照递减的顺序合并两个递增的单链表

这道题融汇了单链表编程中的几个重要技巧1.前后指针2.头指针next设置为空,用原始节点组合成新的单链表根据下面这个例子不难看懂 LinkList Re_Con_Sort(LinkList L, LinkList M){ LNode*p = L-&gt;next, *q = M-&gt;next; LNode *p_rear = NULL; LNode *q_rear = NULL; L-&gt;next = NULL; M-&gt;ne...

2020-07-20 21:02:00

【数据结构】-图-用DFS实现拓扑排序

void BubbleSort(vector&lt;int&gt; &amp;p, int length,vector&lt;int&gt; &amp;ind_diff){ for (int m = 0; m &lt; length; m++) { ind_diff[m] = m; } for (int i = 0; i &lt; length; i++) { for (int j = 0; j &lt; length - i - 1; j++) { if (p[j] &g.

2020-07-19 20:02:59

【数据结构】-单链表-将一个单链表奇偶位置节点原地拆分成两个单链表

L=a1,b1,a2,b2,....an,bn返回值:a1,a2,a3,.....an原始单链表:b1,b2,b3..bn LinkList split(LinkList &amp;L) { //分成的两个单链表一个是返回值M,另一个在原始单链表L中 LNode *p = L-&gt;next; LNode *q = p-&gt;next; LinkList M = (LinkList)malloc(sizeof(LNode)); M-&gt;next = ..

2020-07-18 16:28:45

【数据结构】-图-判断图中是否存在vi到vj的路径

方法一:深度优先,不断向前走,采用递归形式比较简单,下图是递归的例子编程注意事项:1.递归出口:i==j2.判断i到j是否存在路径,把问题化解到最简单的情况,一步一步向前走,能向前迈步的条件是:本次已经有连通路径,并且下一个要加进来的点没被访问过。bool exit_path(ALGraph G, int i, int j) { if (i == j)return true; else { visited[i] = true; for (ArcNode* p = G.

2020-07-16 17:04:28

【数据结构】-单链表-按递增顺序输出单链表节点的值

思路:采用最简单的打擂台的办法,题目要求删除节点,因此必须保留前驱。引入遍历指针p,前驱指针pre,最小值指针min,最小值前驱pre_min。(最小值前驱可以省略,但是加入之后会使得程序更加清晰,况且一个指针的内存开销也不大)。编程注意事项:1.教材上最后free(L)了,个人觉得好像没有必要,只要将节点全部删除一直到最后L-&gt;next=null即可。2.要明白free(p)干了什么,它只是把p所指向的内存空间交还给了操作系统,并不会将指针变为null,所以建议每次用完free后,手

2020-07-15 17:12:31

【数据结构】-排序-基于单链表的简单选择排序

方法一:不进行任何断链插入操作,找到目标节点之后,只是交换data值,这个思路很简单,与简单选择排序的思路一摸一样。编程注意事项:min不能标记最小值,应该要标记最小值对应的链表节点LinkList createLink(LinkList L) { cout &lt;&lt; "尾插法创建单链表:"&lt;&lt;endl; int a; L = (LinkList)malloc(sizeof(LinkNode)); L-&gt;next = NULL; LinkNode *p=L,

2020-07-12 11:08:18

【数据结构】-图-输出顶点u到v的所有简单路径

思路:一步一步递归向下走,以下面这个图为例,详细的递归过程如下所示:编程注意事项:1.path数组少为开大一点,避免越界2.一定记得返回之前要把visited恢复3.path和visited要加引用,但是d一定不能加void printPath(vector&lt;int&gt; &amp;path,int d) { for (int i = 0; i &lt;= d; i++) cout &lt;&lt; path[i] &lt;&lt; " ";...

2020-07-08 11:47:00

【数据结构】-图-判断一个无向图是否是一棵树

思路:判断一个无向图是否是一棵树,只需要判断该图是否是一个包含n个顶点的连通子图且边数为n-1,只要这两个条件都满足,那么就是一棵树。因此我们可以采用深度遍历,若图连通,那么只要一次深度遍历就可以遍历出所有的顶点,于是只需要调用一次dfs,并设置两个计数器记录边和顶点的数目即可。变成注意事项:邻接表在存储无向图的时, 每一条边都存储了两次,所以计数器中得到的是两边的边数void DFS_my(ALGraph &amp;G, int v, int &amp;count_vec, int &a

2020-07-08 09:35:42

【数据结构】-单链表-判断序列B是否是序列A的连续子序列

算法思路:用两个指针来遍历两个单链表,当节点值相同的时候,两个指针同时向后移动一个位置当节点值不相同的时候,A表的指针继续向后面遍历,B表的指针回到头部重新开始遍历例子如下: bool isSon(LinkList A, LinkList B) { LNode *p,*q; p = A-&gt;next; q = B-&gt;next; while (p) { if (p-&gt;data != q-&gt;data) { p = p-&gt;n.

2020-07-07 14:29:51

【数据结构】-排序-快速排序的改进算法

快速排序的最好情况是每一趟排序的基准值都将序列划分成两个长度尽可能一样的序列在默认情况下,我们通常选择第一个元素作为基准值,但是,则会有问题。最坏情况是原序列顺序和逆序的情况,此时基准值左右的序列长度一个是0,一个是n-1即使序列原本就是顺序的,但是快排它无法判断有序,还是不断地做比较;逆序的情况下是不断地比较,不断地移动元素。因此,将基准值的选取对快排的效率有很大的影响,我们用“随机”法和“三数取中”法来选取基准值,这样的方法基本可以避免上述两种最坏的情况发生。编程注意事项:1.c

2020-07-05 09:53:40

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。