数据结构(第2章)讲义

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

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

2、表上删除与插入运算的实现。⒋教学难点：⑴链式存储的表示及其运算的实现；⑵头结点在链表中的作用；指针操作；⑶链表中删除、插入运算中的指针操作顺序；⑷双链表上指针的操作顺序。⒌教学时数：8学时9/3/20212数据结构讲义第二章线性表线性表是线性结构的基本形式2.1线性表的逻辑结构2.2线性表的顺序存储及运算实现2.3线性表的链式存储和运算实现2.4顺序表和链表的比较9/3/20213数据结构讲义数据结构的内容包括三个层次的五个“要素”9/3/20214数据结构讲义2.1线性表的逻辑结构线性表的定义线性表的基本操作9/3/20215数据结构讲义2.1线性表的逻辑结构线性表的定义线性

3、结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，记为：(a1，a2，…ai-1，ai，ai+1，…an)；其中：n为表长，n＝0时称为空表。表中相邻元素之间存在顺序关系：ai-1称为ai的直接前趋，ai+1称为ai的直接后继。a1，…an-1有且仅有一个直接后继；a2，…an有且仅有一个直接前趋。9/3/20216数据结构讲义2.1线性表的逻辑结构线性表的基本操作：①线性表初始化:Init_List(L)②求线性表长度:Length_List(L)③取表元:Get_List(L,i)④按值查找:

4、Locate_List(L,x)⑤插入操作:Insert_List(L,i,x)⑥删除操作:Delete_List(L,i)9/3/20217数据结构讲义借助于C++的类来定义一个线性表的抽象类型，线性表类的声明如下：ConstintMaxSize=…;TemplateClassSeqList{Public;intLength();TGet_List(i)；intLocate(Tx)；voidInsert(inti,Tx)；TDelete(i)；Private：Tdata[MaxSize];intlength;};9/3/20218数据结构讲义需要说明的是：某数

5、据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。在上面各操作中定义的线性表Ｌ仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构。9/3/20219数据结构讲义2.2线性表的顺序存储及运算实现线性表的顺序存储顺序表上基本运算的实现顺序表应用举例9/3/202110数据结构讲义2.2.1线性表的顺序顺序存储线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。存储的特点：物理上的相邻实现了逻辑相邻的表示。9/3/20211

6、1数据结构讲义顺序存储能随机访问第i个元素：设a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a１)+(i-1)*d1≤I≤nlast的作用？存储的特点：物理上的相邻实现了逻辑相邻的表示。9/3/202112数据结构讲义用C支持的数据类型将上面的存储思想描述出来：设数据元素的类型为：DataType，则：DataTypedata[MAXSIZE];intlast;从结构性上考虑，通常将data和last封装成一个结构作为顺序表的类型：typedefstruct{DataTypedata[MAXSIZE];intlas

7、t;}SeqList;9/3/202113数据结构讲义定义顺序表变量L：SeqListL;则线性表中的元素a1．．an存放在：L.data[0]．．L.data[L.last]中L.last是最后元素an的相对地址。9/3/202114数据结构讲义采用C/C++描述算法时定义一个指向SeqList类型的指针更方便：SeqList*L；L=(SeqList*)malloc(sizeof(SeqList));（或者L=newSeqList）//来获得线性表的存储空间//L中存放的是顺序表的地址注