2019-02-14 00:12:51 weixin_43891901 阅读数 97

1.递推算法的思想:

	利用已知的条件不断推导未知的信息。

2.递推算法的分类:

(1).顺推法
(2).逆推法

3.逆推算法的应用:

《斐波那契数列》

  • 问题:斐波那契数列又叫兔子数
    月数:1 2 3 4 5 6 7 8…
    对数:1 1 2 3 5 8 13 21…
  • (1).解决核心思想:
    将数字转化成一个公式模型

  • (2).递推公式模型:
    F(1=F(2)=1F(1)=F(2)=1

    F(n)=F(n1)+F(n2)F(n)=F(n-1)+F(n-2)


4.代码示例:

首先头文件分别定义stdio.h引用库函数
其次#define NUM 13

int main()
{
int i;
int F[NUM] = { 1,1 };//保存兔子的初始数据
for (i = 2; i <NUM; i++)
{
	F[i] = F[i - 1]+F[i - 2];
}
for (i = 0; i < NUM; i++)
	printf("第%d月兔子总数:%d\n", i, F[i]);
return 0;
}

5.执行程序图:

执行效果图

2020-02-06 03:05:17 weixin_44611116 阅读数 19

约瑟夫问题及其变种(递推法)全网最详细讲解

为什么写这篇文章?

做刘汝佳老师的训练指南的UVAlive-4727这一题时又一次遇到了约瑟夫问题,之前训练指南的例题部分有讲过约瑟夫问题,刘汝佳老师讲的不是很清楚,就只记了公式,没有深究了。但是又一次遇到这个问题,而且在原来的要求上增加了新的要求,于是就又想了想。
在网上查了一些文章,实在是看不懂,写的太不友好了。不知道是他们也没有理解透彻,还是我太笨了。于时绞尽脑汁,终于理解了约瑟夫问题以及他的变种。
反过来再看网上的很多文章,实在是认为该写一篇文章来把这个问题讲透,讲明白。于是,终于写下了我的第一篇文章。以前从来没写过这些东西,所以格式什么的可能不太好看,还请包含。文章比较长,但是我相信,你看完后一定会有很大收获。废话不多说了,进入正题。

问题描述

约瑟夫问题

普通的约瑟夫问题是把n个人(下标0~n-1)组成一个圆环,从第一个人开始报数,报到第k个时此人出队,然后他后面的人接着这样做,每次出队一人,直到没人为止。

UVAlive-4727,Jump问题描述

约瑟夫问题只要求你求出最后一个出队的是谁,而本题则要求你求出最后三个。

(普通)约瑟夫问题的理解

大多数文章直接告诉你一个递推公式 f(n)=(f(n1)+k)%nf(n) = (f(n-1)+ k)\%n ,然后可能会带着你推导这个式子。但是他们绝大多数人忽略了一个最终要最基本的问题,f(n)f(n)是什么,他有什么意义?
首先从理解f(n)f(n)开始。现阶段我们可以简单的将它理解为nn个人组成的环中最后一个出队的人的下标。在接下来的推导过程中,你要时刻牢记我们对f(n)f(n)意义的定义。

考虑一个n=10,k=3n=10,k=3的约瑟夫问题。
蓝色是轮次,绿色是下标,黄色是删除元素
其中蓝色是进行的轮次,绿色是下标,黄色是删除的元素,最后两行元素个数不够,因此做了重复处理,以便看清删除的是谁。
在这里插入图片描述
绿色的行是下标。下面我们只关注第一次操作,我们把数组向左移动kk个,由于是一个环所以头部的数会移到尾部,而第一次删除的元素“恰好”是移到尾部的元素。

接下来关注下一次循环,下一次循环将会从哪里开始呢?没错,它将会从上面表格最后一行的数字3开始继续报数。3是它之前的下标,而在新的一行中,它的下标变为了0,规模变为了n1n-1

将原序列左移kk位后再删除的好处是什么呢?这样做就环不会断了!比如第二次删除时,将现在的队列左移3位后(注意黄色的数字不在序列中,不要动)再删除尾部的元素,如图。我们不断重复以上操作:左移kk位,删除尾元素,规模-1。
在这里插入图片描述
接下来关注f(n)f(n),还记得之前定义的f(n)f(n)是什么意义么?f(n)f(n)nn个人组成的环中最后一个出队的人的下标。在最后一次删除操作之前该下标都不是黄色的,也就是说它每次都将向左移动kk位,然后获取一个新的下标。一个规模为nn的问题,最后一个要被删除的元素在进行第一次左移之后它的下标会减少kk,由于是环因此要取模,最后一个要被删除的元素的新下标为变(f(n)k)%n(f(n)-k)\%n,而新下标为n1n-1的元素(尾元素)将会被删除。

至此,问题的规模将变为n1n-1,而n1n-1个人组成的环中最后一个出队的人的下标这就是我们定义中的f(n1)f(n-1)的意义。于是有f(n1)=(f(n)k)%nf(n-1)=(f(n)-k)\%n,用通俗的话翻译一下就是:n1n-1个人组成的环中最后一个出队的人的下标 = nn个人组成的环中最后一个出队的人的下标向左移动kk个单位的新下标。反过来就有f(n)=(f(n1)+k)%nf(n)=(f(n-1)+k)\%n.
于是:
f(n)=(f(n1)+k)%nf(n)=(f(n-1)+k)\%n
f(n1)=(f(n2)+k)%(n1)f(n-1)=(f(n-2)+k)\%(n-1)
f(n2)=(f(n3)+k)%(n2)f(n-2)=(f(n-3)+k)\%(n-2)
……
为了避免误会,递推公式应该写为f(i)=(f(i1)+k)%if(i)=(f(i-1)+k)\%i.

再次强调f(n)f(n)的意义是nn个人组成的环中最后一个出队的人的下标。那么在哪里会比较特殊呢?很容易想到当问题规模为1时,有f(1)=0f(1)=0,即1个人组成的环中最后一个出队的人的下标为0,正确性是显然的,因为只有一个元素。根据这一公式和边界条件可以得出以下代码:

#include<iostream>
using namespace std;

const int maxn=10000+5;
int f[maxn];
int n,k;

int main() {
	scanf("%d%d",&n,&k);
	f[1]=0;									//只有一个元素,则最后一个出队元素下标一定是0
	for(int i=2;i<=n;i++) f[i]=(f[i-1]+k)%i;
	printf("%d\n",f[n]+1);					//由于题目往往说的是从1到n,因此实际答案为下标+1
	return 0;
}

注意到如果题目只是普通的约瑟夫问题,存储f(n)f(n)是不必要的,尤其是在nn较大的情况下。因此进一步优化代码:

#include<iostream>
using namespace std;

int n,k;

int main() {
	scanf("%d%d",&n,&k);
	int ans=0;								//只有一个元素,则最后一个出队元素下标一定是0
	for(int i=2;i<=n;i++) ans=(ans+k)%i;
	printf("%d\n",ans+1);					//由于题目往往说的是从1到n,因此实际答案为下标+1
	return 0;
}

至此,普通的约瑟夫问题解决了。

(约瑟夫问题的变种) UVAlive-4727,Jump

在本题中,题目要求求出最后三个出队的人,而普通约瑟夫问题则是只求最后一个出队的人。

这题我在没有理解f(n)f(n)时想的是直接将循环中的i<=ni<=n变为i<=n1i<=n-1i<=n2i<=n-2。然而,得到的答案却是错误的。上网看了几个题解,都不是很清楚,直到我终于理解了f(n)f(n)的意义,才变得豁然开朗。

好了,在复习一遍f(n)f(n)的意义,nn个人组成的环中最后一个出队的人的下标。也就是说ff这个数组始终都是代表了最后一个出队的人的下标。因此,简单的将nn变为n1n-1并不能是倒数第二个出队的人的下标。

那么该如何解决这一问题呢?仿佛无从下手,因为我们的ff始终是最后一个出队的人的下标,要想通过它求的倒数第二个乃至倒数第三个出队人的初始下标好像很困难。

还记得第一次描述f[n]f[n]的意义时我说的“现阶段可以简单理解为……”么?是的!这一定义太过狭隘,以至于我们在递推时束手束脚。f(n)f(n)既然代表了下标,那么经过我们上面说的左移kk个单位,删除尾元素,规模-1的操作后,只要是之前未被删除的元素它们的下标都会和最后一个出队的人的下标的变化规律相同,即都符合f(i)=(f(i1)+k)%if(i)=(f(i-1)+k)\%i这一递推式。

我们可以扩展f(n)f(n)的意义,新定义的f(n)f(n)意为nn个人组成的环中之前未出队的人的下标。这一定义可能有些抽象,我们重新定义一个更加具体的定义,定义f(i,j)f(i,j)表示ii个人组成的环中倒数第jj个出队的人的下标。具体到本题,我们只需要f(n,1),f(n,2),f(n,3),f(n,1),f(n,2),f(n,3),分别表示倒数第1,2,3个出队的人的下标。他们都满足f(i)=(f(i1)+k)%if(i)=(f(i-1)+k)\%i.

唯一不同的是边界条件f(1,1)=0f(1,1)=0的意义和普通约瑟夫问题一样。而考虑倒数第2个出队的人的下标的特征,它会在只剩下2个人时的那次左移后移动到尾元素位置,然后被删除。也就是它的下标应满足f(2,2)=(k1)%2,f(2,2)=(k-1)\%2, 即在尾部,接下来会被删除。同理有f(3,3)=(k1)%3,f(3,3)=(k-1)\%3,,即倒数第3个出队的元素的下标会在问题规模变为3时被移动到尾部进而被删除(实际根据这一定义可以得出有f(i,i)=(k1)%if(i,i)=(k-1)\%i)。

根据上述定义可以写出代码:

#include<iostream>
using namespace std;

const int maxn=500000 5;
int f[maxn][3];							//分别表示倒数第1、2、3个出队的人的坐标变化情况
int n,k;

int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&k);
		for(int i=1;i<=3;i++) {
			f[i][i-1]=(k-1)%i;
			for(int j=i 1;j<=n;j++) f[j][i-1]=(f[j-1][i-1]+k)%j;
		}
		printf("%d %d %d\n",f[n][2]+1,f[n][1]+1,f[n][0]+1);		//由于题目是1~n,因此答案为下标+1
	}
	return 0;
}

