《数据结构--线性表--ppt课件-文档资料》由会员分享，可在线阅读，更多相关《数据结构--线性表--ppt课件-文档资料（103页珍藏版）》请在金锄头文库上搜索。
1、数据结构,主讲人: 张炜,第二章 线性表,在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使用，并不是一个陌生的概念。,基本内容 1 线性表的概念； 2 线性表两类存储结构和它们的类型定义； 3 在这些存储结构下，线性表的基本操作的算法； 学习要点： 1 了解线性表逻辑结构的特征; 2 重点掌握线性表的顺序存储结构和链式存储结构，它们如 何表达线性表中数据元素之间的结构关系；如何用C语言 描述它们的类型定义； 3 掌握在顺序存储结构下，线性表的基本操作的算法； 4 掌握在链式存储结构下，线性表的基本操作的算法； 5 能够从时间复杂度的角度，比较线性表
2、两类存储结构 的不同特点及适用场合；,第二章 线性表,线性表是n 个类型相同数据元素的有限序列，通常记作(a1,a2,a3, , an),2.1 线性表的概念,例1、数学中的数列（11，13，15，17，19，21） 例2、英文字母表（A, B, C, D, E Z ）。 例3、某单位的电话号码簿。,一、线性表的逻辑结构,电话号码簿是数据元素 的有限序列，每一数据 元素包括两个数据项， 一个是用户姓名，一个 是对应的电话号码。,2.1 线性表的概念,说明：设 A=(a1,a2,.,ai-1,ai,ai+1,an)是一线性表 1）线性表的数据元素可以是各种各样的，但同一线性表中的元素须是同一类型
3、的； 2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前趋，ai+1是ai的直接后继； 3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结 构特征的数据结构称为线性结构。线性表是一种线性数据结构； 4）线性表中元素的个数n称为线性表的长度，n=0时称为空表； 5）ai是线性表的第i个元素，称i为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号；,2.1 线性表的概念,设L=（a1,a2,.ai-1,ai,ai+1,an）是一线性表 1 初始化操作 InitList(&L) 功能：建立空的线性表
4、L； 2 销毁操作DetroyList(&L) 功能：回收为线性表L动态分配的存储空间； 3 置空操作ClearList(&L) 功能：L中已存在，重新将其置成空表； 4 判空操作ListEmpty(L) 功能：判断线性表L是否为空表，若为空表返回TRUE，否则返回FALSE； 5 求表长操作 ListLength(L) 功能：返回线性表L的表长；,二、线性表的基本操作,6 取元素操作：GetElem(L, i, 9 删除操作 ListDelete(&L, i, &e ) 功能：删除线性表L的第i个元素，并用e返回； 10 遍历操作 ListTraverse (&L,visit( ) ) 功能
5、：依次对线性表L的每一个元素调用函数visit( )。若visit( )失 败，则返回ERROR，否则返回OK；,说明 1 上面列出的操作，只是线性表的一些常用的基本操作； 2 不同的应用，基本操作可能是不同的； 例如：上面列出的删除操作Delete( &L, i, &e ), 功能是在线性表L中删除第i个元素，并用e返回其值。 在电话号码查询系统中，一旦某用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与给定元素e值相同的数据元素； 3 线性表的复杂操作可通过基本操作实现； 这有点类似于数中的情形，例如整数的基本操作
6、是+,-,/。如果要求某班同学的平均年龄则可利用+/实现，全班同学的平均年龄 =(age1+age2+age3+)/全班同学的人数,例如，我们要在设计一个电话号码询系统，显然这个系统至少要具备下列功能： 查询某人的电话号码； 在电话号码薄中，插入一新用户姓名及电话号码； 在电话号码薄中，删除已撤销的用户姓名及电话号码； 由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就是对线性表的查找、插入、删除操作，为了在计算机上实现上述功能，我们应该做什么呢？ 显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对这些信息进行加工处理，实现上述功能。,2.2 线性表的顺序存储和实现 一
7、、线性表的顺序存储结构顺序表 1. 线性表的顺序存储结构 2. 顺序表的类型定义 二、顺序表的基本操作算法 三、利用基本操作实现线性表的其他操作,为了存储线性表，至少要保存两类信息： 1）线性表中的数据元素； 2）线性表中数据元素的顺序关系；,2.2 线性表的顺序存储和实现,在计算机内部可以采用不同的方式来存储一个线性表，其中最简单的方式就是本节要讲的线性表的顺序存储结构。,线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。,用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存储顺序反映出来的,线性表(a1,a2a3,.an ) 的顺序存储结构,用顺序存储结构
8、存储的线性表: 称为顺序表,2.2 线性表的顺序存储和实现,一、线性表的顺序存储结构: 顺序表,1.线性表的顺序存储结构,2.2 线性表的顺序存储和实现,说明： 在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息； 假没线性表中每个数据元素占用 k 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：Loc(ai) = Loc(a1)+( i1)k 这里 Loc(ai)是第 i 个元素的存储位置, Loc( a1 ) 是第1个元素的存储位置，也称为线性表的基址；,2.2 线性表的顺序存储和实现
9、,2、顺序表的类型定义 以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？为此，我们用C语言对这种存储方式进行描述，我们知道C语言一维数组的机内表示也是顺序结构，因此，可借用C语言的一维数组实现线性表的顺序存储。,2.2 线性表的顺序存储和实现,顺序表的类型定义 #define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量 #define LISTINCREMENT 10 /线性表存储空间的分配增量 typedef struct ElemType * elem; /线性表存储空间基址 int length; /当前线性表长度 int listsi
10、ze; /当前分配的线性表存储空间大小(以sizeof(ElemType)为单位) SqList;,SqList ：类型名，SqList类型的变量是结构变量，它的三个域分别是： *elem： 存放线性表元素的一维数组基址； 其存储空间在初始化操作（建空表）时动态分配； length： 存放线性表的表长； listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。,2.2 线性表的顺序存储和实现,顺序表图示,存放线性表元素 的一维数组,设 A =（a1,a2 , a3 , . an ）是一线性表，L是SqList 类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：,2.2
11、 线性表的顺序存储和实现,二、顺序表的基本操作算法 回顾本书算法中常用到的两个C函数。 1) Malloc(int size) 功能：系统内存分配size个的存储单元，并返回该空间的基址。 使用方法： . int m = 100, float *p; p = (float*)malloc(m*sizeof(float ); 执行语句p=(float*) malloc(m*sizeof(float)，计算机将按float 类型变量所占空间的大小(一般为32bit)分配m*sizeof(float)个的存储单元,并将其基址赋值给指针变量p;,p,p = (float*) malloc(m*size
12、of(float) 图示,2.2 线性表的顺序存储和实现,调用free ( p ),调用free(p)图示,2) free ( p ) 功能：将指针变量p所指示的存储空间，回收到系统内存空间中去；,使用方法： . int m = 100; float *p; p = (float*) malloc(m*sizeof(float); / 一旦p所指示的内存空间不再使用， /调用free( ) 回收之 free(p);,2.2 线性表的顺序存储和实现,如何在顺序表 上实现线性表的基本操作？ 如何建空表？如何求表长？ 如何插入？删除？,？,设线性表用顺序表L存储，下面我们介绍用顺序表存储线性表时，各
13、种基本操作的算法。当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存中的顺序表进行操作。,2.2 线性表的顺序存储和实现,1）初始化操作 InitList_Sq( SqList ,初始化操作演示,2.2 线性表的顺序存储和实现,顺序表初始化,L.length,L.listsize,L.elem,0 LIST_INIT_SIZE,再演示一次,2.2 线性表的顺序存储和实现,初始化操作算法： Status InitList_Sq(SqList /InitList_Sq 算法2.3,2.2 线性表的顺序存储和实现,销毁操作图示,2 销毁操作 DetroyList ( SqList &
14、L) 功能：回收为顺序表动态分配的存储空间 主要步骤：调用free( ) 回收为顺序表动态分配的存储空间,2.2 线性表的顺序存储和实现,销毁顺序表,L.length,L.listsize,L.elem,=null,再演示一次,2.2 线性表的顺序存储和实现,销毁操作算法： Status DetroyList_Sq ( SqList /DetroyList_Sq,2.2 线性表的顺序存储和实现,置空操作图示,3、置空操作ClearList_Sq ( SqList / ClearList_Sq,2.2 线性表的顺序存储和实现,2.2 线性表的顺序存储和实现,置空操作图示,置空,再演示一次,取元素
15、操作图示,6 取元素操作 GetElem_Sq ( SqList L, int i, ElemType /GetElem_Sq 由于C语言的一维数组下标从0开始, 故线性表的第一个元素放在L.elem0，第i个素放L.elemi-1中，最后一个元素放在 L.elemL.length-1中。,2.2 线性表的顺序存储和实现,取元素操作,n LIST_INIT_SIZE-1,ai,再演示一次,2.2 线性表的顺序存储和实现,8 插入操作 ListInsert_Sq ( 插入操作示意图：,2.2 线性表的顺序存储和实现,为初学者易于理解插入算法主要步骤，这里简化了书上的插入算法2.4，对插入算法中表
16、空间已满的情况，只简单的返回出错（ERROR），在2.2的最后部分给出完整的插入算法。当然，应用中对各种情况的如何处理，要根据实际问题的需要来决定。,注意,2.2 线性表的顺序存储和实现,2.2 线性表的顺序存储和实现,插入操作图示,插入操作主要步骤： 1）i是否合法，若合法转2），否则算法结束，并返回ERROR； 2）L是否已满，若未满转3），否则算法结束，并返回ERROR； 3）将顺序表ai及之后的所有元素后移一个位置； 4) 将新元素写入空出的位置； 5）表长+1 ；,用鼠标单击 图中的绿字,Status ListInsert_Sq(SqList /ListInsert_Sq 算法2.4 a,插入操作算法,为初学者易于理解 插入算法，这里通过下标引用L.elem 中的元素。,2.
