计算机考研小组(100)课件.ppt

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

2、结构。2谢谢观赏2019-5-183谢谢观赏2019-5-18基础基础 4谢谢观赏2019-5-185谢谢观赏2019-5-186谢谢观赏2019-5-187谢谢观赏2019-5-188谢谢观赏2019-5-189谢谢观赏2019-5-1810谢谢观赏2019-5-1811谢谢观赏2019-5-1812谢谢观赏2019-5-1813谢谢观赏2019-5-1814谢谢观赏2019-5-1815谢谢观赏2019-5-1816谢谢观赏2019-5-1817谢谢观赏2019-5-1818谢谢观赏2019-5-1819谢谢观赏2019-5-1820谢谢观赏2019-5-1821谢谢观赏2019-5-18

3、数据指针数据域指针域单链表结点结构单链表结点结构22谢谢观赏2019-5-18typedef struct node ET data; struct node *link ; NODE;结点的内存分配：结点的内存分配： （NODE *)malloc(sizeof(NODE)23谢谢观赏2019-5-1824谢谢观赏2019-5-1825谢谢观赏2019-5-1826谢谢观赏2019-5-1827谢谢观赏2019-5-1828谢谢观赏2019-5-1829谢谢观赏2019-5-1830谢谢观赏2019-5-1831谢谢观赏2019-5-1832谢谢观赏2019-5-18非空表（a)headhea

4、d空表（b)33谢谢观赏2019-5-1834谢谢观赏2019-5-1835谢谢观赏2019-5-1836谢谢观赏2019-5-1837谢谢观赏2019-5-18headllinkrlinkdata带头结点的双向链表带头结点的双向链表双向链表的结点结构双向链表的结点结构38谢谢观赏2019-5-1839谢谢观赏2019-5-1840谢谢观赏2019-5-1841谢谢观赏2019-5-1840 0 1 00 0 2 0 090 0 0 00 0 0 0 70 0 0 5 0 r c v Ma0Ma1Ma2Ma3Ma4Ma5Ma6A=42谢谢观赏2019-5-1840 9 0 00 0 0 0 0

5、0 2 0 0 01 0 0 0 50 0 0 7 0 r c v Mb0Mb1Mb2Mb3Mb4Mb5Mb6B=43谢谢观赏2019-5-1844谢谢观赏2019-5-18 行域行域 列域列域 值域值域 向下域向下域 向右域向右域45谢谢观赏2019-5-1846谢谢观赏2019-5-1847谢谢观赏2019-5-18栈底Bottom栈顶Top48谢谢观赏2019-5-1849谢谢观赏2019-5-1850谢谢观赏2019-5-1851谢谢观赏2019-5-18Top -1012345012345012345012346Top Top Top MAXLEN-1MAXLEN-1MAXLEN-1

6、MAXLEN-152谢谢观赏2019-5-1853谢谢观赏2019-5-1854谢谢观赏2019-5-1855谢谢观赏2019-5-1856谢谢观赏2019-5-18自由区lefttoprighttop0MAXLEN-157谢谢观赏2019-5-1858谢谢观赏2019-5-1859谢谢观赏2019-5-1860谢谢观赏2019-5-1861谢谢观赏2019-5-1862谢谢观赏2019-5-1863谢谢观赏2019-5-18a0, a1, a2, a3, a4, ,a i a n-1出队出队入队入队64谢谢观赏2019-5-1865谢谢观赏2019-5-1866谢谢观赏2019-5-1867

7、谢谢观赏2019-5-1868谢谢观赏2019-5-18活动记录进退栈示意图活动记录进退栈示意图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调用者调用者69谢谢观赏2019-5-18主函数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)=1

8、fact(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，然后再一一返回计算，最终得到结果。70谢谢观赏2019-5-18例例 汉诺塔汉诺塔传说在创世纪时，在一个叫传说在创世纪时，在一个叫BrahmaBrahma的寺庙里，有三个柱子，其中

9、的寺庙里，有三个柱子，其中一柱上有一柱上有6464个盘子从小到大依次叠放，僧侣的工作是将这个盘子从小到大依次叠放，僧侣的工作是将这6464个盘个盘子从一根柱子移到另一个柱子上。子从一根柱子移到另一个柱子上。 移动时的规则：移动时的规则： 每次只能移动一个盘子；每次只能移动一个盘子； 只能小盘子在大盘子上面；只能小盘子在大盘子上面； 可以使用任一柱子。可以使用任一柱子。当工作做完之后，就标志着世界永远和平。当工作做完之后，就标志着世界永远和平。x y zx y znn 171谢谢观赏2019-5-18分析：分析： 设三根柱子分别为设三根柱子分别为 x x，y, z , y, z , 盘子在盘子在

10、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谢谢观赏2019-5-1873谢谢观赏2019-5-1874谢谢观赏2019-5-1875谢谢观赏2019-5-1876谢谢观赏2019-5-1877谢谢观赏2019-5-1878谢谢观赏2019-5-1

11、879谢谢观赏2019-5-1880谢谢观赏2019-5-1881谢谢观赏2019-5-1882谢谢观赏2019-5-1883谢谢观赏2019-5-1884谢谢观赏2019-5-1885谢谢观赏2019-5-1886谢谢观赏2019-5-1887谢谢观赏2019-5-1888谢谢观赏2019-5-1889谢谢观赏2019-5-1890谢谢观赏2019-5-1891谢谢观赏2019-5-1892谢谢观赏2019-5-1893谢谢观赏2019-5-1894谢谢观赏2019-5-1895谢谢观赏2019-5-1896谢谢观赏2019-5-1897谢谢观赏2019-5-1898谢谢观赏2019-5-1899谢谢观赏2019-5-18100谢谢观赏2019-5-18101谢谢观赏2019-5-18102谢谢观赏2019-5-18103谢谢观赏2019-5-18104谢谢观赏2019-5-18105谢谢观赏2019-5-18106谢谢观赏2019-5-18107谢谢观赏2019-5-18108谢谢观赏2019-5-18