我们注意到,这一代码是正确的,但是开辟了过多的空间,虽然仍可AC,但是仍然可以向普通的约瑟夫问题那样优化。除此之外,我们定义的状态非常具体,具体到了它是倒数第几个出队的,这实际上是没有必要的。我们回到我们起初使用的抽象的定义上。即定义f(n)f(n)意为nn个人组成的环中之前未出队的人的下标,而至于这个人具体是谁我们隐藏起来,不显式的写出来。经过这样的两个优化后新的代码为:

#include<iostream>
using namespace std;

int n,k;

int main() {
	int  T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&k);
		for(int i=3;i>=1;i--) {				//i隐式的指出当前的值是倒数第i个出队的下标
			int ans=(k-1)%i;				//初始化边界
			for(int j=i 1;j<=n;j++) ans=(ans+k)%j;
			printf("%d",ans+1);				//由于题目是1~n,因此答案为下标 1
			if(i==1) printf("\n");
			else printf(" ");
		}
	}
	return 0;
}

进一步的思考

注意到求倒数后三个出队的人的下标时,我们实际上是将每个人的下标都追踪了一遍,每次这样做的成本是O(n)O(n)。如果要求倒数后mm个出队的人(也可以是任意指定的m个人)的下标,我们就要追踪mm次,总的时间成本为O(mn)O(mn),是否有更高效的方法呢?

