课件计算机考研基础讲义数据结构基础

1、计算机考研小组计算机考研小组(100)(100)20102010年计算机考研基础班讲义年计算机考研基础班讲义http:/ 按某种关系组织起来的一批数据。以一按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这中，并在这些数据上定义一个运算集合，这就是数据结构。就是数据结构。基础基础 数据指针数据域指针域单链表结点结构单链表结点结构typedef struct node et data; struct node *link ; node;结点的内存分配：结点的内存分配： （node *)malloc(

2、sizeof(node)非空表（a)headhead空表（b)headllinkrlinkdata带头结点的双向链表带头结点的双向链表双向链表的结点结构双向链表的结点结构40 0 1 00 0 2 0 090 0 0 00 0 0 0 70 0 0 5 0 r c v ma0ma1ma2ma3ma4ma5ma6a=40 9 0 00 0 0 0 00 2 0 0 01 0 0 0 50 0 0 7 0 r c v mb0mb1mb2mb3mb4mb5mb6b= 行域行域 列域列域 值域值域 向下域向下域 向右域向右域栈底bottom栈顶toptop -101234501234501234501

3、2346top top top maxlen-1maxlen-1maxlen-1maxlen-1自由区lefttoprighttop0maxlen-1a0, a1, a2, a3, a4, ,a i a n-1出队出队入队入队活动记录进退栈示意图活动记录进退栈示意图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)=120fact(0)=1调用者调用者主函数mani()n=fact(5)第一层调用n=5s=5*fact(4)第二层调用n=

4、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函数内调用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact结果为1，然后再一一返回计算，最终得到结果。例例

5、汉诺塔汉诺塔传说在创世纪时，在一个叫传说在创世纪时，在一个叫brahmabrahma的寺庙里，有三个柱子，其中的寺庙里，有三个柱子，其中一柱上有一柱上有6464个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这6464个盘个盘子从一根柱子移到另一个柱子上。子从一根柱子移到另一个柱子上。 移动时的规则：移动时的规则： 每次只能移动一个盘子；每次只能移动一个盘子； 只能小盘子在大盘子上面；只能小盘子在大盘子上面； 可以使用任一柱子。可以使用任一柱子。当工作做完之后，就标志着世界永远和平。当工作做完之后，就标志着世界永远和平。x y zx y znn 1分析：分析： 设三根柱子分别为设三根柱子分别为 x x，y, z , y, z , 盘子在盘子在x x柱上，要移到柱上，要移到z z柱上。柱上。1 1、当、当n=1n=1时，盘子直接从时，盘子直接从 x x 柱移到柱移到 z z 柱上；柱上；2 2、当、当n1n1时时, , 则则设法将前设法将前n n1 1个盘子借助个盘