2012数据结构教案

吉林大学珠海学院教案2011～2012学年第2学期系(中心)计算机科学与技术系教研室课程名称数据结构主讲教师陈守孔、冯广慧吉林大学珠海学院教务处制教案讲授章节第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)例：矩阵乘法：nxnfor(i=0;in;i++)//(n+1)for(j=0;jn;j++)//n(n+1){c[i][j]=0；//n2for(k=0;kn;j++)//n2(n+1)c[i][j]=c[i][j]+a[i][k]*b[k][j];//n3}说明：各语句行后的数字是该语句重复执行的次数;本算法时间复杂度为O(n3)6.空间复杂度算法原地（就地）工作：若所用额外存储空间相对于输入数据量来说是常数，则称此算法为原地（就地）工作。本章节的教学重点、难点：1.重点是数据结构的基本概念2.难点是时间复杂度分析教学方法、教学手段：1.介绍到算法概念（45分钟）2.算法分析和举例（45分钟）使用教具：计算机和投影仪作业、讨论题、思考题：编写最优算法，从小到大依次输出顺序读入的三个整数。要求：最佳情况：比较2次，无移动；最差情况：比较3次，7次移动参考资料：1．陈守孔等著《算法与数据结构C语言版》机械工业出版社20072．陈守孔等著《算法与数据结构考研试题精析》机械工业出版社20083．严蔚敏等著《数据结构C语言版》清华大学出版社20054．D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社教案讲授章节第2讲线性表――顺序表授课时数2教学目的：1.理解非空线性结构的四个特征。2.线性表是重要的线性结构，要掌握线性表的定义。3.掌握线性表的操作在顺序表中的实现。教学内容（讲授提纲）1.非空线性结构的四个特征。2.线性表的定义3.给定线性表的逻辑结构就可以设计算法：（1）遍历线性表L（2）合并线性表1:设La和Lb是元素属于同一数据对象且非递减有序的两个线性表，现要求将两个线性表合并成一个新的非递减有序的线性表Lc。（3）合并线性表2:设La和Lb是元素属于同一数据对象的两个线性表，试将线性表Lb合并到线性表La中。要求Lb中元素和La中元素相同的不再合并。要分析为什么（2）和（3）的时间复杂度分别是O(m*n)和O(m+n)。4.线性表的顺序表示和实现#defineMAXSIZE100∥顺序表的最大容量typedefstruct{ElemTypedata[MAXSIZE];∥存放线性表的数组intlast;∥last是线性表的长度}SeqList;5.线性表的操作在顺序表中的实现。（1）定义的线性表的10个操作在顺序表中的实现。（2）分析在插入和删除操作中的时间复杂度。6.几个算法举例：（1）顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。（2）请写一个算法将顺序表（a1,...,an）逆置为(an,...,a1)。（3）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量）。（4）设将n（n1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移P（0Pn）个位置，即将R中的数据由（X0,X1,…,Xn-1）变换为（Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。解答：(1)算法设计思想：按照下标0到p-1、p到n-1、0到n-1的顺序，将这三段分别逆置，最后的结果即为所求。(2)voidleftshift(intR[],intp,intn)//将有n个元素的一维数组R的序列循环左移p(0pn)个位置{elemtypet;//t和数组R中的元素具有相同类型for(i=0;ip/2;i++)//逆置0..p-1段{t=R[i];R[i]=R[p-1-i];R[p-1-i]=t;}for(i=p;i(n+p)/2;i++)//逆置p..n-1段{t=R[i];R[i]=R[n-1-i+p];R[n-1-i+p]=t;}for(i=0;in/2;i++)//逆置0..n-1段，即整个数组逆置{t=R[i];R[i]=R[n-1-i];R[n-1-i]=t;}}//算法初始调用:leftshift(R,p,n)，各参数意义如上。(3)算法执行了两趟逆置，时间复杂度为O(n);用了一个辅助变量空间，空间复杂度为O(1)。讨论：若采用直接左移p位，空间复杂度仍为O(1)，但时间复杂度为O(np)。本章节的教学重点、难点：重点是顺序表的定义，基本操作的实现。难点是高效算法设计，例如国家2010年硕士研究生入学考试算法题就有5种解法教学方法、教学手段：1.开始到顺序表中各种操作实现（45分钟）2.顺序表算法举例（45分钟）使用教具：计算机和投影仪作业、讨论题、思考题：2.3分析在顺序存储结构下插入和删除结点时平均需要移动多少个结点。原2.16顺序表la与lb非递减有序，顺序表空间足够大。试设计一种高效算法，将lb中元素合到la中，使新的la的元素仍保持非递减有序。高效指最大限度地避免移动元素。改为2.16顺序表la非递减有序，lb非递增有序，顺序表空间足够大。试设计一种高效算法，将lb中元素合到la中，使新的la的元素仍保持非递减有序。高效指最大限度地避免移动元素。参考资料：1．陈守孔等著《算法与数据结构C语言版》机械工业出版社20072．陈守孔等著《算法与数据结构考研试题精析》机械工业出版社20083．严蔚敏等著《数据结构C语言版》清华大学出版社20054．D.E.Knuth著《计算机程序设计技巧》第一、三卷管纪文译国防出版社教案讲授章节第3讲单链表授课时数2教学目的：1从顺序存储结构的优缺点，引出链表的必要性。2.掌握链表的类型定义。3.掌握线性表的操作在单链表中的实现。4.掌握单链表的建立方法，特别是头插法和尾插法。5.了解单链表的应用。教学内容（讲授提纲）1顺序存储结构的缺点：插入和删除必须大量移动元素；必须预先确定空间；表空间不易扩充。2.链表的类型定义。typedefstructNode{ElemTypedata;structNode*next;}LNode，*LinkedList；几个概念：结点，首元结点，第一元素结点，头结点，指针，头指针3.掌握线性表的操作在单链表中的实现。ListInit(L)；ListLength(L)；ListGet(L,i);ListLocate(L,x);ListClear(L);ListEmpty(L)；ListPrior(L,e)；ListNext(L,e)；ListInsert(L,i,e);ListDelete(L,i);4.掌握单链表的建立方法，特别是头插法和尾插法。（1）头插法LinkedListLinkedListCreat1(){//用头插法建立带头结点的单链表LinkedListL;L=(LNode*)malloc(sizeof(LNode));//申请结点L-next=NULL;//初始化一个空链表，L为头指针scanf(&x);//x是和链表元素具有相同类型的变量while(x!=flag)//flag为结束输入的标志{p=(LNode*)malloc(sizeof(LNode));p-data=x;//输入元素值p-next=L-next;//链接到表中L-next=p;//插入到表头scanf(&x);//读入下一个元素的值}returnL;}（2）尾插法LinkedListLinkedListCreat2(){//用尾插法建立带头结点的单链表LinkedListL;L=(LNode*)malloc(sizeof(LNode));L-next=NULL;r=L;scanf(&x);while(x!=flag)//设置结束标志{p=(LNode*)malloc(sizeof(LNode);p-data=x;//赋值元素值r-next=p;//在尾部插入新结点r=p;//r指向新的尾结点scanf(&x);}r-next=NULL;//最后结点的指针域放空指针returnL;}（3）单链表的遍历voidprint(LinkedListla)//非递归{LinkedListp=la-next;while(p){printf(“%c，”,p-data);//正序输出p=p-next;}}voidout(LinkedListp)//递归{if(p){out(p-next);printf(“%c，”,p-data);//逆序输出}//若将以上两个语句位置调换，则正序输出}5.了解单链表的应用。举例1.：LinkedListUnion(LinkedListla，LinkedListlb){∥将非递减有序的单链表la和lb合并成新的非递减有序单链表lc，并要求利用原表空间举例2：已知一个带有表头结点的单链表，结点结构为(data,link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上