mm较大时,仍然使用这一算法的效果可能并不好,比如m=nm=n时,它要大约n2/2n^2/2次计算,时间复杂度为O(n2)O(n^2)。因此当mm很大,而kk又较小时可以直接用循环数组或链表进行模拟,时间复杂度为O(kn)O(kn)

以上是我对约瑟夫算法及其变种的一些理解,希望对你有帮助。如有错误还望指正。

2014-11-03 20:43:32 guugle2010 阅读数 1337
数据结构是算法实现的基础,算法总是要依赖于某种数据结构来实现的。往往是在发展一种算法的时候,构建了适合于这种算法的数据结构。一种数据结构如果脱离了算法,也就没有存在的价值了。
算法的作用----解决任何一个实际问题,都不可避免地涉及到算法的问题,通过一定的算法,得到一个最优(或较优)的方案。
递推算法:递推算法是一种简单的算法,即通过已知条件,利用特定关系得出中间推论,直至得到结果的算法。
顺推法:从已知条件出发,逐步推算出要解决的问题的方法。
逆推法:从已知问题的结果出发,用迭代表达式逐步推算出问题的开始的条件,即顺推法的逆过程。

顺推实例:
兔子繁殖过程

c++代码:
#include<iostream>
int main()
{
    using namespace std;
    const int NUM = 13;
    int count = 0;
    int rabbit[NUM] = {1,1};
    for (int i=0; i<NUM-2; i++)
    {
        rabbit[i+2] = rabbit[i] + rabbit[i+1];
    }
    for (int j=0; j<NUM; j++)
    {
        cout << j << "月兔子总数: " << rabbit[j] << "只\n";
    }
    return 0;
}
php代码:
<?php
   $rabbit = array();
   $rabbit[1] = $rabbit[0] =1;
   define("MONTH", 12);
   for ($i=2; $i<=MONTH; $i++) {
       $rabbit[$i] = $rabbit[$i-2] + $rabbit[$i-1];
   }
   for ($i=0; $i<=MONTH; $i++) {
       echo "第 " . $i . " 月,兔子总数量为:". $rabbit[$i] . "只<br/>";
   }
