数据结构 第2版 宗大华 陈吉人 数据结构 课件-2

《数据结构 第2版 宗大华 陈吉人 数据结构 课件-2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表1.2.3.本章讲述内容：4.线性表的基本知识；线性表的顺序存储实现；线性表的链式存储实现（单链表、双链表、循环链表）；线性表的具体应用举例。2.1线性表的基本知识线性表的定义1.一组数据的逻辑结构呈线性关系时，称其为线性表。即所谓“线性表”，是由具有相同类型的有限多个数据元素组成的一个有序序列。若把一个线性表取名为L，里面有n（n≥0）个元素，每个元素用ai（1≤i≤n）表示，下标代表该元素在线性表中的位置，那么可以把线性表L记为：L=(a1,a2,…,ai,ai+1,…,an−1,an)..线性表的若

2、干概念2..线性表中数据元素的个数n，称为线性表的“长度”。当n=0时，表示线性表中不包含任何元素，称其为“空表”。若线性表L为空，则记为L=（）或L=Ø。.在线性表中，对任意一对相邻结点ai和ai+1（1≤i≤n−1），称ai为ai+1的“直接前驱”，称ai+1为ai的“直接后继”。aiai+1ai+1的直接前驱ai的直接后继.若线性表中元素的值与它的位置间存在联系，比如其元素的值是按递增顺序排列的，那么称这种线性表为“有序线性表”；若线性表中元素的值与它的位置之间没有特殊的联系，那么称这种线性表为“无序线性表”。

3、2.2线性表的顺序存储实现2.2.1顺序表线性表的特点3...有且仅有一个起始结点a1，它没有直接前驱，只有一个直接后继a2。.有且仅有一个终端结点an，它没有直接后继，只有一个直接前驱an−1。其余结点ai（2≤i≤n−1）都有且仅有一个直接前驱ai−1和一个直接后继ai+1。线性表上的常见处理4..创建一个新的线性表，或删除一个已经存在的线性表。.使线性表增长（即插入一个元素）、使线性表缩短（删除一个元素），增长或缩短后元素间仍将保持线性关系。.得到当前线性表里拥有的元素个数（测试出线性表的长度）。.查找到所需要

4、的线性表元素的值，读出这个值，或者对这个值进行修改。.从一个元素出发，得到它的前驱结点和后继结点。顺序表的定义1.采用顺序式存储结构存放线性表时，是把表中的数据结点按其逻辑次序依次存储在内存中的一块连续存储区里。这时，线性表中逻辑上邻接的两个数据结点，其存储结点在物理位置上也是相邻接的。以这种顺序存储结构实现的线性表，被称为“顺序表”。由于顺序表中任一个存储结点的位置可通过计算得到，所以对顺序表中的任一数据元素的访问，都可在相同的时间内实现，即可方便地实现随机访问。由于顺序表要占用内存中的连续存储区，因此为其分配一块

5、存储区域之后，在该区域里能够容纳的数据元素的个数是有限的。顺序表所占存储区大小2.在顺序式存储中，存储结点里不需要存放结点间的邻接关系，数据的存储结点大小与其数据结点大小相同。因此，顺序表所占的连续存储区，应该由数据结点所需的存储量以及数据结点的个数来决定。求顺序表任一存储结点地址的公式3.LOC(ai)=LOC(a1)+sizex(i-1)第i个存储结点的地址第1个存储结点的地址存储结点尺寸前面已有的结点个数a11a22a33aiiai+1i+1an-1n-1ann位置序号：结点内容：存储地址：LOC(a1)siz

6、eLOC(a1)+sizeLOC(a1)+sizex(i-1)空闲设存储结点的数据类型为elemtype，每个存储结点所需存储量为size，顺序表Sq第1个存储结点a1的起址为LOC(a1)。那么，顺序表Sq第i个存储结点ai的起址LOC(ai)可通过公式得到。顺序表的几个特点4....由于顺序表中元素之间是一种线性的逻辑关系，因此在往顺序表里插入或删除一个数据元素时，势必要对原有数据元素进行移动，以求维持这种线性关系。2.2.2顺序表的基本算法描述创建顺序表的算法算法2-1算法描述(1)Create_Sq(Sq，S

7、q_num，Sq_max){elemtypeSq[MAX*size];Sq_num=0;Sq_max=MAX;returnOk;}算法分析(2)算法讨论(3)算法说明一个类型为elemtype、名为Sq的数组，获得顺序表所需存储空间，分配的存储区尺寸为MAX*size。..Sq_max的作用，是为了在顺序表Sq上进行操作时，能与Sq_num比较，确保顺序表不发生越界行为。.Sq_num的作用，用来随时记录顺序表中当前存放的数据元素的个数。注意，Sq_max是顺序表的最大长度，表创建后，它是保持不变的常量；Sq_num

8、是顺序表内当前拥有的数据元素个数，随着数据元素的插入与删除，Sq_num将会不断地发生变化，但不能让它越过Sq_max。..顺序表里已有元素的下标是1～Sq_num。也就是说，通常顺序表里的元素可以表示成：Sq[1]～[Sq_num]。注意，若是用C语言里的数组来实现线性表，就要注意C语言的数组下标规定则是从0开始的。②③在顺序表指定位置后插入