湖南涉外经济学院 教案 学 院 信息科学与工程学院 系/教研室 软件工程系 课程名称 数据结构 主讲教师 邹竞 湖南涉外经济学院 教 案 讲授章节 第 1 讲 绪论 授课时数 2 教学目的： 1. 了解数据结构课程的重要性和课程的基本要求，以及本课程涵盖的内容； 2. 掌握数据结构的基本概念； 3. 理解算法描述和简单的算法分析。 教 学 内 容（讲授提纲） 1. 从后序课（数据库、操作系统、编译原理、人工智能）的需要和考研两方面介绍数据结构课程的重要性。 2. 通过三个例子讲解数据结构研究的内容。 3. 介绍基本概念：数据的三个层次，数据结构的三个要素，数据结构的分类，四种存储结构，抽象数据类型，算法，算法的五个特性，对算法设计的要求，算法描述和算法分析，时间复杂度和空间复杂度。 4. 从“百钱买百鸡”(“一百元钱买一百支笔”)的算法例子说明选择算法的重要性： 方案1： for( i = 0; i < =100; i++) for( j = 0; j < =100; j++) for( k= 0; k< =100; k++) if(i+j+k==100 &&3*i+2*j+0.5*k==100) printf(“i=%d，j=%d，k=%d”,i,j,k) 方案2： for( i = 0; i < =20; i++) for( j = 0; j < =34-i; j++) if(3*i+2*j+(100-i-j) *0.5==100) printf(“i=%d,j=%d,k=%d”,i,j, 100-i-j); 方案1 内层循环超过 100 万次，在某机器上运行了50 分钟；方案2 的if 语句执行 525次，运行了2 秒钟，相差 1500 倍。 5. 算法分析举例 （1）常量阶：时间复杂度为 O(1) ++x; s=0; 语句频度为 1，时间复杂度为 O(1)。 for(j=1;j<=10000;++j) {++x; s+=x;} 语句频度为 10000，时间复杂度为 O(1)。 （2）对数阶：时间复杂度为 O(logn) s=0; for(j=1; j<=n; j*=2) s++; 语句频度为logn，所以时间复杂度为O(logn)。 （3）线性阶：时间复杂度为O(logn) S=0; for(j=1;j<=n;++j) s++; 语句频度为n，所以时间复杂度为O(n)。 （4）时间复杂度为O(nlogn) s=0; for(j=1;j<=n;j*=2) for(k=1;k<=n;++k) s++; 时间复杂度为O(nlogn) （5）平方阶：时间复杂度为O(logn) s=0; for(j=1;j<=n;++j) for(k=1;k<=n;++k) s++; 语句频度为n2，所以时间复杂度为O(n2)。 s=0; for(j=1; j<=n; j++) for(k=1;k<=j;++k) s++; 语句频度为n(n+1)/2，所以时间复杂度仍为O(n2)。 （6）立方阶：时间复杂度为O( n3) 例：矩阵乘法：n x n for(...