?>
C++编译运行结果


逆推实例
父亲准备为小龙的四年大学生活一次性储蓄一笔钱,使用整存零取的方式,控制小龙每月月底取1000元准备下月使用。假设银行整存领取的年息为1.71%,请算出父亲至少需要存入多少钱才行。
c++代码:
#include<iostream>
int main()
{
    using namespace std;
    const double RATE = 0.0171;
    double money[48];
    money[47] = 1000;
    for (int i=47; i>0; i--)
    {
        money[i-1] = (money[i] + 1000)/(1+RATE/12);
    }
    for (int j=47; j>0; j--)
    {
        cout << "第 " << j << " 月本利合计为: " << money[j] << " 元\n";
    }
    return 0;
}

php代码:
<?php
    $month = array();
 $month[47] = 1000;
 define("RATE", 0.0171);
 for ($i=47; $i>0; $i--) {
     $month[$i-1] = ($month[$i] + 1000)/(1+RATE/12);
 }
 for ($i=47; $i>0; $i--) {
     echo "第 " . $i . " 月本息合计为:" . $month[$i] . "元<br />";
 }
?>
C++编译运行结果



2018-11-28 20:40:16 qq_37457432 阅读数 86

数据结构与算法

 

1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报

2、算法的基本运算和操作:算术运算、逻辑运算、关系运算、数据传输

3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构

4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法

5、算法的复杂度主要包括:时间复杂度、空间复杂度

6、算法的时间复杂度:指执行算法所需要的计算工作量

7、算法的空间复杂度:指执行这个算法所需要的内存空间

8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算

9、数据结构研究的目的:提高数据处理的效率

10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间

11、数据处理:指对数据集合中的各元素以各种方式进行运算

12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素

13、数据结构:指反映数据元素之间关系的数据元素集合的表示

14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,

两要素:数据元素的集合、数据元素在集合上的关系

15、数据的存储结构:

指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等

16、数据结构的图形表示中每个元素加上方框成为结点

17、数据结构一般分为:线性结构、非线性结构

18、线性结构满足:

有且仅有一个根结点、每个结点最多有一个前件和后件、在一个线性结构中插入和删除任何一个结点后还是线性结构

 19、线性表定义:线性表是由n个数据元素a1、a2、a3、a4„„an组成的一个有限序列,

表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个

后件

20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无

后件、除了第一个和最后一个外,其他所有结点只有一个前件和一个后件

 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表

22、线性表的顺序存储的特点:所有元素所占的存储空间是连续的、各数据元素在存储空间中是按逻辑顺序一次存放的

23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k  24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转

25、栈的定义:栈是限定在一端进行插入和删除的线性表,它按照“先进后出,后进先出”

的原则组织数据

26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m为栈的最大容量

27、栈的基本运算:入栈、退栈、读栈顶元素

28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误

29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误

30、队列的定义:队列是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先

进先出”的原则组织数据

31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队

列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列

循环使用

32、循环队列空的状态:s=0,且front=rear=m 

循环队列满的状态:s=1,且front=rear 

33、循环队列的基本运算:入队、退队

34、入队运算:同样队列满时发生“上溢”错误

35、退队运算:同样队列空时发生“下溢”错误

36、线性链表的基本概念:线性表的链式存储结构

37、线性链表的存储结构:

线性链表的每个结点中数据域存放数据元素的值,指针域存放好后件结点的存储地址

38、双向链表的存储结构:

双向链表的存储结构比线性链表的存储结构多出一个指针域,它用来存放前面的存储地址

39、栈的链式结构:

栈的链式结构基本上和线性链表的链式存储结构相同。只是线性链表的链式存储结构的头指针变成了栈的链式结构的栈顶指针

40、队列的链式结构:

队列的链式结构和线性链表的存储结构基本相同。只是队列的链式结构保持有两个指针:一个指向队列头的头指针,一个指向队列尾的尾指针

41、线性链表的主要运算:插入、删除、合并、分解、逆转、复制、排列、查找

42、线性链表的特点

43、树结构中结点的类型:根结点、父结点、子结点、叶子结点

44、结点的度:一个结点所拥有的后件个数成为结点的度

45、树的度:在所有结点中最大的度数

46、树的深度:树的最大层,也就是树的高度

47、子树:子结点构成的树

48、二叉树的特点:一是非空二叉树只有一个根结点,二是每一个结点最多有两棵子树

49、二叉树的性质:①在二叉树的第k层上,最多有2的(k-1)次方个结点

 ②深度为m的二叉树最多有2的m次方减1个结点 

