数据结构教案

湖南涉外经济学院教案学院信息科学与工程学院系/教研室软件工程系课程名称数据结构主讲教师邹竞湖南涉外经济学院教案讲授章节第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个位置上的结点（k为正整数），若查找成功，算法输