新版计算机考研小组(100)培训课件.ppt

1、计算机考研小组计算机考研小组(100)(100)20102010年计算机考研基础班讲义年计算机考研基础班讲义精选1直观定义：数据结构是研究程序设计中计算直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一机操作的对象以及它们之间关系和运算的一门学科。门学科。数据结构是指数据之间的关系数据结构是指数据之间的关系 按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这就是数据结构。就是数据结构。精选2精选3基础

2、基础 精选4精选5精选6精选7精选8精选9精选10精选11精选12精选13精选14精选15精选16精选17精选18精选19精选20精选21数据指针数据域指针域单链表结点结构单链表结点结构精选22typedef struct node ET data;struct node *link;NODE;结点的内存分配：结点的内存分配：（NODE*)malloc(sizeof(NODE)精选23精选24精选25精选26精选27精选28精选29精选30精选31精选32非空表（a)headhead空表（b)精选33精选34精选35精选36精选37headllinkrlinkdata带头结点的双向链表带头结点

3、的双向链表双向链表的结点结构双向链表的结点结构精选38精选39精选40精选4140 0 1 00 0 2 0 090 0 0 00 0 0 0 70 0 0 5 0 r c v Ma0Ma1Ma2Ma3Ma4Ma5Ma6A=精选4240 9 0 00 0 0 0 00 2 0 0 01 0 0 0 50 0 0 7 0 r c v Mb0Mb1Mb2Mb3Mb4Mb5Mb6B=精选43精选44 行域行域 列域列域 值域值域 向下域向下域 向右域向右域精选45精选46精选47栈底Bottom栈顶Top精选48精选49精选50精选51Top -1012345012345012345012346To

4、p Top Top MAXLEN-1MAXLEN-1MAXLEN-1MAXLEN-1精选52精选53精选54精选55精选56自由区lefttoprighttop0MAXLEN-1精选57精选58精选59精选60精选61精选62精选63a0,a1,a2,a3,a4,a i a n-1出队出队入队入队精选64精选65精选66精选67精选68活动记录进退栈示意图活动记录进退栈示意图s=fact(1)=1*fact(0)=1s=fact(2)=2*fact(1)=2s=fact(3)=3*fact(2)=6s=fact(4)=4*fact(3)=24s=fact(5)=5*fact(4)=120fac

5、t(0)=1调用者调用者精选69主函数mani()N=fact(5)第一层调用n=5s=5*fact(4)第二层调用n=4s=4*fact(3)第三层调用n=3S=3*fact(2)第四层调用n=2S=2*fact(1)第五层调用n=1S=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24fact(5)=120输出s=120.00递归调用过程示意图递归调用过程示意图从图中可看到fact函数共被调用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)为主函数调用，其它则为在fact函数内调用。每一次递归调用并未立即

6、得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact结果为1，然后再一一返回计算，最终得到结果。精选70例例 汉诺塔汉诺塔传说在创世纪时，在一个叫传说在创世纪时，在一个叫BrahmaBrahma的寺庙里，有三个柱子，其中的寺庙里，有三个柱子，其中一柱上有一柱上有6464个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这6464个盘个盘子从一根柱子移到另一个柱子上。子从一根柱子移到另一个柱子上。移动时的规则：移动时的规则：每次只能移动一个盘子；每次只能移动一个盘子；只能小盘子在大盘子上面；只能小盘子在大盘子上面；可以使用任一柱子。可以使用任一柱子。

7、当工作做完之后，就标志着世界永远和平。当工作做完之后，就标志着世界永远和平。x y zx y znn 1精选71分析：分析：设三根柱子分别为设三根柱子分别为 x x，y,z,y,z,盘子在盘子在x x柱上，要移到柱上，要移到z z柱上。柱上。1 1、当、当n=1n=1时，盘子直接从时，盘子直接从 x x 柱移到柱移到 z z 柱上；柱上；2 2、当、当n1n1时时,则则设法将前设法将前n1n1个盘子借助个盘子借助z z，从，从x x移到移到y y柱上，柱上，把把 盘子盘子n n从从x x移到移到z z柱上；柱上；把把n1n1个盘子从个盘子从y y移到移到z z柱上。柱上。精选72精选73精选74精选75精选76精选77精选78精选79精选80精选81精选82精选83精选84精选85精选86精选87精选88精选89精选90精选91精选92精选93精选94精选95精选96精选97精选98精选99精选100精选101精选102精选103精选104精选105精选106精选107精选108