数据结构讲义ppt课件.ppt

《数据结构讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、⒈教学内容：2.1线性表逻辑结构；2.2线性表的顺序存储及运算实现；2.3线性表的链式存储和实现。⒉教学目的：⑴理解线性表的定义及其运算；⑵理解顺序表和链表的定义、组织形式、结构特征和类型说明；⑶掌握在这两种表上实现的插入、删除和按值查找的算法；⑷了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。⒊教学重点：⑴线性表的定义及逻辑上的特点；⑵顺序表上插入、删除和定位运算的实现；⑶单链表的结构特点及类型说明；⑷头指针和头结点的作用及区别；⑸定位、删除、插入运算在单链表上的实现；⑹循环链表、双链表的结构特点，循环链表

2、、双链表上删除与插入运算的实现。⒋教学难点：⑴线性表与线性结构的联系与区别；⑵头结点在链表中的作用；指针操作；⑶删除、插入运算中的指针操作顺序；⑷双链表上指针的操作顺序。⒌教学时数：8学时（含习题课2学时）第二章线性表12.1线性表的逻辑结构线性表的定义线性表的基本操作22.1.1线性表的定义线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。线性表是具有相同数据类型的n(n>=0)个数据元素的有限序

3、列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中n为表长，n＝0时称为空表。表中相邻元素之间存在着顺序关系。将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。就是说：对于ai，当i=2，...，n时，有且仅有一个直接前趋ai-1.，当i=1，2，...，n-1时，有且仅有一个直接后继ai+1，而a1是表中第一个元素，它没有前趋，an是最后一个元素无后继。需要说明的是：ai为序号为i的数据元素（i=1,2,…,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情

4、况信息表中，它是用户自定义的学生类型；在字符串中，它是字符型；等等。32.1.2线性表的基本操作⑴线性表初始化：Init_List(L)初始条件：表L不存在操作结果：构造一个空的线性表⑵求线性表的长度：Length_List(L)初始条件：表L存在操作结果：返回线性表中的所含元素的个数⑶取表元：Get_List(L,i)初始条件：表L存在且1<=i<=Length_List(L)操作结果：返回线性表L中的第ｉ个元素的值或地址⑷按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。初始条件：线性表L存在操作结果：返回在

5、L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功;否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。⑸插入操作：Insert_List(L,i,x)初始条件：线性表L存在，插入位置正确(1<=i<=n+1,ｎ为插入前的表长)。操作结果：在线性表L的第i个位置上插入一个值为x的新元素，这样使原序号为i,i+1,...,n的数据元素的序号变为i+1,i+2,...,n+1，插入后表长=原表长+1。⑹删除操作：Delete_List(L,i)初始条件：线性表L存在，1<=i<=n。操作结果：在线性表L中删除序号为i的

6、数据元素，删除后使序号为i+1,i+2,...,n的元素变为序号为i,i+1,...,n-1，新表长＝原表长－１。需要说明的是：某数据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。在上面各操作中定义的线性表Ｌ仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构。42.2线性表的顺序存储及运算实现线性表的顺序存储顺序表上基本运算的实现顺序表应用举例52.2.1线性表的顺序顺序存储线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存

7、放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。设a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a１)+(i-1)*d1≤I≤n从结构性上考虑，通常将data和last封装成一个结构作为顺序表的类型：typedefstruct{datatypedata[MAXSIZE];intlast;}SeqList;62.2.2顺序表上基本运算的实现⒈顺序表的初始化顺序表的初始化即构造一个空表，对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，

8、将表中last指针置为－1，表示表中没有数据元素。7⒉插入运算线性表的插入是指在表的第i个位置上插入一个值为x的新元素：8插入算法的时间性能分析顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入x，从ai到an都要向下移动一个位置