数据结构授课教案-第2章

山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第二章线性表第一节线性表的类型定义线性表的逻辑结构定义和抽象数据类型定义。第二节线性表的顺序表示和实现顺序表的类型定义、查找、插入和删除。第三节线性表的链式表示和实现线性链表（单链表）的结构、类型定义、查找、插入和删除；带头结点的单链表；循环链表的结构，循环链表与单链表操作的区别；双向链表的结构、类型定义、插入和删除。目的要求目的：理解线性表的定义和实现。基本要求：了解线性表的逻辑结构和基本操作；理解循环链表和双向链表的概念和基本算法；掌握线性表的顺序存储结构及基本操作的实现、线性表的链式存储结构及基本操作的实现。重点顺序表的定义、查找、插入和删除；单链表的定义、查找、插入和删除，头结点的作用；循环链表的定义，循环链表的操作和单链表操作的区别；双向链表的定义、插入和删除。难点单链表的定义、插入和删除；带头结点和不带头结点的单链表的基本操作的区别。作业布置习题2参考书1.数据结构题集(C语言版),严蔚敏，清华大学出版社，2002。3.数据结构、算法与应用－C++语言描述，(美)SartajSahni著，汪诗林等译，机械工业出版社，2002。课型理论课学时分配复习分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟教学手段板书、课件总结分钟备注共8学时，包括2学时的习题课。注：课型一栏填写理论课、实验课、习题课等授课内容备注第二章线性表线性结构的特点：在数据元素的非空有限集中1.存在唯一的一个被称做“第一个”的数据元素；2.存在唯一的一个被称做“最后一个”的数据元素；3.除第一个之外，每个元素都只有一个前驱；4.除最后一个之外，每个元素都只有一个后继。2.1线性表的逻辑结构线性表是一种最简单的数据结构，它是一种线性结构。线性表是n(n=0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中:1)同一线性表中的数据元素必须具有相同数据类型，2)ai是线性表的第i个元素，称i为数据元素ai的序号3)相邻数据元素间存在序偶关系：将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。a1是表中第一个元素，它没有前趋；an是最后一个元素无后继；其余有且仅有一个直接前趋，有且仅有一个直接后继4)n为表长，n＝0时称为空表（）。5)线性表的数据元素，或者叫结点，或者叫记录，是独立的信息。它可以是一个数：例某校从1978年到1983年各种型号的计算机拥有量的变化情况可以用线性表表示为：（6，17，28，50，92，188）或一个符号，如英文字母表（A，B，…，Z）；也可以由若干个数据项组成：如：学生健康情况登记表如下：线性表的其他表示方式:1)二元组表示L=D,S，其中:D={a1,a2,a3,...an};S={R}R={a1,a2,a2,a3,a3,a4…an-1,an}2)图示表示线性表的基本操作：表的初始化存取操作：存、取线性表中第i个数据元素查找操作：在线性表中查找满足条件元素插入操作：在线性表的第i个元素之前插入删除操作：删除线性表的第i个元素遍历求表长说明：1)上面列出的操作，只是线性表的一些常用的基本操作；2)线性表的复杂操作可通过基本操作实现；2.2线性表的顺序存储和实现线性表的顺序存储结构:指的是用一组地址连续的存储单元依次存储线性表的数据元素，用物理上的相邻表示逻辑上的相邻。说明：在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（表示）出来；假设线性表中每个数据元素占用t个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：Loc(ai+1)=Loc(ai)+tLoc(ai)=Loc(a1)+(i–1)t顺序表特点：可随机存取一、顺序表的类型定义：几种方法：1)#defineListSize100typedefintElemType;ElemTypeList[ListSize];intlength;2)#defineListSize100typedefintElemType;ElemTypeList[ListSize];intlength;3)#defineListSize100typedefintElemType;typedefstruct{ElemTypedata[ListSize];intlength;}SqList;4)#defineLIST_INIT_SIZE100#defineLISTINCREAMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList二、顺序表上的基本操作1.插入功能：在顺序表v中的第i(1=i=n+1)个数据元素之前插入一个新元素x即：插入前线性表为(a1,a2,a3,…,ai-1,ai,,…an)；插入后,线性表长度为n+1,线性表为(a1,a2,a3,…,ai-1,x,ai,,…an)。注意两点：1第n至第i个元素（共n－i+1个）依次后移2表长增1，考虑溢出算法：#defineListSize100typedefintElemType;typedefstruct{ElemTypedata[ListSize];intlength;}SqList;intinsert_listSq(SqList&L,inti,ElemTypee){if(L.length=ListSize)return-1;/*溢出*/if(i1||iL.length+1)return(0);/*i值不合法*/for(j=L.length-1;j=i-1;j--)L.data[j+1]=L.data[j];/*结点移动*/L.data[i-1]=e;/*插入e*/L.length++;/*表长增1*/return1;/*插入成功，返回*/}/*第二种写法*/#defineListSize100typedefintElemType;ElemTypeVector[ListSize];intlength;intinsert_listSq(inti,ElemTypee){if(length=ListSize)return-1;/*溢出*/if(i1||ilength+1)return(0);/*i值不合法*/for(j=length-1;j=i-1;j--)Vector[j+1]=Vector[j];/*结点移动*/Vector[i-1]=e;/*插入e*/length++;/*表长增1*/return1;/*插入成功，返回*/}顺序表插入算法分析：平均移动数据元素的次数：这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度T(n)＝Ｏ(n)。1111s2)1(11)1(Eniniiininninp2.删除功能：在顺序表删除第i(1=i=n+1)个数据元素，将被删除元素值存入e,删除前线性表为(a1,a2,a3,…,ai-1,ai,,…an)；删除后,线性表长度为n－1,线性表为(a1,a2,a3,…,ai-1,ai+1,…an)。注意两点：1第i+1至第n个元素（共n－i个）依次前移2表长减1算法：#defineListSize100typedefintElemType;typedefstruct{ElemTypedata[ListSize];intlength;}SqList;intdelete_listSq(SqList&L,inti,ElemType&e){if(i1||iL.length)return(0);/*检查空表及删除位置的合法性*/e=L.data[i-1];/*取出第i个元素存入e*/for(j=i-1;j=L.length-2;j++)L.data[j]=L.data[j+1];/*结点移动*/L.length--;/*表长减1*/return1;/*删除成功，返回*/}顺序表删除算法分析设删除第i个元素的概率为Pi，当Pi=1/n，即为等概率情况，则平均移动数据元素的次数：这说明：在顺序表上做删除操作需移动表中一半的数据元素。显然时间复杂度T(n)＝Ｏ(n)。3.初始化空表#defineListSize100typedefintElemType;typedefstruct{ElemTypedata[ListSize];intlength;}SqList;voidinit_listSq(SqList&L){L.length＝0;return;}思考：采用其它的定义如何初始化空表？11121)(1)(Eniniideninninp三顺序表应用举例设有两个按元素值递增有序排列的顺序表A和B，请编写算法将A和B归并成一个按元素值递增有序排列的线性表C。voidmerge(SeqListA,SeqListB,SeqList&C){i=0;j=0;k=0;while(iA.length&&jB.length)if(A.data[i]B.data[j])C-data[k++]=A.data[i++];elseC-data[k++]=B.data[j++];while(iA.length)C-data[k++]=A.data[i++];while(jB.length)C-data[k++]=B.data[j++];C-length=k;}小结顺序表是线性表最简单的一种存储结构顺序表的特点：1通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；2可随机存取顺序表的元素；3顺序表的插入、删除操作要通过移动元素实现；2.3线性表的链式表示和实现由于顺序表的存贮特点是用物理上的相邻实现了逻辑上的相邻，优点是可以随机存取，但插入和删除操作会移动大量的结点。本节介绍线性表链式存储结构，它不需要用地址连续的存储单元来实现，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。2.3.1线性链表一线性链表的概念二线性链表的基本操作算法三线性链表的其它操作2.3.2循环链表2.3.3双向链表一双向链表的概念二双向链表的基本操作算法2.3.1线性链表一线性链表（单链表）的概念1线性链表用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。线性链表有关术语1)结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；1)结点的数据域：结点中用于保存数据元素的部分;2)结点的指针域：结点中用于保存数据元素直接后继存储地址的部分;3)头指针：用于存放线性链表中第一个结点的存储地址;4)头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；5)带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；通常用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L、H中。线性链表的类型定义typedefintelemtypetypedefstructnode{elemtypedata;structnode*next;}LNode，*LinkList；例：定义头指针变量：LinkListH；相当于定义了一个单链表H两个C函数1)malloc(intsize)功能：在系统内存中分配size个的存储单元，并返回该空间的基址。使用方法：p=(LinkList)malloc(sizeof(LNode));为p申请一个结点2)free(p)功能：将指针变量p所指示的存储空间，回收到系统内存空间中去。使用方法：free(p)二线性链表基本操作的