③在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个 

④具有n个结点的二叉树,其深度至少为[log2(n)]+1,其中[log2(n)]表示log2(n)的整数部分

50、满二叉树定义:除最后一层外,每一层上的所有结点都有两个子结点

51、完全二叉树定义:除最后一层外,每一层上的结点数均达到最大值,在最后一层上缺少

右边的若干结点

52:二叉树的存储结构:L(i)左指针域R(i)右指针域V(i)数据域

53:二叉树的遍历集中用到了递归的思想,主要有三种遍历方式:前序遍历,中序遍历,后

序遍历

54、查找技术分为:顺序查找、二分查找、

55、排序技术分为:

交换类排序(冒泡排序法和快速排序法)、插入类排序(简单插入排序

法和希尔排序法)、选择类排序(简单选择排序法和堆排序法)

2017-05-29 13:28:07 ljh_learn_from_base 阅读数 1010
数据结构与算法
1、 算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 
2、 算法的基本运算和操作:算术运算、逻辑运算、关系运算、数据传输 3、 算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 
4、 算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、 算法的复杂度主要包括:时间复杂度、空间复杂度 6、 算法的时间复杂度:指执行算法所需要的计算工作量 7、 算法的空间复杂度:指执行这个算法所需要的内存空间 
8、 数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、 数据结构研究的目的:提高数据处理的效率 
10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 
12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 
16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 
18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件和后件、在一个线性结构中插入和删除任何一个结点后还是线性结构 
19、线性表定义:线性表是由n个数据元素a1、a2、a3、a4„„an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件 
20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个和最后一个外,其他所有结点只有一个前件和一个后件 
21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间是连续的、各数据元素在存储空间中是按逻辑顺序一次存放的 
23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 
24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 
25、栈的定义:栈是限定在一端进行插入和删除的线性表,它按照“先进后出,后进先出”的原则组织数据 
26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m为栈的最大容量 
27、栈的基本运算:入栈、退栈、读栈顶元素 
28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 
29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 

31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用 
32、循环队列空的状态:s=0,且front=rear=m     循环队列满的状态:s=1,且front=rear 33、循环队列的基本运算:入队、退队 
34、入队运算:同样队列满时发生“上溢”错误 35、退队运算:同样队列空时发生“下溢”错误 36、线性链表的基本概念:线性表的链式存储结构 
37、线性链表的存储结构:线性链表的每个结点中数据域存放数据元素的值,指针域存放好后件结点的存储地址 
38、双向链表的存储结构:双向链表的存储结构比线性链表的存储结构多出一个指针域,它用来存放前面的存储地址 
39、栈的链式结构:栈的链式结构基本上和线性链表的链式存储结构相同。只是线性链表的链式存储结构的头指针变成了栈的链式结构的栈顶指针 
40、队列的链式结构:队列的链式结构和线性链表的存储结构基本相同。只是队列的链式结构保持有两个指针:一个指向队列头的头指针,一个指向队列尾的尾指针 
41、线性链表的主要运算:插入、删除、合并、分解、逆转、复制、排列、查找 42、线性链表的特点 
43、树结构中结点的类型:根结点、父结点、子结点、叶子结点 44、结点的度:一个结点所拥有的后件个数成为结点的度 45、树的度:在所有结点中最大的度数 
46、树的深度:树的最大层,也就是树的高度 47、子树:子结点构成的树 
48、二叉树的特点:一是非空二叉树只有一个根结点,二是每一个结点最多有两棵子树 49、二叉树的性质:①在二叉树的第k层上,最多有2的(k-1)次方个结点 ②深度为m的二叉树最多有2的m次方减1个结点 ③在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个 ④具有n个结点的二叉树,其深度至少为[log2(n)]+1,其中[log2(n)]表示log2(n)的整数部分 
50、满二叉树定义:除最后一层外,每一层上的所有结点都有两个子结点 
51、完全二叉树定义:除最后一层外,每一层上的结点数均达到最大值,在最后一层上缺少右边的若干结点 
52:二叉树的存储结构:L(i)左指针域R(i)右指针域V(i)数据域 
53:二叉树的遍历集中用到了递归的思想,主要有三种遍历方式:前序遍历,中序遍历,后序遍历 
54、查找技术分为:顺序查找、二分查找、 
55、排序技术分为:交换类排序(冒泡排序法和快速排序法)、插入类排序(简单插入排序法和希尔排序法)、选择类排序(简单选择排序法和堆排序法)

递推算法和实例

阅读数 30

数据结构于算法

阅读数 17

数据结构

阅读数 198

没有更多推荐了,返回首页